Luận văn: Nghiên cứu và cài đặt giải thuật phân cụm, phân lớp - Vũ Lan Phương

Nghiên cứu chuyên sâu Các giải thuật phân cụm, phân lớp: Nghiên cứu & Cài đặt ứng dụng cao trong học thuật và nghiên cứu thực tiễn

• Tác giả: Vũ Lan Phương
• Người hướng dẫn: PGS.TS Nguyễn Ngọc Binh
• Trường học: Trường Đại Học Bách Khoa Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Nghiên Cứu Và Cài Đặt Một Số Giải Thuật Phân Cụm, Phân Lớp
• Loại tài liệu: Luận Văn Thạc Sĩ Khoa Học
• Năm xuất bản: 2006
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng Quan Về Phát Hiện Trí Thức Và Khai Phá Dữ Liệu

Khai phá dữ liệu (Data Mining) là quá trình phát hiện những kiến thức mới, có giá trị và có thể hiểu được từ những tập dữ liệu lớn. Đây là một trong những công nghệ quan trọng nhất trong thế kỷ 21, giúp các tổ chức khai thác thông tin ẩn chứa trong dữ liệu lịch sử. Phát hiện tri thức (KDD - Knowledge Discovery in Databases) là một quá trình phức tạp bao gồm nhiều bước từ chuẩn bị dữ liệu cho đến phân tích kết quả. Các kỹ thuật khai phá dữ liệu chính bao gồm phân loại, phân cụm, và các phương pháp khác. So với các phương pháp truyền thống, khai phá dữ liệu có lợi thế vượt trội trong việc xử lý khối lượng dữ liệu khổng lồ một cách tự động.

1.1. Khái Niệm Cơ Bản Về Khai Phá Dữ Liệu

Khai phá dữ liệu là quá trình tìm kiếm các mẫu, quy luật và mối quan hệ trong những tập dữ liệu lớn. Nó sử dụng các thuật toán máy học để tự động phát hiện tri thức. Quá trình này khác biệt với truy vấn cơ sở dữ liệu truyền thống vì nó không chỉ trả lời các câu hỏi được định nghĩa trước mà còn phát hiện những thông tin mới.

1.2. Các Kỹ Thuật Chính Trong Khai Phá Dữ Liệu

Hai kỹ thuật chính được sử dụng rộng rãi là phân loại (Classification) và phân cụm (Clustering). Phân loại dự đoán lớp của các đối tượng dựa trên dữ liệu huấn luyện. Phân cụm nhóm các đối tượng tương tự vào các cụm. Ngoài ra còn có các phương pháp như khai phá luật kết hợp, phân tích chuỗi thời gian và phát hiện bất thường.

II. Kỹ Thuật Phân Loại Classification Trong Khai Phá Dữ Liệu

Phân loại là kỹ thuật học có giám sát, trong đó mô hình được huấn luyện từ dữ liệu có nhãn sẵn để dự đoán lớp của các mẫu mới. Các vấn đề quan trọng trong phân loại bao gồm chọn lựa thuộc tính, xử lý dữ liệu không cân bằng, và đánh giá hiệu suất. Có nhiều phương pháp phân loại khác nhau như cây quyết định (Decision Tree), Bayesian, mạng nơron, và các phương pháp dựa trên kết hợp. Mỗi phương pháp có ưu và nhược điểm riêng, phù hợp với các bài toán khác nhau.

2.1. Cây Quyết Định Quy Nạp Inductive Decision Tree

Cây quyết định là một trong những phương pháp phân loại phổ biến nhất. Giải thuật ID3 sử dụng entropy để chọn thuộc tính có thông tin thu được cao nhất tại mỗi nút. Cây quyết định dễ hiểu, dễ triển khai và có hiệu suất tốt trên các tập dữ liệu nhỏ đến trung bình.

2.2. Phân Loại Bayesian Và Mạng Nơron

Phân loại Bayesian dựa trên định lý Bayes, tính toán xác suất có điều kiện để dự đoán lớp. Mạng nơron truyền thẳng sử dụng lan truyền ngược để huấn luyện. Nó có khả năng xấp xỉ các hàm phi tuyến phức tạp, thích hợp cho các bài toán phức tạp.

III. Kỹ Thuật Phân Cụm Clustering Trong Khai Phá Dữ Liệu

Phân cụm là kỹ thuật học không giám sát, nhóm các đối tượng tương tự vào các cụm mà không cần dữ liệu huấn luyện có nhãn. Các kiểu dữ liệu trong phân cụm bao gồm dữ liệu số, danh mục, và hỗn hợp. Có nhiều phương pháp phân cụm chính như phương pháp phân chia (Partitioning), phân cấp (Hierarchical), dựa trên mật độ (Density-based), và dựa trên lưới (Grid-based). Mỗi phương pháp có cách tiếp cận khác nhau để định nghĩa và tìm cụm.

3.1. Phương Pháp Phân Chia K Means Và K Medoids

K-means là thuật toán phân chia phổ biến nhất, chia dữ liệu thành k cụm bằng cách tối thiểu tổng bình phương khoảng cách. K-medoids sử dụng đối tượng thực tế làm tâm cụm thay vì trung bình, ít nhạy cảm với nhiễu hơn. Cả hai đều đơn giản, hiệu quả nhưng cần xác định k trước.

3.2. Phương Pháp Phân Cấp Và Dựa Trên Mật Độ

Phân cụm phân cấp tạo một cây phân cấp các cụm, có thể là bottom-up (agglomerative) hoặc top-down (divisive). Phương pháp dựa trên mật độ như DBSCAN và OPTICS phát hiện cụm có hình dạng bất kỳ bằng cách dựa vào mật độ điểm, không bị giới hạn bởi hình cầu như k-means.

IV. Cài Đặt Và Thử Nghiệm Các Giải Thuật

Cài đặt thử nghiệm các giải thuật phân loại và phân cụm là bước quan trọng để đánh giá hiệu suất thực tế. Giai đoạn chuẩn bị dữ liệu bao gồm làm sạch, chuẩn hóa, và chọn lựa đặc trưng. Thiết kế chương trình cần xem xét hiệu quả thuật toán, khả năng mở rộng, và tính chính xác. Kết quả thử nghiệm và đánh giá sử dụng các độ đo như độ chính xác (Accuracy), precision, recall, F-measure cho phân loại, và silhouette coefficient, Davies-Bouldin index cho phân cụm.

4.1. Chuẩn Bị Dữ Liệu Và Thiết Kế Chương Trình

Dữ liệu mẫu được chuẩn bị từ các bộ dữ liệu công khai hoặc sinh tế. Xử lý dữ liệu bao gồm loại bỏ giá trị thiếu, chuẩn hóa tỷ lệ, và mã hóa dữ liệu danh mục. Thiết kế hệ thống phải hỗ trợ dễ dàng thay đổi tham số, so sánh giữa các thuật toán khác nhau.

4.2. Đánh Giá Hiệu Suất Và Kết Quả Thử Nghiệm

Độ chính xác là chỉ số quan trọng nhất, được tính bằng holdout validation hoặc cross-validation. Các độ đo khác như precision, recall, confusion matrix giúp đánh giá toàn diện. Kết quả thử nghiệm cho thấy mỗi thuật toán có điểm mạnh riêng tùy theo tính chất dữ liệu.

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

CHƯƠNG 1: TỎNG QUAN PHÁT THIỆN TRÌ THỨC VẢ KHAI PHÁ DỮ LIEU 1.1 Giới thiệu chung Trong những năm gân đây, sự phát triển mạnh mẽ của CNLT và ngành công nghiệp phẩn cứng đã làm cho khả nắng thu thập và lưu trữ tháng tín của các hệ thông thông tin tăng riưanh một cách chúng mặt. Bên cạnh đó việc tìn hoc hoa một cách Š ạt và nhanh chống các hoại động sân xuất, kinh doanh eing nhur nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ khéng 16. [lang trigu CSDL da duoc sit dung trong các hoạt động sản xuất, kinh. doanh, quan li., trong 46 cé nhiều CSDL cực lén cỡ Gigabyte, thim chi 1a Terabyte.

Sur bing nd nay đã dẫu tới một yêu câu cấp thiết là cần có những kĩ thuật và công cụ mới để tự động chuyển dễi lượng đữ liệu khổng lỗ kĩa thành các trì thức có ích. Tử dỏ, các kĩ thuật khai phà đữ liệu đã trở thánh một lĩnh vực thời sự của nên CNTT thể giới hiện nay.1 Khải niệm khai phá dữ liệu Khải phá dữ liệu (Data Miring) là một khái niệm ra đời vào những răn cuối của thắp kỳ 1980. Nó là quả trình trích xuất các thông tin có giả trị tiểm Ân bên trong lượng lớn dữ liệu được lưu trữ trong các CSUL, kho dữ liệu. Liện nay, ngoài thuật ngữ khai phá đữ liệu, người †a côn đứng một số thuật ngữ khác có Ý nghĩa tương tự như: khai phá trị thức từ CSDL, trích lọc dữ liệu, phân tích dữ hệu/mẫu, khảo cổ dữ liệu, nạo vúi dữ liệu.

Nhiễn người coi Khai phá dữ liệu và một thưặt ngữ thông dựng khác lá Phát hiện trị thức troug CSDL (Knowlegde TDiseovery m Databases - KDD) là như nhau. Tuy nhiên trên thực tả, khai phá dữ liệu chỉ là một bước thiết yếu trong quá trinh Phat hién tri thúc trong CSDT, Có thể nói Data Mining là giai đoạn quan trọng nhất trong tiến trình Phát hiện trí thức từ cơ sở dữ liệu, các trị thức này hỗ trợ trong việc ra quyết định trong khoe học và kinh doanh.2 Các bước của quả trình phảt hiện trì thức Quá trình phát hiện trí thức tiến hành qua 6 giai đoạn như hình 1 1: -4- thuật thưởng dùng trong Khai phá dữ liệu, đó là Phân loại (ClassiBeation) và Phan cum (Clustering hay Cluster Analyse) « Bổ cục luận văn Ngoài các phần Mớ đầu, Mục lục, Danh mục hình, Danh mục bảng, Kết Tuân, Tài liệu tham khảo, luận văn được chia làm 4 phân: Phan I: Téng quan về Phát hiện trì thức và Khai phá dữ liệu Phần mày giới thiệu một cách tổng quát về quá trình phát hiện tì thức nói chung và khai phá dữ liệu nói riêng. Đặc biệt nhân mạnh về hai kỹ thuật chính. được nghiên cứu trong luận văn đỏ là Kỹ thuật phân loại và Xÿ thuật phân cụm.

Phan TT: Kỹ thuật phân loai (Classification) Trong phần này, kỹ thuật phâu loại được giới thiệu một cách chỉ tiếL Có nhiều kiểu phân loại như phần loại bằng cây quyết dịnh quy nạp, phần loại Bayesian, phan loai bing mạng lan truyền ngược, phân loại dựa trên sự kết hợp và cáo phương pháp phân loại khảo. Ngoài ra còn đánh giá độ chỉnh xác của phiên loại thông qua các classilfer - người phâu loại Phân TT: Kỹ thuật phan cum (Clustering) Kỹ thuật phân cum cũng dược chia làm nhiều kiểu: phản cụm phân chia, phan cum phan cấp, phân cụm dựa trên mật 46 va phan cum dựa trên lưới. Phần TV: Cài đặt thử nghiệm Thần nay trình bày một số kết quả đã đạt được khí tiến hành áp dụng các giải thuật khai phá dữ liệu để khai thác thông tin dữ liệu mẫu. -Š- MOT 86 TU VIET TÁT VÀ THUẬT NGỮ THƯỜNG DÙNG [KbB TA.

DM" — — | Classificaion -3- MODAU « Giới thiệu Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ théng tín trong nhiều lnh vực của đời sông, kinh tế xã hội trong nhiều năm qua cũng đông nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích kỹ nhiều lên. Họ lưu trữ các dữ liệu nay vi cho rằng trong nó ẩn chứa xhhững giả trị nhất đỉnh nào đó. Tuy nhiên, theo thống kê thì chỉ có một lượng nhỏ của những đữ liêu này (khoảng từ 5% dén 10%) la luén được phân tích. số còn lại họ không biết sẽ phái làm gì hoặc có thể làm gi với chúng nhưng họ vẫn tiếp tục thu thập rất tốn kém với ý nghĩ lo sợ rằng sẽ có cái gì đỏ quan trọng đã bị bỏ qua sau này có lúc cản đến nó.

Mặt khác, trong môi trường cạnh tranh, Tigười tá ngày cảng cần có nhiều thông in với tốc độ nhanh đỄ trợ giúp việc ra quyết định và ngày cảng có nhiều gâu hỏi mang tính chối. định tĩnh cần phải trả lời dựa trên một khối lượng đữ liệu khổng lỗ đã có. Với những lý do như vậy, các phương pháp quản trị và khai thác cơ số đữ liệu truyển thống ngày cảng không đếp ứng được thực lễ đã làm phái. triển một khuynh hướng kỹ thuật mới đỏ là Kỹ thuật phát hiện trí thức và khai phá đữ ligu (KDD - Knowledge Discovery and Data Mining).

Kỹ thuật phát hiện trí thức và khai phá đữ liệu đã và đang được nghiên cửu, vng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thể giới, tại Việt Nam kỹ thuật này tượng đổi còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần dưa vào ứng dụng. Bước quan trọng nhất của quá trình này là Khai phá dữ liệu (Data Mining - DM), giúp người sử dụng thu dược những trí thức hữu ¡ch từ những CSDL hoặc các nguồn dữ liệu khổng lễ khác, Rất nhiều đoanh nghiệp và tổ chức trên thể giới đã ứng dụng kĩ thuật khai phá dữ liệu vào hoạt động sản xuất kinh doanh của mình và đã thu được những lợi ích to lớn. Nhung dé lam được điều đỏ, sự phát triển của các mô hình toán học vả các giải thuật hiệu quả là chìa khoả quan trọng. Vì vậy, trong luận văn này, tác giả sẽ đẻ cập tới hai kỹ -4- thuật thưởng dùng trong Khai phá dữ liệu, đó là Phân loại (ClassiBeation) và Phan cum (Clustering hay Cluster Analyse) « Bổ cục luận văn Ngoài các phần Mớ đầu, Mục lục, Danh mục hình, Danh mục bảng, Kết Tuân, Tài liệu tham khảo, luận văn được chia làm 4 phân: Phan I: Téng quan về Phát hiện trì thức và Khai phá dữ liệu Phần mày giới thiệu một cách tổng quát về quá trình phát hiện tì thức nói chung và khai phá dữ liệu nói riêng.

Đặc biệt nhân mạnh về hai kỹ thuật chính. được nghiên cứu trong luận văn đỏ là Kỹ thuật phân loại và Xÿ thuật phân cụm. Phan TT: Kỹ thuật phân loai (Classification) Trong phần này, kỹ thuật phâu loại được giới thiệu một cách chỉ tiếL Có nhiều kiểu phân loại như phần loại bằng cây quyết dịnh quy nạp, phần loại Bayesian, phan loai bing mạng lan truyền ngược, phân loại dựa trên sự kết hợp và cáo phương pháp phân loại khảo. Ngoài ra còn đánh giá độ chỉnh xác của phiên loại thông qua các classilfer - người phâu loại Phân TT: Kỹ thuật phan cum (Clustering) Kỹ thuật phân cum cũng dược chia làm nhiều kiểu: phản cụm phân chia, phan cum phan cấp, phân cụm dựa trên mật 46 va phan cum dựa trên lưới.

Phần TV: Cài đặt thử nghiệm Thần nay trình bày một số kết quả đã đạt được khí tiến hành áp dụng các giải thuật khai phá dữ liệu để khai thác thông tin dữ liệu mẫu. -Š- MOT 86 TU VIET TÁT VÀ THUẬT NGỮ THƯỜNG DÙNG [KbB TA. DM" — — | Classificaion -3- MODAU « Giới thiệu Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ théng tín trong nhiều lnh vực của đời sông, kinh tế xã hội trong nhiều năm qua cũng đông nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích kỹ nhiều lên. Họ lưu trữ các dữ liệu nay vi cho rằng trong nó ẩn chứa xhhững giả trị nhất đỉnh nào đó.

Tuy nhiên, theo thống kê thì chỉ có một lượng nhỏ của những đữ liêu này (khoảng từ 5% dén 10%) la luén được phân tích. số còn lại họ không biết sẽ phái làm gì hoặc có thể làm gi với chúng nhưng họ vẫn tiếp tục thu thập rất tốn kém với ý nghĩ lo sợ rằng sẽ có cái gì đỏ quan trọng đã bị bỏ qua sau này có lúc cản đến nó. Mặt khác, trong môi trường cạnh tranh, Tigười tá ngày cảng cần có nhiều thông in với tốc độ nhanh đỄ trợ giúp việc ra quyết định và ngày cảng có nhiều gâu hỏi mang tính chối. định tĩnh cần phải trả lời dựa trên một khối lượng đữ liệu khổng lỗ đã có.

Với những lý do như vậy, các phương pháp quản trị và khai thác cơ số đữ liệu truyển thống ngày cảng không đếp ứng được thực lễ đã làm phái. triển một khuynh hướng kỹ thuật mới đỏ là Kỹ thuật phát hiện trí thức và khai phá đữ ligu (KDD - Knowledge Discovery and Data Mining). Kỹ thuật phát hiện trí thức và khai phá đữ liệu đã và đang được nghiên cửu, vng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thể giới, tại Việt Nam kỹ thuật này tượng đổi còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần dưa vào ứng dụng. Bước quan trọng nhất của quá trình này là Khai phá dữ liệu (Data Mining - DM), giúp người sử dụng thu dược những trí thức hữu ¡ch từ những CSDL hoặc các nguồn dữ liệu khổng lễ khác, Rất nhiều đoanh nghiệp và tổ chức trên thể giới đã ứng dụng kĩ thuật khai phá dữ liệu vào hoạt động sản xuất kinh doanh của mình và đã thu được những lợi ích to lớn.

Nhung dé lam được điều đỏ, sự phát triển của các mô hình toán học vả các giải thuật hiệu quả là chìa khoả quan trọng. Vì vậy, trong luận văn này, tác giả sẽ đẻ cập tới hai kỹ -9- Đảnh giá luật { phả dữ liệu Chuyển đổi dit Tiga | Lam sach, tiền xử - lý dữ liệu “Trịch lọc dữ liệu -Gom dữ liệu Hình 1.1: Quả trình phát Bắt đầu của quá trinh là kho dữ liêu thỏ vả kết thúc với trì thức được chiết xuất ra. Về lý thuyết thì cỏ về rất đơn giản nhưng thực sự đây là một quá trình rất khỏ khăn gặp phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình, v. (1) Gom đữ liệu: Tập hợp đữ liệu là bước đầu tiên trong quả trình khai phá dữ liêu.