ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Chung XÂY DỰNG DANH BẠ WEB TIẾNG VIỆT VỚI PHÂN CỤM PHÂN CẤP VĂN BẢN KHOÁ LUẬN TỐT NGHIỆP HỆ ĐẠI HỌC 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Ệ Nguyễn Thị Thu Chung XÂY DỰNG DANH BẠ WEB TIẾNG VIỆT VỚI PHÂN CỤM PHÂN CẤP VĂN BẢN KHOÁ LUẬN TỐT NGHIỆP HỆ ĐẠI HỌC CHÍNH QUY Ngành: Công nghệ thông tin Giáo viên hướng dẫn: PGS.TS Hà Quang Thụy Giáo viên đồng hướng dẫn: ThS Nguyễn Thu Trang Hà Nội - 2009 LỜI CẢM ƠN Trước tiên, em xin gửi lời cảm ơn chân thành biết ơn sâu sắc tới thày giáo Phó giáo sư, Tiến sĩ Hà Quang Thụy Thạc sĩ Nguyễn Thu Trang tận tình hướng dẫn em suốt trình thực khoá luận Em xin bày tỏ lời cảm ơn sâu sắc đến thầy cô giáo giảng dạy em suốt bốn năm học qua, cho em kiến thức quý báu để em vững bước đường Em xin gửi lời cảm ơn tới bạn lớp K50CA ủng hộ, khuyến khích em suốt trình học tập trường Và lời cuối cùng, em xin bày tỏ lòng chân thành biết ơn vô hạn tới cha mẹ, chị, người bên cạnh em lúc khó khăn nhất, giúp em vượt qua khó khăn học tập sống Hà Nội, ngày 24 tháng 05 năm 2009 Sinh viên Nguyễn Thị Thu Chung TÓM TẮT Danh bạ web hệ thống trang web tổ chức dạng phân cấp với mục đích định hướng người dùng tìm kiếm truy cập thông tin dễ dàng hiệu Xây dựng danh bạ tiếng Việt với quy mô lớn chất lượng cao việc làm có ý nghĩa Tạo dựng danh bạ theo hướng sử dụng kiến thức chuyên gia hay lấy ý kiến người dùng tốn nhiều thời gian, cần tìm phương pháp tự động nhóm trang web vào chủ đề theo nội dung chúng Giải pháp sử dụng phân cụm web để xây dựng phân cấp chủ đề phương án hiệu để tạo danh bạ web [22][25][26] Khóa luận nghiên cứu phương pháp tạo danh bạ web, sâu vào giải pháp xây dựng phấp dựa phân cụm văn Khóa luận tập trung tìm hiểu hai phương pháp phân cụm điển hình phân cụm phân cấp K-means Hai phương pháp đánh giá chất lượng phân cụm trình bày kỹ làm tiêu chí đánh giá cho thực nghiệm tiến hành phân cụm tạo danh bạ Dựa liệu Vnexpress Wikipedia, khóa luận sử dụng phân cụm phân cấp K-means tạo danh bạ web tiếng Việt đạt kết bước đầu khả quan với chất lượng tốt, độ xác cao đạt đến 99% MỤC LỤC BẢNG CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT i DANH MỤC HÌNH VẼ ii DANH MỤC BẢNG BIỂU iii Chương GIỚI THIỆU Chương DANH BẠ WEB Giới thiệu danh bạ web 1.1 Phân loại 1.2 Đặc điểm 1.3 Mục đích Một số danh bạ web điển hình thực trạng Việt Nam 2.1 Một số danh bạ web điển hình 2.2 Thực trạng xây dựng danh bạ web Việt Nam Phương pháp tạo danh bạ 3.1 Tích hợp danh bạ sẵn có 3.2 Xây dựng danh bạ 15 Chương PHÂN CỤM WEB Phân cụm 17 17 1.1 Bài toán phân cụm nói chung 17 1.2 Đặc điểm phân cụm .22 1.3 Phân cụm kết trả từ máy tìm kiếm .24 Một số thuật toán phân cụm web 25 2.1 Phân cụm phân cấp 25 2.2 Phân cụm K-means 32 Phương pháp đánh giá chất lượng phân cụm 36 3.1 Đánh giá dựa vào kinh nghiệm người dùng 36 3.2 Đánh giá dựa vào chủ đề mẫu 36 Chương THỰC NGHIỆM Dữ liệu 39 39 Môi trường 40 Tiến hành thực nghiệm 41 3.1 Chuẩn hóa liệu 41 3.2 Phân cụm 42 Kết đánh giá 42 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 47 TÀI LIỆU THAM KHẢO 48 PHỤ LỤC 51 BẢNG CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Từ viết tắt Từ nguyên gốc Ý nghĩa HC Hierarchical Clustering Phân cụm phân cấp HAC Hierarchical Agglomerative Clustering Phân cụm phân cấp từ lên STC Suffix Tree Clustering Phân cụm hậu tố ODP Open Directory Project Danh bạ web Dmoz VNSEN Việt Nam Search Engine Máy tìm kiếm tiếng Việt CRFs: Conditional Random Fields Mô hình trường ngẫu nhiên i DANH MỤC HÌNH VẼ Hình 1: Danh bạ web DMOZ Hình 2: Danh bạ web Yahoo!Directory .7 Hình 3: Danh bạ dọc FindLaw Hình 4: Mô hình ghép S vào đích M 10 Hình 5: Quy trình phân cụm 17 Hình 6: Ma trận thuộc tính biểu diễn liệu 18 Hình 7: Ma trận khoảng cách biểu diễn liệu 18 Hình 8: Biểu đồ phân cụm HAC tài liệu 26 Hình 9: Phân cụm với single-linkage 27 Hình 10: Phân cụm với complete-linkage 27 Hình 11: Ba bước nhóm cụm Centroid clustering 30 Hình 12: Centroid clustering không đồng biến 31 Hình 13: Biểu diễn tài liệu không gian Eucliden 34 Hình 14: Chọn ngẫu nhiên tài liệu làm tâm cụm 34 Hình 15: Tính lại tâm cụm .35 Hình 16: Mô hình thực nghiệm 41 Hình 17: Biểu đồ so sánh độ đo F1 mức liệu .43 Hình 18: Biểu đồ so sánh độ đo F1 chủ đề (Vnexpress) 44 Hình 19: Biểu đồ so sánh độ đo F1 chủ đề giáo dục (Wikipedia) 45 Hình 20: Cây chủ đề Vnexpress hai mức 45 Hình 21: Cây chủ đề Wikipedia hai mức 46 ii DANH MỤC BẢNG BIỂU Bảng 1: Bốn luật định tích hợp danh bạ 14 Bảng 2: Bảng tham số thuộc tính nhị phân 20 Bảng 3: Các chủ đề thuộc Vnexpress 39 Bảng 4: Các chủ đề thuộc Wikipedia 40 Bảng 5: Các chủ đề thuộc nhánh giáo dục .40 Bảng 6: Đánh giá kết phân cụm mức .43 Bảng 7: Đánh giá kết phân cụm chủ đề thuộc Vnexpress 43 Bảng 8: Đánh giá kết phân cụm chủ đề giáo dục (Wikipedia) 43 iii Chương 1: Giới thiệu Chương GIỚI THIỆU Với phát triển nhanh chóng Internet, thông tin không sợ thiếu, việc cần thiết khai phá, tìm hiểu xem thông tin có mục đích thông tin có ích Việc tổ chức trang web thành cấu trúc đầy đủ có hệ thống việc làm có ý nghĩa giúp định hướng người dùng tìm kiếm thông tin dễ dàng từ chủ đề họ quan tâm Thông tin danh bạ thường dễ tìm kiếm với cấu trúc phân cấp rõ ràng, Dos hệ điều hành sớm sử dụng cách tổ chức thông tin danh bạ để lưu trữ truy cập thông tin Ngày nay, danh bạ dường diện nơi, liệt kê tất thông tin lĩnh vực sống, mà gần gũi với ta danh bạ số điện thoại Mọi danh bạ có chung mục đích giúp loại bỏ việc tìm kiếm cách không mục đích thông tin có ích đồng thời cho phép liệu quản lý thuận tiện Danh bạ web điển Yahoo!, LookSmart Open Directory Project (ODP) tập đường link liên kết tới trang web trang web xếp vào chủ đề Chúng điển hình biểu diễn dạng phân cấp, xếp theo cấu trúc lớp, biểu diễn miền kiến thức dạng chủ đề Công nghệ biết đến với tên gọi “bản thể học” hay “ontology” [8] Những thể thường giống với cấu trúc sử dụng hệ thống danh mục thư viện, chủ đề phân tách nhỏ thành danh mục cụ thể Chính công nghệ giúp cho việc tìm kiếm nâng cao máy tìm kiếm Google, Microsoft’s MSN Netscape Search … Trên giới, việc xây dựng danh bạ web quan tâm từ năm 1995 đạt thành công cụ thể Các trang web ngày tích hợp vào thư mục danh bạ lớn, nhỏ giúp cho việc tổ chức trang web ngày hoàn thiện Mặc dù tổ chức đứng xây dựng danh bạ web với mục đích khác nhau, số tổ chức xây dựng danh bạ web theo hướng mở trang danh bạ web tiếng Anh: ODP, AOL, Google, HotBot, Lycos hay số trang danh bạ nhỏ khác Wherewithal, Zeal, Go Guides… số tổ chức lại xây dựng danh bạ web mang tính thương mại không công bố phương pháp tạo LookSmart, MSN, time Warner, About.com, NBCi…; danh bạ mạnh riêng lĩnh vực riêng, toán đặt làm để tích hợp danh bạ thành danh bạ thống nhất, hoàn chỉnh Dù vậy, việc khó khăn -1- Chương 3: Phân cụm web nhóm tạo cách chia nhóm C’={c’1,…,c’k}, với mẩu tin , Sự gán nhãn ban đầu trông cấu trúc ẩn mà hệ thống phân cụm phải tìm [11] Độ đo NMI (normalized mutual information) [11] sử dụng: • Với P(c) biểu diễn xác suất mà mẩu tin chọn ngẫu nhiên sj thuộc c • P(c,c’) biểu diễn xác suất mẩu tin chọn ngẫu nhiên sj thuộc c c’ Nhân tử dùng để chuẩn hóa, cần thiết để giải thích cho thực tế số phần tử C C’ khác Giá trị NMI cao có nghĩa chất lượng phân cụm tốt Vivisimo tạo cụm có chồng lên phần (trong thử nghiệm [11] có khoảng 27% số mẩu tin thuộc nhiều cụm) NMI thiết kế cho phân cụm không trùng lặp Và [12], tác giả sử dụng phép đo phổ biến precision, recall purity, entropy để đánh giá chất lượng cụm so với chủ đề cho trước Độ xác (precision): Độ hồi tưởng (recall): • So sánh cụm i với mục chủ đề j • nij số trang web xuất cụm i chủ đề j • ni nj số trang web xuất cụm i chủ đề j Độ đo F (F-measure) phép đo phổ biến tính toán giống phép đo IR: - 37 - Chương 3: Phân cụm web Độ đo F mục j Fj=max{Fij} tương tự ta có độ đo F toàn là: Chất lượng cụm tính toán độ tinh khiết purity entropy Độ đo purity độ tinh khiết, rõ ràng cụm i Purity toàn trình phân cụm tính theo trọng số số hạng thuộc cụm: ¾ Với n tổng số trang web Entropy cụm i Ei= −∑ j pij log pij Tính toán theo trọng số tỷ lệ với tất cụm ta nhận entropy tổng thể việc phân cụm: - 38 - Chương 4: Thực nghiệm Chương THỰC NGHIỆM Khóa luận tiến hành thực nghiệm cài đặt thuật toán phân cụm phân cấp HAC phân cụm K-means tư tưởng xây dựng phân cấp chủ đề để tạo danh danh bạ web tiếng Việt với quy mô chất lượng tốt Dữ liệu Quá trình thực nghiệm tiến hành miền liệu văn với ba liệu Trong có tài liệu tiếng Anh hai tài liệu tiếng Việt phân cụm để so sánh kết Ba liệu phần phân cấp đầy đủ phân nhóm ¾ Bộ liệu Sample: Gồm 58 tài liệu tiếng Anh thuộc hai lớp thể thao: Tennis Maratghon ¾ Bộ liệu Vnexpress: Thu thập từ trang web http://www.vnexpress.net Gồm 789 tài liệu tiếng Việt, danh sách danh mục chủ đề mức mức thể bảng STT Chủ đề mức Tên chủ đề văn hóa kinh doanh xã hội Chủ đề mức Số lượng 305 270 124 Tên chủ đề Số lượng âm nhạc 251 thời trang 54 bất động sản 113 cổ phiếu 139 wto 18 du học 15 du lịch 101 tuyển sinh máy tính 64 máy tính 64 pháp luật pháp luật bóng đá bóng đá giới giới xe máy xe máy Bảng 3: Các chủ đề thuộc Vnexpress ¾ Bộ liệu Wikipedia tiếng Việt: Gồm 3035 tài liệu thuộc lớp Mỗi lớp đề cập đến miền lĩnh vực Các tài liệu thu thập từ trang web - 39 - Chương 4: Thực nghiệm http://vi.wikipedia.org/ Đây tập liệu chuẩn sử dụng nhiều nghiên cứu phân cụm phân lớp văn Đặc điểm tập liệu có số cụm chủ đề giống nhau, ví dụ lớp chủ đề khoa học Danh sách lớp lớp phân cấp Wikipedia bảng sau STT Chủ đề Tên Số lượng 2794 170 28 20 giáo dục internet lịch sử internet sinh hóa học sinh học phân tử tin sinh học training viễn thông y học Bảng 4: Các chủ đề thuộc Wikipedia Trong đó, chủ đề giáo dục gồm chủ đề nhỏ liệt kê bảng STT Giáo dục Tên chủ đề môn học trường trung học viện hàn lâm khoa học Số lượng 1939 13 Bảng 5: Các chủ đề thuộc nhánh giáo dục Môi trường Thực nghiệm tiến hành môi trường máy tính sau: ¾ Cấu hình máy: o Intel(R) Core duo T8300 o 2.40 GHz o 3.00 GB ¾ Ngôn ngữ Java o Công cụ Eclipse o Môi trường Java 6.0 ¾ Công cụ o TCT [31]: mã nguồn mở tích hợp nhiều thuật toán phân cụm tiếng Anh - 40 - Chương 4: Thực nghiệm o o o VTC [18]: chương trình cải tiến TCT, tích hợp thuật toán phân cụm chuẩn hóa cho tiếng Việt JvnTexPro [33]: tách từ tiếng Việt Standard: Chương trình chuẩn hóa liệu cho phân cụm tác giả viết Tiến hành thực nghiệm Mô hình thực nghiệm thực theo hình 16 Hình 16: Mô hình thực nghiệm 3.1 Chuẩn hóa liệu Dữ liệu xử lý qua bước sau: ¾ Xử lý trang web: Loại bỏ thẻ HTML không quan trọng, thẻ hiển thị hình ảnh, metatags,… giữ lại nội dung ¾ Tách từ: Chuyển văn thu thành tập từ khóa riêng biệt Việc tách từ văn tiếng Anh thực dựa nguyên tắc từ ngăn cách với dấu cách Đối với văn tiếng Việt, việc tách từ thực công cụ JvnTexpro [37] ¾ Loại bỏ từ dừng văn thu sau bước Việc loại bỏ từ dừng thực dựa tập từ dừng xây dựng sẵn tiếng Anh tiếng Việt Sử dụng module StopWord.java với đầu vào tên đường dẫn thư mục chứa tài liệu Đầu thư mục chứa tài liệu xóa từ dừng - 41 - Chương 4: Thực nghiệm ¾ Loại bỏ tài liệu giống thư mục Sử dụng lớp standard.java thuộc project standard với đầu vào đường dẫn thư mục chứa tài liệu ¾ Tạo tập dataset Sử dụng lớp TestCollectionStorage thuộc project VTC2 với hai tham số đầu vào: đường dẫn thư mục chứa liệu, đường dẫn thư mục chứa tập dataset Chương trình tạo đầu vào cho chương trình phân cụm gồm file o File đánh mục cho văn (dataset.classes) o File đánh mục cho từ khóa (dataset.terms) o File chứa ma trận tọa độ văn sau véc tơ hóa (dataset.mtx) o File chứa lớp văn số hiệu văn thuộc lớp, sử dụng để đánh giá kết thuật toán phân cụm (dataset.docs) 3.2 Phân cụm a Phân cụm dựa thuật toán K-means Chạy chương trình Kmeans_Clustering.java với số cụm k hai tham số đầu vào đường dẫn đến tập dataset tạo bước tên đường dẫn kết ¾ ¾ ¾ ¾ b Tập liệu Sample: k = Tập liệu Vnexpress: k = 13 Tập liệu Wikipedia: k = Tập liệu giáo dục: k = Phân cụm dựa thuật toán HAC Chạy chương trình HAC_Clustering.java với số cụm k, chọn ngưỡng thresthold = 0.001 Đầu vào đường dẫn đến tập dataset tạo bước tên đường dẫn kết ¾ ¾ ¾ ¾ Tập liệu Sample: k = Tập liệu Vnexpress: k = 13 Tập liệu Wikipedia: k = Tập liệu giáo dục: k = Kết đánh giá Kết phân cụm ba liệu với hai thuật toán HAC K-means đánh giá độ đo F1 thể bảng sau - 42 - Chương 4: Thực nghiệm a Kết phân cụm mức Tên tập liệu Sample Vnexpress Wikipedia Số lượng 58 789 3035 Số cụm mức F1 HAC (%) 98 71 92 K-means (%) 66 50 88 Bảng 6: Đánh giá kết phân cụm mức b Kết phân cụm chủ đề • Tập liệu Vnexpress với chủ đề Tên chủ đề văn hóa xã hội kinh doanh Số lượng 305 124 270 F1 Số cụm 3 HAC(%) K-means(%) 80 77 61 99 76 80 Bảng 7: Đánh giá kết phân cụm chủ đề thuộc Vnexpress • Tập liệu Wikipedia với chủ đề giáo dục gồm 1954 tài liệu Tên chủ đề giáo dục Số lượng 1954 F1 Số cụm HAC(%) 99 K-means(%) 99 Bảng 8: Đánh giá kết phân cụm chủ đề giáo dục (Wikipedia) So sánh kết phân cụm với độ đo F1 hai thuật toán thể rõ biểu đồ Hình 17: Biểu đồ so sánh độ đo F1 mức liệu - 43 - Chương 4: Thực nghiệm So sánh độ đo F1 hai thuật toán HAC K-means thể phân cấp mức ba liệu Sample, Vnexpress Wikipedia ta thấy kết phân cụm theo phương pháp HAC đạt độ xác cao hơn, cao 98% liệu Sample, thấp 71% với liệu Vnexpress cao phương pháp K-means với độ đo F1 cao 88% liệu Wikipedia Hình 18: Biểu đồ so sánh độ đo F1 chủ đề (Vnexpress) Xét ba chủ đề thuộc Vnexpress văn hóa, xã hội kinh doanh, đồ thị thể chất lượng phân cụm phương pháp HAC nói chung cao K-means Riêng với chủ đề xã hội, thuật toán K-means nhỉnh so với HAC 1% Nói chung, kết phân cụm với HAC đạt chất lượng tốt Việc phân cụm đạt đến gần xác chủ đề văn hóa với F1 = 99% Tiếp đến kinh doanh 80% xã hội 76% Tiến hành phân cụm chủ đề giáo dục thuộc Wikipedia, hai thuật toán HAC K-means đưa phân cụm gần với chủ đề giáo dục ban đầu với F1 = 99% - 44 - Chương 4: Thực nghiệm Hình 19: Biểu đồ so sánh độ đo F1 chủ đề giáo dục (Wikipedia) Từ kết phân cụm mức liệu tiếng Anh (sample) liệu tiếng Việt đồng thời đánh giá chất lượng chủ đề hai phân cấp tiếng Việt Wikipedia Vnexpress ta thấy hai thuật toán đưa kết phân cụm gần với phân cấp gốc Tuy vậy, phân cụm với thuật toán HAC nói chung đạt kết cao so với K-means Bên cạnh đó, thuật toán HAC xây dựng phân cấp gần giống với phân cấp chủ đề danh bạ bước phân cụm mà việc sử dụng phân cụm HAC xây dựng danh bạ web phù hợp Sau phân cụm, hai phân cấp tiếng Việt tạo là: Hình 20: Cây chủ đề Vnexpress hai mức - 45 - Chương 4: Thực nghiệm Hình 21: Cây chủ đề Wikipedia hai mức - 46 - Kết luận hướng phát triển KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Khóa luận nghiên cứu phương pháp xây dựng danh bạ web Từ chứng minh tính đắn phương pháp tạo danh bạ web phân cụm văn Khóa luận đạt số kết sau: Về lý thuyết, khóa luận nghiên cứu hai phương pháp tạo danh bạ web, đồng thời tìm hiểu sâu phân cụm văn bản, hai phương pháp phân cụm điển hình phân cụm phân cấp phân cụm K-means Về thực nghiệm, khóa luận tiến hành thử nghiệm phân cụm phân cấp phân cụm K-means liệu tiếng Anh hai liệu tiếng Việt Vnexpress Wikipedia đạt độ xác cao đồng thời tạo phân cấp giống với cấu trúc phân cấp chủ đề danh bạ web Việc sử dụng phương pháp phân cụm với mục đích xây dựng danh bạ web tiếng Việt phù hợp Khóa luận bước đầu xây dựng danh bạ web tiếng Việt với chất lượng tốt Định hướng tiếp theo, tác giả mở rộng quy mô tập liệu đồng thời kết hợp với module gán nhãn cụm để tạo danh bạ web hoàn chỉnh Ta xin thêm ý kiến người dùng nội dung danh bạ giúp phát triển danh bạ chất lượng ngày tốt - 47 - TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt [1] Nguyễn Thị Thu Chung, Nguyễn Thu Trang, Hà Quang Thụy Đánh giá phương pháp phân cụm HAC máy tìm kiếm Tiếng Việt VNSEN Hội thảo khoa học quốc gia Huế, 2008 [2] http://vnlp.net http://203.113.130.205:8181/vnsen [3] http://www.vinatop.com/ [4] http://www.webdanhba.com/ [5] http://www.vdc.com.vn/ Tài liệu tiếng Anh [6] B Raskutti and C Leckie An evaluation of criteria for measuring the quality of clusters In Proceedings of 16th International Joint Conference on Articial Intelligence, IJCAI 99, pages 905-910, Stockholm, Sweden, July 1999 Morgan Kaufmann [7] Christopher D Manning, Prabhakar Raghavan, Hinrich Schütze, An Introduction to Information Retrieval, Cambridge University Press Cambridge, England, November 17, 2007 [8] Chris Sherman, Gary Price, The Invisible Web: Uncovering Information Sources Search Engines Can’t See, Second printing, November 2001 [9] D Zhang and W S Lee Machine learning for IR: Web tax-onomy integration through co-bootstrapping Proceedings of the 27th annual international conference on Research and develop-ment in information retrieval pp 410 - 417 2004 [10] D Zhang and W S Lee, Web taxonomy integration using support vector machines Proceedings of the 13th international conference on World Wide Web, pp 472 - 481, 2004 [11] F Crestani, P Ferragina, and M Sanderson (Eds.) Cluster Generation and Cluster Labelling for Web Snippets, SPIRE 2006, LNCS 4209, pp 25–36, 2006 - 48 - [12] Fatih Gelgi, Hasan Davulcu, Srinivas Vadrevu Term Ranking for Clustering Web Search Results, Proceedings of the 10th International Workshop on Web and Databases (WebDB 2007), June 15, 2007, Beijing, China [13] Giansalvatore Mecca, Salvatore Raunich, Alessandro Pappalardo A New Algorithm for Clustering Search Results, Data & Knowledge Engineering Volume 62, Issue (September 2007), Pages 504-522 [14] 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, Sheffield, South Yorkshire, UK [15] Lawrie D and Croft W B Finding Topic Words for Hierarchical Summarization In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'01), pages 349-357, 2001 [16] M Steinbach, G Karypis, V Kumar A Comparison of Document Clustering Techniques In KDD Workshop on Text Mining, 2000 [17] Michal Wroblewski, A hierarchical www pages clustering algorithm based on the vector space model, MASTER THESIS Submitted in partial fulfillment of the requirements for the degree of Master of Science, Poznań University of Technology, Poland, July 2003 [18] Nguyen Cam Tu Hidden topic discovery to work classification and clustering in Vietnamese web documents Information System falcuty’s Master, Coltech of technology, Hanoi National University Ha Noi, 2008 [19] Oren Zamir and Oren Etzioni, Web Document Clustering: A Feasibility Demonstration, Department of Computer Science and Engineering-University of Washington Seattle, WA 98195-2350 U.S.A, 1998 [20] R Agrawal and R Srikant On Integrating Catalogs pre-sented at Proceedings of the tenth international conference on World Wide Web, 2001 [21] S Newsam, B Sumengen, and B S Manjunath Category-Based Image Retrieval Proc IEEE International Conference on Image Processing (ICIP 2001), Thessalonica, Greece, pp 596-599, Oct 2001 [22] Vera Sheinman, Neil Rubens, Takenobu Tokunaga Commonly Perceived Order within a Category In Proceeding of OntoLex Workshop at 6th International Semantic Web Conference (ISWC 07 ), 2007 - 49 - [23] Wu, T.C.-W., Hsu, W.-L Web directory integration using conditional random fields In WI ’06: Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence (Washington, DC, USA, 2006), IEEE Computer Society, pp 540-543 [24] Yang, C.C., Lin, J Integrating web directories by learning their structures In WWW ’07: Proceedings of the 16th international conference on World Wide Web (New York, NY, USA, 2007), ACM, pp 1239-1240 [25] Yoshimi Suzuki, Fumiyo Fukumoto A Comparison of Manual and Automatic Constructions of Category Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL-2004) at HLT-NAACL 2004 [26] Zamir, Oren and Etzioni, Oren Web document clustering: a feasibility demonstration SIGIR '98: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval 1998 [27] Media 10–20 http://www.10-20media.com/blog/2007/09/18/HorizontalVs VerticalDirectoriesWhatsTheDifference.aspx [28] http://www.18ons.org/ll/AlgDS/Tree/Suffix/ [29] http://dir.yahoo.com/ [30] http://www.dmoz.org/ [31] http://en.pudn.com/downloads115/sourcecode/java/detail482582_en.html [32] http://www.findlaw.com/ [33] http://jexpert.us [34] Carrot2 clustering engine, http://project.carrot2.org/ [35] Search Done Right, Vivisimo (2007) http://searchdoneright.com/2007/03/howto-evaluate-a-clustering-search-engine/Vivisimo clustering engine, (2008) [36] http://vivisimo.com [37] http://www.webmd.com/ - 50 - PHỤ LỤC Các hàm viết chương trình thực nghiệm liệt kê bảng phụ lục STT Tên lớp Mô tả standard.java loại bỏ file giống StopWord.java loại bỏ từ dừng Phụ lục 1: Danh sách lớp chương trình standard STT Tên hàm TestCollectionStorage.java HAC_Clustering.java Kmeans_Clustering.java Mô tả tạo tập dataset mô tả đặc trưng tập liệu phân cụm với HAC, đánh giá kết phân cụm độ đo F1 phân cụm K-means, đánh giá kết phân cụm với độ đo F1 Phụ lục 3: Danh sách hàm thuộc chương trình VTC2 ‐ 51 ‐