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 r∑ ∑ ∈ δ hoặc cực đại hóa ),( ii Dd Ddi r∑ ∑ ∈ ρ 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 r∑∑ ∈ δ hoặc cực đại hóa ),( ii Dd Ddi r∑ ∑ ∈ ρ . 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 r (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 r )( . Độ 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)