ĐẠ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
Cán bộ hướng dẫn: TS. Hà Quang Thụy
Cán bộ đồng hướng dẫn: CN. Đặng Thanh Hải
HÀ NỘI - 2006
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%.
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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.
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
1
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.
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
2
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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
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
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
3
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
4
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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
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.
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
5
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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
tóm tắt tự động văn bản; H.T.Kung và C.H.Wu xây dựng taxonomy cho mạng nội
dung [9], Wollersheim và Rahayu (2002 [5]) xây dựng một taxonomy hỗ trợ việc
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ữ.
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
6
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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ì
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.
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
7
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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 (dj, ci) ∈ D × C , trong đó D là tập các văn bản và C= {c1,c2.....cc}
là tập các lớp cho trước.
Giá trị T (True) được gán cho cặp ( d j , ci ) có nghĩa là tài liệu d j thuộc lớp ci ;
Giá trị F (False) tức là tài liệu d j không thuộc lớp ci .
Hoặc, phân lớp văn bản là bài toán tìm một hàm Φ : D × C → {T , F } trong đó D là
tập các văn bản và C= {c1,c2.....cc } là tập các lớp cho trước, hàm
Φ : D × C → {T , F } đượ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 c1 , c2 ,...., c C thành |C| bài
toán nhị phân {ci , ci } với i = 1,..., C . 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.
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
8
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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
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 (Np, Nc). Hướng của một cạnh (Np, Nc) được xác định từ
nút cha Np đến nút con trực tiếp Nc , xác định qua toán tử quan hệ N p → N c được gọi là
liên kết trực tiếp (direct path) từ Np đến Nc.
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 :
Φ( D, C i ) = T ⇒ Φ ( D, C j ) = T nếu C j → Ci , C j , Ci ∈ H
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
9
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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ệ Ci → C j thể hiện mối quan hệ IS-A trong đó lớp Cj là cha của Ci trong cây phân cấp
H. Tất cả các tài liệu thuộc lớp Ci đều thuộc lớp Cj . 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ỗ 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
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
10
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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 Reuters21578 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
kiếm. Như chúng ta đã biết, khi người dùng tìm kiếm, số lượng kết quả trả về rất nhiều
(có thể vài nghìn tài liệu liên quan đến từ khoá tìm kiếm), trong số đó chỉ có rất ít tài
liệu đáp ứng mong muốn của người dùng. Vì vậy, thay vì trả về một danh sách các văn
bản cho người sử 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
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
11
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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ý.
Văn bản
Tiền xử lý
Biểu diễn logic
Phân lớp
Mô hình
Cây phân cấp
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
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.
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
12
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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 ti trong một tài liệu được gán một
trọng số wi 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 :
freq (tk , Di ) =
occ(tk , Di )
N
Trong đó N là tổng số từ mục của tài liệu Di và occ(tk,Di) là số lần xuất hiện của
từ tk trong văn bản Di .
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 :
freq(t k , Di ) = log(1 + freq(t k , Di ))
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 :
⎛| D|⎞
TFIDFl ,d = freql ,d ∗ log ⎜
⎟
⎝ dfl ⎠
Trong đó, tần xuất từ mục l trong tài liệu d : freql ,d là số lần xuất hiện của từ
mục l trong tài liệu d
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
13
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
Tần xuất văn bản dfl 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 :
TFIDFl = ∑ TFIDFl ,d
d ∈D
TFIDFl ∈ 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
không mang thông tin, nhập nhằng hoặc bị nhiễu, do đó có thể dẫn tới bộ phân lớp đạt
được kết quả tốt trên dữ liệu học nhưng không tốt trên dữ liệu kiểm tra (overfitting).
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
14
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
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 T ′ ⊂ T với T ′ << T .
Đố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 ′ , T ′ << T
để phân biệt tất cả các lớp Ci 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 Ti′ ,
Ti′ << T phù hợp cho mỗi lớp Ci 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ộ :
Trang trại
Cây lúa mì
Windows
Sữa
Con bò Linux
Con cừu
Nông nghiệp
Chăn nuôi
Trồng trọt
Máy tính
Động vật
Java
C++
Bệnh tật
Tin học
Hệ điều hành
Ngôn ngữ lập trình
Hình 1.3.a : Lựa chọn thuộc tính theo hướng toàn cục
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
15
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
Trang trại
Cây lúa mì
Windows
Sữa
Con bò
Con cừu Nông nghiệp
Bệnh tật
Trồng trọt
Chăn nuôi
Máy tính
Động vật
Java
Tin học
Hệ điều hành
Windows
Java
C++
Linux
Ngôn ngữ lập trình
Hình 1.3.b : Lựa chọn thuộc tính theo hướng cục bộ
Cá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).
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
16
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
Tần suất văn bản : Tần suất của văn bản là số tài liệu mà một từ mục xuất
hiện. Để lựa chọn từ mục theo phương pháp tần suất văn bản, chúng ta phải tính tần
suất văn bản với mỗi từ mục trong tập dữ liệu học và sau đó loại bỏ những từ mục có
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 :
I ( t , c ) = log
Pr ( t ∧ c )
Pr ( t ) × Pr ( c )
Và được ước lượng :
I ( t , c ) ≈ log
A× N
( A + C )× ( A + B)
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.
I ( t , c ) nhận giá trị 0 nếu từ mục t và lớp c độc lập với nhau. Giá trị I ( t , c ) 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
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
17
Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng
có số chiều ít hơn trong không gian từ T ′ , số chiều thu được là sự liên kết các từ trong
không gian từ mục ban đầu T. LSI sử dụng kĩ thuật toán học gọi là phép phân tích ma
trận dựa vào giá trị suy biến (Sigular Value Decomposition - SVD). SVD chuyển ma
trận từ mục – văn bản D ban đầu thành ma trận D% có số chiều nhỏ hơn sao cho khoảng
cách giữa hai ma trận :
∆ = D − D%
2
đạ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 D m × n ban
đầu, trong đó m là số từ mục và n là số tài liệu, SVD thực hiện như sau:
D = Uσ V
Trong đó U là ma trận m × r , V là ma trận r × n . Các cột của U m×r 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 Vr×n trực giao với nhau và được
gọi là các vector suy biến phải. σ r×r là ma trận chéo của các giá trị suy biến từ ma trận
ban đầu D, với r ≤ min ( m, n ) là hạng của ma trận từ mục – tài liệu D ban đầu. Thông
thường r là min(m,n). Tuy nhiên, nếu chúng ta chỉ giữ lại k từ có giá trị suy biến lớn
nhất, xấp xỉ ma trận ban đầu thành ma trận mới sau:
D% = U% m×kσ% k ×kV%kT×n
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
d ' = σ −1uT d
Ngoài việc lựa chọn các thuộc tính mang nhiều thông tin từ tập thuộc tính ban
đầu, quá trình lựa chọn thuộc tính có thể tạo ra các thuộc tính mới (ví dụ các khái
niệm) để thay thế cho một nhóm các thuộc tính thông qua kỹ thuật phân cụm. Nhóm
các từ có sự giống nhau về ngữ nghĩa sẽ được xem là một thuộc tính mới thay thế cho
các từ đơn lẻ. Với phương pháp này, cần xác định độ tương tự giữa các từ và áp dụng
các kĩ thuật phân cụm như k người láng giềng gần nhất
Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ
18
- Xem thêm -