phân loại văn bản bằng phương pháp support vector machine

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "phân loại văn bản bằng phương pháp support vector machine": http://123doc.vn/document/1051271-phan-loai-van-ban-bang-phuong-phap-support-vector-machine.htm

^ ]
Luận văn Thạc sỹ
5
Support Vector Machine
Danh mục các ký hiệu, các từ viết tắt

Từ Tiếng Anh Tiếng Việt
CSDL
Database Cơ sở dữ liệu
DF
Document Frequency Tần xuất tài liệu
ERM
Empirical Risk Minimization Tối thiểu hoá rủi ro theo kinh
nghiệm
IG
Information Gain Thu nhận thông tin
KDD
Knowledge Discovery in Database Khai phá tri thức trong CSDL
KNN
K Neighbourhood Nearest K láng giêng gần nhất
ODM
Oracle Data Mining Khai phá dữ liệu Oracle
SVM
Support Vector Machine Máy học vector hỗ trợ
SRM
Structural Risk Minimization Tối thiểu hoá rủi ro cấu trúc
VC
Vapnik-Chervonenkis Chiều VC




^ ]
Luận văn Thạc sỹ
6
Support Vector Machine
Danh mục các bảng
Bảng 1.1. Bảng ngẫu nhiên cho phân loại c
j
và thuật ngữ f
k
. 24
Bảng 4.1. Bảng các thuộc tính của SVM_CLASSIFIER 79
Bảng 5.1. Bảng dữ liệu thử nghiệm đã phân loại 82
Bảng 5.2. Bảng kết quả thử nghiệm lần 1 89
Bảng 5.3. Bảng kết quả thử nghiệm lần 2 90
Bảng 5.4. Bảng kết quả thử nghiệm lần 3 90
Bảng 5.5. Bảng tổng hợp kết quả thử nghiệm qua 3 lần 90

^ ]
Luận văn Thạc sỹ
7
Support Vector Machine
Danh mục các hình vẽ, đồ thị


Hình 1.1. Các bước trong tiến trình KDD 14
Hình 1.2. Hoạt động của một bộ phân loại trên một tập tài liệu 19
Hình 2.1. Mô hình hoá các lỗi 30
Hình 2.2. Mô tả VC Dimension 32
Hình 2.3. Mô tả của phương trình 2.7. 34
Hình 2.4. Siêu phẳng phân tách tối ưu là một siêu phẳng phân tách dữ liệu
với margin lớn nhất 37
Hình 2.5. Sử dụng một hàm ánh xạ
Φ
vào không gian đặc trưng F có thể
được tìm thấy bằng cách sử dụng một siêu phẳng tuyến tính (bên phải). 42
Hình 2.6. Siêu phẳng phân tách tối ưu là một phân tách với lề cực đại 47
Hình 2.7. Không gian đặc trưng SV ánh xạ không gian nguồn vào một không
gian đặc trưng nhiều chiều và sau đó xây dựng một siêu phẳng tối ưu trong
không gian đặc trưng. 54
Hình 4.1 Cấu trúc cuả một ứng dụng phân loại v
ăn bản 63
Hình 4.2. Mô hình phân loại tổng quan trong Oracle 72
Hình 4.3. Quy trình đánh chỉ số văn bản 75


^ ]
Luận văn Thạc sỹ
8
Support Vector Machine
Mở đầu

Phân loại văn bản là tiến trình xếp các tài liệu văn bản vào trong một
hoặc nhiều các phân loại hoặc lớp các tài liệu tương tự xác định trước. Sự
khác nhau trong các kết của của từng phân loại từ sự lựa chọn tập đặc trưng
tới sự kết hợp của tài liệu đã cho với một phân loại cho trước. Chủ trương của
nhận dạng phân lo
ại văn bản xếp các tài liệu văn bản vào trong các phân loại
của các tài liệu với các yêu cầu cao hơn để thu nhận nhanh hơn các tài liệu đó
và cung cấp các lĩnh vực trong đó người dùng có thể khảo sát sâu hơn các tài
liệu tương tự. Trước đây, các hệ thống thu nhận thông tin sử dụng các biểu đồ
phân loại truyền thống trong khi hầu hết các giải thuật phân nhóm sử dụng mô
hình không gian vector để hình th
ức hoá các nhóm tài liệu.
Gần đây hơn, các nhà nghiên cứu đã thực hiện sử dụng các kỹ thuật học
máy để kết hợp tự động các tài liệu với các phân loại bằng cách đầu tiên sử
dụng một tập huấn luyện để thông qua bộ phân loại tới tập đặc trưng của tập
tài liệu đặc biệt. Quy trình học máy được khởi tạo bởi một mộ
t sự kiểm tra
các tài liệu mẫu để quyết định tập đặc trưng tối thiểu mà sinh ra các kết quả
phân loại mong muốn. Giai đoạn huấn luyện này có thể được kiểm soát hoặc
không kiểm soát. Trong cả hai trường hợp một tập các phân loại được định
nghĩa một quyền ưu tiên, không giống phân nhóm mà định nghĩa các phân
loại dựa trên đặc trưng của các tài liệu thực sự
. Các kỹ thuật học không kiểm
soát sử dụng các đặc trưng của các tài liệu huấn luyện để cho giải thuật quyết
định phân loại mỗi tài liệu thuộc vào. Các kỹ thuật học có kiểm soát sử dụng
một tập các tài liệu huấn luyện mà đã được kết hợp trong một phân loại để
quyết định tập đặc trưng nào của các tài liệu sẽ tạo ra kế
t quả mong muốn.
Các kỹ thuật học máy, nếu thành công, cung cấp một ưu thế mới với các tập
tài liệu động thông qua qua mô hình không gian vector chuẩn, trong đó hướng
^ ]
Luận văn Thạc sỹ
9
Support Vector Machine
dẫn của các tài liệu mới và các tập tài liệu mới sẽ không yêu cầu xây dựng lại
các ma trận vector tài liệu
.
Với số lượng thông tin ngày càng tăng được sinh ra bởi các giao dịch
thương mại và các nhà nghiên cứu có một nhu cầu cho các giải thuật chính
xác và nhanh để phân tích dữ liệu. Các cải tiến trong kỹ thuật CSDL, thực
hiện tính toán và trí tuệ nhân tạo đã xây dựng để phát triển phân tích dữ liệu
thông minh. Dữ liệu thế giới thực thường được đặc tính hoá bằng cách có các
số lớn các ví dụ, ví dụ hàng tỷ các giao dịch thẻ tín d
ụng ,…Quan hệ giữa các
biến dự đoán như ký hiệu vật lý và các khái niệm đích,… thường không tuyến
tính. Một kỹ thuật gần đây được phát triển để thu nhận các vấn đề đó là SVM.
SVM được phát triển như một công cụ thô để phân loại và hồi quy trong các
lĩnh vực phức tạp và đa dạng.
Các CSDL thương mại hiện đại càng phát triển đã làm tăng khả năng
phân tích. Kỹ thuật khai phá văn bản trở nên chủ yếu để phân tích khối lượng
lớn dữ liệu. Các kỹ thuật khai phá tài liệu hiện tại đã đưa ra các kết quả chính
xác cao và tổng quá hoá cho tập dữ liệu. Tuy nhiên, các kết quả thu được có
chất lượng cao yêu cầu mức độ chuyên nghiệp hơn của người dùng. SVM là
một giải thuật khai phá văn bản mạnh có thể giải quyết các vấn
đề mà không
cần các phương pháp thống kê truyền thống. Tuy nhiên, vẫn còn một số giới
hạn về độ phức tạp phương pháp luận, khả năng linh hoạt, và cài đặt sản phẩm
SVM có chất lượng thấp. Luận văn này mô tả cách thực hiện của SVM nhằm
chính vào tính dễ sử dụng và khả năng linh hoạt trong khi vẫn duy trì tính
chính xác cao. SVM đã được hợp nhất vào CSDL Oracle và do đó có thể dễ
dàng khai phá vă
n bản trong CSDL với việc hỗ trợ dữ liệu trong CSDL hoặc
ngoài CSDL và thực hiện phân loại với bộ dữ liệu gồm nhiều phân loại và
mỗi tài liệu có thể thuộc một hoặc nhiều phân loại khác nhau.
^ ]
Luận văn Thạc sỹ
10
Support Vector Machine
Với dữ liệu thông tin trong CSDL ngày càng lớn cùng với yêu cầu thực
tế của các ứng dụng phân loại văn bản là đa lớp và đa nhãn nên trong luận văn
này tác giả tập trung nghiên cứu về vấn đề phân loại văn bản bằng phương
pháp SVM và thử nghiệm với bộ dữ liệu gồm nhiều phân loại khác nhau bên
trong CSDL. Trong phần thực nghiệm, chúng tôi cũng thử nghiệm với các
văn bả
n được đưa vào trong CSDL Oracle, đồng thời thực hiện thử nghiệm
giải thuật SVM đã được hợp nhất trên Oracle với phiên bản mới nhất là
Oracle 10g Release 2 .
Nội dung của luận văn được chia thành 2 phần chính.
Phần 1: Cơ sở lý thuyết về các vấn đề được nêu trên. Phần này được
tổ chức với 3 chương. Chương 1 là giới thiệu tổng quan về Khai phá văn bản.
Chương 2 tác giả
trình bày về quá trình hình thành SVM, nội dung giải thuật
SVM và một số vấn đề khi phân loại với SVM. Chương 3 trình bày về khái
niệm phân loại văn bản và lý do vì sao SVM lại được lựa chọn cho phân loại
văn bản
Phần 2: mô tả phương pháp luận về khai phá văn bản với Oracle, và
phương pháp để có thể thực hiện phân loại văn bản trong Oracle với giải
thuật SVM. Phần này được tổ chứ
c thành 2 chương. Chương 4 trình bày
phương pháp luận về khai phá văn bản trong Oracle. Chương 5 báo cáo một
số kết quả thử nghiệm dữ liệu văn bản với giải thuật SVM trong CSDL Oracle
10g.
Ngoài ra, tại phần cuối cùng là: Kết luận và định hướng nghiên cứu và
phát triển của luận văn.



^ ]
Luận văn Thạc sỹ
11
Support Vector Machine
Em xin chân thành cảm ơn TS.Nguyễn Linh Giang cùng các thày cô
giáo bộ môn đã trang bị kiến thức, giúp đỡ tận tình trong suốt quá trình học và
quá trình làm luận văn. Em cũng cảm ơn những người bạn lớp CH CNTT
2004-2006, các bạn đồng nghiệp, những người bạn thân và gia đình đã thường
xuyên động viên khích lệ và giúp đỡ em trong thời gian qua.
















^ ]
Luận văn Thạc sỹ
12
Support Vector Machine


PHẦN I - CƠ SỞ LÝ THUYẾT

Trong phần đầu tiên này, tác giả đưa ra một số khái niệm, quá trình hình
thành và các vấn đề khi phân loại thông thường khi áp dụng SVM:
- Khái niệm về khai phá văn bản
- Giới thiệu phương pháp SVM
- Các vấn đề gặp phải khi phân loại bằng phương pháp SVM
- Bài toán phân loại văn bản, cách sử dụng SVM trong bài toán phân
loại văn bản.
^ ]
Luận văn Thạc sỹ
13
Support Vector Machine
CHƯƠNG 1. TÔNG QUAN VỀ KHAI PHÁ VĂN BẢN

Mục đích của chương này là giới thiệu một cách tóm tắt về vấn đề khai phá
dữ liệu văn bản, bài toán phân loại văn bản.
9 Khai phá dữ liệu văn bản là gì?
9 Các bước để xây dựng bài toán khai phá dữ liệu văn bản.
9 Bài toán phân loại văn bản
9 Khái niệm các bước cần thực hiện để phân loại văn bản
1.1. Một số khái niệm
Trước tiên, tác giả xin trình bày một số khái niệm cơ bản để hiểu rõ
được mối liên quan giữa dữ liệu, thông tin và tri thức, và lý do vì sao lại cần
phải giải quyết các bài toán liên quan của lĩnh vực này.
• Dữ liệu được hiểu là một chuỗi các con số hoặc các đối tượng mà
chúng ta thu thập được hàng ngày. Ví dụ: dữ liệu là các file trong máy
tính, dữ liệu là các văn bản giấy tờ mà chúng ta xử lý hàng ngày,
• Thông tin
là dữ liệu đã được loại bỏ đi nhiễu, sự dư thừa và đã được
biểu diễn dưới dạng mà con người có thể nhận thức được. Ví dụ: thông
tin về tình hình chiến sự tại IRAQ, thông tin về nhiệt độ trong tháng.
• Tri thức được hiểu là các thông tin đã được tích hợp lại, đã được nhận
thức, kiểm nghiệm, hay được đúc rút ra thành các quy luật có ý nghĩ
a
đối với con người. Ví dụ: từ thông tin về nhiệt độ trong tháng, con
người có thể đưa ra được những dự báo thời tiết quan trọng,
Như vậy, tri thức chính là các dữ liệu, thông tin ở mức trừu tượng và
khái quát cao hơn, tri thức ở dạng cô đọng và dễ hiểu nhất đối với con người.
Rõ ràng trong kỷ nguyên công nghệ thông tin này thì con người chỉ muốn tìm
kiếm và lĩnh hội các tri thức, đó là cách nhanh nhấ
t và hợp lý nhất, chứ không
^ ]
Luận văn Thạc sỹ
14
Support Vector Machine
thể có đủ thời gian và khả năng để hiểu được các dữ liệu ở một dạng thô sơ
nào đó. Điều đó cũng cho thấy vai trò quan trọng của lớp các bài toán khai
phá dữ liệu và phát hiện tri thức. Phần tiếp theo tác giả trình bày về tiến trình
khai phá dữ liệu và phát hiện tri thức (KDD). Theo nhiều tài liệu khác nhau
thì tiến trình KDD nói chung đều bao gồm 5 bước cơ bản sau đây:
Bước 1. Tìm hiể
u về lĩnh vực và các vấn đề có liên quan.
Bước 2. Thu thập và tiền xử lý dữ liệu. Đây là một bước cực kỳ quan trọng,
chiếm phần lớn thời gian và sức lực (70 ÷ 90%) trong cả tiến trình.
Nó cũng ảnh hưởng tới toàn bộ các kết quả thu được về sau của tiến
trình khai phá dữ liệu.
Bước 3. Khai phá dữ liệu, trích chọn ra các mẫu, các thông tin có ý nghĩa.
Bước này gồm các phương thức để sản sinh ra các tri thức hữu ích.
Bước 4. Thể hiện và đánh giá các tri thức đã rút ra được ở bước 3.
Bước 5. Đưa các tri thức đã phát hiện được vào sử dụng trong thực tế.
Mô hình KDD không phải là một mô hình như kiểu mô hình thác nước
(thực hiện xong bước 5 là kết thúc) mà trên thực tế nó có tính lặp lại, bước
sau phản hồi về cho bước trước
đó, rồi thực hiện những sự điều chỉnh cần
thiết nhằm đưa đến một kết quả tốt nhất cho toàn bộ hệ thống.

Hình 1.1. Các bước trong tiến trình KDD