Dựa vào các nghiên cứu gần đây trong bài toán xửlý văn bản, khóa luận đã
nghiên cứu, chọn lọc cũng nhưphát triển một sốvấn đềvà đạt được những kết quảban
đầu nhưsau:
Tìm hiểu và trình bày được một sốphương pháp biểu diễn văn bản.
Nghiên cứu vềlý thuyết tập mờvà các phép toán liên quan. Qua đó giới thiệu
được một phương pháp biểu diễn văn bản dựa trên các khái niệm mờ.
Nghiên cứu và tìm hiểu vềbài toán phân lớp, trình bày một sốthuật toán
phân lớp tiêu biểu.
Có được những kết quảthửnghiệm, những so ban đầu khi áp dụng cách biểu
diễn văn bản mới với cách biểu diễn thông thường. Qua đó thấy được một số
ưu điểm:
- Giảm bớt được sốchiều của vector văn bản khi biểu diễn. Giảm bớt
sựphức tạp khi tính toán.
- Cho kết quảtốt hơn khi áp dụng vào bài toán phân lớp với thuật
toán kNN
61 trang |
Chia sẻ: lylyngoc | Lượt xem: 2529 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Biểu diễn văn bản trên lý thuyết tập mờ . Áp dụng trong bài toán 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
số wij tỷ lệ thuận với số lần xuất hiện của từ khĩa
ti trong văn bản dj. Khi số lần xuất hiện từ khĩa ti trong văn bản dj càng lớn thì điều đĩ cĩ
nghĩa là văn bản dj càng phụ thuộc vào từ khĩa ti, hay nĩi cách khác từ khĩa ti mang
nhiều thơng tin trong văn bản dj.
Ví dụ, khi văn bản xuất hiện nhiều từ khĩa máy tính, điều đĩ cĩ nghĩa là văn bản
đang xét chủ yếu liên quan đến lĩnh vực tin học.
Nhưng suy luận trên khơng phải lúc nào cũng đúng. Một ví dụ điển hình là từ
“và” xuất hiện nhiều trong hầu hết các văn bản, nhưng trên thực tế từ này lại khơng mang
nhiều ý nghĩa như tần suất xuất hiện của nĩ. Hoặc cĩ những từ khơng xuất hiện trong văn
bản này nhưng lại xuất hiện trong văn bản khác, khi đĩ ta sẽ khơng tính được giá trị của
log(fij). Một phương pháp khác ra đời khắc phục được nhược điểm của phương pháp TF,
đĩ là phương pháp IDF.
b. Phương pháp dựa trên nghịch đảo tần số văn bản (IDF – Inverse Document
Frequency)
Trong phương pháp này, giá trị wij được tính theo cơng thức sau:
⎪⎩
⎪⎨
⎧ −==
l¹i ng−ỵc nÕu
liƯu tµi trong xuÊt hiƯn khãa tõ nÕu
0
dt)hlog()mlog(
h
mlog
w jiiiij
trong đĩ m là số lượng văn bản và hi là số lượng văn bản mà từ khĩa ti xuất hiện.
Trọng số wij trong cơng thức này được tính dựa trên độ quan trọng của từ khĩa ti
trong văn bản dj. Nếu ti xuất hiện trong càng ít văn bản, điều đĩ cĩ nghĩa là khi nĩ xuất
hiện trong dj thì trọng số của nĩ đối với văn bản dj càng lớn hay nĩ là điểm quan trọng để
phân biệt văn bản dj với các văn bản khác và hàm lượng thơng tin trong nĩ càng lớn.
c. Phương pháp TF × IDF
Phương pháp này là tổng hợp của hai phương pháp TF và IDF, giá trị của ma trận
trọng số được tính như sau:
Khĩa luận tốt nghiệp Nguyễn Việt Cường
19
⎪⎩
⎪⎨
⎧ ≥⎟⎟⎠
⎞
⎜⎜⎝
⎛+=
l¹i ng−ỵc nÕu
f nÕu1
0
1
h
mlog)]flog([
w iji
ij
ij
Đây là phương pháp kết hợp được ưu điểm của cả hai phương pháp trên. Trọng số
wij được tính bằng tần số xuất hiện của từ khĩa ti trong văn bản dj và độ hiếm của từ khĩa
ti trong tồn bộ cơ sở dữ liệu.
Cách tìm kiếm:
Các câu hỏi đưa vào sẽ được ánh xạ vector Q(q1,q2,…,qm) theo hệ số của các từ
vựng trong nĩ là khác nhau. Tức là: Khi từ vựng càng cĩ ý nghĩa với nội dung cần tìm thì
nĩ 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.
qi 0 khi từ vựng đĩ thuộc danh sách các từ cần tìm.
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ĩ cùng
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.
Một số ưu, nhược điểm của phương pháp biểu diễn này:
Ư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.
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.
Nhược điểm
Khĩa luận tốt nghiệp Nguyễn Việt Cường
20
Việc tìm kiếm tiến hành chậm khi hệ thống các từ vựng là lớn do phải tính tốn
trên tồ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 sẽ 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 tố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 hố lại tồ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 đĩ.
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ợp cá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.
2.5. Biểu diễn văn bản trong máy tìm kiếm
2.5.1. Giới thiệu về máy tìm kiếm
Thơng tin trên các trang Web đa dạng về mặt nội dung cũng như hình thức. Tuy
nhiên cùng với sự đa dạng và số lượng lớn thơng tin như vậy đã nảy sinh vấn đề quá tải
thơng tin. Đối với mỗi người dùng chỉ một phần rất nhỏ thơng tin là cĩ ích, chẳng hạn cĩ
người chỉ quan tâm đến trang Thể thao, Văn hĩa mà khơng mấy khi quan tâm đến Kinh
tế. Người ta khơng thể tìm tự kiếm địa chỉ trang Web chứa thơng tin mà mình cần, do vậy
địi hỏi cần phải cĩ một trình tiện ích quản lý nội dung của các trang Web và cho phép tìm
thấy các địa chỉ trang Web cĩ nội dung giống với yêu cầu của người tìm kiếm. Hiện nay
chúng ta đã làm quen với một số các tiện ích như vậy đĩ là: Yahoo, Google, Alvista,...
Máy tìm kiếm là các hệ thống được xây dựng cĩ khả năng tiếp nhận các yêu cầu
tìm kiếm của người dùng (thường là một tập các từ khĩa), sau đĩ phân tích và tìm kiếm
trong cơ sở dữ liệu đã cĩ sẵn và đưa ra các kết quả là các trang web cho người sử dụng.
Cụ thể, người dùng gửi một truy vấn, dạng đơn giản nhất là một danh sách các từ khĩa, và
máy tìm kiếm sẽ làm việc để trả lại một danh sách các trang Web cĩ liên quan hoặc cĩ
chứa các từ khĩa đĩ. Phức tạp hơn, thì truy vấn là cả một văn bản hoặc một đoạn văn bản
hoặc nội dung tĩm tắt của văn bản.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
21
2.5.2. Mơ hình biểu diễn văn bản trong máy tìm kiếm
Như đã được giới thiệu, mơ hình vector là mơ hình biểu diễn phổ biến nhất trong
các CSDL văn bản. Tuy nhiên, cịn cĩ một các biểu diễn khác cũng thường được sử dụng,
đặc biệt trong các máy tìm kiếm, đĩ biểu diễn theo mơ hình index ngược (inverted index).
Với một từ khố trong câu hỏi của người dùng, thơng qua mơ hình index ngược hệ thống
cơ sở dữ liệu văn bản sẽ nhanh chĩng xác định được tập hợp các văn bản chứa từ khĩa đĩ
và các vị trí xuất hiện của từ khĩa đĩ trong các văn bản kết quả.
Ở dạng đơn giản nhất, mơ hình index ngược cĩ dạng như được mơ tả như hình
sau:
Hình 4. Mơ hình index ngược
Trong mơ hình này, tồn tại tập hợp V (được gọi là từ điển) gồm tất cả các từ khĩa
trong hệ thống; các từ khĩa trong V được lưu trữ theo danh sách Inverted Index. Mỗi một
từ khĩa vi trong V liên kết với một con trỏ b(vi) chỉ dẫn tới một cấu trúc dữ liệu, được gọi
là brucket, là một danh sách chứa tất cả các bản ghi mơ tả văn bản chứa từ khĩa vi và vị
trí xuất hiện của từ khĩa vi trong văn bản đĩ (hình 2). Tồn tại một số giải pháp tổ chức từ
điển V hiệu quả nhằm cho phép lưu trữ V ở bộ nhớ trong, chẳng hạn V thường được tổ
chức theo dạng bảng băm để tăng hiệu quả truy cập. Nếu như brucket được lưu ngay
trong bộ nhớ trong thì việc thay đổi chỉnh sửa các brucket được thực hiện rất dễ dàng.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
22
Tuy nhiên, điều này là khơng khả thi do kích thước của chúng thường khá lớn so với kích
thước bộ nhớ trong. Vì vậy, các brucket (cũng như nội dung các văn bản) được lưu trong
đĩa cứng. Để các cơ sở dữ liệu văn bản cĩ khả năng quản lý được một lượng lớn các trang
văn bản thì cần cĩ các thuật tốn chuyên biệt nhằm đảm bảo việc thao tác tới các brucket
trên đĩa cứng được nhanh chĩng.
CSDL văn bản sử dụng mơ hình index ngược cho khả năng tìm ra các trang
văn bản cĩ chứa từ khĩa vi cho trước là khá đơn giản. Đầu tiên, hệ thống truy cập vào
“inverted index” để lấy b(vi) và sau đĩ duyệt danh sách theo các con trỏ của b(vi) để lấy
được các trang văn bản. Trường hợp câu truy vấn cĩ dạng một biểu thức phức tạp cĩ
nhiều từ khĩa được kết nối với nhau theo các phép tốn lơgic như AND, OR, NOT thì
cơng việc tìm kiếm phức tạp hơn. Với câu truy vấn cĩ k từ khĩa, thuật tốn thực hiện việc
lấy các trang văn bản tương ứng với mỗi từ khĩa (dựa trên thuật tốn tìm kiếm theo từ
khĩa nĩi trên) và nhận được k danh sách trang văn bản. Kết quả trả lời câu truy vấn nhận
được bằng cách kết hợp k danh sách này tương ứng với biểu thức lơgic đã cho.
Trong mọi trường hợp, sử dụng biểu diễn index ngược thì tìm kiếm văn bản đáp
ứng câu hỏi thơng qua từ khố sẽ cĩ tốc độ rất nhanh.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
23
Chương 3. BIỂU DIỄN VĂN BẢN SỬ DỤNG CÁC KHÁI
NIỆM MỜ
Trong chương này chúng tơi sẽ trình bày một số khái niệm cơ bản về tập mờ, tiến
hành định nghĩa các khái niệm mờ và một số tính chất của các khái niệm mờ thơng qua
việc tích hợp các từ khĩa và mối quan hệ giữa chúng với nhau. Từ đĩ, sẽ giới thiệu
phương pháp biểu diễn văn bản theo khái niệm mờ.
3.1. Lý thuyết mờ
Cĩ thể nĩi cho đến nay, phần lớn các thành tựu của khoa học của lồi người đều
dựa trên lập luận logic rất chặt chẽ mà nền tảng của các lập luận này là đại số logic Bool.
Trong đại số logic Bool mọi tốn hạng, biểu thức chỉ cĩ giá trị 0 (false) hoặc 1 (true). Tuy
nhiên trên thực tế điều này khơng luơn luơn đúng, nhiều hiện tượng trong tự nhiên và xã
hội khơng thể biểu diễn rõ ràng như vậy. Để cĩ thể phản ánh đúng bản chất của các sự
vật, hiện tượng diễn ra trong thực tế, buộc người ta phải mở rộng đại số Bool để sao cho
các tốn hạng, các biểu thức cĩ thể nhận giá trị khơng chỉ là 0 hoặc 1 mà chúng cĩ thể
nhận giá trị nào đĩ nằm giữa 0 và 1.
Một cách tự nhiên để xây dựng lí thuyết mờ, người ta phải đi từ những khái niệm
nguyên thuỷ nhất. Giống như trong tốn học, một trong những khái niệm nguyên thuỷ của
tốn học là tập hợp, trong lí thuyết mờ người ta đi từ xây dựng tập mờ.
3.1.1. Tập mờ
Trong tốn học truyền thống khái niệm tập hợp được phát biểu như sau:
Cho tập hợp X và A ⊆ X khi đĩ ta cĩ thể xây dựng một hàm, được gọi là hàm đặc
trưng, xác định các phần tử của tập X như sau:
Xét µ : X → {0,1 } với x ∈ X thì:
µ (x) = 1 nếu x ∈ A;
µ (x) = 0 nếu x ∉ A;
Hàm đặc trưng µ(x) rõ ràng là hàm xác định các phần tử của tập A. Nhờ hàm µ(x)
ta cĩ thể nĩi tập A là tập gồm những phần tử x mà µ (x)=1. Bây giờ tập A cĩ thể biểu diễn
một cách khác qua các phần tử của tập X:
Khĩa luận tốt nghiệp Nguyễn Việt Cường
24
A={(x, µ(x)=1)| x ∈ X}
Mở rộng khái niệm tập hợp của tốn học học cổ điển nêu trên, Lofti Zadeh xét
hàm µ trên tồn đoạn [0,1].
Định nghĩa 3.1: Tập mờ
Cho X là một tập hợp. A được gọi là một tập mờ trong X nếu: A = {(x, µA(x))|
x∈X} trong đĩ µA(x) là hàm xác định trên đoạn [0,1], µA: X → [0,1]. Hàm µA được gọi là
hàm thuộc của A cịn µA(x) là một giá trị trong đoạn [0,1] được gọi là mức độ thuộc của x
trong A.
Biểu diễn tập mờ
Khi X là tập các điểm rời rạc x1, x2, …xn thì tập mờ A cĩ thể biểu diễn bằng cách
liệt kê A = {(x1, µ A(x1)), (x2, µ A(x2)),...... (xn , µ A(xn))}
Hoặc được ký hiệu là:
A = µ A(x1)/ x1 + µ A(x2)/ x2 + … + µ A(xn)/ xn
Trường hợp X liên tục thì A được kí hiệu là:
A = ∫ ∈ µXx A x/)x(
Ví dụ:
Cho X là tập các điểm tổng kết trung bình các mơn học của sinh viên. Qua thống
kê người ta thấy rằng :
0% số người coi một sinh viên là giỏi khi điểm tổng kết đạt dưới 7.0
5% số người coi một sinh viên là giỏi khi điểm tổng kết đạt điểm từ 7.0 đến 7.5
10% số người coi một sinh viên là giỏi khi điểm tổng kết đạt đến 8.0;
20% số người coi một sinh viên là giỏi khi điểm tổng kết đạt đến 8.5;
80% số người coi một sinh viên là giỏi chỉ khi điểm tổng kết đạt từ 9 đến 9,5 .
100% số người coi một sinh viên là giỏi khi điểm tổng kết đạt đến điểm 10
Bây giờ cần biểu diễn tập các điểm trên X, được ký hiệu là tập A, để mơ tả một
"sinh viên giỏi". Với kết quả thống kê như trên, khơng thể dùng khái niệm tập hợp theo
Khĩa luận tốt nghiệp Nguyễn Việt Cường
25
quan niệm truyền thống để biểu diễn tập A. Trong trường hợp này, khái niệm tập mờ là
rất hữu dụng và A chính là một tập mờ. Nếu xét X chỉ gồm các đại lượng hữu hạn, X =
{7, 7.5, 8.0, 8.5, 9.0, 9.5, 10.0}, thì tập mờ A được biểu diễn như sau:
A={ (7, 0.05),(7.5,0.05),(8.0,0.1), (8.5, 0.2), (9.0,0.8) (9.5,0.8),(10,1.0 ) }
Hoặc:
A= 0.05/7 + 0.05/7.5 + 0,0.1/8 + 0.2/8.5 + 0,0.8/9 + 0.8/9.5 + 1.0/10
Nếu xét X là một khoảng liên tục X = [7.0, 10] thì ta cĩ thể biểu diễn đồ thị hàm
thuộc của A như sau:
Hình 5: Đồ thị hàm phụ thuộc tập mờ A
3.1.2. Các phép tốn trên tập mờ
Giao của hai tập mờ.
Cho X là tập hợp, A, B là hai tập mờ trong X và cĩ các hàm thuộc lần luợt là µA,
µB. Giao của hai tập mờ A và B, ký hiệu A∩B, là một tập mờ cĩ hàm thuộc µA∩B xác định
như sau:
µA∩B(x) = min(µA(x), µB(x)) ∀x∈X
Hợp của hai tập mờ.
Cho X là tập hợp, A, B là hai tập mờ trong X và cĩ các hàm thuộc lần luợt là µA,
µB. Hợp của hai tập mờ A và B trong X, ký hiệu A∪B, là một tập mờ cĩ hàm thuộc µA∪B
xác định như sau:
µA∪B(x) ) = max(µA(x), µB(x)) ∀x∈X
Khĩa luận tốt nghiệp Nguyễn Việt Cường
26
Tích đại số của hai tập mờ.
Cho X là tập hợp, A, B là hai tập mờ trong X và cĩ các hàm thuộc lần lượt là
µA(x), µB(x). Tích đại số của hai tập mờ A và B trong X, ký hiệu A.B là một tập mờ cĩ
hàm thuộc được xác định như sau:
µA.B(x) = µA(x).µB(x) ∀x∈X
Tổng đại số của hai tập mờ.
Cho X là tập hợp, A, B là hai tập mờ trong X và cĩ các hàm thuộc lần lượt là µA,
µB. Tổng đại số của hai tập mờ A và B trong X, ký hiệu A+B là một tập mờ cĩ hàm thuộc
được xác định như sau:
µA+B(x) = µA(x) + µB(x) - µA(x).µB(x) ∀x∈X.
Phần bù của một tập mờ.
Cho A là tập mờ trong X cĩ hàm thuộc µA. Phần bù A của A trong X là một tập
mờ cĩ hàm thuộc xác định như sau:
)x(
A
µ = 1 - µA(x) ∀x∈X.
Tổng rời của hai tập mờ.
Cho X là tập hợp, A và B là hai tập mờ trong X. Tổng rời của hai tập mờ A và B
trong X, ký hiệu A⊕B định nghĩa như sau:
A⊕B = ( A∩B) ∪ (A∩B )
Phép trừ hai tập mờ.
Cho X là tập hợp, A, B là hai tập mờ trong X và cĩ các hàm thuộc lần lượt là µA,
µB. Phép trừ của hai tập mờ A và B trong X ký hiệu A\B được định nghĩa như sau:
A\B = A∩B .
Cho X là tập hợp, A và B là hai tập mờ trong X, cĩ các hàm thuộc lần lượt là µA,
µB. A gọi là nằm trong B, ký hiệu A⊂B nếu hàm thuộc thỏa mãn:
µA(x) ≤ µB(x) ∀x∈X.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
27
Cho X là tập hợp, A và B là hai tập mờ trong X, cĩ các hàm thuộc lần lượt là µA,
µB . A gọi là bằng B, ký hiệu A=B nếu và chỉ nếu:
µA(x) = µB(x) ∀x∈X
Tập hợp mức α của tập mờ.
Cho α ∈[0,1], X là tập hợp, A là một tập mờ trong X cĩ hàm thuộc µA. Tập hợp
Aα thoả mãn Aα={x∈X | µA(x) ≥ α} gọi là tập hợp mức α của tập mờ A.
Khoảng cách Euclid trên tập mờ
X là tập hợp cĩ hữu hạn n phần tử, A và B là hai tập mờ trên X. Khoảng cách
Euclid (trong khơng gian n chiều) trên tập mờ được tính như sau:
e(A,B) = ∑
=
µ−µn
1i
2
iBiA ))x()x((
Khoảng cách e2(A,B) được gọi là một chuẩn Euclid.
3.1.3. Quan hệ mờ
Định nghĩa 3.2: Quan hệ mờ trên tích Đề-các
Cho X,Y là hai tập và x∈X, y∈Y. Ký hiệu (x,y) là cặp thứ tự nằm trong tích Đề-
các XxY. Tập mờ R = {(x,y), µR(x,y)|(x,y) ∈ XxY} được gọi là một quan hệ mờ trên
X×Y với hàm thuộc: µR(x,y): X×Y → [0,1]
Nếu R là một tập mờ trong X = X1×X2×….×Xn thì R được gọi là một quan hệ mờ
n ngơi.
Định nghĩa 3.3: Quan hệ mờ trên tập mờ
Cho X,Y là hai tập mờ và x∈X, y∈Y. Ký hiệu (x,y) là cặp thứ tự nằm trong tích
Đề-các X×Y. R = {(x,y), µR(x,y)|(x,y) ∈ X×Y} được gọi là một quan hệ mờ trên tập mờ
A, B nếu: µR(x,y) ≤µA(x,y), ∀X×Y và µR(x,y) ≤µB(x,y) ∀X×Y
3.1.4. Các phép tốn trên quan hệ mờ
Ngồi một số phép tốn giống như trên tập mờ trong tích Đề-các: Phép hợp, giao,
tổng đại số, tích đại số…, người ta cịn đưa ra thêm một số phép tốn khác trong quan hệ
mờ như sau:
Khĩa luận tốt nghiệp Nguyễn Việt Cường
28
Phép hợp thành max-min
Giả sử R1 là quan hệ mờ trong X×Y, R2 là quan hệ mờ trong Y×Z. Phép hợp
thành max-min của hai quan hệ mờ R1, R2 (kí hiệu R1 o R2) là một quan hệ mờ trong X×Z
thoả mãn:
µ R1oR2(x,z) = maxy(min(µR1(x,y), µR2(y,z))) ∀x∈X, ∀y∈Y, ∀z∈Z
Phép hợp thành max-tích
Giả sử R1 là quan hệ mờ trong X×Y, R2 là quan hệ mờ trong Y×Z. Phép hợp
thành max-tích của hai quan hệ mờ R1, R2 (kí hiệu R1.R2) là một quan hệ mờ trong X×Z
thoả mãn:
µ R1.R2(x,z) = maxy(µR1(x,y). µR2(y,z)) ∀x∈X, ∀y∈Y, ∀z∈Z
Phép hợp thành max-trung bình
Giả sử R1 là quan hệ mờ trong X×Y, R2 là quan hệ mờ trong Y×Z. Phép hợp
thành max-trung bình của hai quan hệ mờ R1, R2 (R1avR2) là quan hệ mờ trong X×Z thoả
mãn:
µ R1avR2(x,z) = maxy((µR1(x,y)+µR2(y,z))/2) ∀x∈X, ∀y∈Y, ∀z∈Z
Phép hợp thành max-*.(max-* composition) (* là tốn tử hai ngơi bất kỳ)
Giả sử R1 là quan hệ mờ trong X×Y, R2 là quan hệ mờ trong Y×Z. Phép hợp
thành max-* của hai quan hệ mờ R1, R2 (R1* R2) là một quan hệ mờ trong X×Z thoả mãn:
µR1*R2(x,z) = max(µR1(x,y)*µR2(y,z)) ∀x∈X, ∀y∈Y, ∀z∈Z
Hàm tích hợp mờ
Khi cĩ một tập các tập mờ và tích hợp các hàm thuộc của chúng lại, ta sẽ thu
được một tập mờ là một hàm tích hợp mờ.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
29
Một hàm tích hợp mờ được định nghĩa là một tốn tử n ngơi như sau:
F: [0,1]n → [0,1] thỏa mãn điều kiện:
Nếu 0, 1 là hai điểm cực trị thì: F(0,…,0) = 0 và F(1,…,1)=1 và ∀a trong [0,1]
thì: F(a,…,a)=a
Nếu ai’ > ai thì: F(a1,…,ai’,…,an) ≥ F(a1,…,ai,…,an) (tính đơn điệu tăng của hàm
tích hợp mờ)
Một số hàm tích hợp mờ:
1. Hàm trung bình tổng quát:
2. Hàm trung bình số học:
3. Hàm trung bình hình học:
4. Hàm min:
5. Hàm max:
3.2. Biểu diễn văn bản sử dụng các khái niệm mờ
Cách biểu diễn văn bản thơng thường là sử dụng mơ hình khơng gian vector,
trong đĩ văn bản được biểu diễn bằng một vector và mỗi thành phần của vector là một từ
khĩa. Ở chương II, khĩa luận đã nêu ra một số nhược điểm của phương pháp này: gây tốn
kém, phức tạp trong việc lưu trữ, chiều của mỗi vector là rất lớn khi văn bản cĩ nhiều từ
khĩa … Trong phần này, chúng tơi xin trình bày một phương pháp biểu diễn văn bản mà
phần nào khắc phục được nhược điểm nêu trên, đĩ là phương pháp biểu diễn văn bản sử
dụng các khái niệm mờ.
0pR,p,)(x
n
1
)x,...,F(x p
n
1i
p
1n1 ≠∈= ∑
=
)0( →= pn
1
n21n1 )...x.x(x)x,...,F(x
)(min −∞→= p)x,...,x,(x)x,...,F(x n21n1
)(max +∞→= p)x,...,x,(x)x,...,F(x n21n1
∑
=
==
n
1i
1n1 )(xn
1
)x,...,F(x )1( p
Khĩa luận tốt nghiệp Nguyễn Việt Cường
30
3.2.1. Khái niệm mờ
Cĩ một tập gồm m văn bản: D=(d1, d2, …dm).
Khí đĩ xác định được một tập p từ khĩa: K = (k1, k2, … kp)
Một khái niệm cĩ thể là một từ khĩa theo nghĩa thơng thường, trong đĩ gồm các từ cĩ liên
quan đến từ khĩa đĩ. Ví dụ với khái niệm là “bệnh viện”, nĩ cĩ thể bao gồm 1 số từ khĩa:
“bác sĩ”, “y tá”, “bệnh nhân”, “ống nghe”, “thuốc”
Gọi C là tập gồm cĩ n khái niệm liên quan đến văn bản, C được kí hiệu như sau:
C = {c1, c2, …cn}
Trong đĩ: ci là khái niệm do người dùng xác định. Giả sử một khái niệm ci sẽ bao
gồm các từ khĩa cĩ liên quan, ci = {k1, k2, …kp}, trong đĩ ki là các từ khĩa trong tập từ
điển và cĩ liên quan đến khái niệm ci. Trong ví dụ trên chúng ta cĩ “bệnh viện” = {“bác
sĩ”, “y tá”, “bệnh nhân”, “ống nghe”, “thuốc”}.
Định nghĩa 3.3: Khái niệm mờ
Một tập mờ tương ứng với khái niệm trong đĩ hàm thuộc của nĩ được xác định
bằng độ quan trọng của các từ khĩa cĩ liên quan tới khái niệm đĩ được gọi là một khái
niệm mờ, kí hiệu c* . Ta cĩ thể biểu diễn khái niệm mờ qua tập từ khĩa như sau:
))}k(,k)),...(k(,k()),k(,k{(c pcp2c21c1
* µµµ=
Trong đĩ:
Từ khái niệm mờ, ta cĩ định nghĩa sau:
Định nghĩa 3.4: Hàm tích hợp khái niệm mờ:
Một hàm tích hợp khái niệm mờ là hàm tích hợp các hàm thuộc của các khái niệm
mờ. Hàm tích hợp này được kí hiệu F: [0,1]p → [0,1], thỏa mãn các tính chất của hàm tích
hợp mờ:
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=
c niƯm kh¸ithuéc i k nÕu)i(kc
c vµotoµn hoµnthuéc i k nÕu1
c thuéc kh«ng i k nÕu0
)
i
(k
c
µ
µ
Khĩa luận tốt nghiệp Nguyễn Việt Cường
31
1.
2.
Trong đĩ, µc(ki) biểu diễn mức độ quan trọng của các từ khĩa trong văn bản.
Ví dụ:
Giả sử ta cĩ tập từ khĩa: ‘bệnh viện’, ‘trường học’, ‘thuốc’, ‘xe máy’, ‘y tá’,
‘bệnh nhân’, ‘ống nghe’, ‘sinh viên’, ‘hoa hồng’, ‘điện thoại’, ‘bác sỹ’.
K = {‘bệnh viện’, ‘bác sỹ’, ‘trường học’, ‘thuốc’, ‘xe máy’, ‘y tá’, ‘bệnh nhân’,
‘ống nghe’, ‘sinh viên’, ‘hoa hồng’, ‘điện thoại’, ‘bác sỹ’} với độ liên quan đến văn bản
được xác định bằng một hàm đánh chỉ số tương ứng:
µK = {µ(‘bệnh viện’), µ(‘bác sỹ’), µ(‘trường học’), µ(‘thuốc’), µ(‘xe máy’), µ(‘y
tá’), µ(‘bệnh nhân’), µ(‘ống nghe’), µ(‘sinh viên’), µ(‘hoa hồng’), µ(‘điện thoại’), µ(‘bác
sỹ’)}
= {0.8, 0.7, 0.1, 0.4, 0.0, 0.3, 0.6, 0.3, 0.0, 0.1, 0.0, 0.2}
Ta tìm được một cụm từ khĩa cĩ liên quan đến nhau trong trong văn bản: {‘bệnh
viện’, ‘bác sỹ’, ‘thuốc’, ‘bệnh nhân’, ‘ống nghe’}
Chọn từ khĩa ‘bệnh viên’ làm khái niệm, thì khái niệm mờ c* = ‘bệnh viện’ được
biểu diễn như sau:
‘bệnh viện’ = {(‘bác sỹ’, 0.7), (‘thuốc’, 0.4), (‘bệnh nhân’, 0.6), (‘ống nghe’,
0.3)}
Khi đĩ, độ quan trọng trong văn bản của ‘bệnh viện’ được xác định bởi hàm tích
hợp khái niệm mờ:
µ(‘bệnh viện’) = F(µ (‘bác sỹ’), µ(‘thuốc’), µ(‘bệnh nhân’), µ(‘ống nghe’))
Nếu hàm tích hợp là hàm MAX thì:
µ(‘bệnh viện’) = MAX(0.7, 0.4, 0.6, 0.3) = 0.6
Nếu hàm tích hợp là hàm trung bình thì:
µ(‘bệnh viện’) = AVEG(0.7, 0.4, 0.6, 0.3) = 0.55
p1,...,i ),(k)(k víi
))(k),...,(k),...,(kF())(k),...,(k),...,(kF(
ic
'
ic
pcic1cpc
'
ic1c
=>
≥
µµ
µµµµµµ
[0,1]))(k),...,(kF( pc1c ∈µµ
Khĩa luận tốt nghiệp Nguyễn Việt Cường
32
3.2.2. Biểu diễn văn bản
Với cách định nghĩa khái niệm mờ như trên, ta cĩ thể biểu diễn văn bản bằng
cách xem nĩ như một vector cĩ các thành phần là các khái niệm mờ thay vì một vector
với các thành phần là các từ khĩa.
Khi đĩ, một văn bản d sẽ được biểu diễn dưới dạng sau:
d = µ(c1*)/ c1* + µ(c2*)/c2* + … + µ(cn*)/(cn*)
Trong đĩ µ(ci*) là là mức độ quan trọng của khái niệm mờ c*i của văn bản. µ(ci*)
được xác định bằng hàm tích hợp mờ của tập các từ khĩa liên quan đến khái niệm ci*.
Chú ý rằng trong phương pháp biểu diễn này, một từ khĩa cũng cĩ thể coi như là
một khái niệm mờ khi đồng nhất từ khĩa với khái niệm mờ.
Nếu trong các khái niệm, khái niệm nào cĩ các từ khĩa liên quan đến văn bản lớn
hơn thì trọng số của nĩ sẽ lớn hơn, và như vậy ngữ nghĩa của nĩ cũng sẽ rõ ràng hơn.
Một vấn đề đặt ra là tìm tập các từ khĩa biểu diễn cho một khái niệm mờ, các từ
khĩa này phải liên quan đến nhau và cĩ nghĩa tương tự nhau. Việc phát triển một thuật
tốn như vậy hiện nay cịn là một vấn đề. Thơng thường cĩ hai cách chính như sau:
1. Xác định tập các khái niệm bằng tri thức con người: Người dùng tự xác định các
từ khĩa cĩ liên quan theo cảm nhận của mỗi người, hoặc chọn các từ khĩa đại diện
cho văn bản đĩ. Việc này tuy đưa lại kết quả chính xác khá cao (Đã được thực
hiện trong các hệ lớn như Yahoo!) tuy nhiên rất mất nhiều thời gian và cơng sức.
2. Phát triển các thuật tốn tự động: Sử dụng các kỹ thuật của ngành xử lý ngơn ngữ
tự nhiên để xác định các từ khĩa cĩ liên quan với nhau. Các thuật tốn như vậy
hiện cũng đang là một chủ đề nĩng trong các bài tốn xử lý ngơn ngữ tự nhiên.
Mục đích trong nghiên cứu này là chúng tơi muốn thử nghiệm việc biểu diễn xử
dụng các khái niệm mờ trong bài tốn phân lớp văn bản. Các khái niệm mờ được xác định
trước dựa trên tập chủ đề đã được xác định trước. Chi tiết các khái niệm mờ áp dụng được
mơ tả trong phần thực nghiệm.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
33
3.2.3. Đề xuất giải pháp cho vấn đề đồng nghĩa
Trong văn bản, thường xuất hiện một số từ đồng nghĩa (hoặc cĩ nghĩa gần nhau).
Sự xuất hiện này sẽ làm cho việc biểu diễn văn bản khĩ khăn hơn vì khơng giảm được số
chiều của vector biểu diễn.
Khĩa luận này xin đề xuất một phương pháp tìm ra và xử lý các từ đồng nghĩa
trong văn bản như sau:
Tìm ra từ đồng nghĩa
Chúng tơi sử dụng sự hỗ trợ của từ điển Wordnet. Wordnet là Từ điển ngơn ngữ
học cho tiếng Anh, được giới thiệu vào năm 1985 tại phịng thí nghiệm khoa học của
trường đại học Princeton.
Wordnet sẽ cung cấp:
Nhĩm các từ tiếng Anh thành một tập những từ đồng nghĩa gọi là synsets
Cung cấp những định nghĩa ngắn, tổng quát và ghi lại nhiều quan hệ ngữ
nghĩa học giữa những tập từ đồng nghĩa này.
Phân biệt động từ, danh từ, tính từ bởi chúng đi theo những quy tắc văn phạm
khác nhau.
Mục đích: Tạo ra sự kết hợp giữa từ điển và danh sách các từ đồng nghĩa, hỗ trợ
việc phân tích văn bản và ứng dụng trong AI.
Ví dụ:
Computer: a machine for performing calculations automatically.
syn: data processor, electronic computer, information processing system.
Từ một từ khĩa trong tập các từ khĩa, kết hợp với từ điển wordnet, ta tìm ra
những từ đồng nghĩa với từ khĩa đĩ. Tìm giao của 2 tập: Tập từ khĩa và tập từ đồng
nghĩa, chúng ta sẽ tìm ra được một nhĩm các từ đồng nghĩa trong tập từ khĩa đã cĩ.
Xử lý từ đồng nghĩa:
Với tập từ đồng nghĩa xuất hiện trong văn bản mà ta vừa tìm được, bằng cách sử
Khĩa luận tốt nghiệp Nguyễn Việt Cường
34
dụng hàm tích hợp mờ, ta tích hợp chúng lại trong một khái niệm chung. Việc xử lý văn
bản thay vì việc tính tốn trên các từ khĩa, sẽ tính tốn trên một khái niệm này. Làm như
vậy, ta sẽ giảm bớt được số chiều của vector biểu diễn, giảm sự phức tạp trong tính tốn
và tránh gây nên sự khĩ hiểu cho người sử dụng khi bắt gặp các từ đồng nghĩa trong văn
bản.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
35
Chương 4. CÁC PHƯƠNG PHÁP PHÂN LỚP VĂN BẢN
Trong chương này, chúng tơi trình bày về bài tốn phân lớp văn bản và các thuật
tốn áp dụng vào bài tốn đĩ.
4.1. Tổng quan về bài tốn phân lớp
Phân lớp văn bản tự động là một lĩnh vực được chú ý nhất trong những năm gần
đây. Để phân lớp người ta sử dụng nhiều cách tiếp cận khác nhau như dựa trên từ khĩa,
dựa trên ngữ nghĩa các từ cĩ tần số xuất hiện cao, mơ hình Maximum Entropy, tập thơ,
tập mờ … Một số lượng lớn các phương pháp phân lớp đã được áp dụng thành cơng trên
ngơn ngữ này : mơ hình hồi quy , phân lớp dựa trên láng giềng gần nhất (k-nearest
neighbors), phương pháp dựa trên xác suất Nạve Bayes, cây quyết định, học luật quy nạp,
mạng nơron (neural network), học trực tuyến, và máy vector hỗ trợ (SVM-support vector
machine)
Bài tốn: Cho một tập hợp các văn bản đã được người dùng phân lớp bằng tay
vào một số chủ đề cĩ sẵn. Khi đưa vào một văn bản mới, yêu cầu hệ thống chỉ ra tên chủ
đề phù hợp nhất với văn bản đĩ.
Theo cách truyền thống, việc phân lớp văn bản cĩ thể thực hiện một cách thủ
cơng, tức là đọc từng văn bản một và gán nĩ vào nhĩm phù hợp. Cách thức này sẽ tốn
nhiều thời gian và chi phí nếu như số lượng văn bản lớn. Do vậy, cần phải xây dựng các
cơng cụ phân lớp văn bản một cách tự động.
Để xây dựng cơng cụ phận loại văn bản tự động người ta thường dùng các thuật
tốn học máy (machine learning). Tuy nhiên, cịn cĩ các thuật tốn đặc biệt hơn dùng
cho phân lớp trong các lĩnh vực đặc thù. Một ví dụ điển hình là bài tốn phân lớp cơng
văn giấy tờ. Hệ thống sẽ tìm ra đặc thù của văn bản một cách tương đối máy mĩc, cụ thể
là khi tìm thấy ở lề trên bên trái cĩ ký hiệu “NĐ” thì hệ thống sẽ phân văn bản đĩ vào
nhĩm “Nghị định”, tương tự như vậy với các ký hiệu “CV”, “QĐ” thì hệ thống sẽ phân
văn bản này vào nhĩm “Cơng văn”, và “Quyết định”. Thuật tốn này tương đối hiệu quả
song lại chỉ phù hợp cho các nhĩm dữ liệu tương đối đặc thù. Khi phải làm việc với các
Khĩa luận tốt nghiệp Nguyễn Việt Cường
36
văn bản ít đặc thù hơn thì cần phải xây dựng các thuật tốn phân lớp dựa trên nội dung
của văn bản và so sánh độ phù hợp của chúng với các văn bản đã được phân lớp bởi con
người. Đây là tư tưởng chính của thuật tốn học máy. Trong mơ hình này, các văn bản đã
được phân lớp sẵn và hệ thống của chúng ta phải tìm cách để tách ra đặc thù của các văn
bản thuộc mỗi nhĩm riêng biệt. Tập văn bản mẫu dùng để huấn luyện gọi là tập huấn
luyện (train set) hay tập mẫu (pattern set), quá trình phân lớp văn bản bằng tay gọi là quá
trình huấn luyện (training), cịn quá trình máy tự tìm đặc thù của các nhĩm gọi là quá
trình học (learning). Sau khi máy đã học xong, người dùng sẽ đưa các văn bản mới vào
và nhiệm vụ của máy là tìm ra xem văn bản đĩ phù hợp nhất với nhĩm nào mà con người
đã huấn luyện nĩ.
Trong phân lớp văn bản, sự phụ thuộc của một văn bản vào một nhĩm cĩ thể là
các giá trị rời rạc đúng và sai (true hoặc false), để hiểu rằng văn bản đĩ thuộc hay khơng
thuộc một nhĩm nào đĩ) hoặc các giá trị liên tục (một số thực, chỉ ra độ phù hợp của văn
bản với một nhĩm nào đĩ). Khi câu trả lời đưa ra bắt buộc phải là đúng hoặc sai thì giá trị
liên tục cĩ thể được rời rạc hĩa bằng cách đặt ngưỡng. Ngưỡng đặt ra tùy thuộc vào thuật
tốn và yêu cầu người dùng.
4.2. Các thuật tốn phân lớp
Cĩ rất nhiều thuật tốn khác nhau để giải quyết bài tốn phân lớp văn bản, trong
chương này chúng tơi xin trình bày một số thuật tốn sau:
4.2.1. Phân lớp dựa trên thuật tốn Naive Bayes
Naive Bayes là một trong những phương pháp phân lớp dựa vào xác suất điển
hình nhất trong khai thác dữ liệu và tri thức
Cách tiếp cận này sử dụng xác suất cĩ điều kiện giữa từ và chủ đề để dự đốn xác
suất chủ đề của một văn bản cần phân lớp. Đồng thời, giả định rằng sự xuất hiện của tất
cả các từ trong văn bản đều độc lập với nhau. Như thế, nĩ sẽ khơng sử dụng việc kết hợp
các từ để đưa ra phán đốn chủ đề như một số phương pháp khác, điều này sẽ làm cho
việc tính tốn Naive Bayes hiệu quả và nhanh chĩng hơn.
Cơng thức
Khĩa luận tốt nghiệp Nguyễn Việt Cường
37
Mục đích chính là tính được xác suất Pr(Cj, d′) , xác suất để văn bản d′ nằm trong
lớp Cj . Theo Bayes, văn bản d′ sẽ được gán vào lớp Cj nào cĩ xác suất Pr(Cj, d)′ cao nhất.
Cơng thức sau dùng để tính Pr(Cj, d′):
Trong đĩ:
- TF(wi,,d′) là số lần xuất hiện của từ wi trong văn bản d′
- |d′| là số lượng các từ trong văn bản d′
- wi là một từ trong khơng gian đặc trưng F với số chiều là |F|
- Pr(Cj): là tỷ lệ phần trăm của số văn bản mỗi lớp tương ứng trong tập dữ liệu
luyện:
Pr(wi|Cj) sử dụng phép ước lượng Laplace:
Naive Bayes là một phương pháp rất hiệu quả trong một số trường hợp. Nếu tập
dữ liệu huấn luyện nghèo nàn và các tham số dự đốn (như khơng gian đặc trưng) cĩ chất
lượng kém thì sẽ dẫn đến kết quả tồi. Tuy nhiên, nĩ được đánh giá là một thuật tốn phân
lớp tuyến tính thích hợp trong phân lớp văn bản nhiều chủ đề với một số ưu điểm: cài đặt
đơn giản, tốc độ nhanh, dễ dàng cập nhật dữ liệu huấn luyện mới và cĩ tính độc lập cao
Khĩa luận tốt nghiệp Nguyễn Việt Cường
38
với tập huấn luyện, cĩ thể sử dụng kết hợp nhiều tập huấn luyện khác nhau. Thơng
thường, người ta cịn đặt thêm một ngưỡng tối ưu để cho kết quả phân lớp khả quan.
4.2.2. Phân lớp dựa trên thuật tốn K - Nearest Neighbor (KNN)
Thuật tốn phân lớp KNN [4] là một phương pháp truyền thống và khá nổi tiếng
trong hướng tiếp cận dựa trên thống kê, đã được nghiên cứu trong nhận dạng mẫu trong
vài thập kỷ gần đây.
Nĩ được đánh giá là một trong những phương pháp tốt nhất và được sử dụng
ngay từ những thời kỳ đầu của phân lớp văn bản .
Muốn phân lớp một văn bản mới, thuật tốn KNN sẽ tính khoảng cách (Euclide,
Cosine …) của văn bản này đến các văn bản trong tập huấn luyện và chọn ra k văn bản cĩ
khoảng cách gần nhất, cịn gọi là k “láng giềng”. Dùng các khoảng cách vừa tính được
đánh trọng số cho các chủ đề đã cĩ. Trọng số của một chủ đề sẽ được tính bằng tổng các
khoảng cánh từ văn bản cần phân lớp đến các văn bản trong k láng giềng mà cĩ cùng chủ
đề đĩ. Những chủ đề khơng xuất hiện trong tập k văn bản sẽ cĩ trọng số bằng 0. Các chủ
đề được sắp xếp theo độ giảm dần của các trọng số và chủ đề nào cĩ trọng số cao sẽ là
chủ đề cho văn bản cần phân lớp.
Cơng thức
Trọng số của chủ đề cj đối văn bản x :
W( x ,cj) = ∑
∈
−
KNNd
jjii
i
b)c,d(y).d,x(sim
Trong đĩ:
- )c,d(y ji ∈ {0,1} với:
y = 0: văn bản id khơng phụ thuộc chủ đề cj
y = 1: văn bản id thuộc về chủ đề cj
- )d,xsim( i độ giống nhau giữa văn bản cần phân loại x và văn bản id . Sử
dụng độ đo cosin để tính )d,xsim( i :
Khĩa luận tốt nghiệp Nguyễn Việt Cường
39
)d,xsim( i = )d,x(cos i =
i
i
d.x
d.x
- bj là ngưỡng phân loại của chủ đề cj , được tự động học sử dụng một tập văn
bản hợp lệ chọn ra từ tập huấn luyện
Khi số văn bản trong tập văn bản láng giềng càng lớn thì thuật tốn càng ổn định
và sai sĩt thấp.
4.2.3. Phân lớp dựa vào thuật tốn cây quyết định
Cây quyết định (Decision Tree) là một trong các phương pháp được sử dụng rộng
rãi trong học quy nạp từ tập dữ liệu lớn. Đây là phương pháp học xấp xỉ các hàm mục
tiêu cĩ giá trị rời rạc. Một ưu điểm của phương pháp cây quyết định là cĩ thể chuyển dễ
dàng sang dạng cơ sở tri thức là các luật Nếu - Thì (If - Then).
Trên cây gồm các nút trong được gán nhãn bởi các khái niệm, các nhánh cây chứa
nút được gán nhãn bằng các trọng số của khái niệm tương ứng đối với tài liệu mẫu và các
lá trên cây được gán nhãn bởi các nhãn nhĩm. Một hệ thống như vậy sẽ phân loại một tài
liệu di bởi phép thử đệ quy các trọng số mà các khái niệm được gán nhãn cho các nút
trong với vector id cho đến khi với tới một nút lá, khi đĩ nhãn của nút này được gán cho
tài liệu di. Đa số các phương pháp phân loại như vậy sử dụng biểu diễn ở dạng nhị phân
và các cây cũng được biểu diễn dưới dạng nhị phân.
Ví dụ cây quyết định:
Hình 7. Cây quyết định
Khĩa luận tốt nghiệp Nguyễn Việt Cường
40
Entropy
Entropy là đại lượng đo độ đồng nhất thơng tin hay tính thuần nhất của các mẫu.
Đây là đại lượng hết sức quan trọng trong lý thuyết thơng tin.
Đại lượng Entropy được tính như sau:
∑
=
−≡
n
i
ii ppS
1
)Entropy( 2log
trong đĩ pi là phân bố của thuộc tính thứ i trong S.
Information Gain
Information Gain là đại lượng đo độ ảnh hưởng của một thuộc tính trong mẫu đĩ
trong việc phân lớp.
Information Gain của một thuộc tính A trong tập S, ký hiệu là )Gain(S, A được
xác định như sau:
∑
∈
−≡
)Values(
)Entropy()Entropy(),Gain(
Av
v
v S
S
S
SAS
trong đĩ Values(A) là tập các giá trị cĩ thể của thuộc tính A, cịn Sv là tập con cĩ
thể của tập S các phần tử cĩ thuộc tính A = v, tức là })(|{ vsASsSv =∈= .
Biểu thức đầu Entropy (S) là đại lượng entropy nguyên thủy của tập S, biểu thức
sau là giá trị kỳ vọng của entropy sau khi S được chia thành các tập con theo các giá trị
của thuộc tính A. Do đĩ Gain(S,A) thực chất là độ giảm kì vọng của entropy khi biết các
giá trị thuộc tính A. Giá trị Gain(S,A) là số bit cần lưu khi mã hĩa các giá trị mục tiêu của
một thành phần của S, khi biết các giá trị của thuộc tính A.
Thuật tốn ID3
ID3 và cải tiến của nĩ, C4.5, là các thuật tốn học cây quyết định phổ biến nhất.
Nhìn chung, thuật các bước trong thuật tốn ID3 cĩ thể được phát biểu một cách
ngắn gọn như sau:
- Xác định thuộc tính cĩ độ đo Information Gain cao nhất trong tập mẫu
Khĩa luận tốt nghiệp Nguyễn Việt Cường
41
- Sử dụng thuộc tính này làm gốc của cây, tạo một nhánh cây tương ứng với mỗi
giá trị cĩ thể của thuộc tính.
- Ứng với mỗi nhánh, ta lại lặp lại quá trình trên tương ứng với tập con của tập
mẫu (training set) được phân cho nhánh này.
4.2.4. Phân lớp sử dụng Support Vector Machines (SVM)
Máy sử dụng vector hỗ trợ (SVM)[12] được Cortess và Vapnik giới thiệu năm
1995, là phương pháp tiếp cận phân lớp hiệu quả để giải quyết vấn đề nhận dạng mẫu 2
lớp sử dụng nguyên lý Cực tiểu hĩa Rủi ro cĩ Cấu trúc (Structural Risk Minimization).
Trong khơng gian vector cho trước một tập huấn luyện được biểu diễn trong đĩ
mỗi tài liệu là một điểm, thuật tốn SVM sẽ tìm ra một siêu mặt phẳng h quyết định tốt
nhất cĩ thể chia các điểm trên khơng gian này thành hai lớp riêng biệt tương ứng lớp + và
lớp –. Chất lượng của siêu mặt phẳng phân cách này được quyết định bởi khoảng cách
(gọi là biên) của điểm dữ liệu gần nhất của mỗi lớp đến mặt phẳng này. Khoảng cách biên
càng lớn thì mặt phẳng quyết định càng tốt và việc phân lớp càng chính xác. Mục đích
thuật tốn SVM là tìm được khoảng cách biên lớn nhất. Hình sau minh họa cho thuật tốn
này:
Hình 8: Siêu mặt phẳng h phân chia dữ liệu huấn huyện thành 2 lớp + và - với khoảng cách biên
lớn nhất. Các điểm gần h nhất (được khoanh trịn) là các vector hỗ trợ - Support Vector
Khĩa luận tốt nghiệp Nguyễn Việt Cường
42
Cơng thức
Phương trình siêu mặt phẳng chứa vector id trong khơng gian:
0. =+ bwd i
Đặt
⎪⎩
⎪⎨
⎧
<+−
>++=+=
0bw.d,1
0bw.d,1
)bw.d(sign)d(h
i
i
ii
khi
khi
Từ đĩ, )( idh biễu diễn sự phân lớp của id vào hai lớp nĩi trên.
Cĩ iy = {±1}, thì với yi = +1, văn bản id ∈ lớp “+”; với yi = - 1, id ∈ lớp “-”. Lúc
này muốn cĩ siêu mặt phẳng h, ta sẽ giải bài tốn sau:
Tìm Min || w ||, trong đĩ w và b thỏa mãn điều kiện:
1)).((:,1 ≥+∈∀ bwdsignyni ii
Khi đĩ ta cĩ thể sử dụng tốn tử Lagrange biến đổi thành dạng thức để giải bài
tốn.
Ở phương pháp SVM, mặt phẳng quyết định chỉ phụ thuộc vào các điểm gần nĩ
nhất (vector hỗ trợ - support vector) mà cĩ khoảng cách đến nĩ là:
w
1 . Khi các điểm
khác bị xĩa đi thì vẫn khơng ảnh hưởng đến kết quả ban đầu.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
43
Chương 5. MỘT SỐ KẾT QUẢ THỰC NGHIỆM
5.1. Tập dữ liệu và tiền xử lý
Mơ tả dữ liệu đầu vào
Chúng tơi tiến hành thử nghiệm trên cơ sở dữ liệu là bộ phân lớp chuẩn
20newsgroup cĩ 19997 tài liệu, phân ra thành 20 lớp. Mỗi lớp cĩ khoảng 1000 tài liệu
Tuy nhiên, do số lượng văn bản của tập dữ liệu này rất lớn, nên chúng tơi chỉ
chọn ra 2 lớp để thử nghiệm. Đĩ là các lớp: rec.sport.; rec.autos .
Chúng tơi tiến hành thực nghiệm với số lượng tài liệu trong 2 lớp là: 50, 100, 500
. Trong đĩ tỷ lệ giữa tập train và tập test là: 2/1.
Biểu diễn văn bản qua các từ khĩa
Với tập dữ liệu kiểm tra, trước tiên chúng tơi thực hiện bước tiền xử lý: loại bỏ
các từ dừng. Chương trình loại bỏ từ dừng được viết bằng ngơn ngữ C/C++. Sau đĩ,
chúng tơi tạo ra tập từ khĩa của tập dữ liệu.
Sau khi hồn thành các bước trên, tiến hành biểu diễn văn bản. Các văn bản sẽ
được biểu diễn dưới dạng vector các từ khĩa. Định dạng của vector như sau:
Name_VB(id1,TS1; id2,TS2;…idn,TSn), trong đĩ: Name_VB là tên văn bản, idi là chỉ số
của từ khĩa thứ i trong tập từ khĩa ở trên; TSi là trọng số của từ khĩa thứ i. Trọng số của
từ khĩa được tính bởi cơng thức TF.IDF (chương II). Chương trình này được viết bằng
ngơn ngữ C/C++.
Biểu diễn văn bản qua các khái niệm mờ
Từ tập từ khĩa tạo được ở trên, chúng tơi tìm ra được những cụm từ khĩa cĩ liên
quan với nhau. Từ đĩ xác định các khái niệm mờ đại diện cho cụm đĩ.
Một vài ví dụ về cách biểu diễn các cụm từ khĩa liên quan và các khái niệm mờ
như sau:
“sport” = {hockey, baseball, sport, winner, finals, won, game, teams, played,
season , cup, stars, fans, newspaper, begin, goaltender, league, day, distribution, pic,
predictions, champions, scorer, power, driver, time, finished, worried, public, matter,
blow, car, miles}
Khĩa luận tốt nghiệp Nguyễn Việt Cường
44
“wood” = {hiller, wood}
“academic” = {university, academic, computer, science, school, laboratory,
college, staff, chemistry, technology, operating}
“humour” = {jokes, humour, coyote, average}
“cool” = {cool, air}
“speed” = {speed, coordination, skating, hilarious, observation, advised, ranked}
“raise” = {breakthrough, raise}
Sau khi đã xác định được các khái niệm mờ và kết hợp với tập từ khĩa trong văn
bản, chúng tơi biểu diễn văn bản theo các khái niệm mờ đĩ. Từ trọng số của các từ khĩa
trong văn bản, sử dụng hàm tích hợp mờ MAX, ta xác định được độ liên quan của các
khái niệm mờ trên đối với từng văn bản. Nếu các từ khĩa cĩ liên quan trong khái niệm mờ
khơng nằm trong văn bản đang xét, độ liên quan của khái niệm đến văn bản sẽ bằng 0.
5.2. Cơng cụ và phương pháp phân lớp
Cơng cụ phân lớp:
Chúng tơi sử dụng cơng cụ phân lớp là phần mềm Weka. Khĩa luận xin cung
cấp một số thơng tin về weka như sau:
9 Weka là một phần mềm nguồn mở về khai phá dữ liệu được phát triển bởi
đại học University of Waikato nước New Zealand. “Weka” là từ viết tắt cho
cụm từ Waikato Environment for Knowledge Analysis. Weka cĩ thể được
sử dụng ở nhiều cấp độ khác nhau. Cấp độ đơn giản của nĩ là ta cĩ thể áp
dụng các thuật tốn của Weka để xử lý dữ liệu từ dịng lệnh. Nĩ bao gồm
nhiều các cơng cụ dùng cho việc biến đổi dữ liệu, như các thuật tốn dùng
để rời rạc hĩa dữ liệu
9 Weka cung cấp tất cả các chức năng cơ bản của khai phá dữ liệu bao gồm
các thuật tốn về phân lớp (classifier), các thuật tốn về tiền xử lý dữ liệu
(filter), các thuật tốn về phân cụm (cluster), các thuật tốn về kết tập luật
(association rule).
Khĩa luận tốt nghiệp Nguyễn Việt Cường
45
Chương trình chuyển từ biểu diễn theo từ khĩa và theo khái niệm mờ sang dữ
liệu chuẩn của weka được viết bằng ngơn ngữ Java. Tập văn bản trước đĩ đã
được biểu diễn theo vector trọng số các từ khĩa trở thành Input. Sau đĩ, tiến
hành chạy chương trình và cho ra output là file dữ liệu chuẩn của weka.
Phương pháp phân lớp :
Trong chương 4, khĩa luận đã trình bày về một số thuật tốn phân lớp. Qua phân
tích, chúng tơi nhận thấy rằng: phương pháp K - Nearest Neighbor là một phương pháp
đơn giản và được đánh giá là một trong những phương pháp tốt và cho hiệu quả cao. Vì
vậy, chúng tơi chọn thuật tốn K - Nearest Neighbor trong thực nghiệm này
5.3. Kết quả thực nghiệm
Cĩ hai đại lượng thường dùng để đo hiệu suất của phân lớp văn bản, đĩ là
precision (độ chính xác) và recall (độ hồi tưởng). Ngồi ra người ta cịn xác định
thêm thơng số F1. F1 là một chỉ số cân bằng giữa độ chính xác và độ hồi tưởng,
F1 sẽ lớn khi độ chính xác và độ hồi tưởng lớn và cân bằng, F1 sẽ nhỏ khi độ
chính xác và độ hồi tưởng nhỏ hoặc khơng cân bằng. Mục tiêu trong các bài tốn
là F1 càng cao càng tốt.
Trong 1 lớp văn bản C, khi kiểm tra độ chính xác trong phân lớp, người ta
xác định 3 đại lượng: precision, recall và F1 như sau:
Trong đĩ:
9 num_of_match: là số lượng văn bản được gán nhãn đúng
9 num_of_model: là số lượng văn bản được mơ hình gán nhãn của lớp C
9 num_of_manual: là số lượng văn bản thuộc về lớp C
Khĩa luận tốt nghiệp Nguyễn Việt Cường
46
Khi phân lớp với bộ dữ liệu 50 văn bản. Trong đĩ: Traning set: 34, Test set: 16.
Sau khi thử với một số giá trị của tham số k, chúng tơi thấy k = 2, cĩ kết quả phân
lớp cao nhất.
Biểu diễn văn bản bằng tập từ khĩa:
Kết quả output như sau:
Correctly Classified Instanse: 10 62.5%
InCorrectly Classified Instances: 6 37.5%
----------------------
Precision Recall F1 Class
1 0.25 0.4 rec.autos_25
0.571 1 0.72 rec.Sport_25
----------------------
a b <---classified as
2 6 | a = rec.autos_25
0 8 | b = rec.sport_25
Khĩa luận tốt nghiệp Nguyễn Việt Cường
47
Biểu diễn bằng các khái niệm mờ:
Kết quả output như sau:
Correctly Classified Instanse: 13 81.25%
InCorrectly Classified Instances: 3 18.75%
----------------------
Precision Recall F1 Class
1 0.625 0.769 rec.autos_25
0.727 1 0.842 rec.Sport_25
----------------------
a b <---classified as
5 3 | a = rec.autos_25
0 8 | b = rec.sport_25
Khĩa luận tốt nghiệp Nguyễn Việt Cường
48
Khi phân lớp với bộ dữ liệu 100 văn bản. Trong đĩ: Traning set: 64, Test set: 32.
Cũng giống như với bộ dữ liệu gồm 50 văn bản, chúng tơi nhận thấy rằng trong
bộ dữ liệu này, k = 2 cho ta kết quả phân lớp cao nhất.
Biểu diễn văn bản bằng tập từ khĩa:
Kết quả ra như sau:
Correctly Classified Instanse: 23 71.875%
InCorrectly Classified Instances: 9 28.125%
----------------------
Precision Recall F1 Class
1 0.438 0.609 rec.autos_50
0.64 1 0.780 rec.Sport_50
----------------------
a b <---classified as
7 9 | a = rec.autos_50
0 16 | b = rec.sport_50
Khĩa luận tốt nghiệp Nguyễn Việt Cường
49
Biểu diễn văn bản bằng các khái niệm mờ:
Kết quả ra như sau:
Correctly Classified Instanse: 27 84.375%
InCorrectly Classified Instances: 5 15.625%
----------------------
Precision Recall F1 Class
1 0.688 0.815 rec.autos_50
0.762 1 0.865 rec.Sport_50
----------------------
a b <---classified as
11 5 | a = rec.autos_50
0 16 | b = rec.sport_50
Khi phân lớp với bộ dữ liệu 500 văn bản. Trong đĩ: Traning set: 334, Test
set: 166. Khơng giống với hai trường hợp trên, trong trường hợp này, k = 8 sẽ cho
kết quả phân lớp tốt nhất.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
50
Biểu diễn văn bản bằng tập từ khĩa:
Kết quả như sau:
Correctly Classified Instanse: 131 78.916%
InCorrectly Classified Instances: 35 24.084%
----------------------
Precision Recall F1 Class
0.929 0.627 0.748 rec.autos_250
0.718 0.952 0.818 rec.Sport_250
----------------------
a b <---classified as
52 31 | a = rec.autos_250
4 79 | b = rec.sport_250
Biểu diễn văn bản bằng tập các khái niệm mờ:
Khĩa luận tốt nghiệp Nguyễn Việt Cường
51
Kết quả như sau:
Correctly Classified Instanse: 146 87.952%
InCorrectly Classified Instances: 20 12.048%
----------------------
Precision Recall F1 Class
0.957 0.795 0.868 rec.autos_250
0.825 0.964 0.889 rec.Sport_250
----------------------
a b <---classified as
66 17 | a = rec.autos_250
3 80 | b = rec.sport_250
Qua ba trường hợp trên, chúng tơi nhận thấy: khi số lượng văn bản trong tập
training và tập test nhỏ, kết quả phân lớp với thuật tốn kNN khơng cao. Khi tăng dần số
Khĩa luận tốt nghiệp Nguyễn Việt Cường
52
lượng văn bản lên, kết quả cĩ tốt hơn. Giá trị của tham số k cũng tỷ lệ thuận với số lượng
này.
Đồ thị so sánh giữa việc biểu diễn văn bản theo khái niệm mờ và việc biểu diễn
theo từ khĩa thơng thường:
Khĩa luận tốt nghiệp Nguyễn Việt Cường
53
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Kết quả đạt được
Dựa vào các nghiên cứu gần đây trong bài tốn xử lý văn bản, khĩa luận đã
nghiên cứu, chọn lọc cũng như phát triển một số vấn đề và đạt được những kết quả ban
đầu như sau:
Tìm hiểu và trình bày được một số phương pháp biểu diễn văn bản.
Nghiên cứu về lý thuyết tập mờ và các phép tốn liên quan. Qua đĩ giới thiệu
được một phương pháp biểu diễn văn bản dựa trên các khái niệm mờ.
Nghiên cứu và tìm hiểu về bài tốn phân lớp, trình bày một số thuật tốn
phân lớp tiêu biểu.
Cĩ được những kết quả thử nghiệm, những so ban đầu khi áp dụng cách biểu
diễn văn bản mới với cách biểu diễn thơng thường. Qua đĩ thấy được một số
ưu điểm:
9 Giảm bớt được số chiều của vector văn bản khi biểu diễn. Giảm bớt
sự phức tạp khi tính tốn.
9 Cho kết quả tốt hơn khi áp dụng vào bài tốn phân lớp với thuật
tốn kNN
Hướng phát triển
Chúng tơi xin đề xuất một phương pháp tìm ra các từ khĩa cĩ liên quan trong
văn bản: Cĩ một tập các từ khĩa trong tập văn bản đã qua bước tiền xử lý.
Trong tập từ khĩa này, lần lượt tìm những cụm từ cùng xuất hiện trong các
văn bản và đếm số lần xuất hiện đĩ. Đặt ra một ngưỡng α, nếu số lần xuất
hiện vượt qua ngưỡng này thì ta cĩ thể coi rằng các từ trong cụm đĩ cĩ liên
quan đến nhau. Cĩ nhiều cách để chọn một từ khĩa trong cụm này làm khái
niệm, chẳng hạn lấy từ cĩ trọng số cao nhất.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
54
Thời gian tới, chúng tơi sẽ tiến hành phân lớp trên các thuật tốn khác nhau:
Nạve Bayes, Cây quyêt định, SVM… để so sánh giữa các kết quả phân lớp
và tìm ra thuật tốn phân lớp tốt nhất khi áp dụng phương pháp biểu diễn
theo khái niệm mờ.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
55
TÀI LIỆU THAM KHẢO
Tiếng Việt:
[1]. Đinh Trung Hiếu, Vũ Bội Hằng, Nguyễn Cẩm Tú, Giải pháp tìm kiếm theo
lĩnh vực trong máy tìm kiếm, Báo cáo nghiên cứu khoa học Khoa Cơng Nghệ, ĐHQGHN
năm 2004.
[2]. Đồn Sơn (2002) Phương pháp biểu diễn văn bản sử dụng tập mờ và ứng
dụng trong khai phá dữ liệu văn bản Luận văn thạc sỹ Khoa Cơng Nghệ, ĐHQGHN, năm
2002.
Tiếng Anh:
[1]. D. Hand, H. Mannila, P. Smyth, Principles of Data Mining, MIT Press,
Cambridge, MA, 2001
[2]. D.Lewis, Representation and Learning in Information Retrieval, PhD Thesis,
Graduate School of the University of Massachusetts, 1991
[3]. D. Tikk, J. D. Yang, and S. L. Bang, Hierarchical text categorization using
fuzzy relational thesaurus. Kybernetika, 39(5), pp. 583–600, 2003
[4]. Eui-Hong Han, Text Categorization Using Weight Adjusted k-Nearest
Neighbor Classification. PhD thesis, University of Minnesota, October 1999
[5] F. Sebastiani, Machine learning in automated text categorization, Technical
Report IEI-B4-31-1999, Consiglio Nazionale delle Ricerche, Pisa, Italy, 1999.
[6]. G. Piatetsky Shapiro, W. Frawley (Eds), Knowledge Discovery in Databases,
MIT Cambridge, MA,1991.
[7]. Ian H.Witten, Eibe Frank, Data Mining: Practical Machine Learning Tools
and Techniques, 2nd edition, June 2005
[8]Maria-Luiza Antonie, Osmar R. Zaıane, Text Document Categorization by
Term Association, IEEE International Conference on Data Mining, pages 19--26,
December 2002.
Khĩa luận tốt nghiệp Nguyễn Việt Cường
56
[9]. M. Grabisch, S.A.Orlovski, R.R.Yager. Fuzzy aggregation of numerical
preferences, In R. Slowinski, editor, Fuzzy Sets in Decision Analysis, Operations
Research and Statistics, pages 31-68
[10]. Ricardo Baeza-Yates, Berthier Ribeiro-Neto, Modern Information Retrieval,
Addison Wesley, 1999
[11]. S. Eyheramendy, D. Lewis and D. Madigan, On the Naive Bayes Model for
Text Categorization, In Proceedings of Artificial Intelligence & Statistics 2003.
[12]. T. Joachims, Text categorization with Support Vector Machines: Learning
with many relevant features. In Machine Learning: ECML-98, Tenth European
Conference on Machine Learning, pp. 137-142
[13]. W. Frawley, G. Piatetsky-Shapiro, C. Matheus, Knowledge Discovery in
Databases: An Overview. AI Magazine, Fall 1992.
[14]. H.J. Zimmerman, Fuzzy set Theory and Its Applications, Kluwer Academic
Publishers, 1991
Các file đính kèm theo tài liệu này:
- k47_nguyen_viet_cuong_thesis_3607.pdf