Xây dựng một hệ thống hỏi đáp tự động phục vụ tư vấn ghi danh trực tuyến

Trang 15 Chương 2. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÂU HỎI VÀ TÌM KIẾM THÔNG TIN TRONG HỆ THỐNG HỎI ĐÁP Ba bước quan trọng nhất trong hệ thống hỏi-đáp là: phân tích câu hỏi, tìm kiếm tài liệu có chứa câu trả lời và rút trích câu trả lời từ tài liệu. Do mục tiêu của luận văn là hướng đến một hệ thống hỏi-đáp cho một miền cụ thể là tư vấn ghi danh trực tuyến với các đặc thù trình bày trong chương mở đầu, không có nhu cầu rút trích thông tin câu trả lời từ tài liệu, nên chúng tôi trình bày trong chương này hai nội dung chính là các phương pháp phân tích câu hỏi và các phương pháp tìm kiếm thông tin. Hệ thống hỏi-đáp phục vụ tư vấn ghi danh trực tuyến có hai yếu tố quan trọng nhất là làm thế nào rút trích thông tin có ý nghĩa nhất từ câu hỏi và tìm kiếm câu trả lời như thế nào. Vì vậy, chúng tôi đề cập trong chương này 2 phương pháp chính khi phân tích câu hỏi và những đặc trưng riêng trong việc phân tích câu hỏi tiếng Việt. Tìm kiếm thông tin là lĩnh vực được nghiên cứu rộng rãi, áp dụng trong nhiều lĩnh vực khác nhau. Phương pháp phổ biến nhất là mô hình không gian vector và phương pháp trọng số tf-idf, sẽ được trình bày chi tiết trong chương này. Thêm vào đó, gom cụm dữ liệu trước khi tìm kiếm sẽ làm tăng hiệu suất hệ thống, vì vậy trong phần trình bày này, chúng tôi trình bày các phương pháp gom cụm văn bản tiêu biểu. 2.1 Phương pháp phân tích câu hỏi Phân tích câu hỏi đóng vai trò quan trọng trong bất kỳ loại hình hệ thống hỏi- đáp nào. Trong giai đoạn này, câu hỏi được phân tích và xử lý để trích lọc càng Trang 16 nhiều thông tin càng tốt để có thể được sử dụng trong giai đoạn tìm kiếm dữ liệu sau này. Có 2 phương pháp phân tích câu hỏi, cũng được xem như 2 phương pháp của hệ thống hỏi-đáp. Đó là phương pháp nông và phương pháp sâu. 2.1.1 Phương pháp nông (Shallow Method) Một số phương pháp QA sử dụng các kỹ thuật dựa trên từ khóa để xác định vị trí các đoạn và các câu từ các tài liệu được trả về bởi giai đoạn tìm kiếm, và sau đó lọc ra câu trả lời dựa trên sự hiện diện của loại câu trả lời trong văn bản được trả về đó. Sau đó một chiến lược xếp hạng được thực hiện, dựa trên các đặc điểm cú pháp thứ tự từ hoặc vị trí từ và sự tương tự với câu truy vấn. Khi sử dụng các tập dữ liệu lớn và các phương pháp loại bỏ dữ liệu dư thừa tốt, một số hệ thống sử dụng các mẫu để tìm ra câu trả lời cuối cùng với hy vọng rằng các câu trả lời chỉ là một khuôn mẫu của câu hỏi. Ví dụ, nếu người dùng hỏi "What is a dog?", hệ thống sẽ phát hiện các chuỗi con "What is a X" và tìm các tài liệu mà bắt đầu với "X is a Y". Điều này thường hoạt động tốt các câu hỏi đơn giản như hỏi về họ tên, ngày tháng, địa điểm, và số lượng. 2.1.2 Phương pháp sâu (Deep Method) Tuy nhiên, trong trường hợp các kỹ thuật từ khóa hay kỹ thuật sử dụng khuôn mẫu không hiệu quả, thì các kỹ thuật xử lý cú pháp, ngữ nghĩa và ngữ cảnh phức tạp hơn phải được thực hiện để trích xuất hoặc xây dựng các câu trả lời. Những phương pháp này có thể bao gồm nhận dạng các thực thể có tên (named- entity regconition), phát hiện mối quan hệ, sử dụng phương pháp suy luận... Các hệ thống này cũng thường sử dụng những tri thức có thể được tìm thấy trong các ontology như Wordnet [8] hoặc SUMO [28]. Những loại câu truy vấn phức tạp hơn như các câu hỏi “Tại sao” hoặc các câu hỏi “như thế nào”, câu hỏi phân cấp, câu hỏi nhập nhằng về nghĩa…Tất cả các câu hỏi phức tạp này sẽ cần những phân tích sâu hơn để có thể hiểu chúng. Các Trang 17 đoạn văn bản phức tạp và nhập nhằng về nghĩa cần có các kỹ thuật xử lý ngôn ngữ tự nhiên để có thể hiểu chúng. Phương pháp thống kê cũng được xem là một phương pháp sâu. Phương pháp này đưa ra các mô đun xử lý câu hỏi và rút trích câu trả lời dựa trên thống kê, chẳng hạn như trong [15] tác giả sử dụng phương pháp thống kê để phân lớp loại câu hỏi và câu trả lời. Nhiều công cụ xử lý ngôn ngữ tự nhiên cấp độ thấp được sử dụng, chẳng hạn như là gán nhãn từ loại, phân tích cú pháp, phát hiện các thực thể có tên, xác định ranh giới câu và tìm kiếm tài liệu đã có sẵn như các ứng dụng xác suất. 2.2 Vấn đề phân tích câu hỏi trong ngôn ngữ tiếng Việt. Việc phân tích câu hỏi bằng ngôn ngữ tự nhiên phụ thuộc rất nhiều vào đặc trưng ngôn ngữ của từng ngôn ngữ khác nhau. Khi phân tích câu hỏi tiếng Việt, khác với các câu hỏi tiếng Anh, chúng ta phải giải quyết: ¾ Xác định ranh giới giữa các từ trong câu. Đối với tiếng Anh khoảng trắng chính là ranh giới phân biệt các từ ngược lại tiếng Việt thì khoảng trắng không phải là ranh giới để xác định các từ mà chỉ là ranh giới để xác định các tiếng. ¾ Có quá nhiều từ mà mật độ xuất hiện cao nhưng không mang ý nghĩa cụ thể nào mà chỉ là những từ nối, từ đệm hoặc chỉ mang sắc thái biểu cảm như những từ láy. Những từ này cần phải được xác định và loại bỏ ra khỏi tập các mục từ. Nó giống như hư từ (stopword) trong tiếng Anh. ¾ Chính tả tiếng Việt còn một số điểm chưa thống nhất như sử dụng "y" hay "i" ( ví dụ "quý" hay "quí" ), cách bỏ dấu ( "lựơng" hay "lượng" ), cách viết hoa tên riêng( "Khoa học Tự nhiên" hay "Khoa Học Tự Nhiên")... gây khó khăn trong việc phân tích câu hỏi và tìm kiếm câu trả lời. ¾ Tồn tại nhiều bảng mã tiếng Việt đòi hỏi khả năng xử lý tài liệu ở các bảng mã khác nhau. Cách giải quyết là đưa tất cả về bảng mã chuẩn của hệ thống. Trang 18 ¾ Sự phong phú về nghĩa của một từ (từ đa nghĩa). Một từ có thể có nhiều nghĩa khác nhau trong những ngữ cảnh khác nhau nên việc tìm kiếm và rút trích câu hỏi khó có được kết quả với độ chính xác cao. ¾ Từ đồng nghĩa hoặc từ gần nghĩa: có nhiều từ khác nhau nhưng lại có cùng ý nghĩa. Do đó, việc tìm kiếm câu trả lời theo từ khoá thường không tìm thấy câu trả lời chứa từ đồng nghĩa hoặc gần nghĩa với các từ trong câu hỏi. Vì vậy, việc tìm kiếm câu trả lời cho ra kết quả không tối ưu. ¾ Các văn bản có nội dung chính là một vấn đề cụ thể, một đề tài nghiên cứu khoa học nhưng đôi khi trọng số của các từ chuyên môn này thấp so với toàn tập tài liệu. Vì vậy, một số thuật toán tính trọng số bỏ sót những trường hợp như vậy. Kết quả là các từ chuyên môn đó không được lập chỉ mục. Chính vì những đặc điểm rất riêng của tiếng Việt nên việc phân tích câu hỏi tiếng Việt gặp nhiều khó khăn. Các công cụ phân tích ngôn ngữ tiếng Việt cũng như các tài nguyên ngôn ngữ học phục vụ cho quá trình xử lý còn chưa đầy đủ hoặc đang hoàn thiện [11], điều này ảnh hưởng rất nhiều đến các hệ thống hỏi-đáp tiếng Việt. 2.3 Tìm kiếm thông tin Tìm kiếm thông tin (Information Retrieval (IR)) đã trở thành một lĩnh vực quan trọng trong hầu hết các nghiên cứu khi mà khối lượng dữ liệu ngày càng gia tăng, đặc biệt là sự phát triển của Internet. Để tìm kiếm thông tin có hiệu quả, các tài liệu thường được chuyển đổi thành các cách biểu diễn tài liệu thích hợp. Có rất nhiều phương pháp khác nhau được đề xuất, được tổng hợp như sau: - Các mô hình lý thuyết tập hợp: Các phương pháp này biểu diễn các tài liệu thành một tập hợp các từ và các cụm từ. Tính tương tự giữa các tài liệu được rút ra từ tập hợp các toán tử của lý thuyết tập hợp trên các tập hợp này. Các mô hình tiêu biểu như: Mô hình Boolean chuẩn (Standard Trang 19 Boolean Model), mô hình Boolean mở rộng (Extended Boolean Model), mô hình tìm kiếm mờ (Fuzzy Retrieval). - Các mô hình đại số: Các phương pháp này biểu diễn các tài liệu và truy vấn thành các vector, ma trận hoặc các bộ dữ liệu. Tính tương tự giữa vector truy vấn và vector tài liệu được biểu diễn như một đại lượng vô hướng. Các mô hình tiêu biểu như: Mô hình không gian vector (Vector Space Model), mô hình không gian vector tổng quát (Generalized Vector Space Model), mô hình Boolean mở rộng (Extended Boolean Model) , mô hình không gian vector dựa trên chủ đề (Enhanced Topic-based Vector Space Model), mô hình chỉ mục ngữ nghĩa ngầm (Latent Semantic Indexing). - Các mô hình xác suất: Mô hình này coi việc tìm kiếm tài liệu như là một suy luận có tính xác suất. Tính tương tự được xem như là xác suất mà một tài liệu liên quan đến một truy vấn đã cho. Lý thuyết xác suất thường được sử dụng trong các mô hình này là xác suất Bayes. Các mô hình tiêu biểu: Tìm kiếm độc lập nhị phân (Binary Independence Retrieval), mô hình tương quan xác suất (Probabilistic Relevance Model), mô hình ngôn ngữ (Language Model)… Chúng tôi xin đề cập ở đây một phương pháp tương đối phổ biến là mô hình không gian vector (vector space model). 2.4 Mô hình không gian vector (Vector Space Model) Mô hình không gian vector là mô hình đại số biểu diễn cho các tài liệu trong quá trình tìm kiếm như là vector của các định danh (cụ thể đối với văn bản thì nó là từ, cụm từ). Một tài liệu được biểu diễn như một vector. Mỗi chiều của vector tương ứng với một mục từ (term). Mục từ có thể là một từ đơn hay một cụm từ. Nếu mục từ này xuất hiện trong tài liệu thì giá trị của nó trong vector đặc trưng là khác 0. Một phương pháp nổi tiếng nhất trong mô hình không gian vector dùng để xác định giá trị các cụm từ trong vector đặc trưng là phương pháp trọng số tf-idf. Trang 20 2.4.1 Phương pháp trọng số tf-idf Cho một tập các tài liệu D, vector của một tài liệu d thuộc tập D được tính như sau: Trong đó: là trọng số của mục từ t Trong đó: : Tần suất xuất hiện của mục từ t trong tài liệu d, trọng số cục bộ. : Nghịch đảo tần suất, trọng số toàn cục, trong đó là tổng số tài liệu trong tập tài liệu, là số lượng các tài liệu chứa mục từ t. Phương pháp trọng số tf-idf đánh giá mức độ quan trọng của mục từ xét về mặt tòan cục kết hợp với trong số cục bộ của cụm từ trong tài liệu. Những từ thường xuất hiện trong một tài liệu nhưng ít xuất hiện trong tòan bộ tập tài liệu thì có trọng số cao. 2.4.2 Xác định độ tương tự giữa hai tài liệu Để xét xem hai tài liệu có tương tự với nhau hay không, phương pháp vector sử dụng độ đo góc giữa hai vector. Độ đo này càng lớn thì xem như độ tương tự càng cao. Trang 21 Trong đó: : Vector đặc trưng của hai tài liệu di : Độ dài vector đặc trưng của tài liệu di 2.4.3 Hạn chế của mô hình vector - Các tài liệu dài sẽ được biểu diễn không tốt vì chúng có một giá trị độ tương tự không tốt (giá trị tích vô hướng nhỏ và kích thước lớn, công thức phần 2.4.2). - Từ khóa dùng để tìm kiếm phải khớp chính xác với mục từ của tài liệu, ngay cả chuỗi con của mục từ cũng không được. - Thiếu ngữ nghĩa, có nghĩa là các tài liệu cùng ngữ cảnh nhưng khác nhau về từ vựng cũng xem như không khớp với nhau. - Thứ tự các mục từ không còn trong vector đặc trưng. 2.4.4 Chuẩn hóa trọng số tf-idf Do bởi hạn chế thứ nhất nêu trên, nên người ta tiến hành chuẩn hóa trọng số tf-idf sao cho nó không còn bị ảnh hưởng bởi chiều dài của tài liệu. Có rất nhiều phương pháp để chuẩn hóa, ví dụ: Với: là tần suất xuất hiện của mục từ t trong tài liệu d, là tổng tần suất xuất hiện của tất cả các mục từ trong tài liệu d. 2.5 Phương pháp gom cụm dữ liệu Tìm kiếm thông tin trong một tập hợp vô cùng lớn các tài liệu mất rất nhiều thời gian tìm kiếm. Chính vì vậy, các nghiên cứu tập trung vào việc làm giảm không gian tìm kiếm bằng cách gom cụm các tài liệu liên quan lại với nhau, hệ thống chỉ tìm kiếm tài liệu trong cùng một nhóm. Như vậy không gian tìm kiếm sẽ giảm đi rất nhiều. Trang 22 Gom cụm dữ liệu hay còn gọi là phân cụm, phân vùng dữ liệu là phương pháp phân một tập các ứng viên vào các cụm. Đây là phương pháp học không giám sát. Gom cụm dữ liệu được ứng dụng trong rất nhiều lĩnh vực khác nhau như là học máy, khai mỏ dữ liệu, xử lý ảnh… Thuật toán K-means là phương pháp được sử dụng nhiều nhất trong hướng tiếp cận phân nhóm phân hoạch (Partitional clustering). Thuật toán này có độ phức tạp thấp O(tkn) với t là số lần lặp, k là số cụm, n là số đối tượng sẽ gom cụm. Tư tưởng chính của thuật toán K-means [19] là gán mỗi ứng viên vào cụm có tâm cụm gần nó nhất, trong đó tâm cụm là giá trị trung bình của tất cả các đối tượng trong cụm. Với mục tiêu cải thiện hiệu quả thuật toán, có khá nhiều thuật toán khác như là: thuật toán k-medoids [14], thuật toán CLARANS [22], thuật toán DBSCAN [7]... Thuật toán k-medoids [14], thay vì lấy giá trị trung bình của các đối tượng trong cụm làm tâm như K-means, thuật toán này lấy một đối tượng trong cụm làm tâm của cụm (gọi là đối tượng tâm). Thuật toán này vẫn dựa trên nguyên tắc làm cực tiểu sự khác nhau giữa các đối tượng trong cùng một cụm. Ý tưởng chính của k- medoids là chọn ngẫu nhiên k đối tượng vào k cụm, coi mỗi đối tượng này là tâm của cụm. Phân bổ các đối tượng còn lại vào cụm mà sự khác nhau của nó với đối tượng tâm của cụm là ít nhất. Sau đó lặp lại quá trình: Thay đổi đối tượng tâm của mỗi cụm sao cho chất lượng của cụm được cải thiện. Chất lượng của cụm được lượng giá bởi một hàm đo sự khác nhau giữa một đối tượng và đối tượng tâm của cụm chứa nó. Quá trình lặp cho đến khi không còn sự thay đổi nào về lực lượng cũng như hình dạng của các cụm. Thuật toán k-medoids mạnh hơn thuật toán k- means trong các trường hợp dữ liệu có nhiễu vì k-medoids chịu ảnh hưởng ít hơn của nhiễu và các giá trị chênh lệnh so với giá trị trung bình. Tuy nhiên, ứng dụng k- means là phương pháp đơn giản hơn. Thuật toán CLARANS (Clustering Large Applications based on RANdomized Search) [22] là một thuật toán phân cụm theo kiểu k-medoids. CLARANS phân cụm dựa trên việc tìm kiếm ngẫu nhiên các tập gồm k đối tượng để làm tâm của k Trang 23 cụm. Tại mỗi bước tìm kiếm sẽ xác định được độ tốt của nó và giữ lại kết quả tìm kiếm tốt nhất. Các tác giả đã thực hiện việc tìm kiếm và đánh giá độ tốt của phép tìm kiếm bằng cách xây dựng một đồ thị tìm kiếm [22]. Thuật toán CLARANS được đánh giá là hiệu quả trên cơ sở dữ liệu lớn. Tuy nhiên, nó cũng bộc lộ một số hạn chế, đó là CLARANS cần đưa cả cơ sở dữ liệu vào bộ nhớ trong và thời gian thực thi có nhiều trường hợp rất xấu, trường hợp tốt nhất là O(kn2) và trường hợp xấu nhất là O(nk). Thuật toán DBSCAN [7] được khẳng định qua thực nghiệm là tốt hơn các thuật toán khác. Cụ thể so với thuật toán CLARANS thì DBSCAN phát hiện ra các cụm bất kì nhiều hơn và hiệu quả cao hơn [7]. Trong trường hợp không có sử dụng cấu trúc chỉ mục thì phương pháp này có độ phức tạp là O(n2), có sử dụng cấu trúc chỉ mục là O(n.logn), nhưng phương pháp này chủ yếu áp dụng cho phân cụm các dữ liệu không gian. Một phương pháp khác trong hướng tiếp cận phân cấp (Hierarchical Clustering) khá phổ biến là HAC (Hierarchical Agglomerative Clustering). Ý tưởng của thuật toán này là kết hợp các cụm có khoảng cách gần nhau thành một cụm sau mỗi bước lặp. Thuật toán này có độ phức tạp O(n2). Đối với hệ thống hỏi-đáp cho diễn đàn tư vấn ghi danh trực tuyến, dữ liệu khá lớn, cần các phương pháp có độ phức tạp thấp và kết quả phân cụm là chấp nhận được. K-means và HAC là hai phương pháp có độ phức tạp thấp. Vì vậy, chúng tôi chọn trình bày chi tiết 2 phương pháp này. 2.5.1 Thuật toán K-Means Đây là thuật toán nổi tiếng và được sử dụng nhiều nhất. Thuật toán này có nhiều biến thể khác nhau nhưng được đưa ra đầu tiên bởi J.B MacQueen vào năm 1967 [19]. Đầu vào của thuật toán này là một tập gồm n mẫu và một số nguyên K. Cần phân n đối tượng này thành K cụm sao cho sự giống nhau giữa các mẫu trong cùng cụm là cao hơn là giữa các đối tượng khác cụm. Trang 24 Tư tưởng của thuật toán này như sau: Đầu tiên chọn ngẫu nhiên K mẫu, mỗi mẫu này coi như biểu diễn một cụm, như vậy lúc này trong mỗi cụm thì đối mẫu đó cũng là tâm của cụm (hay còn gọi là nhân). Các mẫu còn lại được gán vào một cụm nào đó trong K cụm đã có sao cho tổng khoảng cách từ mẫu đó đến tâm của nhóm là nhỏ nhất. Sau đó tính lại tâm cho các nhóm và lặp lại quá trình đó cho đến khi hàm tiêu chuẩn hội tụ. Hàm tiêu chuẩn được dùng phổ biến nhất là hàm tiêu chuẩn bình phương sai. Thuật toán này có thể áp dụng được đối với cơ sở dữ liệu đa chiều, nhưng để dễ minh họa chúng tôi mô tả thuật toán trên dữ liệu hai chiều. Thuật toán k-means được mô tả cụ thể như sau: Input: K, và dữ liệu về n mẫu của một cơ sở dữ liệu. Output: Một tập gồm K cụm sao cho cực tiểu về tổng bình phương sai. Thuật toán: - Bước 1: Chọn ngẫu nhiên K mẫu vào K cụm. Coi tâm của cụm chính là mẫu có trong cụm. - Bước 2: Tìm tâm mới của cụm. - Bước 3: Gán (gán lại) các mẫu vào từng cụm sao cho khoảng cách từ mẫu đó đến tâm của cụm đó là nhỏ nhất. - Bước 4: Nếu các cụm không có sự thay đổi nào sau khi thực hiện bước 3 thì chuyển sang bước 5, ngược lại sang bước 2. - Bước 5: Dừng thuật toán. Ví dụ: Giả sử trong không gian hai chiều, cho 12 điểm (n = 12) cần phân 12 điểm này thành hai cụm (k=2). Đầu tiên chọn hai điểm ngẫu nhiên vào hai cụm, giả sử chọn điểm (1,3) và điểm (9,4) (điểm có màu đỏ trên hình 2-1(a)). Coi điểm (1,3) là tâm của cụm 1 và điểm (9,4) là tâm của cụm hai. Tính toán khoảng cách từ các điểm khác đến hai điểm này và ta gán được các điểm còn lại này vào một trong hai cụm, những điểm có màu xanh lơ vào cụm 1, những điểm có màu Trang 25 xanh đậm vào cụm 2 (hình 2-1(b)). Hiệu chỉnh lại tâm của hai cụm, điểm màu đỏ trên hình 2-1(c) là tâm mới của hai cụm. Tính lại các khoảng cách các điểm đến tâm mới và gán lại các điểm này, hình 2-1(d). Tiếp tục hiệu chỉnh lại tâm của hai cụm. Cứ như thế lặp lại cho đến khi không còn sự thay đổi nữa thì dừng. Khi đó ta thu được kết quả của bài tóan. Hình 2-1: Ví dụ minh họa thuật toán k-means Dễ thấy độ phức tạp cuả thuật toán này là O(tKn). Trong đó n là số mẫu trong cơ sở dữ liệu, K là số cụm, t là số lần lặp. Thông thường t,K << n. Nên thuật toán này có hiệu quả tương đối với các cơ sở dữ liệu lớn. Thuật toán này có ưu điểm là rõ ràng, dễ dàng cài đặt. Nhưng nhược điểm của thuật toán này là phải chỉ ra số lượng cụm và yêu cầu cơ sở dữ liệu cần phân nhóm phải xác định được tâm. 2.5.2 Thuật toán HAC HAC (Hierarchical Agglomerative Clustering) là thuật toán phân cụm không giám sát (không cần biết trước số cụm cần phân vào) nhưng phải cung cấp điều kiện dừng. Trang 26 Hình 2-2: Thuật toán HAC Thuật toán HAC có thể tóm gọn như sau: Giả sử có N phần tử và ma trận khoảng cách N*N - Bước 1: Bắt đầu cho mỗi phần từ vào một phân vùng của nó. Nếu có N phần tử thì có N phân vùng khởi tạo - Bước 2: Tìm cặp phân vùng có khoảng cách nhỏ nhất và hợp lại thành một phân vùng. Lúc này số phân vùng đã giảm đi một - Bước 3: Tính khoảng cách giữa phân vùng mới với các phân vùng cũ còn lại - Bước 4: Lặp lại bước 2,3 cho đến khi chỉ còn lại một phân vùng hoặc thỏa mản điều kiện dừng nào đó Thuật toán HAC có 2 cách làm: - Agglomerative: Đi từ dãy các phần tử và ở mỗi bước gom nhóm các cặp phân vùng(có thể là một phần tử hay là một nhóm có nhiều phần tử đã gom nhóm vào) có khoảng cách giữa 2 phần tử là gần nhau nhất. Cứ như thế cho đến khi thỏa mãn điều kiện dừng hay chỉ còn lại 1 nhóm Trang 27 - Divisive: Cách này đi ngược lại với cách làm trên. Do mỗi phần tử có thể là một nhóm nên có 3 cách tính khoảng cách là: - Single Link: Là khoảng cách nhỏ nhất giữa bất cứ thành viên nào từ phân vùng này tới phân vùng kia - Complete Link: Là khoảng cách xa nhất giữa bất cứ thành viên nào từ phân vùng này tới phân vùng kia - Average Link: Kết hợp 2 cách trên *) Ưu điểm và khuyết điểm của HAC • Ưu điểm: - Dễ hiểu và dễ cài đặt • Khuyết điểm: - Chi phí tính toán có thể là O(n2) Kết luận Trong chương này, chúng tôi đã trình bày hai vấn đề chính là phân tích câu hỏi và tìm kiếm thông tin trong hệ thống hỏi-đáp. Đồng thời cũng trình bày những đặc trưng ngôn ngữ tiếng Việt khác với ngôn ngữ tiếng Anh đòi hỏi việc phân tích câu hỏi tiếng Việt phải chú ý giải quyết. Trong phần tìm kiếm thông tin, chúng tôi tập trung trình bày chi tiết mô hình không gian vector và hai phương pháp gom cụm phổ biến có độ phức tạp thấp là K-means và HAC. Chương 3. GIẢI PHÁP VÀ THỬ NGHIỆM HỆ THỐNG