Khóa luận Phân lớp phân cấp taxonomy văn bản web và ứng dụng

t từ. Khi một tập hợp từ mục mới được tạo ra, bộ phân lớp dựa vào đó để xây dựng và sau đó kiểm tra trên tập dữ liệu kiểm tra. Tập dữ liệu cho kết quả tốt nhất sẽ được chọn. Không gian từ mục tốt nhất được tạo ra cho thuật toán phân lớp. Phương pháp này tạo thuận lợi cho thuật toán phân lớp; Tuy nhiên hạn chế của phương pháp này là sự phức tạp trong tính toán. Kỹ thuật thứ ba, đánh chỉ mục dựa vào ngữ nghĩa tiềm ẩn - Latent Semantic Indexing (LSI – Deerwester 1990, theo [xx]), nén các vector từ mục thành các vector Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 18 có số chiều ít hơn trong không gian từ T ′ , số chiều thu được là sự liên kết các từ trong không gian từ mục ban đầu T. LSI sử dụng kĩ thuật toán học gọi là phép phân tích ma trận dựa vào giá trị suy biến (Sigular Value Decomposition - SVD). SVD chuyển ma trận từ mục – văn bản D ban đầu thành ma trận D% có số chiều nhỏ hơn sao cho khoảng cách giữa hai ma trận : đạt giá trị nhỏ nhất. Để làm được điều này, với ma trận từ mục – văn bản m nD × ban đầu, trong đó m là số từ mục và n là số tài liệu, SVD thực hiện như sau: Trong đó U là ma trận m r× , V là ma trận r n× . Các cột của m rU × trực giao với nhau và được gọi là các vector suy biến trái. Các cột của r nV × trực giao với nhau và được gọi là các vector suy biến phải. r rσ × là ma trận chéo của các giá trị suy biến từ ma trận ban đầu D, với ( )min ,r m n≤ là hạng của ma trận từ mục – tài liệu D ban đầu. Thông thường r là min(m,n). Tuy nhiên, nếu chúng ta chỉ giữ lại k từ có giá trị suy biến lớn nhất, xấp xỉ ma trận ban đầu thành ma trận mới sau: Ma trận D% thu được bằng cách xóa bỏ những giá trị suy biến nhỏ từ σ , U% và V% thu được bằng cách xóa bỏ hàng và cột tương ứng. Sau khi thu được kết quả từ SVD dựa trên dữ liệu học, một tài liệu mới được ánh xạ vào không gian từ mục nhỏ hơn như sau: Ngoài việc lựa chọn các thuộc tính mang nhiều thông tin từ tập thuộc tính ban đầu, quá trình lựa chọn thuộc tính có thể tạo ra cá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 2 D D∆ = − % D U Vσ= T m k k k k nD U Vσ× × ×=% % %% ' 1 Td u dσ −=r r Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 19 1.4. Các thuật toán 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, thuật toán Naive Bayes, thuật toán máy vector hỗ trợ, thuật toán Boosting... Phần này 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 máy vector hỗ trợ. 1.4.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 x đến tất cả các đ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-NN 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 (1.1). Trong đó ),,( kDxcN là tập con chỉ chứa các đối tượng thuộc lớp c của tập ),,( kDxN . ( , , ) ( | ) c o s ( , ) (1 .1) x N c x D k S c o r e c x x x ′∈ ′= ∑ Khi đó tài liệu x sẽ được phân vào lớp oc nếu: { }CcxcscoreMaxxocscore ∈= ),|()|( 1.4.2. Thuật toán phân lớp AdaBoost Boosting là một phần đặc biệt của các "Bộ phân lớp ủy ban" (classifier committees). Ý tưởng của bộ phân lớp ủy ban là kết hợp k bộ phân lớp độc lập để xây dựng một bộ phân lớp mới. Với bộ phân lớp ủy ban, các nhà nghiên cứu thường sử dụng nhiều bộ phân lớp khác nhau như bộ phân lớp dựa cây quyết định, bộ phân lớp Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 20 dựa vào xác suất, bộ phân lớp tuyến tính.... Boosting điển hình chỉ sử dụng một bộ phân lớp gọi là bộ phân lớp yếu (weak classifier) hoặc bộ phân lớp cơ sở (base classifier). Ngược lại với bộ phân lớp ủy ban, Boosting không kết hợp các bộ phân lớp độc lập. Thay vào đó, Boosting kết hợp các giả thuyết phân lớp được xây dựng từ cùng một thuật toán trên các tập dữ liệu học khác nhau. Tại mỗi vòng lặp tính bộ phân lớp yếu, một tập dữ liệu học phù hợp được chọn và cuối cùng tất cả các giả thuyết phân lớp yếu được kết hợp với nhau. Hiện nay, AdaBoost là phương pháp phổ biến nhất của Boosting, được phát triển dựa trên lý thuyết thống kê. AdaBoost được phát triển vào năm 1994 bởi Freund và Schapire [12]. Theo các nghiên cứu, AdaBoost là bộ phân lớp nhanh và hiệu quả trong nhiều ứng dụng khác nhau. AdaBoost cũng đã được áp dụng với bài toán phân lớp văn bản và khá thành công. Hiện nay, nó được xem là một trong những thuật toán phân lớp nhanh và hiệu quả nhất. Cho { }1, .... ,i m mS d y d y= r r , idr là dữ liệu học và iy là nhãn tương ứng của dữ liệu id r từ tập nhãn hữu hạn Y . Trong trường hợp đơn giản { }1,1Y = − là bài toán phân lớp nhị phân và có thể dễ dàng mở rộng thành bài toán phân lớp nhiều lớp. Tập dữ liệu học S và phân phối B là đầu vào của thuật toán học yếu (weak learning algorithm) hoặc thuật toán học cơ sở (base learning algorithm) ( ),S BΦ để tính toán bộ phân lớp yếu :h I →ℜ . Dấu của ( )h dr , tức ( )( )sgn h dr thể hiện nhãn dữ đoán của văn bản d r và ( )h dr thể hiện độ tin cậy của dữ đoán. Mặc dù ( )h dr có thể nhận giá trị thực nhưng ta thừa nhận ràng buộc ( )h dr thuộc đoạn [ ]1,1− mà không mất tính tổng quát. Phân phối B của tập dữ liệu học được biểu diễn thông qua trọng số ( ) [ ]0,1B i ∈ cho mỗi văn bản. Tại mỗi vòng lặp, giả thuyết phân lớp yếu ( ),t th S B= Φ được tính toán dựa vào phân phối hiện tại của tập dữ liệu học. Sau đó, phân phối tB được cập nhật: ( ) ( ) ( )( )t1 exp - i t itt t B i y h d B i Z α + ∗ = r Trong đó: ( ) ( )( )texp -t t i t i i Z B i y h dα= ∗∑ r Đặt: ( ) ( )t 0 T t t f d h dα = =∑r r Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 21 Là trọng số của hàm phân lớp yếu th . Hàm phân lớp cuối cùng ( )H dr được tính như sau: ( ) ( )( )sgnH d f d=r r Thuật toán: Input: { }1, .... ,i m mS d y d y= r r , id D∈r , { }1,1iy Y∈ = − với S... Tập dữ liệu học với nhãn tương ứng. Y... Nhãn của dữ liệu học, có giá trị 1 nếu là dữ liệu dương, -1 nếu dữ liệu âm. B....Phân phối của tập dữ liệu học với ( )tB i là trọng số của idr tại thời điểm t. Φ ... Hàm phân lớp yếu nhận S, B là đầu vào, đầu ra th . th : { }1,1D → − được tính bởi Φ với tB . Funtion AdaBoost Begin Khởi tạo: ( )1 1B i m= For 1,...,t T= Tính ( ),t th S B= Φ Chọn tα ∈ℜ For ( )t tB i B∈ do Cập nhật phân phối: ( ) ( ) ( )( )t1 exp - i t itt t B i y h d B i Z α + ∗ = r với: ( ) ( )( )texp -t t i t i i Z B i y h dα= ∗∑ r End for End for Output: ( ) ( )t 0 sgn T t t H d h dα = ⎛ ⎞= ⎜ ⎟⎝ ⎠∑ r r End function 1.4.3. Thuật toán máy vector hỗ trợ Theo [16], 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. 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 [Soumen Chakrabarti, trang 183, Mining the web- discovering Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 22 knowledge from Hypertext Data] [18] 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à 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 ( ) 0 h x ⎧= ⎨⎩ nếu ( ) 0f x > ngược lại 1. 0w← 2. 0 0w ← 3. repeat 4. 0e ← 5. for 1,...,i n← 6. ( )( )0do Ti is sign y w x w← + 7. if 0s < 8. then i iw w y x← + 9. 0 0 i iw w y x← + 10. 1e e← + 11. until e = 0 12. return ( )0,w w Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 23 Đ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. Trong hình 1.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 1.4. Mối quan hệ giữa các siêu phẳng phân cách Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 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 [16]. Đị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 1.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 + ≥ = Hình 1.5. Siêu phẳng tối ưu và biên. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 25 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. Đặ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: Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 26 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. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 27 Chương II. PHÂN LỚP VĂN BẢN WEB SỬ DỤNG CẤU TRÚC PHÂN CẤP TAXONOMY 2.1. Hai phương pháp phân lớp phân cấp Phân lớp phân cấp văn bản hướng tới việc gán tài liệu vào một hoặc nhiều lớp phù hợp của cây phân cấp. Các phương pháp giải quyết bài toán phân lớp phân cấp văn bản có thể được chia thành hai hướng [Sun and Lim, 2001][3]: – Phương pháp toàn cục (hoặc big-bang). – Phương pháp cục bộ (hoặc top down). Trong phương pháp big-bang, chỉ một bộ phân lớp được sử dụng trong quá trình phân lớp. Cho một tài liệu, bộ phân lớp sẽ gán nó vào một hoặc nhiều lớp trong hệ phân cấp. Các lớp được gán có thể là lá hoặc các nút trong của hệ phân cấp phụ thuộc vào cấu trúc của hệ phân cấp và từng bài toán khác nhau. Phương pháp big-bang có thể thu được với bộ phân lớp Rocchio, bộ phân lớp dựa vào luật và các phương pháp được xây dựng trên khai phá các luật kết hợp. Đánh giá kết quả được sử dụng trong những thực nghiệm này dựa trên số tài liệu được phân lớp đúng hoặc phần trăm tài liệu bị phân lớp sai. Trong phương pháp top-down, một hoặc nhiều bộ phân lớp được xây dựng tại mỗi nút của cây phân cấp và mỗi bộ phân lớp làm việc như một bộ phân lớp phẳng ở mức đó. Một tài liệu đầu tiên sẽ được phân lớp bởi bộ phân lớp ở mức gốc vào một hoặc nhiều lớp ở mức thấp hơn. Nó sẽ tiếp tục được phân lớp xa hơn ở các mức tiếp theo cho đến khi nó đạt được lớp cuối cùng có thể là lá hoặc nút trong của cây. Phương pháp top-down được thực hiện với các thuật toán như Bayesian, SVM. Ba độ đo: precision, recall, độ đo F được sử dụng trong phương pháp này. Phương pháp cục bộ có vẻ tự nhiên hơn cho phân lớp phân cấp bởi vì nó phản ánh cách mà con người thường thực hiện đối với những bài toán như vậy. Phân biệt giữa ít lớp đơn giản hơn so với phân biệt giữa hàng trăm lớp. Điều này là đúng với các hệ thống tự động. Trong học máy, nói chung theo kinh nghiệm, càng nhiều lớp thì bài toán càng khó hơn. Phân lớp vào các mức cao đơn giản hơn so với phân lớp vào tất cả các lớp không phải chỉ vì số lượng lớp ít hơn mà bởi vì chúng được phân biệt với nhau rõ hơn. Do đó, sau khi Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 28 phân lớp ở mức cao, khả năng phân lớp ở mức thấp ít hơn bởi vì chúng ta chỉ xem xét lớp được lựa chọn. Dễ nhận thấy phương pháp toàn cục có những nhược điểm sau: – Nặng về tính toán. – Rất khó để biểu diễn tập thuộc tính khác nhau tại các mức khác nhau. – Không đủ mềm dẻo, linh hoạt vì mỗi khi cấu trúc taxonomy thay đổi thì bộ phân lớp phải được học lại. Do đó, trong khóa luận này, chúng tôi tập trung vào bài toán phân lớp phân cấp văn bản theo hướng tiếp cận top-down. 2.2. Phân lớp phân cấp văn bản theo hướng top-down Phân lớp phân cấp văn bản theo chiến lược top-down định hướng vào bài toán phân lớp lớn ban đầu theo phương pháp chia nhỏ và đệ quy. Với phương pháp này, ta cần xây dựng nhiều bộ phân lớp và phân lớp một tài liệu mới được thực hiện bằng cách bắt đầu từ gốc và duyệt qua cây phân cấp cho đến khi tìm được các lớp phù hợp. Đệ quy tại mỗi nút, và các bộ phân lớp tại các nút trong sẽ quyết định nhánh nào, cạnh nào của cây phân cấp sẽ được đi xuống sâu hơn. 2.2.1. Mô hình phân lớp Phương pháp phân lớp trong mô hình này là tính toán bộ phân lớp tại mỗi nút. Cho một tài liệu với đầu vào là một vector, bộ phân lớp sẽ xác định đường đi từ nút gốc của cây phân cấp. Phân lớp một tài liệu sẽ dừng lại nếu như không có lớp nào được chọn bởi bất kì bộ phân lớp nào. Như đã giới thiệu ở phần 2.1, đây là phương pháp top-down. Trong bài toán phân lớp với hệ phân cấp dạng taxonomy, mục tiêu cuối cùng là thu được độ chính xác cao nhất tại các bộ phân lớp lá. Thông thường, các bộ phân lớp nhánh đóng vai trò bổ trợ, làm tăng độ chính xác cho các nút lá. Tuy vậy, kết quả phân lớp của các nút lá trong taxonomy lại phụ thuộc vào các bộ phân lớp nhánh. Do đó, các các bộ phân lớp nhánh đóng vai trò rất quan trọng trong kết quả của hệ thống phân lớp. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 29 Với bài toán đa nhãn, giả sử có bốn lớp A, B, C, D và bốn bộ phân lớp nhị phân tương ứng. Các dữ liệu có thể được gán vào nhiều hơn một lớp. Những dữ liệu này sẽ được phân lớp bằng hai phương pháp : phân lớp phẳng và phân lớp phân cấp. Cấu trúc lớp được trình bày như hình 2.1 dưới đây : Giả sử hai dữ liệu kiểm tra là Doc-1 và Doc-2. Vì bài toán là phân lớp đa nhãn nên với phương pháp phân lớp phẳng, chúng ta áp dụng bốn bộ phân lớp tại cùng thời điểm với mỗi dữ liệu kiểm tra. Với phương pháp phân cấp, đầu tiên chúng ta áp dụng hai bộ phân lớp lá cho lớp A và D và bộ phân lớp nhánh BC. Nếu kết quả phân lớp cho nhánh BC là dương, chúng ta áp dụng hai bộ phân lớp lá cho B và C. Nếu kết quả phân lớp cho nhánh BC là âm thì sẽ không đi sâu xuống nhánh BC nữa. Như vậy, một tài liệu sẽ bắt đầu từ gốc của taxonomy, phân lớp cho tài liệu sẽ dừng lại nếu : – Không có nút nào được chọn. – Nút được chọn là nút lá của Taxonomy. Khi sử dụng phương pháp phân cấp, có hai thuận lợi so với phân lớp phẳng: tiết kiệm thời gian dự đoán và tăng độ chính xác của kết quả phân lớp. Bởi vì khi dự đoán một tài liệu mới bằng phương pháp top-down, chúng ta chỉ cần thực hiện chỉ một phần nhỏ của các bộ phân lớp và do đó có thể tiết kiệm đáng kể thời gian. Hơn thế nữa, nếu yêu cầu về độ chính xác không cao, chúng ta có thể giảm đáng kể thời gian học các bộ phân lớp phân cấp bằng cách chia tập dữ liệu học thành những nhóm phù hợp và sử Hình 2.1. Cấu trúc lớp của 4 lớp Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 30 dụng các bộ phân lớp nhị phân như SVMs. Sử dụng chiến lược top-down cho bài toán phân lớp phân cấp, tại mỗi mức của taxonomy, ta chỉ cần phân lớp với số lớp nhỏ hơn rất nhiều so với phân lớp với tất cả các lớp. Và do đó, kết quả phân lớp sẽ chính xác hơn. Bởi vì thực hiện bài toán với ít lớp sẽ đơn giản hơn so với nhiều lớp. Cấu trúc taxonomy cũng có thể được sử dụng để thiết lập tập dữ liệu âm và dữ liệu dương tại thời điểm phân lớp để thu được tập dữ liệu hoc tại các mức khác nhau. Và đôi khi có thể sử dụng tập thuộc tính nhỏ hơn cho mỗi lớp. Có nhiều thuộc tính tốt nhưng không hữu ích để phân biệt giữa các lớp trong bài toán phân lớp phẳng. Xem xét một taxonomy với cấu trúc như hình 2.2. dưới đây. Trong mô hình phân lớp phẳng, ta cần phân biệt giữa 6 lớp. Các lớp này được xem là tách biệt nhau và không có cấu trúc xác định mối quan hệ giữa chúng. Một thuộc tính như “Máy tính” sẽ không được phân biệt lắm bởi vì nó có thể liên quan tới cả ba lớp: Phần cứng, phần mềm, tán ngẫu. Trong khi đó, với mô hình phân cấp, từ “Máy tính” là một thuộc tính tốt để phân biệt ở mức đầu tiên. Tại mức thứ hai nhiều từ chuyên biệt hơn có thể được sử dụng là các thuộc tính tốt để phân biệt ba lớp “Tán ngẫu”, “Phần cứng”, “Phần mềm” của cây con “Tin học”. Và một số thuộc tính giống nhau có thể được sử dụng để phân biệt các lớp ở mức hai đều là các thuộc tính tốt. Ví dụ, một số từ xuất hiện trong cả hai lớp “Thể thao/Tán ngẫu” và “Máy tính/Tán ngẫu”, nhưng ở mức hai, những từ này đều là các thuộc tính tốt cho cả hai lớp này. Trong bài toán phân lớp văn bản, việc lựa chọn thuộc tính đóng vai trò hết sức quan trọng, ảnh hưởng trực tiếp đến độ chính xác của thuật toán. Vì vậy, lựa chọn được tập thuộc tính tốt sẽ làm tăng kết quả phân lớp. Tin học Thể thao Phần mềm Phần cứng Bóng đá Tán ngẫu Tán ngẫu Quần vợt Hình 2.2. Một Taxonomy Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 31 2.2.2. Xây dựng các bộ phân lớp nhị phân Các bộ phân lớp nhị phân thông thường được học với cả dữ liệu học dương và âm. Trong phương pháp phân lớp phân cấp, một bộ phân lớp nhị phân được xây dựng cho mỗi lớp. Các bộ phân lớp này được chia thành hai loại : – Bộ phân lớp xác định một tài liệu có thuộc lớp nào đó hay không gọi là bộ phân lớp cục bộ (local-classifier) – Bộ phân lớp xác định một tài liệu có thuộc nhánh nào đó không được gọi là bộ phân lớp nhánh (subtree-classifier). Sự phân biệt giữa bộ phân lớp cục bộ và bộ phân lớp nhánh được đề xuất bởi Dumais và Chen [21]. Để xây dựng các bộ phân lớp nhị phân trong phân lớp phân cấp, việc rất quan trọng là phải xác định tập dữ liệu học cho mỗi bộ phân lớp. Kí hiệu Parent( iC ) là lớp cha của iC và Coverage(Ci ) với Ci thuộc taxonomy là tập tất cả các lớp thuộc nhánh có gốc là Ci gồm cả Ci . Một tài liệu jd ∈Coverage(Ci ) là đúng nếu jd thuộc bất kì lớp nào của Coverage(Ci ). Ví dụ taxonomy hình 2.2 : Coverage(Tin học ) = {Tin học, Phần cứng, Phần mềm, Tán ngẫu } Tập dữ liệu học cho các bộ phân lớp được lựa chọn theo chiến thuật sau: ♦ Bộ phân lớp nhánh của lớp gốc rootC : – Dữ liệu dương : ( )j rootd Coverage C∈ – Dữ liệu âm : ( )j rootd Coverage C∉ ♦ Bộ phân lớp nhánh cho nút trong iC của taxonomy: – Dữ liệu dương : ( )j id Coverage C∈ – Dữ liệu âm : ( )j id Coverage C∉ và ( )( )j id Coverage Parent C∈ ♦ Bộ phân lớp cục bộ cho nút trong iC của taxonomy: – Dữ liệu dương : j id C∈ Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 32 – Dữ liệu âm : j id C∉ và ( )j id Coverage C∈ ♦ Bộ phân lớp cục bộ cho lá lC của taxonomy: – Dữ liệu dương : j ld C∈ – Dữ liệu âm : j ld C∉ và ( )( )j ld Coverage Parent C∈ 2.3. Đánh giá Để đánh giá phương pháp phân lớp phân cấp, cách trực tiếp là áp dụng độ hồi tưởng (recall) và độ chính xác (precision) của phân lớp phẳng tại mỗi lớp của toàn bộ hệ phân cấp. Trong cấu trúc phân cấp, các lớp có mỗi quan hệ cha-con, anh-em. Càng đi sâu xuống cây phân cấp, sự phân biệt giữa các lớp càng khó khăn hơn. Hai lớp có thể tương tự nhau khi chúng cùng chứa một số tài liệu. Ví dụ, lớp Programming và Software Engineering có thể có chung một số thuộc tính cho phép tài liệu được phân lớp vào cả hai lớp đó. Vì vậy, nếu một tài liệu không được gán vào đúng lớp chứa nó, nhưng được gán vào lớp cha hoặc lớp con được xem là tốt hơn so với các lớp ở nhánh khác. 2.3.1. Đánh giá cho bài toán phân lớp phẳng Đá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. Trong khóa luận này, chúng tôi tập trung vào độ chính xác của kết quả phân lớp cuối cùng. Theo khảo sát của Sebastiani [8], độ đo phổ biến nhất được sử dụng để đánh giá phân lớp