LUẬN VĂN: PHÂN LỚP PHÂN CẤP TAXONOMY VĂN BẢN WEB VÀ ỨNG DỤNG pot

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

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

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

Nguyễn Thị Hương Thảo - Lớp K47CA – Trường Đại học Công nghệ 2

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.

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

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

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