Gom nhóm văn bản dựa trên mẫu hữu ích được đánh trọng phổ biến

Chia sẻ: Trang Trang | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

46
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong bài báo này, các tác giả đề xuất một phương pháp mới để gom nhóm văn bản dựa vào mẫu hữu ích được đánh trọng phổ biến thông qua việc sử dụng TF (Term Frequency) cho mỗi từ trong văn bản. Trọng số của từ trên toàn bộ tập văn bản được tính dựa vào IDF (Inverse Document Frequency), sau đó sử dụng thuật toán MWIT-FWUI để khai thác các mẫu hữu ích phổ biến.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Gom nhóm văn bản dựa trên mẫu hữu ích được đánh trọng phổ biến

Khoa học Tự nhiên Gom nhóm văn bản dựa trên mẫu hữu ích được đánh trọng phổ biến Trần Thanh Trâm1, Võ Đình Bảy2* Trường Đại học Công nghệ thông tin, Đại học Quốc gia TP Hồ Chí Minh Khoa Công nghệ thông tin, Trường Đại học Công nghệ TP Hồ Chí Minh 1 2 Ngày nhận bài 26/3/2018; ngày chuyển phản biện 30/3/2018; ngày nhận phản biện 22/4/2018; ngày chấp nhận đăng 27/4/2018 Tóm tắt: Gom nhóm văn bản là chủ đề quan trọng trong khai thác dữ liệu văn bản, và phương pháp hiệu quả để gom nhóm văn bản là dựa trên mẫu phổ biến. Đã có nhiều thuật toán được phát triển nhằm nâng cao độ chính xác cho bài toán gom nhóm văn bản dựa trên mẫu phổ biến, nhưng lại không quan tâm tới trọng số của từ trong văn bản. Trong bài báo này, các tác giả đề xuất một phương pháp mới để gom nhóm văn bản dựa vào mẫu hữu ích được đánh trọng phổ biến thông qua việc sử dụng TF (Term Frequency) cho mỗi từ trong văn bản. Trọng số của từ trên toàn bộ tập văn bản được tính dựa vào IDF (Inverse Document Frequency), sau đó sử dụng thuật toán MWIT-FWUI để khai thác các mẫu hữu ích phổ biến. Tiếp theo, tiến hành gom nhóm văn bản bằng thuật toán MC (Maximum Capturing). Kết quả thử nghiệm trên kho ngữ liệu gồm 1.600 văn bản (16 chủ đề) cho thấy, phương pháp mới đã cải thiện đáng kể độ chính xác của việc gom nhóm văn bản so với phương pháp dựa vào mẫu phổ biến. Từ khóa: cơ sở dữ liệu số lượng, gom nhóm văn bản, mẫu hữu ích được đánh trọng phổ biến, mẫu phổ biến, trọng số của từ. Chỉ số phân loại: 1.2 Đặt vấn đề Hiện nay, các công trình nghiên cứu về bài toán gom nhóm văn bản tiếng Việt còn rất ít, hầu hết sử dụng các phương pháp truyền thống như phương pháp gom nhóm đồ thị [1], gom nhóm dựa trên thực thể có tên [2]… Năm 2002, Beil và cộng sự đã giới thiệu một hướng tiếp cận mới cho bài toán gom nhóm văn bản, đó là gom nhóm văn bản dựa vào mẫu phổ biến [3]. Kết quả thực nghiệm cho thấy, gom nhóm văn bản dựa vào mẫu phổ biến có độ chính xác cao hơn, thời gian xử lý tốt hơn so với gom nhóm văn bản dựa vào bisecting k-means [4]. Công trình này mở ra một hướng tiếp cận hoàn toàn mới cho bài toán gom nhóm văn bản và là tiền đề cho rất nhiều công trình nghiên cứu sau này. Một số thuật toán gần đây đã giải quyết được vấn đề gom nhóm văn bản dựa trên mẫu phổ biến như phương pháp CMS [5], phương pháp FIHC [6], phương pháp CFWS [7]. Tuy nhiên, các phương pháp này lại không quan tâm tới trọng số của từ trong các văn bản, chỉ quan tâm tới tần số xuất hiện của các item trong mẫu phổ biến. Trong [8], tác giả đã chỉ ra một số hạn chế của các thuật toán trên như sau: 1) Có thể dẫn tới việc trùng lặp các văn bản trong kết quả * gom nhóm cuối cùng; 2) Có khuynh hướng chọn nhóm ứng viên có số văn bản ít, trong khi độ phổ biến của những văn bản đó lớn để gom thành 1 nhóm, dẫn tới kết quả một số lớn các nhóm được gom chỉ có 1 văn bản; 3) Không thể giải quyết được mâu thuẫn nhóm khi chỉ định các văn bản vào các nhóm, một văn bản có thể được chia thành nhiều nhóm khác nhau… Khai thác mẫu phổ biến không quan tâm đến trọng số của các mục, vì vậy khi áp dụng các thuật toán khai thác mẫu phổ biến để gom nhóm văn bản, các tác giả chỉ quan tâm đến sự xuất hiện hay không xuất hiện của mỗi từ trong văn bản. Thực tế, các từ trong văn bản có số lần xuất hiện khác nhau, nên có đóng góp khác nhau. Trong bài báo này, chúng tôi đề xuất phương pháp gom nhóm văn bản dựa trên trọng số (chẳng hạn TF-IDF, tần số xuất hiện…) của các từ và thuật toán MC với mục tiêu cải thiện độ chính xác của kết quả gom nhóm. Phương pháp nghiên cứu Cơ sở dữ liệu (CSDL) số lượng: cho một CSDL D với một tập các giao dịch T = {t1, t2,... tm}, một tập các mặt hàng I = {i1, i2,… in} và một tập các trọng số W = {w1, w2,…, wn} tương ứng với mỗi mặt hàng trong I. Với mỗi giao dịch Tác giả liên hệ: Email: bayvodinh@gmail.com 60(8) 8.2018 1 Phương pháp nghiên cứu Cơ sở dữ liệu (CSDL) số lượng: Cho một CSDL D với một tập các giao dịch T = {t1, t2,... tm}, một tập các mặt hàng I = {i1, i2,… in} và một tập các trọng số W = {w1, w2,…, wn} tương ứng với mỗi mặt hàng trong I. Với mỗi giao dịch tk = {xk1, xk2,… xkn} mà trong đó xki là số lượng sản phẩm được mua bởi mặt hàng thứ i trong giao dịch tk. Trọng số của từ (TF-IDF): TF-IDF (term frequency - inverse document frequency) của một từ thể hiện mức độ quan trọng của từ này trong một văn bản nằm trong một tập hợp các văn bản. Nó dựa vào tần số xuất hiện của 1 từ trong 1 văn bản (TF) và tần số nghịch của 1 từ trong tập văn bản (IDF). TFtần(term frequency) số1xuất hiệnGiá củatrị1 TF từ của trong TF (term frequency) là số xuất hiện của 1là từtần trong văn bản. một1 từ t trong văn bản d đượcvăn tínhbản. theo công thức (1). Giá trị TF của một từ t trong văn bản d được tính Khoa học Tự nhiên Text clustering using frequent weighted utility itemsets Thanh Tram Tran , Dinh Bay Vo 1 theo công thức (1). �� (�, �) = 2* �(�, �) �(�) (1) (1) đó,hiện n(t,từd)t trong là số văn lần bản xuấtd;hiện t trong vănhiện bản d; Trong đó, n(t, d) là sốTrong lần xuất n(d) từ là số lần xuất của University of Information Technology, Vietnam National University n(d) tất cả các từ trong văn bản d. là số lần xuất hiện của tất cả các từ trong văn bản d. Ho Chi Minh City 2 Faculty of Information Technology, Ho Chi Minh CityIDF University (inverseof document frequency) là tần số nghịch của một từ trong tập văn bản IDF (inverse document frequency) là tần số nghịch của (corpus). Trong tập văn bản, mỗi từ chỉ có 1 giá trị IDF duy nhất được tính theo công thức Technology một từ trong tập văn bản (corpus). Trong tập văn bản, mỗi (2): Received 26 March 2018; accepted 27 April 2018 từ chỉ có 1 giá trị IDF duy nhất được tính theo công thức (2): 1 Abstract: �� (�, �) = �� |�| |{� Î �|� Î � }| 2 (2) (2) Ma trận trọng số Text clustering is one of the important topics of the |D|trong là tập tổng số văn bảnlà trong tậpd có D,xuất tổng sốđó, văn bản D, |{� Î �|� Î � }| số văn bản text mining. One of the most effective methods forTrong text đó, |D| làTrong hiện từ t trong tập D. Nếu từ đó không xuất hiện ở bất cứ một văn bản nào trong tập D thì |{d ∈ D|t ∈ d }| là số văn bản d có xuất hiện từ t trong clustering is the frequent itemsets based approach. mẫu số sẽ bằng 0, dẫn tới phép chia không hợp lệ, vì thế người ta thường thay bằng công tập D. Nếu từ đó không xuất hiện ở bất cứ một văn bản There are many frequent itemsets based algorithms thức 1 + |{� Î �|� Î �}|. Cơ số logarit trong công thức này không thay đổi giá trị của 1 từ to improve the accuracy of text clustering. mà However, nào trong D đó. thì Việc mẫuthay số đổi sẽ cơ bằng dẫn ảnh tới hưởng phép đến chiatỷ lệ chỉ thu hẹp khoảng giá trị tập của từ số sẽ0,không these algorithms do not focus on the weight of terms intrị IDF. giữa các giá Tuyhợp nhiên, thay người đổi khoảng giá trị sẽthay giúpbằng tỷ lệ giữa và TF không lệ,việc vì thế ta thường côngIDF thức tương thức như sau:trong công thức này không documents. In fact, the frequency of each term in đồng eachđể dùng 1+ cho |{d công ∈ D|t ∈ tính d}. TF-IDF Cơ số logarit document has a great impact on results. In this paper, thay đổi giá trị của từmà TF-IDF(t,d,D) = tf(t,1 d) idf chỉ (t, D)thu hẹp khoảng giá trị của từ (3) we propose a new method for text clustering based on đó. Việc thay đổi cơ số sẽ không ảnh hưởng đến tỷ lệ giữa Trong từ có giá trị TF-IDF cao là những từ xuất hiện nhiều trong văn bản frequent weighted utility itemsets. First, we calculate TF đó, những giácáctrịvăn IDF. khoảng sẽ lại này và ít xuất hiệncác trong bản Tuy khác.nhiên, Việc nàyviệc giúpthay lọc rađổi những từ phổ giá biến trị và giữ (Term Frequency) for each term in documents những to create |�| từ cóagiá trị cao (từ của�) văn giúp tỷ khoá lệ�� (�, giữa IDF = bản). ��và TF tương đồng để dùng cho công (2) |{� Î �|� Î � }| number matrix for the documents. The weights of terms Nội dung nghiênthức cứu tính TF-IDF như sau: in the documents is based on the IDF (Inverse Document Mô hình Trong đó, |D| là tổng số văn bản trong tập D, |{� Î �|� Î � }| là số văn bản d có xuất hiện từ t trong tập D. Nếu từ đó không hiện ở bất một văn bản nào trong tập(3) D thì TF-IDF(t,d,D) = nhóm tf(t,xuất d) × idf (t,cứD) Frequency). Next, we use MWIT-FWUI algorithmMôfor hìnhsốgiải quyết gom văn thể hiện trên sơ đồ mẫu sẽ bằng 0, bài dẫn toán tới phép chia không hợpbản lệ, tiếng vì thế Việt ngườiđược ta thường thay bằng công mining frequent weighted utility itemsets fromhình a number 1. thức 1 + |{� Î �|� Î �}|. số logarit côngtrị thức này khôngcao thay là đổinhững giá trị củatừ 1 từ Trong đó, Cơ những từ trong có giá TF-IDF matrix and the weight of terms in the documents. Finally, mà chỉ thu hẹp khoảng giá trị của từ đó. Việc thay đổi cơ số sẽ không ảnh hưởng đến tỷ lệ Tập văn bản xuất hiện nhiều Tập văn trong bản đã đượcvăn xử lý bản này và ít xuất Tập các từ trong các văn Tuy nhiên, giữa các giá Xử trịlýIDF. việc thay đổi khoảng trị sẽ giúphiện tỷ lệ giữa IDFsố và TF Loại bỏgiá hư từ Đánh trọng based on frequent utility itemsets, we cluster text using bản tương đồng đểbản dùngkhác. cho công thứcnày tính TF-IDF nhưra sau: văn Việc giúp lọc những từ phổ biến và giữ (Stopword) MC (Maximum Capturing) algorithm. We have tested từ có giá trị caod)(từ (3) = tf(t,  idfkhoá (t, D) của văn bản). this method on a corpus consisting of 1,600 documents lại nhữngTF-IDF(t,d,D) including 16 different topics. Experimental results Trong đó, những từ có giá trị TF-IDF cao là những từ xuất hiện nhiều trong văn bản nghiên cứu này và ítNội xuấtdung hiện trong các văn bản khác. Việc này giúp lọc ra những từ phổ biến và giữ lại have shown that our method significantly improves những từ có giá trị cao (từ khoá của văn bản). the accuracy of the text clustering compared with the Mô hình Tập mẫu hữu ích được đánh Nội dung nghiên cứu clustering method using frequent itemsets. trọng phổ biến Mô hình Gom nhóm văn Mô hình giải quyết bài toán gom nhóm Khai văn thác bản mẫu hữutiếng ích được Văn được giải quyết bài toán gom bản nhóm văn bản tiếng Việt được thể hiện trên sơ đồ Môbảnhình đánh trọng phổ biến Keywords: frequent itemsets, frequent weighted utility Việt nhómđược thể hiện trên sơ đồ hình 1. hình 1. gom itemsets, quantitative databases, text clustering, weight Tập văn bản Tập văn bản đã được xửvăn lý Hình 1. Mô hình giải quyết bài toán gom nhóm bản Loại tiếng Việt. Tập các từ Đánh trọng số Xử lý văn bỏ hư từ of terms. bản (Stopword) Xử lý văn bản Tách từ tiếng Việt: Trước khi thực hiện gom nhóm văn bản cần tiến hành tách từ tiếng Việt. Không như tiếng Anh, ranh giới giữa các từ trong tiếng Việt không đơn thuần chỉ là những khoảng trắng, đòi hỏi phải xử lý riêng trước. Ví dụ câu “Tổ quốc ta đẹp như tranh vẽ” sẽ được tách ra thành: Tổ_quốc | ta | đẹp | như | tranh_vẽ. Tập mẫu hữu ích được đánh trọng phổ biến Gom văn Nhận dạng tên riêng tiếng Việt (NER - nhóm Named Entity Recogniton) tk = {xk1, xk2,… xkn} mà trong đó xki là số lượng sản phẩm Khai thác mẫu hữu ích được Văn bản được bản đánh trọng phổ biến Sau khi tách từ tiếng Việt, hệ thống sẽ tiến hành nhận dạng tên riêng tiếng Việt. Ví gom nhóm được mua bởi mặt hàng thứ i trong giao dịch tk. dụ câu “Triển lãm diễn ra từ 22 đến 30/6 tại Bảo tàng Mỹ thuật”. Sau khi tách từ và tiến Hình 1. Môtiếng quyết bài gomcác nhóm văn bản tiếng Việt. hành nhận dạng tên riêng Việt, sẽ ratoán thành từ: Triển_lãm | diễn_ra từ | 22/NUM 1. hình Mô giải hình giải quyết bài toán gom nhóm văn | bản tiếng | Trọng số của từ (TF-IDF): TF-IDF (term frequency - |Hình đến | 30/6/NUM tạilý| văn Bảo_tàng Mỹ_thuật/PER |. Xử bản Việt. Tách bài từ tiếng thựcdạng hiệntên gomriêng nhómtiếng văn bản cầnchúng tiến hành táchdụng từ inverse document frequency) của một từ thể hiện mức Việt, tôi sử Để độ giải quyết toánViệt: táchTrước từ vàkhi nhận tiếng Việt. Không như tiếng ranh giới từ trong tiếng Việt không để đơnnhận thuầndạng chỉ công cụ VnTokenizer để phân đoạnAnh, từ tiếng Việtgiữa và các công cụ CLC_VN_NER Xử lý văn bản quan trọng của từ này trong một văn bản nằm trong một tập là những tên riêng tiếng Việt.khoảng trắng, đòi hỏi phải xử lý riêng trước. Ví dụ câu “Tổ quốc ta đẹp như tranh Ma trận trọng số Classification number: 1.2 vẽ” sẽ được tách ra thành: Tổ_quốc | ta | đẹp | như | tranh_vẽ. từriêng tiếng Việt: trước- Named khi thực gom nhóm văn NhậnTách dạng tên tiếng Việt (NER Entityhiện Recogniton) 3 táchtiến từ tiếng Việt,tách hệ thống sẽ tiến Việt. hành nhận dạng tên riêng tiếngAnh, Việt. Ví bản Sau bảnkhicần hành từ tiếng Không như tiếng dụ câu “Triển lãm diễn ra từ 22 đến 30/6 tại Bảo tàng Mỹ thuật”. Sau khi tách từ và tiến ranh giữatiếng cácViệt, từ sẽtrong tiếng Việt không đơn thuần chỉ | hành nhận dạnggiới tên riêng ra thành các từ: Triển_lãm | diễn_ra | từ | 22/NUM đến | 30/6/NUM | tại | Bảo_tàng Mỹ_thuật/PER |. Để giải quyết bài toán tách từ và nhận dạng tên riêng tiếng Việt, chúng tôi sử dụng công cụ VnTokenizer để phân đoạn từ tiếng Việt và công cụ CLC_VN_NER để nhận dạng tên riêng tiếng Việt. hợp các văn bản. Nó dựa vào tần số xuất hiện của 1 từ trong 1 văn bản (TF) và tần số nghịch của 1 từ trong tập văn (IDF). 60(8) 8.2018 2 3 Khoa học Tự nhiên là những khoảng trắng, đòi hỏi phải xử lý riêng trước. Ví dụ câu “Tổ quốc ta đẹp như tranh vẽ” sẽ được tách ra thành: Tổ_quốc | ta | đẹp | như | tranh_vẽ. Nhận dạng tên riêng tiếng Việt (NER - Named Entity Recogniton) Sau khi tách từ tiếng Việt, hệ thống sẽ tiến hành nhận dạng tên riêng tiếng Việt. Ví dụ câu “Triển lãm diễn ra từ 22 đến 30/6 tại Bảo tàng Mỹ thuật”. Sau khi tách từ và tiến hành nhận dạng tên riêng tiếng Việt, sẽ ra thành các từ: Triển_lãm | diễn_ra | từ | 22/NUM | đến | 30/6/NUM | tại | Bảo_tàng Mỹ_thuật/PER |. Để giải quyết bài toán tách từ và nhận dạng tên riêng tiếng Việt, chúng tôi sử dụng công cụ VnTokenizer để phân đoạn từ tiếng Việt và công cụ CLC_VN_NER để nhận dạng tên riêng tiếng Việt. Loại bỏ các hư từ Sau khi tách văn bản thành danh sách các từ, hệ thống tiến hành loại bỏ các hư từ (stopword) không có ý nghĩa đặc trưng (thì, là, nhỉ, vâng, nếu, như…). Để loại bỏ các hư từ, chúng tôi sử dụng từ điển các hư từ được chúng tôi tổng hợp lại (gồm 880 từ). Hình 2. Thuật toán MWIT-FWUI. Thuật toán tìm mẫu hữu ích được đánh trọng phổ biến Loại bỏ các hư từ Loại bỏ các hư từ Như đã được trình bày ở trên, các công trình trước đây Sau khi tách văn bảnthành thànhdanh danhsách sáchcác cáctừ, từ,hệhệthống thốngtiến tiếnhành hànhloại loại bỏ cáchư hưtừtừ Sau khi tách quan văn bản tâm đến trọng số(thì, của là, cácnhỉ, itemvâng, hoặc nếu, vừa quan tâmĐể đếnloạibỏbỏcác pword) không có ý nghĩa đặc trưng như…). các hư từ, word) không cótrọng ý nghĩa đặccác trưng (thì, là,trọng nhỉ, số vâng, nếu, như…). Đểcác loại bỏ các hư từ, số của item, lẫn của mỗi item trong tôisửsửdụng dụngtừtừđiển điểncác cáchư hư từđược đượcchúng chúngtôi tôitổng tổnghợp hợplạilại(gồm (gồm880 880từ). từ). gngtôi giao dịch.hữu Đốitừích vớiđược CSDL đượctrọng xây dựng từ các văn bản, Thuật toán tìm mẫu đánh phổ biến Thuật toán tìm phổtrong biến các giao dịch. chỉmẫu quanhữu tâm ích đến được trọng đánh số củatrọng các item Như đã được trình bày ở trên, các công trình trước đâyquan quantâm tâmđến đếntrọng trọngsốsốcủa củacác các Như đã đượcVì trình bày trên, các công trình trước đây vậy, cóởtrọng thể ápsố dụng thuật toán MWIT-FWUI (hình 2) trong mhoặc hoặcvừa vừaquan quantâm tâm đến của các item, lẫn trọng số của mỗi item các giao đếnthác trọng sốhữu củaích cácđược item,đánh lẫn trọng số của mỗi item trong các giao để được khai mẫu trọng phổ biến. Trong h.Đối Đốivới vớiCSDL CSDL xâydựng dựngtừ từcác cácvăn vănbản, bản,chỉ chỉ quan tâm đếntrọng trọngsốsốcủa củacác cácitem item được xây quan tâm đến phần này, các tác giả đề xuất thuật toán cho phép khai thác cácgiao giaodịch. dịch.VìVìvậy, vậy,cócóthể thểápápdụng dụngthuật thuậttoán toánMWIT-FWUI MWIT-FWUI(hình (hình1)1)đểđểkhai khaithác thác gngcác mẫu hữu íchphổ được đánh trọngphần phổ này, biến các từ ma trận tần số thuật toán cho uhữu hữuích íchđược đượcđánh đánhtrọng trọng biến. Trong tác giả đề xuất phổ biến. Trong phần này, các tác giả đề xuất thuật toán cho pkhai khaithác thácmẫu mẫuxuất hữuhiện íchđược được đánh trọngvăn phổbản biến matrận trậntần tầnsốsốxuất xuấthiện hiệncủa củacác cáctừtừ của các từ trọng trong như trên hình 3. hữu ích đánh phổ biến từtừma ng văn bản như trên hình 2. g văn bản như trên Định hình 2. nghĩa 1: theo [9] Trọng số hữu ích của giao dịch tk, Định nghĩa 1: Theo [9] Trọngsốsốhữu hữu íchcủa củagiao giaodịch dịch t , ký hiệu twu (t ), được tính Định nghĩa 1:kýTheo theo công thức (4).tk,kký hiệu twu (tk),k được tính hiệu [9] twuTrọng (tk), được tínhích ocông côngthức thức(4). (4). ∑�� ∈ �(��) �� × �� ∑ �� ∈ �(�� ) �� × �� (4) ) ��(� = � ��(�� ) = |� | � |�� | Trongđó, đó,��là làtrọng trọng của itemi isố giaoidịch dịch thứ j trong Trong làitem trọng của giao item trong giao đó, Trong sốsốxcủa trong thứ t t.k.dịch thứ t . �� kij j j k (4) (4) k Địnhnghĩa nghĩa22[9]: [9]: Độhỗ hỗtrợ trợ2hữu hữu ích (wus weighted utility support)của củamột mộtitemset itemset Định nghĩa [9]:ích độ(wus hỗ trợ hữu ích (wus - support) weighted Định Độ - -weighted utility htheo theocông côngthức thức(5). (5). utility support) của một itemset tính theo công thức (5). ∑�� ∈ �(�) ��(�)� ) ∑ �� ∈ �(�) ��(�� ( ) �� � = (5) ��(�) = ∑ (5) (5) ��(�(�)� ) ∑�� ∈ �∈ �� � Hình 3. Thuật toán Gom nhóm văn bản. 60(8) 8.2018 3 5 6 7 8 9 Khoa học Tự nhiên 0 0,167 0,286 0 0 0,5 0 0,286 0,5 0 � Xét cơ sở dữ liệu tần số xuất hiện của các từ như trên bảng 1. Item Bảng 1. Cơ sở dữ liệu số lần xuất hiện của các từ. A 0,35 B 0,25 C 0,11 D 0,25 E 0,18 ITEM B C D E IDF TID dụ minh họa 1 0 0 cơ sở dữ liệu tần số xuất hiện2 của các từ như 3trên bảng 1. 2 3 0 0,5 0 0 0,333 0,5 0 0 0 0,222 Sử dụng công thức (2) để tính trọng số của các từ trong văn bản. Mỗi từ chỉ có 1 giá trị IDF duy nhất trong tập văn bản, được xem như là trọng số của mỗi từ trong tập văn bản � Ta có: IDF (A, D) =Bảng log 3.; Trọng tươngsốtựcủa thucác được kết quả như ở bảng 3. Item. Ví dụ minh họa A h 2. Thuật toán Gom nhóm văn bản. 0 0,333 0,429 0,5 0,444 Bảng 3. Trọng số của các Item. Item IDF A 0,35 B 0,25 C 0,11 D 0,25 E 0,18 Tính trọng số hữu ích giao dịch (twu) của mỗi văn bản: từ dữ ở bảng 2 và bảng 3, mỗi tính văn đượcbản: trọng Tính trọng số hữu liệu ích giao dịch (twu) của Từsố dữhữu liệuích ở bảng 2 và bảng 0 2 0 1 3 giao dịch (twu) của mỗi văn bản theo công thức (4): Bảng 1. Cơ sở dữ liệu số lần xuất hiện của 3, cáctính từ. được trọng số hữu ích giao dịch (twu) của mỗi văn bản theo công thức (4): TID 4 ITEM0 3 4 A 0B 2 C 5 D1 0 2 1 03 3 00 2 20 0 12 1 0 3 0 4 2 2 7 2 2 3 4 3 0 1 2 8 0 0 5 32 0 02 6 00 2 34 9 0 1 7 2 2 3 0 8 tập văn bản 0 2 = 2{d , 0d , Ta có: D 1 2 9 từ I = {A, 0 B, 0 C,4D, E}, 3 và tập các 6 E 4 2 1 2 2 0 3 4 Tương tự, 3 3 0 1 0 0 2 0 0 3 0 3 2 0 d03, d4, d5, d6, d7, d8, d9}, 2 d = {2, 0, 3, 0, 4}, với 1 ��(�� ) = �� �� �� � Tương tự, tanhư được quả 4như trên bảng 4. ta được kết quả trênkếtbảng = 0,064 số hữu giao văn bản. Bảng 4.Bảng Trọng4.sốTrọng hữu ích giaoích dịch củadịch mỗicủa vănmỗi bản. Tids twu Tids twu 1 0,064 1 0,064 2 0,072 2 0,072 3 0,0535 3 0,0535 4 0,063 5 0,108 6 0,074 0,0915 7 0,073 0,058 8 0,0915 0,657 9 0,058 nghĩa văn bản d có 2 từ A, 3 từ C, 4 từ E, không 4 C, D, có: Tập văn bản D =là{dtrong 1, d2, d3, d4, d5,1 d6, d7, d8, d9}, và tập các từ I = {A, B, có từ B, D. 5 có từ = {2, 0, 3, 0, 4}, nghĩa là trong văn bản d1 có 2 từ A, 3 từ C, 4 từ E, không 6 Khai thác mẫu hữu ích được đánh trọng phổ biến: 7 ai thác mẫu hữu ích phổđểbiến: Sửđược dụng đánh công trọng thức (1) tính tần số xuất hiện TF của 8 item dụng công thức tínhvăn tầnbản. số xuất hiệnA TF các từ trong bản. Vì các(1) từ để trong Vì item xuấtcủa hiện ở văn bản 1,văn 4, 6, � 9 n ở văn bản 1,7,4,nên 6, 7,TF(A) nên TF(A) được được tính tính như như sau:sau: TF TF (A,(A,d1)d1)== ; TF (A, d4) � �,��×�,��,��×�,��,��×�,�� SUM 0,063 0,108 0,074 0,073 (A, ddd6666)))== = ;;; TF TF(A, (A,ddd777)7)))== = ...Tương Tươngtự tựcho chocác các item itemcòn còn lại, lại, thu thu được được kết kết quả quả như như ởởở TF (A, = TF (A, = Tương tự tự cho cho các item lại, thu được kết quả như = TF (A, d4) = == ��;;; TF TF (A, 5còn �� �� Tính độ hỗ trợSUM hữu ích 0,657 (wus): từ dữ liệu ở bảng 2 và 4, bảng 2.thu được kết quả như ở bảng 2. bảng bảng 2. các item còn lại,2. ta tính độ hỗ trợ hữu ích theo công thức (5), trong đó lấy Bảng2. 2.Tần Tầnsố sốxuất xuấthiện hiệncủa củacác cáctừ từđộ trong văn bản. ích (wus): Từ dữ liệu ở bảng 2 và 4, ta tính độ hỗ trợ hữu ích theo Tính hỗvăn trợbản. hữu Bảng Bảng 2. Tần số xuất hiện của các từ trong trong văn bản. min_wus = 0,2. Item A xuất hiện ở văn bản 1, 4, 6, 7 nên: ITEM công thức (5), trong đó lấy min_wus = 0,2. Item A xuất hiện ở văn bản 1, 4, 6, 7 nên: ITEM ITEM Bảng 2. Tần số xuất hiện củaTID các từ trong văn bản. B 6 TID TID A AA B B C CC D DD EEE �,��,��,��,�� wus (A) = = 0,42 ITEM � = ; TF � 2. TID bảng 1 2 3 4 5 6 7 8 9 0,222 0,333 0,444 �,�� 111 0,222 0,222 000 0,333 0,333 000 0,444 0,444 2 0,333 0 0,167 0,5 (C) = 0,73, wus (D) = 0,49, wus (E) = 0,64. � 000 2 2 0,333 0,333 0 0 0,167 0,167 0,5 0,5 tự, wus (B)thu= được 0,61, wus DTương E ta đượccòn (A, dA6) = ; TFB (A, d ) C= . 00Tương tự cho quảwus như(B) ở = 0,61, wus (C) = 0,73, wus Tương được 0 0,444các item 0,222 lại, 0,222tự, ta kết 0,111 333 7 0,444 0,444 0,222 0,222 0,222 0,222 0,111 0,111 � �Tất cả các giá trị này đều thỏa min_wus = 0,2, do đó tất cả các item đơn này sẽ được thêm 0,375 0,125(D) = 0,49, 0,25 wus (E) 0,25= 0,64. Tất cả các giá trị này đều thỏa 444 0,375 0,375 000 0,125 0,125 0,25 0,25 0,25 0,25 vào phổ biến:000 = min_wus {A, B,000C,=D, E}.do 0 cây 0,5 0,5 55 0,5 0,5 0,5 0,5 0,222 0 5số 0 mẫu 0,444 0,2, đó tất cả các item đơn này sẽ được thêm Bảng 2. Tần xuất0,333 hiện00của các từ trong văn bản. 0,167 0 0,333 0,5 0 666 0,167 0,167 0 0 0,333 0,333 0,5 0,5 0 0 Xét lớp tương đương A, A kết hợp với B, ta ITEM 0 0,333 0 0,167 0,5 vào cây mẫu phổ biến: φ =được {A, một B, C,itemset D, E}. mới AB với wus (AB) 0,286 0,286 0,429 777 A 0,286 0,286 0,286 0,286 0,429 0,429 000 E 000 TID B C D = 0,12 < min_wus, vì vậy AB không được thêm vào A. Tương tự, wus (AC) = 0,42 ≥ 8 0 0,5 0,5 0 0 0 0,444 0,222 00 0,222 0,5 88 0,5 0,111 0,5 0,5 00 00 Xét lớp tương đương A, A kết hợp với B, ta được một 9 0,222 00 0 0,333 0,444 0,333 0,222wus (AD) = 0,21 ≥ min_wus, thêm AD vào min_wus, thêm AC vào A, ta được A = {AC}; 9 9 0 0 0 0 0,444 0,444 0,333 0,333 0,222 0,222 1 0 0,444 0,375 0 0,125 0,25 0,25 itemset mới wus (AB)vì= vậy 0,12AE < min_wus, vì thêm vậy vào A. 2 0 0,333 0 {AC, AD}; 0,167 0,5 =AB A, ta được A = wus (AE) 0,19với < min_wus, không được 0 3 0,5 0 0 0 0,5 AB không được thêm vào A. Tương tự, wus (AC) = 0,42 ≥ 0,444 0,222 0,222 0,111 Sửdụng dụngcông công thức(2) (2)để đểSau tínhkhi trọng sốhiện của0,25 các từtrong trong vănsẽ bản. Mỗi từchỉ chỉcó có giá để tiếp tục tạo ra các lớp Sử dụng công thức (2) để tính tính trọng trọng số số của của các các từ từ trong văn văn bản. bản. Mỗi từ từ chỉ có giá thực xong ở lớp A, gọiMỗi thuật toán đệ111Agiá quy 4Sử 0,375thức 0,125 0,25 min_wus, thêm AC vào A, ta được = {AC}; wus (AD) = 0,167 0 0,333 0 0,5 0 trị IDF duy nhất trong tập văn bản, được xem như là trọng số của mỗi từ trong tập văn bản. trị trị IDF IDF5duy duy nhất nhất trong trong tập tậptương văn văn bản, được được xem xem như là0,21 trọng trọng≥tương số số của củatựmỗi mỗi từ từcác trong trong tập văn bản. bản. đương nó.như Thực hiện vớithêm lớptập B, văn C, D, E, cuốiA cùng ta có được mẫu 0 0,5bản, 0sau 0là 0,5 min_wus, AD vào A, ta được = {AC, AD}; 0,286 0,286 0,429 0 0 � 6IDF (A, D)0,167 0 ích được 0,5 0 đánh trọng phổ biến thỏa mãn min_wus = 0,2 là {A, B, C, D, E, AC, AD, BC, Tacó: có:IDF =log log��hữu ;tương tương tựthu thu0,333 đượckết kếtquả quả như ở bảng 3. Ta Ta có: IDF (A, (A, D) D) = = log ; ; tương tự tự thu được được kết quả như như ở ở bảng bảng 3. 3. 0,429 0 wus (AE) 0 = 0,19 < min_wus, vì vậy AE không được thêm 0 7 0,5 0,286 0,5�� 0,286 0 0 BE, CD, CE, DE, ACD, CDE} trên hình 3. vào A.Item. 8 0 0,5 0,5 0 Bảng 3.Trọng Trọngsố số0của của các Item. Bảng 3. 3. Trọng số của các các Item. 0 0 0,444 0,333Bảng 0,222 9 0 0 0,444 0,222 Item IDF0,333 � Item Item IDF IDF Sau khi thực hiện xong ở lớp A, sẽ gọi thuật toán đệ quy Sử dụng công thức (2) để tính trọng số của A các từ trong A 0,35 để tiếp tục tạo ra các lớp tương đương sau nó. Thực hiện A 0,35 0,35 dụng công để tính trọng từ trongtương văn bản. Mỗi chỉB, cóC,1 D, giáE, cuối cùng ta có được mẫu văn bản.Sử Mỗi từ chỉ cóthức 1 giá(2) trị IDF duy nhấtsốtrong tập văn B các 0,25 B Bcủa 0,25 0,25 tự với cáctừlớp trị IDF nhất tập số văncủa bản, được xem Ctập như là trọng số của mỗi từ trong tập văn bản. bản, đượcduy xem nhưtrong là trọng mỗi từ trong văn bản. 0,11 hữu ích được đánh trọng phổ biến thỏa mãn min_wus = 0,2 CC 0,11 0,11 � TaTacó: tương tự tự thu thuđược đượckết kết quảnhư như quả ở bảng 3. B, C, D, E, AC, AD, BC, BE, CD, CE, DE, ACD, có:IDF IDF(A, (A,D) D)==log log ; tương D 0,25 là {A, D D 0,25 0,25 � ở bảng 3. 0,18 CDE} trên hình 4. Bảng 3. Trọng Item. EEE số của các 0,18 0,18 Item IDF Agiao 0,35 Tínhtrọng trọngsố sốhữu hữuích ích giaodịch dịch (twu) của mỗimẫu vănhữu bản:ích Từđược dữliệu liệu bảngphổ và bảng Tính Tính trọng số hữu ích giao dịch (twu) (twu) của của mỗi mỗi văn văn bản: bản: Từ Từ dữ dữ liệu bảng bảng 222và và bảng bảng Hình 3. Cây đánhởởởtrọng biến với min_wus = 0,2. B 0,25 3, tính được trọng số hữu ích giao dịch (twu) của mỗi văn bản theo công thức (4): 3, 3, tính tính được được trọng trọng số số hữu hữu ích ích giao giao dịch dịch (twu) (twu) của của mỗi mỗi văn văn bản bản theo theo công công thức thức (4): (4): Gom nhóm văn bản: �,��×�,��,��×�,��,��×�,�� C 0,11 �,��×�,��,��×�,��,��×�,�� �,��×�,��,��×�,��,��×�,�� 60(8) 8.2018 4 =Xây = 0,064 ��(((��)))= = dựng ma trận = 0,064 = 0,064 �� �� tương đương: Từ dữ liệu ở bảng 2 và hình 3, ta xây dựng được �� D 0,25 maEtrận tương đương với a[i][j] = số mẫu phổ biến giống nhau giữa hai văn bản (bảng 5). Tươngtự, tự,ta tađược đượckết kếtquả quảnhư như0,18 trênbảng bảng444 Tương Tương tự, ta được kết quả như trên trên bảng Bảng 5. Ma trận tương đương. Khoa học Tự nhiên Bước 4: tìm giá trị max trong A và các cặp văn bản có cùng giá trị với max. Ta thấy max = 5; các cặp văn bản (1, 4); (2, 3) có cùng giá trị với max; (1, 4); (2, 3) có văn bản 3, 4 thuộc nhóm (3, 4, 6, 9), do đó ta gom 1, 2 vào nhóm này. Thu được (1, 2, 3, 4, 6, 9) là 1 nhóm và gán giá trị cho các cặp văn bản vừa tìm được bằng 0; còn lại văn bản (5, 7, 8) chưa được gom nhóm (bảng 7). Hình 4. Cây mẫu hữu ích được đánh trọng phổ biến với min_wus = 0,2. Bảng 7. Ma trận tương đương với các văn bản (1, 2, 3, 4, 6, 9) đã được gom nhóm. 1 Gom nhóm văn bản: 1 - Xây dựng ma trận tương đương: từ dữ liệu ở bảng 2 và hình 4, ta xây dựng được ma trận tương đương với a[i][j] = số mẫu phổ biến giống nhau giữa hai văn bản (bảng 5). 1 2 1 2 3 4 5 6 7 8 9 6 1 3 3 1 3 5 3 3 1 1 1 3 8 3 3 3 3 7 1 7 3 1 7 0 1 1 1 3 1 3 3 1 5 6 7 8 1 - Thực hiện gom nhóm (5 bước): Bước 1: tìm giá trị nhỏ nhất khác 0 trong ma trận tương đương A: min = 1. Bước 2: tìm giá trị lớn nhất trong A: max = 7. Bước 3: tìm các cặp văn bản có giá trị bằng max. Ta thấy (3, 4); (3, 9); (4, 6); (4, 9) có giá trị bằng 7; gom (3, 4, 6, 9) là 1 nhóm và gán giá trị cho các cặp văn bản vừa tìm được bằng 0; còn lại các văn bản (1, 2, 5, 7, 8) chưa được gom nhóm (bảng 6). Bảng 6. Ma trận tương đương với các văn bản (3, 4, 6, 9) đã được gom nhóm. 1 1 2 3 4 5 7 8 9 1 3 0 1 3 3 1 3 0 3 3 1 1 1 3 0 3 3 3 3 0 1 0 3 1 0 0 1 1 1 3 1 3 3 1 Xét tiếp (2, 5) có văn bản 2 thuộc nhóm (1, 2, 3, 4, 6, 9), do đó ta gom 5 vào nhóm đã có này và gán giá trị (2, 5) bằng 0, được (1, 2, 3, 4, 5, 6, 9) là 1 nhóm; (7, 8) là 1 nhóm, gán giá trị cho các cặp văn bản vừa tìm được bằng 0. Như vậy, tất cả văn bản đã được gom nhóm; kết thúc việc gom nhóm. Từ 9 văn bản đã cho ban đầu ta gom được thành 2 nhóm: nhóm 1 gồm các văn bản (1, 2, 3, 4, 5, 6, 9) và nhóm 2 gồm các văn bản (7, 8) như trên bảng 8. Bảng 8. Ma trận tương đương với tất các văn bản đã được gom nhóm. 1 3 4 5 6 7 8 9 1 3 5 1 3 3 1 3 5 3 3 1 1 1 3 3 3 3 3 0 1 0 3 1 0 0 1 1 1 5 3 1 3 6 1 7 1 8 6 7 3 8 60(8) 8.2018 1 Bước 5: tiếp tục tìm giá trị max trong A và các cặp văn bản có cùng giá trị với max. Ta thấy max = 3, các cặp văn bản (1, 3); (1, 6); (1, 7); (1, 9); (2, 4); (2, 5); (2, 9); (3, 5); (3, 6); (3,7); (3, 8); (4, 7); (6, 7); (6, 9); (7, 8) có cùng giá trị với max. Trong các cặp văn bản trên, có cặp văn bản (7, 8) chưa thuộc nhóm văn bản đã được gom cụm, do đó ta gom (7, 8) thành 1 nhóm và gán giá trị cho (7, 8) bằng 0. 2 0 6 5 5 7 5 4 3 3 4 2 7 4 3 3 Bảng 5. Ma trận tương đương. 1 2 1 2 3 4 5 2 3 4 5 6 7 8 9 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 1