Bài toán phân lớp văn bản và áp dụng phân lớp dữliệu tài chính ngân hàng

à Dis(Ci, Ck) được định nghĩa là số đường liên kết giữa Ci và Ck. Nếu đường liên kết càng ngắn thì hai lớp càng gần nhau hơn. Từ đó, có thể tính được độ hồi tưởng, độ chính xác và độ đo F dựa vào khoảng cách giữa các lớp. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 17 -  Chương 2. CÁC PHƯƠNG PHÁP PHÂN LỚP VĂN BẢN Phân lớp văn bản là quá trình gán nhãn các văn bản ngôn ngữ tự nhiên vào một hoặc nhiều lớp từ tập các lớp hữu hạn cho trước. Hiện nay tồn tại rất nhiều thuật toán phân lớp văn bản như: thuật toán K người láng giềng gần nhất, thuật toán học cây quyết định [4][5][7], thuật toán Naïve Bayes, thuật toán máy hỗ trợ vector [13][11][14][12][16], thuật toán Boosting, Mô hình Maximum Entropy[15][16][2]… Chương này sẽ giới thiệu một số thuật toán điển hình, trong đó tập trung vào thuật toán Maximum Entropy. 2.1. Thuật toán K người láng giềng gần nhất Bộ phân lớp dựa trên thuật toán K người láng giềng gần nhất là một bộ phân lớp dựa trên bộ nhớ, đơn giản vì nó được xây dựng bằng cách lưu trữ tất cả các đối tượng trong tập huấn luyện. Để phân lớp cho một điểm dữ liệu mới x, trước hết bộ phân lớp sẽ tính khoảng cách từ điểm dữ liệu trong tập huấn luyện. Qua đó tìm được tập N(x, D, k) gồm k điểm dữ liệu mẫu có khoảng cách đến x là gần nhất. Ví dụ nếu các dữ liệu mẫu được biểu diễn bởi không gian vector thì chúng ta có thể sử dụng khoảng cách Euclian để tính khoảng cách giữa các điểm dữ liệu với nhau. Sau khi xác định được tập N(x, D, k), bộ phân lớp sẽ gán nhãn cho điểm dữ liệu x bằng lớp chiếm đại đa số trong tập N(x, D, k). Mặc dù rất đơn giản, nhưng thuật toán K người láng giềng gần nhất đã cho kết quả tốt trong nhiều ứng dụng thực tế. Để áp dụng thuật toán K người láng giềng vào tài liệu văn bản, chúng ta sử dụng hàm tính trọng số cho mỗi lớp theo biểu thức : ( , , ) ( | ) c o s ( , ) x N c x D k S c o r e c x x x ′∈ ′= ∑ Trong đó Nc(x, D, k) là tập con chỉ chứa các đối tượng thuộc lớp c của tập N(x, D, k). Khi đó tài liệu x sẽ được phân vào lớp c0 nếu: { }CcxcscoreMaxxocscore ∈= ),|()|( ¾ Phương pháp K người láng giềng gần nhất là một phương pháp đươn giản. Tuy nhiên, thuật toán này ổn định và sai sót thấp khi số văn bản trong tập văn bản láng giềng phải lớn. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 18 -  2.2. Mô hình cây quyết định (Decision Tree) Trong lý thuyết quyết định, một cây quyết định là một đồ thị những quyết định và những kết quả có khả năng của chúng (bao gồm cả giá phải trả và độ rủi ro) được sử dụng để tạo ra một đường đi tới đích [4]. Cây quyết định là một dạng đặc biệt của cấu trúc cây được xây dựng để trợ giúp việc ra quyết định. Trong lĩnh vực học máy, cây quyết định là một mô hình dự đoán, có nghĩa là từ việc quan sát các item để rút ra kết luận về giá trị đích của item đó. Mỗi nút bên trong tương đương với một biến, mỗi cung đi tới một nút con tương ứng với giá trị có thể của biến đó. Các là tương ứng với giá trị đích được dự đoán cho các biến. Kỹ thuật học máy sử dụng việc xây dựng cây quyết định trên tập dữ liệu được gọi là học cây quyết định hay đơn giản chỉ là cây quyết định. Học cây quyết định cũng là một phương pháp rất thông dụng trong khai phá dữ liệu. Trong đó cây quyết định mô tả cấu trúc cây mà ở đó các lá đại diện cho các lớp và các nhánh cây biểu diễn sự kết hợp của các đặc trưng dẫn dắt tới việc phân lớp. Một cây quyết định có thể được học bằng cách chia tập nguồn thành các tập con dựa trên giá trị các thuộc tính kiểm tra [4], [5]. Quá trình này được lặp lại trên từng tập con thu được. Quá trình đệ quy sẽ kết thúc khi không thể chia tiếp được nữa hoặc khi từng phần tử của tập con được gán với một lớp đơn [5]. Cây quyết định được mô tả bằng cách tính toán xác suất có điều kiện. Cây quyết định cũng có thể được mô tả như là một kỹ thuật tính toán và hỗ trợ toán học, kỹ thuật này hỗ trợ việc mô tả, phân loại và khái quát tập dữ liệu đưa vào. Dữ liệu đưa vào dạng ghi có dạng: (x, y) = (x1, x2, … ,xk, y ) Biến phụ thuộc y là biến mà chúng ta cố gắng để biết, phân lớp hay tổng quát hóa, còn các biến x1, x2,… là các biến giúp ta thực hiện công việc đó. Để xây dựng được cây quyết định của tập dữ liệu nào đó chúng ta phải hiểu được khái niệm độ đo Entropy và Information Gain (Lợi ích thông tin). Khái niệm lượng thông tin và độ đo Entropy: Khái niệm lượng thông tin được Shanon (nhà toán học, nhà vật lý) [7] đưa ra năm 1948 thông qua khái niệm trung gian là “độ bất định” trong dự án khả năng xảy ra trước khi nhận được thông tin. Sau khi nhận được thông tin, nếu độ bất định giảm đi thì có thể coi lượng thông tin nhận được là bằng mức độ giảm đi của độ bất định. Nếu ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 19 -  dự đoán càng nhiều tình huống có thể xảy ra thì độ bất định trong dự báo càng lớn. Tuy nhiên Shanon cũng cho rằng trong n tình huống dự đoán có thể xảy ra không nhất thiết cả n tình huống đều có khả năng xảy ra như nhau, do vậy công thức tính độ bất định do ông đưa ra có tính tới các xác suất khác nhau của dự báo. Độ đo entropy của biến ngẫu nhiên rời rạc x với n trạng thái có thể 1, 2, … , n là: ∑ ∑ = = −=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛= n i n i ipip ip ipxH 1 1 22 )(log)()( 1log)()( Công thức này hoàn toàn trùng với công thức tính Entropy trong nhiệt động học do nhà toán học Boltzmann người áo đưa ra. Theo nguyên lý thứ 2 của nhiệt động học thì một hệ kín, không có trao đổi năng lượng bên ngoài tất yếu sẽ chuyển động đến trạng thái cân bằng tới khi các bộ phận cấu thành của hệ thống đó giống nhau, đồng nhất và mất đi cấu trúc hay là tan vỡ trật tự và trở nên hỗn độn. Entropy là đại lượng để đo trạng thái mất trật tự, mất cấu trúc trong hệ thống. Độ đo entropy luôn là một số dương [7]. Lợi ích thông tin (Information Gain) Gain(S, A) là lợi ích thông tin mà thuộc tính A mang lại cho sự phân lớp tập S. A có m giá trị v1, v2, … , vm Ký hiệu Svi = {x ∈ S | x có giá trị thuộc tính A là vi} U m i vi SS 1= = ∑ = = m i vi vi SEntropy S S ASGain 1 )( || || ),( |S| là số phần tử của tập S Thuật toán tìm cây quyết định: Cho tập ví dụ huấn luyện D. Tìm cây quyết định phù hợp với D. Bước 1: Khởi tạo cây một đỉnh gốc Toàn bộ tập ví dụ huấn luyện D đều đi vào đỉnh này. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 20 -  Bước 2: Repeat Chọn một đỉnh lá chưa gán nhãn để phát triển gọi là đỉnh hiện thời Giả sử tập ví dụ huấn luyện đi vào đỉnh này là S 2.1 If (S = rỗng) Then (gán nhãn chung nhất trong D) Else 2.2 if (tất cả các ví dụ trong S đều được gán cùng một nhãn c) Then (đỉnh hiện thời được gán nhãn c) Else 2.3 Đỉnh hiện thời được gán nhãn là thuộc tính A trong đó A = argmax Gain (S, Ai) Ai: ứng viên là nhãn của đỉnh hiện thời và mỗi giá trị v của A được gán nhãn cho nhánh đi từ A tới đỉnh mới. Tập ví dụ huấn luyện đi tới đỉnh mới đó là Sv trong đó Sv = {s ∈ S | s có giá trị của thuộc tính A là v} Until (tất cả các đỉnh của cây đều được gán nhãn) ¾ So với các phương pháp khác trong Data Mining, phương pháp cây quyết định có những ưu điểm nổi bất như: - Rất dễ hiểu và dễ giải thích: mọi người đều có thể hiểu mô hình cây quyết định qua một số giải thích tổng quát ban đầu. - Dữ liệu dùng cho cây quyết định chỉ là những dữ liệu căn bản hoặc có thể không cần thiết. Một số kỹ thuật khác có thể đòi hỏi dữ liệu chuẩn, tạo các biến giả và loại bỏ đi các giá trị trống. - Có khả năng xử lý cả dữ liệu thực và dữ liệu mập mờ. Một số kỹ thuật khác chỉ sử dụng những tập dữ liệu đặc biệt chẳng hạn như mạng nơron có thể chỉ sử dụng các biến là số. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 21 -  - Có thể kiểm chứng mô hình bằng cách thử thống kê. - Có khả năng thực hiện tốt đối với dữ liệu lớn trong thời gian ngắn: một lượng lớn dữ liệu có thể được phân tích bằng máy tính cá nhân trong thời gian ngắn đủ để người sử dụng đưa ra quyết định dựa trên sự phân tích đó. Tuy nhiên sử dụng phương pháp cây quyết định có thể xảy ra hiện tượng overfit, tức là tồn tại một giả thuyết h phù hợp với tập ví dụ huấn luyện nhưng tiên đoán không chính xác bằng giả thuyết h’ ít phù hợp với tập ví dụ huấn luyện hơn so với h. Để giải quyết vấn đề này chúng ta phải dùng cách chặt bớt cây (pruning), bỏ bớt đi các nhánh dữ liệu nhiễu và dư thừa… 2.3. Thuật toán máy hỗ trợ vector (SVM – Suport Vector Machine) Thuật toán máy vector hỗ trợ (Support Vector Machines - SVM) được Corters và Vapnik giới thiệu vào năm 1995 [13]. SVM rất hiệu quả để giải quyết các bài toán với dữ liệu có số chiều lớn như các vector biểu diễn văn bản. Thuật toán SVM ban đầu chỉ được thiết kế để giải quyết bài toán phân lớp nhị phân tức là số lớp hạn chế là hai lớp. Hiện nay, SVM được đánh giá là bộ phân lớp chính xác nhất cho bài toán phân lớp văn bản [13], bởi vì đó là bộ phân lớp tốc độ rất nhanh và hiệu quả đối với bài toán phân lớp văn bản. Cho tập dữ liệu học { }( , ), 1,...,i iD x y i n= = với mix R∈ và { }1,1iy ∈ − là một số nguyên xác định ix là dữ liệu dương hay âm. Một tài liệu ix được gọi là dữ liệu dương nếu nó thuộc lớp ic ; ix được gọi là dữ liệu âm nếu nó không thuộc lớp ic . Bộ phân lớp tuyến tính được xác định bằng siêu phẳng: { }0: ( ) 0Tx f x w w= + = Trong đó mw R∈ và 0w R∈ đóng vai trò là tham số của mô hình. Hàm phân lớp nhị phân { }: 0,1mh R → có thể thu được bằng cách xác định dấu của f(x) : Học bộ phân lớp của mô hình bao gồm việc xác định w và 0w từ dữ liệu. Với thuật toán này, mỗi dữ liệu được xem là một điểm trong mặt phẳng. Dữ liệu học là 1 ( ) 0 h x ⎧=⎨⎩ Nếu 0)( >xf ngược lại ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 22 -  tách rời tuyến tính (linearly separable) nếu tồn tại một siêu phẳng sao cho hàm phân lớp phù hợp với tất cả các nhãn; tức là ( ) 0i iy f x > với mọi i = 1,...,n. Với giả thuyết này, Rosenblatt đã đưa ra một thuật toán đơn giản để xác định siêu phẳng : 1. w ←0 2. w0←0 3. repeat 4. e←0 5. for i←1,…,n 6. do s←sign(yi(wTxi +w0) 7. if s<0 8. then w ←w + yixi 9. w0←w0 + yixi 10. e←e+1 11. util e=0 12. return (w,w0) Điều kiện cần để D tách rời tuyến tính là số dữ liệu học n = |D| nhỏ hơn hoặc bằng m+1. Điều này là thường đúng với bài toán phân lớp văn bản, bởi vì số lượng từ mục có thể lên tới hàng nghìn và lớn hơn nhiều lần so với số lượng dữ liệu học. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 23 -  Trong hình 4, giả sử rằng các dữ liệu mẫu thuộc lớp âm và lớp dương đều tuân theo luật phân bố chuẩn Gaussian, và được tạo ra với cùng một xác suất. Khi đó một siêu phẳng phân cách được gọi là lý tưởng nếu nó làm cực tiểu xác suất phân lớp sai cho một điểm dữ liệu mới. Với giả thuyết ở trên thì siêu phẳng phân cách lý tưởng sẽ trực giao với đoạn thẳng nối tâm của hai vùng có mật độ xác suất lớn nhất. Rõ ràng các siêu phẳng mà chúng ta xây dựng nhằm phân cách các điểm dữ liệu mẫu có thể lệch đi rất nhiều so với siêu phẳng lý tưởng, do đó sẽ dẫn tới việc phân lớp không tốt trên dữ liệu mới sau này. Độ phức tạp của quá trình xác định siêu phẳng lý tưởng sẽ tăng theo số chiều của không gian đầu vào m, vì với một số lượng các dữ liệu mẫu cố định, tập hợp các siêu phẳng thực tế sẽ tăng theo hàm mũ với lũy thừa m. Với bài toán phân lớp trang văn bản, m thường rất lớn, khoảng vài ngàn hay thậm chí là hàng triệu từ. Siêu phẳng lý tưởng Siêu phẳng thực tế Hình 4. Mối quan hệ giữa các siêu phẳng phân cách ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 24 -  Theo lý thuyết thống kê được phát triển bởi Vapnik năm 1998 chỉ ra rằng : chúng ta có thể xác định một siêu phẳng tối ưu thoả mãn hai tính chất quan trong : nó là duy nhất với mỗi tập dữ liệu học tách rời tuyến tính; và khả năng overfitting là nhỏ hơn so với các siêu phẳng khác [14]. Định nghĩa biên M của bộ phân lớp là khoảng cách giữa các siêu phẳng và các dữ liệu học gần nhất. Siêu phẳng tối ưu nhất là siêu phẳng có biên lớn nhất, điều đó có nghĩa là chúng ta cần tìm siêu phẳng sao cho khoảng cách từ siêu phẳng đến những điểm gần nhất là lớn nhất (Hình 5). Vapnik cũng chứng minh rằng khả năng overfitting với siêu phẳng tối ưu nhỏ hơn so với các siêu phẳng khác. Khoảng cách từ một điểm x đến siêu phẳng là : ( )01 Tw ww + Vì vậy siêu phẳng tối ưu có thể thu được bằng ràng buộc tối ưu sau: 0, max w w M Sao cho ( )01 , 1,...,Ti iy w x w M i nw + ≥ = Trong đó ràng buộc yêu cầu mỗi tài liệu học (tương đương với các điểm) phải nằm trên nửa mặt phẳng của nó và khoảng cách từ điểm tới siêu phẳng lớn hơn hoặc bằng M. Hình 5. Siêu phẳng tối ưu và biên ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 25 -  Đặt 1Mw = biểu thức trên được viết lại như sau: 0, min w w w Sao cho : ( )0 , 1,...,Ti iy w x w M i n+ ≥ = Đưa về phương trình Lagrangian: ( )2 0 1 1( ) 1 2 n T i i i L D w y w wα = ⎡ ⎤= − + + −⎣ ⎦∑ Sau đó tính đạo hàm của phương trình trên với 0,w w ta thu được: 1 1max 2 n T i iα α α α = − Λ +∑ thoả mãn : i 0 1,...,i nα ≥ = Với Λ là ma trận n n× trong đó Tij i j i jy y x xα = . Đây là bài toán bậc hai, theo lý thuyết có thể giải được bằng phương pháp chuẩn tối ưu. Với mỗi dữ liệu học i, cách giải phải thoả mãn điều kiện: ( )0 1 0Ti iy w wα ⎡ ⎤+ − =⎣ ⎦ Và do đó hoặc 0iα = hoặc ( )0 1Ti iy w x w+ = . Nói cách khác, nếu 0iα > thì khoảng cách từ điểm ix đến mặt phẳng phân cách là M. Các điểm thoả mãn 0iα > được gọi là các vector hỗ trợ. Hàm quyết định h(x) có thể được tính qua công thức dấu của f(x) hoặc tương đương với dạng sau: 1 ( ) n T i i i i f x y x xα = =∑ Nếu dữ liệu học không tách rời tuyến tính, thêm biến iξ và thay phương trình trên bằng phương trình: 0, 1 min n iw w i w C ξ = + ∑ thoả mãn ( )0 1 1,..., 0 1,..., T i i i i y w x w i n i n ξ ξ ⎧ + ≥ − =⎪⎨ ≥ =⎪⎩ Vấn đề này có thể đưa về dạng: 1 1max 2 n T i iα α α α = − Λ +∑ thoả mãn: 0 1,....,i C i nα≤ ≤ = Bộ phân lớp theo cách này được gọi là bộ phân lớp máy vector hỗ trợ – Support Vector Machine. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 26 -  ¾ Phương pháp SVM được coi là phương pháp hiệu quả để giải quyết bài toán phân lớp với dữ liệu có số chiều lớn như các vector biểu diễn văn bản. Về mặt lý thuyết, thuật toán phân lớp nhị phân này cũng có thể sử dụng cho bài toán phân lớp đa lớp bằng cách chuyển bài toán đa lớp thành bài toán nhị phân. Tuy nhiên, đối với bài toán phân lớp văn bản sử dụng phương pháp SVM thì việc lựa chọn thuộc tính cho từng phân lớp lại là vấn đề cực kỳ quan trọng, nó quyết định đến hiệu quả của phân lớp. 2.4. Mô hình Entropy cực đại 2.4.1. Định nghĩa nguyên lý entropy cực đại Có rất nhiều thuật toán của phương pháp học giám sát đã được đưa ra để giải quyết bài toán phân lớp văn bản như giả thiết Naïve Bayes [Lewis, 1998; McCallum and Nigam, 1998; Sahami, 1996], K - người láng giềng gần nhất [Yang, 1999], máy hỗ trợ vector [Joachims, 1998; Dumais et al., 1998], boosting [Schapire and Singer, 1996], Các thuật toán học luật [Cohen and Singer, 1996; Slattery và Craven, 1998]. Tuy nhiên, trong số đó chưa có một thuật toán nào được chứng minh là làm tốt hơn các thuật toán khác trên nhiều miền ứng dụng. Sử dụng kỹ thuật Entropy cực đại cho bài toán phân lớp văn bản như là một cách thay thế các thuật toán đã được dùng trước đây. Entropy cực đại đã được sử dụng rộng rãi cho nhiều ngôn ngữ tự nhiên. Entropy cực đại đã chứng tỏ được là một thuật toán hiệu quả và cạnh tranh cao trong nhiều miền ứng dụng. Đối với bài toán phân lớp dữ liệu, Entropy cực đại là một kỹ thuật dùng để ước lượng xác suất các phân phối từ dữ liệu. Tư tưởng chủ đạo của nguyên lý Entropy cực đại là “mô hình phân phối đối với mỗi tập dữ liệu và tập các ràng buộc đi cùng phải đạt được độ cân bằng / đều nhất có thể” [15]. Tập dữ liệu học (tức là tập gồm các dữ liệu đã được gán nhãn) được sử dụng để tìm ra các ràng buộc cho mô hình, đó là cơ sở để ước lượng phân phối cho từng lớp cụ thể. Những ràng buộc này được thể hiện bởi các giá trị ước lượng được của các đặc trưng. Từ các ràng buộc sinh ra bởi tập dữ liệu này, mô hình sẽ tiến hành tính toán để có được một phân phối cho Entropy cực đại [10], [15]. Ví dụ một mô hình Entropy cực đại: “Giả sử với bộ phân lớp về lĩnh vực kinh tế trên báo VnEconomy có bốn lớp chính được chỉ ra là ngân_hàng, chứng_khoán, bất_động_sản, doanh_nghiệp. Các thống kê dữ liệu chỉ ra rằng trung bình 70% các tài liệu trong lớp ngân_hàng có chứa từ vay_vốn. Như vậy một cách trực quan có thể thấy ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 27 -  rằng nếu một tài liệu D có chứa từ vay_vốn thì xác suất được phân vào lớp ngân_hàng là 70% và xác suất phân vào ba lớp còn lại là 10% đối với mỗi lớp. Nếu tài liệu D không chứa từ vay_vốn thì xác suất phân phối của D là 25% đều cho mỗi lớp.” Trong ví dụ trên, “nếu tài liệu chứa cụm từ vay_vốn thì có xác suất phân vào lớp ngân_hàng là 70%” là một ràng buộc của mô hình. 2.4.2. Các ràng buộc và đặc trưng Trong nguyên lý Entropy cực đại, chúng ta sử dụng tập dữ liệu mẫu làm để thiết lập ràng buộc cho phân phối điều kiện. Với mỗi ràng buộc được mô tả bởi một đặc tính của tập dữ liệu học. Một đặc trưng trong mô hình Entropy cực đại được biểu diễn bởi một hàm fi(d, c), trong đó d là tài liệu và c là lớp. Entropy cực đại cho phép giới hạn mô hình phân phối để có thu các giá trị kỳ vọng cho mỗi đặc trưng của tập dữ liệu. Vì vậy, ta có thể đặt xác suất phân phối của dữ liệu d cho lớp c là P(c|d) thỏa mãn phương trình sau: Trong quá trình huấn luyện, phân phối tài liệu P(d) là không biết và chúng ta không cần quan tâm tới nó. Vì vậy, ta chỉ sử dụng tập dữ liệu mẫu như là một điều kiện để phân phối dữ liệu tuân theo ràng buộc sau: Như vậy khi sử dụng entropy cực đại, bước đầu tiên là cần xác định tập các hàm đặc tính sẽ sử dụng cho phân lớp. Sau đó, với mỗi đặc tính, ước lượng giá trị kỳ vọng thông qua tập dữ liệu học và tạo ra các ràng buộc cho mô hình phân phối. 2.4.3. Mô hình Entropy cực đại Mô hình xác suất Entropy cực đại cung cấp một cách đơn giản để kết hợp các đặc trưng của tài liệu trong những ngữ cảnh khác nhau để ước lượng xác suất của một số lớp xuất hiện cùng với một số ngữ cảnh này. Tư tưởng cơ bản của phương pháp Entropy cực đại là tìm ra một mô hình có phân phối xác suất thỏa mãn mọi ràng buộc quan sát được từ dữ liệu mà không đưa thêm bất kì một giả thiết nào khác. Theo nguyên lý Entropy cực đại, phân phối cần đáp ứng dữ liệu quan sát và làm cực đại độ đo Entropy có điều kiện: ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 28 -  ( ) ( ) ( ) ( ) , | log |≡ −∑ % c d H p p c p c d p d c ( )* a rg m a x ∈ = p C p H p Trong đó p* là phân xác suất tối ưu. Mô hình Entropy cực đại xây dựng các đặc trưng từ tập dữ liệu huấn luyện. Mỗi đặc trưng được biểu diễn dưới một hàm nhận một trong hai giá trị đúng hoặc sai. Tập các ràng buộc sẽ được thiết lập từ các đặc trưng này. Một ràng buộc là một điều kiện từ dữ liệu buộc mô hình phải thỏa mãn. Mỗi đặc trưng fi được gán cho một trọng số iλ . Khi đó, bài toán phân lớp được đưa về bài toán ước lượng xác suất có điều kiện: Trong đó Z(d) là biểu thức chuẩn hóa để đảm bảo điều kiện ( ) 1| =∑ dcp . Từ đó đưa ra công thức sau: 2.3.4. Entropy cực đại cho phân lớp văn bản Để áp dụng mô hình Entropy cực đại cho một miền, chúng ta cần phải chọn ra một tập các đặc trung để sử dụng thiết lập các ràng buộc. Đối với phân lớp văn bản với mô hình Entropy cực đại, chúng ta sử dụng số lượng từ như là các đặc trưng. Trong nghiên cứu này cho với mỗi từ kết hợp, ta đưa ra một đặc tính như sau: Trong đó, N(d, w) là số lần từ w xuất hiện trong tài liệu d, và N(d) là số lượng các từ có trong tài liệu d. Trong công thức này, nếu một từ xuất hiện thường xuyên trong một tài liệu, ta sẽ tính trọng số cho các cặp từ này và thấy rằng trọng số đó sẽ cao hơn so với trọng số của các từ ghép trong tài liệu. Trong hầu hết ngôn ngữ tự nhiên sử dụng Entropy cực đại thì các đặc trưng thường là đặc trưng nhị phân. Trong phân lớp văn bản, chúng ta mong muốn các đặc trưng được tính bằng số lần suất hiện của một từ trong một tài liệu có thể củng cố cho phân lớp. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 29 -  Một trong những khía cạnh đặc biệt của Entropy cực đại là nó không bị bất kỳ giả thuyết độc lập nào ràng buộc. Ví dụ, với cụm từ “Buenos Aires”, hai từ này hầu như luôn xuất hiện động thời cùng nhau.Với giả thiết Naïve Bayes sẽ đếm số từ xuất hiện hai lần trong cụm từ này. Mặt khác, Entropy cực đại sẽ giảm giá trị trọng số iλ của mỗi đặc trưng đi một nửa. Một trong những hệ của việc không phụ thuộc vào bất kỳ giả thuyết độc lập nào đó là các sơ đồ và các cụm từ có thể được thêm vào các đặc trưng của Entropy cực đại một cách dễ dàng mà không cần lo lắng rằng các đặc tính này chồng lên nhau. ¾ Ưu điểm của mô hình Entropy cực đại: - Cho phép khả năng hầu như không hạn chế trong việc biểu diễn các vấn đề phức tạp về tri thức thông qua dạng các hàm đặc trưng. - Có thể giải quyết nhiều dạng thuộc tính khác nhau. - Các giả thiết không cần phải độc lập với nhau. - Trọng số của các đặc trưng được xác định một cách tự động. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 30 -  Chương 3. BÀI TOÁN PHÂN LỚP VĂN BẢN TÀI CHÍNH NGÂN HÀNG TIẾNG VIỆT 3.1. Một số đặc trưng của dữ liệu tài chính ngân hàng trong tiếng Việt Luận văn tập trung nghiên cứu trên tập các văn bản về lĩnh vực tài chính ngân hàng Việt Nam với ngôn ngữ Tiếng Việt. Bất kỳ một ngôn ngữ nào cũng có các đặc trưng riêng, hơn nữa Tiếng Việt còn là ngôn ngữ rất đa dạng, phong phú về từ ngữ, ngữ pháp… Một số đặc điểm của Tiếng Việt được liệt kê dưới đây: - Tiếng Việt thuộc ngôn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm tách rời nhau và được thể hiện bằng một chữ viết. - Đặc điểm ngữ âm: Trong Tiếng Việt có một loại đơn vị đặc biệt gọi là “tiếng”. Về mặt ngữ âm mỗi tiếng là một âm tiết. - Đặc điểm từ vựng: mỗi tiếng, nói chung, là một yếu tố có nghĩa. Tiếng là đơn vị cơ sở của hệ thống các đơn vị có nghĩa của Tiếng Việt. Từ tiếng người ta tạo ra các đơn vị từ vựng khác để định danh sự vật, hiện tượng nhờ phương pháp ghép và láy từ... Vốn từ vựng tối thiểu của Tiếng Việt phần lớn là các từ đơn tiết (một âm tiết, một tiếng). Sự linh hoạt trong sử dụng, việc tạo ra các từ ngữ mới nột cách dễ dàng đã tạo điều kiện thuận lợi cho sự phát triển vốn từ, vừa phong phú về số lượng, vừa đa dạng trong hoạt động. Cùng một sự vật, hiện tượng, một hoạt động hay một đặc trưng, có thể được biểu thị theo nhiều cách khác nhau. - Đặc điểm ngữ pháp: Từ của Tiếng Việt không biến đổi hình thái khi kết hợp các từ để làm thành kết cấu như ngữ, câu Tiếng Việt rất coi trọng trật tự từ và hư từ. Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các quan hệ cú pháp. Trong Tiếng Việt, nói “Anh ta lại đến” là khác với nói “Lại đến anh ta”. Khi các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước giữ vai trò chính, từ đứng sau giữ vai trò phụ. Nhờ trật tự kết hợp từ mà ta thấy “cảm tình” khác với “tình cảm”. Trật tự chủ ngữ đứng trước, vị ngữ đứng sau là trật tự phổ biến của kết cấu câu Tiếng Việt. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 31 -  Phương thức hư từ cũng là phương pháp phổ biến trong Tiếng Việt. Nhờ hư từ mà tổ hợp từ “anh của em” khác với tổ hợp từ “anh và em” hay “anh vì em”. Ngoài những đặc điểm chung của Tiếng Việt, văn bản tài chính ngân hàng Việt Nam còn có những đặc điểm riêng, chẳng hạn có chứa những từ, cụm từ đặc trưng như: “ngân hàng”, “cho vay”, “lãi suất vay vốn”, “lãi suất tiết kiệm”, “cổ phiếu”, “thị trường tiền tệ”, “huy động vốn”… 3.2. Xây dựng một số lớp trong lĩnh vực tài chính ngân hàng Trong phần này, khóa luận sẽ đi xây dựng một tập các nhãn (lớp) trên lĩnh vực tài chính ngân hàng. Thông qua việc khảo sát dữ liệu về tài chính ngân hàng được thu thập từ các trang Web và quá trình nghiên cứu về nghiệp vụ ngân hàng, tài chính Việt Nam [6], khóa luận xin đề xuất một tập các nhãn (lớp) để đưa ra thử nghiệm ban đầu, với những khái niệm cơ bản sau: ƒ Huy động vốn: Ngân hàng được huy động vốn dưới các hình thức sau: - Nhận tiền gửi của tổ chức kinh tế, cá nhân và các tổ chức tín dụng khác dưới hình thức tiền gửi không kỳ hạn, tiền gửi có kỳ hạn, tiền gửi tiết kiệm và các loại tiền gửi khác. - Phát hành chứng chỉ tiền gửi, trái phiếu và giấy tờ có giá khác để huy động vốn của tổ chức, cá nhân trong nước và nước ngoài. - Đi vay vốn của các tổ chức tín dụng trong và ngoài nước. - Vay vốn ngắn hạn của Ngân hàng Nhà Nước. - Các hình thức huy động vốn khác theo quy định của Ngân hàng Nhà Nước. ¾ Dữ liệu thuộc lớp huy động vốn gồm những văn bản có nội dung liên quan tới một trong những hoạt động huy động vốn vừa được nêu như: thông tin về lãi suất gửi tiền tiết kiệm, các hình thức vay vốn của ngân hàng đối với các tổ chức tín dụng khác… ƒ Tín dụng: Ngân hàng thương mại được cấp tín dụng cho tổ chức, cá nhân dưới các hình thức cho vay, chiết khấu thương phiếu và giấy tờ có giá khác, bảo lãnh, cho thuê tài chính và các hình thức khác theo quy định của Ngân hàng Nhà Nước. Trong các hoạt động cấp tín dụng, cho vay là hoạt động quan trọng và chiếm tỷ trọng lớn nhất. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 32 -  - Cho vay: Ngân hàng thương mại được cho các tổ chức, cá nhân vay vốn dưới các hình thức sau: o Cho vay ngắn hạn (dưới 12 tháng) nhằm đáp ứng nhu cầu vốn cho sản xuất, kinh doanh, dịch vụ và đời sống. o Cho vay trung hạn, dài hạn (trên 12 tháng) để thực hiện các dự án đầu tư phát triển sản xuất, kinh doanh, dịch vụ và đời sống. - Bảo lãnh: Ngân hàng thương mại được bảo lãnh vay, bảo lãnh thanh toán, bảo lãnh thực hiện hợp đồng, bảo lãnh đấu thầu và các hình thức bảo lãnh ngân hàng khác bằng uy tín và bằng khả năng tài chính của mình đối với một khách hàng thương mại không được vượt quá tỷ lệ so với vốn tự có của ngân hàng thương mại. - Chiết khấu: Ngân hàng thương mại được chiết khấu thương phiếu và các giấy tờ có giá ngắn hạn khác đối với tổ chức, cá nhân và có thể tái chiết khấu các thương phiếu và các giấy tờ có giá ngắn hạn khác đối với tổ chức tín dụng khác. - Cho thuê tài chính: Ngân hàng thương mại được hoạt động cho thuê tài chính nhưng phải thành lập công ty cho thuê tài chính riêng. Việc thành lập, tổ chức và hoạt động của công ty cho thuê tài chính thực hiện theo Nghị định của Chính Phủ về tổ chức và hoạt động của công ty cho thuê tài chính. ¾ Dữ liệu thuộc lớp tín dụng gồm những văn bản mang thông tin về hoạt động cho vay vốn, bảo lãnh, chiết khấu, cho thuê tài chính của ngân hàng đối với cá nhân và tổ chức. ƒ Dịch vụ thanh toán: Để thực hiện các dịch vụ thanh toán giữa các doanh nghiệp thông qua ngân hàng, ngân hàng thương mại được mở tài khoản tiền gửi thanh toán cho khách hàng trong và ngoài nước. Hoạt động dịch vụ thanh toán của ngân hàng thương mại bao gồm các hoạt động sau: - Cung cấp các phương tiện thanh toán như thẻ ghi nợ (debit card), thẻ tín dụng (credit card) có phạm vi thanh toán có thể thực thanh toán trong và ngoài nước. - Thực hiện các dịch vụ thanh toán theo nhu cầu của khách hàng (ủy nhiệm chi, thanh toán lương, thanh toán hóa đơn,…). ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 33 -  - Thực hiện dịch vụ thu hộ và chi hộ trong nội bộ ngân hàng hoặc liên ngân hàng trong nước. - Thực hiện các dịch vụ thanh toán khác theo qui định của Ngân hàng Nhà Nước. - Thực hiện các dịch vụ thanh toán quốc tế đối với khách hàng mở thư tín dụng (letter credit). - Thực hiện dịch vụ chuyển tiền trong và ngoài nước. ¾ Dữ liệu thuộc lớp dịch vụ thanh toán gồm những văn bản mang thông tin về các hoạt động dịch vụ thanh toán của ngân hàng như: cung cấp các phương tiện thanh toán, các dịch vụ liên quan đến thanh toán như đã nêu ở trên… ƒ Ngoại tệ: Gồm các thông tin về việc ngân hàng thương mại trực tiếp kinh doanh hoặc thành lập công ty trực thuộc để kinh doanh ngoại hối, tiền tệ và vàng trên thị trường trong nước và thị trường quốc tế. ƒ Chứng khoán: Tất cả các ngân hàng thương mại muốn kinh doanh chứng khoán đều phải lập công ty trực thuộc ngân hàng. Chẳng hạn, các ngân hàng ngoại quốc doanh như Vietcombank, Incombank, Ngân hàng Đầu tư và Phát triển, Ngân hàng Nông nghiệp và phát triển nông thôn,… đều có thành lập công ty chứng khoán. Cơ sở hạ tầng của thị trường chứng khoán bao gồm những hệ thống và tổ chức cung cấp phương tiện cho giao dịch, thanh toán, ký gửi và lưu ký cổ phiếu, trái phiếu. Ngoài ra, còn bao gồm cả những quy định pháp lý làm cơ sở cho giao dịch và quản lý thị trường cổ phiếu. ¾ Dữ liệu thuộc lớp chứng khoán gồm những văn bản mang thông tin về giao dịch, thanh toán, ký gửi, lưu ký cổ phiếu, trái phiếu của ngân hàng trên thị trường chứng khoán. 3.3. Bài toán phân lớp văn bản tài chính ngân hàng trong Tiếng Việt 3.3.1. Phát biểu bài toán: - Input: một tập văn bản (text) dữ liệu thông tin về tài chính ngân hàng. - Output: Phân loại từng văn bản vào các lớp tương ứng. Ví dụ, đưa vào một văn bản có chứa nhiều cụm từ đặc trưng như “cho vay vốn” thì chương trình phải xác định được đặc trưng này và xếp văn bản này vào lớp tín dụng. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 34 -  3.3.2. Phương pháp phân lớp Như đã trình bày ở chương 3, có rất nhiều phương pháp để giải quyết bài toán phân lớp văn bản như: K người láng giềng gần nhất, Cây quyết định, Máy hỗ trợ vector (SVM), Mô hình Entropy cực đại. Tùy đặc điểm của từng miền dữ liệu mà mỗi phương pháp có những ưu nhược điểm riêng. Tuy nhiên, Dựa trên kết quả thực nghiệm của Hacioglu [25] và Li [22], Luận văn của Nguyễn Thị Hương Thảo [1], Trần Minh Tuấn [2] đã cho thấy sử dụng phương pháp SVM, Entropy vào bài toán phân lớp văn bản cho kết quả rất khả quan. Mặt khác, trong quá trình nghiên cứu các thuật toán đã nêu ở chương 2, mô hình Entropy cực đại có ưu điểm hơn so với phương pháp cây quyết định ở chỗ: việc ước lượng tham số trong mô hình Entropy cực đại không cần phải phân chia dữ liệu dẫn tới không xảy ra hiện tượng phân mảnh dữ liệu, do đó không cần tới thuật toán làm mịn để chặt bớt đi các nhánh dữ liệu dư thừa, thưa thớt . So với phương pháp SVM thì phương pháp Entropy cực đại có một ưu điểm lớn là việc sử dụng các đặc trưng linh hoạt, dễ dàng khai báo các thuộc tính. Dựa vào kết quả thực nghiệm của khóa luận Trần Minh Tuấn [2] còn cho thấy, đối với miền dữ liệu Tiếng Việt thì phương pháp Entropy cực đại cho kết quả khả quan hơn phương pháp SVM. Do có những ưu điểm so với các phương pháp đã trình bày, phần tiếp theo luận văn sẽ áp dụng mô hình Entropy cực đại cho bài toán phân lớp văn bản tài chính ngân hàng Tiếng Việt. 3.3.3. Mô hình của bài toán phân lớp văn bản tài chính ngân hàng Để xây dựng được bài toán phân lớp văn bản dữ liệu về tài chính ngân hàng như trên, trước hết chúng ta cần thu thập dữ liệu và thực hiện việc tách từ trong các văn bản, loại bỏ từ dừng và biểu diễn các văn bản dưới dạng đặc trưng đầu vào cho mô hình Entropy cực đại. Các bước trong quá trình phân lớp văn bản được thực hiện như sau: ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 35 -  Hình 6. Mô hình bài toán phân lớp dữ liệu tài chính ngân hàng Quá trình tiền xử lý (preprocessing) dữ liệu thông tin về tài chính ngân hàng gồm cách bước sau: - Tách từ: Với một tập văn bản đầu vào, thông qua module tách từ, các từ trong văn bản sẽ được nhận biết, mỗi từ sẽ được biểu diễn trong một cặp dấu ngoặc vuông ( [ ] ) và cách nhau bởi một kí tự trắng. Module tách từ sẽ giúp chúng ta phân biệt được những từ có nghĩa, là cơ sở để loại bỏ từ dừng. Ví dụ, với từ “cao cấp”, nếu văn bản không qua xử lý tách từ và trong bộ từ dừng có từ Tập văn bản đầu vào Module tách từ Tiếng Việt Module loại bỏ từ dừng Biểu diễn tất cả các văn bản dưới dạng 1 văn bản đặc trưng Với mỗi một dòng trong văn bản đặc trưng Module phân lớp văn bản Tập văn bản kết quả Văn bản đã được phân lớp Lặp hết các dòng trong văn bản đặc trưng ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 36 -  “cao” thì khi qua xử lý loại bỏ từ dừng thì từ “cao” bị loại bỏ ngay lập tức mà không cần biết tới nghĩa của nó khi đi cùng từ đằng sau. Ngược lại, nếu văn bản được xử lý tách từ thì sẽ ko có trường hợp loại bỏ này xảy ra. Module tách từ làm cho quá trình loại bỏ từ dừng chính xác hơn. Ví dụ, nội dung của một đoạn văn bản dữ liệu về tài chính ngân hàng sau khi qua bộ tách từ: [Đáy] [lãi suất] [cho vay] [về] [mức] [12%] / [năm][Lãi suất] [cho vay] [bằng] [đồng] [Việt Nam] [vừa] [thiết lập] [đáy] [mới] [ở] [mức] [12%] / [năm] [sau] [khi] [Ngân hàng] [Nhà nước] [công bố] [hạ] [lãi suất] [cơ bản] [VND] [xuống] [còn] [11%] / [năm] .[Vietcombank] [tạo] [đáy] [lãi suất] [cho vay] [mới] [ở] [mức] [12%] / [năm][Từ] [nhiều] [ngày nay] , [các] [ngân hàng] [thương mại] [đã] [cùng] [vào] [cuộc đua] [giảm] [lãi suất] [cho] [vay] [nhằm] [giải] [ngân] [nguồn] [tiền] [đang] [được] [đánh giá] [là] [khá] [dư thừa] [trong] [kho]. - Loại bỏ từ dừng: Từ dừng (stop-words) dùng để chỉ các từ mà xuất hiện quá nhiều trong các văn bản của toàn tập kết quả, thường thì không giúp ích gì trong việc phân biệt nội dung của các tài liệu. Trong tiếng Anh, có nhiều từ chỉ dùng để phục vụ cho biểu diễn cấu trúc chứ không biểu đạt nội dung của nó, như là “a”, “the” (mạo từ), “in” (giới từ), “but” (liên từ), động từ phổ biến có dạng “to”, “be” và một số trạng từ và tính từ đặc biệt được xem là những từ dừng. Trong Tiếng Việt, các từ “và”, “hoặc”, “nhưng”, “cũng”… xuất hiện rất nhiều trong các văn bản, cũng được coi là các từ dừng. Luận văn tập trung nghiên cứu thực nghiệm trên tập dữ liệu tài chính ngân hàng, cho thấy những con số, dấu câu không có ý nghĩa đối với quá trình phân lớp nên cũng coi đó là những từ dừng. Danh sách từ dừng được sử dụng đối với văn bản tài chính ngân hàng trong luận văn này sẽ được trình bày cuối luận văn. Vì đặc điểm của từ dừng nên chúng được loại bỏ mà không ảnh hưởng đến các công việc biểu diễn văn bản tiếp theo. Hơn thế nữa giai đoạn xử lý loại bỏ từ dừng sẽ làm cho văn bản kết quả giữ lại được các từ đặc trưng, loại bỏ được những từ gây nhiễu. Tách từ và loại bỏ từ dừng là hai bước trong quá trình tiền xử lý dữ liệu đầu vào cho bộ phân lớp, làm cho hiệu suất của quá trình phân lớp tăng. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 37 -  Các văn bản sau khi được xử lý tách từ sẽ là đầu vào cho bước loại bỏ từ dừng. Thông qua modulo loại bỏ từ dừng, các tiếng trong một từ sẽ được cách nhau bởi một kí tự gạch dưới ( _ ) và các từ sẽ cách nhau bởi một kí tự trắng. Ví dụ, nội dung của một đoạn văn bản sau khi loại bỏ từ dừng: lãi_suất cho_vay mức Lãi_suất cho_vay đồng Việt_Nam thiết_lập mức Ngân_hàng Nhà_nước công_bố hạ lãi_suất cơ_bản VND xuống Vietcombank tạo đáy lãi_suất cho_vay mức Từ ngày_nay ngân_hàng thương_mại cuộc_đua giảm lãi_suất vay nhằm giải ngân nguồn tiền đánh_giá khá dư_thừa kho Mức lãi_suất cho_vay ưu_đãi đáy cũ thiết_lập - Biểu diễn tất cả các văn bản dưới dạng 1 văn bản đặc trưng: Tất cả các văn bản sau khi đã được tách từ và loại bỏ từ dừng sẽ được biểu diễn dưới dạng một văn bản đặc trưng đầu vào cho bộ phân lớp như sau: nội dung của mỗi văn bản được biểu diễn trên một dòng và từ cuối cùng trên dòng đó là tên lớp. Ví dụ: Nội dung văn bản A Tên_lớp_1 Nội dung văn bản B Tên_lớp_2 … ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 38 -  Chương 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ 4.1. Dữ liệu và chương trình Dữ liệu dùng để thực nghiệm cho bộ phân lớp văn bản về tài chính ngân hàng là các văn bản được lấy từ trang Web: Tập dữ liệu có tất cả 1075 tài liệu. Toàn bộ tập dữ liệu của thử nghiệm đều được gán nhãn bằng tay. Tập dữ liệu được chia thành hai tập con rời nhau, tập dữ liệu huấn luyện và tập dữ liệu kiểm tra, theo tỉ lệ tập dữ liệu huấn luyện : tập dữ liệu kiểm tra bằng 2:1. Bảng 1. Phân bố dữ liệu học và kiểm tra Tổng số tài liệu 1075 Tập dữ liệu học 717 Tập dữ liệu kiểm tra 358 Các phân lớp của dữ liệu được xậy dựng như đã giới thiệu ở chương 3, mục 3.2 bao gồm 5 lớp (huy động vốn, tín dụng, dịch vụ thanh toán, ngoại tệ và chứng khoán). Dữ liệu dùng cho huấn luyện cùng số lượng tài liệu cho mỗi lớp được mô tả trong Bảng 2. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 39 -  Bảng 2. Tập dữ liệu huấn luyện STT Phân lớp Ký hiệu Số lượng tài liệu 1 Ngoại tệ NgoaiTe 273 2 Huy động vốn HuyDongVon 104 3 Dịch vụ thanh toán DichVuThanhToan 60 4 Chứng khoán ChungKhoan 137 5 Tín dụng TinDung 143 Tổng số: 717 Tập dữ liệu dùng để kiểm tra được mô tả trong bảng 3, số lượng tài liệu của mỗi lớp tỉ lệ với số lượng tài liệu trong tập dữ liệu dùng để huấn luyện. Bảng 3. Tập dữ liệu kiểm tra STT Phân lớp Ký hiệu Số lượng tài liệu 1 Ngoại tệ NgoaiTe 150 2 Huy động vốn HuyDongVon 34 3 Dich vụ thanh toán DichVuThanhToan 34 4 Chứng khoán ChungKhoan 70 5 Tín dụng TinDung 70 Tổng số: 358 4.2. Môi trường thực nghiệm Môi trường thực nghiệm: hệ điều hành Windows XP, vi xử lý Pentium 4, RAM 256. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 40 -  Khóa luận xây dựng chương trình thực hành phân lớp được viết trên ngôn ngữ java, môi trường Jcreator, Elipse. Chương trình này tích hợp module tiền xử lý văn bản (do khóa luận xây dựng) và sử dụng thư viện của tác giả Phan, X.H [23]. 4.3. Thiết kế và kết quả thực nghiệm Khóa luận thử nghiệm theo mô hình nguyên lý Entropy cực đại. 4.3.1. Thiết lập thông số cho Entropy cực đại Với thuật toán Entropy cực đại, khóa luận sử dụng thư viện của tác giả Phan Xuân Hiếu [23], việc sử dụng đòi hỏi phải thiết lập một số thông số cho mô hình. Các thông số này được lựa chọn qua nhiều lần thử nghiệm, chi tiết được mô tả ở bảng 4. Bảng 4. Tham số huấn luyện mô hình Entropy cực đại Tham số Giá trị Mô tả numIterations 10 Số bước lặp trong quá trình huấn luyện. fRareThreshold 0 Các mệnh đề mô tả thông tin ngữ cảnh phải xuất hiện nhiều hơn số này thì sẽ được dùng để xây dựng các đặc trưng. cpRareThreshold 0 Các đặc trưng xuất hiện nhiều hơn số này thì sẽ không bị loại bỏ khỏi tập dữ liệu huấn luyện. 4.3.2. Kết quả thực nghiệm Tiến hành thực nghiệm trên tập dữ liệu huấn luyện với số lượng bước lặp là 10. Các kết quả phân lớp thu được khá khả quan với thời gian khoảng 0.4594 giây/lần và được mô tả trong một số bảng biểu và đồ thị sau. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 41 -  Bảng 5. Kết quả 10 lần huấn luyện với Entropy cực đại Độ chính xác Độ hồi tưởng F1 Bước lặp Thời gian Avg 1 Avg 2 Avg 1 Avg 2 Avg1 Avg2 1 0.766 81.04 55.87 39.43 55.87 53.05 55.87 2 0.485 81.95 81.56 74.95 81.56 78.29 81.56 3 0.453 82.99 82.68 76.39 82.68 79.56 82.68 4 0.406 84.59 87.15 84.75 87.15 84.67 87.15 5 0.422 86.38 89.39 86.43 89.39 86.40 89.39 6 0.422 87.64 90.22 86.98 90.22 87.31 90.22 7 0.39 84.67 87.43 84.28 87.43 84.48 87.43 8 0.422 86.49 88.83 86.46 88.83 86.48 88.83 9 0.39 87.73 89.66 87.47 89.66 87.60 89.66 10 0.407 86.73 88.83 86.92 88.83 86.82 88.83 Trung bình 0.4563 84.821 84.162 79.406 84.162 81.466 84.162 ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 42 -  Qua bảng trên, cho thấy kết quả khả quan nhất là ở bước lặp thứ 6 với độ đo F1 đạt 90.22% chi tiết bước lặp này như sau: Bảng 6. Kết quả của bước lặp thứ 6 Tên lớp Độ chính xác Độ hồi tưởng F1 NgoaiTe 96.64 96.00 96.32 HuyDongVon 71.43 73.53 72.46 DichVuThanhToan 96.77 88.24 92.31 ChungKhoan 87.84 92.86 90.28 TinDung 85.51 84.29 84.89 Avg1 87.64 86.98 87.31 Avg2 90.22 90.22 90.22 Trong bảng kết quả trên thì kết quả của phân lớp HuyDongVon là kém nhất với độ đo chính xác là 72.46% và tốt nhất là phân lớp NgoaiTe với độ đo chính xác là 96.32%. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 43 -  0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 Bước lặp Đ ộ đo F 1 F1-Avg2 F1-Avg1 Hình 7. Đồ thị biểu diễn sự phụ thuộc của độ đo F1 vào số lần lặp 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 Bước lặp Đ ộ ch ín h xá c củ a ph ân lớ p Độ chính xác Độ hồi tưởng F1 Hình 8. Tổng hợp độ đo qua 10 lần huấn luyện ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 44 -  96.32 72.46 92.31 90.28 84.89 0 20 40 60 80 100 120 Ng oa iTe Hu yD on gV on Di ch Vu Th an hT oa n Ch un gK ho an Tin Du ng Lớp Đ ộ đo F 1 Hình 9. Biểu đồ biểu diễn độ đo F1 của các lớp trong lần lặp thứ 6 4.4. Đánh giá kết quả thực nghiệm Việc tiến hành thực nghiệm trên tập dữ liệu huấn luyện là 717 dữ liệu cho 5 phân lớp cho kết quả tốt về độ đo F1 là 90.22%. Cả 5 bộ phân lớp đều cho độ đo F1 gần 90%, đặc biệt, bộ phân lớp NgoaiTe đạt kết quả rất cao là 96.32% cho cả độ chính xác và độ hồi tưởng. Bộ phân lớp HuyDongVon thu được kết quả thấp nhất với độ đo F1 là 72.46%. Do số lượng dữ liệu mẫu cho từng lớp khá cân bằng nhau nên khả năng đoán nhận của bộ phân lớp là khá tốt. Nhưng muốn khả năng này cao hơn nữa thì tập dữ liệu huấn luyện cần gia tăng thêm về số lượng, đảm bảo cung cấp đầy đủ các ràng buộc từ dữ liệu cho mô hình. Như đã trình bày ở mục 2.4, tư tưởng chủ đạo của nguyên lý Entropy cực đại là thay vì thêm vào các ràng buộc mới, mô hình tự tìm ra trong dữ liệu (tập câu hỏi mẫu) những ràng buộc và đặc trưng riêng cho từng phân lớp. Điều này làm cho sự phân lớp trong khi sử dụng mô hình Entropy cực đại được đảm bảo cả khi tập dữ liệu không có số lượng quá lớn và mỗi tài liệu chỉ chứa ít đặc trưng. Từ kết quả của thực nghiệm cho thấy khi xây dựng bộ phân lớp văn bản tiếng Việt sử dụng mô hình Entropy cực đại cho kết quả rất tốt. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 45 -  KẾT LUẬN Từ việc nghiên cứu lý thuyết và kết quả thực nghiệm có thể khẳng định rằng bài toán phân lớp văn bản thực sự có vai trò ý nghĩa rất quan trọng trong việc tổ chức, quản lý cũng như tìm kiếm thông tin trên nguồn tài nguyên lớn, đặc biệt với nguồn tài nguyên về lĩnh vực tài chính ngân hàng. Sự đa dạng của các thuật toán phân lớp dữ liệu làm cho việc lựa chọn thuật toán để xây dựng module phân lớp văn bản cho từng ngôn ngữ trở nên khó khăn hơn. Khóa luận tiếp cận các vấn đề nói trên và nghiên cứu các thuật toán phổ biến hiện nay, từ đó đưa ra phương pháp và thuật toán áp dụng vào phân lớp dữ liệu ngân hàng tài chính trong tiếng Việt. Về mặt nội dung, khóa luận đã đạt được những kết quả sau: - Nghiên cứu về bài toán phân lớp văn bản: khái niệm, mô hình, đánh giá phân lớp. Luận văn đã tập hợp và trình bày một số phương pháp phổ biến nhất hiện nay như k người láng giềng gần nhất, mô hình cây quyết định, mô hình Entropy cực đại, SVM. Sau đó trình bày ưu nhược điểm của từng phương pháp, từ đó đưa ra quyết định sử dụng mô hình entropy cực đại khi áp dụng cho tiếng Việt. - Xây dựng nhãn / lớp cho văn bản tài chính ngân hàng trong tiếng Việt. - Xây dựng chương trình thi hành phân lớp văn bản được viết trên ngôn ngữ Java, môi trường Eclipse được tích hợp từ module tiền xử lý văn bản (do khóa luận xây dựng) và module phân lớp (khai thác mã nguồn bộ phân lớp Entropy cực đại). Kết quả thực nghiệm trên tập dữ liệu về lĩnh vực tài chính ngân hàng được crawler từ Web cho thấy tính khả thi của chương trình phân lớp văn bản sử dụng phương pháp Entropy cực đại với độ đo F1 đạt 90.22%. Bên cạnh đó, do thời gian và kiến thức có hạn, khóa luận vẫn còn một vài hạn chế sau: - Chương trình sử dụng thuật toán Entropy cực đại cho bài toán phân lớp văn bản mới thi hành trên một bộ dữ liệu tiếng Việt nên chưa đối sánh kết quả trên nhiều bộ dữ liệu. Chưa thi hành nhiều thuật toán để chọn được phương pháp tốt. Trong tương lại, khóa luận sẽ tiếp tục hoàn thiện mặt hạn chế đã đưa ra đó là sử dụng một số thuật toán phân lớp khác với Entropy cực đại để tìm ra được thuật toán hiệu nhất đối với bài toán phân lớp dữ liệu tiếng Việt. Đồng thời, thử nghiệm trên nhiều bộ dữ liệu tiếng Việt khác nhau. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 46 -  TÀI LIỆU THAM KHẢO Tài liệu Tiếng Việt [1]. Nguyễn Thị Hương Thảo, “Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng”, Khóa luận tốt nghiệp đại học, Đại học Công nghệ, ĐHQGHN, 2006. [2]. Nguyễn Minh Tuấn, “Phân lớp câu hỏi hướng tới tìm kiếm ngữ nghĩa Tiếng Việt trong lĩnh vực y tế ”, Khóa luận tốt nghiệp đại học, Đại học Công Nghệ, ĐHQGHN, 2008. Tài liệu Tiếng Anh [3]. Aixin Sun, Ee-Peng Lim. Hierarchical Text Classification and Evaluation. Proceedings of the 2001 IEEE International Conference on Data Mining (ICDM 2001) Pages 521-528, California, USA, November 2001. [4]. Decision Tree, Analysis mindtools.com [5]. T.M.Michell, Machine Learning, Mc Graw Hill [6]. Nghiệp vụ ngân hàng. TS. Nguyễn Minh Kiều. Trường Đại Học Kinh Tế TPHCM. Nhà xuất bản Thống Kê, tháng 12-2005. [7]. David J.C. MacKay. Information Theory, Inference, and Learning Algorthms Cambridge: Cambridge University Press, 2003. ISBN 0521642981 [8]. “Text Classification from Labeled and Unlabeled Documents using EM”. Machine Learning. Kluwer Academic Publishers, Boston. Manufactured in The Netherlands. [9]. “An Extensive Empirical Study of Feature Selection Metrics for Text Classification”. George Forman, Intelligent Enterprise Technology Laboratory. HP Laboratories Palo Alto, HPL-2002-147 (R.1), November 20th , 2002*. [10]. K. Nigam, J. Lafferty, and A. McCallum, "Using maximunm Entropy for text classification", Proceeding of the 16th International Joint Conference Workshop on Machine Learning for Information Filtering: 61-67 Stockholm, Sweden, 1999. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 47 -  [11]. “Support Vector Machine Active Learning with Applications to Text Classification”. Simon Tong and Daphne Koller. [12]. Lewis, D. and W.Gale: 1994, “A Sequential Algorithm for Training Text Classifiers”. In: Proceedings of the Seventeenth Annual International ACM- SIGIR Conference on Research and Development in Information Retrieval.pp. 3-12, Springer-Verlag. [13]. Soumen Chakrabarti. Mining the web- discovering knowledge from Hypertext Data Morgan Kaufman Publishers, trang 183-188. [14]. Pierre Baldi, Paolo Frasconi, Padhraic Smyth. Modeling the Internet and the Web: Probabilistic Methods and Algorithms. Published by John Wiley & Sons Ltd, The Southern Gate, Chichester West Sussex PO19 8SQ, England - 2003. [15]. Nguyen Viet Cuong, Nguyen Thi Thuy Linh Ha, Quang Thuy and Phan Xuan Hieu (2006). A Maximum Entropy Model for Text Classification. The International Conference on Internet Information Retrieval 2006:134- 139, Hankuk Aviation University, December 6, 2006, Goyang-si, Korea. [16]. Sebastiani, F.:2001, “Machine Learning in Automated Text Categorisation”. Technical Report IEI-B4-31-1999, Istituto di Elaborazione dell’Informazione. [17]. Svetlane Kiritchenko. Hierarchical Text Categorization and Its Application to Bioinformatics. Ph.D thesis in Computer Science – School of Information Technology and Engineering Faculty of Engineering University of Ottawa, Canada 2005. [18]. The Kluwer international Series in Engineering and Computer Science. “Data mining in finance”. Advances in Relational and Hybrid Methods. Boris Kovalerchuk, Central Washington University, USA and EvgenII Vityaev, Instutue of Mathematics Russian Academy of Sciences, Russia. [19]. “Classification of Text Documents”. Department of Computer Science and Engineering, Michigan State University, East Lansing, Michigan, USA. [20]. “Flexible Text Classification for Financia, ApplicationL The Facile Systeml”, Fabio Ciravegna and Luca Gilardoni and Alberto Lavelli. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 48 -  [21]. “The Effect of Financial Statement Classification of Hybrid Financial Instrucments on Financial Analysts’s Stock Price Judgments”. Patrick E.Hopkis. [22]. Li, X. & Roth, D. “Learning Question Classifiers”, Proceedings of the 19th International Conference on Computational Linguistics (COLING):556– 562, 2002. [23]. Phan, X.H, “JTextPro: A Java-based Text Processing Toolkit”, [24]. Thorsten Joachims, SVM multiclass Multi-Class Support Vector Machine, Cornell University Department of Computer Science. [25]. Kadri Hacioglu and Wayne Ward. "Question Classification with Support Vector Machines and Error Correcting Codes". Proceedings of HLT- NAACL2003:28-30, Edmonton, Alberta, Canada, May 2003. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 49 -  DANH SÁCH CÁC TỪ DỪNG Danh sách các từ dùng được sử dụng trong thực nghiệm: Nhận, rằng, cao, nhà, quá, riêng, gì, muốn, rồi, số, thấy, hay, lên, lần, nào, qua, bằng, điều, biết, lớn, khác, vừa, nếu, thời gian, họ, từng, đây, tháng, trước, chính, cả, việc, chưa, do, nói, ra, nên, đều, đi, tới, tôi, có thể, cùng, vì, làm, lại, mới, ngày, đó, vẫn, mình, chỉ, thì, đang, còn, bị, mà, năm, nhất, hơn, sau, ông, rất, anh, phải, như, trên, tại, theo, khi, nhưng, vào, đến, nhiều, người, từ, sẽ, ở, cũng, không, về, để, này, những một, các, cho, được, với, có, trong, đã, là, và, của, ảnh. Ngoài ra thì một số literal không có ý nghĩa trong văn bản khi tiến hành phân lớp cũng được loại bỏ: {, }, “, “, (, ), /, \, :, -, _, ., ?, ,.