Khóa luận 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

c thuộc tính mới (ví dụ các khái niệm) để thay thế cho một nhóm các thuộc tính thông qua kỹ thuật phân cụm. Nhóm các từ có sự giống nhau về ngữ nghĩa sẽ được xem là một thuộc tính mới thay thế cho các từ đơn lẻ. Với phương pháp này, cần xác định độ tương tự giữa các từ và áp dụng các kỹ thuật phân cụm như k người láng giềng gần nhất. 1.3.4. Đánh giá 1.3.4.1. Đánh giá cho bài toán phân lớp Đánh giá kết quả phương pháp phân lớp văn bản có thể được tính toán theo nhiều cách khác nhau. Theo khảo sát của Sebastiani [3], độ đo phổ biến nhất được sử dụng để đánh giá phân lớp là độ hồi tưởng và độ chính xác. Kí hiệu: Dữ liệu thực Lớp Ci Thuộc lớp Ci Không thuộc lớp Ci Thuộc lớp Ci TPi TNi Dự đoán Không thuộc lớp Ci FPi FNi Trong đó: - TPi (true positives): số lượng ví dụ dương được thuật toán phân đúng vào lớp Ci. - TNi (true negatives): số lượng ví dụ âm được thuật toán phân đúng vào lớp Ci. - FPi (false positives): số lượng ví dụ dương được thuật toán phân sai vào Ci. - FNi (false negatives): số lượng ví dụ âm được thuật toán phân sai vào Ci. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 13 -  Độ chính xác Pri của lớp Ci là tỷ lệ số ví dụ dương được thuật toán phân lớp cho giá trị đúng trên tổng số ví dụ được thuật toán phân lớp vào lớp iC : ii i i TNTP TP +=Pr Độ hồi tưởng iRe của lớp iC là tỷ lệ số ví dụ dương được thuật toán phân lớp cho giá trị đúng trên tổng số ví dụ dương thực sự thuộc lớp iC : ii i i FPTP TP +=Re Dựa vào độ chính xác và độ hồi tưởng chuẩn của mỗi lớp, độ chính xác và độ hồi tưởng cho toàn bộ các lớp, tức là { }mCCC ,...,, 21 có thể thu được bằng hai cách: cực tiểu trung bình (Micro-Average) và cực đại trung bình (Macro-Average). - Microaveraging: 1 1 ˆ ( ) m i i m i i i TP Pr TP TN µ = = = + ∑ ∑ 1 1 ˆ ( ) m i i m i i i TP Re TP FP µ = = = + ∑ ∑ - Macroaveraging: 1ˆ m i M i Pr Pr m == ∑ 1ˆ m i M i Re Re m == ∑ Độ chính xác và độ hồi tưởng nếu sử dụng riêng biệt thì chưa đánh giá được năng lực của bộ phân lớp. Vì vậy, đánh giá bộ phân lớp văn bản thường được đo bằng tổ hợp của hai độ đo trên. Các độ đo phổ biến của tổ hợp hai độ đo này là: - Break-Even Point (BEP): BEP được đề xuất bởi Lewis [3], xác định điểm mà tại đó độ chính xác và độ hồi tưởng bằng nhau. Tuy nhiên, trong một số trường hợp không thể xác định được BEP. Ví dụ, nếu chỉ có vài dữ liệu dương và rất nhiều dữ liệu âm, khi đó độ hồi tưởng sẽ cao hơn rất nhiều so với độ chính xác, khi đó không thể xác định được BEP. ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 14 -  - Độ đo βF : độ đo βF được đề xuất bởi Rijbergen [3]. Nó là độ đo đơn giản được tính từ độ chính xác và độ hồi tưởng phụ thuộc vào độ quan trọng mà người dùng định nghĩa ( )β . Thông thường, 1=β . Công thức tính độ đo βF là: ( ) RePr. Re.Pr.1 2 2 + += β β βF Trong trường hợp 1=β chúng ta có F1 là độ đo thông dụng nhất trong việc đánh giá năng lực của các bộ phân lớp. - Độ chính xác trung bình của 11 điểm: độ chính xác là nội suy của 11 điểm mà độ hồi tưởng là 0.0, 0.1, … , 1.0. Độ đo này được sử dụng khi phương pháp phân lớp tính hạng tài liệu phù hợp với một lớp hoặc lớp tương tự với một tài liệu. Bên cạnh độ chính xác và độ hồi tưởng, một số độ đo phổ biến khác cũng được sử dụng như: tỉ lệ đúng (Accuracy) và tỉ lệ lỗi (Error) kí hiệu là iAc và iEr của lớp iC : iii ii i FNFPTP FNTP Ac ++ += i iiii ii i AcFNFPTNTP TNFP Er −=+++ += 1 1.3.4.2. Đánh giá dựa vào độ tương tự Nếu phương pháp A và B đều không phân tài liệu vào đúng lớp iC của nó, nhưng phương pháp A phân vào lớp tương tự với lớp iC hơn thì phương pháp A được đánh giá là tốt hơn so với phương pháp B. Vì vậy, Sun và Lim [3] đã mở rộng định nghĩa độ chính xác và độ hồi tưởng chuẩn để đánh giá bộ phân lớp A và B. Độ tương tự giữa hai lớp iC và kC , kí hiệu là ( )ki CCCS , có thể được tính bằng nhiều cách khác nhau. Trong phân lớp văn bản, nếu mỗi tài liệu được biểu diễn là một vector thuộc tính: { }NNi twtwtwC ,...,, 2211= { }NNk tvtvtvC ,...,, 2211= Độ tương tự (Category Similarity - CS) và độ tương tự trung bình (Average Category Similarity - ACS) được tính theo công thức: ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 15 -  ( ) ( ) ∑ ∑ ∑ = − = × × = N n N n nn N n nn ki vw vw CCCS 1 1 22 1, ( ) ( )1 ,2 1 1 −× × = ∑ ∑ = += mm CCCS ASC m i m ik ki Trong đó tn là chỉ số từ khóa và wn và vn là trọng số từ khóa. Dựa vào độ đo tương tự, chúng ta có thể tính mức độ đúng của việc tài liệu jd được gán vào lớp Ci. Trường hợp đơn giản nhất là jd được gán vào đúng lớp Ci , tức là do jd iTP∈ , jd được tính là một trong công thức tính độ chính xác và độ hồi tưởng của lớp Ci. Tuy nhiên, nếu jd không được gán nhãn đúng (tức là ij FPd ∈ ) chúng ta sẽ xem xét độ tương tự của các lớp mà jd được gán nhãn với lớp Ci bằng cách tính phân phối của jd đối với lớp Ci , kí hiệu là ( )ij CdCon , theo công thức: ( ) ( )( ) ACS ACSCCCS CdCon agddC i ij j − −′ = ∑ ∈′ 1 , , . Trong đó, agdd j . là các lớp mà jd được gán vào. Tương tự, nếu jd là dữ liệu âm và thuật toán phân đúng vào lớp Ci , tức là ij TNd ∈ , thì phân phối của jd với lớp Ci phụ thuộc vào độ tương tự giữa lớp Ci và các lớp mà jd thực sự thuộc (kí hiệu là lbdd j . ): ( ) ( )( ) ACS ACSCCCS CdCon lbddC i ij j − −′ = ∑ ∈′ 1 , , . Phân phối của một tài liệu có thể có giá trị âm hoặc dương, phụ thuộc vào độ tương tự giữa các nhãn được gán cho tài liệu và các lớp chứa tài liệu và độ tương tự trung bình ACS. Chú ý rằng một tài liệu có thể thuộc nhiều hơn một lớp. Phân phối của một tài liệu jd với lớp Ci được hạn chế trong đoạn [-1,1]. Vì vậy, phân phối cải tiến (Refined - Contribution), kí hiệu ( )ij CdRCon , được xác định: ( ) ( )( )( )ijij CdConCdRcon ,,1max,1min, −= ĐH Công Nghệ - ĐH QGHN CNTT                         ‐ 16 -  Với tất cả các tài liệu thuộc FPi , tổng phân phối FpConi sẽ là: ( )∑ ∈ = ij FPd iji CdRConFpCon , Tương tự, tổng phân phối TnConi là: ( )∑ ∈ = ij TNd iji CdRConTnCon , Độ chính xác và độ hồi tưởng mở rộng cho lớp Ci dựa vào độ tương tự được xác định như sau: Precision: ( ) iii iiiCS i FpConTNTP TnConFpConTP ++ ++= ,0maxPr Recall: ( ) iii iiiCS i TnConFPTP TnConFpConTP ++ ++= ,0maxRe Ngoài ra, chúng ta cũng có thể đánh giá dựa vào khoảng cách giữa các lớp [3]. Thay vì sử dụng độ tương tự giữa các lớp, chúng ta sử dụng độ đo khoảng cách giữa các lớp. Khoảng cách giữa hai lớp Ci và Ck, kí hiệu là 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 l