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

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 nghiên cứu rút gọn thuộc tính bảng quyết định nhất quán; nghiên cứu cây quyết định, khai phá đồ thị con thường xuyên đóng; nghiên cứu phân loại đa nhãn cho đồ thị.

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

2.1 Kiến thức chuẩn bị

Lý thuyết cơ sở dữ liệu quan hệ 

Lý thuyết tập thô 

Lý thuyết đồ thị

Tập có thứ tự và dàn giao (lattices) 

Phân tích khái niệm chính thức (FCA) 

Biến đổi và đồng biến đổi Mobius 

Lý thuyết Dempster-Shafer 

2.2 Khai phá dữ liệu dạng bảng 

Đặt vấn đề 

Loại bỏ thuộc tính dư thừa

Rút gọn thuộc tính không heuristic

Rút gọn đối tượng bảng quyết định nhất quán 

Xây dựng cây quyết định từ bảng rút gọn 

Ví dụ thu gọn bảng và cây quyết định

Đánh giá thực nghiệm 

2.3 Khai phá dữ liệu đồ thị

Đặt vấn đề 

Khai phá đồ thị con thường xuyên đóng

  • Ý tưởng đề xuất 
  • Nhãn chuẩn hóa 
  • Sinh tập ứng viên
  • Kiểm tra đồ thị con đẳng cấu
  • Thuật toán PSI-CFSM

Phân loại đa nhãn cho đồ thị

  • Ý tưởng đề xuất 
  • Xây dựng dàn giao khái niệm
  • Thuật toán phân loại đa nhãn đồ thị

Ví dụ PSI-CFSM và phân loại đa nhãn

Đánh giá thử nghiệm 

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

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận án Tiến sĩ trên ---

Ngày:18/08/2020 Chia sẻ bởi:

CÓ THỂ BẠN QUAN TÂM