Tại sao lại cần khai phá dữ liệu (datamining)
Khoảng hơn một thập kỷ trở lại đây, lượng thông tin được lưu trữ trên các
thiết bị điện tử (đĩa cứng, CD-ROM, băng từ, .v.v.) không ngừng tăng lên. Sự tích lũy
dữ liệu này xảy ra với một tốc độ bùng nổ. Người ta ước đoán rằng lượng thông tin
trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo đó số lượng cũng như kích cỡ
của các cơ sở dữ liệu (CSDL) cũng tăng lên một cách nhanh chóng. Nói một cách hình
ảnh là chúng ta đang “ngập” trong dữ liệu nhưng lại “đói” tri thức. Câu hỏi đặt ra là
liệu chúng ta có thể khai thác được gì từ những “núi” dữ liệu tưởng chừng như “bỏ đi”
ấy không ?
“Necessity is the mother of invention” - Data Mining ra đời như một hướng
giải quyết hữu hiệu cho câu hỏi vừa đặt ra ở trên []. Khá nhiều định nghĩa về Data
Mining và sẽ được đề cập ở phần sau, tuy nhiên có thể tạm hiểu rằng Data Mining như
là một công nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu
được tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó.
Khai phá dữ liệu là gì?
Khai phá dữ liệu (datamining) được định nghĩa như là một quá trình chắt lọc
hay khai phá tri thức từ một lượng lớn dữ liệu. Một ví dụ hay được sử dụng là là việc
khai thác vàng từ đá và cát, Dataming được ví như công việc "Đãi cát tìm vàng" trong
một tập hợp lớn các dữ liệu cho trước. Thuật ngữ Dataming ám chỉ việc tìm kiếm một
tập hợp nhỏ có giá trị từ một số lượng lớn các dữ liệu thô. Có nhiều thuật ngữ hiện
được dùng cũng có nghĩa tương tự với từ Datamining như Knowledge Mining (khai
phá tri thức), knowledge extraction(chắt lọc tri thức), data/patern analysis(phân tích dữ
liệu/mẫu), data archaeoloogy (khảo cổ dữ liệu), datadredging(nạo vét dữ liệu), .
Định nghĩa: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự
động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ
liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó.
Khai phá dữ liệu là một bước trong bảy bước của quá trình KDD (Knowleadge
Discovery in Database) và KDD được xem như 7 quá trình khác nhau theo thứ tự
sau:s
54 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1755 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Đề tài Vấn đề tìm kiếm và phân lớp văn bản, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
chóng đại lượng PageRank.
Đại lượng PageRank được định nghĩa như sau:
Giả sử trang A có các trang T1,T2,…,Tn trỏ tới. Tham số d là hệ số hãm có giá
trị trong khoảng 0 và 1. Chúng ta thường đặt d=0.85. C(A) là số liên kết ra từ trang A.
Khi đó PageRank của A được tính như sau:
PR(A)=(1-d)+d (PR(T1)/C(T1)+…+PR(Tn)/C(Tn)).
Vì PageRank của một trang là đại lượng đại diện cho sự phân bổ xác suẩt trên
các trang Web trong một tập các trang Web nhất định, do đó tổng các giá trị pagerank
của tất cả các trang Web trong tập các dữ liệu có giá trị bằng 1
Trang V1
Trang V2
Trang Vm
Trang U
RV1/ NV1
RV1/NVm
H×nh 2.2
Quá trình tính toán được lặp đi lặp lại cho đến khi hội tụ.
Với d=0.85, số vòng lặp =20 với khoảng vài triệu trang. Và để tính PageRank
cho 26 triệu trang web với một trạm làm việc vừa phải thì thời gian tiêu tốn tới vài giờ.
2.3. NHƯỢC ĐIỂM CỦA CÁC MÁY TÌM KIẾM
1. Là các hệ tìm kiếm tự động, người sử dụng chưa có vai trò gì trong quá
trình tìm kiếm, không có cơ chế phản hồi từ người sử dụng để cập nhật các tham số
tìm kiếm nhằm tăng hiệu quả cho lần tìm kiếm sau
2. Coi độ quan trọng của các từ khóa là như nhau, do đó chưa cho phép tính độ
quan trọng khác nhau của các từ khóa. Như trong các hệ tìm kiếm lớn như Google,
Yahoo, nếu đưa vào từ “System Information” thì hệ số tìm kiếm tất cả các trang Web
có liên quan đến 2 từ “System” và “Information”. Nếu người dùng muốn tìm kiếm từ
“Computer Story” mà trong đó từ Computer có nghĩa nhiều hơn từ Story (chẳng hạn,
từ Computer có trọng số 0.8, story có trọng số 0.2), thì vấn đề đặt ra là cần phải xây
dựng một hệ tìm kiếm như vậy
3. Chưa quan tâm đến bản chất của xử lý văn bản, vấn đề từ đồng nghĩa, đa
nghĩa
Có rất nhiều tài liệu liên quan đến nội dung cần tìm nhưng không chứa các từ
khóa đưa vào, mà chỉ chứa các từ đồng nghĩa với chúng và những tài liệu đó sẽ bị bỏ
qua trong quá trình tìm kiếm.
Vì các máy hầu hết tìm kiếm theo từ khóa, dựa vào việc đánh chỉ mục cho các
trang Web(index-base search engine), có thể có hàng trăm tài liệu cùng chứa từ khóa
đưa vào, dẫn đến một số lượng lớn tài liệu nhận được từ máy tìm kiếm, mà rất nhiều
trong chúng ít hoặc không liên quan đến nội dung cần tìm
2.4. BÀI TOÁN TÌM KIẾM MỚI
Hàng ngày có hàng tỷ người truy cập vào Internet và cũng có từng ấy người
thực hiện các thao tác tìm kiếm với các máy tìm kiếm khác nhau. Nếu thống kê các
thông tin của mỗi lần tìm kiếm này thì chắc chắn chúng ta sẽ được một nguồn thông
tin khổng lồ, và nểu biết cách sử dụng chúng thì sẽ làm được rất nhiều công việc hữu
ích. Các bài toán tìm kiếm trong các máy tìm kiếm thông thường chỉ đơn giản đáp ứng
nhu cầu tìm kiếm thông tin của khách hàng mà chưa biết tận dụng những thông tin từ
phía khách hàng qua mỗi lần tìm kiếm. Dưới đây là bài toán đề xuất thêm vào tính
năng của các máy tìm kiếm và hướng giải quyết trong tương lai.
Bài toán:
Căn cứ vào các tài liệu mà khách hàng xem hoặc down về, sau khi phân tích ta
biết được khách hàng đó hay tập trung vào các trang có nội dung gì trên tập các trang
Web của chúng ta, để từ đó bổ xung thêm nhiều tài liệu mà khách hàng quan tâm và
ngược lại. Còn về phía khác hàng sau khi phân tích chúng ta cũng biết được khách
hàng hay tập trung về vấn đề gì , từ đó có thêm những hỗ trợ cho khách hàng.
Hướng giải quyết:
Xây dựng một CSDL về các tài liệu, trong đó có một trường ClassificationID
cho biết tài liệu này thuộc lĩnh vực nào dựa trên kết quả đã phân tích trước đó.(Bằng
phân lớp)
Xây dựng một CSDL về phía khách hàng: Trước khi khách hàng truy cập vào
CSDL, yêu cầu đăng ký một account thông tin: tên, tuổi, địa chỉ,…chúng ta cũng đưa
thêm hai trường quan trọng là nghề nghiệp, trình độ (cho độ chính xác của thông tin là
c%). Yêu cầu đăng ký account là tuỳ chọn với khách hàng. Sau đó trong quá trình mỗi
lần khách hàng truy cập vào CSDL chúng ta sẽ ghi lại các tài liệu mà khách hàng truy
nhập vào bảng thông tin khách hàng. Sau đó dựa vào các thông tin về tài liệu mà
khách hàng truy nhập và thông tin về khách hàng, phân tích theo thuật toán cây quyết
định để sinh luật cho biết khách hàng khách hàng có nghề nghiệp và trình độ như thế
nào thì quan tâm đến lĩnh vực nào với độ tin cậy là ngưỡng c
2.5. KẾT LUẬN
Chương 3. BÀI TOÁN PHÂN LỚP
3.1. PHÁT BIỂU BÀI TOÁN
Trong tù nhiªn, con ng−êi th−êng cã ý t−ëng chia sù vËt thµnh c¸c phÇn,
c¸c líp kh¸c nhau. T−¬ng tù nh− vËy, gi¶i thuËt ph©n líp ®¬n gi¶n chØ lµ mét phÐp
¸nh x¹ c¬ së d÷ liÖu ®· cã sang mét miÒn gi¸ trÞ cô thÓ nµo ®ã, dùa vµo mét thuéc
tÝnh hoÆc mét tËp hîp c¸c thuéc tÝnh cña d÷ liÖu.
Phân lớp văn bản được các nhà nghiên cứu định nghĩa thống nhất như là
việc gán các chủ đề đã được xác định cho trước vào các văn bản Text đựa trên nội
dung của nó. Phân lớp văn bản là công việc được sử dụng để hỗ trợ trong quá trình
tìm kiếm thông tin (Inrmation Retrieval), chiết 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.Để phân loại văn bản, người ta sử dụng phương pháp học máy có
giám sát (supervised learning). Tập dữ liệu được chia ra làm hai tập là tập huấn
luyện và tập kiểm tra¸ trước hết phải xây đựng mô hình thông qua các mẫu học
bằng các tập huấn luyện, sau đó kiểm tra sự chính xác bằng tập đữ liệu kiểm tra.
Hình sau là môt khung cho việc phân lớp văn bản, trong đó bao gồm ba
công đoạn chính: công đoạn đầu là biểu diễn văn bản, tức là chuyển các dữ liệu
văn bản thành một dạng có cấu trúc nào đó, tập hợp các mẫu cho trước thành một
tập huấn luyện. Công đoạn thứ hai là việc sử dụng các kỹ thuật học máy để học
trên các mẫu huấn luyện vừa biểu diễn. Như vậy là việc biểu diễn ở công đoạn một
sẽ là đầu vào cho công đoạn thứ hai. Công đoạn thứ ba là việc bổ sung các kiến
thức thêm vào do người dùng cung cấp để làm tăng độ chính xác trong biểu diễn
văn bản hay trong quá trình học máy.
Trong công đoạn hai, có nhiều phương pháp học máy được áp dụng, mô
hình mạng Bayes, cây quyết định, phương pháp k ngườii láng giềng gần nhất,
mạng Neuron, SVM,…
D÷
liÖu
vµo
Gi¶i
thuËt
ph©n
líp
ho¹t
®éng
Líp 1
Líp 2
Líp n
3.2. CÁC PHƯƠNG PHÁP BIỂU DIỄN VĂN BẢN
3.2.1. Các phương pháp biểu diễn văn bản trong Cơ sở dữ liệu
FullText
Tồn tại ba mô hình CSDL FullText điển hình: Mô hình logic, mô hình cú pháp
và mô hình Vector
a. Mô hình phân tích cú pháp
a.1. Quy tắc lưu trữ:
- Mỗi văn bản đều phải được phân tích cú pháp và trả lại thông tin chi tiết về
chủ đề của văn bản đó.
- Sau đó tiến hành Index các chủ đề của từng văn bản. Cách Index trên chủ đề
giống như khi Index trên văn bản nhưng chỉ Index trên các từ xuất hiện trong chủ đề.
- Các văn bản được quản lý thông qua các chủ đề này để có thể tìm kiếm được
khi có yêu cầu, câu hỏi tìm kiếm sẽ dựa trên các chủ đề trên.
a.2. Quy tắc tìm kiếm:
Câu hỏi tìm kiếm sẽ dựa vào các chủ đề đã được Index. Vậy đầu tiên
phải tiến hành Index các chủ đề. Cách Index trên chủ đề giống như Index trên toàn bộ
các từ có trong chủ đề đó,
Câu hỏi đưa vào có thể được phân tích cú pháp để trả lại một chủ đềvà
tìm kiếm trên chủ đề đó
Như vậy bộ phận xử lý chính đối với một hệ CSDL xây dựng theo mô hình
này chính là hệ thống phân tích cú pháp và đoán nhận nội dung văn bản.
a.2. ¦u ®iÓm, nh−îc ®iÓm
¦u ®iÓm
Khi đã có sẵn chủ đề thì việc tìm kiếm theo phương pháp này lại khá hiệu quả
và đơn giản do tìm kiếm nhanh và chính xác.
Đối với những ngôn ngữ đơn giản về mặt ngữ pháp thì việc phân tích trên có
thể đạt được mức độ chính xác cao và chấp nhận được.
Nh−îc ®iÓm
Chất lượng của hệ thống theo phương pháp này hoàn toàn phụ thuộc vào chất
lượng của hệ thống phân tích cú phápvà đoán nhận nội dung tài liệu. Trên thực tế, việc
xây dựng hệ thống này là rất phức tạp, phụ thuộc vào đặc điểm của từng ngôn ngữ và
đa số vẫn chưa đạt đến độ chính xác cao.
b. Mô hình Logic
Theo mô hình này các từ có nghĩa trong văn bản được Index và nội dung văn
bản được quản lý theo các chỉ số Index đó.
b.1. Các quy tắc lưu trữ
- Mỗi văn bản được Index theo quy tắc:
Thống kê các từ có nghĩa trong các văn bản, đó là những từ mang thông tin
chính về các văn bản lưu trữ.
Index các văn bản đưa vào theo danh sách các từ khoá nói trên. Ứng với mỗi
từ khoá trong danh sách sẽ lưu vị trí xuất hiện nó trong từng văn bản và tên văn bản
tồn tại từ khoá đó.
Ví dụ, có hai văn bản với mã tương ứng là VB1,VB2.
“Cộng hòa xã hội chủ nghĩa Việt Nam” (VB1)
“ Việt Nam dân chủ cộng hòa” (VB2)
Khi đó ta có cách biểu diễn như sau:
b.2. Các quy tắc tìm kiếm:
Câu hỏi tìm kiếm được đưa ra dưới dạng Logic, tức là gồm một tập hợp các
phép toán (AND, OR,…) được thực hiện trên các từ hoặc cụm từ. Việc tìm kiếm sẽ
dựa vào bảng Index đã tạo ra và kết quả trả lại là các văn bản thoả mãn toàn bộ các
điều kiện trên
b.3. ¦u ®iÓm Nh−îc ®iÓm
¦u ®iÓm
- Tìm kiếm nhanh và đơn giản. Thựcvậy, giả sử cần tìm kiếm từ “computer”.
Hệ thống sẽ duyệt trên bảng Index để trỏ đến chỉ số Index tương ứng. Nếu từ
“computer” tồn tại trong hệ thống. Việc tìm kiếm này là khá nhanh và đơn giản khi
trước đó ta đã sắp xếp bảng Index theo vần chữ cái. Phép tìm kiếm trên có độ phức tạp
cấp θ(nlog2n), với n là số từ trong bảng Index. Tương ứng với chỉ số index trên sẽ cho
ta biết các tài liệu chứa nó.Như vậy việc tìm kiếm liên quan đến k từ thì các phép toán
cần thực ehiện là k*n*log2n, với n là số từ trong bảng Index
- Câu hỏi tìm kiếm nhanh và linh hoạt
Có thể dùng các kí tự đặc biệt trong câu hỏi tìm kiếm mà không làm ảnh
hưởng đến độ phức tạp của phép tìm kiếm. Ví dụ ta tìm “ta” thì kết quả sẽ trả lại các
văn bản có chứa các từ “ta”, “tao”, “tay”,…là các từ bắt đầu bằng từ “ta”
Kí tự % được gọi là kí tự đại diện (wildcard character).
Ngoài ra, bằng các phép toán Logic các từ cần tìm có thể tổ chức thành các
câu hỏi một cách linh hoạt. Ví dụ: Cần tìm từ [tôi, ta, tao], dấu “[]” sẽ thể hiện việc
tìm kiếm trên một trong số nhiều từ trong nhóm. Đây thực ra là một cách thể hiện linh
hoạt phép toán OR trong đại số Logic thay vì phải viết là: Tìm các tài liệu có chứa từ
“tôi” hoặc từ “ta” hoặc “tao”.
Từ mục MãVB_Vị trí XH
Cộng VB1(1), VB2(5)
Hòa VB1(2), VB2(6)
Xã VB1(3)
hội VB1(4)
chủ VB1(5), VB2(4)
nghĩa VB1(6)
Việt VB1(7), VB2(1)
Nam VB1(8), VB2(2)
Dân VB2(3)
Nhược điểm:
- Người tìm kiếm phải có chuyên môn trong lĩnh vực tìm kiếm
Thực vậy, do câu hỏi đưa vào dưới dạng Logic nên kết quả trả lại cũng có giá
trị Logic (Boolean). Một số tài liệu sẽ được trả lại khi thoả mãn mọi điều kiện đưa
vào. Như vậy muốn tìm được tài liệu theo nội dung thì phải biết đích xác về tài liệu.
- Việc Index các tài liệu là tốn nhiều thời gian và phức tạp.
- Tốn không gian để lưu trữ các bảng Index.
- Các tài liệu tìm được không được xắp xếp theo độ chính xác của chúng.
- Các bảng Index không linh hoạt. Khi các từ vựng thay đổi (thêm, xóa,…)
thì chỉ số Index cũng phải thay đổi theo
c. Mô hình không gian Vector
c.1. Quy tắc lưu trữ
Một trong những phương pháp điển hình để biểu diễn văn bản nói chung là sử
dụng không gian Vector. Trong cách biểu diễn này, mỗi văn bản được biểu diễn bằng
một vector. Mỗi thành phần của Vector là một từ mục riêng biệt trong tập văn bản
gốc(corpus)và được gán một giá trị là hàm f chỉ mật độ của từ mục trong văn bản.
Chúng ta có thể biểu diễn các văn bản dưới dạng với từ mục là các từ đơn và
hàm f biểu diến số lần xuất hiện của chúng, cách biểu diễn này còn gọi là biểu diễn
theo túi các từ (bag of words)
Chẳng hạn văn bản vb1, nó được biểu diễn bởi một vector V (v1,v2,…,vn)
Với vi là số lần xuất hiện của từ khóa thứ i (ti) trong văn bản vb1.
Ta xét hai văn bản sau:
Tõ Vector cho v¨n V
Computer 2 1
Is 1 1
Life 0 1
Not 1 0
Only 1 0
Có nhiều tiêu chuẩn để chọn hàm f, do đó mà chúng ta có thể sinh ra nhiều giá
trị trọng số khác nhau. Sau đây là một vài tiêu chuẩn để chọn hàm f
Computer is not only computer
Computer is life
Mô hình Boolean
Giả sử có một CSDL gồm m văn bản D={d1,d2,…,dm}. Mỗi văn bản được
biểu diễn dưới dạng một vector gồm n từ mục T={t1,t2,…,tn}. Gọi W=(wij) là ma trận
trọng số, trong đó wij là giá trị của từ mục ti trong văn bản dj.
Mô hình Boolean là mô hình đơn giản nhấ, được xác định như sau:
Wij = 0 nếu ti không có mặt trong dj
1 nếu ngược lại
Ví dụ chúng ta có hai văn bản sau:
Tõ Vector cho v¨n V
Computer 1 1
Is 1 1
Life 0 1
Not 1 0
Only 1 0
Mô hình tần số (Frequency Model)
Mô hình tấn số xác định giá trị các số trong ma trận W=(wij) các giá trị là các
số dương dựa vào tần số của cá từ suất hiện trong văn bản hoặc tần số xuất hiện của
văn bản trong CSDL. Có ba phương pháp phổ biến sau:
Phương pháp dựa trên tần số từ mục (TF_Term Frequency)
Các giá trị của các từ mục được tính dựa trên số lần xuất hiện của của cá từ
mục trong văn bản . Gọi tfij là số lần xuất hiện của từ mục ti trong văn bản dj, khi đó
wij được tính bởi công thức:
Wij = tfij hoặc wij = 1+log(tfij) hoặc w=tfij.
Phương pháp dựa trên nghịch đảo t số văn bản(IDF_ Inverse Document
Frequency)
Giá trị từ mục được tính bởi công thức sau:
Wij= log
dfij
m =log(m)- log(dfi)
Computer is not only computer
Computer is life
Phương pháp TF.IDE
Phương pháp này là tổng hợp của hai phương pháp TF và IDF, ma trận trọng
số được tính như sau:
Wij = [1+log(tfij)] log ( dfi
m ) nếu tfij >=1
0 nếu tfij =0
c.2. Các quy tắc tìm kiếm
Các câu hỏi đưa vào được ánh xạ vector Q(q1,q2,…,qm) theo hệ số của các từ
vựng là khác nhau. Tức là: Từ vựng càng có ý nghĩa với nội dung cần tìm có hệ số
càng lớn.
Qi =0 khi từ vựng đó không thuộc danh sách những từ cần tìm.
Qi0 khi từ vựng đó thuộc danh sách các từ cần tìm và Qi càng lớn thì mức
độ liên quan đến nội dung tài liệu càng cao. Tức là hệ thống sẽ ưu tiên hơn đối với các
tài liệu có chứa các từ tìm kiếm có hệ số cao.
Ví dụ: Nếu nội dung cần tìm có từ “Machine” quan trọng hơn từ “Computer”,
thì trong đó vector Q ta có thể đặt qk=2,qh=1 tương ứng với tk=”Machine”, th=”đa số”.
Khi đó, cho một hệ thống các từ vựng ta sẽ xác định được các vector tương
ứng với từng tài liệu và ứng với mỗi câu hỏi đưa vào ta sẽ có một vector tương với nó
với những hệ số đã được xác định từ trước. Việc tìm kiếm và quản lý sẽ được thực
hiện trên tài liệu này.
Từ cách xác định nội dung các tài liệu và câu hỏi theo các vector trệ cho ta
phương pháp tìm kiếm và lưu trữ các tài liệu dạng Full-Text theo cách mới như sau:
1. Mỗi tài liệu được mã hóa bởi một vector
2. Phân loại các tài liệu theo các vector nói trên.
3. Mỗi câu hỏi đưa vào cũng được mã hóa bởi một vector
Việc tìm kiếm các tài liệu được thực hiện bằng cách nhân lần lượt từng Vector
câu hỏi với vector của từng tài liệu
Kết quả trả lại sẽ là mọi tài có liên quan đến câu hỏi tìm kiếm
c.3. Ưu, nhược điểm
¦u ®iÓm
- Các tài liệu trả lại có thể được sắp xếp theo mức độ liên quan đến nội dung
yêu cầu do trong phép thử mỗi tài liệu đều trả lại chỉ số đánh giá độ liên quan của nó
đến nội dung yêu cầu.
- Việc đưa ra các câu hỏi tìm kiếm là dễ dàng và không yêu cầu người tìm
kiếm có trình độ chuyên môn cao về vấn đề đó
- Tiến hành lưu trữ và tìm kiếm đơn giản hơn phương pháp Logic. Người tìm
kiếm có thể tự đưa ra số các tài liệu trả lại có mức độ chính xác cao nhất
Nhược điểm
- Việc tìm kiếm tiến hành khá chậm khi hệ thống các từ vựng là lớn do phải
tính toán trên toàn bộ các Vector của tài liệu.
- Khi biểu diễn các Vector với các hệ số là số tự nhiên làm tăng mức độ chính
xác của việc tìm kiếm nhưng làm tốc độ tính toán giảm đi rẩt nhiều do các phép nhân
vector phải tiến hành trên các số tự nhiên hoặc số thực, hơn nữa việc lưu trữ các vector
sẽ tốn kém và phức tạp
- Hệ thống không linh hoạt khi lưu trữ các từ khóa. Chỉ cần một thay đổi rất
nhỏ trong bảng từ vựng sẽ kéo theo hoặc là vector hoá lại toàn bộ các tài liệu lưu trữ,
hoặc là sẽ bỏ qua các từ có nghĩa bổ sung trong các tài liệu được mã hóa trước đó. Tuy
nhiên, với những ưu điểm nhất định sự sai số nhỏ này có thể bỏ qua do hiện tại số các
từ có nghĩa được mã hóa khá đầy đủ trước khi tiến hành mã hóa tài liệu. Vì ậy phương
pháp Vector vẫn được quan tâm và sử dụng
- Một nhược điểm nữa, chiều của mỗi Vector theo cách biểu diễn này là rất
lớn, bởi vì chiều của nó được xác định bằng số lượng các từ khác nhau trong tập hợp
văn bản. Ví dụ số lượng các từ có thể có từ 103 đến 105 trong tập hợp các văn bản nhỏ,
còn trong tập hợpc ác văn bản lớn thì số lượng sẽ nhiều hơn, đặc biệt trong môi trường
Web
Cách khắc phục: Có một số phương pháp giảm bớt số chiều của Vector được
áp dụng. Một phương pháp đơn giản và hiệu quả là loại bỏ các từ dừng (stop words).
Từ dừng là các từ dùng để biểu diễn cấu trúc câu chứ không biểu đạt nội dung
văn bản, ví dụ như các từ nối, các giới từ…Những từ như vậy xuất hiện rất nhiều trong
văn bản nhưng lại không liên quan đến chủ đề và nội dung văn bản. Do đó chúng ta có
thể loại bỏ các từ này đi để làm giảm được số chiều của các vector biểu diễn mà lại
không làm ảnh hưởng gì đến hiệu quả tìm kiếm.
Một số ví dụ về các từ dùng
TiÕng ViÖt TiÕng Anh
Vµ a
HoÆc the
Còng do
about
3.2.2. Các phương pháp biểu diễn văn bản trong Cơ sở dữ liệu
HyperText
Trong chương I chúng ta đã nêu ra những khó khăn trong việc tìm kiếm dữ
liệu Web và sự khác nhau giữa cấu trúc một văn bản truyền thống với một văn bản
HyperText Chính v× nh÷ng khã kh¨n gÆp ph¶i nh− vËy mµ viÖc biÓu diÔn d÷ liÖu trong
c¸c m¸y t×m kiÕm lµ rÊt quan träng. BiÓu diÔn c¸c trang web nh− thÕ nµo ®Ó cã thÓ l−u
tr÷ ®−îc mét sè l−îng khæng lå c¸c trang web ®ã ®Ó m¸y t×m kiÕm cã thÓ thùc hiÖn
viÖc t×m kiÕm nhanh chãng vµ ®−a ra c¸c kÕt qu¶ chÝnh x¸c cho ng−êi sö dông?
a. Biểu diễn văn bản HyperText trong các máy tìm kiếm (inverted index)
Modul Indexer lấy các trang đã được Crawler down về chứa trong Repository,
Đánh chỉ sổ lưu vào CSDL. CSDL được tạo ra trong quá trình index. Đây là cấu trúc
chính của cơ sở dữ liệu trong hầu hết các máy tìm kiếm:
- Một File Từ khóa gồm các bản ghi, mỗi bản ghi tối thiểu có hai trường : Mã
số từ khóa, từ khóa. Các từ khóa này dược thiết lập trong quá trình Indexing
- File chứa các văn bản quản lý trong hệ thống gồm các bản ghi, mỗi bản ghi
cho một văn bản, tối thiểu có các trường là: Mã văn bản, tên văn bản (địa chỉ URL),
địa chỉ trong máy hệ thống chứa file văn bản (cache của các trang web đó)
- File chứa sự xuất hiện của các từ khóa trong văn bản gồm các bản ghi, mỗi
bản ghi có ba trường: mã số văn bản, mã số từ khóa, vị trí xuất hiện từ
khóa này trong văn bản
Ưu điểm: Biểu diễn được vị trí xuất hiện của các từ (Biết được từ khóa xuất
hiện trong các loại thẻ khác nhau, xuất hiện ở tiêu đề hay thân văn bản). Lưu trữ được
thông tin quan trọng của các từ khóa.
Nhược điểm: Chưa biểu diễn được tấn số xuất hiện của các từ khóa. Dẫn đến
thiếu chức năng tìm kiếm trangWeb theo nội dung
b. Biểu diễn văn bản HyperText theo mô hình Vector
Trong luận án tiến sỹ, tác giả Séan Slattery [May 2002_CMU-CS-02-142] đã
đưa ra 4 cách biểu diễn theo mô hình Vector cho tài liệu HyperText
Cách 1
Bỏ qua tất cả các thông tin liên kết giữa các tài liệu láng giềng mà chỉ biểu
diễn riêng nội dung tài liệu đang cần biểu diễn. Đây là cách biểu diễn theo “túi các từ”.
Nếu khẳng định được nội dung các tài liệu láng giềng là hoàn toàn độc lập với
lớp thì cách biểu diễn này là sự lựa chọn tốt. Thực tế là các tài liệu láng giềng cung cấp
khá nhiều thông tin hữu ích cho việc phân lớp, do vậy cách biểu diễn này là không hiệu
quả.
Cách 2
Cách thức đơn giản nhất nhằm sử dụng nội dung các tài liệu láng giềng là kết
hợp nội dung tài liệu cần biểu diễn với nội dung mọi tài liệu láng giềng của nó để tạo ra
một “super_document”. Khi đó, thành phần vector biểu diễn chính là tần suất xuất hiện
của từ khóa trong “super_document”.
Hạn chế của cách biểu diễn này chính là việc xóa nhòa phân biệt tài liệu đang
xét với láng giềng của nó, và vì thế tạo nên nhiều lộn xộn khi phân lớp. Cách biểu diễn
này chỉ tốt trong trường hợp các tài liệu được trỏ tới có cùng chủ đề với tài liệu cần
phân lớp.
Cách 3
Trong cách biểu diễn này, vector biểu diễn được chia thành hai phần: Phần đầu
biểu diễn các từ khóa trong chính tài liệu cần phân lớp, phần sau biểu diễn các từ khóa
xuất hiện trong tất cả các tài liệu láng giềng với nó.
Cách biểu diễn này khắc phục được nhược điểm của cách biểu diễn trước đó là
tránh làm mờ nhạt tài liệu đích với các tài liệu láng giềng. Nếu các tài liệu láng giềng
hữu ích cho việc phân lớp thì có thể dễ dàng truy cập đến nội dung của chúng. Tuy
nhiên cách biểu diễn này có nhược điểm là số chiều của Vector lớn.
Cách 4
Cách biểu diễn này được thể hiện qua các nội dung sau:
- Tìm số lượng trang láng giềng trong toàn bộ văn bản hypertext đang xem xét,
giả sử có d là số lượng láng giềng.
- Cấu trúc vector biểu diễn thành d+1 phần:
Phần đầu tiên biểu diễn trực tiếp tài liệu cần phân lớp.
Từ phần thứ 2 đến phần d+1 biểu diễn các tài liệu láng giềng, mỗi
phần tương ứng với một láng giềng.
Dễ nhận thấy vector nhận được là rất lớn và mặt khác, lại không tuân theo một
quy tắc duy nhất. Tồn tại nhiều cách chọn thứ tự từ phần thứ 2 trở đi. Chính vì sự đa
dạng trong cách biểu diễn của phương pháp này đã gây khó khăn trong việc lựa chọn
mẫu dữ liệu để xây dựng
Qua các cách biểu diẽn trên, chúng ta đưa ra một số nhận xét về cách biểu
diễn văn bản HyperText theo mô hình Vector như trình bày dưới đây.
Ưu điểm:
- Khai thác được thông tin tiềm năng của các siêu liên kết.
- Biểu diễn được tần số xuất hiện của các từ, nên có khả năng thực hiện chức
năng tìm kiếm văn bản theo “Độ gần nhau về nội dung”
Nhược điểm :
- Không biểu diễn được vị trí xuất hiện của các từ. Dẫn đến bỏ qua các thông
tin để lấy được độ quan trọng của từ khóa, như nếu từ khóa xuất hiện ở tiêu đề hay
trong các thẻ in đậm sẽ quan trọng hơn ở các vị trí khác
- Số chiều của Vector là rất lớn
III 2.2.3 Biểu diễn văn bản HyperText theo mô hình quan hệ
Biểu diễn văn bản theo mô hình quan hệ là cách biểu diễn tự nhiên cho văn
bản HyperText. Chúng ta dễ dàng cấu trúc một quan hệ nhị phân (mối liên kết giữa
các văn bản) mà đối số thứ nhất là tên của tài liệu có chứa các Hyperlink và đối số thứ
2 là tên của tài liệu được trỏ tới.
a) Quan hệ là gì
Để hiểu được những ưu thế của học quan hệ (relational learning), trước tiên
ta so sánh chúng với những thuật toán định đề (propositional algorithms) mà làm việc
với những ví dụ hay thực thể cô lập. Mọi điều mà học định đề cần biết về các ví dụ
huấn luyện chỉ là các miêu tả hay thông tin về chính ví dụ đó. Hơn nữa khi thực hiện
phân lớp cho một ví dụ, học định đề cũng chỉ quan tâm đến thông tin của chính ví dụ
đó mà không quan tâm đến mối liên hệ giữa ví dụ đó với các ví dụ khác.
Biểu diễn quan hệ bao gồm cả biểu diễn định đề (như biểu diễn theo mô hình
vector, túi các từ (bag of word), tập hợp các từ (set of word)) cùng với các thông tin về
mối quan hệ giữa các ví dụ với nhau. Chẳng hạn, nếu ví dụ huấn luyện của chúng ta là
people , biểu diễn định đề chỉ chỉ mô tả các thông tin như tên, tuổi, công việc,
lương,… của từng người, trong khi đó biểu diễn quan hệ sẽ biểu diễn tất cả những
thông tin trên cộng thêm một số thông tin khác nữa, ví dụ như mối quan hệ giữa ông
chủ-người làm thuê hay mối quan hệ hôn nhân.
Như vậy rõ ràng rằng một biểu diễn quan hệ cho ta một cơ hội để tìm kiếm
toàn bộ không gian giàu có của các mối quan hệ. Nếu chúng ta tin tưởng rằng các ví
dụ liên quan có thể là nguồn thông tin hữu ích cho sự phân lớp một vài ví dụ, thì cách
biểu diễn quan hệ là phù hợp, còn ngược lại, các ví dụ liên quan không cung cấp thêm
thông tin nào cần thiết thì cách biểu diễn quan hệ (relation representation) không thể
nào tốt hơn cách biểu diễn định đề (proposition representation)
Biểu diễn quan hệ trong cho HyperText
Các quan hệ :
Link_to (page, page): Mối quan hệ này thể hiện các siêu liên kết (hyperlink)
tham chiếu đến cấu trúc giữa các trang trong toàn bộ văn bản Web. Chúng ta có thể
biểu diễn rằng trang 15 chứa siêu liên kết tham chiếu đến trang 37 như sau: link_to
(page15, page37).
Has_word (page): Cung cấp thông tin về nội dung của mỗi trang Web. Chúng
ta sẽ chỉ biểu diễn những từ mà ta quan tâm (hay sau này sẽ chọn làm từ khóa). Chẳng
hạn has_computer(A) có nghĩa là trang A có chứa từ computer.
Ta có thể biểu diễn phủ định: not(link_to (page15, page37)) có nghĩa là
page15 không liên kết với page17, còn not(has_computer(A) có nghĩa là trang A
không có chứa từ computer
Ví dụ: Có hai trang Web A và B sau:
Giả sử A là trang chủ của sinh viên của tập hợp các trang Web của một trường
đại học
Khi đó trang A được biểu diễn như sau:
A:- has_engine(A), has_list(A), has_vector(A), link_to(B,A), has_jame(B),
has_link(B), has_paul(B), not(has_home(A))
Và nếu bằng ngôn ngữ thì ta có thể dịch ra thành luật như sau: Một trang mà
chứa các từ khóa list, vector, common nhưng không chứa từ khóa home, và được liên
kết bởi trang có chứa các từ jame, paul, link thì đó là trang chủ của sinh viên
A
List
Vector
Common
B
Jame
Paul
Link
3.3. CÁC PHƯƠNG PHÁP HỌC MÁY
3.3.1. Thuật toán phân lớp Bayes
Thuật toán phân lớp Bayes là một trong những thuật toán phân lớp điển hình
nhất trong khai thac dữ liệu và tri thức. Ý tưởng chính của thuật toán là tính xác suất
có sau của sự kiện c thuộc lớp x theo sự phân loại dựa trên xác suất có trước của sự
kiện c thuộc lớp x trong điều kiện T
Gọi V là tập tất cả các từ vựng.
Giả sử có N lớp tài liệu: C1, C2,…,Cn
Mỗi lớp Ci có xác suất p(Ci) và ngưỡng CtgTshi.
Gọi p(C| Doc) là xác suất để tài liệu Doc thuộc lớp C.
Cho một lớp C và một tài liệu Doc, nếu xác suất p(C|Doc) tính được lớn hơn
hoặc bằng giá trị ngưỡng của C thì tài liệu Doc sẽ thuộc vào lớp C.
Tài liệu Doc được biểu diễn như một vector có kích thước là số từ khoá trong
tài liệu. Mỗi thành phần chứa một từ trong tài liệu và tần xuất xuất hiện của từ đó
trong tài liệu. Thuật toán được thực hiện trên tập từ vựng V, vector biểu diễn tài liệu
Doc và các tài liệu có sẵn trong lớp, tính toán p(C|Doc) và quyết định tài liệu Doc sẽ
thuộc lớp nào.
Xác suất p(C | DOC) được tính theo công thức sau:
X¸c suÊt p(C | Doc) ®−îc tÝnh theo c«ng thøc sau:
Với:
p(c | x, τ) = Σ p(c | x,T) p(T |⎯x)
T in τ
Trong ®ã:
|V| : sè l−îng c¸c tõ trong tËp V
Fj : tõ kho¸ thø j trong tõ vùng
TF(Fj | Doc) : Tần xuất của từ Fj trong tài liệu Doc (bao gồm cả từ đồng
nghĩa)
TF(Fj | C) : Tần xuất của từ Fj trong lớp C (số lần Fj xuất hiện trong tất cả
các tài liệu thuôc lớp C)
P(Fj | C) : Xác suất có điều kiện để từ Fj xuất hiện trong tài liệu của lớp C
Công thức F(Fi | C) được tính sử dụng ước lượng xác suất Laplace. Sở dĩ
có số 1 trên tử số của công thức này để tránh trường hợp tần suất của từ Fi trong
lớp C bằng 0, khi Fi không xuất hiện trong lớp C.
Để giảm sự phức tạp trong tính toán và giảm thời gian tính toán, ta để ý
thấy rằng, không phải tài liệu Doc đã cho đều chứa tất cả các từ trong tập từ vựng
V. Do đó, TF(Fi | DOC) =0 khi từ Fi thuộc V nhưng không thuộc tài liệu Doc, nên
ta có, (P(Fj | C))TF(Fj, Doc) = 1. Như vậy công thức (1) sẽ được viết lại như sau:
Với:
Như vậy trong quá trình phân lớp không dựa vào toàn bộ tập từ vựng mà chỉ
dựa vào các từ khóa xuất hiện trong tài liệu Doc.
3.3.2. Thuật toán k-người láng giềng gần nhất.
ThuËt to¸n ho¹t ®éng kh«ng dùa vµo tËp tõ vùng. Tuy nhiªn, nã vÉn sö
dông ng−ìng CtgTsh, và thực hiện theo các bước như đã đề cập ở trên. Đó là tiến
hành ngẫu nhiên k tài liệu và tính xác suất p(C|Doc) dựa trên sự giống nhau giữa tài
liệu Doc và k tài liệu được chọn. Xác suất p(C| Doc) được tính theo công thức sau:
Trong ®ã:
n : Số lớp
k : Số tài liệu được chọn để so sánh
P(Ci | Dj ) : Có giá trị 0 hoặc 1, cho biết tài liệu Dj có thuộc lớp Ci
không. Sở dĩ có giá trị này vì một tài liệu có thể thuộc hơn một lớp
Sm(Doc,Dj) xác định mức độ giống nhau của tài liệu Doc với tài liệu được
chọn Dj , được tính bằng cos của góc giữa hai Vector biểu diễn taì liệu Doc và tài liệu
được chọn Dj.
Cách biểu diễn các tài liệu trong thuật toán này hoàn toàn tương tự như trong
thuật toán phân lớp Bayes thứ nhất, nghĩa là cũng gồm Fi từ khóa và tấn xuất Xi
tương ứng.
Trong c«ng thøc (4):
Xi lµ tÊn xuÊt cña tõ kho¸ thø i (dùa trªn sè tõ ®ång nghÜa xuÊt hiÖn trong tµi
liÖu Doc)
Yi lµ tÇn xuÊt cña tõ thø i (dùa trªn sè tõ ®ång nghÜa xuÊt hiÖn trong tµi liÖu
Di)
3.3.3. Phân lớp dựa vào cây quyết định
Học cây quyết định là phươgn pháp được sử dụng rộng rãi cho việc học quy
nạp từ một mẫu lớn. Đây là phương pháp xấp xỉ hàm mục tiêu có giá trị rời rạc. Mặt
khác, cây quyết định còn có thể chuyển sang dạng biểu diễn tương đương dưới dạng
tri thức là các luật If-then. Trong các thuật toán học cây quyết định thì ID3 và C4.5 là
hai thuậta toán nổi tiếng nhất. Sau đây là nội dung thuật toán ID3.
ID3 (Example, Target attributes, Attributes)
1.Tạo một nút gốc Root cho cây quyết định
2. Nếu toàn bộ Examples đều là các ví dụ dương, tả lại cây Root một nút
đơn, với nhãn +.
3. Nếu toàn bộ Examples đều là các ví dụ âm, trả lại cây Root một nút đơn,
với nhãn -.
4. Nếu Attributes là rỗng thì trả lại cây Root một nút đơn với gàn nhãn bằng
giá trị phổ biến nhất của Target_attribute trong Example.
5. Ngược lại Begin
5.1. A<= thuộc tính từ tập Attribute mà phân loại tốt nhất tập Examples
5.2. Thuộc tính quyết định cho Root<=A
5.3. For mỗi giá trị có thể có vi của A
5.3.1. Cộng thêm một nhánh cây con ở dưới Root, phù hợp với
biểu thức kiểm tra A=vi.
5.3.2. Đặt Examplesvi là một tập con của tập các ví dụ có giá trị
vi cho A
5.3.3. Nếu Examplesvi rỗng
-Dưới mỗi nhánh mới thêm một nút lá với nhẵn bằng giá
trị phổ biến nhất của Target_attribute trong tập Examples
-Ngược lại thì dưới nhánh mới này thêm một cây con
ID3(Examples, target_attribute, Attribute-{A}).
End
Return Root.
Thuộc tính tốt nhất là thuộc tính có độ lấy thông tin lớn nhất.
Phương pháp học máy dùng cây quyết định và dựa trên cây quyết định là rất
hiệu quả bởi vì nó có thể làm việc được với một số lượng lớn các thuộc tính, và hơn
nữa từ cây quyết định có thể rút ra được một hệ thống luật học được
3.3.4. Thuật toán học quan hệ FOIL
a. Khái niệm mệnh đề Horn (Horn Clause)
Mệnh đề Horn là các mệnh đề có nhiều nhất một literal dương, có dạng như
sau:
H \/ (-L1)\/ (-L2)\/…\/ (-Ln))
Trong đó H, L1,L2,…,Ln gọi là các literal dương, còn –L1,-L2,…-Ln gọi là
các literal âm.
Hay viết dưới dạng luật:
( L1^L2^…^Ln)=>H. Dạng này được gọi là luật First_Order
L1,L2,…Ln gọi là tập các tiền điều kiện. H gọi là kết luận.
VD về các luật First_Order:
If Parents(x,y) then Ancestor (x,y)
If (Parents(x,z) ^ Ancestor(z,y) ) then Ancestor(x,y).
Trong đó Parents, Ancestor,… gọi là các predicate
b.Thuật toán Foil
FOIL ®−îc ®Ò xuÊt vµ ph¸t triÓn bëi Quinlan (Quinlan, 1990). FOIL häc c¸c
tËp d÷ liÖu chØ bao gåm hai líp, lớp các ví dụ “d−¬ng” và ví dụ “âm”. FOIL häc m«
t¶ líp ®èi víi líp “d−¬ng”. Đầu vào của Foil gồm các tiền điều kiện và các kết luận. .
Đầu ra là một tập các luật sinh từ các tiền điều kiện và các kết luận đó. Mỗi bước Foil
sẽ thêm một literal vào các tiền điều kiện của luật đang huấn luyện. Thuật toán sử
dụng hàm Foil_Gain để tính toán lựa chọn một literal trong tập các literal ứng cử
FOIL lµ m« h×nh häc m¸y kh«ng t¨ng trong thuËt to¸n “leo ®åi” sö dông
metric dùa theo lý thuyÕt th«ng tin x©y dùng mét luËt bao trïm lªn d÷ liÖu. Trong
Foil có hai trạng thái chính :
1. separate stage (trạng thái phân tách) : Bắt đầu một trạng thái mới
2. Conquer State (trạng thái chế ngự): Kết hợp các literal để xây dựng thân
của mệnh đề.
Pha “t¸ch rêi” cña thuËt to¸n b¾t ®Çu tõ luËt míi trong khi pha “chÕ ngù” x©y
dùng mét liªn kÕt c¸c literal lµm th©n cña luËt. Mçi luËt m« t¶ mét tËp con nµo ®ã c¸c
vÝ dô d−¬ng vµ kh«ng cã vÝ dô ©m. L−u ý r»ng, FOIL cã hai to¸n tö: b¾t ®Çu mét luËt
míi víi th©n luËt rçng vµ thªm mét literal ®Ó kÕt thóc luËt hiÖn t¹i. FOIL kÕt thóc viÖc
bæ sung literal khi kh«ng cßn vÝ dô ©m ®−îc bao phñ bëi luËt, vµ b¾t ®Çu luËt míi ®Õn
khi tÊt c¶ mçi vÝ dô d−¬ng ®−îc bao phñ bëi mét luËt nµo ®ã.
C¸c vÝ dô d−¬ng ®−îc phñ bëi mÖnh ®Ò sÏ ®−îc t¸ch ra khái tËp d¹y vµ qu¸
tr×nh tiÕp tôc ®Ó häc c¸c mÖnh ®Ò tiÕp theo víi c¸c vÝ dô cßn l¹i, vµ kÕt thóc khi kh«ng
cã c¸c vÝ dô d−¬ng thªm n÷a.
Sau đây là thiết kế bước 1 của FOIL:
1.Gọi POS là tập các ví dụ dương.
2. Gọi NEG là tập các ví dụ âm
3. Đặt NewClauseBody bằng rỗng
4. Trong khi POS chưa rỗng thực hiện:
Separate: (Bắt đầu một luật mới)
5. Loại khỏi POS tất cả những ví dụ thoả mãn NewClauseBody.
6. Đặt lại NEG là tập các ví dụ âm ban đầu
7. Đặt lại NewClauseBody bằng rỗng
Trong khi NEG chưa rỗng thực hiện.
. Conquer (Xây dựng thân mệnh đề)
8. Chọn Literal L
9. Kết hợp vào NewClauseBody.
10. Loại khỏi NEG những ví dụ mà không thoả mãn L.
FOIL sö dông thuËt to¸n leo ®åi ®Ó bæ sung c¸c literal víi th«ng tin thu ®−îc
lín nhÊt vµo mét luËt. Víi mçi biÕn ®æi cña mét kh¼ng ®Þnh P, FOIL ®o l−îng th«ng
tin ®¹t ®−îc. §Ó lùa chän literal víi th«ng tin ®¹t ®−îc cao nhÊt, nã cÇn biÕt bao nhiªu
bé d−¬ng vµ ©m hiÖn t¹i ®−îc b¶o ®¶m bëi c¸c biÕn ®æi cña mçi kh¼ng ®Þnh ®−îc x¸c
®Þnh theo c¸ch dµn tr¶i.
Công thức tính infortmaion gain của Foil là:
Gain(Literal)=T++ *(log2(P1/P1+N1) - log2(P0/P0+N0))
P0 và N0 là số ví dụ dương và âm trước khi thêm một literal L vào mệnh đề
P1 và N1 là số ví dụ dương và âm sau khi thêm literal L vào mênh đề.
T++ là số ví dụ dương cố định cả trước và sau khi thêm literal .(nghĩa là số ví
dụ đúng với cả hai luật R và R’_là R sau khi đã thêm vào literal L)
Sau đây là một ví dụ minh họa cho thuật toán FOIL.
Ta muốn học mối quan hệ Grandaughter(x,y) từ các quan hệ (Predicate)
Grandaughter, Father, Mail, Femail và các hằng số: Victor, Sharon, Bob, Tom.
Tập ví dụ: Là những giả định liên quan đến các Predicate Grandaughter,
Father, Mail, Femail và các hằng số Victor, Sharon, Bob, Tom, trong đó có các ví dụ
dương là Grandaughter(Victor, Sharon), Father (Sharon, Bob), Father(Tom, Bob),
Femail(Sharon), Father(Bob, Victor). Các ví dụ còn lại là âm (Chẳng hạn như
-Grandaughter(Tom,Bob),-Father(Victor, Victor),…).
Để chọn các literal cho luật, FOIL xét các cách kết hợp khác nhau của các
biến x,y,z,t với các hằng số ở trên. Chẳng hạn bước khởi đầu khi luật chỉ là :
- Bước 1:
Luật khởi đầu: Grandaughter (x,y) Å
Sự kết hợp {x/Bob, y/Sharon}sẽ cho ta một ví dụ dương vì trong dữ liệu
huấn luyện Grandaughter(Bob, Sharon) là đúng.
Còn 15 cách kết hợp còn lại sẽ tương ứng với các ví dụ âm vì không tìm thấy
sự xác nhận tương ứng trong tập huấn luyện
- Mỗi trạng thái tiếp theo, luật được hình thành dựa trên tập các kết nối mà
cho ra các ví dụ dương, âm. Khi mỗi literal được thêm vào luật, tập các ví dụ âm
dương sẽ thay đổi. Chẳng hạn xét literal tiếp theo để đề cử vào luật là Father (y,z), thì
thay ví kết nối {x/Bob,y/Sharon} ở trên, kết nối {x/ Bob, y/Sharon,z/ Bob} mới
tưong ứng với một ví dụ dương. Tại mỗi bước, số ví dụ âm, dương sẽ được tính toán
để có được độ lấy thông tin Foil_Gain (L,R).
CHƯƠNG 4. HỆ THỐNG THỬ NGHIỆM
4.1. MỘT SỐ CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN
Hệ thống thử nghiệm được xây dựng dựa trên sự kết hợp những ưu điểm của
các giải pháp trong các công trình nghiên cứu về vấn đề tìm kiếm và phân lớp văn bản
trước đây. Sau đây là nội dung và kết quả của các công trình nghiên cứu
1.. [Séan Slattery (May 20002_CMU-CS-02-142)] Luận án tiến sỹ ”HyperText
Classification”
Trong luận án tiến sĩ của mình, tác giả đã so sánh các thuật toán học máy áp dụng
cho phân lớp trang Web cùng với các cách biểu diễn tương ứng, đó là:
1. Dùng Naïve Bayes với cách biểu diễn tài liệu thành một túi các từ (bag of
words)
2. Dùng k người láng giềng gần nhất với mô hình tấn số cho biểu diễn trang
Web (TF-IDF)
3. Thuật toán FOIL với cách biểu diễn thành tập các từ (set of words) cho mỗi
tài liệu (không tính đến các liên kết trong mỗi tài liệu)
4. Thuật toán FOIL với cách biểu diễn thành tập các từ (set of words) và có tính
đến các thông tin liên kết trong các tài liệu
Tác giả đã cài đặt và thử nghiệm và đưa ra kết quả, với tiêu chuẩn đánh giá là Độ
hồi tưởng(recall)và Độ chính xác( Precision)
Cách tiếo cận 4 ưu điểm hơn cả, cho độ hồi tưởng và độ chính xác cao hơn hẳn.
Tiếp đến, tác giả đã xây dựng một bộ phân lớp HyperText mới sử dụng thuật toán
FOIL_PILES với cách biểu diễn văn bản theo mô hình quan hệ.
2. [Đoàn Sơn] Luận văn thạc sĩ ”Phương pháp sử dụng Logic mờ và ứng dụng trong
khai phá dữ liệu FullText”
Trong luận văn này, tác giả thực hiện phân lớp văn bản sử dụng cách biểu diễn văn
bản bằng phương pháp sử dụng Logic mờ và ứng dụng thuật toán học cây quyết định.
Với cách giải quyết bài toán như vậy đã cho ta thấy một số ưu điểm: Sử dụng các
khái niệm mờ đã làm giảm số chiều của các thuộc tính, dẫn đến làm giảm thời gian
tính toán khi học cây quyết định.
Tuy nhiên cách biểu diễn này còn có một số mặt hạn chế, đó là việc con người có
thể sẽ tốn nhiều công sức cho việc xây dựng chủ đề, các khái niệm và mối liên quan
giữa chúng.
3. [Bùi Quang Minh] “Máy tìm kiếm Vietseek”. Báo cáo kết quả nghiên cứu thuộc đề
tài khoa học đặc biệt cấp ĐHQGHN mã số QG 02-02.
Trong máy tìm kiếm Vietseek, các văn bản được tổ chức thành cơ sở dữ liệu.
Vietseek đã xây dựng được cả ba loại chỉ mục (TextIndex, StructureIndex và
UtilityIndex). Cơ sở dữ liệu Vietseek được chia thành hai phần:
Phần 1: Dữ liệu về văn bản Web, Domain, Word được lưu trữ trong các bảng của
CSDL mySQL
Phần 2: Dữ liêu về chỉ mục (index) được lưu trữ riêng và có cơ cấu riêng. Do phần
này đòi hỏi tốc độ cao nên không lưu trữ trong CSDL MySql mà lưu trữ trong 300 file
nhị phân khác nhau.
Vietseek thực hiện tìm kiếm theo cụm từ đưa vào và trả về các văn bản có chứa các
cụm từ khóa đó chứ chưa thực hiện phân lớp
4. [Phạm Thị Thanh Nam] Luận văn Thạc sỹ “Một số giải pháp cho bài toán tìm kiếm
trong CSDL HyperText”.
Từ CSDL chỉ mục đã được xây dựng của Vietsek, tác giả đã xây dựng nên vector
biểu diễn các trang Web, với thành phần của vector chính là tần suất xuất hiện của các
từ khóa trong văn bản đang xét.
Luận văn này đề xuất một số thuật toán:
- Liệt kê danh sách các trang Web “Gần nghĩa nhất” với trang Web hoặc cụm từ
tìm kiếm đưa vào theo tiêu chí “Gần nhau về nội dung”. Độ gần nhau về nội dung sẽ
thu được khi so sánh các vector biểu diễn với nhau
- Độ quan trọng của trang Web dựa vào mối liên kết với trang Web khác và tần số
xuất hiện của các từ khóa tìm kiếm trong trang.
- Kết hợp độ gần nhau về nội dung và độ quan trọng của trang web thành một tiêu
chí gọi là “giá trị kết hợp”. Kết quả sẽ được hiển thị theo “giá trị kết hợp”.
Nhận xét
Tuy công trình đầu tiên [Séan Slattery] đã giới thiệu khá tổng quan về các
phương pháp phân lớp và phân tích một số kết quả thử nghiệm, nhưng nói chung cả
bốn công trình nghiên cứu nói trên chưa thực sự đề cập tới vấn đề thiết kế và cài đặt
những giải pháp thực sự tinh tế giải quyết vấn đề từ đồng nghĩa và đa ngôn ngữ đối với
hệ thống phân lớp trong CSDL Web. Thực hiện việc khảo sát những giải pháp cho vấn
đề này và cài đặt thử nghiệm là một công việc nghiên cứu có ý nghĩa.
Tồn tại một số thuật toán điển hình giải quyết bài toán phân lớp trong các CSDL
văn bản. Việc cài đặt thử nghiệm và đánh giá hiệu quả hoạt động của một số thuật toán
phân lớp điển hình như vậy trong một CSDL web thực sự (khoảng vạn trang ) có thể
được coi như những bước đi cần thiết đầu tiên trong việc xây dựng và phát triển các
máy tìm kiếm tiếng Việt.
4.2. ĐỀ XUẤT MỘT CÁCH TỔ CHỨC CSDL VÀ THUẬT TOÁN ÁP
DỤNG
Theo những phương pháp biểu diễn văn bản HyperText đã và đang được sử dụng,
nghiên cứu, ta có nhận xét tổng quát sau: cách biểu diễn văn bản HyperText trong các
máy tìm kiếm có ưu điểm là khai thác được những thông tin quan trọng về vị trí xuất
hiện của từ khóa, để từ đó xếp hạng được các trang Web tìm được theo thứ tự gần với
nội dung từ khóa cần tìm, nhưng chưa thấy đề cập đến tần số xuất hiện của các từ
khóa trong văn bản. Nên việc tìm theo nội dung là khó thực hiện được.
Còn với cách biểu diễn theo mô hình Vector của Seán Slattery [2002] thì đã bỏ
qua thông tin về vị trí xuất hiện của các từ khóa, một thông tin rất quan trọng cho
phân lớp văn bản. Hơn nữa nếu theo cách biểu diễn 2, văn bản gốc cần phân lớp sẽ bị
mờ nhạt đi trong tập hợp các văn bản liên qua đến nó, vì phân lớp sẽ mất chính xác
nhất là khi các văn bản liên quan không có cùng chủ đề. Còn với cách biểu diễn 3 và
4, số chiều của vector sẽ rất lớn và có rất nhiều thành phần lặp (chính là các từ xuất
hiện lặp đi lặp lại trong tập các văn bản liên quan).
Từ những ưu nhược điểm của các phương pháp trên, đề tài đưa ra một cách biểu
diễn riêng. Ý t ưởng chính vẫn là dựa trên mô hình vector, đồng thời trong cách xây
dựng file từ khóa có tính đến các từ đồng nghĩa
4.2.1. Đặt bài toán
Tồn tại một tập các văn bản HyperText cho trước, mỗi lớp chứa các tài liệu (dưới
dạng *.html) thuộc cùng một thể loại. Xây dựng hệ thống với chức năng:
Đọc một tài liệu mới, yêu cầu hệ thống phân tài liệu đó vào một lớp thích hợp.
4.2.2. Cách biểu diễn văn bản:
Sử dụng mô hình Vector tính tần suất có tính đến độ quan trọng của vị trí xuất
hiện các từ khóa, cùng với các liên kết giữa các trang
Xây dựng vector cho trang Web A bằng cách:
- Với mỗi trang Web A nào đó, thống kê các trang Web có liên kết tới A và được
A trỏ tới.
- Đếm số lần của mỗi từ khóa xuất hiện trong A và trong các trang có liên quan
đến A, giả sử count[i] là số lần xuất hiện của từ khóa thứ i trong vector biểu diễn của
trang A,
Nếu i xuất hiện trong thẻ body () thì chỉ tăng count[i] lên 1,
Nếu từ i xuất hiện trong thẻ tiêu đề () thì tăng count[i] lên 3,
Sau khi đếm xong trang A, nhân count [i] với 3 (chính là trọng số của văn bản cần
biểu diễn), sau đó đếm tiếp trong các trang có liên kết, với nguyên tắc tính trọng số vị
trí xuất hiện như trong văn bản A, trọng số của các văn bản liên quan bằng 1.
Như vậy: Cách biểu diễn trên đã sử dụng kết hợp được các thông tin: Các liên
kết vào ra của tài liệu HyperText, tính đến các tài liệu láng giềng nhưng cũng đặt ra
trọng số cho tài liệu gốc, biểu diễn được số lần xuất hiện của từ khóa trong tài liệu
đồng thời tính đến vị trí xuất hiện của các từ khóa đó trong tài liệu
4.2.3. Thiết kế CSDL.
Các văn bản HyperText được mã hóa thành 3 bảng trong CSDL Access.
1. Bảng 1: bảng các từ khóa (KeyWords),
Field Name Data Type Description
KeyWordID
KeyWord
Synonymous
Auto Number
Text
Memo
Mã từ khóa
Từ khóa
Các từ đồng nghĩa với từ khóa
Từ khóa (KeyWord) : Nội dung là một từ trong tiếng Anh nên nó phải thỏa mãn
các điều kiện sau: Từ trong tiếng Anh có một âm tiết, mỗi âm tiết là một chuỗi ký tự a-
z,A-Z. Các từ trong câu được tách biệt bởi dấu cách hoặc các ký tự bất kỳ (dấu chấm,
dấu phảy, dấu hai chấm,…) không thuộc a-z, A-Z.
Các từ đồng nghĩa (Synonymous): Là trường memo có dạng (word1,
word2,…,wordn ). Vậy các từ đồng nghĩa có cùng mã (keywordID) với từ khóa.
2. Bảng 2: Bảng các văn bản (Documents)
Field Name Data Type Description
DocID
DocName
CacheAdd
Vector
Auto Number
Text
Text
Memo
Mã văn bản
Tên văn bản
Địa chỉ Cache
Vector biểu diễn cho văn bản đó
Vector: là trường kiểu Memo, mỗi vector có dạng:
(Mã từ khóa 1, số lần xuất hiện ở tiêu đề, tổng số lần xuất hiện trong văn
bản);( Mã từ khóa 2, số lần xuất hiện ở tiêu đề, tổng số lần xuất hiện trong văn
bản);…
Số thành phần của Vector chính là số từ khóa xuất hiện trong trang Web đang
biểu diễn, chứ không phải là toàn bộ các từ khóa trong bảng KeyWord, do đó số chiều
của vector sẽ giảm đi rất nhiều. Mỗi thành phần của vector biểu diễn số lần xuất hiện
và vị trí xuất hiện của các từ khóa trong văn bản.
VD: Một Vector có dạng: (1,1,4);(2,1,4);(4,2,7) có ý nghĩa: Từ khóa thứ nhất
xuất hiện 4 lần, trong đó 1 lấn xuất hiện ỏ tiêu đề. Tứ khoá thứ 2 xuất hiện 4 lần trong
đó 1 lần xuất hiện ở tiêu đề Tứ khoá thứ 4 xuất hiện 7 lần trong đó 2 lần xuất hiện ở
tiêu đề
DocID Cache Address Vector
1
2
3
4
C:\data\sport\s1.htm
C:\data\sport\s2.htm
C:\data\culture \ct3.htm
C:\data\ culture \c4.htm
(1,1,4); (3,1,4); (4,2,7);….
(1,2,7); (2,1,4); (3,2,8);….
(1,2,6); (5,1,4); (7,2,7);….
(2,1,4); (3,1,4); (4,2,7);….
3.Bảng 3 Thể hiện sự kiên kết giữa các văn bản. (LINKS)
Field Name Field Type Descrription
DocID1
DocID2
Number
Number
Mã của văn bản liên kết đi
Mã văn bản được liên kết tới
DocID1 là mã các văn bản có liên kết tới các văn bản có mã trong DocID2.
4. Bảng 4. Xác suất của các lớp
4.2.4.Thiết kế Modul chương trình
Field name Fielsd type Description
ClassName
Probability
Text
Number(từ 0..100)
Tên lớp
Xác suất để có lớp
1.Modul phân tích trang Web để tạo ra bảng KEYWORDS
Thuật toán:
Input: Các văn bản dùng để tạo từ khóa
While (chưa đọc hết các văn bản) do
1. Đọc từng văn bản
2. While (chưa đọc xong văn bản) do
2.1.Đọc từng từ
2.2. Insert vào Cơ sở dữ liệu
End
End.
Output: File các từ khóa
Truờng Synonymous sẽ được bổ sung bằng tay đối với từng từ khóa
Thêm chức năng nhập thêm từ khóa bằng tay, xóa từ khóa không cần thiết.
2.Modul lấy địa chỉ Cache (CacheAddress) của từng tài liệu huấn luyện và tạo
ra mã tài liệu (DocID) để thêm vào hai trường đầu tiên của các bảng DOCUMENTS.
Còn trường Vector sẽ tạo sau nhờ Modul thứ 4.
Thuật toán:
Input: Các văn bản dùng để huấn luyện
While (chưa đọc hết các văn bản) do
1.1. Đọc địa chỉ Cache của từng văn bản
Insert vào CSDL
1.2. Đọc tên văn bản
Insert vào CSDL
End
Mã văn bản tự tăng.
3.Modul tạo bảng LINKS. Để tạo bảng LINKS trước hết phải có bảng
DOCUMENTS để lấy địa mã của từng tài liệu (DocID) tương ứng.
Thuật toán:
1. Đọc từ thư mục chứa các tài liệu từ trên đĩa cứng
2. Đặt biến TênTM=[đường dẫn của thư mục]
3. While (chưa phân tích hết các tài liệu) do
3.1. Lấy từng tài liệu trong thư mục kèm thêm địa chỉ Cache(CacheAdd).
3.2. Tìm trong bảng DOCUMENTS DocID của tài liệu này nhờ vào
CacheAdd, được DocID1
3.2.1. Phân tích để lấy được các thẻ siêu liên kết, đó là các cụm từ có
dạng: href=[Tên tài liệu được trỏ tới], giả sử có N thẻ.
3.2.2. For i=1 to N do
3.2.2.1. Cộng TênTM và [tên tài liệu được trỏ tới] được địa chỉ
Cache, duyệt trong DOCUMENTS để lấy DocID, được
DocID2
3.2.2.2.Thực hiện lệnh Insert hai DocID đã lấy được ở trên vào hai
trường DocID1 và DocID2 của bản LINKS
End.
End
4. Trả lại bảng LINKS trong CSDL
4. Modul tạo ra vector cho mỗi tài liệu, thêm vào trường Vector của bảng
DOCUMENTS.
Thuật toán:
1. Đọc từ bảng DOCUMENTS trong CSDL để lấy DocID và CacheAdd
2. While (chưa đọc hết các bản ghi)
2.1. Dùng CacheAdd để đọc tài liệu từ đĩa cứng
2.2. Gán DocID_curence=DocID
2.3. Gán total_occurence=0; header_occurence=0; vector=””;
2.4. Lấy từng từ khóa keyword trong bảng KEYWORDS để so sánh
2.4.1 While (chưa hết các từ khóa)
2.4.1.2. Phân tích tài liệu để lấy từng từ mục : word
2.4.1.2. Kiểm tra xem nếu word chưa có trong bảng KEYWORD thì bổ
sung thêm
2.4.1.3. While (chưa đọc hết tài liệu)
- Nếu (word= keyword) hoặc (word=từ đồng nghĩa) và (word nằm trong
thẻ ) thì total_occurence+3 và header_occurence+1;
- Nếu (word=keyword) hoặc (word=từ đồng nghĩa) và (word không nằm
trong thẻ ) thì total_occurence ++; header_occurense++;
End.
2.4.1.4. total_occurence*3;
header_occurence*3;
2.4.1.5. Đọc tất cả các tài liệu mà tài liệu hiện thời liên kết tới(outgoing)
Lặp lại các bước phân tích như đối với tại liệu hiện thời, để tăng 2 biến
total_occurence và header_occurence
2.4.1.6. Đọc tất các tài liệu liên kết tới tài liệu hiện thời (incoming)
Lặp lại các bước phân tích như đối với tài liệu hiênh thời để tăng 2 biến
total_occurence và header_occurence
End.
2.5. Nếu (total_occurence !=0 ) thì vector += KeyWordID + “,” +
total_occurence + “,” + header_occerence +”;”
2.6. Insert into DOCUMENTS (Vector) values vector where
DocID=DocID_curence.
3. End.
5. Modul thực hiện phân lớp.
Input:Tập hợp các tài liệu cần phân lớp.
While (chưa đọc hết tài liệu) do
Đọc vào tài liệu cần phân lớp
1. Phân tích tài liệu thành các vetor như trong modul tạo trường vector
của bảng DOCUMENTS
2. Kết hợp với các vector của các tài liệu trong CSDL, áp dụng một trong
các thuật toán học máy để phân lớp.
End
4.2.5. Phân tích các chức năng của hệ thống
a. Chức năng chính của hệ thống
b. Chức năng chi tiết
- Chức năng tạo CSDL
- Chức năng phân lớp và tìm kiếm
4.2.6. Đánh giá hệ thống thử nghiệm
a. Một số ví dụ kết quả trên hệ thống thử nghiệm
Hệ thống đã chạy và cho một số kết quả ban đầu
- Xây dựng được hệ thống CSDL như đã trình bày ở trên
+ Phân tích các văn bản để lấy từ khóa
+ Thể hiện được các liên kết (link) giữa các tài liệu siêu văn bản trong một siêu
văn bản
+ Mã hóa các văn bản thành các vector và lưu trữ vào CSDL
- Thực hiện việc phân lớp một tài liệu siêu văn bản cho trước
- Cho phép tìm kiếm một tài liệu siêu văn bản có nội dung gần với tài liệu đưa vào
b. Hạn chế của hệ thống
Do hạn chế về mặt thời gian nên hệ thống còn có một số mặt hạn chế
- Các từ khóa vẫn chưa đầy đủ và chưa có chọn lọc
- Chỉ phân lớp được từng tài liệu một (nếu còn thời gian sẽ tiếp tục sửa)
- Độ chính xác chưa cao do chưa có dữ liệu học chính xác.
Các file đính kèm theo tài liệu này:
- K44_Do_Thi_Dieu_Ngoc_Thesis.pdf