Khóa luận Sử dụng phương pháp xếp hạng trong bài toán phân cụm Tiếng Việt

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Thị Tâm SỬ DỤNG PHƯƠNG PHÁP XẾP HẠNG TRONG BÀI TOÁN PHÂN CỤM TIẾNG VIỆT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin \ HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Thị Tâm SỬ DỤNG PHƯƠNG PHÁP XẾP HẠNG TRONG BÀI TOÁN PHÂN CỤM TIẾNG VIỆT KHOÁ 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: Th.S Trần Thị Oanh Cán bộ đồng hướng dẫn: CN Nguyễn Minh Tuấn HÀ NỘI - 2009 Lời cảm ơn Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo sư Tiến sĩ Hà Quang Thụy, Thạc sĩ Trần Thị Oanh và Cử nhân Nguyễn Minh Tuấn, những người đã tận tình chỉ bảo và hướng dẫn tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp. Tôi chân thành cảm ơn các thầy cô đã tạo cho tôi những điều kiện thuận lợi để học tập và nghiên cứu tại trường đại học Công nghệ. Tôi xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong phòng Công nghệ tri thức và tương tác người máy – trường ĐH Công nghệ - ĐHQGHN đã tạo điều kiện và giúp tôi tiến hành thực nghiệm của khóa luận. Cuối cùng, tôi muốn gửi lời cảm ơn vô hạn tới gia đình, bạn bè luôn bên cạnh và động viên cũng như tạo những điều kiện tốt nhất cho tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp. Sinh viên Phạm Thị Tâm i Tóm tắt Cùng với sự gia tăng nhanh chóng về số lượng các trang Web thì nhu cầu về khai phá dữ liệu Web ngày càng nhận được sự quan tâm của các nhà khoa học và các nhóm nghiên cứu. Trong lĩnh vực khai phá Web thì phân cụm Web là một trong những bài toán cơ bản và quan trọng. Đây cũng là thành phần chịu nhiều ảnh hưởng của các đặc trưng ngôn ngữ. Khóa luận này tập trung nghiên cứu về bài toán phân cụm Web sử dụng phương pháp xếp hạng. Trên cơ sở lý thuyết phân cụm Web và lựa chọn các đặc trưng của tiếng Việt, khóa luận đã sử dụng phương pháp xếp hạng các cụm từ quan trọng vào phân cụm các tài liệu Web tiếng Việt và tiến hành thực nghiệm. Kết quả thực nghiệm đánh giá theo các đặc trưng TFDF, độ dài (LEN), tương tự nội tại (ICS), entropy nội tại cụm văn bản (CE) cho thấy đặc trưng TFIDF và LEN có ảnh hưởng lớn hơn so với các đặc trưng khác. ii Mục lục Tóm tắt..............................................................................................................................i  Mục lục ........................................................................................................................... ii  Danh sách các bảng ....................................................................................................... iv  Danh sách các hình..........................................................................................................v  Lời mở đầu.......................................................................................................................1  Chương 1. Khái quát về phân cụm Web .........................................................................2  1.1.  Giới thiệu về phân cụm Web.......................................................................2  1.1.1.  Đặc điểm bài toán phân cụm web......................................................3  1.1.2.  Các yêu cầu đối với phân cụm web...................................................4  1.1.3.  Một số độ đo độ đánh giá ..................................................................5  1.2.  Một số thuật toán phân cụm web ................................................................6  1.2.1.  Thuật toán phân cụm bottom-up (HAC - Hierarchical Agglomeraltive Clustering) ...............................................................7  1.2.2.  Thuật toán phân cụm top-down.........................................................9  1.3.  Đánh giá các thuật toán phân cụm ............................................................18  Chương 2: Phân cụm văn bản tiếng Việt.......................................................................19  2.1.  Đặc trưng của tiếng Việt và tách từ trong tiếng việt .................................19  2.1.1.  Đặc trưng của tiếng Việt..................................................................19  2.1.2.  Tách từ tiếng Việt ............................................................................21  2.2.  Một số nghiên cứu về phân cụm tiếng Việt ..............................................23  2.2.1.  Phân cụm từ tiếng Việt bằng phương pháp học máy cấu trúc.........23  2.2.2.  Đánh giá chất lượng phân cụm trong máy tìm kiếm tiếng Việt ......24  2.2.3.  Gom cụm đồ thị và ứng dụng vào việc rút trích nội dung chính của khối thông điệp trên diễn đàn thảo luận...........................................26  iii Chương 3. Phân cụm văn bản sử dụng..........................................................................27  phương pháp xếp hạng cụm từ quan trọng ....................................................................27  3.1.  Khái quát bài toán .....................................................................................27  3.1.1.  Nhu cầu về phân cụm các kết quả tìm kiếm....................................27  3.1.2.  Mô tả bài toán và thuật toán ............................................................29  3.2.  Trích các cụm từ quan trọng .....................................................................31  3.2.1.  Đặc trưng TFIDF .............................................................................32  3.2.2.  Đặc trưng độ dài ..............................................................................33  3.2.3.  Đặc trưng tương tự nội tại cụm .......................................................33  3.2.4.  Đặc trưng entropy nội tại cụm.........................................................34  3.2.5.  Đặc trưng độc lập cụm từ ................................................................34  3.3.  Xếp hạng các cụm từ quan trọng...............................................................35  3.3.1.  Hồi qui tuyến tính ............................................................................35  3.3.2.  Hồi qui logistic ................................................................................36  3.3.3.  Hồi qui hỗ trợ vector (Support vector regression)...........................36  Chương 4. Thực nghiệm và đánh giá ............................................................................38  4.1.  Dữ liệu của thực nghiệm ...........................................................................38  4.2.  Cài đặt thực nghiệm ..................................................................................39  4.2.1.  Phần cứng ........................................................................................39  4.2.2.  Phần mềm ........................................................................................40  4.3.  Phương pháp đánh giá...............................................................................40  4.4.  Kết quả thực nghiệm và đánh giá..............................................................40  Kết luận..........................................................................................................................44  Tài liệu tham khảo .........................................................................................................46  iv Danh sách các bảng Bảng 1: Kết quả phân cụm với truy vấn “Việt Nam” [15] .............................................4  Bảng 2: Các tài liệu chứa cụm từ ở các node ...............................................................16  Bảng 3: So sánh một số đặc điểm của tiếng Việt và tiếng Anh .....................................21  Bảng 4: Các truy vấn trong tập huấn luyện ..................................................................38  Bảng 5: Số cụm từ và số giá trị y=1 trong tập dữ liệu huấn luyện ...............................39  Bảng 6: Độ chính xác khi sử dụng từng đặc trưng để xếp hạng ...................................41  Bảng 7: Độ chính xác của từng truy vấn.......................................................................42  v Danh sách các hình Hình 1: Minh họa để tính cosin của hai vector ...............................................................6  Hình 2: Cây hậu tố mở rộng..........................................................................................16  Hình 3: Kết quả sau khi trộn các tài liệu ......................................................................17  Hình 4: Thống kê về tách từ tiếng Hoa và tiếng Việt [12] ............................................22  Hình 5: Hệ thống phân cụm từ tiếng Việt theo phương pháp học máy cầu trúc ..........24  Hình 6: Ví dụ với truy vấn “Việt Nam” trên máy tìm kiếm google[14]........................28  Hình 7: Ví dụ với truy vấn “Việt Nam” trên máy tìm kiếm Vivisimo[15] ....................28  Hình 8: Biểu đồ độ chính xác khi sử dụng từng đặc trưng để xếp hạng .......................41  Hình 9: Biểu đồ độ chính xác của từng truy vấn...........................................................42  1 Lời mở đầu Internet được phát triển nhanh chóng và sinh ra một khối lượng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web), đã trở thành một kênh quan trọng về mọi thông tin của đời sống. Chính vì vậy, lĩnh vực khai phá Web có tốc độ phát triển vượt bậc, nhận được nhiều sự quan tâm của các nhà khoa học và các nhóm nghiên cứu. Một trong những bài toán quan trọng trong lĩnh vực khai phá Web chính là phân cụm Web [6]. Số lượng các trang Web là rất lớn và luôn luôn thay đổi, mỗi tài liệu không chỉ liên quan đến một khía cạnh mà còn đề cập đến nhiều khía cạnh khác nhau dẫn đến sự trùng lặp thông tin giữa các tài liệu. Xuất phát từ những đặc điểm này mà phân cụm Web chỉ nên thực hiện trên các tài liệu Web của một truy vấn trả về từ máy tìm kiếm. Sau đó kết quả sẽ được tổ chức lại cho người dùng theo các cụm. Khóa luận với đề tài “Sử dụng phương pháp xếp hạng trong bài toán phân cụm tiếng Việt” nghiên cứu về phân cụm Web, phân cụm trong tiếng Việt và bài toán phân cụm tài liệu Web dựa vào việc xếp hạng các cụm từ quan trọng. Khóa luận cũng trình bày kết quả và đánh giá ban đầu về thực nghiệm ứng dụng kỹ thuật phân cụm trên trong các tài liệu web tiếng Việt. Khóa luận gồm 4 chương với nội dung các chương được miêu tả như dưới đây: Chương 1: Khái quát về phân cụm Web. Chương 1 trình bày những nét cơ bản nhất về bài toán phân cụm Web gồm: định nghĩa và đặc điểm của bài toán, một số độ đo độ đánh giá, các phương pháp phân cụm phổ biến, đánh giá về các phương pháp. Chương 2: Phân cụm văn bản tiếng Việt. Chương này sẽ trình bày về các đặc điểm của tiếng Việt và các hướng tiếp cận trong việc tách từ tiếng Việt, đồng thời cũng nêu ra một số đề tài đã được nghiên cứu về phân cụm trong tiếng Việt. Chương 3: Phân cụm văn bản sử dụng phương pháp xếp hạng cụm từ quan trọng. Nội dung chính của chương này là kỹ thuật phân cụm các kết quả trả về của máy tìm kiếm dựa vào việc xếp hạng các cụm từ quan trọng. Chương này đưa ra nhu cầu về phân cụm kết quả tìm kiếm, mô tả về bài toán và thuật toán cũng như những tính toán để giải quyết bài toán. Chương 4: Thực nghiệm và đánh giá trình bày các bước tiến hành thực nghiệm trên các tài liệu Web tiếng Việt, việc thu thập dữ liệu huấn luyện, cài đặt thực nghiệm. Sau đó đưa ra kết quả của thực nghiệm và đánh giá các kết quả này. 2 Chương 1. Khái quát về phân cụm Web 1.1. Giới thiệu về phân cụm Web Trong thời gian gần đây, sự phát triển nhanh chóng của mạng Internet đã tạo nên một khối lượng khổng lồ các dữ liệu dạng siêu văn bản. Vì vậy, nội dung khai phá Web rất được quan tâm. Và một trong những bài toán quan trọng trong lĩnh vực khai phá Web chính là bài toán phân cụm Web. [6] Phân cụm Web - nói một cách khái quát - là việc tự động sinh ra các lớp tài liệu dựa vào sự tương tự của các tài liệu. Các lớp tài liệu ở đây là chưa biết trước, người dùng có thể chỉ yêu cầu số lượng các lớp cần phân loại, hệ thống sẽ đưa ra các tài liệu theo từng tập hợp, từng cụm, mỗi tập hợp chứa các tài liệu tương tự nhau. Phân cụm Web – hiểu một cách đơn giản - là phân cụm trên tập các tài liệu được lấy từ Web. Theo [6] có hai tình huống phân cụm tài liệu, đó là: • Tình huống thứ nhất là việc phân cụm trên toàn bộ một cơ sở dữ liệu (CSDL) có sẵn gồm rất nhiều tài liệu Web. Thuật toán phân cụm cần tiến hành việc phân cụm toàn bộ tập dữ liệu thuộc CSDL đó. Tình huống này thường được gọi là phân cụm không trực tuyến (off-line). • Tình huống thứ hai thường được áp dụng trên một tập tài liệu nhỏ là tập hợp các tài liệu do máy tìm kiếm trả về theo một truy vấn của người dùng. Trong trường hợp này, giải pháp phân cụm được tiến hành kiểu trực tuyến (on-line) theo nghĩa việc phân cụm tiến hành theo từng bộ phận các tài liệu nhận được. Khi đó, thuật toán phải có tính chất “gia tăng” để tiến hành phân cụm ngay khi chưa có đủ tài liệu và phân cụm tiếp theo cần không tiến hành với dữ liệu đã được phân cụm. Do tập tài liệu trên Web là vô cùng lớn cho nên cách phân cụm trực tuyến là thích hợp hơn và phải đòi hỏi tính "gia tăng" của thuật toán phân cụm. Việc xử lý truy vấn cũng như xếp hạng các kết quả trả về của máy tìm kiếm phụ thuộc vào sự tính toán độ tương tự giữa tài liệu và truy vấn, giữa các tài liệu với nhau. Mặc dù các truy vấn liên quan phần nào đến các tài liệu cần tìm, nhưng nó thường quá ngắn và dễ xảy ra sự nhập nhằng. Như đã biết, trung bình các truy vấn trên Web chỉ gồm hai đến ba từ do đó gây nên độ nhập nhằng. Chẳng hạn, truy vấn star dẫn đến sự nhập nhằng rất cao, các tài liệu lấy được liên quan đến astronomy, plants, animals, 3 popular media and sports figures… Độ tương tự giữa các tài liệu của một truy từ đơn như vậy là khác nhau rất lớn. Vì lẽ đó, nếu máy tìm kiếm phân cụm các kết quả theo từng chủ đề thì người dùng có thể hiểu truy vấn nhanh chóng hoặc tìm vào một chủ đề xác định. 1.1.1. Đặc điểm bài toán phân cụm web Việc phân cụm trực tuyến các tài liệu Web kết quả trả về từ máy tìm kiếm là rất khác so với việc phân cụm các tài liệu thông thường. Một đặc điểm của phân cụm tài liệu web chính là số lượng các tài liệu Web là vô cùng lớn và nội dung luôn luôn thay đổi. Ngoài ra một vấn đề nữa là các hệ thống tìm kiếm thông tin là tương tác người dùng cho nên thời gian đáp ứng của hệ thống phải đủ nhanh, cụ thể bài toán ở đây cần thời gian đáp ứng cần tính bằng giây [6]. Mỗi tài liệu Web không chỉ liên quan đến một khía cạnh cụ thể nào đó mà đề cập đến nhiều khía cạnh khác nhau. Chẳng hạn như tài liệu nói về “Việt Nam” cũng có thể đề cập đến cuộc đời và sự nghiệp của “Các danh nhân Việt Nam”. Cho nên tồn tại sự trùng lặp thông tin giữa các tài liệu, có nghĩa là một tài liệu có thể liên quan đến nhiều nội dung khác nhau. Xuất phát từ những đặc điểm đó nên việc phân cụm chỉ nên được thực hiện trên tập các tài liệu Web của mỗi truy vấn trả về từ máy từ máy tìm kiếm. Sau đó kết quả sẽ được tổ chức lại cho người sử dụng. Thông thường một máy tìm kiếm phục vụ hàng triệu truy vấn một ngày cho nên việc phân phối CPU cũng như bộ nhớ cho mỗi truy vấn cần được rút ngắn tối đa. Cho nên việc phân cụm có thể được thực hiện trên một máy tách riêng tại đó chỉ nhận các kết quả của máy tìm kiếm như đầu vào, tạo ra các cụm và biểu diễn chúng cho người sử dụng [6]. 4 Với câu truy vấn “Việt Nam” máy tìm kiếm Vivisimo [15] trả về 254 kết quả tìm kiếm với 41 cụm: Tên cụm Số kết quả Sản 7 Tin tức 27 Giáo 22 Học 21 Viet Nam 24 Nghiệp 20 … … Bảng 1: Kết quả phân cụm với truy vấn “Việt Nam” [15] 1.1.2. Các yêu cầu đối với phân cụm web Để có thể phân các tài liệu Web thành các cụm, việc đầu tiên là cần phải tính được độ tương tự (hay độ tương đồng) giữa các tài liệu trên cơ sở biểu diễn tài liệu Web và xem xét các đo độ tương tự giữa chúng. Thuật toán phân cụm cần đưa ra các điều kiện dừng và gắn nhãn cho các cụm một các thích hợp nhất. Căn cứ đặc điểm và yêu cầu của bài toán phân cụm Web thì phương pháp phân cụm được lựa chọn cần đáp ứng được các yêu cầu sau [6]: • Tính phù hợp: Phương pháp phải tạo nên các cụm trong đó nhóm tài liệu phù hợp với truy vấn của người dùng tách riêng với các nhóm không phù hợp khác. • Tổng hợp phải dễ đọc: Tránh trường hợp thay vì người dùng không phải xem xét danh sách các tài liệu được phân hạng lại phải xem xét danh sách tài liệu trong một cụm. Do đó phương pháp phải cung cấp mô tả ngắn gọn và chính xác của các cụm. • Tính đa hình: Vì các tài liệu có nhiều chủ đề, nên tránh việc hạn chế một tài liệu chỉ thuộc về một cụm. • Sử dụng các mẩu thông tin: Phương pháp phải tạo ra các cụm tốt thậm chí chỉ sử dụng các mẩu thông tin được trả về bởi máy tìm kiếm (thông thường các máy tìm 5 kiếm chỉ trả về các mẩu thông tin mô tả về tài liệu). Điều này tránh cho việc người dùng phải chờ đợi hệ thống tải toàn bộ tài liệu gốc từ Web, tải toàn bộ tài liệu gốc là rất tốn thời gian. • Tốc độ: Một người sử dụng dù kiên nhẫn cũng chỉ có thể xem xét khoảng 100 tài liệu trong danh sách các tài liệu được phân hạng. Hệ thống cần cho phép người dùng có thể đọc qua một tập đủ lớn các tài liệu trong một thời gian chấp nhận được. Vì vậy cần một phương pháp phân cụm khoảng 1000 mẩu thông tin trong vài giây. • Tính gia tăng: Để tiết kiệm thời gian, phương pháp nên xử lý từng mẩu thông tin ngay khi lấy được từ Web để có được kết quả tức thời ứng với mỗi thời điểm. 1.1.3. Một số độ đo độ đánh giá Độ đo đánh giá thuật toán phân cụm là một tiêu chuẩn được chỉ ra bởi một tập n tài liệu D và một tập các truy vấn Q. Với mỗi q Є Q, một tập của các tài liệu phù hợp là Dq Є D được xác định bằng tay. Giả sử có một truy vấn được gửi đến hệ thống, một danh sách được phân hạng các tài liệu (d1, d2, … dn) được trả về. Các hệ thống tìm kiếm thông thường chỉ hiển thị một số mục đầu tiên của danh sách này. Tương ứng với danh sách như vậy, có thể tính một danh sách phù hợp (r1, r2,…rn) bởi các số (0/1) trong đó ri =1 nếu di Є Dq và bằng 0 trong các trường hợp khác. Dưới đây là một số độ đo độ đánh giá được trình bày như trong [6]. • Độ hồi tưởng: Với truy vấn q, độ hồi tưởng (recall) tại hạng k ≥ 1 được xác định là tỷ số của tất cả các tài liệu phù hợp bên trong (d1, d2, … dk): Recall (k) = ∑ ≤≤ ki i q r D 1 1 • Độ chính xác và độ chính xác trung bình - Độ chính xác (precision) tại hạng k là tỷ số của k tài liệu trên cùng tập tài liệu mà thật sự phù hợp: Precision (k) = ∑ ≤≤ ki irk 1 1 - Một cách đo khác là độ chính xác trung bình (Average Precision): Độ chính xác trung bình là tổng của độ chính xác tại mỗi vị trí phù hợp trong danh sách đáp ứng chia cho tổng số các tài liệu phù hợp được chọn. Độ chính xác 6 trung bình bằng 1 khi lấy được toàn bộ các tài liệu phù hợp và xếp loại chúng lên trên tất cả các tài liệu không phù hợp. Average Precision = ∑ ≤≤ × Dk k q kprecisionr D 1 )(1 • Đo độ tương tự - Độ trùng lặp: Độ trùng lặp dùng để đo độ tương tự của một tài liệu này với tài liệu khác hay với một truy vấn. Cách trực tiếp nhất là đo phần giao nhau của các đặc trưng tương ứng, ở đây là trùng lặp của các từ khóa. Đại lượng này cũng được gọi là mức kết hợp (coordination level): )(),( dq KKdqCoordLevel ∩= - Độ tương tự Cosin: Một phương pháp khác có thể được sử dụng để đo độ tương tự giữa các tài liệu là độ tương tự cosin. Kỹ thuật cosin là một kỹ thuật (hay một phương pháp tính) được bắt nguồn từ tính toán vector. Trong thu nhận thông tin, công thức tính toán cosin được sử dụng để chỉ ra (để đo) mức độ tương tự giữa hai tài liệu hoặc giữa tài liệu và truy vấn, (xem hình minh họa). Hình 1: Minh họa để tính cosin của hai vector Hai vector jd và Q càng gần nhau khi góc θ càng nhỏ hay cosin của góc đó càng lớn. Có thể dùng cosin của góc θ làm độ tương tự của hai vector, trong đó cosin của góc giữa hai vector được xác định như sau: wv wv . .cos =θ 1.2. Một số thuật toán phân cụm web Một phương pháp nhằm thi hành thuật toán phân cụm là phân hoạch tập tài liệu vào k tập con hoặc các cụm D1, …, Dk để làm cực tiểu khoảng cách bên trong cụm θ 7 ∑ ∑ ∈i Ddd ddi ),( 2, 121 δ hoặc làm cực đại sự tương tự bên trong cụm ∑∑ ∈i Ddd ddi ),( 2, 121 ρ []. Nếu một biểu diễn bên trong của các tài liệu là có giá trị thì biểu diễn này cũng được dùng để xác định một biểu diễn của các cụm liên quan đến cùng mô hình. Chẳng hạn, nếu các tài liệu được biểu diễn sử dụng mô hình không gian vector, một cụm của các tài liệu có thể được biểu diễn bởi trọng tâm (trung bình) của các tài liệu vector. Khi một biểu diễn cụm là có giá trị, một mục tiêu có thể phân hoạch D thành D1, …,Dk để cực tiểu hóa ),( ii Dd Ddi ρ∑ ∑ ∈ δ hoặc cực đại hóa ),( ii Dd Ddi ρ∑ ∑ ∈ ρ trong đó Di là biểu diễn vector của cụm i. Có thể xem xét tới việc gán tài liệu d cho cụm i như việc đặt một giá trị Boolean zd,i là 1. Điều này có thể phát sinh ra việc phân cụm mềm tại đó zd,i là một số thực từ 0 đến 1. Trong bối cảnh như vậy, ta có thể muốn tìm zd,i để cực tiểu hóa ),( ii Dd Ddi ρ∑∑ ∈ δ hoặc cực đại hóa ),( ii Dd Ddi ρ∑ ∑ ∈ ρ . Việc phân hoạch có thể thực hiện theo hai cách. Bắt đầu với mỗi tài liệu trong một nhóm của nó và kết hợp các nhóm tài liệu lại với nhau cho đến khi số các phân hoạch là phù hợp; cách này gọi là phân cụm bottom-up. Cách khác là có thể khai báo số các phân hoạch mong muốn và gán các tài liệu vào các phân hoạch; cách này gọi là phân cụm top-down [6]. Có thể xem xét một kỹ thuật phân cụm bottom-up dựa vào quá trình lặp lại việc trộn các nhóm của các tài liệu tương tự nhau cho đến khi đạt được số cụm mong muốn, và một kỹ thuật top-down sẽ làm mịn dần bằng cách gắn các tài liệu vào các cụm được thiết đặt trước. Kỹ thuật bottom-up thường chậm hơn, nhưng có thể được sử dụng trên một tập nhỏ các mẫu để khởi tạo các cụm ban đầu trước khi thuật toán top-down tiến hành. 1.2.1. Thuật toán phân cụm bottom-up (HAC - Hierarchical Agglomeraltive Clustering) Mặc dù có rất nhiều các công thức của vấn đề phân cụm, một cách nhận thức đơn giản để tìm ra các cụm là bắt đầu với tất cả các tài liệu và từng bước kết nối chúng thành các nhóm ở đó độ tương tự các tài liệu bên trong mỗi nhóm là cao, và ngừng lại khi đạt được số cụm mong muốn[6]. 8 HAC (Hierarchical Agglomerative Clustering) được sử dụng rất rộng rãi trong phân cụm và các ứng dụng truy xuất thông tin. Dưới đây là đoạn mã giả của thuật toán HAC [6]. 1. Đặt mỗi tài liệu d là một nhóm đơn {d} 2. Đặt G là tập tất cả các nhóm 3. while |G| > 1 do 4. Chọn Ґ, Δ Є G thông qua độ đo tính tương tự s(Ґ, Δ) 5. Loại bỏ Ґ, Δ khỏi G 6. Đặt Ф= Ґ ∪ Δ 7. Thêm Ф vào G 8. end while Quá trình trộn theo cấp bậc tạo thành cây gọi là cây lược đồ. Thông thường, việc trộn giữa các nhóm với độ tương tự s(Ґ ∪ Δ) lớn sẽ thực hiện trước. Giá trị này sẽ ngày càng nhỏ hơn cho các lần trộn sau. Người dùng có thể cắt qua cây lược đồ tại mức thích hợp để lấy được số cụm mong muốn. Các thuật toán khác nhau ở cách chúng tính các giá trị mong muốn để trộn Ґ và Δ. Một độ đo phổ biến được sử dụng là độ tương tự nội tại của Ґ ∪ Δ. Độ tương tự nội tại của một nhóm các tài liệu Ф được định nghĩa là trung bình độ tương tự của từng cặp tài liệu trong Ф[6] . ∑ ∈−= φφφφ 21 , 21 ),( )1( 2)( dd ddss Trong đó độ đo cosin TFIDF được sử dụng phổ biến cho các độ tương tự s(d1, d2) của các tài liệu bên trong. Ngoài ra còn tồn tài nhiều điều kiện trộn khác. Một cách khác để trộn các cặp của các cụm (Ґ, Δ) là maximizes mind1Є Ґ,d2Є Δ s(d1, d2) hay maxd1Є Ґ,d2Є Δ s(d1,d2) hay )./()),(( 2, 121 ΔΓ∑ Δ∈Γ∈ ddsdd Giả sử tài liệu d được biểu diễn trong không gian vector là d ρ (dùng luôn ký hiệu d để biểu diễn vector của tài liệu d). Nếu các tài liệu đã được chuẩn hóa thì s(d1, d2) được dùng là tích vô hướng của (d1, d2). Với bất kỳ cụm Ф các tài liệu, thuật toán duy trì một vector đại diện cho cụm và tính ∑ ∈ = φ φ d dp ρ )( . Độ tích tụ của một cụm được tính theo công thức sau: 9 )1( )(),( )( − −= φφ φφφφ pps và p(Ґ ∪ Δ) = + + 2 Vì vậy để tính s(Ґ ∪ Δ) từ p(Ґ) và p(Δ) tại bước 4 của thuật toán HAC (ở trên) chỉ phải mất thời gian để tính toán các tích vô hướng. Ngoài ra còn một số phương pháp phân cụm bottom up khác như là: Single-link, Group-average, Complete-link [1][9]: • Single-link: với phương pháp này, khoảng cách giữa hai cụng được định nghĩa là khoảng cách giữa những đối tượng giống nhau nhất giữa hai nhóm D(r,s) = Min (d(i,j)) với i thuộc ra và j thuộc s. Với hai cụm bất kỳ, ta tính tất cả các khoảng cách giữa hai phần tử thuộc hai cụm, từ đó suy ra khoảng cách nhỏ nhất tìm được chính là khoảng cách giữa hai cụm. Tại mỗi bước, hai cụm gần nhau nhất sẽ được chọn để ghép lại với nhau. • Complete-link: Phương pháp này đối ngược với single-link, khoảng cách giữa các cụm được định nghĩa là: D(r,s) = Max(d(i,j)) với i thuộc r, j thuộc s. Hai cụm có khoảng cách nhỏ nhất sẽ được chọn để nhóm làm một cụm. • Group-average: phân cụm bằng group-average đánh giá chất lượng phân cụm dựa vào độ tương tự giữa tất cả các cụm, nó tránh được thiếu sót của hai phương pháp single-link và complete-link. Nó tính độ tương tự trung bình sim-ga của tất cả các cặp văn bản, bao gồm cả các cặp trong cùng một cụm, nhưng những độ tương tự tính trong một cùng một cụm không chứa trong phép trung bình. 1.2.2. Thuật toán phân cụm top-down Nếu kỹ thuật phân cụm bottom-up dựa vào quá trình lặp việc trộn các cụm tài liệu tương tự nhau đến khi đạt được số cụm mong muốn thì kỹ thuật top-down lại ngược lại, gán các tài liệu vào các cụm được lập từ trước. Dưới đây sẽ trình bày hai thuật toán phân cụm theo kỹ thuật top-down là k-means và Sufix Tree Clustering. a. Thuật toán k-means ¾ K-means với gán “cứng” Theo các nghiên cứu được công bố, kỹ thuật phân cụm Bottom-up được sử dụng trực tiếp tốn thời gian và không gian O(n2) và không thích hợp cho các tập dữ liệu lớn. 10 Nếu coi như đặt trước số cụm là k, kỹ thuật phân hoạch Top-down thường được sử dụng vì hiệu quả hơn [6]. Một thuật toán nổi tiếng nhất sử dụng kỹ thuật này là thuật toán K-means. 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[6]. Dạng “cứng” ánh xạ tài liệu tới các cụm theo một trong hai giá trị 0 hoặc 1, dạng “mềm” ánh xạ tài liệu tới các cụm theo một giá trị trong khoảng 0 và 1. Trong dạng tổng quát, thuật toán k-means sử dụng các biểu diễn nội tại cho các đối tượng được phân cụm và chính các cụm. Sử dụng phương pháp biểu diễn vector cho tài liệu và dùng vector trọng tâm các tài liệu thuộc cụm để thể hiện cho cụm. Khởi tạo một cấu hình ban đầu tùy ý (hoặc được chọn từ một tính toán từ trước) cho thuật toán k-means, chứa đựng tập các tài liệu được chia thành k cụm với k vector trọng tâm tương ứng đã được tính. Quá trình thực hiện thuật toán theo mô tả sau đây[6]: 1. Khởi tạo các trọng tâm của cụm từ các vector được chọn 2. while có thể tốt hơn do 3. for mỗi tài liệu d do 4. Tìm cụm c tại đó trọng tâm của cụm là gần nhất với d 5. Gán d cho cụm c 6. end for 7. for mỗi cụm c do 8. Tính lại trọng tâm của cụm c dựa vào các tài liệu đã gán cho nó. 9. end for 10. end while Bước cơ bản (vòng lặp while) trong thuật toán k-means được gọi là move-to- nearest. Tồn tại một số cách thức đặt điều kiện cho việc dừng vòng lặp. Một điều kiện dừng vòng lặp while ("có thể tốt hơn") thường được dùng là sau khi thực hiện thân vòng lặp while mà các cụm là không thay đổi (hoặc sự thay đổi là không đáng kể), hoặc trọng tâm của cụm di chuyển các khoảng không đáng kể trong các lần lặp tiếp theo. ¾ Thuật toán K-means với gán “mềm” Thay vì chỉ rõ việc gán các tài liệu cho các cụm, dạng “mềm” của k-means biểu diễn mỗi cụm c sử dụng một vector μc trong không gian. Do không có một sự rõ ràng 11 trong việc gán các tài liệu cho các cụm, μc không trực tiếp liên hệ với các tài liệu – ví dụ nó không cần thiết là trọng tâm của các tài liệu. Mục đích của k-means “mềm” là tìm một μc cho mỗi cụm c để tối thiểu hóa lỗi lượng tử ∑ −d cc d 2min μ . Một chiến lược đơn để giảm lỗi là đưa ra các vector trung bình là khoảng cách từ các tài liệu đến cụm gần nhất[6]. Ta sẽ lập lại việc quét qua các tài liệu, và với mỗi tài liệu d, tích lũy một Δμc cho cụm μc gần d nhất: nếu μc gần d nhất ( ) 0C c d d μ η μ−⎧Δ = ⎨⎩∑ các trường hợp khác Sau khi quét một lần qua tất cả các tài liệu, tất cả các μc được cập nhật đồng loạt bởi công thức μc Å μc + Δμc trong đó η được gọi là learning rate. Nó duy trì một số dữ liệu của quá khứ và làm ổn định hệ thống. Chú ý mỗi tài liệu d chỉ chuyển vào một μc trong mỗi đợt. Việc phân bố tài liệu d không bị giới hạn đến chỉ một μc mà gần nó nhất. Việc phân bố có thể được chia sẻ giữa nhiều tài liệu, việc phân chia cho cụm c quan hệ trực tiếp đến độ tương tự hiện thời giữa μc và d. Ví dụ để có thể làm mềm công thức tính Δμc ở trên như sau: )( /1 /1 2 2 c c c d d d μ μ μημ γ γ − − −=Δ ∑ Hoặc )( )exp( )exp( 2 2 c c c d d d μμ μημ γ γ − −− −−=Δ ∑ Tồn tại nhiều quy tắc cập nhật khác có thể được sử dụng. Gán “mềm” không làm mất đi liên kết chặt trong việc tạo nên phân bố các tài liệu cho một cụm đơn đạt được một cách tỉ mỉ[6]. b. Thuật toán STC (Suffix Tree Clustering) Theo [11][13] STC là thuật toán phân cụm dựa vào việc nhận dạng các cụm từ thường xuyên xuất hiện trong một nhóm văn bản. Trong hoàn cảnh của chúng ta, một cụm từ là một chuỗi có trình tự của một hoặc nhiều hơn một từ. Chúng ta định nghĩa 12 một base cluster (cụm cơ sở) là một tập hợp các văn bản cùng chia sẻ một cụm từ nào đó. Thuật toán gồm ba bước: (1) “làm sạch” tài liệu (document “learning”), (2) xác định các cụm cơ sở (base clusters) sử dụng cây hậu tố, (3) trộn các cụm cơ sở tạo thành các cụm. (1)Trong bước làm sạch tài liệu, xóa tất cả các hậu tố và tiền tố của các từ nếu có, đưa toàn bộ số nhiều về số ít, loại bỏ các ký tự không phải là một từ (như các thẻ HTML, hệ thống dấu chấm câu), các từ trong tài liệu được giữ nguyên vị trí. (2) Xác định các cụm cơ sở: Theo định nghĩa trong [13] thì cây hậu tố T là một cây có hướng có gốc, biểu diễn một chuỗi s bất kỳ có chiều dài m với đúng m nút lá. Mỗi cạnh trên cây hậu tố đều được gán nhãn bằng một chuỗi con khác rỗng của chuỗi s. Các nhãn của hai cạnh bất kỳ xuất phát từ một nút chung phải bắt đầu bằng các ký tự khác nhau. Đối với nút lá của cây hậu tố, việc kết các nhãn của các nút nằm trên con đường đi từ gốc đến nút lá đó sẽ tạo thành một hậu tố của chuỗi s. Như tên của nó, cây hậu tố sẽ biểu diễn các chuỗi hậu tố của 1 từ hoặc một cụm từ. Chuỗi hậu tố là tập hợp các đơn vị từ hoặc chữ cái cạnh nhau đi sau từ hoặc cụm từ. Đơn vị từ ở đây có thể là chữ cái nếu xây dựng cây hậu tố cho từ, và là từ nếu xây dựng cây hậu tố cho 1 cụm Lấy ví dụ: Từ misisippi có các hậu tố là T1 = mississippi T2 = ississippi T3 = ssissippi T4 = sissippi T5 = issippi T6 = ssippi T7 = sippi T8 = ippi T9 = ppi T10 = pi 13 T11 = i Ta có thể sắp xếp lại từ tự dãy hậu tố trên như sau: T11 = i T8 = ippi T5 = issippi T2 = ississippi T1 = mississippi T10 = pi T9 = ppi T7 = sippi T4 = sissippi T6 = ssippi T3 = ssissippi Việc xây dựng như trên giúp ta xây dựng một cây với đặc điểm là: • Không có 2 nút nào cùng là con của một nút có nhãn cạnh như nhau. • Và có thể đưa ra tất cả các tập con với các đơn vị từ liên tiếp có đơn vị cuối là đơn vị cuối của từ, cụm từ được đưa vào phân tích. • Có một nút gốc sinh ra cây • Mỗi nút trong có ít nhất 2 nút con • Các nhãn được đặt phải có liên kết với nhau. • Với mỗi hậu tố của s, tồn tại một nút có nhãn là s. Cây hậu tố được tổ chức thành cây gồm nhiều nút. Mỗi nút sẽ lưu trữ tất cả các thông tin về các cụm từ ( tần số xuất hiện trong tập văn bản, tần số xuất hiện trong từng văn bản) trong khi quan hệ giữa chúng lại nói lên sự tồn tại của các cụm từ Trong phân cụm, người ta sử dụng cây hậu tố mở rộng để phân tích các câu: [11] Cây hậu tố mở rộng là cây hậu tố nhằm kết tất cả các hậu tố của các câu trong văn bản. 14 Tức là ta phân tích văn bản bằng cây hậu tố, mỗi câu được coi là một hậu tố, mỗi hậu tố của câu cũng là một hậu tố. Mỗi nút có thể là 1 tử, hoặc là 1 cụm từ đi liền. Sau đó xét tất cả các cụm được coi là hậu tố và xét quan hệ của chúng với nhau để nhóm lại thành một cây. Ví dụ một cây hậu tố với tập hợp các string là 3 câu: “cat ate cheese”, "mouse ate cheese too" , "cat ate mouse too". Phân tích với cây hậu tố với mỗi đơn vị là một từ. Ở trong văn bản gồm 3 câu này sẽ có các cụm từ được đưa ra lần lượt như sau: 1. cat [2]( 1 3) 2. cat ate [2]( 1 3) 3. cat ate cheese [1]( 3) 4. cat ate mouse [1]( 1) 5. cat ate mouse too [1]( 1) 6. ate [3]( 1 2 3) (ate xuất hiện 3 lần trong cả 3 câu) 7. ate cheese [2]( 2 3) 8. ate cheese too [1]( 2) 9. ate mouse [1]( 1) 10. ate mouse too [1]( 1) 11. cheese [2]( 2 3) 12. cheese too [1]( 2) 13. mouse [2]( 1 2) 14. mouse ate cheese [1]( 2) 15. mouse ate cheese too [1]( 2) 16. mouse too [1]( 1) 17. too [2]( 1 2] 15 và cây hậu tố chúng ta xây dựng được sẽ là tree1>|---cat ate cheese |---ate cheese |---cheese Tree2>|---mouse ate cheese too |---ate cheese too |--- cheese too |--- too Tree3>|---cat ate mouse too |---ate mouse too |--- mouse too |---too Coi mỗi hậu tố là một vector. Ta so sánh độ tương đồng giữa các vetor và dùng các thuật toán gom cụm để gom các câu trong văn bản lại và tổng hợp đưa ra vector đặc trưng cho câu. Cây cuối cùng được đưa ra là TreeÆ|---cat ate|---cheese | |----mouse | |---ate|---cheese|---too | | |--- $ | |---mouse too | |---mouse|---too | |---ate cheese too |---cheese|---too | |---$ |---too 16 Hình 2: Cây hậu tố mở rộng Trong đó Node(a, b): a= hậu tố thuộc câu b= số thứ tự của lần xuất hiện chúng ta gán nhãn cho tất cả các nút trong của cây. Mỗi nhãn này tương đương với một từ hoặc một cụm từ nhận được từ các cạnh liền nhau từ gốc đến nhãn đó. Sau đó đánh giá các nút này. Node Cụm từ Văn bản a Cat ate 1, 3 b Ate 1, 2, 3 c Cheese 1, 3 d Mouse 2, 3 e Too 2, 3 F Ate cheese 1, 2 Bảng 2: Các tài liệu chứa cụm từ ở các node Và bằng cách này, cụm cơ sở được đưa ra dựa vào số văn bản mà cụm từ này xuất hiện và số từ trong cụm. Công thức: S(B) = |B| * f 17 Trong đó: |B| là số văn bản trong cụm cơ sở B |P| số lượng từ hợp pháp trong cụm P (have non zero score) zero score words: stopwords, quá ít(40%) hàm f không xác định với các cụm từ có độ dài bằng 1, là một hàm tuyến tính với những cụm từ có độ dài từ 2 đến 6 và sẽ không đổi với những cụm từ dài hơn 6. (3)Một vấn đề đặt ra là các văn bản có thể chứa nhiều cụm từ giống nhau. Vì thế với cách phân cụm cơ sở như trên thì việc 2 cụm cơ sở có chia sẻ chung một số văn bản có xác suất khá lớn. Để tránh việc trùng lấp này chúng ta trộn những cụm có chứa số văn bản dùng chung lại thành một cụm. Giả sử Bm and Bn là 2 cụm phân biệt. Gọi |Bm∩Bn| là tập hợp các văn bản thuộc cả 2 cụm trên. Chúng ta định nghĩa độ tương tự giữa 2 cụm là 1 nếu: |Bm∩Bn|/|Bm| >0.5 và |Bm∩Bn|/|Bn| > 0.5. Và là 0 trong trường hợp còn lại Hình 3: Kết quả sau khi trộn các tài liệu Xét trong ví dụ trên. Các thông số được thể hiện như hình trên. Mỗi nút là một cụm và mỗi cạnh nối với nhau thể hiện rằng độ tương tự giữa 2 cụm là lớn hơn 1 tức là các cụm có tồn tại một cạnh nối có thể hợp lại với nhau thành một cụm. như vậy sơ đồ trên thể hiện duy nhất một cụm. 18 Xét trong trường hợp của ví dụ này. Ta thấy b (ate) là một stopword, nút b sẽ được đánh giá là 0. Như vậy các cạnh nối từ b cũng bị bỏ đi và chúng ta có 3 cụm được đưa ra là “mouse too” “cat ate” “ate cheese” 1.3. Đánh giá các thuật toán phân cụm Như đã được giới thiệu, thuật toán AHC thường chậm khi áp dụng cho các tập tài liệu lớn. Các thuật toán khác theo hướng này như Single-link và Group-average có thời gian thực hiện là O(n2), đồng thời thời gian kết nối hoàn toàn (complete-link) là O(n3). Các thuật toán theo hướng này là quá chậm so với yêu cầu của bài toán phân cụm Web. Một điểm đáng chú ý nữa đối với các thuật toán HAC là điều kiện dừng. Đã có rất nhiều đề xuất về điều kiện dừng được đưa ra nhưng chủ yếu là dựa trên việc điều kiện dừng đã được xác định trước (chẳng hạn, dừng khi chỉ còn 5 cụm). Điều kiện dừng đối với các thuật toán này (HAC) là cực kỳ quan trọng. Nếu như thuật toán trộn các cụm “tốt” với nhau có thể tạo ra kết quả không theo mong muốn của người dùng. Trên Web, với kết quả trả về theo truy vấn là vô cùng đa dạng (về số lượng, độ lớn, kiểu và sự phù hợp của các tài liệu) thì điều kiện dừng không tốt sẽ làm cho kết quả trở nên nghèo nàn [6]. Thuật toán k-means thuộc vào lớp các thuật toán phân cụm thời gian tuyến tính và là những lựa chọn tốt nhất để đáp ứng yêu cầu về tốc độ của bài toán phân cụm on- line. Thời gian thực hiện của các thuật toán này là O(nk) trong đó k là số các cụm mong muốn [6]. Thêm một ưu điểm của thuật toán K-means so với HAC là việc đáp ứng các yêu cầu của bài toán phân cụm Web là nó có thể tạo ra các cụm có sự giao thoa. Điểm yếu chính của thuật toán này là nó chạy hiệu quả nhất chỉ khi các cụm mong muốn là các miền hình cầu đối với độ đo tương tự được dùng. Không có lý do gì để tin rằng các tài liệu sẽ thuộc vào các miền cầu. Vì vậy thuật toán có thể làm mất đi các thông tin có giá trị. Các thuật toán như HAC hay K-means đều không là các thuật toán gia tăng. Một số thuật toán gia tăng đã được phát triển như thuật toán phân cụm cây hậu tố (Suffix Tree Clustering - STC), với thời gian thực hiện O(n) trong đó n là kích thước của tập tài liệu[6]. 19 Chương 2. Phân cụm văn bản tiếng Việt 2.1. Đặc trưng của tiếng Việt và tách từ trong tiếng việt Có thể nói, khai phá web là giao thoa của khai phá dữ liệu, xử lý ngôn ngữ tự nhiên và Word-Wide-Web. Vì vậy để có thể làm việc được với các tài liệu web tiếng Việt cần phải tìm hiểu về các đặc trưng của tiếng Việt và việc tách từ tiếng Việt. 2.1.1. Đặc trưng của tiếng Việt Tiếng Việt thuộc ngôn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm tách rời nhau và được thể hiện bằng một chữ viết. Đặc điểm này thể hiện rõ rệt ở tất cả các mặt ngữ âm, từ vựng, ngữ pháp. Dưới đây trình bày một số đặc điểm của tiếng Việt theo các tác giả ở Trung tâm ngôn ngữ học Việt Nam đã trình bày Error! Reference source not found.. a. Đặc điểm ngữ âm Tiếng Việt có một loại đơn vị đặc biệt gọi là "tiếng", về mặt ngữ âm, mỗi tiếng là một âm tiết. Hệ thống âm vị tiếng Việt phong phú và có tính cân đối, tạo ra tiềm năng của ngữ âm tiếng Việt trong việc thể hiện các đơn vị có nghĩa. Nhiều từ tượng hình, tượng thanh có giá trị gợi tả đặc sắc. Khi tạo câu, tạo lời, người Việt rất chú ý đến sự hài hoà về ngữ âm, đến nhạc điệu của câu văn. b. Đặc điểm từ vựng: Mỗi tiếng nói chung là một yếu tố có nghĩa. Tiếng là đơn vị cơ sở của hệ thống các đơn vị có nghĩa của tiếng Việt. Từ tiếng, người ta tạo ra các đơn vị từ vựng khác để định danh sự vật, hiện tượng..., chủ yếu nhờ phương thức ghép và phương thức láy. Việc tạo ra các đơn vị từ vựng ở phương thức ghép luôn chịu sự chi phối của quy luật kết hợp ngữ nghĩa, ví dụ: đất nước, máy bay, nhà lầu xe hơi, nhà tan cửa nát... Hiện nay, đây là phương thức chủ yếu để sản sinh ra các đơn vị từ vựng. Theo phương thức này, tiếng Việt triệt để sử dụng các yếu tố cấu tạo từ thuần Việt hay vay mượn từ các ngôn ngữ khác để tạo ra các từ, ngữ mới, ví dụ như tiếp thị, karaoke, thư điện tử (e-mail), thư thoại (voice mail), phiên bản (version), xa lộ thông tin, siêu liên kết văn bản, truy cập ngẫu nhiên, v.v. 20 Việc tạo ra các đơn vị từ vựng ở phương thức láy thì quy luật phối hợp ngữ âm chi phối chủ yếu việc tạo ra các đơn vị từ vựng, chẳng hạn như chôm chỉa, chỏng chơ, đỏng đa đỏng đảnh, thơ thẩn, lúng lá lúng liếng, v.v. Vốn từ vựng tối thiểu của tiếng Việt phần lớn là các từ đơn tiết (một âm tiết, một tiếng). Sự linh hoạt trong sử dụng, việc tạo ra các từ ngữ mới một cách dễ dàng đã tạo điều kiện thuận lợi cho sự phát triển vốn từ, vừa phong phú về số lượng, vừa đa dạng trong hoạt động. Cùng một sự vật, hiện tượng, một hoạt động hay một đặc trưng, có thể có nhiều từ ngữ khác nhau biểu thị. Tiềm năng của vốn từ ngữ tiếng Việt được phát huy cao độ trong các phong cách chức năng ngôn ngữ, đặc biệt là trong phong cách ngôn ngữ nghệ thuật. Hiện nay, do sự phát triển vượt bậc của khoa học-kĩ thuật, đặc biệt là công nghệ thông tin, thì tiềm năng đó còn được phát huy mạnh mẽ hơn. c. Đặc điểm ngữ pháp Từ của tiếng Việt không biến đổi hình thái. Đặc điểm này sẽ chi phối các đặc điểm ngữ pháp khác. Khi từ kết hợp từ thành các kết cấu như ngữ, câu, tiếng Việt rất coi trọng phương thức trật tự từ và hư từ. Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các quan hệ cú pháp. Trong tiếng Việt khi nói “Anh ta lại đến” là khác với “Lại đến anh ta”. Khi các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước giữ vai trò chính, từ đứng sau giữ vai trò phụ. Nhờ trật tự kết hợp của từ mà "củ cải" khác với "cải củ", "tình cảm" khác với "cảm tình". Trật tự chủ ngữ đứng trước, vị ngữ đứng sau là trật tự phổ biến của kết cấu câu tiếng Việt. Phương thức hư từ cũng là phương thức ngữ pháp chủ yếu của tiếng Việt. Nhờ hư từ mà tổ hợp “anh của em” khác với tổ hợp “anh và em”, “anh vì em”. Hư từ cùng với trật tự từ cho phép tiếng Việt tạo ra nhiều câu cùng có nội dung thông báo cơ bản như nhau nhưng khác nhau về sắc thái biểu cảm. Ví dụ, so sánh các câu sau đây: - Ông ấy không hút thuốc. - Thuốc, ông ấy không hút. - Thuốc, ông ấy cũng không hút. Ngoài trật tự từ và hư từ, tiếng Việt còn sử dụng phương thức ngữ điệu. Ngữ điệu giữ vai trò trong việc biểu hiện quan hệ cú pháp của các yếu tố trong câu, nhờ đó nhằm đưa ra nội dung muốn thông báo. Trên văn bản, ngữ điệu thường được biểu hiện bằng 21 dấu câu. Sự khác nhau trong nội dung thông báo được nhận biệt khi so sánh hai câu sau: - Đêm hôm qua, cầu gãy. - Đêm hôm, qua cầu gãy. Qua một số đặc điểm nổi bật vừa nêu trên đây, chúng ta có thể hình dung được phần nào bản sắc và tiềm năng của tiếng Việt 2.1.2. Tách từ tiếng Việt Các tác giả [6][12]rút ra một số đặc điểm của từ tiếng Việt như sau: - là đơn vị có ranh giới trùng với hình vị và âm tiết - không có sự biến đổi hình thái trong quá trình sử dụng - là đơn vị có sẵn, được tái hiện trong khi nói - có tính định hình hoàn chỉnh - Có thể chia từ tiếng việt thành hai loại: từ đơn và từ phức Chính từ những đặc điểm này mà tách từ là một khó khăn chính trong việc xử lý các văn bản tiếng Việt. Mặc dù được viết bằng các ký tự La tinh mở rộng, tiếng Việt cũng có những đặc tính chung với các ngôn ngữ Đông Nam Á khác như khó xác định ranh giới giữa các từ và có các điểm khác biệt về phonetic, văn phạm và ngữ nghĩa so với tiếng Anh. Do đó, rất khó có thể áp dụng các kỹ thuật và hướng tiếp cận đã được nghiên cứu và thử nghiệm thành công trên tiếng Anh cho tiếng Việt nếu không xây dựng thành công giải pháp cho việc tách từ trong văn bản tiếng Việt. Dưới đây là một số điểm khác biệt chính giữa tiếng Việt và tiếng Anh được trình bày trong [12]. Đặc điểm Tiếng việt Tiếng Anh Đơn vị cơ bản Tiếng Từ Tiền tố/Hậu tố Không có Có Từ loại Not unanimous Được định nghĩa rõ Ranh giới từ Tổ hợp có nghĩa dựa vào ngữ cảnh của các tiếng Khoảng trắng hoặc dấu câu Bảng 3: So sánh một số đặc điểm của tiếng Việt và tiếng Anh 22 Những đặc điểm này làm cho việc tách từ tiếng việt trở nên khó khăn hơn. Dưới đây là kết quả khảo sát về tách từ trong văn bản tiếng hoa và thống kê về tách từ tiếng Việt được công bố hiện tại [12]. Hình 4: Thống kê về tách từ tiếng Hoa và tiếng Việt [12] Các hướng tiếp cận dựa trên “từ”: được chia thành 3 nhóm: dựa vào thống kê, dựa vào từ điển và nhóm lai, nhằm tách từ trọng vẹn trong câu. Các giải pháp dựa theo hướng tiếp cận vào thống kê cần phải dựa vào thông tin thống kê như term, từ hay tần số ký tự. hay xác suất cùng xuất hiện trong một tập dữ liệu cơ sở. Do đó, tính hiệu quả của các giải pháp này chủ yếu dựa vào dữ liệu huấn luyện cụ thể được sử dụng. Trong hướng tiếp cận dựa vào từ điển, các đoạn văn bản được đối sánh dựa vào từ điển. Việc xây dựng từ điển các từ và ngữ pháp tiếng việt hoàn chỉnh là không khả thi. Hướng tiếp cận lai áp dụng nhiều cách khác nhau để tận dụng ưu điểm của các giải pháp. Các hướng tiếp cận để phân loại văn bản tiếng việt dựa vào từ chỉ khả thi khi có một bộ từ vựng tốt. 23 Hướng tiếp cận dựa trên ký tự: có thể chia làm hai nhóm uni-gram và n-gram. Các phương pháp này tuy đơn giản nhưng đã đem lại kết quả khả thi. 2.2. Một số nghiên cứu về phân cụm tiếng Việt Cho đến nay đã có khá nhiều các công trình nghiên cứu về phân cụm trong tiếng Việt và đều đạt được những kết quả khả quan. Dưới đây, khóa luận sẽ trình bày ba nghiên cứu về phân cụm trong tiếng Việt là phân cụm từ tiếng Việt bằng phương pháp học máy cấu trúc [2], đánh giá chất lượng phân cụm trong máy tìm kiếm tiếng Việt [1], gom cụm đồ thị và ứng dụng vào việc trích rút nội dung chính của khối thông điệp trên diễn đàn thảo luận[3]. 2.2.1. Phân cụm từ tiếng Việt bằng phương pháp học máy cấu trúc Nghiên cứu về phân cụm từ tiếng Việt là khá mới mẻ đối với bài toán tiếng Việt[2]. Bài toán phân cụm từ tiếng việt được phát biểu như sau: gọi X là câu đầu vào tiếng Việt bao gồm một dãy các từ tố ký hiệu X=(X1, X2,…, Xn). Cần xác định Y=(Y1,Y2,…, Yn) là một dãy các nhãn cụm từ (cụm danh từ, cụm động từ). Bài toán được qui về học đoán nhận dãy (có thể được thực hiện qua việc sử dụng các mô hình học máy ….). Qui trình học được thực hiện bằng cách gán nhãn câu mới ( không thuộc tập huấn luyện). Để thực hiện việc gán nhãn cụm cho câu tiếng việt, tác giả sử dụng hai mô hình học khá thông dụng bao gồm: Conditional Random Fields (CRFs) và Online Learing. Cả hai phương pháp đối với bài toán này đều dựa trên giả thuyêt các từ tố trong câu X=(X1, X2,…, Xn) tuân theo quan hệ của chuỗi Markov. Hoạt động của hệ thống góp nhóm từ tiếng việt được thể hiện ở hình dưới [2]: 24 Hình 5: Hệ thống phân cụm từ tiếng Việt theo phương pháp học máy cầu trúc Trong thực nghiệm, tác giả sử dụng dữ liệu huấn luyện từ VTB (VietTree Bank) cho bài toán phân cụm sử dụng mô hình CRFs và mô hình học Online Learning. Số lượng dữ liệu không nhiều (260 câu được gán nhãn) nhưng kết quả thực nghiệm rất khả quan. 2.2.2. Đánh giá chất lượng phân cụm trong máy tìm kiếm tiếng Việt Nhóm tác giả nghiên cứu về các phương pháp đánh giá chất lượng phân cụm và áp dụng đánh giá chất lượng kết quả phân cụm của máy tìm kiếm VNSEN. VNSEN là máy tìm kiếm dựa trên mã nguồn mở có tích hợp phân cụm do nhóm tác giả phát triển. Có nhiều phương pháp phân cụm khác nhau như k-mean, STC, HAC có thể áp dụng vào phân cụm các trang Web trả về của máy tìm kiếm. Và việc đánh giá thường dựa vào chất lượng kết quả phân cụm. Để người dùng có thể tìm được tài liệu mong muốn một cách nhanh chóng thì cần phải gán nhãn các cụm tốt. Tồn tại một số phương pháp đánh giá như sau [1]: - Đánh giá phân cụm dựa vào kinh nghiệm của người dùng: nhãn cụm cần ngắn gọn súc tích và không trùng lặp quá nhiều, số lượng cụm tạo ra vừa đủ để người dùng không bị quá tải bởi các chủ đề quá cụ thể, nhãn cụm cần tránh chứa các từ truy vấn. Thuật toán phân cụm phải đủ nhanh để có thể phân cụm với lượng thời gian phù hợp. Xử lý ngôn ngữ cũng rất quan trọng để tránh các từ gần nghĩa, đồng nghĩa. 25 - Các tiêu chí đánh giá độ kết dính và cô lập của các cụm: độ cô đọng súc tích là độ dính kết hoặc đơn nhất của mỗi cặp đối tượng trong từng cụm riêng rẽ. Độ cô lập đo sự tách biệt giữa hai cụm. Trong [1], Nguyễn Thi Thu Chung và cộng sự giới thiệu 4 tiêu chuẩn đánh giá chất lượng cho phân cụm để bảo đảm tính kết dính và độc lập là: giảm tối thiểu tổng khoảng cách (tổng khoảng cách giữa trọng tâm các cụm với trọng tâm toàn cục và tổng khoảng cách giữa đối tượng với trọng tâm của cụm chứa đối tượng), phân cụm sao cho độ tách biệt giữa các cụm là lớn nhất, vị trí cụm của đối tượng và số lượng đối tượng có vị trí cụm đúng. - Phương pháp đánh giá dựa vào tập dữ liệu mẫu: chọn một chuẩn cơ sở để so sánh khả năng phân cụm của bộ phân cụm: độ đo chất lượng phân cụm, đo chất lượng của một hệ thống phân cụm bởi các mức. Một số độ đo được sử dụng là MNI (normalized mutual information), độ hồi tưởng, độ chính xác, F, Purity (chỉ ra độ tinh khiết, rõ ràng của cụm i). Từ các phương pháp trên tác giả đã tiến hành đánh giá chất lượng phân cụm của máy tìm kiếm VNSEN dựa trên cây phân cấp chủ đề và so sánh với kết quả phân cụm của máy tìm kiếm vivisimo[1]. - Dựa vào cây phân cấp chủ đề: cây phân cấp chủ đề là một cấu trúc thư mục Web lớn nhất được xây dựng. Tác giả tiến hành thu thập tài liệu trên wikipedia tiếng Việt và tạo cây phân cấp thô ban đầu. Sau đó lọc ra các chủ đề chưa có tài liệu, các tài liệu chưa có nội dung hoặc chưa được dịch. Thực hiện tách các thẻ html. Hiện tại, đã xây dựng được cây phân cấp với 10 gốc chủ đề và 500 chủ đề các cấp. Thử nghiệm và thông qua hai độ đo là F và Purity cho thấy modul phân cụm có chất lượng tốt. - So sánh kết quả phân cụm với máy tìm kiếm vivisimo: lựa chọn các truy vấn tiếng Việt mang nghĩa tổng quát để phân cụm được rõ ràng. Tác giả lấy kết quả trả về của google và tiến hành phân cụm với VNSEN. Sau đó so sánh kết quả phân cụm của VNSEN và vivisimo. Nguyễn Thi Thu Chung và cộng sự [1] đã trình bày các phương pháp đánh giá chất lượng phân cụm và xây dựng cây phân cấp chủ đề dựa trên wikipedia tiếng Việt để phục vụ đánh giá. Qua đó đánh giá chất lượng phân cụm của VNSEN và đưa ra kết quả khả quan. 26 2.2.3. Gom cụm đồ thị và ứng dụng vào việc rút trích nội dung chính của khối thông điệp trên diễn đàn thảo luận Trong các hệ thống trực tuyến, diễn đàn thảo luận là phương tiện hữu hiệu để trao đổi và khối lượng thông tin trên diễn đàn là rất lớn. Để người quản lý có thể nắm bắt các nội dung chính của thông tin trao đổi trên diễn đàn trong một giai đoạn, cần xây dựng một hệ thống gom cụm các thông điệp, hỗ trợ trích rút nội dung chính trong khối thông điệp [3]. Đỗ Phúc và cộng sự trình bày cách sử dụng mạng Kohonen để gom cụm các đồ thị đặc trưng văn bản và rút trích các ý chính từ khối văn bản hỗ trợ tạo trích lược thông tin chính trong khối văn bản. Mạng Kohonen có thể gom cụm dữ liệu mà không cần định trước số cụm. Các bước thực hiện của phương pháp này như sau [3]: - Biều diễn văn bản bằng đồ thị: trích rút các từ phổ biến trong văn bản, tính các thành phần có ý nghĩa dựa trên tần suất xuất hiện đồng thời của hai từ trong một câu, đoạn văn bản. Nếu tần suất xuất hiện đồng thời của hai từ lớn hơn một ngưỡng cho trước thì sẽ xuất hiện một cung nối hai từ này. Ở đây, các từ tiếng Việt cũng được tách đúng các từ đơn và từ ghép nhằm tạo chính xác các đỉnh trong đồ thị. - Dữ liệu nhập vào mạng Kohonen là tập các đồ thị đặc trưng văn bản. Sau khi huấn luyện, các đồ thị nhập sẽ được gom vào các nút trên lớp ra của mạng Kohonen. (Kết quả huấn luyện mạng Kohonen sẽ tạo trên lớp ra Kohonen các cụm dữ liệu ứng với nhóm các nút gần nhau trên lớp ra Kohonen. Các mẫu học sẽ thuộc về cụm có khoảng cách gần nhất từ nó đến nowrron trong cụm. Các cụm có vị trí gần nhau trên mạng Kohonen sẽ chứa các đối tượng có mức độ tương tự cao). Qua thử nghiệm cho thấy hệ thống gom cụm văn bản biểu diễn bằng đồ thị có độ chính xác cao hơn so với gom cụm văn bản được biểu diễn bằng vector [3]. Trên đây là một số những nghiên cứu về phân cụm văn bản trong tiếng Việt. Các nghiên cứu đều cho những kết quả rất khả quan. Ở chương sau, khóa luận sẽ trình bày phương pháp phân cụm văn bản dựa theo việc xếp hạng các cụm từ quan trọng [10]. Tiếp đó là phần thực nghiệm với việc áp dụng kỹ thuật phân cụm này đối với các văn bản tiếng Việt là kết quả trả về của máy tìm kiếm Google 27 Chương 3. Phân cụm văn bản sử dụng phương pháp xếp hạng cụm từ quan trọng 3.1. Khái quát bài toán Với sự phát triển nhanh chóng của công nghệ thông tin thì các tài nguyên trên internet cũng ngày càng phong phú và đa dạng. Việc tìm kiếm thông tin trên internet là rất quan trọng và cần thiết đối với người sử dụng. Và việc tổ chức các kết quả tìm kiếm thành các cụm làm cho người sử dụng dễ dàng hơn trong việc duyệt các kết quả tìm kiếm. Theo [10] thì các kỹ thuật phân cụm truyền thống không phù hợp với phân cụm kết quả tìm kiếm bởi chúng tạo ra các tên cụm “khó đọc”. Vì vậy, phương pháp phân cụm ở đây sẽ đưa bài toán phân cụm về bài toán xếp hạng các cụm từ quan trọng. Đưa ra truy vấn và lấy về một danh sách các tài liệu đã được xếp hạng từ máy tìm kiếm, đầu tiên là tách các tài liệu thành các cụm từ, sau đó xếp hạng các cụm từ này. Các cụm từ cũng chính là tên các cụm ban đầu (candidate cluster). Việc xếp hạng các cụm từ dựa vào một mẫu hồi qui được học từ tập dữ liệu huấn luyện. Các tài liệu sẽ được gắn với các cụm từ quan trọng tạo thành các cụm với tên cụm chính là tên của cụm từ. 3.1.1. Nhu cầu về phân cụm các kết quả tìm kiếm Tài nguyên trên internet rất phong phú và đa dạng, có thể nói, người sử dụng có thể tìm kiếm thông tin về mọi lĩnh vực trên internet. Các máy tìm kiếm là công cụ tìm kiếm hỗ trợ rất tốt cho người sử dụng. Tuy nhiên, với các máy tìm kiếm khá phổ biến như Google [14], Yahoo [16], MSN [17] thì khi nhận một truy vấn từ người dùng, các máy tìm kiếm này thường trả về một danh sách dài các kết quả tìm kiếm. Các kết quả được xếp hạng theo sự phù hợp với truy vấn của người dùng dựa vào một số yếu tố như các từ khóa trong tài liệu, mức tương tự với truy vấn, dựa theo link liên kêt,… Tuy nhiên, danh sách kết quả trả về thường rất lớn. Thêm vào đó, đối với các truy vấn “nhập nhằng”, có nhiều chủ đề liên quan thì người dùng rất khó khăn và tốn nhiều thời gian xem xét các tiêu đề và đoạn tóm lược của tài liệu để tìm ra kết quả mong muốn. Ví dụ với truy vấn “việt nam” trên máy tìm kiếm google. Số kết quả trả về là rất lớn, vào khoảng 78 000 000. 28 Hình 6: Ví dụ với truy vấn “Việt Nam” trên máy tìm kiếm google[14] Từ vấn đề được nêu ra ở trên, một giải pháp đưa ra là phân cụm các kết quả trả về của máy tìm kiếm thành các nhóm khác nhau. Người sử dụng dựa vào mô tả của các nhóm để chọn ra chủ đề mà họ cần tìm. Với mỗi chủ đề, các tài liệu có độ quan trọng cao sẽ được đặt ở trên. Vivisimo là tiêu biểu của phân cụm các kết quả tìm kiếm dựa theo cụm từ quan trọng. Lấy ví dụ với truy vấn là “Việt Nam” trên máy tìm kiếm Vivisimo thu được 264 kết quả tìm kiếm, chia thành các cụm với mô tả các cụm rất trực quan. Hình 7: Ví dụ với truy vấn “Việt Nam” trên máy tìm kiếm Vivisimo[15] 29 3.1.2. Mô tả bài toán và thuật toán a. Mô tả bài toán Phương pháp phân cụm ở đây là chuyển từ bài toán phân cụm không giám sát sang bài toán xếp hạng có giám sát [10]. Chính xác hơn là đưa ra danh sách được xếp hạng gốc của kết quả tìm kiếm R={r(di|q)}. Trong đó: + q là truy vấn hiện tại + di là một tài liệu + r là một hàm tính độ liên quan giữa di và q Kỹ thuật phân cụm truyền thống cố gắng tìm ra một tập các cụm topic-coherent C (các tài liệu trong cụm cùng hướng về một chủ đề) theo truy vấn q. Mỗi cụm được kết hợp với một danh sách tài liệu mới, theo xác suất di có liên quan tới cả q và cụm hiện tại: C={Rj}, với Rj={r(di|q,Rj)} (1) Trái lại, phương pháp phân cụm tài liệu dựa vào xếp hạng cụm từ [10] nhằm vào tìm một danh sách đã xếp hạng của các cụm C’, với mỗi cụm kết hợp với một tên cụm và còn thêm một danh sách đã xếp hạng mới của các tài liệu: C’={r’(ck,Rk|q)} với Rk={r(di|q, ck)} (2) Như trong (1) và (2), định nghĩa của các cụm được thay đổi bằng việc thêm các tên cụm ck, và nhấn mạnh hạng của chúng bằng hàm r’, để cải tiến việc có thể đọc được của các cụm. Phương pháp phân cụm ở đây loại ra yêu cầu về topic-coherence của các cụm, độ phức tạp của thuật toán giảm xuống. Tính chất không mạch lạc chủ đề (non-topic-coherence) không được coi là một mặt hạn chế của phương pháp này bởi vì nó không ảnh hưởng đến hiệu quả của việc duyệt của người dùng [10]. b. Mô tả thuật toán Phương pháp phân cụm không yêu cầu xác định trước các mục chủ đề (categories) như phương pháp phân lớp. Do đó, chúng thích hợp hơn với các câu truy vấn về nhiều nội dung khác nhau. Tuy nhiên, phương thức phân cụm thử thách hơn phương thức phân lớp bởi vì chúng được hướng dẫn theo cách không giám sát. Hơn nữa, hầu hết các thuật toán phân cụm truyền thống nhất không thể trực tiếp sử dụng cho phân cụm kết quả tìm kiếm. Ví dụ, thuật toán phải đưa ra các tóm tắt tài liệu thay cho các tài liệu đưa vào, vì việc tải các tài liệu gốc tốn nhiều thời gian; thuật toán phân 30 cụm phải đủ nhanh cho tính toán online; và các cụm được tạo ra phải có mô tả dễ đọc để người dùng có thể duyệt nhanh chóng, vv… Đây cũng là các yêu cầu trong thiết kế thuật toán. Phương pháp phân cụm dựa vào xếp hạng các cụm từ quan trọng [10] đã đưa bài toán phân cụm kết quả tìm kiếm sang bài toán xếp hạng các cụm từ quan trọng. Theo đó, bài toán phân cụm không giám sát sẽ được chuyển sang bài toán học có giám sát. Mặc dù phương thức học có giám sát yêu cầu thêm dữ liệu huấn luyện, nhưng nó làm cho việc thực hiện nhóm kết quả tìm kiếm cải tiến đáng kể, và chúng ta có thể đánh giá thuật toán một cách chính xác hơn. Đưa ra một truy vấn và lấy về danh sách được xếp hạng các kết quả trả về của một máy tìm kiếm, trước tiên là phân tích cú pháp toàn bộ danh sách tài liệu gồm tiêu đề và nội dung tóm tắt (snippet), trích ra tất cả các cụm từ có thể (n-grams) từ nội dung, và tính một vài đặc trưng cho mỗi cụm từ như là tần suất cụm từ, tần suất tài liệu, độ dài cụm từ, vv… Một mô hình hồi quy đã học từ dữ liệu huấn luyện được áp dụng để kết hợp các thuộc tính này trong điểm quan trọng riêng. Các cụm từ được xếp hạng tăng dần theo điểm quan trọng, và các cụm từ có hạng top được lấy như là các cụm từ quan trọng. Các cụm từ quan trọng là tên các cụm ban đầu, các cụm được hợp lại theo các tài liệu phù hợp của chúng. Phương pháp phân cụm ở đây phù hợp hơn với phân cụm kết quả tìm kiếm web vì nó nhấn mạnh hiệu quả của việc nhận ra những cụm thích hợp cho người dùng web. Nó tạo ra tên cụm ngắn (và vì vậy hi vọng rằng dễ đọc hơn), các tên cụm ngắn cho phép người dùng xác định nhanh hơn các chủ đề của một cụm. Hơn nữa, các cụm được xếp hạng theo điểm quan trọng của chúng, do đó các cụm thích hợp hơn với yêu cầu của người sử dụng được xếp hạng cao hơn. Thuật toán phân cụm theo cụm từ quan trọng bao gồm 4 bước[10]: (1) Lấy về kết quả tìm kiếm từ máy tìm kiếm (2) Phân tích cú pháp tài liệu và tính toán các đặc trưng của cụm từ (3) Xếp hạng cụm từ quan trọng (4) Xử lý tiếp theo để tạo ra các cụm Bước đầu tiên lấy trang web của các kết quả đã kiếm trả về bởi một máy tìm kiếm web. Các trang web này được phân tích bởi bộ phân tích cú pháp HTML và kết quả trả về được trích ra. Thông thường, chỉ các tiêu đề và các đoạn tóm tắt (snippet) có thể sử dụng trong mỗi mục kết quả. Giả sử là các nội dung này cung cấp đủ tin tức cần 31 thiết vì hầu hết các máy tìm kiếm được thiết kế để người dùng dễ dàng tìm các tài liệu liên quan chỉ bằng tiêu đề và đoạn tóm tắt (snippet), do đó nó có thể biểu thị hầu hết các nội dung liên quan cho câu truy vấn đưa ra. Mỗi cụm từ được trích là tên của cụm ban đầu, phù hợp với một tập các tài liệu có chứa cụm từ. Trong lúc đó, một vài đặc trưng của mỗi cụm từ được tính trong quá trình phân tích cú pháp. Các đặc trưng này được mô tả trong phần sau của khóa luận. Trong bước thứ hai, các tiêu đề và đoạn tóm tắt (snippet) được phân tích cú pháp để loại bỏ các thẻ HTML và hệ thống dấu chấm câu, tách thành các n-grams với n có giá trị từ 1 đến 3. Trong quá trình sinh n-gram vẫn tồn tại các từ dừng, vì vậy chúng có thể ở ngay sát với các từ khóa có ý nghĩa trong các tên cụm. Trong bước xử lý sau, các từ dừng này sẽ được loại bỏ. Cũng với lý do như vậy, các từ truy vấn cũng tồn tại trong bước phân tích cú pháp và sẽ được lọc ra ở bước xử lý sau. Tiến hành tính 5 đặc trưng với mỗi cụm từ bao gồm: Phrase Frequency/Inverted Document Frequency, Phrase Leng, Intra-cluster, Cluster Entropy, Phrase Independence Với các đặc trưng được nêu ở trên, một mô hình hồi qui được sử dụng, mô hình này được học từ dữ liệu huấn luyện trước, để kết hợp các đặc trưng này thành một điểm quan trọng . Các cụm từ quan trọng được xếp hạng bằng điểm ở trên theo sắp xếp giảm dần. Như vậy, các cụm ở trên sẽ có hạng cao hơn. Sau khi các cụm từ quan trọng được xếp hạng, các tài liệu tương ứng được kết hợp tạo thành các cụm ban đầu, các cụm từ quan trọng chính là tên của cụm. Trong bước xử lý sau, các cụm từ chỉ chứa các từ dừng hoặc các từ truy vấn được lọc ra. Tiếp theo tiến hành ghép các cụm từ, để làm giảm các cụm từ giống nhau. Đặc biệt, nếu phần chung của hai cụm vượt quá một ngưỡng nào đó (trong thực nghiệm của [10] ngưỡng được chọn là 75%), chúng được ghép vào thành một cụm. Cùng lúc đó, các tên cụm được điều chỉnh theo cụm mới tạo ra từ việc ghép các cụm. Cuối cùng, top các cụm được đưa ra cho người dùng. Khi một người dùng lựa chọn một cụm, danh sách tài liệu liên quan được đưa ra cho người dùng. Danh sách tài liệu này có thể như trong thứ tự gốc hoặc sẽ xếp hạng lại theo sự kết hợp cụm từ quan trọng. 3.2. Trích các cụm từ quan trọng Việc trích các cụm từ từ các tài liệu và tính toán các đặc trưng là vấn đề quan trọng của phương pháp phân cụm này. Đặc biệt là đối với các tài liệu tiếng việt bởi đặc 32 điểm của tiếng việt như đã nêu trong chương 2. Mỗi cụm từ được thể hiện bởi 5 đặc trưng [10]. Các đặc trưng được tính toán ở đây là TFDF (Phrase Frequency/Inverted Document Frequency), độ dài (Phrase leng LEN), Tương tự nội tại (Intra-cluster similarity - ICS), entropy cụm (Cluster entropy -CE), độc lập cụm từ (Phrase Independence - IND). Những đặc trưng này là cơ sở để xác định độ quan trọng của cụm từ. Trong phần mô tả các đặc trưng dưới đây, w biểu diễn một cụm từ đang xét (một n-gram), D(w) biểu diễn tập các tài liệu có chứa cụm từ w. 3.2.1. Đặc trưng TFIDF Đặc trưng này được tính như ý nghĩa của IFIDF. TFIDF là kết hợp của tần số từ khóa (TF: Term Frequency) và nghịch đảo số văn bản chứa từ khóa (IDF: Inverted Document Frequency). Tần số từ khóa (TF: Term Frequency) là tần suất xuất hiện của từ khóa đó trong tài liệu. Một cách trực quan thì một từ là quan trọng cho một tài liệu nếu từ đó xuất hiện nhiều lần trong tài liệu đó. Nghịch đảo số văn bản (IDF: Inverted Document Frequency): Theo [6] thì IDF là nghịch đảo số văn bản chứa từ khóa. Không phải tất cả các từ khóa có độ quan trọng như nhau và vì vậy giá trị trọng số tương ứng với các từ không quan trọng phải nhỏ. Ví dụ, tần số của các từ chức năng như “và”, “hoặc”, “cũng” thường rất lớn và sẽ gây nhiễu đến nội dung của tài liệu. IDF tìm cách co lại trọng số tương ứng với các từ khóa xuất hiện trong nhiều văn bản. IDF=log(N/|D(w)|) Với N là tổng số tài liệu. Trọng số từ (TFIDF) là tích của tần suất từ khóa TF và nghịch đảo số văn bản chứa từ khóa đó và được xác định bằng công thức: TFIDF = f(w).log(N/|D(w)|) Trong đó f(w) là hàm tính tần số của cụm từ w. TFIDF là một phương pháp chuẩn thường được sử dụng để biểu diễn độ quan trọng của từ khóa trong tài liệu. TFIDF của một cụm từ sẽ giảm nếu như cụm từ đó xuất hiện trong hầu hết các tài liệu. Vì vậy , một từ xuất hiện quá ít hoặc quá nhiều được đánh giá ít quan trọng hơn so với các từ xuất hiện cân bằng. 33 3.2.2. Đặc trưng độ dài Đặc trưng này là số lượng các từ trong một cụm từ. Ví dụ: LEN(“nhà”) = 1 LEN(“việt nam”) = 2 Trong quá trình sinh các n-gram từ tiêu đề và đoạn tóm tắt, giá trị của n nằm trong khoảng từ 1 đến 3. Như vậy đối với từ tiếng Việt thì số lượng từ trong một cụm từ thường có giá trị từ 1 đến 6. Đối với người sử dụng, thường thì những cụm từ dài sẽ mang ý nghĩa rõ ràng hơn, và nó sẽ thuận lợi hơn cho người sử dụng trong quá trình tìm kiếm cụm liên quan đến vấn đề cần tìm. Do đó, các cụm từ có giá trị LEN lớn sẽ có độ quan trọng lớn hơn. LEN = n 3.2.3. Đặc trưng tương tự nội tại cụm Một trong những yêu cầu đối với phân cụm là các tài liệu trong cùng một cụm phải có độ tương tự lớn hơn so với tài liệu ở các cụm khác. Nếu một cụm từ là một mô tả tốt cho một chủ đề riêng thì các tài liệu có chứa cụm từ đó sẽ có độ tương tự với nhau. Đặc trưng này dùng để đo độ chặt (compaccnes) của các tài liệu chứa cụm từ với cụm từ đó. Đầu tiên, các tài liệu được chuyển thành các vector trong không gian vector: di = (xi1, xi2,…) Mỗi thành phần của vector mô tả một unigram riêng và có giá trị là TFIDF của unigram này. Số chiều của vecto là tổng số unigram của toàn bộ dữ liệu. Khi biểu diễn một tài liệu, nếu một unigram không có trong tài liệu đó thì giá trị của nó là 0. Với mỗi cụm ban đầu, trọng tâm của nó được tính theo công thức: Với di là tài liệu có chứa cụm từ w. ICS là độ lệch giữa các tài liệu với trọng tâm của cụm. 34 Với cos(di,o) = di.o/||di||.||o|| 3.2.4. Đặc trưng entropy nội tại cụm Theo Lê Quyết Thắng và cộng sự [4], entropy được định nghĩa như sau “entropy là một đại lượng toán học dùng để đo lượng tin không chắc( hay lượng tin ngẫu nhiên) của một sự kiện hay của phân phối ngẫu nhiên cho trước”. Giả sử x là một biến ngẫu nhiên trong không gian mẫu x=(x1, x2,…, xn) với độ đo xác suất P(xn)=pn. Entropy của x được định nghĩa là: H(x)= - ∑ pilogpi i≤n Với pn=0 thì H(x) có giá trị bằng 0 vì xlog(x)->0 khi x->0. Một số đặc tính của entropy[18]: - entropy tỉ lệ thuận liên tục với các xác suất xuất hiện của các phần tử ngẫu nhiên. Thay đổi nhỏ trong xác suất phải dẫn đến thay đổi nhỏ trong entropy. - Nếu các phần tử ngẫu nhiên đều có xác suất xuất hiện bằng nhau thì việc tăng số lượng phần tử ngẫu nhiên sẽ làm tăng entropy. Trong bài toán phân cụm ở đây, xét với cụm từ w, tập các tài liệu có chứa w là D(w) có thể có phần giao với tập tài liệu D(wi) chứa cụm từ wi với wi khác w. Với trường hợp D(w) phân bố đều trong D(wi), tức là có nhiều tài liệu chứa cả hai cụm từ w và wi thì w có thể là cụm có độ quan trọng cao. Với trường hợp D(w) hiếm khi chồng lên với D(wi) thì w có thể mang một nghĩa riêng. Sử dụng đặc trưng entropy ở đây để mô tả tính riêng của cụm từ. Trong công thức này, nếu không có tài liệu nào chứa cả hai cụm từ w và t tức là D(w) giao với D(t) bằng 0 thì sẽ xuất hiện log0. Vì vậy ở đây coi 0log0=0 3.2.5. Đặc trưng độc lập cụm từ Theo [8], một cụm từ là độc lập khi entropy trong ngữ cảnh của nó là cao. Ký hiệu IND là tính độc lập của một cụm từ. INDl là giá trị độc lập của ngữ cảnh trái của 35 cụm từ w, INDr là giá trị độc lập của ngữ cảnh phải của cụm từ w. Các công thức tính các giá trị INDl, INDr, IND ở dưới được lấy từ [10]. l(w) là tập các từ ở liền kề trái của w trong tập tài liệu, r(w) là tập các từ ở liền kề phải của w trong tập tài liệu. Giá trị độc lập của ngữ cảnh trái của w được xác định như công thức ở dưới. INDr được tính tương tự như INDl. Giá trị IND cuối cùng của w là trung bình của INDl và INDr 3.3. Xếp hạng các cụm từ quan trọng Với 5 thuộc tính ở trên, phương pháp phân cụm ở đây sẽ sử dụng dữ liệu đã huấn luyện để học một mô hình hồi qui. Từ đó tính ra điểm quan trọng của mỗi cụm từ, và dựa vào điểm quan trọng để xếp hạng cụm từ. Hồi qui [10] là một bài toán thống kê kinh điển xác định mối quan hệ giữa hai biến ngẫu nhiên x = (x1,x2,…,xn) và y. Trong phương pháp phân cụm này, biến độc lập x là vector của 5 thuộc tính đã miêu tả ở trên x = (TFIDF,LEN, ISC, CE, IND) và biến độc lập y là một giá trị thực nào đó. Ở đây, y là điểm của các cụm từ, y càng cao thì độ quan trọng của cụm từ càng cao. Một vài kiểu hồi qui có thể được sử dụng như hồi qui tuyến tính (linear regression), hồi qui logistic (logistic regression) và hồi qui hỗ trợ vector (support vector regression). Dưới đây sẽ trình bày sơ lược về các mô hình hồi qui. 3.3.1. Hồi qui tuyến tính Mô hình hồi qui tuyến tính tìm mối quan hệ của x và y với một đường thẳng phù hợp với dữ liệu. Mô hình hồi qui tuyến tính đưa ra là: 36 Với sai số e là một biến ngẫu nhiên độc lập, phân phối theo luật phân phối chuẩn, có giá trị trung bình là 0. Hệ số bj (0<=j<=p) được xác định là tổng của bình phương phần dư nhỏ nhất có thể được. Vì vậy, kết hợp tuyến tính với bj tốt hơn bất cứ hệ số nào khác. Biến xj có thể lấy trực tiếp từ inputs hoặc một vài biến đổi, như log hoặc đa thức, của inputs. 3.3.2. Hồi qui logistic Khi biến độc lập y không phải là biến liên tục mà là biến mang tính đo lường nhị phân: có giá trị là 0 hoặc 1, mô hình hồi qui logistic phù hợp hơn vì những gì cần chính xác không phải là một giá trị số rõ ràng của biến độc lập, nhưng khả năng xảy ra giá trị là 1, còn lại là 0 (q=P(y=1)). Trong [5] trình bày về hồi qui logistic như sau: giả sử một tần số biến cố x ghi nhận từ n đối tượng, xác suất của biến cố đó là: q = x/n q có thể xem là một chỉ số đo lường nguy cơ của một biến cố. Một cách thể hiện nguy cơ khác là odds (khả năng). Khả năng của một biến cố được định nghĩa đơn giản là tỉ số xác suất biến cố xảy ra trên xác suất biến cố không xảy ra: odds = p/p-1 Hàm logit của odds được định nghĩa như sau: q có thể chỉ trong giải từ 0 đến 1, logit(q) chạy từ âm vô cùng đến dương vô cùng. Hồi qui logistic cố gắng tìm hệ số bj (0<=j<=p) phù hợp với x. Thay cho việc sử dụng một bình phương nhỏ nhất độ lệch tiêu chuẩn cho phù hợp nhất, hồi qui logistic sử dụng một phương thức có thể xảy ra lớn nhất với khả năng lớn nhất của việc lấy các kết quả quan sát đưa ra hệ số hồi quy. 3.3.3. Hồi qui hỗ trợ vector (Support vector regression) Trong hồi qui hỗ trợ vecto, x đưa vào được sắp xếp lên trên một không gian đặc trưng nhiều chiều (hight dimensional feature space) sử dụng một vài sắp xếp không tuyến tính, và sau đó một mô hình tuyến tính được xây dựng trong không gian riêng 37 này. Hồi qui hỗ trợ vector sử dụng một kiểu mới của hàm hao phí gọi là hàm hao phí epsilon-insensitive: Hồi qui hỗ trợ vector cố gắng làm nhỏ ||ω||2. Điều này có thể được mô tả bởi việc đưa vào các biến slack (không âm) ξi, ξi* với i=1, 2,..., n, để đo độ lệch của mẫu huấn luyện bên ngoài miền epsilon-sensitive. Do đó mô hình hỗ trợ vecto được chính thức hóa (formalized) như giá trị nhỏ nhất của hàm dưới đây: Bài toán tối ưu hóa này có thể được chuyển vào bài toán đối ngẫu (dual) và vì vậy các hàm nhân non-linear có thể được sử dụng để làm mô hình non-linear. Trên đây là mô tả bài toán cũng như kỹ thuật phân cụm dựa theo các cụm từ quan trọng. Trong phần tiếp theo, khóa luận sẽ trình bày phần thực nghiệm đã được tiến hành dựa theo kỹ thuật phân cụm dựa vào các cụm từ quan trọng thực hiện trên các tài liệu tiếng Việt. Các tài liệu được lấy từ kết quả trả về của máy tìm kiếm Google [14]. Sau đó là kết quả của thực nghiệm và đánh giá hiệu quả phương pháp cũng như kết quả của của thực nghiệm. 38 Chương 4. Thực nghiệm và đánh giá 4.1. Dữ liệu của thực nghiệm Dữ liệu của thực nghiệm được lấy từ danh sách các kết quả trả về của máy tìm kiếm google [14]. Thực hiện gán nhãn dữ liệu cho 10 truy vấn. 10 truy vấn được chọn thuộc ba loại truy vấn: truy vấn nhập nhằng, tên thực thể, các cụm từ chung. Các truy vấn này được lựa chọn bởi chúng có nhiều chủ đề nhỏ, sẽ có lợi cho việc phân cụm các kết quả tìm kiếm. 10 truy vấn được liệt kê trong bảng: Loại truy vấn Truy vấn Truy vấn nhập nhằng Ma trận, thăng long Tên thực thể Việt Nam, Hà Nội, Nguyễn Trãi Cụm từ chung Quốc gia, công nghệ, tài khoản, thị trường, mùa hè Bảng 4: Các truy vấn trong tập huấn luyện Với mỗi truy vấn, thực hiện tìm kiếm trên máy tìm kiếm google[14] và lấy về 50 kết quả đầu tiên bao gồm tiêu đề và đoạn tóm tắt của tài liệu. Sử dụng phần mềm JVnTextPro (của Nguyễn Cẩm Tú và Phan Xuân Hiếu, đại học Công nghệ, đại học quốc gia Hà Nội) để phân tích cú pháp và tách từ tiếng việt. Ví dụ về tách từ: (tiêu đề): việt_nam – wikipedia tiếng_việt (tóm tắt): Để tìm_hiểu các chính_thể trước đây, xin xem việt_nam (định hướng). Để tìm_hiểu về quốc_hiệu việt_nam, xem bài quốc_hiệu việt_nam. Sau đó trích tất cả các n-grams (n<=3), loại bỏ các cụm từ có số tần số nhỏ hơn 3. Với mỗi truy vấn sẽ thu được khoảng từ 100 đến 150 cụm từ. Tập huấn luyện gồm 10 truy vấn với 1386 cụm từ. Đưa các cụm từ này tới 3 người hỏi để lựa chọn các “good phrases” và “medium phrases”. Mỗi người được hỏi sẽ lựa chọn ra 10 “good phrases” (ấn định 100 điểm cho các cụm từ này), 10 “medium phrases” (ấn định 50 điểm cho các cụm từ này). Các cụm từ khác sẽ có điểm là 0. Cuối cùng cộng 3 điểm này lại với nhau. Các cụm từ với điểm từ 100 trở lên thì y sẽ được gán giá trị là 1, các cụm từ khác giá trị của y là 0. 39 STT Truy vấn Số cụm từ Số giá trị y=1 1 Việt Nam 85 19 2 Máy tính 163 23 3 Quốc gia 123 22 4 Thị trường 122 21 5 Ma trận 196 22 6 Tài khoản 165 29 7 Mùa hè 164 21 8 Nguyễn Trãi 139 21 9 Hà Nội 106 26 10 Công nghệ 123 35 Bảng 5: Số cụm từ và số giá trị y=1 trong tập dữ liệu huấn luyện Ở đây giá trị của y được gán là 0 hoặc 1 nhưng ở đầu ra của mô hình hồi qui hỗ trợ vector (cụ thể là SVM rank [19]) thì điểm quan trọng của các cụm từ có giá trị từ âm vô cùng đến dương vô cùng. Với mỗi cụm từ, thực hiện tính toán 4 đặc trưng TFIDF, LEN, ICS, CE. 4.2. Cài đặt thực nghiệm 4.2.1. Phần cứng Mô trường thực nghiệm: - Hệ điều hành Windows XP - Vi xử lý Pentium 4 - RAM 256 40 4.2.2. Phần mềm - Khóa luận sử dụng phần mềm tách từ tiếng Việt JvnTextPro của tác giả Nguyễn Cẩm Tú và Phan Xuân Hiếu (trường đại học Công nghệ, đại học quốc gia Hà Nội). - Khóa luận xây dựng chương trình sinh n-gram và tính các đặc trưng của các cụm từ. Chương trình được viết bằng ngôn ngữ python phiên bản 2.6.1. - Bộ mã nguồn mở SVM rank - Support Vector Machine for Ranking của tác giả Thorsten Joachims [19] được sử dụng để xếp hạng các cụm từ quan trọng. Thông số được thiết lập cho mô hình hồi qui hỗ trợ vector này là thông số -c (được gán giá trị là 3) là giá trị chuyển đổi giữa lỗi của tập huấn luyện và độ lệch chuẩn. Tham số epsilon được đặt mặc định. 4.3. Phương pháp đánh giá Thuật toán phân cụm truyền thống rất khó đánh giá, tuy nhiên với phương pháp phân cụm trong khóa luận, việc đánh giá tương đối dễ vì bài toán phân cụm được đưa về bài toán xếp hạng. Vì vậy, có thể sử dụng phương pháp đánh giá kinh điển trong tìm kiếm thông tin. Sử dụng đúng (P) @ trong N kết quả đầu để đánh giá kết quả thực nghiệm. P@N = |C ∩ R|/|R| Với R là tập hợp của top N từ khóa quan trọng đã trả về bởi thực nghiệm trong khóa luận và C là tập hợp các từ khóa quan trọng đúng. Trong khóa luận sẽ sử dụng P@5, P@10 và P@15 để đánh giá 4.4. Kết quả thực nghiệm và đánh giá Kết quả huấn luyện với SVM-rank như sau: Epsilon: 2.807000 Thời gian huấn luyện: 109.92 giây Số bước lặp: 16 Đầu tiên sử dụng mỗi đặc trưng đã nêu ở chương 3 của khóa luận (4 đặc trưng là TFIDF, LEN, ICS, CE) để xếp hạng các cụm từ, và đánh giá độ chính xác của 10 truy vấn. Độ chính xác trung bình của 5, 10,15 kết quả đầu được thể hiện ở bảng và 41 biểu đồ. Vì rất nhiều từ có cùng giá trị LEN nên TFIDF được sử dụng như là tiêu chuẩn thứ hai để xếp hạng trong việc đánh giá của LEN. P@5 P@10 P@15 TFIDF 0.3 0.35 0.24 LEN 0.26 0.22 0.26 ICS 0.12 0.11 0.06 CE 0.24 0.13 0.18 Bảng 6: Độ chính xác khi sử dụng từng đặc trưng để xếp hạng Hình 8: Biểu đồ độ chính xác khi sử dụng từng đặc trưng để xếp hạng Như biểu đồ trên ta thấy mỗi đặc trưng thể hiện không tốt trong việc xếp hạng các cụm từ khi thực hiện riêng. Xét trong 4 đặc trưng thì TFIDF và LEN tỏ ra tốt hơn trong việc xác định độ quan trọng của cụm từ. Trong khi đó, đặc trưng ICS tỏ ra không tốt để xác định độ quan trọng của cụm từ. Điều này có thể là do mỗi tài liệu chỉ gồm có tiêu đề và đoạn tóm tắt rất ngắn nên không gian vecto dựa vào độ tương tự có lỗi khá lớn. 42 Lấy 5 truy vấn trong tập huấn luyện để đánh giá độ chính xác, kết quả được mô tả trong bảng và biểu đồ. Việt Nam Thị trường Quốc gia Công nghệ Nguyễn trãi P@5 0.8 0.4 0.8 1 0.8 P@10 0.8 0.5 0.7 0.8 0.7 P@15 0.73 0.53 0.73 0.67 0.67 Bảng 7: Độ chính xác của từng truy vấn Hình 9: Biểu đồ độ chính xác của từng truy vấn Có thể nhận thấy độ chính xác ở đây là khá cao song không đều do có sự khác nhau về độ chính xác khá rõ giữa các truy vấn. Với truy vấn “thị trường” độ chính xác thấp, bởi vì top các cụm từ quan trọng có chứa từ truy vấn như “thị trường vàng”, “thị trường bất động sản”,”thông tin thị trường”. Các truy vấn “công nghệ” và “việt nam” có độ chính xác cao hơn, top các cụm từ quan trọng miêu tả các chủ đề nhỏ rõ ràng. Ví dụ với truy vấn là “việt nam” thì top các cụm từ quan trọng theo thứ tự là: phật giáo, khoa học, kinh tế, trực tuyến, lịch sử, tiếng Việt, diễn đàn, thế giới, quốc tế, lĩnh vực. Từ phần thực nghiệm trên có thể thấy phương pháp phân cụm tài liệu dựa vào các cụm từ quan trọng áp dụng trên các văn bản tiếng Việt có kết quả khá khả quan. Các cụm từ quan trọng mô tả khá tốt cho một cụm. Trong mỗi cụm, các tài liệu nhìn 43 chung có liên quan đến cùng chủ đề. Tuy nhiên việc tách các từ tiếng Việt vẫn còn hạn chế nên trong các cụm từ sinh ra vẫn còn nhiều cụm từ có cùng nội dung, ví dụ như “việt nam” ,“viet nam” (đúng dạng phải là “việt_nam’, “viet_nam”). Do đó thực nghiệm vẫn chưa thực hiện được bước xử lý sau, đó là loại bỏ các cụm chỉ có từ dừng, loại bỏ các từ truy vấn, và gộp các cụm có phần giao nhau vượt qua một ngưỡng định trước (ví dụ là 75%). 44 Kết luận Từ việc nghiên cứu bài toán và kỹ thuật phân cụm văn bản dựa vào các cụm từ quan trọng trên các tài liệu tiếng việt, có thể thấy phương pháp phân cụm cho kết quả khá tốt khi các cụm từ mô tả khá tốt cho một cụm có độ quan trọng khá cao. Về mặt nội dung, khóa luận đã đạt được những kết quả sau: - Tổng hợp có hệ thống các nội dung cơ bản nhất về phân cụm văn bản (khái niệm, đặc trưng, các kỹ thuật phân cụm phổ biến và đánh giá các kỹ thuật phân cụm). - Đề cập được ảnh hưởng đặc điểm của từ tiếng Việt, kỹ thuật tách từ tiếng Việt vào phân cụm văn bản tiếng Việt. - Phân tích kỹ lưỡng kỹ thuật phân cụm dựa vào cụm từ quan trọng và những đặc trưng của cụm từ tiếng Việt cần đánh giá, lựa chọn để sử dụng trong thuật toán phân cụm. - Xây dựng chương trình trên ngôn ngữ python phiên bản 2.6.1 sinh n-gram và tính các đặc trưng được lựa chọn của các cụm từ để xác định độ quan trọng tích hợp với phần mềm tách từ tiếng Việt JVnTextPro và khai thác mã nguồn mở SVM-rank để tiến hành thực nghiệm xác định độ quan trọng của các cụm từ và cho kết quả về ảnh hưởng của các đặc trưng cụm từ vào phân cụm, trong đó các đặc trưng TFIDF và LEN có ánh hưởng lớn hơn. Bên cạnh đó, do thời gian và kiến thức có hạn nên khóa luận vẫn còn một vài hạn chế sau: - Theo trực quan thì các từ tiếng Việt vẫn chưa được tách một cách chính xác hoàn toàn. - Kỹ thuật phân cụm dựa vào cụm từ quan trọng được đưa ra cần tính 5 đặc trưng là TFIDF, LEN, ICS, CE, và IND. Tuy nhiên, chương trình được xây dựng để tính các đặc trưng mới chỉ dừng lại ở việc tính 4 đặc trưng là TFIDF, LEN, ICS, CE. - Tập huấn luyện với các truy vấn khá tốt, song lượng truy vấn chưa nhiều (10 truy vấn) và mới mỗi truy vấn chỉ lấy 50 kết quả trả về từ máy tìm kiếm. điều này cũng ảnh hưởng độ chính xác của kết quả thực nghiệm. 45 - Thực nghiệm mới chỉ dừng lại ở bước tính ra điểm quan trọng của cụm từ, chưa xây dựng được chương trình xử lý sau khi có độ quan trọng của cụm từ. Vì vậy việc tạo ra các cụm cũng như đánh giá kết quả thực nghiệm vẫn phải thực hiện bằng tay. Trong tương lai, khóa luận có thể tiếp tục được hoàn thiện theo các hướng sau: - Thử nghiệm trên nhiều bộ dữ liệu khác nhau và với các mô hình hồi qui khác. - Xây dựng chương trình xử lý sau khi có được độ quan trọng của các cụm từ, từ đó đưa ra các cụm với các tài liệu có chứa cụm từ. 46 Tài liệu tham khảo Tiếng Việt [1] Nguyễn Thị Thu Chung, Nguyễn Thu Trang, Hà Quang Thụy, “Đánh giá chất lượng phân cụm trong máy tìm kiếm tiếng Việt”, Hội thảo Quốc gia lần thứ XI, Huế, Việt Nam [2] Nguyễn Lê Minh, Hoàng Cao Trụ, “Phân cụm từ tiếng Việt bằng phương pháp học máy cấu trúc”, thực hiện trong khuôn khổ đề tài Nhà nước “Nghiên cứu phát triển một số sản phẩm thiết yếu về xử lý tiếng nói và văn bản tiếng Việt” mã số KC01.01/06-10 [3] Đỗ Phúc, Mai Xuân Hùng, Nguyễn Thị Kim Phụng, “gom cụm đồ thị và ứng dụng vào việc trích rút nội dung chính của khối thông điệp trên diễn đàn thảo luận”, Tạp chí phát triển KH & CN, tập 11, số 05-2008. [4] Lê Quyết Thắng, Phan Tấn Tài, Dương Văn Hiếu, “Giáo trình lý thuyết thông tin”, Khoa CNTT & truyền thông, đại học Cần Thơ, 2007, tin31/GT_LTTT.pdf [5] Nguyễn Văn Tuấn, “Phân tích số liệu và tạo biểu đồ bằng R”, nhà xuất bản Khoa học kỹ thuật, tr 94-101 [6] Hà Quang Thụy, “Khai phá dữ liệu Web”, Bài giảng, Trường Đại học Công nghệ, ĐHQGHN, 2008. [7] Trung tâm ngôn ngữ học Việt Nam. “Đặc điểm tiếng Việt”, Tiếng Anh [8] Chien L. F. "PAT-Tree-Based Adaptive Keyphrase Extraction for Intelligent Chinese Information Retrieval". Proceedings of the 20th Annual International ACM/SIGIR Conference on Research and Development in Information Retrieval (SIGIR'97), pages 50-58, Phliadelphia, 1997. 47 [9] Christopher D. Manning, Prabhakar Raghavan, Hinrich Schutze, “An introduction to Information Retrival”, Cambridge University, 2007, page 349- 400 [10] Hua-jun zeng, Qi-cai He, Zheng Chen, Wei-Ying Ma, Jinwen Ma. "Learning to Cluster Web Search Results". Proceedings of SIGIR-04, 27th ACM International Conference on Re-search and Development in Information Retrieval, 2004, Sheffield, South Yorkshire, UK [11] Paolo Ferragina, Dino Pedreschi, Francesco Romani, “On two web IR Boosting tools: Clustering and Ranking”, PhD. Thesis, University of Pisa May 6, 2006, page 34-38. [12] Thanh V. Nguyen, Hoang K. Tran, Thanh T.T. Nguyen and Hung Nguyen, “Word Segmentation for Vietnamese Text Categorization: An online corpus approach”, IEEE RIVF2006 - Research, Innovation and Vision of the Future - The 4rd IEEE International Conference in Computer Science, Ho Chi Minh City, Vietnam, 2/2006 [13] Zamir O., Etzioni O. Web Document Clustering: "Web Document Clustering: A Feasibility Demonstration", Proceedings of SIGIR 1998: 46-54 [14] Máy tìm kiếm google, [15] Máy tìm kiếm vivisimo, [16] Máy tìm kiếm yahoo, [17] Máy tìm kiếm MSN, [18] Entropy, [19] Support Vector Machine for Ranking,