Tóm tắt nội dung
Phân lớp Văn bản là quá trình gán Văn bản một cách tự động vào một hoặc nhiều
lớp cho trước. Tuy nhiên, trong trường hợp có số lượng khá lớn các lớp, bài toán sẽ
phức tạp hơn rất nhiều, do đó, khi tiến hành phân lớp thường cho kết quả có độ chính
xác không cao. Vì vậy, một vấn đề được đặt ra là cần phân lớp các Văn bản sử dụng
cấu trúc phân cấp. Hiện nay, bài toán này đã và đang trở thành lĩnh vực nhận được
nhiều sự quan tâm, nghiên cứu của nhiều nhà khoa học trên thế giới. Khoá luận tốt
nghiệp với đề tài "Phân lớp phân cấp Taxonomy Văn bản Web và ứng dụng" nghiên
cứu nội dung, các thuộc tính, các thuật toán giải quyết bài toán phân lớp phân cấp.
Khóa luận đã tiến hành thực nghiệm trên 12 lớp dữ liệu, sử dụng thuật toán máy vector
hỗ trợ, kết quả thu được rất tốt với độ đo F1 trung bình lên tới gần 90%.
Lời mở đầu
Trích chọn thông tin trên Web đã và đang tạo thêm nhiều tài nguyên thông tin,
tri thức mới đáp ứng ngày càng hiệu quả nhu cầu thông tin của con người. Ngày nay,
công nghệ trích chọn thông tin trên Web đã hình thành loại hình dịch vụ đầy triển
vọng trong việc cung cấp thông tin phong phú và hữu ích từ nguồn dữ liệu được coi là
vô hạn trên Web. Một trong những bài toán cơ bản và quan trọng trong trích chọn
thông tin trên Web là bài toán phát hiện các Quan hệ của các lớp đối tượng trên Web
mà Quan hệ phân cấp giữa chúng là một loại quan hệ điển hình. Để thực hiện việc phát
hiện mối Quan hệ phân cấp giữa các lớp đối tượng trên Web thì bài toán đầu tiên cần
giải quyết đó là bài toán phân lớp tự động các đối tượng. Tự động phân lớp Văn bản là
một nhiệm vụ rất quan trọng có thể giúp ích trong việc tổ chức cũng như tìm kiếm
thông tin trên nguồn tài nguyên lớn này. Phân lớp Văn bản là quá trình gán Văn bản
một cách tự động vào một hoặc nhiều lớp cho trước.
Trong các nghiên cứu phân lớp văn bản, hầu hết đều tập trung vào bài toán phân
lớp mà các lớp cho trước đượ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. Những bài toán phân lớp như vậy được gọi là bài toán phân
lớp phẳng (flat classification). Tuy nhiên, trong trường hợp có số lượng khá lớn các
lớp, bài toán sẽ phức tạp hơn rất nhiều và khi thực hiện các giải pháp phân lớp thường
cho kết quả không chính xác. Vì vậy, một vấn đề được đặt ra là cần phân lớp các văn
bản sử dụng cấu trúc phân cấp. Thực hiện công việc này mặc nhiên cũng đã bao hàm
vấn đề phát hiện Quan hệ phân cấp giữa các lớp đối tượng như đã nói ở trên. Về bản
chất đây cũng được coi là một loại Quan hệ ngữ nghĩa giữa các đối tượng và lớp đối
tượng. Bài toán cần được giải quyết là phát hiện các lớp và Kiến trúc các lớp đã được
phát hiện vào một cây phân cấp. Đây là bài toán phân lớp phân cấp. Phân lớp phân cấp
cho phép định hướng vào bài toán phân lớp lớn ban đầu và sử dụng phương pháp chia
nhỏ và đệ quy.
Khoá luận tốt nghiệp với đề tài "Phân lớp phân cấp Taxonomy Văn bản Web
và ứng dụng" nghiên cứu nội dung, các thuộc tính, các thuật toán giải quyết bài toán
phân lớp phân cấp và cố gắng đưa ra một số nhận xét, đề xuất thích hợp và thi hành
chương trình thực nghiệm để kiểm chứng tính khả thi của phương pháp.
Phân lớp phân cấp Taxonomy Văn bản Web và ứng dụng
Khóa luận được tổ chức thành ba chương mà nội dung chính của các chương
được giới thiệu như dưới đây.
Chương 1. Tổng quan về Taxonomy và phân lớp Văn bản trình bày những nét cơ
bản nhất về taxonomy, các khái niệm và nội dung cơ bản về bài toán phân lớp văn bản.
Chương này cũng trình bày một số thuật toán phân lớp Văn bản điển hình, đặc biệt tập
trung vào thuật toán SVM - thuật toán hiện nay được đánh giá là bộ phân lớp nhanh và
hiệu quả nhất với bài toán phân lớp văn bản.
Chương 2. Phân lớp phân cấp Taxonomy Văn bản Web nghiên cứu các phương
pháp giải quyết bài toán phân lớp phân cấp và cách Xây dựng các bộ phân lớp cho cây
phân cấp văn bản. Chương này cũng giới thiệu một số phương pháp đánh giá cho bài
toán phân lớp phẳng và độ đo dựa vào khoảng cách và độ tương tự giữa các lớp.
Chương 3. Thực nghiệm trình bày các kết quả thực nghiệm thu được khi áp
dụng thuật toán SVM và phương pháp phân lớp phân cấp theo hướng top-down. Một
số nhận xét, đánh giá kết luận cũng được trình bày.
Phần kết luận tổng kết các kết quả của khóa luận và trình bày định hướng phát
triển nội dung của khóa luận. Bài toán phân lớp phân cấp Văn bản Web thực sự có ý
nghĩa về nghiên cứu và triển khai.
MỤC LỤC
Chương I. TỔNG QUAN VỀ TAXONOMY VÀ PHÂN LỚP PHÂN CẤP 5
1.1. Giới thiệu Taxonomy 5
1.2. Phân lớp văn bản . .6
1. 2.1. Một số khái niệm 7
1.3. Quá trình tiền xử lý dữ liệu 11
1.3.1.1. Phương pháp biểu diễn tài liệu .12
1.3.1.2. Quá trình lựa chọn thuộc tính . 14
1.4. Các thuật toán phân lớp Văn bản .19
1.4.1. Thuật toán K người láng giềng gần nhất .1 9
1.4.2. Thuật toán phân lớp AdaBoost 19
1.4.3. Thuật toán máy vector hỗ trợ 21
Chương II. PHÂN LỚP Văn bản WEB SỬ DỤNG CẤU TRÚC PHÂN CẤP
TAXONOMY .27
2.1. Hai phương pháp phân lớp phân cấp . 27
2.2. Phân lớp phân cấp Văn bản theo hướng top-down 28
2.2.1. Mô hình phân lớp 28
2.2.2. Xây dựng các bộ phân lớp nhị phân . 31
2.3. Đánh giá .32
2.3.1. Đánh giá cho bài toán phân lớp phẳng 32
2.3.2. Đánh giá dựa vào độ tương tự .34
Chương III. THỰC NGHIỆM .37
3.1. Dữ liệu và chương trình .37
3.2. Môi trường thực nghiệm .40
3.3. Kết quả và đánh giá 40
3.3.1. Thực nghiệm1 : Phân lớp phân cấp theo hướng top-down .40
3.3.2. Thực nghiệm 2 : Khảo sát sự phụ thuộc thời gian huấn luyện và kết quả
vào tập thuộc tính. .46
KẾT LUẬN. .52
61 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2664 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Đề tài Phân lớp phân cấp Faxonomy văn bản Web và ứng dụng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
iệ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 phẳng 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
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ệ 33
– TP (true positives): số lượng ví dụ dương được thuật toán phân đúng vào Ci.
– TN (true negatives): số lượng ví dụ âm được thuật toán phân đúng vào Ci.
– FP (false positives): số lượng ví dụ dương được thuật toán phân sai vào Ci.
– FN (false negatives): số lượng ví dụ âm được thuật toán phân sai vào Ci.
Độ 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 Ci :
ii
i
i TNTP
TP
+=Pr
Độ hồi tưởng Rei 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ụ dương thực sự thuộc lớp Ci:
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à { }1 2, ,..., mC C C có thể thu được bằng hai cách :
Micro-Average và Macro-Average.
• Microaveraging:
1
1
ˆ
( )
m
i
i
m
i i
i
TP
Pr
TP FP
µ =
=
=
+
∑
∑
1
1
ˆ
( )
m
i
i
m
i i
i
TP
Re
TP FN
µ =
=
=
+
∑
∑
• 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à :
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ệ 34
♦ Break-Even Point (BEP): BEP được đề xuất bởi Lewis, 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 có thể cao hơn nhiều so với độ chính xác, do đó
không thể tính được BEP.
♦ Độ đo Fβ : độ đo Fβ được đề xuất bởi Rijbergen. 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à :
2
2
( 1). .
.
Pr ReF
Pr Reβ
β
β
+= +
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à Eri của lớp
Ci :
i i
i
i i i i
TP TNAc
TP TN FP FN
+= + + +
1i ii i
i i i i
FP FNEr Ac
TP TN FP FN
+= = −+ + +
2.3.2. Đánh giá dựa vào độ tương tự
Dễ nhận thấy, nếu phương pháp A và B đều không phân tài liệu vào đúng lớp Ci
của nó, nhưng phương pháp A phân vào lớp tương tự với lớp Ci 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, chúng ta sẽ 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.
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ệ 35
Độ tương tự giữa hai lớp iC và kC , kí hiệu là ( ),i kCS C C 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 :
{ }1 1 2 2, ,...,i N NC w t w t w t=
{ }1 1 2 2, ,..., N Nk vC t v t v t=
Độ 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 :
( )
1
2 2
1 1
, )(
N
n n
n
i k N N
n n
n n
w v
C
w v
CS C =
= =
×
=
×
∑
∑ ∑
( )
( )1 1
2 ,
1
m m
i k
i k i
CS C C
ASC
m m
= = +
×
= × −
∑ ∑
Trong đó tn là chỉ số từ mục và wn và vn là trọng số từ khoá.
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 iC . Trường hợp đơn giản nhất là jd được gán vào đúng lớp iC ,
tức là j iTPd ∈ , jd được tính là 1 trong công thức tính độ chính xác và độ hồi tưởng
của lớp iC . Tuy nhiên, nếu jd không được gán nhãn đúng (tức là j iFPd ∈ ) 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 iC bằng cách tính phân
phối của jd đối với lớp iC , kí hiệu là ( ),j id CCon theo công thức :
( )
( )( )
.
,
,
1
j
i
C d lbd
j i
CS C C ACS
d C
ACS
Con ′∈
′ −
= −
∑
Trong đó, dj.lbd là các lớp mà jd được gán nhã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ệ 36
Tương tự, nếu jd là dữ liệu âm và thuật toán phân lớp cho giá trị sai, tức là
j iFNd ∈ , thì phân phối của jd với lớp iC phụ thuộc vào độ tương tự giữa lớp iC và
các lớp chứa jd ( kí hiệu là dj.agd)
( )
( )( )
.
,
,
1
j
i
C d agd
j i
CS C C ACS
d C
ACS
Con ′∈
′ −
= −
∑
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 iC đượ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 ( ),j iRCon d C được xác định :
( ) ( )( )( ), min 1,max 1, ,j i j iRCon d C Con d C= −
Với tất cả các tài liệu thuộc iFP , tổng phân phối iFpCon sẽ là :
( ),
j i
i j i
d FP
FpCon RCon d C
∈
= ∑
Tương tự, tổng phân phối iFnCon là :
( ),
j i
i j i
d FN
FnCon RCon d C
∈
= ∑
Độ chính xác và độ hồi tưởng mở rộng cho lớp iC dựa vào độ tương tự được
xác định như sau :
( )max 0, i i iCS
i
i i i
TP FpCon FnCon
Pr
TP FP FnCon
+ += + +
( )max 0, i i iCS
i
i i i
TP FpCon FnCon
Re
TP FN FpCon
+ += + +
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 trong
cấu trúc phân cấp. 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 iC và kC , kí hiệu ( ),i kDis C C
được định nghĩa là số đường liên kết giữa iC và kC . 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, độ đo
F dựa vào khoảng cách giữa các 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ệ 37
Chương III. THỰC NGHIỆM
3.1. Dữ liệu và chương trình
Cấu trúc của bộ dữ liệu sử dụng trong thực nghiệm :
Mức 1 Mức 2 Mức 3
Alt.atheism
Misc.forsale
Soc.religion.christian
Graphics
Os.ms-windows.misc
Windows.x
Ibm.pc.hardware
Com.
Sys.
Mac.hardware
Autos
Motor-cycles
Baseball
Rec.
Sport.
Hockey
Crypt
Electronics
Med
Sci.
Space
Guns
Mideast Politics.
Misc
Talk.
Religion.misc
Hình 3.1: Cấu trúc Taxonomy của 20 lớp dữ liệu
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ệ 38
Tập dữ liệu trong chương trình thực nghiệm sử dụng 20 lớp dữ liệu (Lang,
1995) ( chứa 19997 bài báo
thuộc 20 chủ đề khác nhau được lấy từ nguồn dữ liệu Usenet. Đây là tập dữ liệu chuẩn
được sử dụng trong rất nhiều nghiên cứu về phân lớp văn bản. Đặc điểm của tập dữ
liệu này là một số lớp khá giống nhau, ví dụ lớp chủ đề về hệ thống phần cứng của
máy IBM và hệ thống phần cứng của máy Macintos, hay các bài báo thuộc chủ đề
talk.politics.misc và talk.religion.misc. Một đặc điểm nữa là tập từ vựng của 20 chủ đề
rất lớn, nên đòi hỏi các thuật toán phân lớp phải làm việc được với dữ liệu có số chiều
lớn. Cấu trúc taxonomy của bộ dữ liệu được biểu diễn như hình 3.1.
Tập dữ liệu có tất cả 19997 tài liệu thuộc 20 lớp khác nhau. Vì số lượng dữ liệu
lớn nên chương trình thực nghiệm chỉ sử dụng 12 lớp thuộc 3 nhánh: rec, sci, talk:
1. Rec.autos
2. Rec.motor-cycles
3. Rec.sport.baseball
4. Rec.sport.hockey
5. Sci.crypt
6. Sci.electronics
7. Sci.med
8. Sci.space
9. Talk.politics.guns
10. Talk.politics.mideast
11. Talk.politics.misc
12. Talk.religion.misc
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 3.1: Phân bố dữ liệu học và kiểm tra
Tổng số tài liệu 12285
Tập dữ liệu học 8201
Tập dữ liệu kiểm tra 4084
Cấu trúc của 12 lớp dữ liệu lựa chọn trong thực nghiệm được biểu diễn theo
cấu trúc taxonomy sau ( Hình 3.2):
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ệ 39
Tiền xử lý văn bản: module tiền xử lý tách văn bản thành các tập từ đơn
(không tách các cụm từ). Sau khi tách từ và loại bỏ các từ dừng được liệt kê trong phụ
lục A, và một số kí tự đặc biệt delim (delim = _@${}()-[]:;,.=?*&^%#!|+~/\'\),
chương trình tính trọng số từ khoá TF.IDF và chương trình đưa mỗi tài liệu về dạng
vector các từ mục. Bởi vì SVMs có thể giải quyết tốt với các bài toán có số chiều lớn
nên thực nghiệm không làm Trích chọn thuộc tính và loại bỏ các từ mục xuất hiện ít
hơn ba lần trong tập dữ liệu học .
Mỗi văn bản được biểu diễn trên một dòng và dưới dạng vector như sau:
: :<giá trị thuộc
tính>.........:
GỐC
REC
SCI
TALK
AUTOS
MOTOR
CYCLES
SPORT
BASEBALL
CRYPT
ELEC-
TRONICS
MED
SPACE
POLITICS
RELIGION.
MISC
GUN
MIDEAST
MISC
HOCKEY
Hình 3.2. Cấu trúcTaxonomy tập dữ liệu
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ệ 40
Trong đó:
♦ : biểu diễn chủ đề của văn bản.
– Với bài toán phân lớp văn bản nhị phân có giá trị +1 nếu ví dụ
thuộc chủ đề đang xét và -1 nếu ví dụ không thuộc chủ đề đang xét.
– Với bài toán phân lớp văn bản nhiều lớp là các số nguyên.
♦ : là số nguyên dương, tham chiếu đến tập thuộc tính được lựa
chọn trong quá trình tiền xử lý dữ liệu. Văn bản được sắp xếp theo thứ tự tăng
dần của .
♦ : biểu diễn độ quan trọng của thuộc tính trong tập dữ liệu
học. Mỗi giá trị thuộc tính là một số thực, định dạng gồm 16 chữ số sau dấu
phẩy và được tính theo công thức TFIDF:
, ,
| |logl d l d
l
DTFIDF freq
df
⎛ ⎞= ∗ ⎜ ⎟⎝ ⎠
3.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.
Khóa luận xây dựng chương trình thi hành phân lớp phân cấp được viết trên
ngôn ngữ C/C++, môi trường Dev-C++ 4.9.8.0. Chương trình này tích hợp module
chương trình tiền xử lý văn bản (do khóa luận xây dựng) và module phân lớp phẳng
(khai thác mã nguồn bộ phân lớp SVMs nhị phân phiên bản 6.01, ngày 02/09/2004 tại
3.3. Kết quả và đánh giá
3.3.1. Thực nghiệm1 : Phân lớp phân cấp theo hướng top-down
Với bài toán phân lớp phân cấp theo phương pháp top-down, ta cần xây dựng
các bộ phân lớp nhánh và bộ phân lớp lá. Mỗi nút trong và nút lá của taxonomy được
xây dựng một bộ phân lớp nhị phân. Và các bộ phân lớp này phải được học với cả dữ
liệu âm và dữ liệu dương. Việc lựa chọn dữ liệu học cho các bộ phân lớp là rất quan
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ệ 41
trọng và không giống phương pháp lựa chọn tập dưa liệu cho bài toán phân lớp phẳng.
Cách lựa chọn tập dữ liệu học cho các bộ phân lớp như phần 2.2.2 trình bày.
Với cấu trúc taxonomy như hình 3.2, ta cần xây dựng 3 bộ phân lớp nhánh cho
các nút trong tại mức 1; hai bộ phân lớp nhánh tại mức hai và 12 bộ phân lớp cục bộ
cho các lá. Tổng cộng, ta cần xây dựng 17 bộ phân lớp, trong đó có 5 bộ phân lớp
nhánh và 12 bộ phân lớp cục bộ.
Kí hiệu P là số lượng dữ liệu dương, N là số lượng dữ liệu âm. Phân phối dữ
liệu học cho các bộ phân lớp được biểu diễn như hình 3.3.a:
GỐC
P: 2646
REC
N: 3024
P: 2667
SCI
N: 3048
P: 2888
TALK
P: 3304
P: 662
AUTOS
N: 1984
P: 661
MOTOR
CYCLES
N: 1985
P: 1323
SPORT
N: 1323
P: 661
BASEBALL
N: 662
P: 666
CRYPT
N: 2001
P: 667
ELEC-
TRONICS
N: 2000
P: 668
MED
N: 1999
P: 666
SPACE
N: 2001
P: 2142
POLITICS
N: 746
P: 746
RELIGION.
MISC
N: 2142
P: 698
GUNS
N: 1444
P: 666
MIDEAST
N: 1476
P: 778
MISC
N: 1364
P: 662
HOCKEY
N: 661
Hình 3.3.a: Phân phối dữ liệu học cho các 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ệ 42
Dữ liệu kiểm tra cũng được xây dựng tương tự như dữ liệu học. Tổng dữ liệu
kiểm tra cho toàn bộ taxonomy là 4084 tài liệu thuộc 12 lá. Dữ liệu kiểm tra cho các
bộ phân lớp nhánh và bộ phân lớp cục bộ của taxonomy được biểu diễn dưới hình
3.3.b :
GỐC
4084
P: 1323
REC
N: 2761
P: 1320
SCI
N: 2764
P: 1441
TALK
P: 2643
P: 308
AUTOS
N: 1026
P: 325
MOTOR
CYCLES
N: 1009
P: 644
SPORT
N: 690
P: 322
BASEBALL
N: 340
P: 309
CRYPT
N: 997
P: 305
ELEC-
TRONICS
N: 1001
P: 279
MED
N: 1027
P: 306
SPACE
N: 1000
P: 1073
POLITICS
N: 462
P: 322
RELIGION.
MISC
N: 1213
P: 335
GUNS
N: 881
P: 290
MIDEAST
N: 856
P: 386
MISC
N: 760
P: 319
HOCKEY
N: 343
Hình 3.3.b: Phân phối dữ liệu kiểm tra cho các 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ệ 43
Kết quả phân lớp cho các nút trong của taxonomy được biểu diễn trong bảng
3.2.a và biểu đồ 3.1.a :
Bảng 3.2.a: Kết quả phân lớp cho các nút trong của taxonomy
Tên lớp Tỉ lệ phân
lớp đúng
Độ chính
xác
Độ hồi
tưởng
Độ đo Fβ
( 1β = )
Rec 97.48% 95.73% 96.52% 96.12%
Sci 94.42% 91.81% 90.83% 91.32%
Talk 95.49% 90.94% 96.88% 93.82%
Rec.sport 98.20% 96.83% 99.53% 98.16%
Talk.politics 79.35% 82.98% 88.63% 85.71%
96.12
91.32
93.82
98.16
85.71
78
80
82
84
86
88
90
92
94
96
98
100
rec sci talk rec.sport talk.politics
Lớp
Đ
ộ
đo
F
1
Biểu đồ 3.1.a: Biểu đồ biểu diễn độ đo F1 của các nút trong
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ệ 44
Nhận xét :
Từ biểu đồ 3.1.a, ta thấy rằng, 5 bộ phân lớp nhánh của taxonomy làm việc rất
hiệu quả và đạt kết quả cao. Cả 5 bộ phân lớp đều cho độ đo F gần 90%, đặc biệt, bộ
phân lớp nhánh Rec.sport đạt kết quả gần 100% cho cả độ chính xác và độ hồi tưởng.
Bộ phân lớp nhánh talk.politics thu được kết qủa thấp nhất với độ đo F là 85.71%.
Kết quả cho các lá của taxonomy được biểu diễn trong bảng 3.6.b :
Bảng 3.2.b: Kết quả phân lớp cho các lá của taxonomy
Tên lớp Tỉ lệ phân
lớp đúng
Độ chính
xác
Độ hồi
tưởng
Độ đo Fβ
( 1β = )
Rec.autos 97.00% 94.08% 92.86% 93.47%
Rec.motorcycles 97.68% 97.42% 92.29% 94.79%
Rec.sport.baseball 94.56% 91.81% 97.52% 94.58%
Rec.sport.hockey 96.22% 95.94% 96.24% 96.09%
Sci.crypt 96.25% 94.83% 89.00% 91.82%
Sci.electronics 92.50% 90.27% 76.07% 82.56%
Sci.med 90.02% 95.22% 85.66% 90.19%
Sci.space 96.17% 95.82% 89.87% 92.75%
Talk.politics.guns 90.49% 81.56% 87.16% 84.27%
Talk.politics.mideast 93.54% 94.37% 82.21% 87.87%
Talk.politics.misc 83.94% 66.06% 75.17% 70.32%
Talk.religion.misc 87.17% 66.07% 79.81% 72.29%
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ệ 45
93.47 94.79 94.58 96.09 91.82
82.56
90.19 92.75 84.27 87.87
70.32 72.29
0
20
40
60
80
100
120
rec
.au
tos
rec
.m
oto
rcy
cle
s
rec
.sp
or
t.b
as
eb
all
rec
.sp
or
t.h
oc
ke
y
sc
i.c
ryp
t
sc
i.e
lec
tro
nic
s
sc
i.m
ed
sc
i.s
pa
ce
tal
k.p
oli
tic
s.g
un
s
tal
k.p
oli
tic
s.m
ide
as
t
tal
k.p
oli
tic
s.m
isc
tal
k.r
eli
gio
n.m
isc
Lớp
Đ
ộ
đo
F
1
Biểu đồ 3.1.b: Biểu đồ biểu diễn độ đo F1 các lá của taxonomy
Kết quả thực nghiệm cho thấy rằng với phương pháp phân lớp phân cấp, kết quả
thu được tốt cho cả 12 lá của taxonomy. Lớp Talk.politics.misc đạt kết quả thấp nhất
với F1=70.32%, lớp Rec.sport.hockey đạt kết quả cao nhất với F1=96.09%.
Sau khi tính tỉ lệ phân lớp đúng, độ chính xác và độ hồi tưởng cho mỗi bộ phân
lớp. Một vài độ đo tổ hợp được tính toán theo công thức sau:
♦ Tỉ lệ phân lớp đúng trung bình:
1( )
N
i
i
Acc
Avg Acc
N
==
∑
♦ Macroaveraging:
1ˆ
m
i
M i
Pr
Pr
m
==
∑
1ˆ
m
i
M i
Re
Re
m
==
∑
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ệ 46
♦ Độ đo Fβ trung bình tính theo công thức:
1( )
N
i
F
Avg F
N
β
β
==
∑
Kết quả được thể hiện như bảng 3.3 :
Bảng 3.3 : Kết quả trung bình
Tỉ lệ phân lớp đúng trung bình 92.97%
Độ chính xác trung bình 89.51%
Độ hồi tưởng trung bình 89.19%
Độ đo F1 trung bình 89.18%
3.3.2. Thực nghiệm 2 : Khảo sát sự phụ thuộc thời gian huấn luyện và kết
quả vào tập thuộc tính.
Ta biết rằng, việc lựa chọn tập thuộc tính là rất quan trọng vì nó ảnh hưởng trực
tiếp tới thời gian huấn luyện và kết quả phân lớp. Đối với bài toán phân lớp phân cấp,
ở các mức trên của cây phân cấp, chỉ cần chọn tập thuộc tính phù hợp nhất để phân
biệt giữa các lớp ở mức đó. Quay trở lại hình 2.2, như phần 2.2.1 đã trình bày, “Máy
tính” là một thuộc tính rất tốt để phân biệt giữa các lớp ở mức 1. Nếu đi sâu xuống
nhánh “Tin học” sẽ có nhiều thuộc tính chuyên biệt hơn để phân biệt giữa các lớp ở
nhánh này, và độ quan trọng của thuộc tính “Máy tính” tại nhánh “Tin học” sẽ bị giảm
đi. Vì vậy, khoá luận tiến hành một vài thực nghiệm nhằm khảo sát sự phụ thuộc của
việc lựa chọn tập thuộc tính tại mức 1 của cây phân cấp hình 3.2 với thời gian huấn
luyện và kết quả phân lớp thu đượ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ệ 47
Tập thuộc tính của ba lớp ở mức 1 được thể hiện như sau (Bảng 3.4):
REC SCI TALK
16238 18596 19622
Tập thuộc tính được lựa chọn theo độ đo thông tin qua lại(MI) :
( ) ( ) ( ), log
A NI t c
A C A B
×≈ + × +
Thử nghiệm trên ba lần lựa chọn số lượng thuộc tính có MI lớn nhất cho mỗi
lớp giảm dần theo thống kê sau (Bảng 3.5) :
REC SCI TALK
50% 8119 9296 9622
40% 6495 7436 7697
30% 4871 5577 5773
Sử dụng tập dữ liệu kiểm tra cho ba lớp ở mức 1 như thực nghiệm 1 ta thu
được kết quả như sau (Bảng 3.6):
Lớp
Phần trăm
Bảng 3.5 : Số lượng thuộc tính được lựa chọn cho mỗi
lớ
Bảng 3.4 : Tập thuộc tính của mỗi lớp tại mức 1
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ệ 48
Tỉ lệ phân
lớp đúng
Độ chính
xác
Độ hồi
tưởng
Độ đo Fβ
( 1β = )
Không lựa chọn 97.48% 95.73% 96.52% 96.12%
50% 97.45% 95.79% 96.37% 96.08%
40% 96.84% 95.09% 95.06% 95.08%
REC
30% 97.55% 97.51% 94.86% 96.17%
Không lựa chọn 94.42% 91.81% 90.83% 91.32%
50% 94.54% 92.22% 90.76% 91.48% SCI
40% 94.86% 92.30% 91.74% 92.02%
30% 95.13% 93.08% 91.74% 92.41%
Không lựa chọn 95.49% 90.94% 96.88% 93.82%
50% 95.77% 91.18% 96.81% 93.91%
40% 95.98% 91.87% 97.22% 94.47%
TALK
30% 95.94% 93.22% 95.42% 94.31%
Độ đo trung bình của cả ba lớp trong từng trường hợp được thể hiện trong
bảng 3.7 và biểu đồ 3.2:
Bảng 3.6: Kết quả phân lớp cho từng trường hợ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ệ 49
Độ đo
Phần trăm
Tỉ lệ phân
lớp đúng
trung bình
Độ chính
xác trung
bình
Độ hồi
tưởng trung
bình
Độ đo F1
trung bình
Không lựa chọn 95.68% 92.83% 94.74% 93.75%
50% 95.92% 93.06% 94.65% 93.82%
40% 95.89% 93.09% 94.67% 93.86%
305 96.21% 94.60% 94.01% 94.30%
93.57
93.82 93.86
94.3
93.2
93.4
93.6
93.8
94
94.2
94.4
Không lựa
chọn
50% 40% 30%
Các trường hợp
Đ
ộ
đo
F
1
Nhận xét :
Từ biểu đồ 3.2, dễ nhận thấy với bài toán phân lớp phân cấp văn bản, khi lựa
được tập thuộc tính phù hợp để phân biệt giữa các lớp thì kết quả phân lớp trung bình
sẽ tăng lên. Từ bảng 3.6 và 3.7 ta thấy có một số lớp khi tập thuộc tính được rút gọn
Bảng 3.7: Kết quả trung bình cho từng trường hợp
Biểu đồ 3.2: Độ đo F1 của bộ phân lớp khi sử dụng độ đo
thông tin MI
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ệ 50
thì kết quả giảm đi. Điều này là hoàn toàn tự nhiên, và sẽ tồn tại một ngưỡng mà tại đó
kết quả phân lớp trung bình sẽ thấp hơn so với khi không lựa chọn tập thuộc tính. Vì
vậy, đối với các ứng dụng lớn, cần xem xét lựa chọn ngưỡng phù hợp để kết quả phân
lớp cao nhất có thể.
REC SCI TALK Tổng thời gian
Không lựa chọn 7.44 7.89 8.15 23.48
50% 6.58 7.01 7.65 21.24
40% 4.50 5.02 5.36 14.88
30% 3.12 3.75 3.48 10.35
23.48
21.24
14.88
10.35
0
5
10
15
20
25
Không lựa
chọn
50% 40% 30%
Phần trăm đặc trưng được lựa chọn
Th
ờ
i g
ia
n
(s
)
Bảng 3.8 : Thời gian huấn luyện của từng lớp
Biểu đồ 3.3 : Tổng thời gian huấn luyện theo phần trăm thuộc tính
được lựa chọ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ệ 51
Lựa chọn được tập thuộc tính phù hợp không những làm tăng kết quả mà một
điều rất quan trọng là thời gian huấn luyện các bộ phân lớp sẽ giảm đáng kể. Điều này
được thể hiện trong bảng 3.8 biểu diễn thời gian huấn luyện cho từng lớp (tính theo
đơn vị giây) cho từng trường hợp.
Sự phụ thuộc tổng thời gian huấn luyện của cả ba lớp theo sự lựa chọn thuộc
tính được thể hiện như biểu đồ 3.3.
Nhận xét:
Dễ nhận thấy, tập thuộc tính càng được rút gọn thì tổng thời gian huấn luyện
cho cả ba lớp đều giảm đi rõ rệt. Đây là một trong những tiêu chí quan trọng mà các
hệ thống phân lớp hướng tới, đặc biệt với các hệ thống lớn.
Từ thực nghiệm có thể rút ra kết luận rằng : lựa chọn được tập thuộc tính phù
hợp cho các mức của cây phân cấp không chỉ làm giảm thời gian huấn luyện các phân
lớp mà còn làm tăng kết quả phân lớp cuối cù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ệ 52
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 phân cấp văn bản thực sự tốt. Đặc biệt, đối với các hệ thống phân lớp
mà số lượng các lớp nhiều, thì phân lớp phân cấp văn bản sẽ phát huy được những ưu
điểm của mình, không chỉ về kết quả phân lớp mà cả mặt thời gian phân lớp. Bài toán
phân lớp phân cấp văn bản Web thực sự có ý nghĩa về nghiên cứu và triển khai.
Về mặt nội dung, khoá luận đã đạt được những kết quả sau :
– Nghiên cứu một phương pháp giải quyết bài toán phân lớp phân cấp và
cách xây dựng các bộ phân lớp cho cây phân cấp văn bản.
– Nghiên cứu, phân tích hoạt động các thuật toán kNN, AdaBoost và SVM
giải quyết bài toán phân lớp phân cấp. Đề xuất ý tưởng đưa trọng số vào
mỗi nút trong quá trình phân lớp phân cấp.
– Xây dựng chương trình thi hành phân lớp phân cấp được viết trên ngôn
ngữ C/C++, môi trường Dev-C++ 4.9.8.0 được tích hợp từ module
chương trình tiền xử lý văn bản (do khóa luận xây dựng) và module phân
lớp phẳng (khai thác mã nguồn bộ phân lớp SVM nhị phân phiên bản
6.01). Kết quả thực nghiệm trên tập dữ liệu 20 NewsGroup cho thấy tính
khả thi của chương trình phân lớp phân cấp với độ đo F1 xấp xỉ 90%.
Bên cạnh đó, do thời gian và kiến thức có hạn, khoá 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 SVM cho bài toán phân lớp phân cấp
mới thi hành trên một bộ dữ liệu nên chưa có 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 án tốt.
– Do chưa nhận được độ đo đánh giá phân lớp phân cấp chuẩn nên khóa
luận tiến hành đánh giá kết quả phân lớp phân cấp theo các độ đo của
phân lớp phẳng là độ chính xác, độ hồi tưởng và độ đo F1. Đây là một
hạn chế của khóa luậ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ệ 53
Trong tương lai, khoá luận sẽ tiếp tục hoàn thiện theo hướng sau :
– Thử nghiệm trên nhiều bộ dữ liệu khác nhau, đặc biệt áp dụng bài toán
phân lớp với các trang Web tiếng Việt.
– Sử dụng một số thuật toán phân lớp phẳng khác với SVM để từ đó tìm
được thuật toán hiệu quả đối với bài toán phân lớp phân cấp.
– Ý tưởng đánh trọng số cho các thuộc tính dựa vào độ sâu của taxonomy
chưa tiến hành cài đặt được. Trong thời gian tới, chúng tôi sẽ tiến hành
cài đặt chương trình này.
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ệ 54
TÀI LIỆU THAM KHẢO
Tài liệu Tiếng Việt
[1]. Đặng Thanh Hải. Thuật toán phân lớp văn bản web và thực nghiệm trên máy tìm
kiếm Viettseek. Khoá luận tốt nghiệp 2004, Trường Đại học Công Nghệ - Đại học
Quốc gia Hà Nội
Tài liệu Tiếng Anh
[2]. Ahswin K Pulijala, Susan Gauch. Hierachical Text Classification, International
Conference on Cybernetics and Information Technologies, Systems and
Applications: CITSA 2004, Vol. 1, Orlando, FL, July 2004, pp. 257-262.
[3]. Aixin Sun and 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]. Andrew Mc Callum, Ronald Rosenfeld, Tom Mitchell, Andrew Y.Ng Improving
Text Classification by Shrinkage in a Hierarchy of Classes, In Proceedings of The
Eighteenth International Conference on Machine Learning, 1998.
[5] .D.Wollersheim, W.J.Rahayu Using Medical Test Collection Relevance Judgement
to Identify Ontological Relationships Useful for Query Expansion 21st
International Conference on Data Engineering 2005.
[6]. Daphne Koller, Mehran Sahami Hierarchical classifying documents using very
few words Proceedings of the Fourteenth International Conference on Machine
Learning (ML-97) pages 170-178, Nashville, Tennessee, July 1997.
[7]. Delphi Group, a Perot Systems Company. Information intelligence: Content
Classification and the Enterprise Taxonomy Practice, 2004.
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ệ 55
[8]. Fabrizio Sebastiani. Machine Learning in Automated Text Categorization. ACM
Computing Survey, 34(1) pages 1-47, 2002.
[9]. H.T.Kung, C.H.Wu Content Networks: Taxonomy and New Approaches The
Internet as a Large-Scale Complex System, Kihong Park and Walter Willinger
(Editors), published by Oxford University Press as part of Sante Fe Institute
series, 2002.
[10]. Ian H.Witten & Eibe Frank. Data Mining – Practical Machine Learning Tools
and Techniques – second Edition Morgan Kaufmann Publishers.
[11]. Lijuan Cai, Thomas Hofmann Hierarchical Document Categorization with
Support Vector Machines Proceedings of the ACM Conference on Information
and Knowledge Management, pages 78-87.
[12]. Michael Granitzer. Hierarchical Text Classification using methods from Machine
Learning, Master Thesis at Graz University of Technology, submitted by Michael
Granitzer – Institute of Theoretical Computer Science (IGI) Graz University of
Technology A-8010 Graz, Austria, 27th Octorber 2003.
[13].Michael Granitzer,Peter Auer. Experiments With Hierarchical Text
Classification. Proceedings of 9th IASTED International Conference on Artifical
Interlligence, IASTED, ACTA Press, Benidorm, Spain.
[14]. Miguel E.Ruiz , Padmini srinivasan Hierarchical Text Categorization Using
Neural Networks Information Retrieval, 2002 Kluwer Academic Publishers.
[15].OU Shi-yan, KHOO Christopher S.G, GOH Dion H. Division of Information
Studies, Constructing a taxonomy to support multi-document summarization of
dissertation abstracts. Proceedings Issue of the 1st International Conference on
Universal Digital Library (ICUDL 2005).
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ệ 56
[16]. 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.
[17]. Shrikanth Shankar, George Karypis. A weight adjustment algorithm for document
categorization, SIGKDD Wordshop on Text Mining, Boston, MA.
[18]. Soumen Chakrabarti, Indian Institute of Technology, Bombay, trang 183-188,
Mining the web- discovering knowledge from Hypertext Data Morgan Kaufman
Publishers.
[19]. Soumen Chakrabarti, Byron Dom. Rakesh Agrawal, Prabhakar Raghavan Using
taxonomy, discriminats, and signatures for navigating in text databases,
Proceedings of the International Conference on Very Large Data Bases (VLDB).
[20]. 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.
[21]. Susan Dumais, Hao Chen - Hierarchical Classification of Web Content,
Proceedings of the ACM International Conference on Research and Development
in Information Retrieval (SIGIR), pages 256-263.
[22]. Yiming Yang, Jan O.Pedersen A Comparative Study on Feature Selection in Text
Categorization. Proceedings of the Fourteenth Internationcal Conference on
Machine Learning (ICML ’97), 412-420, 1997.
[23]. Yongwook Yoon, Changkl Lee, Gary Geunbae Lee An effective procedure for
constructing a hierarchical text classification system. Journal of American Society
for Information Science and Technology (JASIST), 57(3), (pp. 431-442).
[24].
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ệ 57
PHỤ LỤC A. DANH SÁCH TỪ DỪNG
Danh sách các từ dừng được sử dụng trong thực nghiệm : (danh sách các từ
dừng được sử dụng từ nguồn BOW toolkit – Andrew McCallum 1998,1999)
a, able, about, above, according, accordingly, across, actually, after, afterwards,
again, against, all, allow, allows, almost, alone, along, already, also, although, always,
am, among, amongst, an, and, another, any, anybody, anyhow, anyone, anything,
anyway, anyways, anywhere, apart, appear, appreciate, appropriate, are, around, as,
aside, ask, asking, associated, at, available, away, awfully.
b, be, became, because, become, becomes, becoming, been, before, beforehand,
behind, being, believe, below, beside, besides, best, better, between, beyond, both,
brief, but, by.
c, came, can, cannot, cant, cause, causes, certain, certainly, changes, clearly, co,
com, come, comes, concerning, consequently, consider, considering, contains,
corresponding, could, course, currently.
d, definitely, described, despite, did, different, do, does, doing, done, down,
downwards, during.
e, each, edu, eg, eight, either, else, elsewhere, enough, entirely, especially, et,
etc, even, ever, every, everybody, everyone, everything, everywhere, ex, exactly,
example, except.
f, far, few, fifth, first, five, followed, following, follows, for, former, formerly,
forth, four, from, further, furthermore.
g, get, gets, getting, given, gives, go, goes, going, gone, got, gotten, greetings.
h, had, happens, hardly, has, have, having, he, hello, help, hence, her, here,
hereafter, hereby, herein, hereupon, hers, herself, hi, him, himsefl, his, hither,
hopefully, how, howbeit, however.
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ệ 58
i, ie, if, ignored, immediate, in, inasmuch, inc, indeed, indicate, indicated,
indicates, inner, insofar, instead, into, inward, is, it, its, itsefl.
j, just, k, keep, kept, know, knows, known.
l, last, lately, later, latter, latterly, least, less, lest, let, like, liked, likely, little,
look, looking, looks, ltd.
m, mainly, many, may, maybe, me, mean, meanwhile, merely, might, more,
moreover, most, much, must, my, mysefl.
n, name, namely, nd, near, nearly, necessary, need, needs, neither, never,
nevertheless, new, next, nine, no, nobody, non, none, noone, nor, normally, not,
nothing, novel, now, nowhere.
o, obviously, of, off, often, oh, ok, okay, old, on, once, one, ones, only, onto, or,
other, others, otherwise, ought, our, ours, ourselses, out, outside, overall, own.
p, particular, particularly, per, perhaps, placed, please, plus, possible,
presumably, probably, provides.
q, que, quite, qv.
r, rather, rd, re, really, reasonably, regarding, regardless, regards, relatively,
respectively, right.
s, said, same, saw, say, saying, says, second, secondly, see, seeing, seem,
seeming, seems, seen, self, selves, sensible, sent, serious, seriously, seven, shall, she,
should, since, six, so, some, somebody, somehow, someone, something, sometime,
sometimes, somewhat, somewhere, soon, sorry, specified, specify, specifying, still,
sub, such, sup, sure.
t, take, taken, tell, tends, th, than, thank, thanks, thanx, that, thats, the, their,
theirs, them, themselves, then, thence, there, thereafter, thereby, therefore, therein,
theres, thereupon, these, they, think, third, this, thorough, thoroughly, those, though,
three, through, throughout, thru, thus, to, together, too, took, toward, towards, tried,
tries, truly, try, trying, twice, two.
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ệ 59
u, un, under, unfortunately, unless, unlikely, until, unto, up, upon, us, use, used,
useful, uses, using, usually, uucp.
v, value, various, very, via, viz, vs
w, want, wants, was, way, we, welcome, well, went, were, what, whatever,
when, whence, whenever, where, whereafter, whereas, whereby, wherein, whereupon,
wherever, which, while, whither, who, whoever, whole, whom, whose, why, will,
willing, wish, with, within, without, wonder, would.
x, y, yes, yet, you, your, yours, yourself, yourselves, z, zero.
Các file đính kèm theo tài liệu này:
- Phân lớp phân cấp taxonomy văn bản web và ứng dụng.pdf