ĐẠI HC HU
TRƯỜNG ĐẠI HC KHOA HC
NGUYN TH ĐỊNH
PHÁT TRIN MÔ HÌNH TÌM KIM NH DA
TRÊN CU TRÚC KD-TREE
Ngành: Khoa hc máy tính
Mã s: 9480101
LUN ÁN TIẾN SĨ NGÀNH KHOA HC MÁY TÍNH
Ngưi hưng dn khoa hc
1. PGS. TS. Lê Mnh Thnh
2. TS. Văn Thế Thành
HU, NĂM 2023
Công trình được hoàn thành ti: Khoa Công ngh Thông tin,
Trường Đại hc Khoa hc, Đại hc Huế.
Người hướng dn khoa hc: PGS. TS. Lê Mnh Thnh
TS. Văn Thế Thành
Phn bin 1: PGS. TS. Trần Đăng Hưng, Trường Đại học Sư phạm
Hà Ni.
Phn bin 2: PGS. TS. H S Đàm, Trường Đại hc Công ngh,
Đại hc Quc gia Hà Ni.
Phn bin 3: TS. Hoàng Bo Hùng, Trung tâm Công ngh thông
tin, tnh Tha Thiên Huế.
Lun án s được bo v ti Hội đồng chm lun án cp
Đại hc Huế hp ti: ………………………………………...
………………………………………………………………..
Vào hi:….giờ….........ngày….........tháng….......năm.........
Có thm hiu lun án tại thư vin: Trung tâm thông tin thư viện,
Trường Đại hc Khoa học, Đại hc Huế.
1
M ĐẦU
1. Tính cp thiết ca lun án
D liu nh s được ng dng trong mt s bài toán như phân loại
bnh nhân qua nh nh MRI [75], nhn din đối tượng bng hình nh
[77], v.v. vy, nh s đã trở nên cn thiết đóng vai trò quan trọng
trong lĩnh vực tra cu thông tin và nhn diện đối tượng bng hình nh.
Mt cu trúc d liu lưu trữ được đề xuất đáp ứng nhu cầu gia tăng
d liu là cn thiết cho bài toán tìm kiếm nh, chng hạn như S-Tree
[38], C-Tree [52], KD-Tree [84], v.v. Trong lun án, cu trúc d liu
đa chiều KD-Tree được nghiên cu xây dng cho bài toán tìm kiếm
ảnh đã mang li kết qu kh quan, đáp ng kh năng lưu trữ khi d
liệu tăng trưởng theo thi gian, phù hp vi d liu véc-đặc trưng
hình nh, thi gian tìm kiếm ổn định.
2. Tng quan tình hình nghiên cu
Tìm kiếm nh s dng các k thut gom cm và phân lớp đã mang
li nhng kết qu kh quan trong thp niên va qua; trong đó một s
công trình đã s dng kết hp các k thut hc máy k-Means, k-NN,
DNN, CNN, v.v [26], [63], [64]. Hu hết các công trình này đều s
dng k thut phân lp gom cm thành các nhóm d liệu tương
đồng trưc khi thc hin tìm kiếm nh. Tuy nhiên, quá trình kết hp
các k thut hc máy cho bài toán tìm kiếm nh còn nhng hn chế v
mt s yếu t như: mở rng kh năng lưu trữ theo nhu cu d liệu tăng
trưng, gim thi gian tìm kiếm trên các tp d liu nh ln.
Tìm kiếm nh theo tiếp cn ng nghĩa sử dng ontology mt
hướng tiếp cn đã mang li nhiu kết qu kh quan trong thp niên va
qua. C th như Manzoor cng s (2015) [44] đã đ xut mt
phương pháp tìm kiếm nh theo ng nghĩa dựa trên ontology để truy
2
xut ng nghĩa hình ảnh liên quan đến ni dung tìm kiếm của người
dùng. Olfa Allani và cng s (2016) [4] đề xut mt h thng tra cu
nh tích hp ng nghĩa với các đặc trưng thị giác để xây dng mt
ontology cho vic tra cu t chc các thông tin ng nghĩa hình nh.
Trên cơ sở tng quan tình hình nghiên cứu các hướng tiếp cn bài
toán tìm kiếm nh; mt s định hướng được đề xut và ci tiến nhm
nâng cao độ chính xác cho bài toán tìm kiếm nh da trên cu trúc
KD-Tree. Cui cùng, kết hp KD-Tree Ontology để tìm kiếm nh
theo tiếp cn ng nghĩa được thc hin.
3. Mc tiêu ca lun án
Mc tiêu c th ca lun án gm: (1) nghiên cu cu trúc d liu
đa chiều KD-Tree; xây dng các thut toán thao tác trên KD-Tree t
chức lưu trữ véc-đặc trưng hình nh; (2) phát trin cu trúc KD-
Tree, đồng thi xây dng b sung ng nghĩa cho các bộ d liu
thc nghim nhm thc hin mô hình tìm kiếm nh theo tiếp cn ng
nghĩa; (3) phát trin hình tìm kiếm nh bng cách kết hp các
phương pháp hc có giám sát, bán giám sát để to ra hình phân lp
hình nh, gom cm d liu da trên cu trúc KD-Tree.
4. Đối tượng và phm vi nghiên cu
Đối tượng nghiên cu: (1) các phương pháp phân cụm và phân lớp
dữ liệu; (2) cấu trúc phân cụm dữ liu đa chiều; (3) cu trúc Ontology
và phát trin Ontology; (4) các tập ảnh đơn đối tượng, đa đối tượng.
Phm vi nghiên cu: (1) các phương pháp học máy: học giám
sát, và bán giám sát; (2) cấu trúc dữ liệu đa chiều KD-Tree; (3) các cải
tiến: iKD_Tree, KD-Tree lồng nhau, Re KD-Tree, RF KD-Tree; (4)
cấu trúc Ontology ngôn ngữ truy vấn SPARQL; (5) các tập ảnh
COREL, Wang, Caltech-101, Caltech-256, MS-COCO, Flickr.
5. Phương pháp nghiên cứu
3
Phương pháp thuyết: (1) Tng hp các công trình nghiên cu
liên quan đến tìm kiếm nh trong thi gian gần đây, quan tâm đến kết
qu ca các công trình s dng mô hình hc máy, tìm kiếm nh theo
ng nghĩa và các cấu trúc lưu trữ dng cây. Nghiên cứu phương pháp
làm giàu Ontology phát trin hình tìm kiếm nh theo tiếp cn
ng nghĩa. (2) Đề xut mô hình tìm kiếm nh theo tiếp cn ng nghĩa,
đánh giá thực nghiệm, so sánh độ chính xác tìm kiếm nh vi các công
trình cùng lĩnh vực đ có s điều chnh và ci tiến thích hp.
Phương pháp thc nghim: (1) Các chương trình được viết bng
ngôn ng cp cao cho các thut toán trên h thng máy tính cùng
cu hình. (2) D liu thc nghim làc b d liu nh chuẩn đã được
công b và s dng trong các công trình có kết qu. Mt s công vic
gm: trích xut đặc trưng hình ảnh cho các b d liu nh tiêu chun:
COREL [19], Wang [20], Caltech-101 [12], Caltech-256 [13], phát
hiện, phân đoạn ảnh đối tượng trích xut véc-đặc trưng bộ nh
MS-COCO [21], Flickr [22]. (3) Xây dng cu trúc d liệu, cài đặt
thuật toán và mô hình đề xut để thc nghim trên các b d liu nh
chun; so nh kết qu thc nghim trên cùng b d liu vi các công
trình đã công bố, so sánh kết qu thc nghim ca cùng mt b d liu
trên các mô hình đề xut để minh chứng tính đúng đắn hiu qu ca
cơ sở lý thuyết.
6. B cc ca lun án
Luận án được trình bày trong 139 trang, m đầu (08 trang), kết lun
và hướng phát trin (02 trang), danh mc các công trình khoa hc ca
tác gi liên quan đến lun án (1 trang), tài liu tham kho (07 trang),
lun án chia thành 3 chương. Chương 1 (21 trang) trình bày sở
thuyết cho tìm kiếm nh cu trúc KD-Tree. Chương 2 (36 trang)
trình bày mt s ci tiến cu trúc KD-Tree cho tìm kiếm. Chương 3