Tài liệu Phân cụm đa mức web bằng k means dựa trên chủ đề ẩn và thực nghiệm đánh giá

.PDF

125

dangvantuan Báo vi phạm

Tải xuống 98

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đào Minh Tùng PHÂN CỤM ĐA MỨC WEB BẰNG K-MEANS DỰA TRÊN CHỦ ĐỀ ẨN VÀ THỰC NGHIỆM ĐÁNH GIÁ KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Hà Nội - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đào Minh Tùng PHÂN CỤM ĐA MỨC WEB BẰNG K-MEANS DỰA TRÊN CHỦ ĐỀ ẨN VÀ THỰC NGHIỆM ĐÁNH GIÁ KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: Tiến sỹ Đoàn Sơn Hà Nội - 2011 Lời cảm ơn Trước tiên, tôi muốn gửi lời cảm ơn sâu sắc đến Tiến Sĩ Đoàn Sơn và Phó Giáo sư Tiến sĩ Hà Quang Thụy, người đã tận tình hướng dẫn tôi trong suốt quá trình thực hiện khóa luận. Tôi xin gửi lời cảm ơn chân thành và sâu sắc tới các thầy, cô tại trường Đại học Công Nghệ đã dạy dỗ và tận tình chỉ bảo cho tôi trong suốt quá trình học tập tại trường. Tôi xin cảm ơn tập thể sinh viên K52CHTTT Trường Đại học Công Nghệ cũng như các bạn trong phòng nghiên cứu KT-SISLAB đã ủng hộ và khuyến khích tôi trong quá trình nghiên cứu và thực hiện khóa luận này. Tôi xin cám ơn sự hỗ trợ từ đề tài QG.10.38 của Đại học Quốc gia Hà Nội. Cuối cùng, tôi muốn gửi lời cảm vô hạn tới gia đình và bạn bè, những người thân yêu luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp. Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép nhưng chắc chắn sẽ không tránh khỏi những thiếu sót. Tôi rất mong nhận được sự góp ý chân thành của thầy cô và các bạn để tôi hoàn thiện khóa luận của mình. Hà Nội, ngày 20 tháng 5 năm 2011 Sinh viên Đào Minh Tùng i Tóm tắt nội dung Trước sự bùng nổ của thông tin, phân cụm dữ liệu nói chung và phân cụm trang web nói riêng đã trở thành một lĩnh vực nghiên cứu quan trọng. Đặc biệt, hiện nay sự quan tâm cải tiến đối với chất lượng thuật toán phân cụm rất cao vì sự cần thiết của những ứng dụng có thể giúp người sử dụng Internet xử lý trạng thái quá tải thông tin, đưa ra cái nhìn tổng quan về thông tin tìm kiếm được trả về. Khóa luận đề xuất phương pháp phân cụm trang web đa mức dưới dạng cây bằng thuật toán K-means dựa trên chủ đề Nn. Thực nghiệm cho kết quả ban đầu khá tốt, có thể tiếp tục phát triển để ứng dụng trong máy tìm kiếm. i Lời cam đoan Em xin cam đoan rằng đây là công trình nghiên cứu của mình, có sự giúp đỡ từ giáo viên hướng dẫn là TS. Đoàn Sơn. Các nội dung nghiên cứu và kết quả trong đề tài này là trung thực, không sao chép từ bất cứ nguồn nào có sẵn. Những số liệu trong các bảng biểu phục vụ cho việc phân tích, nhận xét, đánh giá được chính tác giả thu thập từ nhiều nguồn khác nhau có ghi trong phần tài liệu tham khảo. Nếu phát hiện có bất kỳ sự gian lận nào, em xin hoàn toàn chịu trách nhiệm trước hội đồng, cũng như kết quả khóa luận tốt nghiệp của mình. Đào Minh Tùng ii Mục lục Lời cảm ơn .............................................................................................................. i Tóm tắt nội dung .................................................................................................... i Lời cam đoan ......................................................................................................... ii Mục lục ................................................................................................................. iii Danh sách bảng ..................................................................................................... v Danh sách hình vẽ ................................................................................................ vi Mở đầu ................................................................................................................... 1 Chương 1. Giới thiệu về phân cụm web đa mức .................................................. 3 1.1. Phân cụm dữ liệu .................................................................................. 3 1.2. Yêu cầu đối với phân cụm dữ liệu ......................................................... 3 1.3. Phân cụm web đa mức .......................................................................... 4 1.4. Các thuật toán phân cụm HAC và K-means .......................................... 5 1.4.1. Thuật toán HAC (Hierarchical agglomerative clustering) ................. 5 1.4.2. Thuật toán K-means .......................................................................... 6 Chương 2. Phân phối Dirichlet $n (LDA) và lấy mẫu Gibbs ............................ 10 2.1. Giới thiệu về phân phối Dirichlet Nn ................................................... 10 2.2. Ước lượng LDA với lấy mẫu Gibbs .................................................... 12 2.3. Phân định chủ đề theo mô hình LDA với lấy mẫu Gibbs ..................... 13 2.4. Mối quan hệ của LDA với các mô hình biến Nn khác .......................... 13 2.4.1. Mô hình unigram ............................................................................ 13 2.4.2. Mô hình phức hợp các unigram ...................................................... 14 2.4.3. Chỉ mục ngữ nghĩa tiềm Nn ............................................................. 15 Chương 3. Mô hình hệ thống .............................................................................. 18 3.1. Tổng quan ........................................................................................... 18 3.2. Tiền xử lý dữ liệu tiếng Việt ............................................................... 20 3.2.1. Phân đoạn câu (Sentence segmentation).......................................... 20 iii 3.2.2. Tách câu (Sentence Tokenization) .................................................. 20 3.2.3. Tách từ ........................................................................................... 21 3.2.4. Lọc bỏ nhiễu ................................................................................... 21 3.3. Phương pháp phân cụm....................................................................... 22 3.4. Đánh giá phân cụm ............................................................................. 23 Chương 4. Thực nghiệm ..................................................................................... 25 4.1. Môi trường thực nghiệm ..................................................................... 25 4.2. Công cụ thực nghiệm .......................................................................... 25 4.3. ChuNn bị dữ liệu ................................................................................. 25 4.3.1. Dữ liệu học ..................................................................................... 25 4.3.2. Dữ liệu kiểm tra .............................................................................. 27 4.4. Quá trình thực nghiệm ........................................................................ 28 4.4.1. Xây dựng mô hình chủ đề Nn .......................................................... 28 4.4.2. Phân cụm mức 1 ............................................................................. 30 4.4.3. Phân cụm mức 2 ............................................................................. 31 4.4.4. Thời gian xây dựng mô hình chủ đề Nn 2 ....................................... 32 Kết luận và định hướng ...................................................................................... 34 Tài liệu tham khảo .............................................................................................. 35 Tiếng Việt ...................................................................................................... 35 Tiếng Anh ...................................................................................................... 35 iv Danh sách bảng Bảng 1: Một số từ nhiễu cần được loại bỏ ................................................................. 22 Bảng 2: Môi trường thực nghiệm ............................................................................... 25 Bảng 3: Chi tiết số lượng trang web được trích rút với 10 chủ đề lớn ........................ 26 Bảng 4: Chi tiết số lượng trang web được trích rút với 5 chủ đề con thuộc lĩnh vực kinh tế ........................................................................................................................ 27 Bảng 5: Bảng các giá trị tham số cho JGibbsLDA để tạo chủ đề n gồm 20 từ .......... 28 Bảng 6: Bảng tham số cho JGibbsLDA để tạo chủ đề n mức 1 gồm 40 từ ................ 30 Bảng 7: Bảng tham số cho JGibbsLDA để tạo chủ đề n mức 2 gồm 20 từ ................ 30 v Danh sách hình vẽ Hình 1: Ví dụ phân cụm web đa mức ........................................................................... 5 Hình 2: Thuật toán K-means ........................................................................................ 8 Hình 3: Quy trình sinh của LDA ................................................................................ 11 Hình 4: Miêu tả sự khác nhau của các mô hình xác suất bằng đồ thị ......................... 14 Hình 5: Sự khác biệt giữa các mô hình xác suất mô tả bằng hình học ........................ 16 Hình 7: Các công đoạn xử lý trang web tiếng Việt ..................................................... 20 Hình 8: Giải thích về các đại lượng TP, FP, FN, TN ................................................. 23 Hình 9: Minh họa về file dữ liệu học cho JGibbsLDA ................................................ 26 Hình 10: Mô tả dữ liệu đánh giá phân cụm mức 1 ..................................................... 28 Hình 11: Mô tả dữ liệu đánh giá phân cụm mức 2 ..................................................... 28 Hinh 12: Ví dụ về kết quả tạo mô hình chủ đề n ....................................................... 29 Hình 13: F-Score của 10 chủ đề qua phân cụm ......................................................... 31 Hình 14: Đánh giá phân cụm mức 2 với số vòng lặp 1000, 1500, 2000...................... 31 Hình 15: Ví dụ về chủ đề bất động sản với số vòng lặp là 1000 và 2000 .................... 32 Hình 16: Đánh giá thời gian xây dựng mô hình chủ đề n mức 2............................... 33 vi Mở đầu Vấn đề mà người tìm kiếm thông tin trên web phải đối mặt hang ngày là lượng thông tin quá lớn trên Internet trong khi những trang web thật sự liên quan đến nhu cầu người dùng rất nhỏ. Những máy tìm kiếm cho phép người dùng thu được những trang web khớp với truy vấn, nhưng số lượng kết quả trả về thường rất lớn, trong đó có nhiều tài liệu không liên quan đến mục đích tìm kiếm. Các máy tìm kiếm cố gắng sắp xếp kết quả, đưa những trang web “liên quan nhất” lên cao hơn, nhưng người dùng vẫn thường xuyên phải thêm hoặc thay đổi câu truy vấn đề lọc bỏ những kết quả không liên quan. Một giải pháp để hỗ trợ người dùng tìm kiếm thông tin nhanh chóng là phân cụm web [2,9]. Do sự tăng lên nhanh chóng của số lượng các trang web, phân cụm web đang trở thành một phần quan trọng trong các máy tìm kiếm. Phân cụm web là một giải pháp sắp xếp lại kết quả tìm kiếm web theo cách thuận tiện hơn cho việc sử dụng.Với một cách thức phân cụm tốt, kết quả tìm kiếm có thể được tự động sắp xếp vào những cụm nhất định, điều này nâng cao tính sẵn sàng (availability) và truy cập được (accessibility) của dữ liệu. Việc biểu diễn dữ liệu văn bản hiệu quả để khai thác mối quan hệ giữa các thành phần đang nhận được nhiều nghiên cứu phát triển [18]. Trong đó có thể kể tới mô hình LSA [24], pLSI [21] và LDA [16]. LDA là mô hình sinh giải quyết được những tồn tại trong LSA và pLSI [16]. Mô hình LDA có nhiều ứng dụng, trong có ứng dụng khảo sát chủ đề Nn của các văn bản. Khóa luận này tập trung theo hướng phân cụm đa mức các bài báo dựa trên mô hình chủ đề Nn và thuật toán phân cụm K-means. Cách thức phân cụm được tiến hành trong khóa luận bao gồm các bước: Trích rút dữ liệu, tiền xử lý dữ liệu, xây dựng mô hình chủ đề Nn, biểu diễn văn bản cần phân cụm qua chủ đề Nn, phân cụm văn bản. Do trên thực tế, các trang web thường được phân cụm theo 2 mức (Ví dụ, trên trang http://www.dantri.com.vn, các trang web được phân vào “Kinh doanh”, “pháp luật”, “sức khỏe”… sau đó các trang web thuộc lĩnh vực “kinh doanh” lại được phân vào cụm nhỏ hơn như “bất động sản”, “chứng khoán” v..v..) trong khuôn khổ khóa luận này, tôi chỉ tập trung phân cụm các trang web theo 2 mức. Phần còn lại của khóa luận được chia thành bốn chương: 1 Chương 1: Phân cụm web đa mức: Trình bày những nội dung cơ bản về phân cụm, phân cụm web, phân cụm web đa mức và hai thuật toán phân cụm được sử dụng phổ biến là HAC và K-means. Chương 2: Giới thiệu về phân phối Dirichlet Nn và lấy mẫu Gibbs: Trình bày những nội dung cơ bản về phân phối Dirichlet Nn và lấy mẫu Gibbs, bao gồm những mô hình toán học và xác suất. Đây là những kiến thức nền tảng cho việc xây dựng mô hình chủ đề Nn. Chương 3: Mô hình thực nghiệm: Trình bày mô hình xây dựng chủ đề Nn. Chương 4: Thực nghiệm: Xây dựng, thử nghiệm và đánh giá phân cụm đa mức với chủ đề Nn. Kết luận: Tổng kết những nội dung chính của khóa luận, những điều đã đạt được, các vấn đề còn tồn tại và hướng phát triển của hệ thống. 2 Chương 1. Giới thiệu về phân cụm web đa mức 1.1. Phân cụm dữ liệu Phân cụm (Clustering) [2,9] là quá trình phân tách tập các đối tượng dữ liệu thành tập có nghĩa các tập con được gọi là cụm (cluster). Thông thường, cho trước một tập n đối tượng, mỗi đối tượng có p thuộc tính, việc phân cụm nhằm mục đích tìm ra cách chia hợp lý n đối tượng vào một số cụm nào đó. Trong đó, một cụm là một tập các đối tượng dữ liệu giống nhau theo một số thuộc tính và khác với các đối tượng dữ liệu thuộc vào cụm khác. Mỗi cụm có thể được xử lý như một nhóm, vì thế phân cụm còn có thể coi như nén dữ liệu. Khác với việc phân lớp đối tượng, nhãn của lớp là chưa biết. Điều này xảy ra thường xuyên với những cơ sở dữ liệu lớn, vì viêc gán nhãn lớp cho số lượng đối tượng dữ liệu lớn là một quá trình tốn kém. Việc phân cụm rất có ích trong đưa ra cái nhìn tổng quan trên toàn thể dữ liệu. Để đạt được điều đó, mỗi cụm cần được tạo nhãn chủ đề, điểu này giúp cho việc định hướng người dùng về tài liệu trong cụm đó. Việc tạo nhãn cho cụm là một vấn đề quan trọng và được nhiều nghiên cứu quan tâm [4, 17, 19, 23]. Thông thường, để phân cụm dữ liệu, ta sử dụng những đại lượng khoảng cách, ví dụ như khoảng cách Euclide. Phân cụm có ứng dụng trong nhiều lĩnh vực như marketing [3, 11, 20], quản lý [3], kinh tế [3] … Phân cụm không phải là một lĩnh vực mới [9] nhưng vấn đề phân cụm kết quả trả về từ máy tìm kiếm được nhiều nhà khoa học quan tâm trong những năm gần đây, với các nghiên cứu về phân cụm để cải tiến chất lượng tìm kiếm web [5-8, 14, 22]. 1.2. Yêu cầu đối với phân cụm dữ liệu Dưới đây là những yêu cầu thông thường đối với phân cụm dữ liệu [9]: 1) Tính mở rộng được (Scalability) Nhiều thuật toán phân cụm làm việc tốt trên tập dữ liệu nhỏ, tuy nhiên, chúng có thể không xử lý được tập dữ liệu lớn, như chứa trên 10 ngàn đối tượng dữ liệu. Một giải pháp cho vấn đề này là áp dụng thuật toán trên từng tập con của miền dữ liệu lớn, tuy nhiên cách làm này có thể dẫn tới kết quả sai lệch. 2) Khả năng xử lý dữ liệu đa chiều Cơ sở dữ liệu có thể có nhiều chiều hay nhiều thuộc tính. Đa số các thuật toán phân cụm có thể làm việc tốt trên dữ liệu ít chiều, tuy nhiên kém trong xử lý dữ liệu đa chiều, đặc biệt khi mà các thuộc tính thưa (sparse). Nhiều thuật toán chỉ đơn giản tạo 3 ra một chiều tương ứng với mỗi từ trong tập các từ của tập dữ liệu. Do số lượng các từ trong mỗi ngôn ngữ đều lớn, không gian dữ liệu thường lên tới trên 10 ngàn chiều, điều này ảnh hưởng lớn đến quá trình thực hiện của thuật toán. Vấn đề về khả năng xử lý dữ liệu đa chiều liên quan mật thiết đến vấn đề về tính mở rộng (Scalability) và tính hiệu quả (Efficiency) 3) Sử dụng tri thức miền ít nhất để quyết định những tham số đầu vào Đa số các thuật toán phân cụm đều yêu cầu người dùng nhập vào những tham số nhất định, ví dụ như số cụm mong muốn. Kết quả phân cụm có thể phụ thuộc nhiều vào những tham số đầu vào đó. Trong khi đó, các tham số thường khó để chọn, đặc biệt khi dữ liệu là nhiều chiều. Điều này không những gây khó khăn cho người dùng, mà còn làm cho chất lượng phân cụm khó kiểm soát. 4) Khả năng xử lý dữ liệu nhiễu Đa số các cơ sở dữ liệu trên thực tế chứa những dữ liệu biên, thiếu, hoặc sai. Những thuật toán phân cụm phục thuộc vào dữ liệu chuNn có thể dẫn tới kết quả phân cụm tồi khi xử lý những dữ liệu này. 5) Phân cụm tăng dần và khả năng độc lập với thứ tự dữ liệu đầu vào Nhiều thuật toán phân cụm không thể xử lý thêm những dữ liệu mới được thêm vào tới những cấu trúc cụm có sẵn mà phải phân cụm lại từ đầu. Một vài thuật toán phụ thuộc vào thứ tự của dữ liệu đầu vào, nghĩa là, cho một tập các đối tượng dữ liệu, những thuật toán đó có thể cho ra những kết quả phân cụm rất khác nhau phụ thuộc vào thứ tự của dữ liệu. Vì thế, việc thiết lập các thuật toán phân cụm có thểm phân cụm tăng dần và đọc lập với thứ tự dữ liệu là rất quan trọng. 6) Khả năng xử lý nhiều kiểu dữ liệu Những chương trình phân cụm cần có khả năng xử lý nhiều kiểu dữ liệu như số, nhị phân, đa thức hoặc tập hợp của những kiểu dữ liệu trên. 7) Phân cụm dựa trên điều kiện Những ứng dụng thực tế cần thi hành phân cụm dưới những loại ràng buộc khác nhau. 8) Các cụm có thể hiểu được và tính sử dụng được Người dùng mong muốn những cụm được phân có tính hiểu được và sử dụng được, nói cách khác, người dùng có thể nhận ra được sự khác biệt giữa cụm dữ liệu này và cụm khác. 1.3. Phân cụm web đa mức Phân cụm trang web [9] là quá trình tổ chức một cách tự động trang web vào các cụm hay nhóm, sao cho các trang web trong cùng một cụm có độ tương đồng cao so và 4 có sự khác biệt lớn với những trang web trong cụm khác. Nói cách khác, quá trình phân cụm hướng tới tối đa độ tương đồng bên trong cụm (intra-cluster sinilarity) và tối thiểu hóa độ tương đồng giữa các cụm (inter-cluster similarity). Thay vì phân cụm trang web thành tập hợp phẳng các cụm, phân cụm trang web đa mức [9] tổ chức các trang web thành một cây thuận tiện cho tìm kiếm. Mối quan hệ cha-con giữa các node trong cây có thể xem như mối quan hệ giữa chủ đề lớn và chủ đề con của chúng. Hình dưới đây mô tả trực quan về phân cụm web: Web … Kinh tế Giáo dục Chứng khoán Bất động sản … Thể thao Thị trường Hình 1: Ví dụ phân cụm web đa mức 1.4. Các thuật toán phân cụm HAC và K-means 1.4.1. Thuật toán HAC (Hierarchical agglomerative clustering) Thuật toán HAC [10] là một thuật toán phân cụm được sử dụng rất rộng rãi và được tích hợp vào các ứng dụng thu nhập thông tin. HAC yêu cầu định nghĩa hàm khoảng cách- hay độ tương tự giữa các cụm và trang web. Ta có thể định nghĩa các hàm khoảng cách trong không gian Euclide như sau: - Khoảng cách giữa hai tài liệu: , = cos , - - Khoảng cách giữa trong tâm của cụm và : , = , trong đó , lần lượt là trọng tâm hai cụm , . Khi tính khoảng cách giữa hai cụm tài liệu, ta có thể dùng những phương pháp sau: 5 o Phương pháp single-link: khoảng cách giữa hai cụm tài liệu là tổng khoảng cách của những thành viên gần nhau nhất: , = ∈,∈ , o Phương pháp complete-link: khoảng cách giữa hai cụm tài liệu là tổng khoảng cách của những thành viên xa nhau nhất: , = ∈,∈ , o Phương pháp group-average: khoảng cách giữa hai cụm tài liệu là tổng khoảng cách trung bình của các thành viên: 1 , = , | || | ∈ , ∈ Thuật toán HAC được mô tả chi tiết như dưới đây: Cho S là tập các trang cần phân cụm, G là tập các cụm, k là số cụm đích, q là độ tương tự nhỏ nhất. Bước 1: Khởi tạo G là tập các cụm chỉ gồm một trang web trong tập S. Bước 2: Nếu || < , tức là đã đạt được số cụm mong muốn: Dừng thuật toán. Bước 3: Tìm hai cụm có độ tương tự (khoảng cách) lớn nhất. Bước 4: Nếu , ! " < # thì dừng thuật toán. Bước 5: Loại bỏ , ! khỏi G. Bước 6: Tạo cụm $ = ∪ ! và = ∪ $. Bước 7: Quay lại bước 2. 1.4.2. Thuật toán K-means Thuật toán k-means [15] có thể xếp vào lớp thuật toán phân cụm phẳng, ý tưởng chính của thuật toán là biểu diễn một cụm bằng trọng tâm của các trang web nằm trong cụm đó. Thuật toán thực hiện bằng cách tối thiểu hóa tổng bình phương khoảng cách từ dữ liệu đến tâm của cụm tương ứng. Việc quyết định phân một trang web vào một cụm là dựa vào độ tương đồng của trang web đó với trọng tậm của các cụm. Tồn tại hai dạng của thuật toán K-means là dạng cứng và dạng mềm. 1.4.2.1. Thuật toán K-means với gán “cứng” Dạng “cứng” phân các trang web đến các cụm theo một trong hai giá trị 0 hoặc 1. Phương pháp biểu diễn vector được sử dụng để biểu diễn trang web. Trong thuật toán này, cụm được thể hiện bằng vector đại diện, vector này thường là vector của trọng tâm của cụm. Để thể hiện cụm thứ i, ký hiệu là , với vector đại diện di sẽ được mô tả như sau: 6 = & ∈ |, ≤ , ! ∀) ≠ + Trong đó sim(u,v) là giá trị hàm khoảng cách giữa hai vector u và v. Trong trường hợp mỗi trang web được yêu cầu chỉ thuộc một cụm nhưng khoảng cách giữa vector đại diện của trang web đó tới vector trọng tâm của hai hay nhiều cụm bằng nhau, ta có thể chọn ngẫu nhiên trong các cụm đó. Thuật toán được mô tả chi tiết qua các bước như sau: Bước 1: Khởi tạo: Chọn số cụm k. Chọn ngẫu nhiên dữ liệu trong tập dữ liệu ban đầu vào k cụm. Bước 2: Tính tâm của cụm. Bước 3: Tính khoảng cách từ các dữ liệu đến tâm các cụm. Chuyển cụm xảy ra nếu khoảng cách từ dữ liệu đến tâm một cụm khác là nhỏ nhất. Bước 4: Kiểm tra: Nếu không có thay đổi về cụm thì thuật toán dừng. Ngược lại, thuật toán quay lại bước 2. Điểm mấu chốt là ở bước 3, việc di chuyển các trang web giữa các cụm để làm cực đại hóa độ tương tự giữa các trang web bên trong một cụm. Độ đo tương tự trong nội tại một cụm được tính bằng công thức: . , = , ! / -∈- Trong đó và lần lượt là tập hợp các trang web và trọng tâm của cụm i; , ! là độ đo cosin giữa và ! . 7 Bắt đầu Số cluster K Không thay đối? Tính tâm cụm Kết thúc Tính khoảng cách từ dữ liệu Nhóm dữ liệu dựa trên khoảng cách Hình 2: Thuật toán K-means Thuật toán K-means không đảm bảo tìm được giá trị cực đại toàn cục của hàm J nhưng ta có thể chạy thuật toán một số lần để thu được giá trị cực đại cục bộ. Kết quả cuối cùng của K-means phụ thuộc rất nhiều vào cách lựa chọn k trang web ban đầu làm trong tâm của k cụm. Nếu ta tiến hành nhiều lần thí nghiệm , trong mỗi lần đều chọn ngẫu nhiên k trang web ban đầu thì kết quả nhận được trong các lần thí nghiệm có thể khác nhau. Nói cách khác, ta có thể tiến hành thí nghiệm một số lần nhất định với giá trị khởi tạo khác nhau và chọn kết quả của lần chạy tối ưu nhất. Trong thực tế, nếu dữ liệu quá lớn hoặc giải thuật không hội tụ (Thuật toán không dừng) có thể dẫn đến thời gian chạy lớn. Do đó, ta có thể sử dụng thêm các điều kiện dừng như dưới đây: • Khi số lượng vòng lặp vượt quá một ngưỡng nào đó. Tuy nhiên, điều kiện dừng này có thể làm cho quá trình phân cụm không được tốt do có thể số vòng chạy chưa đạt mức cần thiết • Khi giá trị J nhỏ hơn một ngưỡng nào đó (người lập trình thiết lập ngưỡng chấp nhận được của thuật toán) • Khi hiệu hai giá trị liên tiếp của J nhỏ hơn một ngưỡng nào đó. (Mức độ “tốt” của việc phân cụm không được cải thiện thêm nhiều sau vòng lặp) Trên thực tế, 3 điều kiện dừng trên có thể được dùng kết hợp với nhau. 8 1.4.2.2. Thuật toán K-means với gán “mềm” Nếu như dạng cứng của thuật toán K-means gán các trang web cho các cụm, dạng “mềm” lại biểu diễn mỗi cụm c sử dụng một vector 0 trong không gian. Do không có một sự rõ ràng trong việc gán các trang web cho các cụm, 0 không trực tiếp liên hệ với các trang web, nói cách khác, nó không nhất thiết phải là trọng tâm của các cụm. Mực tiêu của K-means dạng “mềm” là tìm 0 cho mỗi cụm c để tối thiểu hóa đại 2 lượng ∑ | − 0 | . Chiến lược đơn giản để thực hiện điều này là đưa ra các vector trung bình là khoảng cách từ các trang web đến cụm gần nhất. Việc quét qua các trang web được thực hiện nhiều lần, và với mỗi trang d ta tích lũy một ∆0 cho cụm 0 gần d nhất: 6 − 0 " 7 0 8 ℎ:? ∆ 0 = 5 0 :<8 ℎ= ℎá Sau khi quét một lần qua tất cả các trang web, tất cả các 0@ được cập nhật đồng loạt bởi công thức 0@ ∶= 0@ + ∆0@ , trong đó 6 được gọi là tỷ lệ học. Chú ý, mỗi lần chỉ một trang web d được chuyển vào một 0@ . Việc phân bố trang web d không bị giới hạn chỉ đến một 0@ gần nó nhất mà có thể được chia sẻ giữa nhiều trang web. Việc phân chia cụm c quan hệ trực tiếp đên độ tương tự hiện thời giữa 0@ và d. Ví dụ, có thể làm mềm công thức tính ∆0@ ở trên như sau: 1 | − 0@ | ∆0@ = 6 − 0@ 1 ∑C | − 0@ | Hoặc: D E|EFG| ∆0@ = 6 − 0@ ∑C D E|EFG | 9 Chương 2. Phân phối Dirichlet $n (LDA) và lấy mẫu Gibbs 2.1. Giới thiệu về phân phối Dirichlet $n LDA [16] là mô hình sinh xác suất cho dữ liệu rời rạc như text corpora, là phát triển của một vài mô hình như Bayes ngây thơ, mô hình Hofman’s aspect (cũng được biết đến với tên gọi khác: probabilistic latent semantic indexing- pLSI) [1]. Trong trường hợp mô hình hóa dữ liệu văn bản, LDA quan niệm mỗi tài liệu được tạo ra bởi tập hợp các chủ đề, trong đó tỷ lệ hỗn hợp giá trị liên tục (continuous-valued mixture proportions) được phân phối như một biến ngẫu nhiên Dirichlet. [2]. Về bản chất, LDA là một mô hình Bayesian cấp 3 (cấp từ) trong đó mỗi phần của mô hình được coi như một mô hình trộn hữu hạn trên cơ sở tập các xác suất chủ đề [2]. Mô hình được trình bày như hình sau: Giả sử ta có 1 corpus của M tài liệu biểu diễn bởi H = I , , . . , K L. Tập từ vựng của corpus này là V. Tài liệu m gồm MN từ O rút từ một tập từ vựng: I: , : , . . , :P L. TU Trong LDA, một tài liệu QQQQQQR ON = &ON,S +S/ đầu tiên được tạo ra bằng cách chọn một phân phối trên chủ đề QQQQQR VN từ một phân bố Dirichlet H - Xem thêm -