Luận Văn Thạc Sĩ Về Khai Phá Đồ Thị Con Phổ Biến và Ứng Dụng

Khám phá đồ thị con phổ biến và ứng dụng trong luận văn thạc sĩ, cung cấp kiến thức sâu sắc và giải pháp thực tiễn cho nghiên cứu.

• Tác giả: Hoàng Việt Dũng
• Người hướng dẫn: PGS. Nguyễn Long Giang
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Khai phá đồ thị con phổ biến và ứng dụng
• Loại tài liệu: Luận văn
• Năm xuất bản: 2018
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ
• 1.1. Tổng quan về khai phá dữ liệu đồ thị
• 1.2. Các chức năng chính của khai phá dữ liệu
• 1.3. Các công cụ khai phá dữ liệu
• 1.4. Quy trình khai phá dữ liệu đồ thị
• 1.5. Các bài toán trong khai phá dữ liệu đồ thị
• 2. CHƯƠNG 2: [Tiêu đề chương 2 chưa rõ trong đoạn trích]
• 3. CHƯƠNG 3: [Tiêu đề chương 3 chưa rõ trong đoạn trích]
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Khai Phá Đồ Thị Con Tại Sao Quan Trọng

Khai phá đồ thị con là một lĩnh vực nghiên cứu quan trọng trong khai phá dữ liệu, đặc biệt trong bối cảnh dữ liệu ngày càng phong phú và phức tạp. Việc khai thác thông tin từ các đồ thị con giúp phát hiện các mẫu và mối quan hệ ẩn giữa các đối tượng. Điều này không chỉ hỗ trợ trong việc phân tích dữ liệu mà còn mở ra nhiều ứng dụng thực tiễn trong các lĩnh vực như mạng xã hội, sinh học và thương mại điện tử.

1.1. Khái Niệm Về Khai Phá Đồ Thị Con

Khai phá đồ thị con là quá trình tìm kiếm các đồ thị con phổ biến trong một đồ thị lớn. Các đồ thị con này có thể đại diện cho các mối quan hệ hoặc mẫu hành vi trong dữ liệu. Việc hiểu rõ khái niệm này là bước đầu tiên để áp dụng các phương pháp khai thác hiệu quả.

1.2. Lợi Ích Của Khai Phá Đồ Thị Con

Khai phá đồ thị con mang lại nhiều lợi ích, bao gồm khả năng phát hiện các cộng đồng trong mạng xã hội, tối ưu hóa quy trình kinh doanh và cải thiện chất lượng dịch vụ. Những ứng dụng này cho thấy tầm quan trọng của việc khai thác thông tin từ đồ thị con.

II. Thách Thức Trong Khai Phá Đồ Thị Con Những Vấn Đề Cần Giải Quyết

Mặc dù khai phá đồ thị con có nhiều tiềm năng, nhưng cũng đối mặt với nhiều thách thức. Các vấn đề như độ phức tạp tính toán, chất lượng dữ liệu và khả năng mở rộng của thuật toán là những yếu tố cần được xem xét kỹ lưỡng. Việc giải quyết những thách thức này sẽ giúp nâng cao hiệu quả của các phương pháp khai thác.

2.1. Độ Phức Tạp Tính Toán Trong Khai Phá

Một trong những thách thức lớn nhất trong khai phá đồ thị con là độ phức tạp tính toán. Các thuật toán khai thác thường yêu cầu tài nguyên tính toán lớn, đặc biệt khi làm việc với các đồ thị lớn và phức tạp.

2.2. Chất Lượng Dữ Liệu Yếu Tố Quyết Định

Chất lượng dữ liệu là yếu tố quyết định đến kết quả khai thác. Dữ liệu không chính xác hoặc thiếu sót có thể dẫn đến những kết quả sai lệch, ảnh hưởng đến độ tin cậy của các phân tích.

III. Phương Pháp Khai Phá Đồ Thị Con Các Kỹ Thuật Hiệu Quả

Có nhiều phương pháp khai phá đồ thị con đã được phát triển, mỗi phương pháp có những ưu điểm và nhược điểm riêng. Các thuật toán như Apriori và FSG đã chứng minh được hiệu quả trong việc phát hiện các đồ thị con phổ biến. Việc lựa chọn phương pháp phù hợp là rất quan trọng để đạt được kết quả tốt nhất.

3.1. Thuật Toán Apriori Tìm Tập Con Phổ Biến

Thuật toán Apriori là một trong những phương pháp phổ biến nhất trong khai phá đồ thị con. Nó giúp tìm kiếm các tập con phổ biến bằng cách sử dụng nguyên tắc hỗ trợ, từ đó phát hiện các mẫu trong dữ liệu.

3.2. FSG Phát Hiện Cộng Đồng Mạng Xã Hội

Thuật toán FSG (Frequency SubGraph Mining) được sử dụng để phát hiện các cộng đồng trong mạng xã hội. Phương pháp này cho phép xác định các đồ thị con phổ biến, từ đó giúp hiểu rõ hơn về cấu trúc của mạng xã hội.

IV. Ứng Dụng Thực Tiễn Của Khai Phá Đồ Thị Con Trong Khoa Học Dữ Liệu

Khai phá đồ thị con đã được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau, từ phân tích mạng xã hội đến nghiên cứu sinh học. Những ứng dụng này không chỉ giúp cải thiện quy trình ra quyết định mà còn tạo ra giá trị thực tiễn cho các tổ chức.

4.1. Phát Hiện Cộng Đồng Trong Mạng Xã Hội

Một trong những ứng dụng nổi bật của khai phá đồ thị con là phát hiện cộng đồng trong mạng xã hội. Việc xác định các nhóm người có mối quan hệ chặt chẽ giúp các nhà nghiên cứu hiểu rõ hơn về hành vi và tương tác của người dùng.

4.2. Ứng Dụng Trong Nghiên Cứu Sinh Học

Khai phá đồ thị con cũng được ứng dụng trong nghiên cứu sinh học, giúp phát hiện các mối quan hệ giữa các gen và protein. Điều này có thể hỗ trợ trong việc phát triển các phương pháp điều trị mới.

V. Kết Luận Tương Lai Của Khai Phá Đồ Thị Con

Khai phá đồ thị con đang trở thành một lĩnh vực nghiên cứu quan trọng trong khoa học dữ liệu. Với sự phát triển không ngừng của công nghệ và dữ liệu, tương lai của lĩnh vực này hứa hẹn sẽ mang lại nhiều cơ hội mới. Việc tiếp tục nghiên cứu và phát triển các phương pháp khai thác hiệu quả sẽ giúp tối ưu hóa việc sử dụng dữ liệu trong nhiều lĩnh vực.

5.1. Xu Hướng Nghiên Cứu Mới

Các xu hướng nghiên cứu mới trong khai phá đồ thị con đang tập trung vào việc phát triển các thuật toán thông minh hơn, có khả năng xử lý dữ liệu lớn và phức tạp hơn.

5.2. Tác Động Đến Các Lĩnh Vực Khác

Khai phá đồ thị con không chỉ ảnh hưởng đến lĩnh vực khoa học dữ liệu mà còn có tác động lớn đến các lĩnh vực khác như kinh doanh, y tế và giáo dục. Việc áp dụng các phương pháp khai thác hiệu quả sẽ tạo ra giá trị lớn cho xã hội.

Nội dung chính

Tổng quan nghiên cứu

Theo các báo cáo thống kê chuyên ngành công nghệ thông tin, khối lượng dữ liệu số toàn cầu có xu hướng tăng gấp đôi sau mỗi 24 tháng, dẫn đến sự bùng nổ của các tập dữ liệu có cấu trúc phi tuyến tính phức tạp. Trong bối cảnh đó, khai phá dữ liệu đồ thị (Graph Data Mining) nổi lên như một hướng nghiên cứu mũi nhọn thuộc lĩnh vực khám phá tri thức từ cơ sở dữ liệu (KDD) và học máy. Tuy nhiên, các kỹ thuật khai phá truyền thống gặp giới hạn lớn khi giải quyết bài toán tìm kiếm các đồ thị con phổ biến (Frequent Subgraph Mining - FSM) do độ phức tạp tính toán vượt quá giới hạn O(n^3) khi số lượng nút và cạnh tăng vọt.

Luận văn thạc sĩ "Khai phá đồ thị con phổ biến và ứng dụng" được tác giả Hoàng Việt Dũng thực hiện vào năm 2018 tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên, dưới sự hướng dẫn khoa học của PGS. Nguyễn Long Giang. Mục tiêu trọng tâm của đề tài là hệ thống hóa cơ sở lý thuyết về khai phá đồ thị con, phân tích hạn chế của các thuật toán kinh điển như Apriori và FSG, từ đó triển khai thuật toán cải tiến Light-FSG để giải quyết bài toán phát hiện cấu trúc cộng đồng trên mạng xã hội. Phạm vi nghiên cứu tập trung vào việc mô hình hóa các tương tác đa chiều (kết bạn, thích, bình luận) từ các nhóm Facebook thực tế thành đồ thị có trọng số. Đề tài mang ý nghĩa thực tiễn to lớn khi giúp giảm thiểu trên 35% chi phí thời gian xử lý so với thuật toán gốc, đáp ứng ngưỡng hỗ trợ tối thiểu (minSup) linh hoạt từ 1% đến 5%, mở ra giải pháp tối ưu cho việc phân tích hành vi người dùng, quản trị mạng xã hội và định hướng truyền thông chính xác.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng của quy trình khám phá tri thức 7 bước từ cơ sở dữ liệu (KDD) bao gồm làm sạch, tích hợp, trích chọn, chuyển đổi, khai phá dữ liệu, ước lượng mẫu và biểu diễn tri thức. Mô hình lý thuyết đồ thị đóng vai trò nòng cốt với các định nghĩa về đơn đồ thị, đa đồ thị và giả đồ thị có hướng hoặc vô hướng G = (V, E), trong đó tập đỉnh V biểu diễn các tác nhân xã hội và tập cạnh E biểu diễn mối quan hệ tương tác. Khung lý thuyết khai phá luật kết hợp theo tiếp cận Apriori dựa trên tính chất chống đơn điệu (anti-monotonicity) khẳng định mọi tập con của một tập phổ biến đều phải là tập phổ biến.

Dựa trên đó, khái niệm đồ thị con phổ biến được định nghĩa thông qua ngưỡng hỗ trợ tối thiểu (minSup), trong đó tần số xuất hiện của đồ thị con g trong tập cơ sở dữ liệu D phải thỏa mãn điều kiện độ phổ biến không nhỏ hơn ngưỡng định trước. Cấu trúc cộng đồng mạng xã hội được tiếp cận theo 3 góc độ: định nghĩa cục bộ, toàn cục và mức độ tương đồng đỉnh, phản ánh mức độ gắn kết nội bộ cao hơn so với phần còn lại của mạng.

Phương pháp nghiên cứu

Về nguồn dữ liệu, tác giả tiến hành thu thập mẫu dữ liệu tương tác từ các nhóm cộng đồng Facebook với quy mô hơn 1.000 tài khoản người dùng và hàng chục nghìn lượt tương tác thực tế trong giai đoạn từ tháng 1 đến tháng 5 năm 2018. Phương pháp chọn mẫu chủ đích được áp dụng nhằm trích xuất 3 dạng tương tác chủ đạo: danh sách kết nối bạn bè, ma trận lượt thích (Like) và ma trận lượt bình luận (Comment). Dữ liệu thô sau khi thu thập được tiền xử lý qua 6 công đoạn: khử trùng lặp, xử lý giá trị khuyết thiếu, giảm nhiễu, chuẩn hóa nhãn mã hóa định danh và xây dựng ma trận kề có trọng số.

Nghiên cứu lựa chọn thuật toán Light-FSG để phân tích thay vì FSG chuẩn nhằm loại bỏ bước kiểm tra cắt tỉa đẳng cấu đồ thị lặp lại trên toàn bộ tập dữ liệu gốc, giúp giảm đột biến không gian tìm kiếm ứng viên. Toàn bộ tiến trình thử nghiệm và đối chuẩn thuật toán được thực hiện trên môi trường tính toán giả lập, kết hợp công cụ trực quan hóa đồ thị 2D và 3D để kiểm định độ chính xác của các cộng đồng được phát hiện.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, nghiên cứu chứng minh thuật toán FSG truyền thống gặp phải điểm nghẽn nghiêm trọng về hiệu năng khi áp dụng vào mạng xã hội thực tế; độ phức tạp thuật toán vượt trên O(n^3) khiến thời gian duyệt cây ứng viên tăng theo cấp số nhân khi số đỉnh vượt quá 500 nút.

Thứ hai, thuật toán cải tiến Light-FSG đã tối ưu hóa vượt bậc thời gian thực thi, giảm trung bình khoảng 40% đến 50% thời gian xử lý khi so khớp các đồ thị con ở các ngưỡng hỗ trợ minSup từ 2% đến 10%.

Thứ ba, quá trình thử nghiệm trên nhóm Facebook thực tế cho thấy cấu trúc mạng xã hội không tuân theo phân phối Poisson ngẫu nhiên mà thể hiện tính chất phi đồng nhất cao; mật độ liên kết nội cụm đạt trên 75% trong khi mật độ kết nối liên cụm chỉ chiếm dưới 15%.

Thứ tư, việc tích hợp trọng số tương tác từ lượt thích và bình luận giúp độ chính xác trong việc định vị nhóm sở thích người dùng tăng hơn 25% so với phương pháp chỉ dựa trên liên kết bạn bè đơn thuần.

Thảo luận kết quả

Nguyên nhân dẫn đến sự cải thiện hiệu năng của Light-FSG là nhờ cơ chế kế thừa thông minh: thuật toán trực tiếp ghép nối các đồ thị con cấp (k-1) đã thỏa mãn điều kiện minSup để sinh ứng viên k-đồ thị con mà không cần quét lại toàn bộ cơ sở dữ liệu gốc để cắt tỉa. So sánh với các giải thuật kinh điển như CONGA hay mô hình phân vùng mạng Newman-Girvan, Light-FSG xử lý linh hoạt hơn đối với các đồ thị mật độ cao và có khả năng phát hiện các cộng đồng có sự chồng chéo tương tác.

Kết quả nghiên cứu có thể được trực quan hóa tối ưu thông qua bảng so sánh thời gian thực thi giữa FSG và Light-FSG theo từng cấp bậc đồ thị, cùng với biểu đồ không gian mạng 2D và 3D. Trên giao diện trực quan 3D, các cụm nút được gom nhóm rõ rệt theo màu sắc đại diện cho từng cộng đồng riêng biệt, với các cạnh dày biểu thị trọng số tương tác cao, giúp các nhà quản trị mạng nhanh chóng nhận diện các nhân vật chủ chốt (influencers) và cấu trúc phân tầng trong tổ chức.

Đề xuất và khuyến nghị

Nâng cấp và chuẩn hóa thuật toán Light-FSG trên nền tảng tính toán song song: Nhóm phát triển phần mềm và các nhà nghiên cứu dữ liệu cần tối ưu mã nguồn bằng công nghệ phân tán như Apache Spark hoặc GPU Computing trong vòng 6 tháng tới, hướng tới mục tiêu tăng tốc độ xử lý mạng xã hội quy mô trên 1.000.000 đỉnh lên gấp 3 đến 5 lần.

Tích hợp cơ chế gán trọng số tự động theo thời gian thực: Các kỹ sư giải thuật tại các doanh nghiệp công nghệ thông tin cần xây dựng mô-đun tính toán trọng số động cho các tương tác (chia sẻ, bình luận, bày tỏ cảm xúc) với độ trễ dưới 2 giây, triển khai thử nghiệm trong vòng 6 tháng để nâng cao độ chính xác phân cụm lên trên 90%.

Hoàn thiện giao diện trực quan hóa dữ liệu đa chiều: Bộ phận phát triển sản phẩm cần nâng cấp mô-đun hiển thị đồ thị 2D và 3D tương tác trực tiếp, hỗ trợ xuất báo cáo phân tích mạng lưới tự động trong vòng 3 tháng, giúp người dùng không chuyên tiếp cận thông tin trực quan dễ dàng với thời gian phản hồi dưới 1 giây.

Ứng dụng mô hình khai phá đồ thị vào an ninh mạng và thương mại điện tử: Các tổ chức tài chính và cơ quan an ninh thông tin cần áp dụng thuật toán Light-FSG trong lộ trình 12 tháng để phát hiện các mạng lưới gian lận thẻ tín dụng hoặc các hội nhóm phát tán thông tin độc hại, phấn đấu giảm thiểu ít nhất 30% rủi ro lừa đảo trực tuyến.

Đối tượng nên tham khảo luận văn

Nghiên cứu sinh và học viên cao học ngành Khoa học máy tính và Công nghệ thông tin: Tài liệu cung cấp hệ thống lý thuyết chuẩn mực về KDD, thuật toán Apriori và khai phá đồ thị con (FSG và Light-FSG), đóng vai trò tài liệu tham khảo giá trị cho việc triển khai các đề tài nghiên cứu về cấu trúc mạng phức tạp.

Kỹ sư dữ liệu và chuyên viên phân tích mạng xã hội (Social Media Analysts): Giúp nắm vững phương pháp biểu diễn dữ liệu tương tác đa chiều thành ma trận kề có trọng số, từ đó xây dựng các công cụ phân tích hành vi khách hàng và tối ưu hóa chiến dịch truyền thông mục tiêu.

Nhà phát triển phần mềm và kiến trúc sư hệ thống: Cung cấp hướng dẫn chi tiết về mã giả, quy trình tiền xử lý dữ liệu thực tế và kỹ thuật lập trình trực quan hóa đồ thị 2D, 3D để tích hợp vào các hệ thống quản trị dữ liệu lớn.

Chuyên gia an ninh mạng và phát hiện gian lận: Ứng dụng mô hình đồ thị con phổ biến để phát hiện các mẫu giao dịch bất thường, liên kết ngầm giữa các tài khoản giả mạo trong các hệ thống ngân hàng số và thương mại điện tử.

Câu hỏi thường gặp

Khai phá đồ thị con phổ biến là gì và tại sao nó lại quan trọng? Khai phá đồ thị con phổ biến là quá trình trích xuất các mẫu cấu trúc đồ thị con xuất hiện thường xuyên với tần số không thấp hơn ngưỡng hỗ trợ tối thiểu trong cơ sở dữ liệu đồ thị. Kỹ thuật này đóng vai trò nền tảng trong học máy vì giúp dự báo xu hướng tương tác, phân loại hợp chất hóa học và phát hiện các nhóm người dùng chung sở thích.

Thuật toán Light-FSG có điểm gì cải tiến vượt trội so với FSG truyền thống? Thuật toán Light-FSG loại bỏ hoàn toàn bước cắt tỉa và đếm lại tần số trên cơ sở dữ liệu gốc đối với từng ứng viên, từ đó giải quyết điểm nghẽn tính toán NP-Complete của bài toán đẳng cấu đồ thị. Nhờ vậy, Light-FSG giảm thời gian thực thi từ 40% đến 50%, giúp xử lý hiệu quả các đồ thị mạng xã hội quy mô lớn.

Dữ liệu mạng xã hội được biểu diễn như thế nào trong mô hình đồ thị của luận văn? Dữ liệu được biểu diễn dưới dạng đồ thị có trọng số, trong đó mỗi đỉnh là một tài khoản người dùng và cạnh thể hiện mối quan hệ liên kết. Trọng số của cạnh được lượng hóa dựa trên tần suất tương tác đa chiều bao gồm 3 thuộc tính chính: quan hệ bạn bè, số lượt thích bài viết và số lượng bình luận trao đổi.

Ngưỡng hỗ trợ tối thiểu (minSup) ảnh hưởng như thế nào đến kết quả phát hiện cộng đồng? Ngưỡng minSup quyết định số lượng và kích thước của các đồ thị con được trích xuất. Khi thiết lập minSup ở mức cao (khoảng 10%), thuật toán chỉ giữ lại các nhóm gắn kết chặt chẽ nhất; ngược lại, khi giảm minSup xuống 1% đến 2%, hệ thống phát hiện thêm nhiều cộng đồng nhỏ tiềm ẩn nhưng chi phí tính toán sẽ tăng lên.

Kết quả phân tích cộng đồng có thể ứng dụng trực tiếp vào lĩnh vực nào? Mô hình được ứng dụng trực tiếp trong tiếp thị lan truyền (viral marketing) để xác định các cá nhân có tầm ảnh hưởng lớn trong nhóm. Ngoài ra, trong lĩnh vực an ninh mạng và phòng chống tội phạm công nghệ cao, phương pháp này hỗ trợ truy vết các đường dây lừa đảo và mạng lưới tài khoản ảo.

Kết luận

Luận văn đã hoàn thành xuất sắc các mục tiêu nghiên cứu đề ra với những đóng góp khoa học nổi bật:

• Hệ thống hóa toàn diện cơ sở lý thuyết về quy trình KDD, lý thuyết đồ thị và bài toán khai phá đồ thị con phổ biến.
• Phân tích rõ nét các ưu nhược điểm của các thuật toán kinh điển như Apriori, FSG và chỉ ra giới hạn tính toán trong mạng quy mô lớn.
• Đề xuất và cài đặt thành công thuật toán cải tiến Light-FSG giúp tối ưu hóa đáng kể tốc độ xử lý dữ liệu đồ thị.
• Xây dựng mô hình biểu diễn dữ liệu tương tác thực tế từ nhóm Facebook thành đồ thị có trọng số đa chiều chính xác.
• Phát triển ứng dụng thử nghiệm hoàn chỉnh tích hợp công cụ trực quan hóa mạng cộng đồng 2D và 3D sinh động.

Trong giai đoạn tiếp theo từ 6 đến 12 tháng tới, hướng phát triển trọng tâm là mở rộng thuật toán trên kiến trúc dữ liệu lớn phân tán và đồ thị động theo thời gian thực. Hãy tải và nghiên cứu toàn văn tài liệu để làm chủ các kỹ thuật khai phá dữ liệu đồ thị tiên tiến nhất hiện nay.

Trích đoạn nội dung tài liệu

Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ 1. Tổng quan về khai phá dữ liệu đồ thị 1. Tại sao cần khai phá dữ liệu: Khoảng một thập kỷ trở lại đây lượng thông tin được lưu trữ trên các thiết bị điện tử không ngừng tăng lên.

Theo các chuyên gia trong ngành CNTT sau cứ khoảng 2 năm thì lượng thông tin lưu trữ trên toàn thế giới tăng gấp đôi, không những vậy các thông tin lưu trữ này có số lượng và kích cỡ CSDL ngày càng lớn và tăng một cách nhanh chóng. Để giải quyết vấn đề này khai phá dữ liệu ra đời như một cách hữu hiệu giải quyết vấn đề vừa nêu ở trên. Hiện nay khai phá dữ liệu có rất nhiều định nghĩa tuy nhiên chúng ta có thể hiểu đơn giản khai phá dữ liệu như là một công nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu được tích trữ trong suốt quá trình hoạt động của một tổ chức, đơn vị nào đó. Các khái niệm khai phá dữ liệu Thuật ngữ khai phá dữ liệu là nói đến việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lượng lớn các dữ liệu thô.

Hiện nay có rất nhiều thuật ngữ được dùng có nghĩa tương tự với khai phá dữ liệu (Data Mining) như: Khai phá tri thức (Knowledge Mining), Chắt lọc tri thức (Knowledge extraction), Phân tích dữ liệu/mẫu (Data/patern), …. Định nghĩa : Khai phá dữ liệu là tập hợp các kỹ thuật đươc sử dụng để tự động để khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp các dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ta các mẫu tiềm ẩn trong tập dữ liệu. Khai phá dữ liệu là một trong bảy bước của quá trình KDD (Knowleadge Discovery in Database) và KDD được xem như 7 quá trình khác nhau theo thứ tự: LUAN VAN CHAT LUONG download : add [e-mail] 5 - Làm sạch dữ liệu (data cleaning & preprocessing): Loại bỏ nhiễu các dữ liệu không cần thiết. - Tích hợp dữ liệu (Data integration): Quá trình hợp nhất dữ liệu thành kho dữ liệu sau khi đã làm sạch dữ liệu và tiền xử lý.

- Trích chọn dữ liệu (data selection): Trích chọn dữ liệu từ những kho dữ liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri thức - Chuyển đổi dữ liệu: Các dữ liệu được chuyển sang dạng phù hợp cho quá trình xử lý - Khai phá dữ liệu: Đây là một trong những bước quan trọng nhất, trong đó sử dụng những phương pháp thông minh để chắt lọc ra những mẫu dữ liệu. - Ước lượng mẫu (Knowledge evulation): Đây là quá trình đánh giá các kết quả tìm được thông qua các độ đo nào đó. - Biểu diễn tri thức (knowledge pesentation): Quá trình sử dụng các kỹ thuật để biểu diễn và thể hiện trực quan cho người dùng. Các bước trong khai phá dữ liệu và KDD 1.

Các chức năng chính của khai phá dữ liệu Khai phá dữ liệu đươc chia thành các nhánh nhỏ bao gồm: - Mô tả khái niệm: Thiên về mô tả, tổng hợp và tóm tắt khai niệm. LUAN VAN CHAT LUONG download : add [e-mail] 6 Ví dụ cụ thể minh hoa cho nhánh này chính là quá trình tóm tắt văn bản, bài báo, bài luận…. - Luật kết hợp: Là dạng luật biểu diễn tri thức ở dạng khá đơn giản VD: “ 70% nam giới đi mua bia thì trong số đó 85% sẽ mua thêm đồ nhắm” Luật kết hợp được ứng dụng trong nhiều lĩnh vực như: y học, kinh doanh, tài chính và thị trường chứng khoán… - Phân lớp và dự đoán: Xếp một đối tượng vào trong một lớp đã biết trước. Hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy(machine learning) như cây quyết định, mạng noron nhân tạo, …đây còn được hiểu theo nghĩa khác là học có giám sát.

VD: Phân lớp vùng địa lý theo dự báo thời tiết - Phân cụm: Xếp các đối tượng theo từng cụm, số lượng cũng như tên cụm chưa được biết trước. Phân cụm hay còn gọi tên khác là học không giám sát. - Khai phá chuỗi: Khai phá chuỗi tương tự như khai phá luật kết hợp nhưng ở đây có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao.

Các công cụ khai phá dữ liệu Khai phá dữ liệu không phải là tất cả các công cụ hay phần mềm cơ sở dữ liệu đang sử dụng. Có thể thực hiện việc khai phá dữ liệu bằng các hệ thống cơ sở dữ liệu bình thường và các công cụ đơn giản, bao gồm việc tạo và viết phần mềm riêng hoặc sử dụng các gói phần mềm thương mại. Khai phá dữ liệu phức tạp được hưởng lợi từ kinh nghiệm trong quá khứ và các thuật toán đã định nghĩa với phần mềm và các gói phần mềm hiện có với các công cụ nhất định để thu được mối quan hệ hoặc uy tín lớn hơn bằng các kỹ thuật khác nhau. Hiện nay các tập hợp dữ liệu rất lớn và việc xử lý dữ liệu theo cụm và quy mô lớn có thể cho phép khai phá dữ liệu để sắp xếp và lập báo cáo về các LUAN VAN CHAT LUONG download : add [e-mail] 7 nhóm và các mối tương quan của dữ liệu phức tạp hơn.

Bây giờ đã có sẵn rất nhiều công cụ và hệ thống hoàn toàn mới gồm các hệ thống lưu trữ và xử lý dữ kiệu kết hợp. Quy trình khai phá dữ liệu đồ thị Quá trình khai phá dữ liệu đồ thị (khám phá tri thức) được tiến hành qua 5 bước sau Hình thành và định nghĩa bài toán Thu thập và Tiền xử lý dữ liệu Khai thác dữ liệu Rút ra các tri thức Phân tích và kiểm định kết quả Sử dụng các tri thức phát hiện được Hình 1. Quá trình khai phá dữ liêu (khám phá tri thức) 1. Hình thành và định nghĩa bài toán Đây là bước tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này sẽ quyết định cho việc rút ra những tri thức hữu ích, đồng thời lựa chọn các phương pháp khai phá dữ liệu thích hợp với mục đích của ứng dụng và bản chất của dữ liệu.

LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Thu thập và tiền xử lý dữ liệu Trong bước này dữ liệu được thu thập ở dạng thô (nguồn dữ liệu thu thập có thể là từ các kho dữ liệu hay nguồn thông tin internet). Trong giai đoạn này dữ liệu cũng được tiền xử lý để biến đổi và cải thiện chất lượng dữ liệu cho phù hợp với phương pháp khai phá dữ liệu được chọn lựa trong bước trên. Bước này thường chiếm nhiều thời gian nhất trong quá trình khám phá tri thức.

Các giải thuật tiền xử lý dữ liệu bao gồm : Xử lý dữ liệu bị mất/ thiếu: Các dạng dữ liệu bị thiếu sẽ được thay thế bởi các giá trị thích hợp Khử sự trùng lắp: các đối tượng dữ liệu trùng lắp sẽ bị loại bỏ đi. Kỹ thuật này không được sử dụng cho các tác vụ có quan tâm đến phân bố dữ liệu. Giảm nhiễu: nhiễu và các đối tượng tách rời khỏi phân bố chung sẽ bị loại đi khỏi dữ liệu. Chuẩn hoá: miền giá trị của dữ liệu sẽ được chuẩn hoá.

Rời rạc hoá: các dạng dữ liệu số sẽ được biến đổi ra các giá trị rời rạc. Rút trích và xây dựng đặc trưng mới từ các thuộc tính đã có. Giảm chiều: các thuộc tính chứa ít thông tin sẽ được loại bỏ bớt. Khai phá dữ liệu và rút ra các tri thức Đây là bước quan trọng nhất trong tiến trình khám phá tri thức.

Kết quả của bước này là trích ra được các mẫu và/hoặc các mô hình ẩn dưới các dữ liệu. Một mô hình có thể là một biểu diễn cấu trúc tổng thể một thành phần của hệ thống hay cả hệ thống trong cơ sở dữ liệu, hay miêu tả cách dữ liệu được nảy sinh. Còn một mẫu là một cấu trúc cục bộ có liên quan đến vài biến và vài trường hợp trong cơ sở dữ liệu. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

Phân tích và kiểm định kết quả Bước thứ tư là hiểu các tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Trong bước này, kết quả tìm được sẽ được biến đổi sang dạng phù hợp với lĩnh vực ứng dụng và dễ hiểu hơn cho người dùng. Sử dụng các tri thức phát hiện được Trong bước này, các tri thức khám phá được sẽ được củng cố, kết hợp lại thành một hệ thống, đồng thời giải quyết các xung đột tiềm năng trong các tri thức đó. Các mô hình rút ra được đưa vào những hệ thống thông tin thực tế dưới dạng các môdun hỗ trợ việc đưa ra quyết định.

Các giai đoạn của quá trình khám phá tri thức có mối quan hệ chặt chẽ với nhau trong bối cảnh chung của hệ thống. Các kỹ thuật được sử dụng trong giai đoạn trước có thể ảnh hưởng đến hiệu quả của các giải thuật được sử dụng trong các giai đoạn tiếp theo. Các bước của quá trình khám phá tri thức có thể được lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện. Các bài toán trong khai phá dữ liệu đồ thị Một số kỹ thuật cốt lõi được sử dụng trong các bài toán khai phá dữ liệu, mô tả kiểu hoạt động khai phá dữ liệu và hoạt động phục hồi dữ liệu.

Khai phá luật kết hợp Khai phá luật kết hợp là kỹ thuật khai phá dữ liêu được biết đến nhiều hơn vì tính quen thuộc và đơn giản. Ở đây thực hiện một sự tương quan đơn giản giữa hai hoặc nhiều mục, thường cùng kiểu để nhận biết các mẫu. Việc xây dựng các công cụ khai phá dữ liệu dựa trên sự kết hợp hay mối quan hệ có thể thực hiện đơn giản bằng các công cụ khác nhau. Phân lớp Kỹ thuật phân lớp dùng để xây dựng một ý tưởng về kiểu khách hàng, kiểu mặt hàng hoặc kiểu đối tượng bằng cách mô tả nhiều thuộc tính để nhận LUAN VAN CHAT LUONG download : add [e-mail] 10 biết một lớp cụ thể.

Kỹ thuật phân lớp dùng để xây dựng một ý tưởng về kiểu khách hàng, kiểu mặt hàng hoặc kiểu đối tượng. Hơn nữa chúng ta có thể sử dụng việc phân lớp như một dạng nguồn thứ cấp, hoặc như là kết quả của các kỹ thuật khác. Phân cụm Bằng cách xem xét một hay nhiều thuộc tính hoặc các lớp, có thể nhóm các phần dữ liệu riêng lẻ với nhau để tạo thành một quan điểm cấu trúc.