ĐẠ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
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

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
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 19
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



superclassification of nế
u hướng liên kết từ nút cha xuống nút con. Đôi khi những
quan hệ này được xác định một cách chặt chẽ hơn là is subclass of hoặc is superclass
of, nếu thực thể thông tin là một lớp đối tượng.
Hình 1.1. mô tả một taxonomy đơn giản gồm lớp Person, lớp con của nó là
Employee, Manager; Lớp cha của Person là Agent. Khi đi lên từ gốc của taxonomy,
các thực thể chung chung hơn. Khi đi xuống những lá ở cuối, thực thể xác đị
nh rõ ràng
hơn. Ví dụ, Agent chung chung hơn Person, Employee cụ thể hơn Person.
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ệ
6

Hình 1.1. Taxonomy đơn giản
Taxonomy rất có ích cho việc phân lớp thực thể thông tin theo ngữ nghĩa, chúng
thiết lập một quan hệ ngữ nghĩa đơn giản để phân biệt giữa các đối tượng trong một
miền thông tin.
Taxonomy đóng vai trò rất quan trọng trong việc tổ chức thông tin và tổ chức tri
thức. Nó được sử dụng chủ yếu để giúp cho việc tìm kiếm và duyệt thông tin thuận lợi
và nhanh chóng hơn, đặc biệ
t khi ta chỉ có những thông tin chung chung về vấn đề cần
tìm kiếm. Khi tìm kiếm trên Internet, nếu sử dụng từ khoá để tìm kiếm thông tin, kết
quả trả về có thể từ vài nghìn đến vài chục nghìn tài liệu về các chủ đề khác nhau. Sử
dụng taxonomy để tìm kiếm và duyệt thông tin sẽ tiết kiệm được rất nhiều thời gian
cho người dùng để tìm được thông tin cần thiết. Đồng thời, taxonomy cho phép các
máy tìm kiếm và các ứng dụ
ng có thể dễ dàng tìm được các thực thể thông tin nhanh
và chính xác hơn nhiều.
Taxonomy đã được áp dụng trong nhiều bài toán khác nhau: OU Shi-yan,
KHOO Christopher S.G, GOH Dion H. (2005 [15]) xây dựng taxonomy hỗ trợ việc

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ì
vậy những công cụ để tự động phân lớp văn bản vào các lớp sẽ rất hữu ích với
công việc này nhất là khi thông tin tràn ngập như ngày nay. Một số ph
ương
pháp phân lớp thống kê và kĩ thuật học máy như Bayesian, máy vector hỗ trợ
(Support Vector Machines), K người láng giềng gần nhất (K-NN), mạng nơron
được áp dụng để giải quyết bài toán này.
Rõ ràng, kĩ thuật phân lớp văn bản là rất cần thiết, nhất là ngày nay khi hầu hết
các thông tin được sinh ra và lưu trữ điện tử. Các bài báo khoa học và giải trí là những
ví dụ về tập các tài liệu điện tử. Vớ
i sự phát triển ngày càng mạnh mẽ của mạng
Internet và Intranet đã tạo ra nguồn thông tin vô cùng phong phú. Các kĩ thuật phân
lớp văn bản sẽ giúp cho nguồn dữ liệu này được lưu trữ tự động một cách hiệu quả và
được tìm kiếm nhanh chó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ệ
8
Phân lớp văn bản được xuất hiện từ những năm 1960, nhưng chỉ 15 năm sau, nó
đã trở thành lĩnh vực nghiên cứu chính trong hệ thống thông tin bởi sự đa dạng của các
ứng dụng. Phân lớp văn bản được sử dụng để hỗ trợ trong quá trình tìm kiếm thông tin
(Information Retrieval), trích lọc thông tin (Information Extraction), lọc văn bản hoặc
tự động dẫn đường cho các văn bản tới nhữ
ng chủ đề xác định trước. Một ứng dụng
khác của phân lớp văn bản là trong lĩnh vực hiểu văn bản. Phân lớp văn bản có thể
được sử dụng để lọc văn bản hoặc một phần văn bản chứa các dữ liệu cần tìm mà
không làm mất đi tính phức tạp của ngôn ngữ tự nhiên.
Định nghĩa phân lớp văn bản: Phân lớp văn bản là nhiệm vụ đặt một giá trị
Boolean cho mỗi cặp (d
j

}
FTCD ,: →
×
Φ
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, hàm
{}
FTCD ,: →×Φ
được gọi là bộ phân lớp.
Tuỳ vào bài toán khác nhau, ta có các ràng buộc khác nhau. Nhìn chung có thể
phân biệt bài toán phân lớp theo hai cách sau :
• Phân lớp văn bản nhị phân/ đa lớp: Bài toán phân lớp văn bản được gọi là nhị
phân nếu
C
=2, gọi là đa lớp nếu
C
>2.
• Phân lớp văn bản đơn nhãn/ đa nhãn: Bài toán phân lớp văn bản được gọi là
đơn nhãn nếu mỗi tài liệu được gán vào chính xác một lớp. Một bài toán phân
lớp văn bản được gọi là đa nhãn nếu một tài liệu có thể được gán nhiều hơn một
nhãn.
Về mặt lý thuyết, thuật toán phân lớp nhị phân cũng có thể được sử dụng cho
bài toán phân lớp đa lớp b
ằng cách chuyển bài toán đa lớp

khó khăn. Vì vậy vấn đề đặt ra là cần phân lớp phân cấp. Năm 1997 Koller và Sahami
đưa ra bài báo đầu tiên về vấn đề phân lớp văn bản sử dụng cấ
u trúc phân cấp [6]. Từ
kết quả thực nghiệm, bài báo chỉ ra rằng phân lớp phân cấp cho kết quả tốt hơn so với
phân lớp phẳng. Sau bài báo này, rất nhiều hướng nghiên cứu về bài toán phân lớp
phân cấp được đề xuất : Soumen Chakrabarti [19]; Dumais và Chen (2000 [21]); Sun
và Lim (2001 [3]) ; Ruiz và Srinivasan (2002 [14]); Cai và Hofmann (2004 [11]),
Yongwook Yoon (2005 [23]) Trong khoảng bốn năm gần đây, phân lớp phân cấp đã
trở thành lĩnh vực nhận được nhiều sự quan tâm và nghiên cứu của nhiều nhà khoa họ
c
trên thế giới.
1. 2.2.1. Định nghĩa và một số khái niệm
Hệ đẳng cấp (H) : Một hệ đẳng cấp H = (N, E) là một đồ thị có hướng bao gồm
tập các nút N và tập các cạnh (N
p
, N
c
). Hướng của một cạnh (N
p
, N
c
) được xác định từ
nút cha N
p
đến nút con trực tiếp N
c
, xác định qua toán tử quan hệ
p
c
NN→ được gọi là

trong cây phân cấp
H. Tất cả các tài liệu thuộc lớp C
i
đều thuộc lớp C
j
. Mối quan hệ này là bất đối xứng
(Ví dụ, xem xét quan hệ giữa chó và động vật, chúng ta có "tất cả loài chó là động vật,
nhưng không phải tất cả động vật đều là chó") và có tính chất bắc cầu (Ví dụ, xem xét
quan hệ giữa cây, cây xanh và cây thông chúng ta có "tất cả cây thông là cây xanh và
tất cả cây xanh là cây thì tất cả cây thông là cây"). Mục tiêu là tìm m
ột hàm đánh giá
bằng cách sử dụng tập tài liệu thoả mãn điều kiện ràng buộc của hệ phân cấp. Với bài
toán phân lớp phân cấp, có hai vấn đề cần được quan tâm :
♦ Cấu trúc của hệ phân cấp:
– Cấu trúc taxonomy (như trình bày ở phần 1) trong đó mỗi lớp (trừ lớp
gốc) có đúng một lớp cha.
– Cấu trúc đồ thị có hướng phi chu trình (Directed Acyclic Graph) trong đó
một lớp có thể có nhiều hơn một lớp cha.
♦ Yêu cầu các lớp chứa văn bản :
– Các tài liệu chỉ được gán vào các nút lá của hệ phân cấp.
– Các tài liệu có thể được gán vào cả nút lá lẫn nút trong của hệ phân cấp.
Khóa luận này chỉ giải quyết bài toán trong trường hợp cấu trúc hệ phân cấp là
taxonomy và văn bản có thể được gán vào cả nút lá lẫn nút trong của taxonomy.
1.2.2.2. Phân lớp đa lớp sử dụng cấu trúc phân cấp
Không giống như phân lớp phẳng trong đó các ứng dụng nhị phân là phổ biến
(ví dụ, lọc thư rác, lọc văn bản), phân lớp văn bản sử dụng cấu trúc phân cấp là nhiều
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

ử dụng, những hệ thống này sẽ trả lại kết quả tìm kiếm được tổ chức
thành một hệ phân cấp các chủ đề hữu hạn cho trước. Những biểu diễn như thế này sẽ
giúp người sử dụng dễ dàng tìm kiếm thông tin họ cần. Việc này có thể thu được bằng
cách tính hạng của kết quả trả về bởi máy tìm kiếm trong một hệ phân c
ấp chủ đề cho
trước.
1.3. Quá trình tiền xử lý dữ liệu
Phân lớp văn bản là quá trình gồm hai bước, với mục đích phân các tài liệu văn
bản vào các lớp hữu hạn có trước. Trong bước thứ nhất, một mô hình của bộ phân lớp
được xây dựng bằng cách phân tích nội dung các trang văn bản trong tập dữ liệu huấ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ệ
12
luyện thông qua việc áp dụng các thuật toán học. Tập dữ liệu huấn luyện là tập hợp các
trang văn bản trong cơ sở dữ liệu đã được gán nhãn từ trước. Trong bước thứ hai, mô
hình này được sử dụng cho việc phân lớp các trang văn bản chưa được gán nhãn.
Để xây dựng mô hình trong bước thứ nhất, thông thường, được chia ra làm hai
bước chính sau (Hình 1.2):
♦ Tiền xử lý dữ liệu: là quá trình biểu diễ
n văn bản thành một dạng biểu diễn
logic mà thuật toán có thể xử lý được (ví dụ, dạng biểu diễn vector của văn
bản).
♦ Học các bộ phân lớp : sử dụng các thuật toán phân lớp để xây dựng mô hình từ
dữ liệu đã qua tiền xử lý. 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ì

và do đó, mỗi tài liệu được biểu diễn như một vector. Trọng số từ khoá có
thể được tính toán bằng nhiều cách khác nhau. Cách đơn giản nhất là gán trọng số
bằng một giá trị nhị phân chỉ ra từ mục có mặt hay không có mặt trong văn bản.
Phương pháp khác là tính số lần xuất hiện của từ mục trong một tài liệu gọi là tần suất
từ mục. Tần suất t
ừ mục được tính theo công thức :

(, )
(, )
ki
ki
occ t D
freq t D
N
=

Trong đó N là tổng số từ mục của tài liệu D
i
và occ(t
k
,D
i
) là số lần xuất hiện của
từ t
k
trong văn bản D
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

⎜⎟
⎝⎠

Trong đó, tần xuất từ mục l trong tài liệu d :
,ld
f
req là số lần xuất hiện của từ
mục l trong tài liệu d
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ệ
14
Tần xuất văn bản
l
df
là số văn bản trong tập tài liệu có chứa từ mục l .
D là tổng số tài liệu học.
Trọng số TFIDF của một từ mục biểu diễn độ quan trọng của từ mục. TFIDF
của một từ mục trong một tài liệu sẽ giảm nếu như từ đó xuất hiện trong hầu hết các
văn bản. Vì vậy, mộ
t từ xuất hiện quá ít hoặc quá nhiều được đánh giá ít quan trọng
hơn so với các từ xuất hiện cân bằng.
Trọng số TFIDF của một từ mục trong toàn bộ tập tài liệu D được tính bởi :
,

lldl
dD
TFIDF TFIDF TFIDF 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ệ
15
Lựa chọn thuộc tính là quá trình chọn ra những thuộc tính mang nhiều thông tin
nhất trong không gian thuộc tính và loại bỏ những thuộc tính nhiễu. Trong phân lớp
phân cấp văn bản, việc chọn lựa các thuộc tính là rất quan trọng vì tập văn bản rất lớn.
Để giải quyết vấn đề này, quá trình lựa chọn thuộc tính được tiến hành bằng cách chỉ
giữ những từ mục có giá trị về thông tin. Vì vậy, v
ấn đề phát hiện các từ mục không
quan trọng phải được giải quyết để thu được không gian từ mục
TT
′
⊂ với TT
′
<
< .
Đối với bài toán phân lớp sử dụng cấu trúc phân cấp, có hai cách tiếp cận khác nhau
cho quá trình trích chọn thuộc tính được đề xuất:
Lựa chọn thuộc tính toàn cục: Lựa chọn thuộc tính trong phân lớp văn bản sử
dụng cấu trúc phân cấp gọi là toàn cục nếu nó lựa chọn tập các thuộc tính
T
′
,
TT
′
<
<

để phân biệt tất cả các lớp C
i


Hình 1.3.a : Lựa chọn thuộc tính theo hướng toàn cụ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ệ
16Cách tiếp cận toàn cục để chọn lựa các thuộc tính thường được sử dụng trong
phân lớp phẳng. Cách tiếp cận cục bộ, coi mỗi nút trong của cây phân cấp như một bài
toán phân lớp và lựa chọn thuộc tính cho mỗi bài toán con độc lập nhau.
Đối với bài toán phân lớp phân cấp, khi số lượng các lớp lên đến hàng trăm thì
việc quản lý số lượng quá nhiều thuộc tính trở nên vô cùng khó khăn, đồng th
ời làm
cho việc xử lý dữ liệu và thời gian học các bộ phân lớp tăng lên đáng kể. Giải pháp là
lựa chọn thuộc tính theo phương pháp cục bộ, tức là sẽ chọn những thuộc tính phù hợp
nhất tại mỗi mức của taxonomy để phân biệt giữa các lớp tại mức ấy. Với chiến lược
này, chúng ta có thể giảm được thời gian huấn luyện các bộ phân lớp đồ
ng thời quản
lý số lượng thuộc tính nhỏ sẽ đơn giản hơn. Weigend năm 1999 (theo [xx]) là người
đầu tiên đưa ra so sánh và phân biệt giữa hai chiến lược lựa chọn thuộc tính này.
Trong học máy, một số kỹ thuật chính sau đây được xây dựng cho quá trình lựa
chọn thuộc tính :
Kỹ thuật thứ nhất thực hiện các phương pháp lọc (filtering) trên tập thuộc tính
ban đầu. Với phương pháp này kết quả thu đượ
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).

tần suất nhỏ
hơn một ngưỡng nào đó để thu được không gian từ mục nhỏ hơn. Đây là
kĩ thuật đơn giản nhất để làm giảm số lượng tâp thuộc tính.
Độ đo thông tin qua lại (MI) : là phương pháp được sử dụng khá phổ biến để
lựa chọn tập thuộc tính dựa vào mô hình thống kê. Với mỗi cặp từ mục t và lớp c , MI
được tính theo công thức sau :
()
(
)
() ()
,log
Pr t c
Itc
P
rt Prc
∧
=
×

Và được ước lượng :
()
()()
,log
AN
Itc
A
CAB
×
≈
+×+

, 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
mn
D
×
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
mr× , V là ma trận rn
×
. Các cột của
mr
U
×
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
rn
V
×
trực giao với nhau và được

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
DD∆= −
%

D
UV
σ
=

T
mk kk kn
DU V
σ
×
××
=
%% %
%

'1T
dud
σ
−
=
r

trọng số cho mỗi lớp theo biểu thức (1.1). Trong đó
),,( kDx
c
N là tập con chỉ chứa các
đối tượng thuộc lớp
c của tập ),,( kDxN .
(, ,)
( | ) cos( , ) (1.1)
xNcxDk
Score c x x x
′
∈
′
=
∑

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


rr
,
i
d
r
là dữ liệu học và
i
y
là nhãn tương ứng của dữ
liệu
i
d
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)
(
)
,SBΦ
để
tính toán bộ phân lớp yếu
:hI→ℜ. Dấu của
(
)
hd

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,1Bi∈ cho mỗi văn bản.
Tại mỗi vòng lặp, giả thuyết phân lớp yếu
(
)
,
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

T
t
t
f
dhd
α
=
=
∑
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
t
h
. Hàm phân lớp cuối cùng
()
Hd
r
được
tính như sau:
(
)
(
)
(
)

t
B
i
là trọng số của
i
d
r
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
t
h .

t
h :
{
}
1,1D →− được tính bởi
Φ
với
t
B
.
Funtion AdaBoost Begin
Khởi tạo:
()
1
1
Bi
m

t
t
B
iyhd
Bi
Z
α
+
∗
=
r

với:
()
()
(
)
t
exp -
tt iti
i
Z
Bi yhd
α
=∗
∑
r

End for
End for

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, ,
ii
Dxyi n== với
m
i
x
R∈ và
{
}
1,1
i
y ∈− là một số
nguyên xác định
i
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

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à
() 0
ii
yf 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
hx
⎧
=
⎨
⎩
nếu
() 0fx>

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

2.
0

wwyx
←
+
9.
00ii
wwyx
←
+
10.
1ee
←
+
11. until
e = 0
12. return
(
)
0
,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
.