Luận án tiến sĩ: Phương pháp khai phá dữ liệu trên dữ liệu có cấu trúc - Học viện CNTT

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 LUẬN ÁN TIẾN SĨ KỸ THUẬT Hà Nội – Năm 2020 luan an 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.04 LUẬN ÁN TIẾN SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. NGUYỄN NGỌC SAN Hà Nội - Năm 2020 luan an i LỜI CẢM ƠN Đầu tiên, nghiên cứu sinh xin được gửi lời cảm ơn sâu sắc tới hai người thầy hướng dẫn; GS. Vũ Đức Thi và GS. Nguyễn Ngọc San đã định hướng nghiên cứu và chỉ dẫn các giải pháp khoa học trong cả quá trình nghiên cứu sinh thực hiện luận án.

Nghiên cứu sinh xin gửi lời cảm ơn tới lãnh đạo và tập thể cán bộ Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt nam cùng phòng Khoa học dữ liệu và Ứng dụng nơi nghiên cứu sinh đang công tác. Nghiên cứu sinh cũng chân thành gửi lời cảm ơn tới TS. Nguyễn Việt Anh đã đọc và góp ý vào phiên bản dự thảo của luận án. Nghiên cứu sinh xin cảm ơn lãnh đạo, các nhà khoa học Học viện Công nghệ Bưu chính viễn thông đã tạo điều kiện, trợ giúp nghiên cứu sinh trong quá trình thực hiện luận án.

Nghiên cứu sinh cũng xin cảm ơn các bạn bè, đồng nghiệp, các nhà khoa học đã có những đóng góp quý báu cho luận án. Nghiên cứu sinh xin cảm ơn Cha, Mẹ đã động viên khuyến khích nghiên cứu sinh trong quá trình nghiên cứu học tập. Cảm ơn vợ Bùi Thị Thuý Hà và hai con Hoàng Hải Lâm và Hoàng Minh Thư, những hy sinh trong quá trình nghiên cứu sinh thực hiện luận án đã tạo động lực để nghiên cứu sinh cố gắng phấn đấu đến ngày hôm nay. luan an ii LỜI CAM ĐOAN Nghiên cứu sinh xin cam đoan những công trình công bố trong luận án này là kết quả của nghiên cứu sinh nghiên cứu dưới sự hướng dẫn khoa học của GS.

Vũ Đức Thi và GS. Nguyễn Ngọc San. Những kết quả được nghiên cứu sinh trình bày trong luận án này là mới, duy nhất và chưa từng được công bố trong bất kỳ công trình nào khác. Nghiên cứu sinh xin hoàn toàn chịu trách nhiệm trước lời cam đoan của mình.

Hà Nội, ngày 31 tháng 12 năm 2019. Nghiên cứu sinh Hoàng Minh Quang luan an iii MỤC LỤC LỜI CẢM ƠN. i LỜI CAM ĐOAN. ii DANH MỤC HÌNH VẼ.

v DANH MỤC BẢNG BIỂU. vi DANH MỤC THUẬT NGỮ. vii LỜI MỞ ĐẦU. 1 1 KIẾN THỨC CHUẨN BỊ 8 1.1 Lý thuyết cơ sở dữ liệu quan hệ .2 Lý thuyết tập thô .4 Tập có thứ tự và dàn giao (lattices) .5 Phân tích khái niệm chính thức (FCA) .6 Biến đổi và đồng biến đổi Mobius .7 Lý thuyết Dempster-Shafer.

20 2 KHAI PHÁ DỮ LIỆU DẠNG BẢNG 23 2.2 Loại bỏ thuộc tính dư thừa .3 Rút gọn thuộc tính không heuristic .4 Rút gọn đối tượng bảng quyết định nhất quán .5 Xây dựng cây quyết định từ bảng rút gọn .6 Ví dụ thu gọn bảng và cây quyết định .7 Đánh giá thực nghiệm .8 Kết luận chương. 59 luan an iv 3 KHAI PHÁ DỮ LIỆU ĐỒ THỊ 61 3.2 Khai phá đồ thị con thường xuyên đóng .3 Sinh tập ứng viên .4 Kiểm tra đồ thị con đẳng cấu .5 Thuật toán PSI-CFSM .3 Phân loại đa nhãn cho đồ thị .2 Xây dựng dàn giao khái niệm .3 Thuật toán phân loại đa nhãn đồ thị .4 Ví dụ PSI-CFSM và phân loại đa nhãn .5 Đánh giá thử nghiệm .6 Kết luận chương. 106 KẾT LUẬN, KIẾN NGHỊ. 107 DANH MỤC CÔNG TRÌNH CÔNG BỐ.

110 TÀI LIỆU THAM KHẢO. 112 luan an v DANH MỤC HÌNH VẼ 2.1 Cây quyết định được sinh ra từ thuật toán DecisionTree(DS) .1 Một cơ sở dữ liệu đồ thị giao tác GD .2 Cây đồ thị con thường xuyên: DFS Code Tree .3 Cây đồ thị con thường xuyên: CAM Tree .4 Dàn giao khái niệm CL của các đồ thị gi P GD .5 Sinh ứng viên và tỉa đồ thị con 2-subgraph theo PSI-CFSM .6 Sinh ứng viên và tỉa đồ thị con 3-subgraph theo PSI-CFSM .7 Tỉa các đồ thị con ứng viên: không thường xuyên, không thoả mãn DFSC. 105 luan an vi DANH MỤC BẢNG BIỂU 2.1 Bảng quyết định nhất quán gốc .2 Bảng quyết định không dư thừa thuộc tính từ bảng gốc 2.3 Một rút gọn đối tượng của bảng quyết định nhất quán 2.4 Một rút gọn thuộc tính miền dương của bảng 2.5 Kết hợp rút gọn đối tượng và thuộc tính của bảng 2.6 Bảng thực hiện một rút gọn thuộc tính .7 Bảng thực hiện rút gọn đối tượng .8 Bảng so sánh tốc độ thực hiện IDRT và ID3 (millisecond) .1 Quan hệ giữa đồ thị và tập tất cả đồ thị con thường xuyên đóng .2 Luật Dempster kết hợp các hàm cấp phát khối .3 Khai phá đồ thị con thường xuyên (đơn vị thời gian: giây). 106 luan an vii DANH MỤC THUẬT NGỮ Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt antikey phản khóa antisymmetry phản đối xứng attribute thuộc tính attribute reduct rút gọn thuộc tính belief function hàm niềm tin β lower distribution reduct rút gọn phân phối cận dưới β β upper distribution reduct rút gọn phân phối cận trên β binary relation quan hệ hai ngôi boudary vùng biên capacity sức chứa closed frequent subgraph đồ thị con thường xuyên đóng closed set tập đóng closure đóng closure system hệ đóng commonality function hàm tính chất chung complete lattice dàn giao khái niệm concept lattice dàn giao khái niệm conjugate liên hợp consistent nhất quán co-Möbius transform đồng biến đổi Möbius data mining khai phá dữ liệu decision table bảng quyết định Dempster’s rule of combination luật kết hợp Dempster domain value miền giá trị discernibility matrix ma trận phân biệt luan an viii equality set tập bằng nhau equivalent class lớp tương đương extent phạm vi plausibility function hàm sự thật frame of discernment khung phân biệt frequent subgraph đồ thị con thường xuyên focal element phần tử tiêu điểm formal concept khái niệm chính thức formal concept analysis (FCA) phân tích khái niệm chính thức formal context ngữ cảnh chính thức full family họ đầy đủ f-family họ f functional dependency phụ thuộc hàm Galois connection kết nối Galois graph đồ thị graph datatabase cơ sở dữ liệu đồ thị graph edit distance khoảng cách sửa đổi đồ thị greatest lower bound lớn nhất cận dưới indiscernibility relation quan hệ bất khả phân biệt information function hàm thông tin information system hệ thông tin intent ý định interval khoảng isomorphism đẳng cấu isomorphism subgraph đẳng cấu đồ thị con key khóa luan an ix k-subgraph k-đồ thị con labeled graph đồ thị được gắn nhãn lattice dàn giao least upper bound nhỏ nhất cận trên lexicographic order thứ tự quy định locally finite hữu hạn cục bộ lower approximation xấp xỉ dưới mass allocation function hàm cấp phát khối maximal commonality subgraph đồ thị con chung lớn nhất maxmimal equality system hệ bằng nhau cực đại minimal key khóa tối tiểu monotonicity đơn điệu Möbius transform biến đổi Möbius multi-label classification phân loại đa nhãn object đối tượng ordered set tập có thứ tự partial order thứ tự bộ phận partially ordered set tập thứ tự bộ phận partition phân hoạch positive region miền dương powerset tập tất cả các tập reduct rút gọn relfexivity phản xạ relation quan hệ relational database cơ sở dữ liệu quan hệ relational scheme lược đồ quan hệ luan an x rough set tập thô set system hệ thống tập hợp shortest path kernels các nhân đường đi ngắn nhất Sperner system hệ Sperner subconcept-superconcept relation quan hệ khái niệm con - khái niệm cha subgraph đồ thị con subset tập con supergraph đồ thị cha theory lý thuyết transitivity bắc cầu universal set tập vũ trụ upper approximation xấp xỉ trên variable precision rough set tập thô chính xác biến luan an 1 LỜI MỞ ĐẦU 1.

TỔNG QUAN LUẬN ÁN VÀ LÝ DO CHỌN ĐỀ TÀI Khai phá dữ liệu lớn [57] 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, [28], [63] 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á. Dữ liệu lớn, trước hết là độ lớn của dữ liệu được thu thập, tập hợp và lưu trữ trên một cụm hệ thống máy tính phân tán, không thể lưu trữ trên các máy tính độc lập, khó có thể khai phá được các giá trị tiềm ẩn.

Với dữ liệu lớn, thời gian truy xuất thông tin trong cả hai việc đọc và viết đều gặp khó khăn với một độ trễ cao. Nếu không tối ưu thời gian truy xuất, giảm tập hợp dữ liệu thành một tập con thì khó xử lý do khai phá luan an 2 dữ liệu yêu cầu phải đáp ứng trong thời gian nhất định không thể kéo dài hơn. Chẳng hạn không thể khai phá dữ liệu phòng chống xâm nhập máy tính trái phép trong khi việc truy xuất dữ liệu đã mất hàng tiếng đồng hồ chưa kể thời gian khai phá dữ liệu. Lúc đó kết quả khai phá dữ liệu sẽ không có ý nghĩa vì tội phạm đã vượt qua hệ thống an ninh và kịp gây ra tất cả tác động xấu.

Liên quan đến tính đa dạng của dữ liệu. Dữ liệu được thu thập từ nhiều nguồn nên kiểu biểu diễn của dữ liệu khác nhau.