Luận văn ThS: Nghiên cứu một số thuật toán phân cụm dữ liệu

Luận văn thạc sĩ về các thuật toán phân cụm dữ liệu, chuyên ngành công nghệ thông tin. Nghiên cứu ứng dụng các thuật toán 1 01 10.

• Tác giả: Trần Thị Kim Thuyến
• Người hướng dẫn: PGSTSKH. Bùi Công Cường
• Trường học: Đại học Công nghệ Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Một Số Thuật Toán Phân Cụm Dữ Liệu
• Loại tài liệu: Luận văn ThS
• Năm xuất bản: 2007
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỤC LỤC
• DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
• DANH MỤC HÌNH VẼ, ĐỒ THỊ
• 1. QUÁ TRÌNH KHÁM PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU
• 2. KHAI PHÁ DỮ LIỆU
• 2.1. KHÁI NIỆM VỀ KHAI PHÁ DỮ LIỆU
• 2.2. CÁC KỸ THUẬT KHAI PHÁ DỮ LIỆU
• 3. PHÂN CỤM DỮ LIỆU
• 3.1. KHÁI NIỆM VỀ PHÂN CỤM DỮ LIỆU
• 3.2. MỘT SỐ VẤN ĐỀ TRONG PHÂN CỤM DỮ LIỆU
• 3.3. MỤC TIÊU CỦA PHÂN CỤM
• 3.4. CÁC BƯỚC CƠ BẢN TRONG PHÂN CỤM
• 3.5. YÊU CẦU CỦA PHÂN CỤM
• 3.6. ỨNG DỤNG CỦA PHÂN CỤM
• 4. CÁC KỸ THUẬT PHÂN CỤM
• 4.1. KIỂU DỮ LIỆU
• 4.1.1. PHÂN LOẠI KIỂU DỮ LIỆU DỰA TRÊN KÍCH THƯỚC MIỀN
• 4.1.2. PHÂN LOẠI KIỂU DỮ LIỆU DỰA TRÊN HỆ ĐO
• 4.2. PHÉP ĐO ĐỘ TƯƠNG TỰ VÀ PHÉP ĐO KHOẢNG CÁCH
• 4.2.1. KHÁI NIỆM TƯƠNG TỰ VÀ PHI TƯƠNG TỰ. ĐỘ ĐO TƯƠNG TỰ VÀ KHÔNG TƯƠNG TỰ
• 4.2.2. PHÉP ĐO KHOẢNG CÁCH
• 4.3. PHƯƠNG PHÁP PHÂN CỤM DỮ LIỆU
• 4.3.1. PHƯƠNG PHÁP PHÂN CỤM PHÂN HOẠCH
• 4.3.2. PHƯƠNG PHÁP PHÂN CỤM PHÂN CẤP
• 4.3.3. PHƯƠNG PHÁP PHÂN CỤM DỰA TRÊN MẬT ĐỘ
• 4.3.4. PHƯƠNG PHÁP PHÂN CỤM DỰA TRÊN LƯỚI
• 4.3.5. PHƯƠNG PHÁP PHÂN CỤM DỰA TRÊN MÔ HÌNH
• 4.3.6. PHƯƠNG PHÁP PHÂN CỤM CÓ DỮ LIỆU RÀNG BUỘC
• 5. MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU
• 5.1. THUẬT TOÁN PHÂN CỤM PHÂN HOẠCH
• 5.1.1. THUẬT TOÁN K-MEANS
• 5.1.2. THUẬT TOÁN PAM
• 5.1.3. THUẬT TOÁN CLARA
• 5.1.4. THUẬT TOÁN CLARANS
• 5.2. CÁC THUẬT TOÁN PHÂN CỤM PHÂN CẤP
• 5.2.1. THUẬT TOÁN HERACHICAL
• 5.2.2. THUẬT TOÁN BIRCH
• 5.2.3. THUẬT TOÁN CURE
• 5.3. CÁC THUẬT TOÁN PHÂN CỤM DỰA TRÊN MẬT ĐỘ
• 5.3.1. THUẬT TOÁN DBSCAN
• 5.3.2. THUẬT TOÁN OPTICS
• 5.4. CÁC THUẬT TOÁN PHÂN CỤM DỰA TRÊN LƯỚI
• 5.4.1. THUẬT TOÁN STING
• 5.4.2. THUẬT TOÁN CLIQUE
• 6. PHÂN CỤM DỮ LIỆU MỜ
• 6.1. VẤN ĐỀ PHÂN CỤM MỜ
• 6.2. KHÁI NIỆM VỀ TẬP MỜ VÀ PHÂN CỤM MỜ
• 6.2.1. KHÁI NIỆM VỀ TẬP MỜ VÀ BIỂU DIỄN TẬP MỜ
• 6.2.2. KHÁI NIỆM PHÂN CỤM MỜ
• 6.3. THUẬT TOÁN PHÂN CỤM MỜ K-MEANS
• 6.3.1. MÔ TẢ THUẬT TOÁN
• 6.3.2. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
• TÀI LIỆU THAM KHẢO
• MỞ ĐẦU
• 1.1. QUÁ TRÌNH KHÁM PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU

Tóm tắt

I. Luận văn ThS Tổng quan thuật toán phân cụm dữ liệu

Từ những thập niên gần đây, sự phát triển vượt bậc của công nghệ phần cứng và truyền thông đã tạo ra một lượng dữ liệu khổng lồ. Sự phong phú về dữ liệu và khả năng khai thác kịp thời đã mang lại những năng suất và chất lượng mới cho công tác quản lý và hoạt động kinh doanh. Nhu cầu về thông tin ngày càng cao, đặc biệt trong lĩnh vực ra quyết định, đòi hỏi những hiểu biết và tri thức để hỗ trợ. Những năm 90 chứng kiến sự bùng nổ của nhu cầu khám phá tri thức, dẫn đến hàng loạt nghiên cứu về tổ chức kho dữ liệu, hệ trợ giúp quyết định, các thuật toán nhận dạng mẫu và phân cụm dữ liệu.

Phân cụm dữ liệu là quá trình tìm kiếm và phát hiện các cụm hoặc mẫu dữ liệu tự nhiên trong cơ sở dữ liệu lớn. Các kỹ thuật chính được áp dụng trong phân cụm dữ liệu phần lớn được kế thừa từ lĩnh vực thống kê, học máy, nhận dạng và lượng hoá. Có nhiều ứng dụng của phân cụm dữ liệu trong các lĩnh vực như tài chính, ngân hàng, y học, xã hội học và nhận dạng ảnh. Sự phát triển mạnh mẽ của công nghệ thông tin đã làm tăng khả năng thu thập và lưu trữ dữ liệu. Kho dữ liệu trở nên vô tận, và việc khai thác nguồn tri thức đó là một vấn đề cấp thiết. Vấn đề khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases) đang thu hút sự quan tâm của nhiều nhà khoa học. Khai phá dữ liệu là một bước quan trọng trong quá trình khám phá tri thức.

Luận văn này tập trung trình bày một số vấn đề của phân cụm dữ liệu, bao gồm bốn chương, phần kết luận và phần phụ lục là chương trình mô phỏng một thuật toán phân cụm dữ liệu. Chương 1 giới thiệu tổng quan về phân cụm dữ liệu, bao gồm khám phá tri thức, khai phá dữ liệu, khái niệm trong phân cụm dữ liệu và các lĩnh vực ứng dụng liên quan. Chương 2 trình bày các kỹ thuật phân cụm, bao gồm kiến thức cơ sở như các kiểu dữ liệu, các phép đo khoảng cách giữa các đối tượng dữ liệu và các kỹ thuật tiếp cận trong phân cụm dữ liệu. Chương 3 tập trung vào các thuật toán phân cụm dữ liệu tiêu biểu, phân chia theo các kỹ thuật tiếp cận như các thuật toán phân cụm phân hoạch, thuật toán phân cụm phân cấp. Chương 4 trình bày về phân cụm mờ và kỹ thuật mờ trong phân cụm dữ liệu, cụ thể là thuật toán Fuzzy C-Means (FCM). Luận văn kết luận bằng cách tổng kết nội dung đã trình bày, kết quả đạt được, các vấn đề chưa giải quyết và đề xuất hướng nghiên cứu tiếp theo. Phụ lục trình bày chương trình mô phỏng một thuật toán phân cụm dữ liệu K-means, một trong những thuật toán phổ biến nhất.

1.1. Quá trình khám phá tri thức trong cơ sở dữ liệu

Quá trình khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) là một quá trình nhận biết đúng đắn, mới, hữu ích và cuối cùng là có thể hiểu được mẫu hoặc mô hình trong dữ liệu. Quá trình này bao gồm các bước như trích chọn dữ liệu, tiền xử lý dữ liệu, biến đổi dữ liệu, khai phá dữ liệu, đánh giá và biểu diễn tri thức, và ứng dụng tri thức được khám phá. Khai phá dữ liệu là giai đoạn quan trọng nhất, tập trung vào việc rút ra tri thức phù hợp từ cơ sở dữ liệu. Theo tài liệu gốc, quá trình này có thể lặp đi lặp lại và điều chỉnh theo tri thức đã được phát hiện.

Bước tiền xử lý dữ liệu bao gồm làm sạch, loại bỏ dữ liệu nhiễu hoặc ngoại lai, xử lý giá trị không đầy đủ, biến đổi và rút gọn dữ liệu, sửa lỗi hệ thống. Sau bước này, dữ liệu trở nên nhất quán, đầy đủ, được rút gọn và rời rạc hóa. Quá trình biến đổi dữ liệu chuẩn hóa và làm mịn dữ liệu, đưa dữ liệu về dạng thuận lợi nhất để phục vụ cho kỹ thuật khai phá dữ liệu ở bước sau.

Cuối cùng, các mẫu thông tin và mối liên hệ trong dữ liệu đã được khám phá được chuyển dạng và biểu diễn ở dạng gần gũi với người sử dụng, đồng thời đánh giá tri thức theo các tiêu chí nhất định. Kinh nghiệm cho thấy rằng các mẫu hoặc mô hình phát hiện được từ dữ liệu không phải lúc nào cũng đáng quan tâm và có thể sử dụng ngay. Do đó, quy trình khám phá tri thức thường được lặp đi lặp lại và điều chỉnh theo các tri thức đã phát hiện.

1.2. Khai phá dữ liệu Khái niệm và các kỹ thuật

Khai phá dữ liệu (Data mining) là quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong các cơ sở dữ liệu lớn, các kho dữ liệu. Các kết quả khoa học cùng những thành công trong khám phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực mang lại nhiều lợi ích và có triển vọng, có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống.

Khai phá dữ liệu liên quan đến nhiều ngành khoa học như hệ cơ sở dữ liệu, thống kê, học máy, trực quan hóa. Tùy theo cách tiếp cận được sử dụng, khai phá dữ liệu còn áp dụng một số kỹ thuật khác như mạng nơron, lý thuyết tập thô hoặc tập mờ, biểu diễn tri thức. So với các phương pháp này, khai phá dữ liệu có một số ưu thế rõ rệt, ví dụ như khả năng sử dụng dữ liệu có nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục, trong khi phương pháp học máy đòi hỏi tập dữ liệu đầy đủ, ít biến động và không quá lớn.

Có hai nhóm kỹ thuật chính trong khai phá dữ liệu: kỹ thuật khai phá dữ liệu mô tả (như phân cụm, tóm tắt, trực quan hóa) và kỹ thuật khai phá dữ liệu dự đoán (như phân lớp, hồi quy). Luận văn này tập trung vào phân cụm dữ liệu, một trong những phương pháp thông dụng nhất thuộc kỹ thuật khai phá dữ liệu mô tả. Mục tiêu là mô tả các tính chất hoặc đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có.

1.3. Giới thiệu về phân cụm dữ liệu Clustering Data

Phân cụm dữ liệu (PCDL) là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin hữu ích cho việc ra quyết định. Phân cụm dữ liệu là kỹ thuật sử dụng quan sát đối tượng để nhóm các đối tượng thành các cụm hoặc chia một tập dữ liệu ban đầu thành các cụm sao cho các đối tượng trong cùng một cụm là giống nhau hoặc gần giống nhau (tương tự), và các đối tượng thuộc các cụm khác nhau sẽ không tương tự (phi tương tự).

Có thể hiểu đơn giản là "Phân cụm là quá trình tổ chức các đối tượng thành các nhóm sao cho các đối tượng trong cùng một nhóm là tương tự với nhau". Quy trình này gồm các bước chính: thuật toán, N đối tượng, phân cụm, K nhóm. Phân cụm tối ưu thuộc lớp bài toán NP-Hard, và số lượng cụm thường được xác định tùy thuộc vào phương pháp phân cụm. Các thuật toán phân cụm tìm các nhóm chứa đối tượng tương tự nhau, và hai hoặc nhiều đối tượng được xếp vào cùng một cụm nếu chúng có chung một định nghĩa về khái niệm hoặc chúng xấp xỉ với các khái niệm được mô tả trước.

II. Vấn đề và thách thức trong bài toán phân cụm dữ liệu

Phân cụm dữ liệu đối mặt với nhiều vấn đề và thách thức, bao gồm xử lý nhiễu, dò tìm phần tử ngoại lai, và tính chất mở và khó của bài toán. Hầu hết dữ liệu sử dụng để phân cụm đều bị nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ. Vì vậy, cần phải xây dựng chiến lược cho bước tiền xử lý dữ liệu nhằm khắc phục hoặc loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích cụm dữ liệu. Dữ liệu bị nhiễu là dữ liệu không chính xác hay là dữ liệu khuyết thiếu thông tin về một số thuộc tính. Một trong các kỹ thuật xử lý nhiễu hiện nay là việc thay thế giá trị các thuộc tính của đối tượng nhiễu bằng các giá trị thuộc tính tương ứng.

Phần tử ngoại lai là một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ liệu trong cơ sở dữ liệu. Loại bỏ những dữ liệu kiểu này để tránh ảnh hưởng đến kết quả phân cụm. Phân cụm đang là vấn đề mở và khó vì phải giải quyết nhiều vấn đề cơ bản như xây dựng hàm tính độ tương tự, xây dựng các tiêu chuẩn phân cụm, xây dựng mô hình cho cấu trúc dữ liệu, xây dựng các thuật toán phân cụm và xác lập các điều kiện khởi tạo, xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm. Hiện nay, chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc dữ liệu. Với những loại dữ liệu hỗn hợp thì việc phân cụm càng trở nên khó khăn và đây đang là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu.

2.1. Xử lý dữ liệu nhiễu và dò tìm phần tử ngoại lai

Việc xử lý dữ liệu nhiễu và dò tìm phần tử ngoại lai là một phần quan trọng trong quá trình phân cụm dữ liệu. Dữ liệu nhiễu có thể xuất phát từ nhiều nguồn, bao gồm lỗi trong quá trình thu thập dữ liệu, lỗi nhập liệu, hoặc các giá trị bị thiếu. Việc không xử lý dữ liệu nhiễu có thể dẫn đến kết quả phân cụm không chính xác hoặc không đáng tin cậy. Các phương pháp xử lý dữ liệu nhiễu bao gồm việc loại bỏ các giá trị nhiễu, thay thế các giá trị nhiễu bằng các giá trị hợp lý, hoặc sử dụng các phương pháp thống kê để làm mịn dữ liệu.

Phần tử ngoại lai là các đối tượng dữ liệu khác biệt đáng kể so với phần còn lại của dữ liệu. Các phần tử ngoại lai có thể là kết quả của lỗi đo lường, hoặc chúng có thể đại diện cho các trường hợp đặc biệt hoặc bất thường. Việc dò tìm và loại bỏ các phần tử ngoại lai có thể cải thiện đáng kể chất lượng của kết quả phân cụm. Các phương pháp dò tìm phần tử ngoại lai bao gồm việc sử dụng các phương pháp thống kê để xác định các đối tượng dữ liệu có giá trị khác thường, hoặc sử dụng các thuật toán phân cụm để xác định các đối tượng dữ liệu không thuộc về bất kỳ cụm nào.

2.2. Mục tiêu và các bước cơ bản trong phân cụm dữ liệu

Mục tiêu của phân cụm là xác định được bản chất nhóm trong tập dữ liệu chưa có nhãn. Để quyết định được cái gì tạo thành một cụm tốt, đòi hỏi người sử dụng phải đưa ra một số tiêu chuẩn mà theo cách đó kết quả phân cụm sẽ đáp ứng được yêu cầu. Ví dụ như quan tâm đến việc tìm đại diện cho các nhóm đồng nhất (rút gọn dữ liệu), tìm kiếm các nhóm hữu ích và phù hợp (các lớp dữ liệu hữu ích), tìm kiếm các đối tượng khác thường (dò tìm phần tử ngoại lai).

Các bước cơ bản trong phân cụm bao gồm chọn lựa đặc trưng, chọn độ đo gần gũi, tiêu chuẩn phân cụm, thuật toán phân loại, công nhận kết quả và giải thích kết quả. Trong một số trường hợp, nên có cả bước phân tích khuynh hướng phân cụm, trong bước này có các kiểm định khác nhau để chỉ ra tập dữ liệu có hay không một cấu trúc phân cụm.

III. Kỹ thuật phân cụm dữ liệu theo các kiểu thuộc tính khác nhau

Trong phân cụm, các đối tượng dữ liệu thường được diễn tả dưới dạng các đặc tính hay còn gọi là thuộc tính. Các thuộc tính này là các tham số cho giải quyết vấn đề phân cụm và sự lựa chọn chúng có tác động đến kết quả phân cụm. Có hai đặc trưng để phân loại: Kích thước miền và hệ đo. Cho cơ sở dữ liệu D chứa n đối tượng trong không gian k chiều và x, y, z là các đối tượng thuộc D. x=(x1, x2,…,xk); y=(y1, y2,…,yk); z=(z1,z2,…,zk) Trong đó xi, yi, zi với i=1÷k là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng x, y, z. Như vậy ta sẽ có các kiểu dữ liệu khác nhau.

3.1. Phân loại kiểu dữ liệu dựa trên kích thước miền

Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm được, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Ví dụ như các thuộc tính về nhiệt độ, hoặc cường độ âm thanh. Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn, đếm được. Ví dụ như các thuộc tính số, liệt kê. Trường hợp đặc biệt của thuộc tính rời rạc là thuộc tính nhị phân mà miền giá trị của nó chỉ có hai phần tử. Ví dụ như: Yes/No, True/False, On/Off.

3.2. Phân loại kiểu dữ liệu dựa trên hệ đo

Giả sử ta có hai đối tượng x, y và các thuộc tính xi, yi với i=1÷k tương ứng với thuộc tính thứ i của chúng. Như vậy sẽ có các kiểu dữ liệu như sau: Thuộc tính định danh: Là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử. Nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x≠y hay x=y. Thuộc tính có thứ tự: Là thuộc tính định danh có thêm tính thứ tự nhưng chúng không định lượng. Nếu x và y là hai thuộc tính thứ tự thì có thể xác định là x≠y hoặc x=y hoặc x>y hoặc xPhép đo độ tương tự và phép đo khoảng cách

IV. Các thuật toán phân cụm dữ liệu phân hoạch phổ biến

Thuật toán phân cụm phân hoạch nhằm phân một tập hợp dữ liệu có n phần tử cho trước thành k nhóm dữ liệu sao cho: mỗi phần tử chỉ thuộc về một nhóm dữ liệu và mỗi nhóm dữ liệu có ít nhất một phần tử dữ liệu. Các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề phân cụm dữ liệu do nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Số các cụm được thiết lập sau khi phân hoạch là các đặc trưng được lựa chọn trước, phương pháp này tốt cho các cụm hình cầu trong không gian Euclid. Ngoài ra, phương pháp này còn phụ thuộc vào khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là gần nhau, xa nhau so với mỗi điểm khác. Phương pháp này không xử lý được các điểm có hình thù kỳ quặc hay mật độ dày đặc. Do phải tìm kiếm hết các phân hoạch có thể được nên các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm toàn cục. Do vậy, trên thực tế thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của cụm cũng như để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu.

4.1. Thuật toán K Means Nguyên lý và ứng dụng

K-means là một trong những thuật toán học không giám sát đơn giản và được sử dụng rộng rãi để giải quyết vấn đề phân cụm dữ liệu. Thuật toán K-means do J. MacQueen đề xuất năm 1967, cho đến nay đã có nhiều dạng biến đổi khác nhau của thuật toán này. Trong thuật toán K-means, các cụm được định nghĩa dựa trên trung tâm của các phần tử. Phương pháp này dựa trên độ đo khoảng cách của các đối tượng dữ liệu trong cụm. Trong thực tế, nó đo khoảng cách của mỗi đối tượng dữ liệu tới trung tâm của cụm. Trung tâm của cụm được xem là giá trị trung bình của các đối tượng. Như vậy, nó cần khởi tạo một tập trung tâm các cụm ban đầu, thông qua đó lặp lại các bước như gán mỗi đối tượng vào cụm mà có trung tâm gần nó nhất, tính toán lại trung tâm của mỗi cụm trên cơ sở có thêm các đối tượng vừa gán mới. Quá trình này dừng khi trung tâm hội tụ.

4.2. Thuật toán PAM Partition Around Medoids

Thuật toán PAM (Partition Around Medoids) là thuật toán mở rộng của K-means được đưa ra bởi Kaufman and Rousseeuw [1987]. So với K-means, PAM có khả năng xử lý hiệu quả đối với dữ liệu nhiễu hoặc ngoại lai, PAM sử dụng các đối tượng medoid để biểu diễn các cụm dữ liệu. Medoid là đối tượng đặt tại vị trí trung tâm bên trong mỗi cụm. Vì vậy, đối tượng medoid ít bị ảnh hưởng bởi những đối tượng ở xa trung tâm. Trong khi đó, các trọng tâm của thuật toán K-means lại rất bị ảnh hưởng bởi những đối tượng ở xa trung tâm này. Ban đầu, PAM khởi tạo k đối tượng medoid và phân phối các đối tượng còn lại vào các cụm với các đối tượng medoid đại diện tương ứng sao cho chúng tương tự đối với medoid trong cụm nhất.

V. Kết luận và hướng phát triển của thuật toán phân cụm

Luận văn này đã trình bày tổng quan về thuật toán phân cụm dữ liệu, một lĩnh vực quan trọng trong khai phá dữ liệu. Chúng ta đã xem xét các khái niệm cơ bản, các kỹ thuật tiếp cận khác nhau, và một số thuật toán tiêu biểu như K-means và PAM. Mặc dù đã có nhiều tiến bộ trong lĩnh vực này, vẫn còn nhiều vấn đề và thách thức cần được giải quyết, đặc biệt là trong việc xử lý dữ liệu phức tạp và đa dạng.

5.1. Đánh giá hiệu quả và độ chính xác của các thuật toán

Một trong những hướng nghiên cứu quan trọng là phát triển các phương pháp đánh giá hiệu quả và độ chính xác của các thuật toán phân cụm. Điều này bao gồm việc sử dụng các chỉ số đánh giá khách quan như Silhouette score, Davies-Bouldin index, và Calinski-Harabasz index, cũng như việc so sánh kết quả phân cụm với dữ liệu thực tế hoặc dữ liệu được đánh dấu sẵn.

5.2. Ứng dụng và phát triển thuật toán phân cụm trong Python

Một hướng phát triển khác là mở rộng và tùy chỉnh các thuật toán phân cụm hiện có để phù hợp với các ứng dụng cụ thể. Ví dụ, có thể phát triển các thuật toán đặc biệt để phân cụm văn bản, phân cụm khách hàng, hoặc phân cụm ảnh. Ngoài ra, việc sử dụng các thư viện và công cụ như Scikit-learn trong Python có thể giúp triển khai và thử nghiệm các thuật toán phân cụm một cách dễ dàng và hiệu quả.

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

MỞ ĐẦU Từ vài thập niên trở lại đây, những tác động mạnh mẽ của các tiến bộ trong công nghệ phần cứng và truyền thông, các hệ thống dữ liệu phục vụ cho các lĩnh vực kinh tế-xã hội đã phát triển bùng nổ, lƣợng dữ liệu đƣợc tạo ra ngày càng lớn. Sự phong phú về dữ liệu, thông tin cùng với khả năng kịp thời khai thác của chúng đã mang đến những năng suất và chất lƣợng mới cho công tác quản lý, hoạt động kinh doanh,. Các yêu cầu về thông tin trong các lĩnh vực hoạt động, đặc biệt trong lĩnh vực làm ra quyết định ngày càng đòi hỏi cao, cần có những hiểu biết, những tri thức để hỗ trợ cho việc ra quyết định. Đến những năm 90 nhu cầu khám phá tri thức thực sự bùng nổ, theo đó hàng loạt các lĩnh vực nghiên cứu về tổ chức các kho dữ liệu và kho thông tin, các hệ trợ giúp quyết định, các thuật toán nhận dạng mẫu, phân cụm.

Phân cụm dữ liệu là quá trình tìm kiếm và phát hiện ra các cụm hoặc các mẫu dữ liệu tự nhiên trong cơ sở dữ liệu lớn. Các kỹ thuật chính đƣợc áp dụng trong phân cụm dữ liệu phần lớn đƣợc kế thừa từ lĩnh vực thống kê, học máy, nhận dạng, lƣợng hoá,. Có nhiều ứng dụng phân cụm dữ liệu cho việc giải quyết các vấn đề trong các lĩnh vực nhƣ tài chính, ngân hàng, y học, xã hội học, nhận dạng ảnh,. Nhờ sự phát triển mạnh mẽ của ngành công nghệ thông tin đã làm cho khả năng thu thập và lƣu trữ dữ liệu của các hệ thống thông tin tăng một cách vũ bão.

Kho dữ liệu, nguồn tri thức của nhân loại cũng trở nên vô tận và làm thế nào để khai thác đƣợc nguồn tri thức đó đang là một vấn đề nóng bỏng của nền công nghệ thông tin thế giới. Vấn đề Khám phá tri thức trong Cơ sở dữ liệu (Knowledge Discovery in Databases) đang đƣợc rất nhiều các nhà khoa học quan tâm nghiên cứu. Khai phá dữ liệu là một bƣớc quan trọng trong quá trình khám phá tri thức. TIEU LUAN MOI download : [e-mail] 7 Khai phá dữ liệu có rất nhiều hƣớng tiếp cận, các kỹ thuật khai phá dữ liệu liên quan đến rất nhiều ngành khoa học khác nhƣ: Hệ cơ sở dữ liệu, thống kê, học máy, trực quan hoá,…Tuỳ vào từng cách tiếp cận cụ thể đƣợc sử dụng, khai phá dữ liệu còn áp dụng một số kỹ thuật khác nhƣ mạng nơron, lý thuyết tập mờ, biểu diễn tri thức,… Phân cụm dữ liệu là một trong những kỹ thuật khai phá dữ liệu phổ biến nhất, nằm trong nhóm kỹ thuật khai phá dữ liệu mô tả, có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có.

Luận văn này tập trung trình bày một số vấn đề của phân cụm dữ liệu, luận văn gồm bốn chƣơng, phần kết luận và phần phụ lục là chƣơng trình mô phỏng một thuật toán phân cụm dữ liệu. Chƣơng 1: Tổng quan về phân cụm dữ liệu, bao gồm một số vấn đề về khám phá tri thức, khai phá dữ liệu và tập trung trình bày một số khái niệm trong phân cụm dữ liệu và các lĩnh vực ứng dụng liên quan. Chƣơng 2: Các kỹ thuật phân cụm, trong đó có đề cập đến một số kiến thức cơ sở là nền tảng cho phân cụm dữ liệu nhƣ các kiểu dữ liệu, các phép đo khoảng cách giữa các đối tƣợng dữ liệu, các kỹ thuật tiếp cận trong phân cụm dữ liệu. Chƣơng 3: Các thuật toán phân cụm dữ liệu, tập trung trình bày một số thuật toán tiêu biểu của phân cụm dữ liệu phân chia theo các kỹ thuật tiếp cận nhƣ các thuật toán phân cụm phân hoạch, các thuật toán phân cụm phân cấp, Chƣơng 4: Trình bày về phân cụm mờ và kỹ thuật mờ trong phân cụm dữ liệu, cụ thể là thuật toán FCM.

Kết luận: Tổng kết lại những nội dung đã trình bày và những kết quả đã đạt đƣợc trong luận văn. Qua đó cũng đề cập đến những vấn đề chƣa giải quyết đƣợc và đề xuất hƣớng nghiên cứu tiếp theo. TIEU LUAN MOI download : [e-mail] 8 Phụ lục: Trình bày chƣơng trình mô phỏng một thuật toán phân cụm dữ liệu K-means, một trong những thuật toán phân cụm dữ liệu phổ biến nhất. TIEU LUAN MOI download : [e-mail] 9 CHƢƠNG 1.1 QUÁ TRÌNH KHÁM PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU Cùng với sự phát triển vƣợt bậc của các công nghệ điện tử và truyền thông đã làm cho khả năng thu thập, lƣu trữ và xử lý dữ liệu cho các hệ thống tin học không ngừng nâng cao.

Bên cạnh đó, việc tin học hoá nhiều lĩnh vực của cuộc sống đã tạo ra cho chúng ta một kho dữ liệu khổng lồ. Quá trình khám phá tri thức trong Cơ sở dữ liệu (Knowledge Discovery in Databases) đang là một vấn đề thời sự của nền công nghệ thông tin thế giới hiện nay. Nó đƣợc ứng dụng vào nhiều lớp bài toán thực tế khác nhau và thu đƣợc nhiều thành quả to lớn. Khám phá tri thức trong cơ sở dữ liệu là một quá trình nhận biết đúng đắn, mới, hữu ích và cuối cùng là có thể hiểu đƣợc mẫu hoặc mô hình trong dữ liệu.

Quá trình khám phá tri thức có thể bao gồm các bƣớc nhƣ hình 1.1 [7] Đánh giá và Khai phá dữ Tri thức giải thích liệu Dữ Trích chọn dữ Tiền xử lý dữ Biến đổi dữ liệu liệu liệu liệu thô Hình 1.1: Quá trình khám phá tri thức - Trích chọn dữ liệu: Là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá từ tập dữ liệu lớn ban đầu theo một tiêu chí nhất định. Đây là bƣớc quan trọng để rút ra những tri thức hữu ích và chọn phƣơng pháp khai phá dữ liệu phù hợp với mục đích ứng dụng và bản chất dữ liệu. - Tiền xử lý dữ liệu: Là bƣớc làm sạch dữ liệu: lựa chọn dữ liệu nguồn, loại bỏ các dữ liệu nhiễu hoặc ngoại lai, xử lý các giá trị không đầy đủ, biến TIEU LUAN MOI download : [e-mail] 10 đổi và rút gọn dữ liệu, sửa các lỗi mang tính hệ thống, tập hợp các thông tin cần thiết để mô hình hoặc tính toán nhiễu, quyết định các chiến lƣợc xử lý các trƣờng dữ liệu bị lỗi. Sau bƣớc này dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời rạc hoá.

- Biến đổi dữ liệu: Đây là bƣớc chuẩn hoá và làm mịn dữ liệu để đƣa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho kỹ thuật khai phá ở bƣớc sau. - Khai phá dữ liệu: Áp dụng các kỹ thuật phân tích nhằm để khai thác dữ liệu, trích chọn các mẫu ẩn hoặc mô hình trong dữ liệu. Một mô hình có thể xem nhƣ là một biểu diễn tổng thể của cấu trúc nhằm tóm lƣợc các thành phần mang tính hệ thống có trong dữ liệu hoặc mô tả dữ liệu phát sinh. Ngƣợc lại, một mẫu là một cấu trúc cục bộ có khi chỉ liên quan tới một nhóm các biến và một số trƣờng hợp.

- Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu đã đƣợc khám phá ở bƣớc trên đƣợc chuyển dạng và đƣợc biểu diễn ở một dạng gần gũi với ngƣời sử dụng, đồng thời đánh giá những tri thức khám phá đƣợc theo những tiêu chí nhất định. Đặc biệt là làm sáng tỏ các mô tả và dự đoán, hai mục tiêu chính của các hệ thống khám phá trong thực tế. Kinh nghiệm cho thấy rằng các mẫu hoặc mô hình phát hiện đƣợc từ các dữ liệu không phải lúc nào cũng đáng quan tâm và có thể trực tiếp sử dụng đƣợc ngay, quy trình khám phá tri thức đƣợc lặp đi lặp lại có điều chỉnh theo các tri thức phát hiện đƣợc. Để đánh giá đƣợc các luật áp dụng trong quy trình khám phá tri thức, dữ liệu thƣờng đƣợc chia thành hai tập, huấn luyện trên tập thứ nhất và kiểm chứng trên tập thứ hai.

Có thể lặp lại quy trình này với một số lần với các phần chia khác nhau, sau đó lấy trung bình các kết quả để ƣớc lƣợng các luật thi hành. TIEU LUAN MOI download : [e-mail] 11 - Ứng dụng tri thức được khám phá: Củng cố các tri thức đã khám phá, kết hợp các tri thức thành một hệ thống máy tính. Giải quyết các xung đột tiềm năng trong tri thức khai thác đƣợc. Đƣa kết quả vào thực tiễn là mục đích cuối cùng của khám phá tri thức.

Khai phá dữ liệu là một giai đoạn quan trọng nhất của quá trình khám phá tri thức. Bản chất của quá trình khám phá tri thức là rút ra đƣợc tri thức phù hợp từ cơ sở dữ liệu.2 KHAI PHÁ DỮ LIỆU 1.1 KHÁI NIỆM VỀ KHAI PHÁ DỮ LIỆU Khai phá dữ liệu (Data mining) là quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong các cơ sở dữ liệu lớn, các kho dữ liệu…Các kết quả khoa học cùng những thành công trong khám phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực mang lại nhiều lợi ích và có triển vọng, có ƣu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Khai phá dữ liệu là một lĩnh vực có liên quan đến rất nhiều ngành khoa học khác nhƣ: Hệ cơ sở dữ liệu, thống kê, học máy, trực quan hoá…Tuỳ vào cách tiếp cận đƣợc sử dụng thì khai phá dữ liệu còn áp dụng một số kỹ thuật khác nhƣ mạng nơron, lý thuyết tập thô hoặc tập mờ, biểu diễn tri thức…So với các phƣơng pháp này, khai phá dữ liệu có một số ƣu thế rõ rệt. So với phƣơng pháp học máy, khai phá dữ liệu có thể sử dụng dữ liệu có nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục.

Trong khi đó, phƣơng pháp học máy đòi hỏi tập dữ liệu phải đầy đủ, ít biến động và không quá lớn. Phƣơng pháp hệ chuyên gia, các ví dụ của chuyên gia thƣờng phải đòi hỏi chất lƣợng cao hơn nhiều so với dữ liệu trong cơ sở dữ liệu. TIEU LUAN MOI download : skknchat@gmail.