Luận văn Phương pháp phân cụm tài liệu web và áp dụng vào máy tìm kiếm

ý nghĩa hoàn chỉnh và có cấu tạo ổn định. Câu “Tôi là một sinh viên” được tách thành 4 từ: Tôi, là, một, sinh viên. Trong đó, từ “sinh viên” được hình thành từ hai tiếng “sinh” và “viên”. Hiện nay có rất nhiều phương pháp được sử dụng để tách từ Tiếng Vịêt. Tuy nhiên, với sự phức tạp của ngữ pháp Tiếng Việt nên chưa có phương pháp nào đạt được chính xác 100%. Và việc lựa chọn phương pháp nào là tốt nhất cũng đang là vấn đề tranh cãi. Các khó khăn khác Tiếng Việt có các từ đồng nghĩa nhưng khác âm. Các công cụ hiện nay không hỗ trợ việc xác định các từ đồng nghĩa. Vì vậy, kết qủa trả về sẽ không đầy đủ. Ngược lại, có những từ đồng âm khác nghĩa. Các hệ thống sẽ trả về các tài liệu có chứa các từ đã được tách trong câu hỏi mà không cần xác định chúng có thực sự liên quan hay không. Vì vậy, kết quả trả về sẽ không chính xác. Một số từ xuất hiện rất nhiều nhưng không có ý nghĩa trong tài liệu. Các từ như: và, với, nhưng, ... có tần số xuất hiện rất lớn trong bất cứ văn bản nào. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 39 - Nếu tìm cách trả về các tài liệu có chứa những từ này sẽ thu được kết quả vô ích, không cần thiết. Do đó, chúng ta cần tìm cách loại bỏ các từ này trước khi tìm kiếm. 2.6.2. Tiếng và Từ trong tiếng Việt Về mặt ngữ âm, tiếng là âm tiết. Âm tiết bao gồm những đơn vị ở bậc thấp hơn gọi là âm vị. Mỗi âm vị được ghi bằng một ký tự gọi là chữ. Về mặt ngữ nghĩa, tiếng là đơn vị nhỏ nhất có nghĩa, nhưng cũng có một số tiếng không có nghĩa. Về giá trị ngữ pháp, tiếng là đơn vị cấu tạo từ. Sử dụng tiếng để tạo thành từ, ta có hai trường hợp sau: - Từ một tiếng: gọi là từ đơn. Trường hợp này một từ chỉ có một tiếng. Ví dụ như: ông, bà, cha, mẹ, ... - Từ hai tiếng trở lên: gọi là từ phức. Trường hợp này một từ có thể có hai hay nhiều tiếng trở lên. Ví dụ như: xã hội, an ninh, hợp tác xã, ... Từ là đơn vị nhỏ nhất để tạo thành câu. Trong đặt câu chúng ta dùng từ chứ không dùng tiếng. 2.6.3. Phương pháp tách từ tự động tiếng Việt fnTBL Ý tưởng chính của phương pháp học dựa trên sự biến đổi (TBL) là để giải quyết một vấn đề nào đó ta sẽ áp dụng các phép biến đổi, tại mỗi bước, phép biến đổi nào cho kết quả tốt nhất sẽ được chọn và được áp dụng lại với vấn đề đã đưa ra. Thuật toán kết thúc khi không còn phép biến đổi nào được chọn. Hệ thống fnTBL (Fast Transformation-based learning) gồm hai tập tin chính [1]: - Tập tin dữ liệu học (Training): Tập tin dữ liệu học được làm thủ công, đòi hỏi độ chính xác. Mỗi mẫu (template) được đặt trên một dòng riêng biệt. Ví dụ: tập dữ liệu học cho việc xác định từ loại của một văn bản có thể được định dạng như sau: Công ty danhtu ISA danhturieng bị dongtu Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 40 - kiểm tra. dongtu Trong ví dụ này mỗi mẫu gồm hai phần: phần đầu tiên là từ, phần thứ hai là từ loại tương ứng. - Tập tin chứa các mẫu luật (rule template): Mỗi luật được đặt trên một dòng, hệ thống fnTBL sẽ dựa vào các mẫu luật để áp dụng vào tập dữ liệu học. Ví dụ: chunk_ -2 chunk_-1 => chunk Áp dụng đối với việc xác định từ loại, với chunk_-2 = động từ, chunk_-1 = số từ, chunk = danh từ thì luật trên có ý nghĩa như sau: nếu hai từ trước đó là động từ và số từ thì chuyển từ loại hiện hành thành danh từ. Áp dụng để tách từ Tiếng Việt: Ta có thể áp dụng phương pháp fnTBL để tách từ Tiếng Việt, chỉ cần thay đổi một số định dạng cho phù hợp. - Xây dựng tập tin dữ liệu học: Tập tin dữ liệu cho việc tách từ Tiếng Việt có dạng như sau: Vì B sao B công B ty I ISA B bị B đặt B vào B tình B trạng I ... Các ký tự B, I gọi là các chunk có ý nghĩa như sau: Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 41 - Tiếng có chunk = B nghĩa là tiếng đó bắt đầu một từ (begin) Tiếng có chunk = I nghĩa là tiếng đó nằm trong một từ (inside). - Xây dựng tập tin chứa các mẫu luật: Sau khi tìm hiểu về từ trong Tiếng Việt, ta xây dựng được 3 luật áp dụng cho tách từ tiếng Việt như sau: chunk_0 word_0 => chunk chunk_0 word_-1 word_0 => chunk chunk_0 word_0 word_1 => chunk a, Quá trình học: (1) Từ tập dữ liệu học xây dựng từ điển các từ (2) Khởi tạo các từ (3) Rút ra tập luật Ở bước (1) từ tập dữ liệu học đã có sẵn, sử dụng phương pháp thống kê → ta sẽ có từ điển các tiếng (Lexicon). Các tiếng có thể xuất hiện trong các từ với các chunk khác nhau, ta sẽ ghi nhận lại số lần xuất hiện của mỗi tiếng với các chunk tương ứng. Ví dụ, đối với từ “công ty” thì tiếng “công” có chunk = B nhưng trong từ “của công” thì tiếng công có chunk=I. Ở bước (2) từ tập dữ liệu học, tạo ra tập dữ liệu học không có chunk bằng cách xoá hết các chunk tương ứng. Tập dữ liệu mới này sẽ được sử dụng để khởi tạo lại các chunk thông dụng nhất dựa vào từ điển. Ở bước (3) so sánh tập dữ liệu học với tập dữ liệu đang xét, dựa vào các mẫu luật đã cho, ta sẽ rút ra được các luật ứng viên, ứng với mỗi luật ứng viên ta lại áp dụng vào tập dữ liệu đang xét và tính điểm cho nó (dựa vào số lỗi phát sinh khi so sánh với tập dữ liệu học là tập dữ liệu chuẩn). Chọn luật có điểm cao nhất và lớn hơn một ngưỡng cho trước để đưa vào danh sách luật được chọn. Kết quả ta sẽ được một tập các luật được chọn. Các luật có dạng như sau: SCORE: 414 RULE: chunk_0=B word_0=tế => chunk=I SCORE: 312 RULE: chunk_0=B word_-1=của word_0=công => chunk=I SCORE: 250 RULE: chunk_0=B word_0=hoá => chunk=I Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 42 - SCORE: 231 RULE: chunk_0=B word_0=động => chunk=I SCORE: 205 RULE: chunk_0=B word_0=nghiệp => chunk=I SCORE: 175 RULE: chunk_0=B word_-1=phát word_0=triển => chunk=I SCORE: 133 RULE: chunk_0=B word_-1=xã word_0=hội => chunk=I SCORE: 109 RULE: chunk_0=B word_-1=đầu word_0=tư => chunk=I SCORE: 100 RULE: chunk_0=B word_0 = thể => chunk=I Ở dòng 2 ta có luật: nếu từ hiện hành là “công” (word_0=công) và từ trước đó là “của” (word_-1=của) và chunk của từ hiện hành là B (chunk_0=B) thì chuyển chunk của từ hiện hành là I, nghĩa là “của công” phải là một từ. Toàn bộ quá trình học được mô tả như sau: Hình 4. Quá trình học Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 43 - b, Xác định từ cho tài liệu mới (1) Tài liệu mới đưa vào phải có địng dạng giống như tập tin dữ liệu học, nghĩa là mỗi tiếng trên một dòng. (2) Dựa vào từ điển, gán chunk thông dụng nhất cho các tiếng trong tài liệu mới. (3) Áp dụng các luật có được từ giai đoạn học vào tài liệu đang xét ta sẽ tách được các từ hoàn chỉnh. Giai đoạn xác định từ cho tài liệu mới được mô tả như sau: Hình 5. Giai đoạn xác định từ cho tài liệu mới 2.6.4. Phương pháp Longest Matching Phương pháp Longest Matching tách từ dựa vào từ điển có sẵn [1]. Theo phương pháp này, để tách từ tiếng Việt ta đi từ trái qua phải và chọn từ có nhiều âm tiết nhất mà có mặt trong từ điển, rồi cứ tiếp tục cho từ kế Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 44 - tiếp cho đến hết câu. Với cách này, ta dễ dàng tách được chính xác các ngữ/câu như: “hợp tác|mua bán”, “thành lập|nước|Việt Nam|dân chủ|cộng hoà”... Tuy nhiên, phương pháp này sẽ tách từ sai trong trường hợp như: “học sinh học sinh học” được tách thành “học sinh|học sinh|học”, “một ông quan tài giỏi” được tách thành “một|ông|quan tài|giỏi” , “trước bàn là một ly nước” được tách thành “trước|bàn là|một|ly|nước”,... 2.6.5. Kết hợp giữa fnTBL và Longest Matching Chúng ta có thể kết hợp giữa hai phương pháp fnTBL và Longest Matching để có được kết quả tách từ tốt nhất. Đầu tiên ta sẽ tách từ bằng Longest Matching, đầu ra của phương pháp này sẽ là đầu vào của phương pháp fnTBL học luật. 2.7. Kết luận chương 2 Trong chương này, các nội dung liên quan tới phân cụm tài liệu Web đã được trình bày một cách khái quát nhất giúp có một cái nhìn tổng quan để bắt tay vào thực hiện giải quyết bài toán. Đồng thời hướng giải quyết khó khăn khi phân cụm tài liệu Web tiếng Việt cũng đã được trình bày. Trên cơ sở đó, luận văn nghiên cứu tập trung vào các thuật toán phân cụm Web có tính tăng điển hình. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 45 - CHƯƠNG 3 - THUẬT TOÁN PHÂN CỤM CÂY HẬU TỐ VÀ THUẬT TOÁN CÂY PHÂN CỤM TÀI LIỆU 3.1. Giới thiệu về thuật toán phân cụm trang Web có tính tăng Chúng ta đang quan tâm giải quyết bài toán phân cụm tài liệu cho các trang Web. Theo truyền thống, nhiệm vụ phân lớp tài liệu được tiến hành thủ công. Để gán một tài liệu với một lớp thích hợp, người thực hiện đầu tiên sẽ phân tích các nội dung của tài liệu. Bởi vậy một số lượng lớn nỗ lực của con người sẽ bị yêu cầu. Đã có một vài công việc nghiên cứu hướng dẫn việc phân cụm tự động văn bản text. Một hướng đi là phân lớp văn bản text bằng cách sử dụng các kỹ thuật học máy. Tuy nhiên, các thuật toán này dựa trên một bộ ví dụ huấn luyện đúng và sai cho học các lớp văn bản. Chất lượng của kết quả các lớp muốn cao thì phải phụ thuộc vào các ví dụ huấn luyện phù hợp. Có rất nhiều thuật ngữ và các lớp trên World Wide Web (hoặc chỉ là Web), và rất nhiều thuật ngữ và khái niệm được tạo ra hằng ngày. Thật là không thể để có các chuyên gia trong lĩnh vực này để định nghĩa các ví dụ huấn luyện để học một người phân loại cho từng lớp theo cách như trên. Để tiến hành xử lý phân lớp tài liệu tự động, các kỹ thuật phân cụm đã được sử dụng. Sự thu hút của phân tích phân cụm là ở việc nó có thể tìm thấy các cụm trực tiếp từ dữ liệu đưa vào mà không cần nhờ vào bất cứ thông tin nào đã được xác định trước, chẳng hạn như các ví dụ huấn luyện cung cấp bởi các chuyên gia trong lĩnh vực. Trong chương này, luận văn xin trình bày một số các thuật toán phân cụm thích hợp cho việc phân cụm trang Web bởi các đặc tính tăng của chúng, cụ thể đó là thuật toán phân cụm cây hậu tố (STC) và thuật toán sử dụng cây phân cụm tài liệu (DC-Tree). Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 46 - 3.2. Thuật toán phân cụm cây hậu tố 3.2.1. Mô tả Cây hậu tố (hay còn gọi là cây PAT hoặc gần đây có thể được gọi là cây vị trí) là một cấu trúc dữ liệu biểu diễn các hậu tố của xâu ký tự nhất định cho phép thực hiện một cách đặc biệt nhanh chóng nhất nhiều phép toán quan trọng trên xâu. Cây hậu tố cho một xâu ký tự S là một cây có cạnh và nhãn là các xâu, thí dụ hậu tố eAHC của S phù hợp chỉ có một con đường từ gốc của cây tới một lá. Do đó chỉ có một cây cơ số cho các hậu tố của S. Việc xây dựng một cây cho xâu ký tự S mất thời gian và không gian tuyến tính với độ dài của S. Mỗi một lần xây dựng, một vài thao tác có thể được thực hiện nhanh chóng, ví dụ như việc xác định vị trí một xâu con trong S, xác định vị trí của một xâu con nếu cho phép một số chắc chắn các lỗi, xác định vị trí các xâu tương ứng cho một mẫu công thức thông thường,... Các cây hậu tố cũng cung cấp một trong các giải pháp có thời gian tuyến tính cho vấn đề tìm xâu con thông thường. Tuy nhiên việc tăng tốc độ sẽ dẫn tới tăng chi phí không gian bộ nhớ do phải lưu trữ thêm cây hậu tố của một xâu hơn so việc lưu trữ xâu đó. Hình 6. Cây hậu tố cho xâu BANANA Cây hậu tố cho xâu BANANA được thêm $ vào cuối. Có sáu con đường từ gốc tới một lá (được chỉ ở trên như các hộp) tương ứng với 6 hậu tố A$, NA$, Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 47 - ANA$, NANA$, ANANA$ và BANANA$. Các chữ số trong các hộp chỉ ra vị trí bắt đầu của hậu tố tương ứng. Hậu tố được liên kết bởi mũi tên kéo theo 3.2.2. Thuật toán STC Thuật toán phân cụm cây hậu tố Suffix Tree Clustering (STC) [5] là một thuật toán phân cụm thời gian tuyến tính dựa trên việc nhận dạng các cụm từ chung của các văn bản. Một cụm từ trong ngữ cảnh này là một chuỗi thứ tự của một hoặc nhiều từ. Chúng ta định nghĩa một cụm cơ bản (base cluster) là một tập các văn bản có chia sẻ một cụm từ chung. STC có 3 bước thực hiện logic: (1) “Làm sạch” văn bản, (2) định nghĩa các cụm cơ bản sử dụng một cây hậu tố, và (3) kết hợp các cụm cơ bản vào các cụm. Bước 1: Tiền xử lý (Pro-Precessing). Trong bước này, các chuỗi của đoạn văn bản biểu diễn mỗi tài liệu được chuyển đổi sử dụng các thuật toán chặt (Chẳng hạn như loại bỏ đi các tiền tố, hậu tố, chuyển từ số nhiều thành số ít). Phân ra thành từng câu (xác định các dấu chấm câu, các thẻ HTML). Bỏ qua các từ tố không phải là từ (chẳng hạn như kiểu số, các thẻ HTML và các dấu câu). Các chuỗi tài liệu nguyên gốc được giữ lại, cùng với các con trỏ tại vị trí bắt đầu của mỗi từ trong chuỗi chuyển đổi đến vị trí của nó trong chuỗi gốc. Việc có các con trỏ nhằm giúp hiển thị được đoạn văn bản gốc từ các nhóm từ khóa đã chuyển đổi. Bước 2: Xác định các cụm cơ sở. Việc xác định các cụm cơ sở có thể được xem xét như việc tạo một chỉ số của các nhóm từ cho tập tài liệu. Điều này được thực hiện hiệu quả thông qua việc sử dụng cấu trúc dữ liệu gọi là cây hậu tố. Cấu trúc dữ liệu này có thể được xây dựng trong thời gian tuyến tính với kích cỡ của tập tài liệu, và có thể được xây dựng tăng thêm cho các tài liệu đang được đọc vào. Một cây hậu tố của một chuỗi S là một cây thu gọn chứa đựng tất cả các hậu tố của S. Thuật toán coi các tài liệu như các chuỗi của các từ, không phải của các ký tự vì vậy các hậu tố chứa đựng một hoặc nhiều từ. Mô tả cụ thể về cây hậu tố như sau: 1. Một cây hậu tố là cây có gốc và được định hướng. 2. Mỗi node trong có tối thiểu 2 con. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 48 - 3. Mỗi cạnh được gắn nhãn là một chuỗi con của S và chuỗi đó khác rỗng. Nhãn của một node được xác định thông qua chuỗi nối tiếp của các nhãn được gắn cho các cạnh từ gốc tới node đó. 4. Không có hai cạnh từ một node được gắn nhãn bắt đầu với từ giống nhau. 5. Với mỗi hậu tố s của S, tồn tại một suffix-node có nhãn là s. Cây hậu tố của một tập các chuỗi là một cây thu gọn chứa đựng tất cả các hậu tố của tất cả các chuỗi trong tập tài liệu. Mỗi suffix-node được đánh dấu để chỉ ra chuỗi mà nó thuộc về. Nhãn của suffix-node chính là một hậu tố của chuỗi đó. Để phân cụm ta sẽ xây dựng cây hậu tố của tất cả các câu của tất cả các tài liệu trong tập tài liệu. Chẳng hạn có thể xây dựng cây hậu tố cho tập các chuỗi là {“cat ate cheese”, “mouse ate cheese too”, “cat ate mouse too”}. - Các node của cây hậu tố được vẽ bằng hình tròn - Mỗi suffix-node có một hoặc nhiều hộp gắn vào nó để chỉ ra chuỗi mà nó thuộc về. - Mỗi hộp có 2 số (số thứ nhất chỉ ra chuỗi mà hậu tố thuộc về, số thứ hai chỉ ra hậu tố nào của chuỗi gắn nhãn cho suffix-node) Hình 7: Cây hậu tố của các chuỗi “cat ate cheese”, “mouse ate cheese too”, “cat ate mouse too”. Một số node đặc biệt a → f. Mỗi một node này biểu diễn cho một nhóm tài liệu và một nhóm từ chung được thiết đặt cho tất cả tài liệu. Nhãn của node biểu diễn nhóm từ chung. Tập các tài liệu gắn nhãn suffix-node là kế thừa của các node tạo bởi nhóm tài liệu. Do đó, mỗi node biểu diễn một cụm cơ sở (base Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 49 - cluster). Ngoài ra, tất cả các cụm cơ sở có thể (chứa 2 hoặc nhiều tài liệu) xuất hiện như các node trong cây hậu tố. Bảng sau liệt kê các node a-> f trong hình 1 và các cụm cơ sở tương ứng. Bảng 1: Sáu node từ hình 14 và các cụm cơ sở tương ứng. Node Phrase Documents a cat ate 1,3 b ate 1,2,3 c cheese 1,2 d mouse 2,3 e too 2,3 f ate cheese 1,2 Mỗi cụm cơ sở được gán một điểm số là một hàm của số lượng các tài liệu cụm đó chứa đựng, và các từ hình thành nên nhóm từ của nó. Điểm số s(B) của cụm cơ sở B với nhóm từ P là: s(B) = |B| . f(|P|) (*) Trong đó: |B| là số lượng của các tài liệu trong cụm cơ sở B, |P| là số lượng các từ có trong nhóm từ P mà có điểm số khác 0. Việc xét đến điểm số của nhóm từ P theo nghĩa như sau: Thuật toán cài đặt một danh sách stoplist bao gồm các từ đặc trưng trên internet dùng để xác định các từ khác. ( Ví dụ “previous”, “java”, “frames”, “mail”). Các từ xuất hiện trong danh sách stoplist đó hay các từ xuất hiện quá ít trong một nhóm từ (3 hoặc ít hơn) hay quá nhiều (hơn 40% của tập tài liệu) sẽ được gán điểm số 0 cho nhóm từ. Hàm f trong công thức (*) thực hiện trên các nhóm từ đơn, nó là tuyến tính cho các nhóm từ có độ dài từ 2 đến 6 và là hằng số với các nhóm có độ dài lớn hơn. Bước 3: Kết nối các cụm cơ sở Các tài liệu có thể chia sẻ nhiều hơn một nhóm từ. Kết quả là, tập hợp tài liệu của các cụm cơ sở khác nhau có thể trùng lặp và thậm chí là có thể là giống nhau. Để tránh việc có nhiều các cụm gần giống nhau. Tại bước thứ 3 này của thuật toán việc trộn các cụm cơ sở với một sự trùng lặp cao trong tập tài liệu của chúng (chú ý là các nhóm từ chung không xem xét trong bước này) Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 50 - Thuật toán đưa ra một độ đo tính tương tự giữa các cụm dựa trên việc trùng lặp của tập tài liệu của chúng. Giả sử có hai cụm cơ sở Bm và Bn với kích cỡ là |Bm| và |Bn| tương ứng. Và | Bm ∩ Bn| thể hiện số tài liệu chung của cả hai cụm, độ tương tự giữa Bm và Bn là 1 nếu: +) | Bm ∩ Bn| / |Bm| > 0.5 và +) | Bm ∩ Bn| / |Bn| > 0.5 Ngược lại, độ tương tự là 0. Hãy xem minh họa tiếp theo của ví dụ trong Hình 7. Ở đây mỗi node là các cụm cơ sở. Hai node được nối với nhau khi độ tương tự là 1. Một cụm được xác định là các thành phần được ghép nối trong đồ thị cụm cơ sở. Mỗi một cụm sẽ bao gồm tập của tất cả các tài liệu của các cụm cơ sở trong nó. Hình 7: Đồ thị các cụm cơ sở của ví dụ trong Hình 6 và bảng 1. Trong ví dụ này có một thành phần kết nối, do đó có 1 cụm. Nếu giả sử rằng từ ‘ate’ có trong danh sách stoplist, thì cụm cơ sở b sẻ bị loại ra bởi vì nó có chỉ số của nhóm từ là 0. Và do đó sẽ có 3 thành phần kết nối trong đồ thị, thể hiện 3 cụm. Chúng ta thấy rằng thời gian của việc tiền xử lý các tài liệu tại bước 1 của thuật toán STC hiển nhiên là tuyến tính với kích thước tập tài liệu. Thời gian của việc thêm các tài liệu vào cây hậu tố cũng tuyến tính với kích thước tập tài liệu theo thuật toán Ukkonen cũng như số lượng các node có thể bị ảnh hưởng bởi việc chèn này. Do vậy thời gian tổng cộng của STC tuyến tính với kích thước tập tài liệu. Hay thời gian thực hiện của thuật toán STC là O(n) trong đó n là kích thước của tập tài liệu. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 51 - 3.3. Thuật toán phân cụm sử dụng cây phân cụm tài liệu 3.3.1. Giới thiệu Trong thuật toán phân cụm sử dụng cây phân cụm tài liệu, một tài liệu thông thường được biểu diễn bởi một vector đặc trưng. Một cách đặc tính, từng đặc trưng tương ứng với một từ khoá hoặc cụm từ xuất hiện trong tập tài liệu. Mỗi entry của vector lưu một trọng số cho đặc trưng tương ứng của tài liệu. Sau khi trích chọn các vector đặc trưng của các tài liệu, chúng ta có thể áp dụng thuật toán phân cụm trên tập các vector như trong phân cụm dữ liệu kích thước lớn thông thường. Các lớp tài liệu kết quả thu được cũng với các đặc trưng tiêu biểu (ví dụ các từ khoá hoặc cụm từ khóa với đủ hỗ trợ tài liệu (document support) cho cụm) do đó trình bày cho người sử dụng. Trong luận văn này, tôi xin giới thiệu một cấu trúc cây gọi là DC-tree (Document Clustering Tree: Cây phân cụm tài liệu) có thể phân cụm các tài liệu mà không cần tập huấn luyện [24]. Với DC-tree, một đối tượng dữ liệu đưa vào không bắt buộc phải chèn vào mức (vị trí) thấp khi không tồn tạo một nút con tương tự cho đối tượng dữ liệu. Điều này ngăn cản một vài dữ liệu không tương tự từ việc đặt cùng nhau. Kết quả là thuật toán phân cụm dựa trên cấu trúc DC- tree là ổn định với yêu cầu đưa thêm tài liệu và dễ chấp nhận các tài liệu “nhiễu”. Phương thức này có thể hữu ích trong một số cách: (1) Cho việc tiền xử lý trong việc phân lớp trang Web để người sử dụng có thể chọn lớp thích hợp trước khi tìm kiếm, việc này giúp ích việc tìm kiếm trở nên có trọng tâm hơn và hiệu quả hơn. (2) Cho việc phân lớp trực tuyến online, để khi số lượng lớn các kết qủa trả lại từ một tìm kiếm, Kỹ thuật này có thể phân lớp các kết quả và cung cấp tốt hơn hướng dẫn cho người sử dụng trong các tìm kiếm trong tương lai. (3) Cho việc phân lớp trang Web có tính tăng sau khi cập nhật trên kho dữ liệu. 3.3.2. Trích chọn đặc trưng và phân cụm tài liệu Nhiệm vụ đầu tiên là nhận biết một phương pháp trích chọn đặc trưng tốt thích hợp cho môi trường Web. Trong phần này, luận văn trình bày một phương Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 52 - pháp trích chọn đặc trưng. Ngoài ra, tài liệu và sự biểu diễn phân cụm tài liệu cũng sẽ được mô tả. Cuối cùng, phương pháp ước lượng chất lượng phân cụm cũng sẽ được trình bày. a, Trích chọn đặc trưng tài liệu Phương pháp trích chọn đặc trưng cho thuật toán phân cụm tài liệu Web được đưa ra không phụ thuộc vào tần xuất xuất hiện từ. Phương pháp này cân bằng các yếu tố khác nhau để đạt được sự kết hợp tốt nhất giữa độ hồi tưởng và số các đặc trưng sử dụng cho biểu diễn tài liệu. Trong vấn đề của chúng ta phạm vi phân cụm mục tiêu để giúp đỡ trong việc lấy thông tin trong việc tìm kiếm bằng cách thu hẹp phạm vi tìm kiếm. Trong một viễn cảnh, người sư dụng có thể không muốn quá nhiều phân cụm trong kết quả. Đồng thời, các cụm quá lớn hoặc quá nhỏ là không được mong muốn. Các cụm quá lớn không thể giúp thu hẹp phạm vi tìm kiếm. Các cụm qúa nhỏ có thể làm tăng tổng số các cụm,và nó có thể thậm chí gây nên trạng thái “nhiễu”. Tham số k được sử dụng để thiết lập một số xấp xỉ trên cỡ của cụm. Do đó số các phân cụm là xấp xỉ N/k, trong đó N là tổng số các tài liệu. Phương pháp được đề xuất bao gồm các bước sau: 1. Lấy ngẫu nhiên một tập con của các tài liệu với cỡ m từ tập sao lục. 2. Trích tập các từ có xuất hiện ít nhất một lần trong các tài liệu. Xoá các từ kết thúc và kết nối các từ vào cùng một gốc bằng cách sử dụng kỹ thuật lấp đầy. 3. Đếm tần xuất tài liệu của các từ đã được trích trong bước 2. 4. Đặt lower=k và upper=k 5. Lấy tất cả các từ với tần xuất tài liệu trong giá trị từ lower và upper. 6. Kiểm tra nếu coverage ( độ hồi tưởng) của các từ là lớn hơn ngưỡng định nghĩa trước. Nếu vậy, dừng. Nếu không, đặt lower=lower-1 và upper=upper+1, và quay lại bước 5. Để trích chọn các đặc trưng tiêu biểu từ các tài liệu, chúng ta lựa chọn ngẫu nhiên một tập các tài liệu mẫu cho bước trích chọn đặc trưng trong bước 1. Một vài thử nghiệm [24] chỉ ra rằng phương pháp trích chọn đặc trưng này có thể trích ra một tập các đặc trưng tốt cho phân cụm tài liệu Web. Một danh sách các Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 53 - từ kết thúc thường được sử dụng để xoá các từ ít có ý nghĩa. Kỹ thuật lấp đầy thường được sử dụng để kết nối các từ này trong dạng tương tự. Bởi vì các vector đặc trưng ngắn nhất dẫn tới thời gian phân cụm ngắn hơn, bước 4 và 6 cố gắng để làm nhỏ nhất số các đặc trưng và thu được độ hồi tưởng hợp lý cho các đặc trưng. Thừa nhận người sử dụng muốn cụm kết quả bao gồm khoảng k tài liệu.Trong trường hợp lý tưởng, một đặc trưng cho một cụm sẽ xuất hiện chỉ trong cụm và do đó tần xuất tài liệu của của đặc trưng là k. Bởi vậy, đầu tiên chúng ta chọn các đặc trưng với tần xuất tài liệu là bằng k, bằng cách thiết lập lower và upper bằng k trong bước 4. Khoảng giá trị {lower, upper} là tăng lên một cách lặp lại trong bước 6 để bảo đảm đủ bảo phủ cho tập đặc trưng kết quả. Chúng ta thấy rằng N/k chỉ là một hướng dẫn phỏng đoán, số lượng thực tế các phân cụm của kết quả phân cụm có thể không giống như N/k. Phương pháp cũng sử dụng một ngưỡng hồi tưởng để đảm bảo rằng các đặc trưng được chọn có đủ độ hồi tưởng. Với các thử nghiệm ([24]), chúng ta thấy rằng 0.8 là giá trị ngưỡng hồi tưởng khá tốt. b, Biểu diễn tài liệu Trong thuật toán của chúng ta, một tài liệu (Di) được biểu diễn theo dạng sau: Di=(Wi,IDi), trong đó IDi là sự nhận dạng tài liệu có thể được sử dụng để lấy tài liệu (Di), và Wi là vector đặc trưng của tài liệu: Wi=(wi1,wi2,...,win). Do đó n là số các đặc trưng đã được trích chọn, và wij là trọng số của đặc trưng thứ j, trong đó j Є {1,2,..,n}. Trong thuật toán của chúng ta, sự sắp xếp trọng số nhị phân được sử dụng. Đó là, wij =1 nếu Di bao gồm đặc trưng thứ j, ngược lại, wij =0. Như đã đề cập tại phần trích chọn đặc trưng phía trên, một trang Web điển hình không bao gồm nhiều từ mà tần xuất xuất hiện của một từ không biểu thị sự quan trọng trong thực tế của từ này. Bởi vậy, lược đồ trọng số nhị phân là thích hợp nhất cho phạm vi vấn đề của chúng ta. c, Phân cụm tài liệu (DC) Một giá trị phân cụm tài liệu (DC- Document Cluster) là một bộ ba thông tin mà chúng ta duy trì bởi một tập các tài liệu trong cùng một cụm: (1) số các tài liệu (2) tập các nhận dạng tài liệu Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 54 - (3) vector đặc trưng của phân cụm Định nghĩa1: (DC) Cho N tài liệu trong một phân cụm: {D1,D2,...DN}, giá trị DC của một nút được định nghĩa như một bộ ba: DC = (N,ID,W), trong đó N là số lượng các tài liệu trong cụm, ID là tập các nhận dạng tài liệu của các tài liệu trong cụm, ví dụ ID={ID1,ID2,...IDN}, và W là vector đặc trưng của cụm tài liệu, ví dụ W=(w1,w2,...,wn), trong đó wj=∑ = N i ijw 1 , và n là số các đặc trưng đã được trích chọn. Bộ ba này không chỉ ra tổng hợp tần suất tài liệu trong cụm, nhưng có thể sử dụng để đánh giá sự giống nhau giữa hai cụm. Bổ đề sau cung cấp một cách linh hoạt kết nối hai cụm thành một và cho ra giá trị DC cho cụm kết hợp. Bổ đề [24] (Phép cộng) Cho DC1 = (N1,ID1,W1) and DC2= (N2,ID2,W2) là bộ giá trị DC của hai cụm tài liệu tách rời, trong đó tách rời có nghĩa là một tài liệu không thuộc về nhiều hơn một cụm tại cùng một thời điểm. Khi đó bộ giá trị DC mới, DCnew, của cụm được hình thành bằng cách kết hợp hai cụm tách biệt là: DCnew = (N1+N2, ID1 ∪ ID1, W1+W2), trong đó W1+W2= (w11+w21,w12+w22,...,w1n+w2n), và n là số các đặc trưng đã được trích chọn. d, Các kỹ thuật đánh giá Để đánh giá chất lượng của kết quả việc phân cụm, chúng ta chọn kỹ thuật đánh giá F-Measure (độ đo lường F) [23]. Chi tiết của phương pháp đánh giá được mô tả như sau: Cho từng topic được gán nhãn bằng tay T trong tập tài liệu, giả sử rằng một phân cụm X tương ứng với topic đó được hình thành. N1= số các tài liệu của topic T trong phân cụm X N2=số các tài liệu trong phân cụm X N3= tổng số các tài liệu của topic T P=Precision(X,T)=N1/N2 R=Recall(X,T)=N1/N3 F-measure cho topic T được địng nghĩa như sau: Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 55 - F(T)= RP PR + 2 Với đánh giá cao với một topic T, chúng ta quan tâm phân cụm với độ đo F-measure cao nhất để phân cụm C cho T, và độ đo F-measure đó trở thành điểm số cho topic T. Độ đo overall F-measure[22] cho cây kết quả phân cụm là giá trị trung bình của F-measure cho từng topic T: Overall_F_Measure= ∑ ∑ ∈ ∈ × MT MT T TFT ))(( trong đó M là tập các topic, |T| là số các tài liệu của topic T, và F(T) là F-Measure cho topic T. 3.3.3. Cây phân cụm tài liệu –DC Tree Trong phần này xin giới thiệu một thuật toán phân cụm tài liệu Web bằng phương tiện là cây phân cụm tài liệu (Document Cluster -DC-tree). Trong DC- tree, mỗi nút có thể được quan tâm như một phân cụm tài liệu. Cấu trúc cây được sử dụng để hướng dẫn cách đưa đối tượng tài liệu vào một phân cụm tài liệu (DC) thích hợp tại các nút lá. Nó là tương tự với B+-tree [2] trong đó các bản ghi chỉ số tại các nút lá bao gồm các con trỏ trỏ tới các đối tượng dữ liệu, nhưng nó không là cây có chiều cao cân bằng. Cấu trúc này được thiết kế bởi vì việc gán một tài liệu vào một phân cụm chỉ yêu cầu duyệt qua một số lượng nhỏ các nút. Một DC-tree là một cây với 4 tham số: hệ số nhánh (B), hai ngưỡng tương tự (S1 và S2, trong đó 0 ≤ S1 , S2 ≤ 1) và số nhỏ nhất con của một nút (M). Một nút không phải là lá của toàn bộ các chỉ mục của B có dạng (DCi, Childi), trong đó i=1, 2,..., B, “Childi” là một con trỏ tới nút con thứ i hoặc một tài liệu, và DCi là giá trị DC của phân cụm con tiêu biểu cho nút con thứ i hoặc một tài liệu của nó. Vì thế, một nút không phải là lá mô tả một cụm cấu tạo nên tất cả các cụm con được mô tả bởi chỉ mục của nó. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 56 - Một nút lá DC của toàn bộ chỉ mục B là một chỉ mục có dạng (DCi, Doci), trong đó i Є {1, 2, ..., B}, “Doci” là một con trỏ tới một tài liệu hoặc một tập tài liệu, và DCi là chỉ mục DC của cụm con tương ứng. Gọi tập tài liệu dưới một con trỏ là một nút lá tài liệu ( document leaf node), để phân biệt với nó trong nút lá cây (tree leaf node) hoặc DC leaf node (xem hình 8). Một nút lá DC cũng mô tả một cụm cấu tạo nên tất cả các cụm con được mô tả bởi các chỉ mục DC của nó. Cây DC cho phép một chỉ mục đưa tài liệu vào, để chèn vào một nút lá tài liệu mới tại các mức khác nhau của cây. Vì thế, Cây DC không phải là một cây có chiều cao cân bằng. Hình 8 biểu diễn một ví dụ cây DC với chiều cao là 2, B=3, M=2. Chú ý rằng cây là không cân bằng. Trong việc xây dựng cây, hai ngưỡng được sử dụng: Hình 8. Ví dụ của một cây DC Ngưỡng S1: Để ngăn chặn kết quả phân cụm tài liệu kém chất lượng (ví dụ: Các tài liệu trong các lớp khác nhau được đưa vào cùng 1 cây con hoặc phân cụm) được gây ra bởi thứ tự chèn tài liệu, S1 được sử dụng để quyết định tài liệu đến E có thể được chuyển tới cấp độ tiếp theo hay không trong quá trình chèn tài liệu. Nếu tồn tại một tài liệu con của nút hiện tại mà độ tương tự giữa tài liệu này và tài liệu sắp được đưa vào lớn hơn S1, tài liệu mới sẽ được chuyển đến nút con tương ứng. Ngược lại, tài liệu mới sẽ được thêm vào nút hiện tại như một nút lá mới. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 57 - Ngưỡng S2: Do cây DC được sử dụng cho việc phân cụm tài liệu mà không sử dụng đánh chỉ mục, do đó không cần thiết phải ép mỗi nút lá trỏ đến một tài liệu đơn. Để làm giảm thời gian chèn, tài liệu mới có thế được gộp với một nút lá, nếu độ tương tự của nó lớn hơn một ngưỡng S2. Việc gộp nút này sử dụng phép gộp được mô tả trong bổ đề 1, nó giúp cho giảm bớt việc chèn nút và các thao tác phân chia vì thế mà thời gian chèn có thể giảm đi. Có thể coi cây DC là một thể hiện của tập dữ liệu vì mỗi tài liệu ở nút lá không phải là một điểm dữ liệu đơn mà là một phân cụm của các điểm dữ liệu (mỗi nút lá có thể có nhiều điểm dữ liệu miễn là thỏa mãn ngưỡng S2). Với định nghĩa về cây DC như trên, cỡ của cây sẽ là một hàm dựa trên các ngưỡng S1 và S2. Nếu chúng ta đặt S1 = 0 và S2 là một số nào đó lớn hơn 1, cây DC sẽ tương tự như một cây cân bằng như cây B+ hoặc một cây R [21]. Việc xóa dữ liệu cũng như thuật toán trộn là tương tự như của cây B+. A. Chèn Sau đây là thuật toán để chèn một đối tượng tài liệu vào cây DC. Đối tượng tài liệu ở đây có thể là một tài liệu đơn hoặc một phân cụm của các tài liệu được biểu diễn bởi một nhóm DC (E). Nếu như đối tượng tài liệu là một tài liệu đơn, đầu tiên nó sẽ được gói vào trong một nhóm DC (E). Thuật toán chèn được tiến hành theo những bước sau đây: 1. Nhận dạng nút lá thích hợp: Bắt đầu từ gốc, E duyệt xuống dưới cây DC bằng việc chọn nút con gần nhất với giá trị tương tự lớn hơn S1. Nếu nút con này không tồn tại, E được chèn vào như một nút lá tài liệu vào một nhóm rỗng của nút. Nếu không có nhóm rỗng nào, việc chia nhỏ nút cần được thực hiện. 2. Thay đổi nút lá: Khi chúng ta đang ở một nút lá của cây DC, chúng ta tìm ra nhóm ở nút lá gần nhất với E, ký hiệu là Li và kiểm tra xem nó có thể gộp với E mà không vi phạm yêu cầu về ngưỡng tương tự S2 không. Nếu không vi phạm, nhóm chứa Li sẽ được dùng để gộp. Chú ý rằng một nhóm DC của một phân cụm mới có thể được tính từ những nhóm DC cho Li và E dựa vào bổ đề 1. Ngược lại, E sẽ được cộng vào nút lá. Nếu có khoảng trống trong nút lá để thêm Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 58 - được nhóm này, coi như chúng ta đã hoàn thành, ngược lại, chúng ta phải chia nhỏ nút lá. 3.Thay đổi đường dẫn từ nút lá đến gốc: Sau khi E được chèn vào một nút lá, chúng ta phải cập nhật lại các nhóm không phải là lá trên đường từ gốc đến nút lá. Do chưa có việc chia nhỏ, việc này được thực hiện bằng cách thêm các nhóm DC để tương ứng với việc thêm vào E. Việc chia một nút lá yêu cầu chúng ta phải chèn một nhóm không phải là lá mới vào nút cha, việc này tương ứng với việc tạo ra một nút lá mới. Nếu như nút cha có khoảng trống để mục này có thể chèn vào thì tại tất cả các mức lớn hơn, chúng ta chỉ cập cập nhật các nhóm DC để tương ứng với việc thêm vào E. Một cách tổng quan, chúng ta có thể phải chia nhỏ cả nút cha và thậm chí cả nút gốc. Nếu nút gốc bị chia nhỏ, độ cao của cây sẽ được tăng thêm 1 và một gốc mới sẽ được tạo ra. B. Chi nhỏ nút Để thêm một nhóm mới vào một nút đã đầy chứa B nhóm, cần thiết phải chia tập B+1 nhóm thành 2 nút. Sự chia sẻ này nên được hoàn thành sao cho độ tương tự giữa 2 nút mới sẽ là nhỏ nhất và độ tương tự giữa các tài liệu trong cùng một nút sẽ là lớn nhất. Chúng ta sẽ sử dụng một thuật toán chia nhỏ một tập B+1 nhóm vào 2 tập. Cách đơn giản nhất là tạo ra tất cả các tập có thể và chọn tập tốt nhất. Tuy nhiên, số lượng tập này có thể là rất lớn, xấp xỉ 2B-1 . Phía dưới là một thuật toán chia nút sử dụng thuật toán chèn. Thuật toán chia nút này tương tự như phương pháp được sử dụng trong cây R: 1. Chọn một hạt nhân cho mối nhóm: Mới mỗi cặp nhóm E1 và E2, tính toán độ tương tự giữa chúng. Chọn ra cặp có độ tương tự thấp nhất như là các nhân tố đầu tiên của 2 tập. Để tránh hiệu ứng thắt nút, chúng ta nên chọn ra cặp có số lượng tài liệu là lớn nhất. 2. Kiểm tra điều kiện kết thúc: Nếu tất cả các nhóm đã được đưa vào các tập, dừng ở đây. Nếu một tập có rất ít nhóm thì tất cả các nhóm chưa được xét sẽ được đưa vào nó để thỏa mãn số nhóm nhỏ nhất M. 3. Chọn tập tương ứng: Với mỗi nhóm E chưa ở trong tập nào, tính toán độ tương tự giữa E và một nhóm hạt nhân của mỗi tập. Đưa nhóm vào tập có giá trị tương tự lớn nhất với nó. Quay lại bước 2. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 59 - C. Xóa và trộn nút Thuật toán xóa dữ liệu là tương tự như trong cây B+. Nếu số lượng còn lại của các nhóm lớn hơn hoặc bằng số lượng nhóm tối thiểu M nào đó sau khi loại bỏ một nhóm, việc xóa nút được hoàn thành. Ngược lại việc trộn nút sẽ được sử dụng. Điều này có nghĩa là nút sẽ được trộn với với các anh em của nó. Hơn nữa, việc trộn nút là cần thiết khi một nhóm xa lạ với nút cha. Công việc này được nhân ra tới nút gốc và độ cao của cây có thể bị giảm xuống nếu cần thiết. D. Nhận dạng các phân cụm thú vị Quá trình nhận dạng phận cụm bắt đầu từ gốc của cây. Một thuật toán tìm kiếm “breath-first” được áp dụng để khám phá ra các phân cụm thú vị. Một phân cụm thú vị được định nghĩa là một phân cụm mà chứa các nét đặc trưng tiêu biểu và kích cỡ ở trong một khoảng định trước. Chúng ta có thể sử dụng các giá trị chặn dưới (lower) và chặn trên (upper) được tìm thấy trong phương thức bóc tách đặc trưng của chúng ta để quyết định khoảng giới hạn của cỡ phân cụm. Giả sử l và u là chặn dưới và chặn trên của cỡ phân cụm, thì l và u có thể được quyết định bằng công thức sau: (1) m Nlowerl ×= và (2) m Nupperu ×= Trong đó N là cỡ của tập dữ liệu và m là cỡ của tập dữ liệu mẫu được sử dụng trong quá trình bóc tách đặc trưng. Phạm vi này cũng có thể được điều chỉnh thủ công để đạt được một kết quả phân cụm tốt. Một khi chúng ta đã nhận diện được một phân cụm thú vị, các phân cụm con trong các nút con của nó sẽ không cần phải duyệt nữa. Một đặc trưng tiêu biểu được định nghĩa là một đặc trưng có sự hỗ trợ đủ trong phân cụm. Có nghĩa là tần suất tài liệu của các nét đặc trưng tiêu biểu phải lơn hơn một ngưỡng định trước nào đó. Chúng ta có thể gọi ngưỡng này là ngưỡng tiêu biểu. Các đặc trưng này sau đó sẽ được sử dụng làm đại diện cho phân cụm. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 60 - 3.4. Kết luận chương 3 Chương này trình bày chi tiết hai thuật toán phân cụm có tính tăng là STC và DC-tree. Đồng thời đưa ra các nhận xét cho từng thuật toán, luận văn đưa ra nhận xét thuật toán phân cụm thích hợp đối với các tài liệu Web áp dụng vào máy tìm kiếm. Chương trình cài đặt thử nghiệm cho thuật toán và việc đánh giá kết quả thuật toán sẽ được trình bày ở chương tiếp theo. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 61 - CHƯƠNG 4 - PHẦN MỀM THỬ NGHIỆM VÀ KẾT QUẢ THỰC NGHIỆM 4.1. Giới thiệu Trong phạm vi của luận văn này, tôi áp dụng thuật toán phân cụm tài liệu sử dụng cấu trúc DC-tree vào chương trình thử nghiệm của mình. Để thực nghiệm kết quả của phân cụm DC Tree, tôi đã thể hiện thuật toán này bằng ngôn ngữ lập trình C# trên nền tảng .Net Framework của Microsoft sử dụng SQL Server 2000 để lưu trữ cơ sở dữ liệu. Các chức năng chính của chương trình bao gồm: - Lập dữ liệu từ điển Dựa trên ý tưởng phân cụm sử dụng cụm từ, chương trình đã xây dựng một hệ thống từ điển để phục vụ cho thuật toán tách từ Longest Matching. Ban đầu, các từ này được xây dựng dựa trên các từ lấy từ dữ liệu từ điển Việt-Anh tại nguồn Các dữ liệu này có thể được bổ sung, sửa chữa dần dần để nâng cao hiệu quả của phân cụm. - Lấy dữ liệu từ Internet Dữ liệu phân cụm sẽ được lấy từ Internet một cách độc lập với việc phân cụm. Chương trình sẽ được định nghĩa sẵn một ngưỡng n cho việc lấy dữ liệu từ Internet. Điều này có nghĩa là, sau khi người quản trị cung cấp cho chương trình một URL, chương trình tự động lấy nội dung trang web từ URL này về sau đó phân tích nội dung trang web, tìm các URL khác nằm trong trang web này. Quá trình trên được lặp lại với URL tìm được cho đến khi độ sâu n được thỏa mãn. Như thế với độ sâu n phù hợp, ta có thể lấy được toàn bộ nội dung của một trang Web. - Tách từ và phân cụm Chức năng này cho phép chương trình tách từ và phân cụm các dữ liệu mới được lấy về. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 62 - Trong chức năng này, có 3 bước được thực hiện: Bước 1: Tách từ sử dụng thuật toán Longest Matching với từ điển dựng sẵn Bước 2: Tách từ sử dụng thuật toán fnTBL từ dữ liệu trả về từ thuật toán Longest Matching. Bước 3: Phân cụm dựa trên thuật toán DC-Tree sử dụng hàm tính độ tương tự dựa trên các cụm từ tách được. - Tìm kiếm trên kết quả phân cụm Việc tìm kiếm này sẽ được áp dụng một thuật toán bao gồm 2 bước: Bước 1: Tính độ tương tự của chuỗi tìm kiếm với các đặc trưng của các phân cụm, nếu độ tương tự lớn hơn một ngưỡng S1 nào đó, ta sẽ áp dụng bước 2 cho phân cụm đó. Bước 2: Tìm kiếm các tài liệu trong phân cụm có độ tương tự cao hơn một ngưỡng S2 với chuỗi tìm kiếm. 4.2. Thiết kế cơ sở dữ liệu Cơ sở dữ liệu của chương trình được thiết kế như trong hình phía dưới. Trong đó chức năng của các bảng được mô tả như sau: Bảng: Dictionary – Đây là bảng chứa dữ liệu từ điển tiếng Việt Tên trường Kiểu dữ liệu Mô tả PhraseID Int Là khóa chính của bảng. Phrase Nvarchar Là cụm từ cần lưu trữ PhraseDescription Ntext Là mô tả của cụm từ cần lưu trữ. Hiện tại chưa được sử dụng. Chứa dữ liệu ngữ nghĩa tiếng Anh sau khi được convert từ từ điển StarDict. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 63 - Bảng Documents – Đây là bảng chứa các tài liệu được chương trình lấy về Tên trường Kiểu dữ liệu Mô tả DocID Int Là khóa chính của bảng. Source Nvarchar Địa chỉ nguồn của tài liệu gốc. Dùng để đánh chỉ mục, tránh trùng lặp tài liệu. Snipet Ntext Là trích đoạn của tài liệu, phục vụ cho việc phân cụm. IsTokenized Bit Cho biết tài liệu này đã được tách từ hay chưa. IsClustered Bit Cho biết tài liệu đã được phân cụm hay chưa. Bảng DocumentIndex – Đây là bảng liên kết giữa các tài liệu và dữ liệu từ điển. Tên trường Kiểu dữ liệu Mô tả DocIndexID Int Là khóa chính của bảng. PhraseID Int Khóa ngoài, liên kết đến bảng Dictionary DocID Int Khóa ngoài, liên kết đến bảng Documents Score Float Cho biết độ tương tự/tần suất của từ khóa trong tài liệu dựa trên một hàm tính độ tương tự. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 64 - Bảng Nodes – Chứa các nút của cây DC Tên trường Kiểu dữ liệu Mô tả NodeID Int Là khóa chính của bảng. NodeParentID Int Chứa nút cha của cây ClusterID Int Cho biết phân cụm của nút thuộc vào. Bảng Node-Document – Vì một nút có thể chứa nhiều tài liệu và ngược lại, một tài liệu có thể nằm trên nhiều nút. Bảng này thể hiện mối quan hệ nhiều-nhiều này Tên trường Kiểu dữ liệu Mô tả NodeDocumentID Int Là khóa chính của bảng. NodeID Int Khóa ngoài, liên kết đến bảng Nodes DocID Int Khóa ngoài, liên kết đến bảng Documents Bảng Clusters – Chứa các phân cụm tìm được Tên trường Kiểu dữ liệu Mô tả ClusterID Int Là khóa chính của bảng. Cho biết số thứ tự của phân cụm. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 65 - Dưới đây là sơ đồ liên kết thực thể giữa các bảng: Hình 7. Sơ đồ liên kết thực thể của chương trình thực nghiệm 4.3. Chương trình thử nghiệm Áp dụng các nghiên cứu về lý thuyết phân cụm, trong chương trình thử nghiệm của chúng tôi, mỗi một bước thực hiện sẽ được tách thành từng phần riêng. Tương ứng với các chức năng chính đã mô tả ở trên, chương trình bao gồm bốn module chính: Từ điển, Lấy dữ liệu, Phân cụm, Tìm kiếm. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 66 - - Module Từ điển: hiển thị tất cả các từ có trong từ điển Việt. Với dữ liệu ban đầu được lấy từ nguồn từ điển Việt-Anh tại địa chỉ ta sẽ có một kho từ điển khá hoàn chỉnh các từ Tiếng Việt. Tuy nhiên ta cũng có thể thêm hoặc bớt những từ đã có nếu thấy cần thiết. Tập các từ trong từ điển này sẽ được sử dụng trong bước tách từ trong tài liệu cần phân cụm. Hình: Màn hình hỗ trợ chức năng cập nhật chỉnh sửa Từ điển - Module Lấy dữ liệu: Để xây dựng kho dữ liệu các tài liệu Web, ta tiến hành lấy dữ liệu về. Người sử dụng sẽ nhập đường dẫn URL của trang Web, hệ thống sẽ tự động tìm kiếm và lấy tất cả nội dung của trang Web với một độ sâu n ( đã được định trước) Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 67 - Hình: Màn hình chức năng hỗ trợ lấy dữ liệu từ Internet - Module Phân cụm: Sau khi tiến hành lấy dữ liệu, ta thực hiện phân cụm tài liệu. Hệ thống sẽ tiến hành phân cụm một cách tự động. Trong lần phân cụm khác với tập dữ liệu mới được lấy về, việc phân cụm sẽ không cần phân cụm lại với tập dữ liệu cũ mà ta đã phân cụm trước nữa. Việc phân cụm sẽ chỉ cần thực hiện trên tập dữ liệu mới với kết quả cũ của các lần phân cụm trước. Trong thuật toán có sử dụng các tham số sau: M: Số lượng nhỏ nhất con của một nút M=8 B: Hệ số nhánh của cây B=20 S2:Ngưỡng tương tự 2 S2=1.0 S1: Ngưỡng tương tự 1 S1=0.3 repThreshold: Ngưỡng của đặc trưng tiêu biểu repThreshold=0.4 MCS: Cỡ phân cụm nhỏ nhất MCS=100 Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 68 - Hình: Màn hình hỗ trợ chức năng Phân cụm với dữ liệu đã lấy về từ Internet - Module Tìm kiếm: Người sử dụng sẽ nhập vào từ khoá cần tìm kiếm. Hệ thống sẽ tìm các tài liệu liên quan với từ khoá. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 69 - Hình: Màn hình chức năng hỗ trợ Tìm kiếm. 4.4. Kết luận chương 4 Chương này là kết quả cài đặt thử nghiệm của thuật toán phân cụm cho tài liệu Web Tiếng Việt sử dụng cấu trúc dữ liệu DC-tree đã được trình bày ở chương 3. Chương trình cài đặt viết bằng ngôn ngữ lập trình C# trên nền tảng .Net Framework của Microsoft sử dụng SQL Server 2000 để lưu trữ cơ sở dữ liệu. Chương trình đã thực hiện việc phân cụm với kết quả tương đối hợp lý. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 70 - KẾT LUẬN Luận văn cung cấp một số nội dung về phân cụm Web, đã đạt được một số kết quả như sau: - Giới thiệu khái quát về bài toán phân cụm web, các giải pháp phân cụm web (các yêu cầu, kỹ thuật, đánh giá) trong đó chú ý tới tính tăng của các thuật toán phân cụm wbe, - Trình bày hai thuật toán phân cụm web có tính tăng là STC và DC-tree. Đã phân tích các nội dung kiến thức cơ bản, nền tảng phát triển các thuật toán này. - Xây dựng phần mềm thử nghiệm phân cụm tài liệu theo thuật toán DC- tree. Hệ thống máy tìm kiếm-DC tree do luận văn phát triển đã được đưa lên web, có công cụ lưu các câu truy vấn của người dùng, các phân cụm tìm thấy và các liên kết được người dùng đi tới. Hệ thống đã hoạt động và thực hiện được việc phân cụm các tài liệu Web. Do hạn chế về thời gian và năng lực, luận văn chưa tiến hành đánh giá chất lượng phân cụm của hệ thống. Trong tương lai, chúng tôi sẽ tiến hành các đánh giá công phu hơn. Chúng tôi dự kiến đưa ra các thống kê dựa trên hành vi của hệ thống trong thực tế. Ngoài ra, chúng tôi có thể nghiên cứu các hướng giải quyết vấn đề từ đồng nghĩa trong tiếng Việt. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 71 - TÀI LIỆU THAM KHÁO Tiếng Việt [1]. Đinh Điền, Xử lý ngôn ngữ tự nhiên, NXB Giáo Dục. Tiếng Anh [2]. Clement T.Yu và Weiyi Meng (1998), Principles of Database Query Processing for Advanced Application, Morgan Kaufmann Publisher, Inc. [3]. Gerard Salton/Michael J.McGill, Introduction to Modern Information Retrieval. [4]. M. Steinbach, G. Karypis, V. Kumar (2000), A Comparison of Document Clustering Techniques, TextMining Workshop, KDD. [5]. O. Zamir and O. Etzioni (1998), Web Document Clustering: A Feasibility Demonstration, Proc. of the 21st ACM SIGIR Conference, 46-54. [6]. O. Zamir, O. Etzioni, O Madani, R. M. Karp (1997), Fast and Intuitive Clustering of Web Documents, Proc. of the 3rd International Conference on Knowledge Discovery and Data Mining. [7]. K. Cios, W. Pedrycs, R. Swiniarski (1998), Data Mining – Methods for Knowledge Discovery, Kluwer Academic Publishers. [8]. R. Krishnapuram, A. Joshi, L. Yi (1999), A Fuzzy Relative of the k-Medoids Algorithm with Application to Web Document and Snippet Clustering, Proc. IEEE Intl. Conf. Fuzzy Systems, Korea. [9]. Z. Jiang, A. Joshi, R. Krishnapuram, L. Yi (2000), Retriever: Improving Web Search Engine Results Using Clustering, Technical Report, CSEE Department, UMBC. [10]. T. H. Haveliwala, A. Gionis, P. Indyk (2000), Scalable Techniques for Clustering the Web, Extended Abstract, WebDB’2000, Third International Workshop on the Web and Databases, In conjunction with ACM SIGMOD’2000, Dallas, TX. [11]. A. Bouguettaya (1996), On-Line Clustering, IEEE Trans. on Knowledge and Data Engineering. [12]. A. K. Jain và R. C. Dubes (1988), Algorithms for Clustering Data, John Wiley & Sons. [13]. G. Karypis, E. Han, V. Kumar (1999), CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling, IEEE Computer 32. [14]. O. Zamir và O. Etzioni (1999), Grouper: A Dynamic Clustering Interface to Web Search Results, Proc. of the 8th International World Wide Web Conference, Toronto, Canada. [15]. D. R. Cutting, D. R. Karger, J. O. Pedersen, J.W. Tukey (1993), Scatter/Gather: A Clusterbased Approach to Browsing Large Document Collections, In Proceedings of the 16th International ACM SIGIR Conference on Research and Development in Information Retrieval. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 72 - [16]. R. Michalski, I. Bratko, M. Kubat (1998), Machine Learning and Data Mining – Methods and Applications, John Wiley & Sons Ltd.. [17]. J. Jang, C. Sun, E. Mizutani (1997), Neuro-Fuzzy and Soft Computing – A Computational Approach to Learning and Machine Intelligence, Prentice Hall. [18]. G. Biswas, J.B. Weinberg, D. Fisher (1998), ITERATE: A Conceptual Clustering Algorithm for Data Mining, IEEE Transactions on Systems, Man and Cybernetics. [19]. Z. Huang (1997), A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining, Workshop on Research Issues on Data Mining and Knowledge Discovery. [20]. Y. Yang và J. Pedersen (1997), A Comparative Study on Feature Selection in Text Categorization, In Proc. of the 14th International Conference on Machine Learning. [21]. A Guttman (1984). R-tree: A dynamic index structure for spatial searching, In Proceedings of ACM SIGMOD. [22]. Bjornal Larsen và Chinatsu Aone (1999). Fast and effective text mining using lineartime document clustering, In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA. [23]. C.J.van Rijbergen(1979), Information Retrieval, Butterworth & Co (Publishers) LTd. [24]. Wai-chiu Wong và Ada Fu (2000), Incremental Document Clustering for Web Page Classification, IEEE 2000 Int, Conf. on Infor, Society in the 21st century: emerging technologies anf new challenges (IS2000), Nhật Bản. [25]. Pierre Baldi, Paolo Frasconi, Padhraic Smyth (2003). Modeling the Internet and the Web: Probabilistic Methods and Algorithms. Wiley, 2003. [26]. Sen Slattery (2002). Hypertext Classification. PhD Thesis (CMU-CS-02- 142). School of Computer Science. Carnegie Mellon University, 2002.