ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Nguyễn Thị Hương Thảo PHÂN LỚP PHÂN CẤP TAXONOMY VĂN BẢN WEB
VÀ ỨNG DỤNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ thông tin


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ệ
1

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

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.
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ệ
3
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

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

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ệ
4
TÀI LIỆU THAM KHẢO.......................................................................................54

Tài liệu Tiếng Việt .................................................................................................54

Tài liệu Tiếng Anh .................................................................................................54

PHỤ LỤC A. DANH SÁCH TỪ DỪNG ...............................................................57


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ệ
5

Chương I. TỔNG QUAN VỀ TAXONOMY VÀ PHÂN
LỚP PHÂN CẤP

1.1. Giới thiệu Taxonomy
Vào những năm 90 của thế kỉ XX, khái niệm taxonomy được sử dụng trong
nhiều lĩnh vực khác nhau như tâm lý học, khoa học xã hội và công nghệ thông tin... để
thiết lập sự trùng hợp giữa thuật ngữ của người sử dụng và thuật ngữ của hệ thống.
Các chuyên gia đầu tiên phát triển cấu trúc hệ thống Web đã dùng thuật ngữ taxonomy
để nói về tổ chức nội dung các trang web. Và từ đ
ó, khái niệm taxonomy được sử dụng
rộng rãi với mục đích này.
Do được sử dụng trong nhiều lĩnh vực khác nhau, nên có nhiều định nghĩa khác
nhau về taxonomy. Từ năm 2000 đến năm 2005, có khoảng 36 định nghĩa khác nhau
về taxonomy trong các nguồn tài liệu [24]. Trong lĩnh vực công nghệ thông tin,
taxonomy được định nghĩa như sau :
Định nghĩa : Taxonomy là sự phân loại của toàn bộ thông tin trong một hệ
phân cấp theo một mối quan hệ
có trước của các thực thể trong thế giới thực mà nó
biểu diễn.
Một taxonomy thường được mô tả với gốc ở trên cùng, mỗi nút của taxonomy –
bao gồm cả gốc – là một thực thể thông tin đại diện cho một thực thể trong thế giới
thực. Giữa các nút trong taxonomy có một mối quan hệ đặc biệt gọi là is
subclassification of nếu hướng liên kết từ nút con lên nút cha hoặc là is
superclassification of nế
u hướng liên kết từ nút cha xuống nút con. Đôi khi những

duyệt cơ sở dữ liệu về y tế.
1.2. Phân lớp văn bản
Trong những năm gần đây, với sự phát triển và ứng dụng của Internet, khối
lượng dữ liệu đã tăng trưởng không ngừng theo cả hai phương diện tạo mới và lưu trữ.
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ệ
7
Sự mở rộng các dữ liệu khoa học về địa lý, địa chất, khí tượng do vệ tinh thu thập, sự
giới thiệu quảng bá mã vạch đối với hầu hết các sản phẩm thương mại, việc tin học
hoá sâu rộng các thương vụ và giao dịch, sự phát triển việc ứng dụng công nghệ thông
tin trong quản lý hành chính nhà nước.... đã tạo ra một khối lượng dữ liệu khổng l
ồ. 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.
1. 2.1. Một số khái niệm
Phân lớp văn bản (Text Classification) là quá trình gán nhãn các văn bản ngôn
ngữ tự nhiên một cách tự động vào môt hoặc nhiều lớp cho trước. Thông thường, các
lớp cho trước là các chủ đề nào đó, nhưng cũng có nhiều ứng dụng mà các lớp được
thiết lập theo những tiêu chí khác, ví dụ phân lớp theo thể loại, phân lớp theo độ ưu
tiên.... Hầu hết các bài toán này sẽ tốn thời gian, công sức và đôi khi không chính xác
nếu được phân loại mộ
t cách thủ công - tức là đọc từng văn bản và gán vào một lớp
nào đó. Phân loại những đối tượng mới vào các lớp bằng phương pháp thủ công gặp
phải những khó khăn sau:
♦ Đối với các lĩnh vực đặc biệt, phân loại các đối tượng mới (như cơ sở dữ liệu về
y tế, pháp luật) vào các lớp cho trước cần có hiểu biết về các lĩnh vự
c đó.
♦ Phân lớp bằng tay đôi khi không chính xác vì quyết định phụ thuộc vào sự hiểu
biết và động cơ của người thực hiện.
♦ Quyết định của hai chuyên gia khác nhau có thể nảy sinh bất đồng ý kiến. Vì

i
)
CD ×∈
, trong đó D là tập các văn bản và C= {c
1
,c
2
.....c
c
}
là tập các lớp cho trước.
Giá trị T (True) được gán cho cặp
( )
,
ji
dc
có nghĩa là tài liệu
j
d
thuộc lớp
i
c
;
Giá trị F (False) tức là tài liệu
j
d
không thuộc lớp
i
c
.

12
, ,....,
C
cc c
thành |C| bài
toán nhị phân
{ }
,
ii
cc
với
1,...,iC=
. Hơn nữa thuật toán phân lớp đa lớp có thể được
sử dụng để giải quyết bài toán phân lớp đa 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ệ
9
Do đó, bài toán phân lớp nhị phân là bài toán rất quan trọng trong các ứng dụng
của phân lớp văn bản. Giải quyết bài toán phân lớp nhị phân cũng có nghĩa là giải
quyết bài toán phân lớp đa lớp – ứng dụng quan trọng trong phân lớp văn bản. Bài toán
lọc văn bản (text filtering), lọc thư rác (spam mail) là những ứng dụng điển hình của
phân lớp nhị phân.
1. 2.2. Phân lớp văn bản sử dụng cấu trúc phân cấp
Mặc dù các lớp văn bản được tổ chức thành cây phân cấp, ví dụ các tài liệu
Web, thư viện điện tử, thư mục thư điện tử, các lớp sản phẩm.... Tuy nhiên cho đến
giữa những năm 1990, nhiều nhà nghiên cứu hầu như bỏ qua cấu trúc phân cấp của các
lớp. Đặc biệt với các hệ thống phân lớp lớn trong đó số lượng các lớp từ
vài chục đến
hàng trăm, nếu sử dụng các kĩ thuât phân lớp văn bản phẳng thì sẽ rất phức tạp đồng
thời kết quả phân lớp không cao, bởi vì để phân biệt giữa hàng trăm lớp như vậy là rất

liên kết trực tiếp (direct path) từ N
p
đến N
c
.
Tồn tại một nút gọi là nút gốc của cây phân cấp. Các nút không có con là là nút
lá. Tất cả các nút trừ nút lá và nút gốc được gọi là các nút trong.
Bài toán phân lớp sử dụng cây phân cấp H là việc tìm một hàm
Φ
sao cho : TCDTCD
ji
=Φ⇒=Φ ),(),(
nếu
,,
jiji
CCCCH
→∈

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ệ
10

Trong đó H là cấu trúc phân cấp xác định mối quan hệ giữa các lớp. Mối quan
hệ
ji
CC
→

lớp. Thậm chí khi chúng ta chia bài toán lớn ban đầu thành các bài toán nhỏ hơn, hiếm
khi số lớp là hai. Hầu hết các thuật toán học trạng thái ví dụ Naive Bayes, cây quyết
định, mạng noron,... liên quan đến nhiều lớp. Tuy nhiên, có những thuật toán như máy
máy vector h
ỗ trợ được xây dựng để làm việc chỉ với vấn đề nhị phân. Trong những
trường hợp này, có một số phương pháp để chuyển bài toán phân lớp nhiều lớp thành
bài toán phân lớp nhị phân. Cách đơn giản nhất là chúng ta chuyển vấn đề n lớp cho
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ệ
11
trước thành n vấn đề nhị phân: bài toán nhị phân thứ i tương ứng với một cây quyết
định xem tài liệu có thuộc về lớp thứ i hay không?.
1.2.2.3. Phân lớp đa nhãn sử dụng cấu trúc phân cấp
H ầu hết các ứng dụng thực của phân lớp phân cấp văn bản là bài toán đa nhãn,
có nghĩa là một văn bản có thể được gán vào nhiều hơn một lớp. Ví dụ, bài báo về
David Beckham và Victoria có thể thuộc lớp Sport/Football hoặc
Entertainment/Music. Để giải quyết bài toán này, mỗi thuật toán phân lớp sẽ có những
chiến lược khác nhau. Ví dụ, thuật toán Naive Bayes có thể gán một văn bản không chỉ
vào lớ
p có xác suất dự đoán cao nhất mà sẽ gán vào tất cả các lớp có xác suất cao hơn
một ngưỡng nào đó. Với các thuật toán khác, giải pháp phổ biến là chuyển bài toán n
lớp thành n bài toán nhị phân.
1.2.2.4. Ứng dụng
Rất nhiều ý tưởng nghiên cứu được được thử nghiệm trên tập dữ liệu Reuters-
21578 và 20 News Group và một số nguồn dữ liệu khác từ thư mục Yahoo và
DMOZ.... Bên cạnh những tập hợp dữ liệu này, phân lớp phân cấp văn bản cũng thu
được kết quả rất tốt khi áp dụng cho những miền dữ liệu khác. Phân loại thư cũng là
một ứng dụng của phân lớp phân c
ấp văn bản.
M ột ứng dụng khác của phân lớp phân cấp văn bản là áp dụng cho máy tìm

1.3.1.1. Phương pháp biểu diễn tài liệu
Trong bài toán phân lớp văn bản, cách biểu diễn văn bản đóng vai trò rất lớn.
Một tài liệu được biểu diễn dưới dạng một tập hợp các từ, mỗi từ được xem là một
thuộc tính (feature) và văn bản tương ứng với một vector thuộc tính. Đôi khi, thay vì
những từ đơn, các thuộc tính có thể được biểu diễn bằng các cụm từ hoặc chuỗi n từ

với n >= 2. Dễ dàng thấy, nhiều thuộc tính phức tạp có thể giàu thông tin hơn. Ví dụ,
cụm từ “world wide web” mang nhiều thông tin hơn từng từ riêng biệt. Tuy nhiên,
trong thực hành, sử dụng n-grams dẫn tới việc có quá nhiều số lượng thuộc tính và có
thể làm việc giải quyết bài toán khó khăn hơn. Theo các nghiên cứu về các phương
pháp biểu diễn văn bản khác nhau, đặc biệt là khi so sánh ảnh hưởng và hiệu quả củ
a
nó thì không có cách biểu diễn văn bản nào tốt hơn cách biểu diễn bằng tập các từ
riêng biệt (isolated words) được lấy ra từ văn bản gốc.

Tiền xử lý
Phân lớp
Văn bản
Biểu diễn logic
Cây phân cấp
Mô hình

Hình 1.2. Quá trình xây dựng mô hình được chia thành hai bước : tiền xử lý dữ liệu
và học 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ệ
13
Sau khi xác định được các thuộc tính, chúng ta cần tính giá trị thuộc tính (hoặc
trọng số từ khoá) cho mỗi văn bản. Mỗi từ mục t

i
.
Phương pháp này có vẻ rất trực quan, nhưng mặt hạn chế của phương pháp này
là : nếu một từ xuất hiện nhiều lần trong tài liệu sẽ có tần xuất cao. Tuy nhiên nếu
những từ này đều xuất hiện trong tất cả các văn bản thì nó sẽ không mang nhiều thông
tin ngữ nghĩa của văn bản, và do đó độ quan trọng của nó giảm đi. Thông thường tần
suất củ
a các từ mục trong văn bản là không đồng đều nhau. Một số từ mục xuất hiện
rất thường xuyên, trong khi đó, một nửa số từ mục xuất hiện chỉ một lần. Để giải quyết
hạn chế này, tần xuất logarit (tương tự với tần xuất từ mục) được đề xuất và tính theo
công thức :
)),(1log(),(
ikik
DtfreqDtfreq +=

Phương pháp thứ hai được sử dụng phổ biến hơn phương pháp tần suất từ mục,
nhưng phương pháp này vẫn chưa giải quyết triệt để hạn chế của phương pháp tần suất
từ mục. Theo đó, một từ xuất hiện nhiều lần có tần suất cao, từ xuất hiện ít có tần suất
thấp.
Phương pháp chuẩn thường được s
ử dụng là Term Frequency Inverse Document
Frequency (TFIFF), hàm tính trọng số từ khoá được xác định bởi công thức :

,,
||
log
ld ld
l
D
TFIDF freq

TFIDF TFIDF TFIDF R
∈
= ∈
∑Với bài toán phân lớp sử dụng cấu trúc phân cấp, khóa luận đề xuất một
phương pháp đánh trọng số đối với các nút trong cây phân lớp trong quá trình phân
lớp.
Như chúng ta thấy, đối với các thuộc tính ở một mức nào đó được xuất hiện
nhiều lần, thì đó là những thuộc tính tốt để phân biệt các lớp ở mức trên, vì vậy chúng
cần được đánh trọng số
cao. Tuy nhiên, nếu các thuộc tính đó lại xuất hiện ở các lớp
con của nó hoặc ở mức dưới hơn, thì độ quan trọng của nó sẽ giảm đi, do đó trọng số
sẽ thấp hơn so với ở mức trên. Như vậy, chúng ta cần xác định một giá trị
ϖ
cho mỗi
nút trong taxonomy, hoặc theo kinh nghiệm hoặc theo thống kê. Sau khi xác định được
tập thuộc tính cho cho mỗi nút trong taxonomy, trọng số của các thuộc tính này sẽ
được nhân với giá trị

ϖ
tương ứng với lớp đó. Và như vậy, trọng số mới của thuộc tính
không chỉ thể hiện độ quan trọng của thuộc tính đối với văn bản đó, mà còn thể hiện
được độ quan trọng của nó đối với toàn bộ cấu trúc phân cấp.
1.3.1.2. Quá trình lựa chọn thuộc tính
Kích cỡ của tập từ vựng của tập hợp văn bản thường rất lớn, ví dụ 20.000 tài
liệu của Reuters 21578, tập hợp dữ liệu có khoảng 15.000 từ mục khác nhau. Xử lý các
vector thuộc tính đòi hỏi các thuật toán được tính toán mở rộng và có thể đôi khi
không thể tính toán được đối với một số thuật toán học. Bên cạnh đó, nhiều thuộc tính

<<

để phân biệt tất cả các lớp C
i
trong một cấu trúc phân cấp cho trước.
Lựa chọn thuộc tính cục bộ: Lựa chọn thuộc tính trong trong phân lớp văn bản
sử dụng cấu trúc phân cấp gọi là cục bộ nếu nó lựa chọn tập các thuộc tính
i
T
′
,
i
TT
′
<<
phù hợp cho mỗi lớp C
i
trong cấu trúc phân cấp cho trước.
Hình dưới mô tả cách lựa chọn thuộc tính toàn cục và cục bộ :

Tin học
Nông nghiệp
Ngôn ngữ lập trình
Hệ điều hành
Trồng trọt
Chăn nuôi
Trang trại Máy tính

c từ tính toán thống kê được sử dụng để
loại bỏ những từ mục không thích hợp. Sau đó, bộ phân lớp được huấn luyện trên
không gian từ mục đã được rút gọn. Với chiến lược lựa chọn từ mục này, có một vài
phương pháp như : lựa chọn từ mục theo tần suất văn bản (Documen Frequency), độ
đo thông tin qua lại (Mutual Information).

Sữ
a
Con bò
Con cừu
Bệnh tật
Tin học
Nông nghiệp
Ngôn ngữ lập trình
Hệ điều hành
Trồng trọt
Chăn nuôi
Trang trạiMáy tín
h
Cây lúa mì Động vật
Windows Java

Windows
Java
C++
Linux

Hình 1.3.b : Lựa chọn thuộc tính theo hướng cục 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ệ

+×+

Trong đó :
– A là số lần từ mục t và lớp c đồng thời xuất hiện.
– B là số lần từ mục t xuất hiện mà không thuộc c.
– C là số lần c xuất hiện không chứa t.
– N là tổng số dữ liệu học.
( )
,Itc
nhận giá trị 0 nếu từ mục t và lớp c độc lập với nhau. Giá trị
( )
,Itc
càng
cao thể hiện độ quan trọng của thuộc tính t với lớp c.
K ỹ thuật thứ hai được gọi là kĩ thuật wrapper, trong đó việc lựa chọn từ mục
phụ thuộc vào thuật toán phân lớp. Bắt đầu từ không gian từ mục ban đầu, một không
gian từ mục mới được sinh ra bằng việc thêm hoặc bớ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

×
trực giao với nhau và được
gọi là các vector suy biến phải.
rr
σ
×
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 ,rmn≤
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:


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

′
=
∑

Khi đó tài liệu
x
sẽ được phân vào lớp
o
c
nếu:
{ }
CcxcscoreMaxx
o
cscore ∈= ),|()|(

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

. 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)
( )
,SBΦ
để
tính toán bộ phân lớp yếu
:
hI→ℜ
. Dấu của
( )
hd
r
, tức
( )
( )
sgn hd
r
thể hiện nhãn dữ
đoán của văn bản
d
r

tt
hSB
=Φ
đượ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
t
B
được cập nhật:
()
()
( )
( )
t
1
exp -
it i
t
t
t
B iyhd
Bi
Z
α
+
∗
=
r

Trong đó:
()

t
h
. Hàm phân lớp cuối cùng
()
Hd
r
được
tính như sau:
( ) ( )
( )
sgn
Hd fd=
r r

Thuật toán:
Input:
{ }
1
, .... ,
imm
Sdy dy=
rr
,
i
dD
∈
r
,
{ }
1,1

được tính bởi
Φ
với
t
B
.
Funtion AdaBoost Begin
Khởi tạo:
()
1
1
Bi
m
=

For
1,...,tT=

Tính
( )
,
tt
hSB=Φ

Chọn
t
α
∈ℜ

For

exp -
tt iti
i
Z Bi yhd
α
=∗
∑
r

End for
End for
Output:
() ()
t
0
sgn
T
t
t
Hd hd
α
=
⎛⎞
=
⎜⎟
⎝⎠
∑
rr

End function

x
là dữ liệu dương hay âm. Một tài liệu
i
x
được gọi là dữ liệu dương
nếu nó thuộc lớp
i
c
;
i
x
được gọi là dữ liệu âm nếu nó không thuộc lớp
i
c
. Bộ phân lớp
tuyến tính được xác định bằng siêu phẳng:
{ }
0
:() 0
T
xfx w w= +=

Trong đó
m
wR∈
và
0
wR∈
đóng vai trò là tham số của mô hình. Hàm phân lớp
nhị phân

1
()
0
hx
⎧
=
⎨
⎩
nếu
() 0fx>

ngược lại
1.
0w ←

2.
0
0
w ←

3. repeat
4.
0e ←

5.
for 1,...,in←

6.
( )
( )

ww

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ý