Tóm tắt Luận án Nghiên cứu, phát triển một số phương pháp khai phá dữ liệu trên dữ liệu có cấu trúc
BỘ THÔNG TIN VÀ TRUYỀN THÔNG
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Hoàng Minh Quang
NGHIÊN CỨU, PHÁT TRIỂN MỘT SỐ PHƯƠNG PHÁP
KHAI PHÁ DỮ LIỆU TRÊN DỮ LIỆU CÓ CẤU TRÚC
Chuyên ngành : Hệ thống thông tin
Mã số: 09.48.01.04
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT
Hà Nội - Năm 2020
Công trình được hoàn thành tại:
Học Viện Công Nghệ Bưu chính Viễn thông
Người hướng dẫn khoa học:
1. GS. TS. Vũ Đức Thi
2. GS. TSKH. Nguyễn Ngọc San
Phản biện 1: ………………………………………………………
Phản biện 2: ………………………………………………………
Phản biện 3: ………………………………………………………
Luận án được bảo vệ trước Hội đồng chấm luận án cấp Học viện
họp tại:
Học viện Công nghệ Bưu chính Viễn thông
Vào hồi giờ …… ngày …… tháng …… năm ……
Có thể tìm hiểu luận án tại:
Thư viện Học viện Công nghệ Bưu chính Viễn thông
DANH MỤC CÔNG TRÌNH CÔNG BỐ
[1] János Demetrovics, Hoang Minh Quang, Nguyen Viet Anh, and Vu
Duc Thi. “An Optimization of Closed Frequent Subgraph Mining
Algorithm”. In: Cybernetics and Information Technologies 17.1
(2017), pp. 3–15.
[2] János Demetrovics, Hoang Minh Quang, Vu Duc Thi, and Nguyen
Viet Anh. “An Efficient Method to Reduce the Size of Consistent
Decision Tables”. In: Acta Cybernetica 23.4 (2018), pp. 1039–1054.
DOI: 10.14232/actacyb.23.4.2018.4.
[3] Hoang Minh Quang and Nguyen Ngoc Cuong. “Vấn đề phân loại
đa nhãn cho đồ thị”. In: Proceeding of the eleventh National
Symposium Fundamental and Applied Information Technology
Research. FAIR, Hanoi, Vietnam, 2018, pp. 567–574.
[4] Hoang Minh Quang, Vu Duc Thi, and Vu Thi Lan Anh. “Xây dựng
cây quyết định từ bảng quyết định nhất quán”. In: Proceeding of the
tenth National Symposium Fundamental and Applied Information
Technology Research. FAIR, Da Nang, Vietnam, 2017, pp. 633–640.
[5] Hoang Minh Quang, Vu Duc Thi, and Pham Quoc Hung. “Một số
vấn đề về khai phá đồ thị con thường xuyên đóng”. In: Proceeding of
the ninth National Symposium Fundamental and Applied Information
Technology Research. FAIR, Can Tho, Vietnam, 2016, pp. 471–479.
[6] Hoang Minh Quang, Vu Duc Thi, and Nguyen Ngoc San. “Some
algorithms related to consistent decision table”. In: Journal of
Computer Science and Cybernetics 33.2 (2017), pp. 131–142.
[7] Hoang Minh Quang, Vu Duc Thi, Kieu Thu Thuy, Dao Van Tuyet,
and Phan Trung Kien. “Khai phá cây con thường xuyên trên cơ sở dữ
liệu weblogs”. In: Proceeding of the eighth National Symposium
Fundamental and Applied Information Technology Research. FAIR,
Ha Noi, Vietnam, 2015, pp. 327–355.
1
MỞ ĐẦU
1. TỔNG QUAN LUẬN ÁN VÀ LÝ DO CHỌN ĐỀ TÀI
Khai phá dữ liệu lớn là một xu hướng phát triển công nghệ mang
tính cách mạng, ngày càng được ứng dụng rộng rãi, và đặc biệt còn
nhiều tiềm năng phát triển trên toàn thế giới. Khai phá dữ liệu lớn có
thể được ứng dụng để cải tiến công nghệ ở nhiều lĩnh vực quan trọng
như: y tế, giao thông, tài chính, giáo dục, nhằm đem lại lợi ích trong
việc hỗ trợ ra quyết định, cắt giảm chi phí, và tạo ra các sản phẩm,
dịch vụ mới.
Mặc dù việc khai phá dữ liệu lớn đem lại giá trị to lớn và ý nghĩa,
tuy nhiên, đây cũng là một lĩnh vực đòi hỏi công nghệ cao, đầu tư lớn,
với nhiều thách thức. Nguyên nhân xuất phát từ hai đặc trưng cơ bản
của dữ liệu lớn, đó là: tính lớn và tính đa dạng, phức tạp. Do độ lớn
của dữ liệu, việc khai phá thường mất nhiều thời gian và chi phí, độ
phức tạp tính toán của khai phá dữ liệu lớn thường là độ phức tạp hàm
mũ. Hơn nữa, vì dữ liệu lớn và phức tạp, nên việc khai phá dữ liệu
cần trích xuất được các thông tin cốt lõi để khai phá, thay vì xử lý cả
tập hợp dữ liệu lớn, có nhiều dữ liệu dư thừa, không mang giá trị hữu
ích. Do vậy, vấn đề cơ bản của xử lý dữ liệu lớn là cải tiến tốc độ xử
lý dữ liệu và tăng giá trị của dữ liệu được khai phá.
Với ý nghĩa thực tiễn to lớn của ngành khai phá dữ liệu lớn, nhiều
công trình khoa học đã tập trung nghiên cứu, phát triển các thuật toán
nhằm cải tiến việc xử lý dữ liệu. Một số hướng nghiên cứu chính của
các nhà khoa học trên thế giới trong việc khai phá dữ liệu như sau:
đánh chỉ mục và truy vấn dữ liệu, tìm kiếm theo từ khóa, so khớp đồ
thị, mô tả đồ thị lớn, khai phá các mẫu thường xuyên, phân cụm dữ
liệu, phân lớp dữ liệu, khai phá các dữ liệu phát triển theo thời gian.
Trong luận án này, nghiên cứu sinh tập trung vào cả hai bài toán
2
cơ bản của ngành xử lý dữ liệu lớn là: tăng giá trị của dữ liệu và tăng
tốc độ xử lý dữ liệu. Kết quả của luận án giúp nâng cao tính hiệu quả
và giảm chi phí của việc khai phá dữ liệu lớn. Cụ thể, nghiên cứu sinh
tập trung nghiên cứu, giải quyết hai bài toán: (i) một là các bài toán
liên quan đến rút gọn thuộc tính, rút gọn đối tượng, giảm dữ liệu dư
thừa, trích xuất được những dữ liệu nhỏ, đặc trưng, chính xác hơn,
nhằm xác định giá trị cốt lõi trong tập hợp dữ liệu lớn và phức tạp,
(ii) hai là bài toán tối ưu hóa tính toán, cải thiện tốc độ và chi phí tính
toán trong khai phá dữ liệu có độ phức tạp tính toán lớn như độ phức
tạp tính toán hàm mũ hay độ phức tạp tính toán trong thời gian không
đa thức.
2. MỤC TIÊU - ĐỐI TƯỢNG - PHẠM VI NGHIÊN CỨU
Mục tiêu nghiên cứu
Đặt mục tiêu giải quyết hai bài toán trên, nghiên cứu sinh nghiên
cứu, phát triển một số phương pháp khai phá dữ liệu trên dữ liệu có
cấu trúc, tập trung vào dữ liệu biểu diễn cấu trúc dạng bảng và dạng
đồ thị. Đối với dữ liệu dạng bảng, mục tiêu nghiên cứu là các bài
toán giảm dư thừa dữ liệu, rút gọn thuộc tính, rút gọn đối tượng để
thu được tập dữ liệu nhỏ hơn trong khi vẫn bảo toàn được tính chất rút
gọn thuộc tính, sinh cây quyết định trong khai phá dữ liệu lớn. Đối với
biểu diễn dữ liệu dạng đồ thị, mục tiêu nghiên cứu là tối ưu tính toán
các bài toán có độ phức tạp thời gian không đa thức xuống thời gian
đa thức sử dụng một số ràng buộc dữ liệu để có thể khám phá tri thức
từ dữ liệu trong thời gian chấp nhận được và các bài toán liên quan
đến khai phá các tập dữ liệu mà dạng biểu diễn đồ thị còn gặp khó
khăn trong khi đối với các dạng biểu diễn dữ liệu khác đã có phương
pháp thực hiện.
Đối tượng nghiên cứu
Trong luận án này, nghiên cứu sinh đặt trọng tâm khai phá dữ liệu
3
trên biểu diễn dữ liệu có cấu trúc dạng bảng quyết định nhất quán và
biểu diễn đồ thị của cơ sở dữ liệu đồ thị như biểu diễn dữ liệu cấu
trúc hóa học, biểu diễn dữ liệu sinh học, biểu diễn dữ liệu mạng máy
tính, mạng xã hội. Trên tập dữ liệu được lựa chọn, nghiên cứu sinh
phát triển một số thuật toán phục vụ khai phá dữ liệu lớn như giảm
dư thừa, rút gọn dữ liệu hoặc tối ưu tính toán về độ phức tạp thời gian
đa thức để đáp ứng thời gian khai phá dữ liệu cho phép đối với các
thuật toán mà thông thường cần giải quyết trong độ phức tạp thời gian
không đa thức.
Phạm vi nghiên cứu
Luận án tập trung vào hai đối tượng với phạm vi như: (i) bảng
quyết định nhất quán với các bài toán tìm một rút gọn thuộc tính
không heuristic, tìm một rút gọn đối tượng và sinh cây quyết định,
và (ii) cơ sở dữ liệu giao tác đồ thị với bài toán khai phá đồ thị con
thường xuyên đóng và phân loại đồ thị đa nhãn.
3. KẾT QUẢ - Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN
Trong luận án, nghiên cứu sinh đã nghiên cứu cải tiến một số
phương pháp khai phá dữ liệu đối với biểu diễn dữ liệu có cấu trúc
dạng bảng và dạng đồ thị. Các kết quả đạt được bao gồm:
1. Nghiên cứu rút gọn thuộc tính bảng quyết định nhất quán Tìm
được một rút gọn thuộc tính trong thời gian đa thức không sử
dụng heuristic như các phương pháp tìm một rút gọn thuộc tính
khác.
2. Nghiên cứu rút gọn đối tượng bảng quyết định nhất quán Tìm
được một rút gọn đối tượng trong thời gian đa thức mà vẫn bảo
toàn quá trình tìm tất cả các rút gọn thuộc tính.
3. Nghiên cứu cây quyết định Cải tiến phương pháp sinh cây quyết
4
định thực hiện nhanh hơn quá trình sinh cây quyết định của
thuật toán ID3.
4. Nghiên cứu khai phá đồ thị con thường xuyên đóng Chứng minh
vấn đề đẳng cấu đồ thị con giải quyết trong thời gian đa thức
trong khai phá đồ thị con thường xuyên đóng trong khi các
thuật toán khai phá đồ thị con thường xuyên đóng khác chưa
giải quyết được vấn đề đẳng cấu đồ thị con trong thời gian đa
thức.
5. Nghiên cứu phân loại đa nhãn cho đồ thị Xây dựng độ đo trên
dàn giao khái niệm áp dụng cho phân loại đa nhãn đồ thị sử
dụng lý thuyết Dempster-Shafer, trong khi các công trình phân
loại đa nhãn theo lý thuyết Dempster-Shafer khác phải xây dựng
độ đo dựa trên biểu diễn véctơ mà đồ thị không có biểu diễn
véctơ.
Các kết quả nghiên cứu của nghiên cứu sinh đều có chứng minh
tính đúng đắn và đầy đủ đã thể hiện ý nghĩa khoa học của luận án.
Ngoài ra, các kết quả này có thể áp dụng cho cả các vấn đề nghiên cứu
lẫn thực tiễn, các thuật toán nghiên cứu sinh đề xuất được áp dụng cho
các bộ dữ liệu UCI dataset hoặc NCI dataset như Balance scale, Kr-vs-
kp, Breast cancer, Car, Tic-tac-toe, Molecula, HIV AIDS, Chemical
compound, ... trong một số kết quả thử nghiệm.
3. CẤU TRÚC LUẬN ÁN
Cấu trúc luận án có 3 chương như sau:
• Chương 1. Kiến thức chuẩn bị: Chương này trình bày một số
các định nghĩa cơ sở, các định lý của các lý thuyết sẽ được áp
dụng vào các phương pháp phát triển các thuật toán trong luận
án này như lý thuyết tập thô, lý thuyết cơ sở dữ liệu quan hệ,
5
lý thuyết đồ thị, lý thuyết phân tích khái niệm chính thức, lý
thuyết về độ tin cậy, lý thuyết Dempster-Shafer.
• Chương 2. Chương này trình bày chi tiết về một số phương pháp
nghiên cứu sinh đề xuất trong việc phát triển các thuật toán khai
phá dữ liệu trên biểu diễn dữ liệu có cấu trúc dạng bảng như rút
gọn đối tượng trong thời gian đa thức, rút gọn thuộc tính không
heuristic trong thời gian đa thức và sinh cây quyết định với thời
gian thực hiện nhanh hơn thuật toán ID3, đồng thời nghiên cứu
sinh cũng chứng minh tính đúng đắn và đầy đủ của các phương
pháp này.
• Chương 3. Chương này trình bày một số phương pháp nghiên
cứu sinh đề xuất về khai phá dữ liệu trên biểu diễn dữ liệu cấu
trúc dạng đồ thị như bài toán khai phá đồ thị con thường xuyên
đóng và phân loại đồ thị đa nhãn theo lý thuyết Dempster-
Shafer. Trong bài toán khai phá đồ thị con thường xuyên đóng,
nghiên cứu sinh đề xuất phương pháp xác định đẳng cấu đồ
thị con trong thời gian đa thức và trong bài toán phân loại đa
nhãn đồ thị, nghiên cứu sinh đề xuất độ đo khoảng cách trên
dàn giao khái niệm phục vụ cho quá trình phân loại, đồng thời
nghiên cứu sinh cũng chứng minh tính đúng đắn và đầy đủ của
các phương pháp này.
1 KIẾN THỨC CHUẨN BỊ
1.1 Lý thuyết cơ sở dữ liệu quan hệ
Phần này trình bày một số định nghĩa trong cơ sở dữ liệu quan hệ.
Kết hợp với các định nghĩa của lý thuyết tập thô, các định nghĩa về
tập bằng nhau, hệ bằng nhau cực đại, khóa, phản khóa góp phần thực
6
hiện nhiệm vụ rút gọn thuộc tính và rút gọn đối tượng trên bảng quyết
định nhất quán.
1.2 Lý thuyết tập thô
Phần này trình bày một số khái niệm cơ bản về lý thuyết tập thô
như bảng thông tin, bảng quyết định, bảng quyết định nhất quán, quan
hệ bất khả phân biệt, phân hoạch, lớp tương đương, rút gọn, ma trận
phân biệt, tập lõi. Các định nghĩa này được áp dụng trong bài toán tìm
một rút gọn thuộc tính trong thời gian đa thức, tìm rút gọn đối tượng
trong thời gian đa thức và xây dựng cây quyết định từ bảng quyết định
nhất quán thu gọn cả hai chiều ngang và dọc dựa trên rút gọn thuộc
tính và rút gọn đối tượng.
1.3 Lý thuyết đồ thị
Phần này, nghiên cứu sinh trình bày một số định nghĩa về đồ thị
phục vụ cho thuật toán khai phá đồ thị con thường xuyên đóng và giải
quyết bài toán con của nó là đẳng cấu đồ thị con trong thời gian đa
thức với ràng buộc về sử dụng máy truy cập ngẫu nhiên, tính có thứ
tự của tập nhãn của đỉnh và cạnh.
1.4 Tập có thứ tự và dàn giao (lattices)
Tập có thứ tự và dàn giao là các khái niệm quan trọng trong việc
xác định mối liên quan giữa hai phần tử trong một tập hợp các phần
tử. Các khái niệm này là nền tảng xây dựng dàn giao khái niệm.
7
1.5 Phân tích khái niệm chính thức (FCA)
Phần này trình bày một số định nghĩa về ngữ cảnh chính thức, khái
niệm chính thức, mối quan hệ cha - con giữa các khái niệm chính thức
và dàn giao khái niệm. Từ những khái niệm này, nghiên cứu sinh đề
xuất xây dựng độ đo tương tự giữa hai đồ thị trên dàn giao khái niệm
phục vụ giải quyết bài toán phân loại đa nhãn trên đồ thị.
1.6 Biến đổi và đồng biến đổi Mobius
Biến đổi và đồng biến đổi Mobius được nghiên cứu sinh sử dụng
trong việc xây dựng các hàm như hàm cấp phát khối, hàm niềm tin
theo lý thuyết độ tin cậy Dempster-Shafer từ mối quan hệ trên dàn
giao khái niệm của các đồ thị để phục vụ bài toán phân loại đa nhãn
đồ thị sử dụng lý thuyết hàm niềm tin Dempster-Shafer.
1.7 Lý thuyết Dempster-Shafer
Phần này trình bày một số khái niệm cơ bản của lý thuyết Dempster-
Shafer. Áp dụng luật Dempster trong việc kết hợp các hàm cấp phát
khối và các hàm niềm tin thông qua tập các láng giềng của các đồ thị
theo độ đo dàn giao khái niệm để xác định tập nhãn cho một đồ thị
mới trong giải quyết bài toán phân loại đa nhãn cho đồ thị sử dụng lý
thuyết Dempster-Shafer.
2 KHAI PHÁ DỮ LIỆU DẠNG BẢNG
Nội dung của chương này dựa trên các công trình số [0], [0], [0]
trong danh mục công trình công bố của nghiên cứu sinh.
8
2.1 Rút gọn thuộc tính không heuristic
Tìm các rút gọn từ bảng quyết định là một trong các mục tiêu
chính trong xử lý thông tin. Nhiều nghiên cứu tập trung vào rút gọn
thuộc tính tức là làm giảm số cột trong bảng quyết định. Thật không
may là tìm tất cả các rút gọn thuộc tính trong một bảng quyết định là
vấn đề có độ phức tạp hàm mũ. Nghiên cứu sinh đề xuất một phương
pháp đi tìm một rút gọn thuộc tính trong thời gian đa thức không
theo phương pháp heuristic như các phương pháp khác. Thuật toán
AnAttributeReduct nghiên cứu sinh đề xuất tìm một rút gọn thuộc
tính được chứng minh tính đúng đắn và thực hiện thời gian đa thức.
Algorithm 1: AnAttributeReduct(DS)
Đầu vào: DS “ pU, C Y tdu, V, fq
Đầu ra : D P REDpCq
1 Er Ð EqualitySetpDSq;
2 Md Ð MaximalEqualitySystempDS, Erq;
3 C “ tc1, ..., cnu, H “ C;
4 foreach i “ 0; i ă n; i ` ` do
5
if EB P Md : H ´ ci`1 Ď B then
6
H “ H ´ ci`1
end
;
7
8 end
9 trả về D “ Hpnq (Hpnq là H khi vòng lặp kết thúc với
i “ n “ |C|);
Định lý 2.1. Hpnq P REDpCq.
Độ phức tạp tính toán thời gian của thuật toán AnAttributeReduct(DS)
4
không lớn hơn Op|C|ˆ|U| q. Có thể thấy được rằng nếu thay đổi thứ
9
tự các phần tử của tập C ở bước 3, có thể nhận được một rút gọn thuộc
tính khác từ bảng quyết định nhất quán DS.
2.2 Rút gọn đối tượng bảng quyết định nhất quán
Dựa trên lý thuyết tập thô và lý thuyết cơ sở dữ liệu quan hệ nghiên
cứu sinh đã đề xuất một phương pháp rút gọn các đối tượng của bảng
quyết định nhất quán mà vẫn bảo toàn vấn đề tìm tập tất cả các tập rút
gọn thuộc tính của bảng quyết định nhất quán.
Bổ đề 2.2. Cho bảng quyết định nhất quán DS “ pU, C Y tdu, V, fq
với C “ tc1, c2, ..., cnu, U “ tu1, u2, ..., umu. Xem DS như một
quan hệ r “ tu1, u2, ..., umu trên tập thuộc tính R “ C Y tdu.
Đặt Er “ tEij : 1 ď i ă j ď mu với Eij “ ta P R : apuiq “
apujqu.
Đặt Md “ tA P Er : d R A, EB P Er : d R B, A Ă Bu.
Thì Md “ pKdrq´1 với Kdr la họ các thuộc tính tối tiểu của thuộc tính
tdu trên quan hệ r.
Định nghĩa 2.1. Một rút gọn đối tượng của bảng quyết định nhất
quán DS “ pU, C Y tdu, V, fq là một bảng quyết định nhất quán
DS1 “ pU1, C Y tdu, V, fq, với REDpCq “ REDU pCq và:
1) U1 Ď U,
1
2) REDU pCq “ REDU pCq,
3) REDU pCq ‰ REDU1´tuupCq, @u P U1.
Định lý 2.3. DS1 “ pU1 “ Tpmq, C Y tdu, V, fq trong thuật toán
AnObjectReduct thỏa mãn ba điều kiện 1), 2) và 3) theo định nghĩa
2.1.
Rõ ràng số bước tính toán Er theo định nghĩa hệ bằng nhau
2
2
là ít hơn |U| . Số bước tính toán Md là ít hơn |Er| và |Er| ď
10
Algorithm 2: AnObjectReduct(DS)
Đầu vào: DS “ pU, C Y tdu, V, fq
Đầu ra : DS1 “ pU1, C Y tdu, V, fq
1 Er Ð EqualitySetpDSq;
2 MdU Ð MaximalEqualitySystempDS, Erq;
3 T “ U “ tu1, ..., umu;
4 foreach i “ 0; i ă |U|; i ` ` do
i`1
5
if MdT´u “ MdU then
6
T “ T ´ ui`1
;
7
end
8 end
9 trả về DS1 “ pU1 “ Tpmq, C Y tdu, V, fq (Tpmq là T sau
khi vòng lặp kết thúc với i “ m “ |U|);
|U|p|U| ´ 1q
. Do vậy, độ phức tạp thời gian tồi nhất của thuật toán
2
5
AnObjectReduct(DS) không lớn hơn Op|U| q. Có thể dễ dàng thấy
rằng nếu thay đổi trật tự các phần tử của tập vũ trụ U, có thể tìm được
một rút gọn đối tượng khác.
2.3 Xây dựng cây quyết định từ bảng rút gọn
Vấn đề xây dựng tất cả các cây quyết định từ bảng quyết định từ
một bảng quyết định DS là một vấn đề NP-đầy đủ bởi sẽ có |C|! sự
sắp xếp các thuộc tính để tạo cây quyết định. Các công trình xây dựng
cây quyết định đều là heuristic dựa trên một số độ đo chẳng hạn như
ID3 với Entropy và Gain. Nghiên cứu sinh đề xuất thuật toán sinh cây
quyết định theo độ đo hàm chứa của quan hệ bất khả phân biệt.
Định lý 2.4. Thủ tục RecursiveNodepDSq là đúng đắn.
11
Procedure RecursiveNode(DS)
1 Node Ð H;
2 if pp|U| ““ 1q||p|C Y tdu| ““ 0qq then
3
Node Ð Updq (nút lá);
4 else
5
bestAttribute Ð
ř
max p@pe P C Y tduq pINDpeq Ď INDpdqqq;
remainAttributes Ð pC Y tdu ´ bestAttributeq;
Node Ð bestAttribute;
6
7
8
9
Node.childs Ð tRecursiveNodepDS1qu;
pDS1 “ pU1 “ U : V aluepbestAttribute “
vq, pC Y tduq ´ bestAttribute, V, fqq,
p@v P V aluepbestAttributeqq;
10 end
11 trả về Node;
Định lý 2.5. Thuật toán IRDTpDSq là đúng đắn.
Thực nghiệm kết quả đánh giá các thuật toán rút gọn thuộc tính
(bảng 1) và rút gọn đối tượng (bảng 2) nghiên cứu sinh đề xuất trong
chương khai phá dữ liệu dạng bảng. Các kết quả thực nghiệm được
thực hiện nhanh với ngôn ngữ lập trình Nodejs, Javascript với một số
tập dữ liệu dạng txt từ kho dữ liệu UCI.
Thực nghiệm chỉ ra rằng tốc độ tính toán của thuật toán IRDT là
nhanh vượt trội so với thuật toán ID3 (bảng 3). Có thể dễ dàng nhận
thấy rằng vấn đề đếm số lượng phần tử trong các tập quan hệ bất khả
phân biệt là các phép tính toán số nguyên nên rõ ràng nhanh hơn tính
Entropy và tính Information Gain vốn là các công thức tính toán số
thực.
12
Algorithm 3: IRDT(DS)
Đầu vào: DS “ pU, C Y tdu, V, fq
Đầu ra : DecisionTreepDSq
1 Root Ð RecursiveNodepDS “ pU, C Y tdu, V, fqq;
2 trả về Root;
Bảng 1: Bảng thực hiện một rút gọn thuộc tính
Tập dữ liệu
Examples
Thuộc tính gốc Thuộc tính rút gọn Thời gian(s)
4
9
4
6
3
8
3
5
0.006
0.161
0.248
0.673
Breast cancer
Balance
Car Evaluation
3 KHAI PHÁ DỮ LIỆU ĐỒ THỊ
Nội dung chương này dựa trên các công trình số [0], [0], [0], [0]
trong danh mục công trình công bố của nghiên cứu sinh.
3.1 Khai phá đồ thị con thường xuyên đóng
Nghiên cứu sinh đề xuất một phương pháp khai phá mẫu đồ thị
con thường xuyên với việc kiểm tra đẳng cấu đồ thị con trong thời
gian đa thức với ràng buộc gán nhãn và thứ tự nhãn của cả đỉnh và
cạnh trong tất cả đồ thị của cở sở dữ liệu đồ thị. Thuật toán mới do
nghiên cứu sinh đề xuất cho việc khai phá các đồ thị con thường
xuyên đóng dựa trên chiến lược nhãn chuẩn hóa, mô hình máy truy
cập ngẫu nhiên (RAM) hoặc mô hình von Neumann và cách tiếp cận
13
Bảng 2: Bảng thực hiện rút gọn đối tượng
Tập dữ liệu
Đối tượng gốc Đối tượng rút gọn Thời gian(s)
Examples
Breast cancer
Balance
14
286
625
1728
6
2
6
9
0.005
0.158
0.171
0.771
Car Evaluation
Bảng 3: Bảng so sánh tốc độ thực hiện IDRT và ID3 (millisecond)
Datasets (Atts/Objs)
Examples (4/14)
ID3 (ms) IRDT (ms)
3
1
Breast cancer (9/286)
Car Evaluation (6/1728)
53
64
13
30
Apriori với tính đóng nhằm giảm bớt số lượng ứng viên và các đồ thị
con thường xuyên được sinh ra. Trong thuật toán mới, bài toán đồ thị
con đẳng cấu được giải quyết trong thời gian đa thức so với giải quyết
trong thời gian không đa thức trong các thuật toán hiện có. Thêm vào
đó nghiên cứu sinh cũng chỉ ra tính đúng đắn và độ phức tạp của thuật
toán mới được đề xuất.
Nhãn chuẩn hóa
Trong các công trình nghiên cứu của Huan, Yan 2003 đã chỉ ra
việc sử dụng biểu diễn duy nhất cho một đồ thị làm giảm thời gian
thực hiện khai phá đồ thị con thường xuyên.
Sinh tập ứng viên
Trong thuật toán mới, PSI-CFSM, xác định tất cả các FS2i , với
14
mọi đồ thị con đóng thường xuyên từ tập CSki´1, xây dựng tập đồ thị
con ứng viên Cki với độ phức tạp thời gian đa thức.
Kiểm tra đồ thị con đẳng cấu
Thuật toán PSI-CFSM cải tiến các bước kiểm tra đẳng cấu đồ thị
con bằng cách sử dụng kiểm tra đẳng cấu đồ thị con theo tìm kiếm
nhị phân trong mô hình máy truy cập ngẫu nhiên. Trong lý thuyết độ
phức tạp tính toán, sự phức tạp về thời gian của tìm kiếm nhị phân là
Oplognq trong đó n là số lượng ứng viên đồ thị con. Giả sử lực lượng
của các đồ thị con ứng viên là 2n thì số bước của phép kiểm tra đẳng
cấu đồ thị con bằng cách tìm kiếm nhị phân trên mô hình máy truy
cập ngẫu nhiên là log22n “ n và độ phức tạp của thời gian là Opnq.
Procedure TestIsomorphism(g P Ckj, Cki )
Đầu vào: g P Ckj, Cki
Đầu ra : true _ false
1 b Ð BinarySearch(tcodepCAMpg1 P
Cki qqu, codepCAMpgqq, 0, |Cki |);
2 if b ą 0 then
3
trả về true;
4 else
5
trả về false;
6 end
Bổ đề 3.1. Độ phức tạp tính toán của TestIsomorphism là Oplog2|Cki |q
Bổ đề 3.2. Thủ tục TestIsomorphismpg P Ckj, Cki q là đúng đắn.
Thuật toán PSI-CFSM
Trong thuật toán PSI-CFSM, bước đầu tiên là xây dựng mảng
được sắp xếp thứ tự theo trật tự của mã CAM của các đồ thị con
15
với 2 đỉnh (chỉ có một cạnh) 2-subgraph của đồ thị Gi trong cơ sở
dữ liệu đồ thị GD. Mảng được sắp xếp thứ tự này ký hiệu là C2i,
C2 “ tC2iu. Với mỗi phần tử u trong C2i, so sánh codeCAMpuq
với codeCAMpvq, v P tCj “ C2 ´ C2iu. Nếu codepCAMpuqq “
2
codepCAMpvqq thì tăng độ hỗ trợ của u lên 1. Nếu supu ě σ thì
đặt u vào trong FS2, FS2i . FS2 (FS2D) là tập các đồ thị con thường
xuyên 2-subgraphs của cơ sở dữ liệu đồ thị GD và FS2i là tập các đồ
thị con thường xuyên 2-subgraphs của đồ thị Gi P GD. Xây dựng một
vòng lặp với k ě 3 để tính Cki , FSk, FSki , CSk, CSki dựa trên thuật
toán PSI-CFSM.
Định lý 3.3. Thuật toán PSI-CFSM là đúng đắn.
3.2 Phân loại đa nhãn cho đồ thị
Denoeux 2012 đã đề xuất một phương pháp đề giảm độ phức tạp
tính toán trong thao tác và kết hợp các hàm khối, khi các hàm niềm
tin được xác định trên một tập con phù hợp của khung phân biệt được
kết hợp với cấu trúc dàn giao.
Xây dựng dàn giao khái niệm
Xây dựng dàn giao cho các đồ thị gi P GD sử dụng một bảng ngữ
cảnh chính thức theo định nghĩa ngữ cảnh chính thức bằng cách xây
dựng tập tất cả các đồ thị con thường xuyên đóng CS của cơ sở dữ
liệu đồ thị GD và coi tập CS là tập các thuộc tính còn cơ sở dữ liệu
đồ thị tập đối tượng. Mối quan hệ giữa tập đối tượng và tập thuộc tính
thể hiện qua việc một đồ thị Gi P GD có chứa một đồ thị con thường
xuyên đóng gj P CS thì đồ thị Gi và đồ thị con thường xuyên đóng
gj là có mối quan hệ với nhau.
Từ bảng ngữ cảnh chính thức, tìm ra tất cả các khái niệm chính
thức, xây dựng được một dàn giao khái niệm IcebergLattice.
16
Algorithm 4: PSI-CFSM(GD, σ = min_sup)
Đầu vào: Cơ sở dữ liệu đồ thị GD, σ = min_sup
Đầu ra : CS2, CS3, ..., CSk, các tập đồ thị con thường
xuyên đóng theo mức
1 Xây dựng mảng có thứ tự theo code(CAM) của C2i;
2 foreach u P C2i do
3
TestIsomorphism(u, Cj) và tìm supu ě σ để đặt u vào
2
trong FS2i , FS2D, CS2i và CS2;
4 end
5 k Ð 3;
6 while Combine(@CSki´1, @FS2i ) is not null do
7
8
9
Xây dựng mảng có thứ tự theo code(CAM) của Cki ;
foreach u P Cki do
TestIsomorphism(u, Cj) và tìm supu ě σ để đặt u
k
vào trong CSki và CSk;
10
Kiểm tra v P CSki´1 nếu supv “ supu thì xóa v khỏi
CSk´1
;
11
end
k Ð k ` 1;
12
13 end
Dựa trên định nghĩa dàn giao, dàn giao khái niệm thì Iceberglat-
tice CL sẽ luôn có phần tử cận trên nhỏ nhất và cận dưới lớn nhất
cho mỗi cặp phần tử trên dàn giao khái niệm. Từ dàn giao khái niệm,
định nghĩa một độ đo dựa trên khoảng cách tính theo số lượng cạnh
tính từ phần từ nhỏ nhất cận dưới lubpx, yq đến mỗi đỉnh x, y P CL
trên dàn giao khái niệm gọi là dpx, yq.
Định nghĩa 3.1. Đường đi giữa hai đỉnh x, y trên dàn giao khái niệm
CL là tổng các đường đi ngắn nhất từ lubpx, yq đến x và từ lubpx, yq
Tải về để xem bản đầy đủ
24 trang
15500
Free
Bạn đang xem 20 trang mẫu của tài liệu "Tóm tắt Luận án Nghiên cứu, phát triển một số phương pháp khai phá dữ liệu trên dữ liệu có cấu trúc", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- tom_tat_luan_an_nghien_cuu_phat_trien_mot_so_phuong_phap_kha.pdf
