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

p Dựa vào các vùng vấn đề, thỉnh thoảng các đối tượng biểu diễn dữ liệu đặc trưng không có cùng kiểu. Một sự kết hợp giữa các kiểu dữ liệu số, phân loại, không gian hoặc text có thể được sử dụng. Trong trường hợp này, vấn đề quan trọng là nghĩ ra một phương pháp có thể nắm giữ tất cả các thông tin một cách hiệu quả. Một quy trình chuyển đổi nên được áp dụng để chuyển đổi từ một kiểu dữ liệu này thành một kiểu dữ liệu khác. Thỉnh thoảng một kiểu dữ liệu không thể áp dụng vào được, lúc đó thuật toán phải được chỉnh sửa để làm việc với các kiểu dữ liệu khác [18]. 2.3.2. Độ đo về sự tương tự Nhân tố chính trong thành công của bất kỳ một thuật toán phân cụm nào đó chính là độ đo về sự tương tự của nó. Để có thể nhóm các đối tượng dữ liệu, một ma trận xấp xỉ đã được sử dụng để tìm kiếm những đối tượng (hoặc phân cụm) tương tự nhau. Có một số lượng lớn các ma trận tương tượng đã được đề cập đến trong các tài liệu, ở đây, chúng ta chỉ xem qua một số ma trận thông thường nhất. Việc tính toán độ (không) tương tự giữa 2 đối tượng được thực hiện thông qua các hàm tính khoảng cách (distance), thỉnh thoảng cũng có thể sử Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 28 - dụng các hàm tính về độ không tương tự (dissimilarity). Với 2 véc tơ đặc trưng x và y, cần phải tìm ra độ tương tự (hoặc không tương tự) giữa chúng. Một lớp rất hay được sử dụng của các hàm khoảng cách đó là “gia đình các khoảng cách Minkowski” [7], được mô tả như phía dưới: p n i p ii yxyx ∑ = −=− 1 Trong đó x,y ∈ Rn. Hàm khoảng cách này thực ra là mô tả một họ vô số các khoảng cách được đưa ra bởi p. Thông số này giả thiết là các giá trị lớn hơn hoặc bằng 1. Một vài giá trị chung của p và các hàm khoảng cách là: p = 1: Khoảng cách Hamming ∑ = −=− n i ii yxyx 1 p = 2: Khoảng cách Euclidean ∑ = −=− n i ii yxyx 1 2 p = ∞: Khoảng cách Tschebyshev =− yx maxi=1,2,...,n ii yx − Một độ đo độ tương tự hay được dùng, đặc biệt là trong phân cụm tài liệu đó là độ đo liên quan cosine (cosine correlation) (được sử dụng trong [4], [15], và [13]), được định nghĩa là: yx yxyx .),cos( = trong đó . biểu thị việc nhân vector và ||.|| biểu thị cho độ dài của vector. Một độ đo hay được dùng khác đó là độ đo Jaccard (được sử dụng trong [8], [9]), được định nghĩa là: ),max( ),min( ),( 1 1 i n i i i n i i yx yx yxd ∑ ∑ = == trong trường hợp các vector đặc trưng nhị phân, có thể đơn giản hóa thành: yx yx yxd ∪ ∩=),( Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 29 - Cần phải chú ý rằng từ “khoảng cách” không có gì nhập nhằng với “tương tự”. Những từ này là trái nghĩa với nhau, cho chúng ta biết độ tương tự giữa 2 đối tượng. Độ tương tự giảm khi khoảng cách tăng. Thêm một điểm cần chú ý khác đó là nhiều thuật toán sử dụng hàm khoảng cách (hoặc tương tự) để tính toán sự tương tự giữa 2 phân cụm, một phân cụm và một đối tượng, hai đối tượng. Việc tính toán khoảng cách giữa 2 phân cụm (hoặc các phân cụm và các đối tượng) yêu cầu một vector đặc trưng đại diện cho phân cụm. Thường thì các thuật toán phân cụm thường sử dụng một ma trận tương tự (similarity matrix). Một ma trận tương tự cỡ N × N ghi nhận các khoảng cách (hoặc độ tương tự) giữa từng cặp đối tượng. Hiển nhiên ma trận tương tự là một ma trận đối xứng do đó chúng ta chỉ cần lưu phần trên bên phải hoặc phần dưới bên trái của nó. 2.3.3. Mô hình phân cụm Bất cứ thuật toán phân cụm nào cũng thừa nhận một cấu trúc phân cụm nào đó. Đôi khi cấu trúc phân cụm không thực sự rõ ràng tùy theo nhu cầu của bản thân thuật toán phân cụm. Ví dụ, thuật toán k-means sử dụng các phân cụm hình cầu (hoặc các phân cụm lồi). Đó là vì theo cách k-means tìm kiếm phân cụm trung tâm và cập nhật các đối tượng thành viên. Nếu như không cẩn thận, chúng ta có thể kết thúc việc phân cụm với các phân cụm kéo dài (elongated cluster), trong đó kết quả là có ít phân cụm lớn và có nhiều phân cụm rất nhỏ. Wong và Fu [16] đã đưa ra một giải pháp để giữ kích cỡ phân cụm trong một khoảng nào đó, nhưng việc giữ kích cỡ phân cụm trong một khoảng nào đó không phải bao giờ cũng đáng thực hiện. Một mô hình động để tìm kiếm các phân cụm không thích hợp với cấu trúc của chúng đó là CHAMELEON, được đưa ra bơi Karypis [13]. Tùy theo vấn đề, chúng ta có thể có các phân cụm tách rời (disjoint) hoặc các phân cụm chồng chéo (overlapping). Trong ngữ cảnh phân cụm tài liệu thường mong muốn có các phân cụm chồng chéo bởi vì tài liệu có xu hướng có nhiều hơn một chủ đề (ví dụ một tài liệu có thể chứa thông tin về đua ô tô và các công ty ô tô). Một ví dụ khác về việc tạo ra các phân cụm chồng chéo là hệ thống cây hậu tố (STC) được đưa ra bởi Zamir và Etzionin [5]. Một cách khác để tạo ra các phân cụm chồng chéo đó là phân cụm mờ trong đó các đối tượng có thể Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 30 - thuộc vào các phân cụm khác nhau dựa vào các cấp độ khác nhau của tư cách thành viên [8]. 2.4. Một số kỹ thuật Phân cụm Web điển hình Kỹ thuật phân cụm được chia thành 2 nhóm chính: Phân cụm theo thứ bậc và phân cụm bằng cách phân mảnh. 2.4.1. Phân cụm theo thứ bậc Các kỹ thuật phân cụm theo thứ bậc đưa ra một chuỗi các phần chia lồng vào nhau với một phân cụm gốc ở trên cùng và các phân cụm đơn của các đối tượng đơn lẻ ở phía dưới. Các phân cụm ở cấp độ trên chứa các phân cụm phía dưới chúng theo thứ bậc. Kết quả của thuật toán phân cụm theo thứ bậc có thể xem như một cây, được gọi là một dendogram (Hình 3). Hình 3: Một ví dụ dendogram của phân cụm sử dụng phân cụm có thứ bậc Tùy thuộc vào định hướng của việc xây dựng thứ tự, chúng ta có thể chỉ ra các phương thức của phân cụm theo thứ bậc: tích tụ (Agglomerative) hay chia xẻ (Divisive). Phương thức tích tụ được sử dụng trong hầu hết các phân cụm theo thứ bậc. a, Phân cụm tích tụ theo thứ bậc (AHC) Phương thức này bắt đầu với tập các đối tượng là các phân cụm đơn lẻ, tiếp đó, tại mỗi bước kết nối 2 phân cụm giống giau nhất với nhau. Quá trình này Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 31 - được lặp lại cho đến khi số lượng phân cụm còn lại đạt đến một ngưỡng cho phép hoặc là nếu cần phải hoàn thành toàn bộ thứ bậc thì quá trình này sẽ tiếp tục cho đến khi chỉ còn 1 phân cụm. Phân cụm tích tụ làm việc theo mô hình tham ăn (greedy), trong đó cặp nhóm tài liệu được chọn cho việc tích tụ là cặp mà được coi là giống nhau nhất theo một số tiêu chuẩn nào đó. Phương thức này tương đối đơn giản nhưng cần phải định nghĩa rõ việc tính khoảng cách giữa 2 phân cụm. Có 3 phương thức hay được dùng nhất để tính toán khoảng cách này được liệt kê ở phía dưới. • Phương thức kết nối đơn (Single Linkage Method): Độ tương tự giữa 2 phân cụm S và T được tính toán dựa trên khoảng cách ngắn nhất (minimal) giữa các thành phần nằm trong các phân cụm tương ứng. Phương thức này còn được gọi là phương pháp phân cụm “láng giềng gần nhất” (“nearest neighbour). yxST y Tx −=− ∈∈Smin • Phương thức kết nối toàn bộ (Complete Linkage Method): Độ tương tự giữa 2 phân cụm S và T được tính toán dựa trên khoảng cách lớn nhất (maximal) giữa các thành phần thuộc vào các phân cụm tương ứng. Phương thức này còn được gọi là phương pháp phân cụm “láng giềng xa nhất” (“furthest neighbour”). yxST y Tx −=− ∈∈Smax • Phương thức kết nối trung bình (Average Linkage Method): Độ tương tự giữa 2 phân cụm S và T được tính toán dựa trên khoảng cách trung bình (average) giữa các thành phần của các phân cụm tương ứng. Phương thức này xét tất cả các cặp khoảng cách các đối tượng trong các 2 phân cụm. Phương thức này còn được gọi là UPGMA (Unweighter Pair-Group Method using Arithmetic averages ) TS yx ST y Tx . S ∑ ∈∈ −=− Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 32 - Karypis [13] đã phản đối các phương thức trên vì cho rằng chúng sử dụng một mô hình tĩnh của các liên kết và gần gũi của dữ liệu, và đã đưa ra một mô hình động để tránh được những vấn đề trên. Hệ thống đó được gọi là CHAMELEON, chỉ gộp 2 phân cụm nếu sự liên kết và gần gũi của các phân cụm là có quan hệ mật thiết với sự liên kết và gần gũi bên trong các phân cụm. Các kỹ thuật chất đống thường sử dụng thời gian cỡ Ω(n2) vì đặc trưng của nó là xem xét tất cả các cặp phân cụm có thể. Hệ thống Phân tán/Tập hợp (Scatter/Gather) được giới thiệu trong cuốn Cutting [15], đã sử dụng một nhóm tích tụ trung bình để tìm kiếm các phân cụm hạt nhân (seed) để sử dụng cho thuật toán chia phân cụm. Tuy nhiên, để tránh thời gian chạy bình phương, họ chỉ sử dụng nó với một ví dụ nhỏ của các tài liệu để phân cụm. Ngoài ra, phương thức trung bình nhóm đã được giới thiệu trong Steinbach [4] được coi là tốt hơn hầu hết các phương thức đo độ tương tự khác do tính ổn định của nó. b, Phương pháp phân cụm chia xẻ cấp bậc Những phương thức này làm việc từ trên xuống dưới, bắt đầu với việc coi toàn bộ các tập dữ liệu là một phân cụm và tại mỗi bước lại phân chia một phân cụm cho đến khi chỉ còn những phân cụm đơn của các đối tượng riêng lẻ còn lại. Chúng thường khác nhau bởi 2 điểm: (1) phân cụm nào được phân chia kế tiếp và (2) làm thể nào để phân chia. Thường thì một tìm kiếm toàn diện được thực hiện để tìm ra phân cụm để phân tách dựa trên một vài tiêu chuẩn khác nhau. Một cách đơn giản hơn có thể được sử dụng đó là chọn phân cụm lớn nhất để chia tách, phân cụm có độ tương tự trung bình ít nhất hoặc sử dụng một tiêu chuẩn dựa trên cả kích cỡ và độ tương tự trung bình. Trong Steinbach [4] đã làm một thí nghiệm dựa trên những chiến thuật này và phát hiện ra rằng sự khác nhau giữa chúng là rất nhỏ, do đó họ đã sắp xếp lại bằng việc chia nhỏ phân cụm lớn nhất còn lại. Chi nhỏ một phân cụm cần đưa ra quyết định xem những đối tượng nào được đưa vào phân cụm con. Một phương pháp được dùng để tìm 2 phân cụm con sử dụng k-means trả lại kết quả là một kỹ thuật lai ghép được gọi là kỹ thuật chia cắt k-means (bisecting k-means) [4]. Cũng có một cách khác dựa trên thống kê được sử dụng bằng thuật toán ITERATE [18], tuy nhiên, không cần thiết phải Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 33 - chia một phân cụm thành 2 phân cụm con, chúng ta có thể chia nó thành nhiều phân cụm con, tùy theo kết cấu của các đối tượng. 2.4.2. Phân cụm bằng cách phân mảnh Lớp thuật toán phân cụm này làm việc bằng cách nhận ra các phân cụm tiềm năng cùng một lúc trong khi lặp lại việc cập nhật các phân cụm để làm tối ưu một vài chức năng. Lớp các thuật toán nổi tiếng của nó là thuật toán K-means và các biến thể của nó. K-means bắt đầu bằng việc chọn lựa ngẫu nhiên k phân cụm hạt nhân, sau đó đưa các đối tượng vào phân cụm có ý nghĩa gần nó nhất. Thuật toán lặp lại việc tính toán ý nghĩa của các phân cụm và cấp độ thành viên của các đối tượng mới. Quá trình xử lý tiếp tục cho đến một số lần lặp nhất định hoặc khi không còn sự thay đổi nào được phát hiện trong ý nghĩa của các phân cụm [17]. Các thuật toán K-means có kích cỡ O(nkT) trong đó T là số lượng vòng lặp. Dù sao, một nhược điểm chính của K-means là nó giả định một cấu trúc phân cụm cầu và không thể được áp dụng với các miền dữ liệu mà các cấu trúc phân cụm không phải là hình cầu. Một biến thể của K-means cho phép sự chồng lặp của các phân cụm đó là C-means mờ (FCM: Fuzzy C-means). Thay vì có các quan hệ thành viên kiểu nhị phân giữa các đối tượng và các phân cụm tiêu biểu, FCM cho phép các cấp độ khác nhau của cấp độ thành viên [17]. Krishnapuram [8] đã đưa ra một phiên bản đã chỉnh sửa của FCM được coi là Fuzzy C-Medoids (FCMdd) trong đó các ý nghĩa được thay bằng các ngữ cảnh. Thuật toán này tương đối nhanh và có cỡ là O(n2) và có cường độ hoạt động nhanh hơn FCM. Do sự lựa chọn ngẫu nhiên của các phân cụm hạt nhân những thuật toán này, chúng đối lập với phân cụm có thứ bậc. Do đó kết quả của các lần chạy của thuật toán là không thực sự ổn định. Một vài phương pháp đã được cải tiến bằng cách tìm ra các phân cụm hạt nhân ban đầu “tốt” sau đó mới sử dụng các thuật toán này. Có một ví dụ rất hay trong hệ thống Phân chia/Thu thập [15]. Có một cách tiếp cận gộp cả việc phân cụm phân mảnh và phân cụm lai ghép đó là thuật toán chia cách K-means (Bisecting K-means) đã nói ở phần trước. Thuật toán này là một thuật toán phân chia trong đó việc phân chia phân cụm sử dụng K-means để tìm kiếm 2 phân cụm con. Trong Steinbach đã chỉ ra Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 34 - rằng hiệu suất của thuật toán Bisecting K-means là tuyệt vời so với K-means bình thường cũng như UPGMA [4] Cần phải chú ý rằng một đặc trưng quan trọng của các thuật toán có thứ bậc là hầu hết đều có cập nhật theo tính tăng và các đối tượng mới có thể được đưa vào các phân cụm liên quan rất dễ dàng bằng việc lần theo một đường dẫn nào đó tới vị trí thích hợp. STC [5] và DC- tree [24] là hai ví dụ về các thuật toán này. Nói theo cách khác các thuật toán phân chia đồng loạt thường yêu cầu việc cập nhật đồng loạt về ý nghĩa của các phân cụm và thậm chí là các đối tượng thành viên. Việc cập nhật có tính tăng là rất cần thiết với các ứng dụng hoạt động on-line. 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 ∑ ∑ ∈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 G∑ ∑ ∈ δ hoặc cực đại hóa ),( ii Dd Ddi G∑ ∑ ∈ ρ 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 G∑∑ ∈ δ hoặc cực đại hóa ),( ii Dd Ddi G∑ ∑ ∈ ρ . 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ó Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 35 - 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. 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 2.5. Các yêu cầu đối với các thuật toán phân cụm Web Trong các thảo luận trước đó về các thuật toán phân cụm việc cần phải nhận ra các yêu cầu cho các thuật toán phân cụm tài liệu là cần thiết, việc này sẽ giúp chúng ta thiết kế ra các giải pháp hiệu quả và thiết thực hơn hướng tới các yêu cầu này. Tiếp đây là một danh sách của các yêu cầu này. 2.5.1. Tách các thông tin đặc trưng Vấn đề cốt lõi của bất cứ vấn đề phân cụm nào nằm hầu hết ở việc lựa chọn các tập đại diện của các đặc trưng của mô hình dữ liệu. Tập các đặc trưng được tách ra cần phải có đủ thông tin để nó có thể biểu diễn dữ liệu thực sự đang được phân tích. Ngược lại, dù thuật toán tốt đến mấy, nó sẽ vô dụng nếu như sử dụng những đặc trưng không chứa thông tin. Hơn nữa, việc làm giảm số lượng đặc trưng là rất quan trọng vì số chiều của không gian đặc trưng luôn có tác động đến hiệu suất của thuật toán. Một so sánh được hoàn thành bởi Yang và Pedersen [20] về hiệu quả của các phương pháp tách đặc trưng trong việc chia loại văn bản đã chỉ ra rằng phương pháp ngưỡng tần suất xuất hiện tài liệu (DF) cho những kết quả tốt hơn các phương thức khác và cũng cần ít các xử lý tính toán hơn. Hơn nữa, như đã đề cập ở trên, Wong và Fu [24] đã chỉ ra rằng họ có thể làm giảm số lượng từ đại diện bằng việc chỉ chọn các từ có ý nghĩa trong tập tài liệu. Mô hình tài liệu cũng thực sự rất quan trọng. Hầu hều các mô hình hay được sử dụng đều dựa trên các từ khác nhau được tách lọc từ tập tất cả các tài liệu và tính toán tần suất xuất hiện của từ cũng như tần suất xuất hiện của tài liệu như đã nói ở phần trước. Một mô hình tài liệu khác là mô hình dựa trên cụm từ, Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 36 - như mô hình được Zamir và Eztioni [5] đưa ra trong đó chúng tìm kiếm các cụm từ hậu tố có cùng điểm chung trong tài liệu sử dụng cấu trúc cây hậu tố. 2.5.2. Phân cụm chồng lặp Với tập dữ liệu bất kỳ, đặc biệt là trong lĩnh vực web, sẽ có xu hướng chứa một hoặc nhiều chủ đề. Khi phân cụm tài liệu, việc đưa những tài liệu vào các phân cụm liên quan với nó là cần thiết, điều này có nghĩa là vài tài liệu có thể thuộc vào nhiều hơn một phân cụm. Một mô hình phân cụm chồng lặp cho phép việc phân cụm tài liệu với nhiều chủ đề này. Có rất ít thuật toán cho phép phân cụm chồng lặp trong đó có phân cụm mờ [8] và cây hậu tố [5]. Trong vài trường hợp nếu việc mỗi tài liệu bắt buộc phải thuộc một phân cụm, một thuật toán không chồng lặp sẽ được sử dụng hoặc một tập của các phân cụm độc lập có thể được tạo ra bởi phân cụm mờ sau khi làm rõ các mối liên hệ giữa các phân cụm. 2.5.3. Hiệu suất Trong lĩnh vực web, mỗi một câu lệnh tìm kiếm có thể trả về hàng trăm và thỉnh thoảng là hàng nghìn trang web. Việc phân cụm các kết quả này trong một thời gian chấp nhận được là rất cần thiết. Cần phải chú ý rằng một vài hệ thống đã giới thiệu chỉ phân cụm trên các đoạn tin được trả lại trên hầu hết các máy tìm kiếm chứ không phải toàn bộ trang web [5]. Đây là một chiến thuật hợp lý trong việc phân cụm kết quả tìm kiếm nhanh nhưng nó không chấp nhận được với phân cụm tài liệu vì các đoạn tin không cung cấp đầy đủ thông tin về nội dung thực sự của những tài liệu này. Một thuật toán phân cụm online nên có khả năng hoàn thành trong thời gian tuyến tính nếu có thể. Một thuật toán offline thường hướng tới việc đưa ra các phân cụm có chất lượng cao hơn. 2.5.4. Khả năng khử nhiễu Một vấn đề có thể xảy ra với nhiều thuật toán phân cụm đó là sự xuất hiện của nhiễu và các dữ liệu thừa. Một thuật toán phân cụm tốt phải có khả năng giải quyết những kiểu nhiễu này và đưa ra các phân cụm có chất lượng cao và không bị ảnh hưởng bởi nhiễu. Trong phân cụm có thứ bậc, ví dụ các tính toán khoảng cách láng giềng gần nhất và láng giềng xa nhất, rất nhạy cảm với các dữ Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 37 - liệu thừa do đó không nên được sử dụng nếu có thể. Phương thức trung bình kết nối là thích hợp nhất với dữ liệu bị nhiễu. 2.5.5. Tính tăng Một đặc trưng rất đáng quan tâm trong các lĩnh vực như web đó là khả năng cập nhật phân cụm có tính tăng. Những tài liệu mới cần phải được đưa vào các phân cụm tương ứng mà không phải phân cụm lại toàn bộ tập tài liệu. Những tài liệu đã được chỉnh sửa nên được xử lý lại và đưa đến các phân cụm tương ứng nếu có thể. Thật đáng để nhớ rằng tính tăng càng hiệu quả thì hiệu suất cũng được cải thiện. 2.5.6. Việc biểu diễn kết quả Một thuật toán phân cụm là tốt nếu nó có khả năng biểu diễn một sự mô tả của các phân cụm mà nó đưa ra ngắn gọn và chính xác với người sử dụng. Các tổng kết của phân cụm nên có đủ tiêu biểu về nội dung tương ứng để người sử dụng có thể đưa ra quyết định nhanh xem phân cụm nào mà họ cảm thấy quan tâm. 2.6. Bài toán tách từ tự động tiếng Việt Đối với tiếng Anh, ta tách từ dựa vào khoảng trắng. Tuy nhiên đối với tiếng Việt, công việc này tương đối khó khăn. Cấu trúc tiếng Việt rất phức tạp, không chỉ đơn thuần dựa vào khoảng trắng để tách từ. Hiện nay có rất nhiều công cụ để tách từ tiếng Việt, mỗi phương pháp có ưu, khuyết điểm riêng và tất nhiên, chưa thể coi rằng là phương pháp tách từ nào là tốt nhất. Phần này trình bày một vài phương pháp tách từ tiếng Việt. Nhưng trước đó chúng ta sẽ xem xét một số khó khăn trong phân cụm trang Web tiếng Việt. 2.6.1. Một số khó khăn trong phân cụm trang Web tiếng Việt Hiện nay, chúng ta đã quen thuộc với rất nhiều công cụ hỗ trợ việc tìm kiếm thông tin như Google, Yahoo Search, AltaVista, ... Tuy nhiên, đây là công cụ của người nước ngoài nên chúng chỉ giải quyết tốt đối với các yêu cầu của họ. Chúng ta cũng có một số công cụ hỗ trợ tìm kiếm thông tin tiếng Việt như: Vinaseek, Netnam, ... Các công cụ này cũng tách từ chủ yếu dựa vào khoảng Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 38 - trắng nên việc tìm kiếm cũng chưa được cải thiện. Nhìn chung, để xây dựng một hệ thống tìm kiếm thông tin Tiếng Việt, chúng ta gặp khó khăn trong việc tách từ Tiếng Việt và xác định bảng mã tiếng Việt. Đồng thời đó cũng chính là khó khăn trong việc phân cụm các tài liệu bằng tiếng Việt vì bước đầu tiên của phân cụm cũng chính là tách từ tiếng Việt [1]. Vấn đề bảng mã Tiếng Việt Không như tiếng Anh, tiếng Việt có rất nhiều bảng mã đòi hỏi phải xử lý. Một số công cụ tìm kiếm tiếng Việt hỗ trợ bảng mã rất tốt như Vinaseek, hỗ trợ mọi bảng mã (VNI, TCVN3, ViQR, ...) Khó khăn trong tách từ Tiếng Việt Có thể nói tách từ là giai đoạn khó khăn nhất khi xây dựng một hệ tìm kiếm thông tin Tiếng Việt và phân cụm tài liệu Tiếng việt. Đối với tiếng Anh, việc xác định từ chỉ đơn giản dựa vào khoảng trắng để tách từ. Ví dụ, câu “I am a student” sẽ được tách thành 4 từ: I, am, a, student. Tuy nhiên, đối với Tiếng Việt, tách dựa vào khoảng trắng chỉ thu được các tiếng. Từ có thể được ghép từ một hay nhiều tiếng. Từ phải có ý 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