Đề tài Web mining và xây dựng thử nghiệm ứng dụng web clustering

ăn, gặp phải nhiều vướng mắc như : các dữ liệu phải được sao ra nhiều bản (nếu được chiết suất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi),... Sẽ là quá cồng kềnh với một giải thuật khai phá dữ liệu nếu phải truy nhập vào toàn bộ nội dung của CSDL và làm những việc như trên. Vả lại, điều này cũng không cần thiết. Có rất nhiều giải thuật khai phá dữ liệu thực hiện trên những thống kê tóm tắt khá đơn giản của CSDL, khi mà toàn bộ thông tin trong CSDL là quá dư thừa đối với mục đích của việc khai phá dữ liệu. Bước tiếp theo là chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá để tìm được các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó (thường được biểu diễn dưới dạng luật xếp loại, cây quyết định, luật sản xuất, biểu thức hồi quy,...). Đặc điểm của các mẫu là phải mới (ít nhất là đối với hệ thống đó). Độ mới có thể được đo tương ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá trị hiện tại với các giá trị trước đó hoặc các giá trị mong muốn), hoặc bằng tri thức (mối liên hệ giữa các phương pháp tìm mới và phương pháp cũ như thế nào). Thường thì độ mới của mẫu được đánh giá bằng các hàm logic hoặc hàm đo độ mới, độ bất ngờ của mẫu. Ngoài ra, mẫu phải có khả năng sử dụng tiềm tàng. Các mẫu này sau khi được xử lý và diễn giải phải dẫn đến những hành động có ích nào đó được đánh giá bởi một hàm lợi ích. Ví dụ như trong dữ liệu các khoản vay, hàm lợi ích đánh giá khả năng tăng lợi nhuận từ các khoản vay. Mẫu khai thác được phải có giá trị đối với các dữ liệu mới với độ chính xác nào đó. Xác định nhiệm vụ Xác định dữ liệu liên quan Thu thập và tiền xử lý dữ liệu Dữ liệu trực tiếp Thống kê tóm tắt Giải thuật khai phá dữ liệu Mẫu Với các giải thuật và các nhiệm vụ của khai phá dữ liệu rất khác nhau, dạng của các mẫu chiết xuất được cũng rất đa dạng. Theo cách đơn giản nhất, sự phân tích cho ra kết quả chiết xuất là một báo cáo về một số loại (có thể bao gồm các phép đo mang tính thống kê về độ phù hợp của mô hình, các dữ liệu lạ...). Trong thực tế đầu ra phức tạp hơn nhiều. Mẫu chiết suất được có thể là một mô tả xu hướng, có thể dưới dạng văn bản, một đồ thị mô tả các mối quan hệ trong mô hình, cũng có thể là một hành động ví dụ như yêu cầu của người dùng làm gì với những gì khai thác được trong CSDL. Kỹ thuật khai phá dữ liệu thực chất không có gì mới. Nó là sự kế thừa, kết hợp và mở rộng của các kỹ thuật cơ bản đã được nghiên cứu từ trước như máy học, nhận dạng, thống kê (hồi quy, xếp loại, phân nhóm), các mô hình đồ thị, mạng Bayes, trí tuệ nhân tạo, thu thập tri thức hệ chuyên gia... Tuy nhiên, với sự kết hợp tài tình của khai phá dữ liệu, kỹ thuật này có ưu thế hơn hẳn các phương pháp trước đó, đem lại nhiều triển vọng trong việc ứng dụng phát triển nghiên cứu khoa học cũng như làm tăng mức lợi nhuận trong các hoạt động kinh doanh. 2. Nhiệm vụ chính của khai phá dữ liệu. Rõ ràng mục đích của khai phá dữ liệu là các tri thức chiết xuất được sẽ được sử dụng cho lợi ích cạnh tranh trên thương trường và các lợi ích trong nghiên cứu khoa học. Do đó, có thể coi mục đích của khai phá dữ liệu sẽ là mô tả (description) và dự đoán (prediction). Các mẫu mà khai phá dữ liệu phát hiện được nhằm vào các mục đích này. Dự đoán liên quan đến việc sử dụng các biến hoặc các trường trong CSDL để chiết xuất ra các mẫu là các dự đoán những giá trị chưa biết hoặc những gía trị trong tương lai của các biến đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Để đạt được hai mục đích này, nhiệm vụ chính của khai phá dữ liệu bao gồm như sau: Phân lớp (Classification) : Phân lớp là việc học một hàm ánh xạ (hay phân loại) một mẫu dữ liệu vào một trong số các lớp đã xác định. Hồi quy (Regression) : Hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Phân nhóm (Clustering): Là việc mô tả chung để tìm ra các tập xác định, các nhóm hay các loại để mô tả dữ liệu. Các nhóm có thể tách riêng nhau hoặc phân cấp hoặc gối lên nhau. Có nghĩa là mọt dữ liệu có thể vừa thuộc nhóm này, vừa thuộc nhóm kia. Tóm tắt (summarization) : Liên quan đến các phương pháp tìm kiếm một mô tả tóm tắt cho một tập con dữ liệu. Mô hình hoá phụ thuộc (Dependency Modeling): Bao gồm việc tìm kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa các biến. Các mô hình phụ thuộc tồn tại dưới hai mức : mức cấu trúc của mô hình xác định (thường ở dạng đồ hoạ) các biến nào là phụ thuộc cục bộ với nhau, mức định lượng của một mô hình xác định độ mạnh của sự phụ thuộc theo một thước đo nào đó. Phát hiện sự thay đổi và lạc hướng (Change and Deviation Detection) : Tập trung vào khai thác những thay đổi đáng kể nhất trong dữ liệu từ các giá trị chuẩn hoặc được đo trước đó. Những nhiệm vụ khác nhau này yêu cầu số lượng và các dạng thông tin rất khác nhau nên chúng thường ảnh hưởng đến việc thiết kế và chọn giải thuật khai phá dữ liệu khác nhau. 3. Các phương pháp khai phá dữ liệu Quá trình khai phá dữ liệu là quá trình phát hiện các mẫu trong đó, giải thuật khai phá dữ liệu tìm kiếm các mẫu đáng quan tâm theo dạng xác định như các luật, cây phân lớp, quy hồi, phân nhóm, ... Các thành phần của giải thuật khai phá dữ liệu Giải thuật khai phá dữ liệu bao gồm có ba thành phần chính như sau : biểu diễn mô hình, đánh giá mô hình, tìm kiếm mô hình. Biểu diễn mô hình : Mô hình được biểu diễn bằng một ngôn ngữ L để miêu tả các mẫu có thể khai thác được. Nếu sự mô tả quá bị hạn chế thì sẽ không thể học được hoặc sẽ không thể có các mẫu tạo ra được một mô hình chính xác cho dữ liệu. Vì vậy, việc quan trọng là người phân tích dữ liệu cần phải hiểu đầy đủ các giả thiết miêu tả. Một điều cũng khá quan trọng là người thiết kế giải thuật cần phải diễn tả được các giả thiết miêu tả nào được tạo ra bởi giải thuật nào. Khả năng miêu tả mô hình càng lớn thì càng làm tăng mức độ nguy hiểm và làm giảm đi khả năng dự đoán các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ càng trở nên phức tạp hơn và việc giải thích mô hình cũng khó khăn hơn. Mô hình ban đầu được xác định bằng cách kết hợp biến đầu ra (phụ thuộc) với các biến độc lập mà biến đầu ra phụ thuộc vào. Sau đó phải tìm những tham số mà bài toán cần tập trung giải quyết. Việc tìm kiếm mô hình sẽ đưa ra được một mô hình phù hợp với các tham số được xác định dựa trên dữ liệu (trong một số trường hợp, mô hình được xây dựng độc lập với dữ liệu trong khi đối với một số trường hợp khác thì mô hình và các tham số lại thay đổi để phù hợp với dữ liệu). Trong một số trường hợp, tập dữ liệu được chia thành tập dữ liệu học và tập dữ liệu thử. Tập dữ liệu học được sử dụng để làm cho các tham số của mô hình phù hợp với dữ liệu. Mô hình sau đó sẽ được đánh giá bằng cách đưa các dữ liệu thử vào mô hình và thay đổi lại các tham số cho phù hợp nếu cần. Mô hình lựa chọn có thể là phương pháp thống kê như SASS,..., một số giải thuật máy học, mạng nơron, suy diễn hương tình huống, các kỹ thuật phân lớp. Đánh giá mô hình: Đánh giá xem một mẫu có đáp ứng được các tiêu chuẩn của quá trình phát hiện tri thức hay không. Việc đánh giá độ chính xác dự đoán dựa trên đánh giá chéo (cross validation). Đánh giá chất lượng miêu tả liên quan đến độ chính xác dự đoán, độ mới, khả năng sử dụng, khả năng hiểu mô hình. Cả hai chuẩn thống kê và chuẩn logic đều có thể được sử dụng để đánh giá mô hình. Việc đánh giá mô hình được thực hiện qua kiểm tra dữ liệu (trong một số trường hợp kiểm tra với tất cả các dữ liệu, trong một số trường hợp khác kiểm tra với dữ liệu thử). Phương pháp tìm kiếm: Phương pháp tìm kiếm bao gồm 2 thành phần : tìm kiếm tham số và tìm kiếm mô hình. Trong tìm kiếm tham số, giải thuật cần tìm kiếm các tham số để tối ưu hoá các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một miêu tả mô hình đã định. Việc tìm kiếm không cần thiết đối với các bài toán khá đơn giản: các đánh giá tham số tối ưu có thể đạt được bằng các cách đơn giản hơn. Tìm kiếm mô hình xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số: miêu tả mô hình bị thay đổi tạo nên một họ các mô hình. Với mỗi một miêu tả mô hình, phương pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng của mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic vì kích thước của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng thể, hơn nữa các giải pháp đơn giản không dễ đạt được. 4. Một số bài toán chính đối với nghiên cứu về khai phá dữ liệu : Bài toán phân loại (classification) : tìm một ánh xạ từ một mẫu dữ liệu vào một trong các lớp có sẵn. Bài toán hồi quy (regression): tìm một ánh xạ hồi quy từ một mẫu dữ liệu vào một biến dự đoán có giá trị thực. Bài toán lập nhóm (clustering) : là việc mô tả chung để tìm ra tập xác định hữu hạn các nhóm hay các chủ đề là mô tả đặc trưng của dữ liệu. Bài toán lập tóm tắt (summarization): là việc tìm kiếm một mô tả chung tóm tắt cho một tập con dữ liệu CHƯƠNG III VĂN BẢN VÀ CÁC BÀI TOÁN XỬ LÝ VĂN BẢN Khái niệm Trong các dạng dữ liệu thường xuyên được sử dụng thì văn bản là một trong những dạng được dùng phổ biến nhất. Các văn bản có thể là các bài báo, các tài liệu kinh doanh, các thông tin kinh tế, các bài nghiên cứu khoa học. Nhìn chung, các loại dữ liệu văn bản thường được chia thành 2 loại: Dạng phi cấu trúc (unstructured): là dạng văn bản chúng ta sử dụng hằng ngày được thể hiện dưới dạng ngôn ngữ tự nhiên của con người và chúng không có một cấu trúc định dạng cụ thể nào. Dạng bán cấu trúc (semi-structured): đây là các loại văn bản không được lưu trữ dưới dạng các bản ghi chặt chẽ mà được tổ chức qua các đánh dấu văn bản để thể hiện nội dung chính của văn bản. Phương pháp biểu diễn văn bản bằng mô hình không gian vector (Vector Space Model) Cách biểu diễn văn bản thông dụng nhất là thông qua vector. Đây là một cách biểu diễn tương đối đơn giản và hiệu quả. Trước đây có nhiều bài báo nói rằng phương pháp này gây tốn kém chi phí lưu trữ và công sức xử lý, nhưng khi các phương pháp xử lý vector thưa được áp dụng thì các nhược điểm trên giảm đi rất nhiều. Theo mô hình này, mỗi văn bản được biểu diễn thành một vector. Mỗi thành phần của vector là một thuật ngữ riêng biệt trong tập văn bản gốc và được gán một giá trị là hàm f của từng thuật ngữ trong văn bản. văn bản 1 văn bản 2 văn bản 4 văn bản 3 Thuật ngữ 1 Thuật ngữ 2 Hình 1: Biểu diễn các vector văn bản trong không gian chỉ có 2 thuật ngữ Mô hình Boolean Một mô hình biểu diễn vector với hàm f cho ra giá trị rời rạc với duy nhất hai giá trị đúng và sai (true và false, hoặc 0 và 1) gọi là mô hình Boolean. Hàm f tương ứng với thuật ngữ ti sẽ cho ra giá trị đúng nếu và chỉ nếu thuật ngữ ti xuất hiện trong văn bản đó. Mô hình Boolean được định nghĩa như sau: Giả sử có một cơ sở dữ liệu gồm m văn bản, D = {d1, d2,… dm}. Mỗi văn bản được biểu diễn dưới dạng một vector gồm n thuật ngữ T = {t1, t2,…tn}. Gọi W = {wij} là ma trận trọng số, trong đó wij là giá trị trọng số của thuật ngữ ti trong văn bản dj. Mô hình Boolean là mô hình đơn giản nhất được xác định như sau[1]: Mô hình tần suất Trong mô hình tần suất, ma trận W = {wij} được xác định dựa trên tần số xuất hiện của thuật ngữ ti trong văn bản dj hoặc tần số xuất hiện của thuật ngữ ti trong toàn bộ cơ sở dữ liệu. a. Phương pháp dựa trên tần số thuật ngữ (TF – Term Frequency) Các giá trị wij được tính dựa trên tần số (hay số lần) xuất hiện của thuật ngữ trong văn bản. Gọi fij là số lần xuất hiện của thuật ngữ ti trong văn bản dj, khi đó wij được tính bởi một trong ba công thức: wij = fij wij = 1 + log(fij) wij = Trong phương pháp này, trọng số wij tỷ lệ thuận với số lần xuất hiện của thuật ngữ ti trong văn bản dj. Khi số lần xuất hiện thuật ngữ ti trong văn bản dj càng lớn thì điều đó có nghĩa là văn bản dj càng phụ thuộc vào thuật ngữ ti, hay nói cách khác thuật ngữ ti mang nhiều thông tin trong văn bản dj. Ví dụ, khi văn bản xuất hiện nhiều thuật ngữ máy tính, điều đó có nghĩa là văn bản đang xét chủ yếu liên quan đến lĩnh vực tin học. Nhưng suy luận trên không phải lúc nào cũng đúng. Một ví dụ điển hình là từ “và” xuất hiện nhiều trong hầu hết các văn bản, nhưng trên thực tế từ này lại không mang nhiều ý nghĩa như tần suất xuất hiện của nó. Một phương pháp khác ra đời khắc phục được nhược điểm của phương pháp TF, đó là phương pháp IDF. b. Phương pháp dựa trên nghịch đảo tần số văn bản (IDF – Inverse Document Frequency) Trong phương pháp này, giá trị wij được tính theo công thức sau: ở đó m là số lượng văn bản và hi là số văn bản mà thuật ngữ ti xuất hiện. Trọng số wij trong công thức này được tính dựa trên độ quan trọng của thuật ngữ ti trong văn bản dj. Nếu ti xuất hiện trong càng ít văn bản, điều đó có nghĩa là nếu nó xuất hiện trong dj thì trọng số của nó đối với văn bản dj càng lớn hay nó là điểm quan trọng để phân biệt văn bản dj với các văn bản khác và hàm lượng thông tin trong nó càng lớn. c. Phương pháp TF × IDF Phương pháp này là tổng hợp của hai phương pháp TF và IDF, giá trị của ma trận trọng số được tính như sau: Phương pháp này kết hợp được ưu điểm của cả hai phương pháp trên. Trọng số wij được tính bằng tần số xuất hiện của thuật ngữ ti trong văn bản dj và độ hiếm của thuật ngữ ti trong toàn bộ cơ sở dữ liệu. Phương pháp xử lý vector thưa Theo mô hình vector chuẩn, việc xử lý các phép toán trên vector sẽ phụ thuộc vào độ lớn của ma trận Wnm ở đó n là số lượng thuật ngữ hay số chiều của vector và m là số lượng văn bản có trong cơ sở dữ liệu. Trên thực tế, số lượng thuật ngữ và số văn bản có thể lên đến vài chục nghìn. Khi đó số lượng phần tử trong ma trận Wnm sẽ lên đến con số trăm triệu và việc lưu trữ ma trận Wnm sẽ tốn quá nhiều tài nguyên bộ nhớ đồng thời các phép toán trên các vector sẽ rất phức tạp. Để khắc phục vấn đề này có thể sử dụng kỹ thuật xử lý trên vector thưa thay vì việc lưu trữ và xử lý trên các vector chuẩn. Các điều kiện để có thể áp dụng phương pháp vector thưa: Các vector thực sự thưa: số phần tử có trọng số khác 0 nhỏ hơn rất nhiều so với số thuật ngữ trong cơ sở dữ liệu. Phép xử lý vector là đơn giản nhất: số vector cùng bị tác động trong một phép xử lý cơ bản là nhỏ nhất. Thường số vector bị tác động này được quy định tối đa là 3 hoặc 4. Trên thực tế, số thuật ngữ xuất hiện trong một văn bản thường dưới 1000. Đối với các văn bản dài và đa chủ đề thì số thuật ngữ xuất hiện có thể nhiều hơn. Trong khi đó, số lượng thuật ngữ có trong từ điển có thể lên đến con số 100,000 từ. Đây chính là điều kiện để áp dụng phương pháp vector thưa. Việc thỏa mãn điều kiện thứ hai còn phụ thuộc vào thuật toán được áp dụng cho quá trình xử lý văn bản. Một ví dụ biểu diễn vector thưa từ các vector chuẩn. Đối với vector chuẩn: wij Máy tính Internet Thịt gà Quần bò Cỏ Lông cừu d0(CNTT) 2 3 0 0 0 0 d1(Nông nghiệp) 0 0 4 0 1 1 d2(Công nghiệp) 0 0 0 6 0 2 d0 = (2, 3, 0, 0, 0, 0) d1 = (0, 0, 4, 0, 1, 1) d2 = (0, 0, 0, 6, 0, 2) Đối với vector thưa: d0 = ((1, 2), (2, 3)) d1 = ((3,4), (5,1), (6,1)) d2 = ((4,6), (6,2)) Kiểu phần tử của vector thưa có sự thay đổi so với vector chuẩn. Mỗi phần tử gồm hai giá trị là mã biểu diễn thuật ngữ và giá trị trọng số tương ứng với thuật ngữ đó. Phần tử (6, 2) trong văn bản d2 chỉ ra rằng thuật ngữ có mã 6 (“lông cừu”) có trọng số 2. 3. Các bài toán xử lý văn bản không có cấu trúc 3.1 Bài toán phân loại văn bản (Text Clustering) 3.1.1 Giới thiệu Bài toán : Cho một tập hợp các văn bản đã được người dùng phân loại bằng tay vào một số chủ đề có sẵn. Khi đưa vào một văn bản mới, yêu cầu hệ thống chỉ ra tên chủ đề phù hợp nhất với văn bản đó. Theo cách truyền thống, việc phân loại văn bản có thể thực hiện một cách thủ công, tức là đọc từng văn bản một và gán nó vào nhóm phù hợp. Cách thức này sẽ tốn nhiều thời gian và chi phí nếu như số lượng văn bản lớn. Do vậy, cần phải xây dựng các công cụ phân loại văn bản một cách tự động. Để xây dựng công cụ phận loại văn bản tự động người ta thường dùng các thuật toán học máy (Machine Learning). Tuy nhiên, còn có các thuật toán đặc biệt hơn dùng cho phân loại trong các lĩnh vực đặc thù. Một ví dụ điển hình là bài toán phân loại công văn giấy tờ. Hệ thống sẽ tìm ra đặc thù của văn bản một cách tương đối máy móc, cụ thể là khi tìm thấy ở lề trên bên trái có ký hiệu “NĐ” thì hệ thống sẽ phân văn bản đó vào nhóm “Nghị định”, tương tự như vậy với các ký hiệu “CV”, “QĐ” thì hệ thống sẽ phân văn bản này vào nhóm “Công văn”, và “Quyết định”. Thuật toán này tương đối hiệu quả song lại chỉ phù hợp cho các nhóm dữ liệu tương đối đặc thù. Khi phải làm việc với các văn bản ít đặc thù hơn thì cần phải xây dựng các thuật toán phân loại dựa trên nội dung của văn bản và so sánh độ phù hợp của chúng với các văn bản đã được phân loại bởi con người. Đây là tư tưởng chính của thuật toán học máy. Trong mô hình này, các văn bản đã được phân loại sẵn và hệ thống của chúng ta phải tìm cách để tách ra đặc thù của các văn bản thuộc mỗi nhóm riêng biệt. Tập văn bản mẫu dùng để huấn luyện gọi là tập huấn luyện (train set) hay tập mẫu (pattern set), quá trình phân loại văn bản bằng tay gọi là quá trình huấn luyện (training), còn quá trình máy tự tìm đặc thù của các nhóm gọi là quá trình học (learning). Sau khi máy đã học xong, người dùng sẽ đưa các văn bản mới vào và nhiệm vụ của máy là tìm ra xem văn bản đó phù hợp nhất với nhóm nào mà con người đã huấn luyện nó. Một trong những ứng dụng quan trọng nhất của phân loại văn bản là ứng dụng tìm kiếm văn bản. Từ tập dữ liệu đã được phân loại, các văn bản sẽ được đánh chỉ số đối với từng lớp tương ứng. Người dùng có thể xác định chủ đề mà mình muốn tìm thông qua các truy vấn. Một ứng dụng khác của phân loại văn bản là trong lĩnh vực hiểu văn bản. Phân loại văn bản có thể được dùng để lọc ra một số văn bản hoặc một phần văn bản mà không làm mất đi tính phong phú của ngôn ngữ tự nhiên. Trong phân loại văn bản, sự phụ thuộc của một văn bản vào một nhóm có thể là các giá trị rời rạc đúng và sai (true hoặc false, để hiểu rằng văn bản đó thuộc hay không thuộc một nhóm nào đó) hoặc các giá trị liên tục (một số thực, chỉ ra độ phù hợp của văn bản với một nhóm nào đó). Khi câu trả lời đưa ra bắt buộc phải là đúng hoặc sai thì giá trị liên tục có thể được rời rạc hóa bằng cách đặt ngưỡng. Ngưỡng đặt ra tùy thuộc vào thuật toán và yêu cầu người dùng. Quá trình phân loại văn bản bao gồm các bước: Đánh chỉ số: ở bước này, dữ liệu đầu vào sẽ là một văn bản và kết quả đầu ra là một chuỗi các chỉ số thuật ngữ biểu diễn nội dung của văn bản đầu vào. Cũng giống như trong bài toán tìm kiếm văn bản. Bước này rất quan trọng vì nó quyết định tốc độ và độ chính xác của các bước kế tiếp. Quá trình gán nhãn thường được yêu cầu phải làm việc với tốc độ thời gian thực. Trong bước này thường được chia thành các bước nhỏ hơn: loại bỏ các ký tự thừa và ký tự nhiễu, chuẩn hóa các ký tự, tách từ và đánh chỉ số. Trong các bước này thì bước tách từ và đánh chỉ số là quan trọng nhất. Tuy nhiên cần phải chú ý đến tất cảc các bước vì chúng đều quyết định tốc độ của cả quá trình. Xác định độ phù hợp: cũng giống như tìm kiếm văn bản, phân loại văn bản cần phải có bước xử lý để chỉ ra rằng văn bản đang được phân tích thuộc về một nhóm nào đó dựa trên nội dung của văn bản hay chuỗi các thuật ngữ là biểu diễn của văn bản đó. Bộ phận phân này gọi là bộ phân loại (categorizer hay classifer). Nó cũng giống như bộ định dạng truy vấn trong tìm kiếm văn bản. Tuy nhiên, trong tìm kiếm văn bản mang tính nhất thời, còn trong phân loại văn bản thì mang tính ổn định hơn. Kết quả của quá trình này chỉ ra độ phụ thuộc giữa văn bản đang phân tích với mỗi nhóm có sẵn. Đây có thể coi là bước mang tính quyết định trong cả quá trình phân loại. So sánh: trong hầu hết các bộ phân loại, mỗi văn bản đều được yêu cầu gán giá trị đúng sai vào một lớp nào đó. Sự khác nhau lớn nhất với hệ thống tìm kiếm văn bản là ở đây quá trình so sánh chỉ được thực hiện một lần với số lượng so sánh hữu hạn tùy thuộc vào tập huấn luyện. Việc chọn quyết định phù hợp phụ thuộc chủ yếu vào quan hệ giữa các nhóm dùng để huấn luyện. Phản hồi: quá trình phản hồi đóng hai vai trò trong hệ thống phân loại văn bản. Thứ nhất, khi phân loại văn bản cần phải có một số lượng lớn các văn bản đã được phân loại bằng tay trước đó, các văn bản này được sử dụng làm mẫu huấn luyện để hỗ trợ xây dựng bộ phân loại. Thứ hai, việc phân loại văn bản này không dễ dàng thay đổi như quá trình phản hồi trong tìm kiếm văn bản. Thay vì vậy, người dùng có thể thông tin cho người bảo trì hệ thống về việc xóa, thêm, hay sửa đổi các nhóm văn bản nào đó mình yêu cầu. 3.1.2. Các phương pháp phân loại văn bản Với sự bùng nổ thông tin và sự phát triển không ngừng của Web, bài toán phân loại văn bản đã và đang đóng một vai trò cực kỳ quan trọng. Đơn giản là vì các tài nguyên văn bản trực tuyến ngày càng nhiều. Việc tìm kiếm thông tin sẽ gặp rất nhiều khó khăn nếu như không có chỉ mục tốt và sự tóm tắt nội dung các tài liệu. Trong những năm gần đây, người ta thường sử dụng các phương pháp phân loại bằng phương pháp thống kê và các kỹ thuật máy học để giải quyết bài toán này. Hầu hết các nghiên cứu phân loại văn bản hiện nay đều chỉ giải quyết cho các bài toán nhị phân, trong đó, một tài liệu có liên quan hay không liên quan tới một chủ đề nào đó. Tuy vậy, nhiều tài liệu hiện nay, đặc biệt là các tài liệu trên Internet lại được cấu thành từ nhiều chủ đề khác nhau, đặt ra bài toán phân loại đa lớp (multi-class). Tuy nhiên, các bài toán này cho đến nay vẫn còn rất ít được chú ý quan tâm. Có rất nhiều giải thuật khác nhau để giải quyết bài toán phân loại văn bản, đơn cử như: Thuật toán Rocchio Naive Bayes Decision Trees K- Nearest Neighbor Support Vector Machines Thuật toán cây quyết định (Decision Tree) Cây quyết định là một trong các phương pháp được sử dụng rộng rãi nhất trong học quy nạp từ tập dữ liệu lớn. Đây là phương pháp học xấp xỉ các hàm mục tiêu có giá trị rời rạc. Một ưu điểm của phương pháp cây quyết định là có thể chuyển dễ dàng sang dạng cơ sở tri thức là các luật Nếu - Thì (If - Then). Phương pháp này được Mitchell đưa ra vào năm 1996. Trên cây gồm các nút trong được gán nhãn bởi các khái niệm, các nhánh cây chứa nút được gán nhãn bằng các trọng số của khái niệm tương ứng đối với tài liệu mẫu và các lá trên cây được gán nhãn bởi các nhãn nhóm. Một hệ thống như vậy sẽ phân loại một tài liệu dj bởi phép thử đệ quy các trọng số mà các khái niệm được gán nhãn cho các nút trong với vector cho đến khi với tới một nút lá, khi đó nhãn của nút này được gán cho tài liệu dj. Đa số các phương pháp phân loại như vậy sử dụng biểu diễn ở dạng nhị phân và các cây cũng được biểu diễn dưới dạng nhị phân. Ví dụ về Decision Tree Entropy Entropy là đại lượng đo độ đồng nhất thông tin hay tính thuần nhất của các mẫu. Đây là đại lượng hết sức quan trọng trong lý thuyết thông tin. Giả sử đưa ra tập S có chứa các mẫu ví dụ dương (+) và các mẫu ví dụ âm (-), như vậy S được chia thành hai lớp phân biệt. Khi đó Entropy của tập S được định nghĩa như sau: trong đó p+ là phân bố của các ví dụ dương trong S và p- là phân bố của các ví dụ âm trong S, chúng ta định nghĩa 0log20 = 0. Trong trường hợp tổng quát thì đại lượng Entropy được tính như sau: trong đó pi là phân bố của thuộc tính thứ i trong S. Entropy là đại lượng trong lý thuyết thông tin, tính theo bit, nên hàm logarithm được tính ở cơ số 2, do đó Entropy có thể lớn hơn 1 trong trường hợp n > 2. Information Gain Entropy là đại lượng đặc trưng cho độ đồng nhất thông tin, người ta còn đưa ra một độ đo xác định ảnh hưởng của một thuộc tính trong mẫu đó trong việc phân lớp, đại lượng đó gọi là Information Gain. Information Gain của một thuộc tính A trong tập S, ký hiệu là được xác định như sau: trong đó Values(A) là tập các giá trị có thể của thuộc tính A, còn Sv là tập con có thể của tập S các phần tử có thuộc tính A = v, tức là . Biểu thức đầu Entropy (S) là đại lượng entropy nguyên thủy của tập S, biểu thức sau là giá trị kỳ vọng của entropy sau khi S được chia thành các tập con theo các giá trị của thuộc tính A. Do đó Gain(S,A) thực chất là độ giảm kì vọng của entropy khi biết các giá trị thuộc tính A. Giá trị Gain(S,A) là số bit cần lưu khi mã hóa các giá trị mục tiêu của một thành phần của S, khi biết các giá trị của thuộc tính A. Thuật toán ID3 Các thuật toán học cây quyết định ngày càng được phát triển và cải tiến, nhưng hầu hết các thuật toán đó đều dựa vào cách tiếp cận từ trên xuống và chiến lược tìm kiếm tham lam trong không gian tìm kiếm của cây quyết định. ID3 và cải tiến của nó, C4.5, là các thuật toán học cây quyết định phổ biến nhất. Thuật toán học cây quyết định ID3 lần đầu tiên được Quinlan giới thiệu năm 1975 trong tạp chí machine learning, Vol.1, No.1. Nhìn chung, thuật các bước trong thuật toán ID3 có thể được phát biểu một cách ngắn gọn như sau: Xác định thuộc tính có độ đo Information Gain cao nhất trong tập mẫu Sử dụng thuộc tính này làm gốc của cây, tạo một nhánh cây tương ứn