TÌM KIẾM ẢNH THEO NGỮ NGHĨA DỰA TRÊN CẤU TRÚC iRS-TREE VÀ ONTOLOGY

Lê Thị Vĩnh Thanh và CS. Tập 131, Số 2A, 2022 170 Cải tiến phép toán tách nút trên cây iRS-Tree Cây iRS-Tree là một cấu trúc cây cân bằng động phát triển theo chiều từ lá dưới lên gốc. Việc nút 𝑁𝑖 bị tràn được xử lý bằng cách phân chia 𝑀 + 1 phần tử vào k nút (𝑘 ≥ 2). Thuật toán k-Means được sử dụng để thực việc phân hoạch 𝑀 + 1 phần tử thành 𝑘 nhóm. Sau đó mỗi nhóm sẽ được gán vào mỗi nút lá trên cây iRS-Tree có cùng cha với nút lá được tách. Khi quá trình phân tách xảy ra lan truyền đến nút trong thì thực hiện tách nút trong. Quá trình này có thể lan truyền đến nút gốc; khi nút gốc đầy thì một nút gốc mới sẽ được tạo ra và cây iRS-Tree phát triển thêm một bậc. Việc lựa chọn thuật toán k-Means vì ba lý do sau: (1) hiệu quả về thời gian thực thi; (2) độ chính xác cao; (3) không phụ thuộc vào thứ tự của các đối tượng. Thuật toán tách nút lá được trình bày như sau: Thuật toán 2. Tách nút trên cây Input: Nút lá cần tách 𝑆𝐿 Output: 𝑘 nút sau khi được tách (𝑘 ≥ 2) Function: KMSplitLeafiRST(𝑆𝐿) 1 Begin 2 Phân chia tập 𝑀 + 1 phần tử thành 𝑘 nút sử dụng phương pháp K-Means; 3 Khởi tạo số cụm với 𝑘 = 2; 4 Áp dụng k-Means trên tập M+1 phần tử để phân chia thành k cụm; 5 Tính toán vùng diện tích chồng lắ p giữa k vùng không gian; 6 𝑀𝑎𝑥 = 𝑂𝑣𝑒𝑟𝑙𝑎𝑝𝐴𝑒𝑟𝑎(𝑘); 7 𝑘𝑜𝑝𝑡 = 𝑘; 8 For 𝑘 = 3 to 𝑘𝑚𝑎𝑥 9 Áp dụng k-Means trên tập M+1 phần tử để phân chia thành k cụm; 10 Tính toán 𝑂𝑣𝑒𝑟𝑙𝑎𝑝𝐴𝑒𝑟𝑎(𝑘); 11 If 𝑂𝑣𝑒𝑟𝑙𝑎𝑝𝐴𝑒𝑟𝑎(𝑘) < 𝑀𝑎𝑥 then 12 𝑀𝑎𝑥 = 𝑂𝑣𝑒𝑟𝑙𝑎𝑝𝐴𝑒𝑟𝑎(𝑘); 13 𝑘𝑜𝑝𝑡 = 𝑘;