Luận án TS: 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

1. Mở đầu

1.1 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.

1.2 Đối tượng phạm vi nghiên cứu

Đối tượng nghiên cứu: đặt trọng tâm khai phá dữ liệu 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, 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.

2. Nội dung

3. Kết luận

Dữ liệu lớn là dữ liệu được thu thập từ nhiều miền, nhiều lĩnh vực do đó có đa dạng cấu trúc biểu diễn khác nhau. Các thuật toán khai phá dữ liệu chỉ có thể khai phá dữ liệu trên một tập dữ liệu thống nhất về kiểu dạng biểu diễn. Các cấu trúc dữ liệu khác nhau có thể biểu diễn dữ liệu dưới dạng đồ thị để thống nhất kiểu dạng cho các mục đích khai phá dữ liệu. Tuy nhiên, dữ liệu dạng đồ thị là một dạng dữ liệu phức tạp khi áp dụng các phương pháp khai phá dữ liệu sẽ gặp nhiều khó khăn do hầu hết các công bố khai phá dữ liệu đều có độ phức tạp thời gian không đa thức thậm chí là độ phức tạp hàm mũ. Trong luận án này, nghiên cứu sinh tập trung vào khai phá dữ liệu đồ thị con thường xuyên và phân loại đa nhãn đồ thị. Đối với bài toán khai phá đồ thị con thường xuyên, một vấn đề nổi cộm là xác định đẳng cấu đồ thị con thông thường có độ phức tạp không đa thức. Luận án đã giải quyết khai phá đồ thị con thường xuyên đóng bằng thuật toán PSI-CFSM trong đó vấn đề xác định đẳng cấu đồ thị con trong thời gian đa thức bằng cách áp dụng một số điều kiện ràng buộc về nhãn chuẩn hóa, máy truy cập ngẫu nhiên. Trong luận án, các đề xuất của nghiên cứu sinh về xác định đẳng cấu đồ thị con và xác định độ đo khoảng cách trên dàn giao khái niệm được chứng minh tính đúng đắn và đầy đủ cùng với thực nghiệm chứng tỏ thuật toán PSI-CFSM tối ưu thời gian hơn so với thuật toán gSpan trong khai phá đồ thị con thường xuyên.

4. Tài liệu tham khảo

Charu C Aggarwal, Yuchen Zhao and S Yu Philip. “On Clustering Graph Streams.” in: SDM. SIAM. 2010, pages 478–489.

Charu Aggarwal, Yan Xie and Philip S Yu. “Gconnect: A connectivity index for massive disk-resident graphs”. in: Proceedings of the VLDB Endowment 2.1 (2009), pages 862–873.

Rakesh Agrawal, Ramakrishnan Srikant andothers. “Fast algorithms for mining association rules”. in: Proc. 20th int. conf. very large data bases, VLDB. volume 1215. 1994, pages 487–499.

Bahman Bahmani, Ravi Kumar, Mohammad Mahdian and Eli Upfal. “Pagerank on an evolving graph”. in: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM. 2012, pages 24–32.....