Tài liệu Đề tài Text Categorization Phân Loại Văn Bản (Chương 16): ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN MINH THÀNH – 10 12 042
ĐỒ ÁN MÔN HỌC
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
Đề tài:
Text Categorization
Phân Loại Văn Bản (Chương 16)
Dựa trên tài liệu:
Foundations Of Statistical Natural Language
Processing
Christopher D.Manning, Hinrich Schutze
TP.HCM – 01/2011
MỤC LỤC
1. Tóm tắt đồ án ................................................................................................... 1
2. Bài toán phân loại văn bản............................................................................... 2
2.1 Giới thiệu ................................................................................................... 2
2.2 Phát biểu bài toán ...................................................................................... 2
2.3 Mô hình tổng quát ...................................................................................... 3
2.3.1 Giai đoạn huấn luyện ..........
38 trang |
Chia sẻ: hunglv | Lượt xem: 1271 | Lượt tải: 1
Bạn đang xem trước 20 trang mẫu tài liệu Đề tài Text Categorization Phân Loại Văn Bản (Chương 16), để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CƠNG NGHỆ THƠNG TIN
NGUYỄN MINH THÀNH – 10 12 042
ĐỒ ÁN MƠN HỌC
XỬ LÝ NGƠN NGỮ TỰ NHIÊN
Đề tài:
Text Categorization
Phân Loại Văn Bản (Chương 16)
Dựa trên tài liệu:
Foundations Of Statistical Natural Language
Processing
Christopher D.Manning, Hinrich Schutze
TP.HCM – 01/2011
MỤC LỤC
1. Tĩm tắt đồ án ................................................................................................... 1
2. Bài tốn phân loại văn bản............................................................................... 2
2.1 Giới thiệu ................................................................................................... 2
2.2 Phát biểu bài tốn ...................................................................................... 2
2.3 Mơ hình tổng quát ...................................................................................... 3
2.3.1 Giai đoạn huấn luyện ........................................................................... 4
2.3.2 Giai đoạn phân lớp .............................................................................. 5
2.4 Tiền xử lý văn bản ..................................................................................... 6
2.5 Phương pháp biểu diễn văn bản ................................................................ 7
2.5.1 Mơ hình khơng gian vector .................................................................. 7
2.5.2 Khái niệm trọng số ............................................................................... 7
2.6 Đánh giá bộ phân lớp ................................................................................. 9
2.6.1 Macro-Averaging ............................................................................... 11
2.6.2 Micro-Averaging ................................................................................ 11
3. Các phương pháp phân loại văn bản ............................................................. 12
3.1 Thuật tốn Nạve Bayes ........................................................................... 12
3.1.1 Định lý ............................................................................................... 12
3.1.2 Thuật tốn ......................................................................................... 13
3.1.3 Áp dụng trong phân loại văn bản ....................................................... 15
3.2 Cây quyết định (Decision Tree) ................................................................ 18
3.2.1 Khái niệm .......................................................................................... 18
3.2.2 Thuật tốn xây dựng cây ................................................................... 19
3.2.2.1 Thuật tốn ID3 ............................................................................ 19
3.2.2.2 Các độ đo trong thuật tốn : ........................................................ 20
3.2.2.3 Ví dụ ........................................................................................... 20
3.2.3 Áp dụng vào phân loại văn bản ......................................................... 23
3.2.3.1 Biểu diễn văn bản ....................................................................... 23
3.2.3.2 Giai đoạn huấn luyện .................................................................. 24
3.2.3.3 Cross-validation .......................................................................... 28
3.2.3.4 Giai đoạn phân lớp ..................................................................... 29
3.3 Mơ hình xác xuất Entropy tối đại (Maximum Entropy Modeling) .............. 29
3.3.1 Entropy .............................................................................................. 29
3.3.1.1 Khái niệm .................................................................................... 29
3.3.1.2 Entropy của biến ngẫu nhiên ...................................................... 30
3.3.2 Áp dụng vào phân loại văn bản ......................................................... 30
3.3.2.1 Biểu diễn văn bản ....................................................................... 30
3.3.2.2 Hàm đặc trưng và ràng buộc ...................................................... 31
3.3.2.3 Một số kí hiệu : ............................................................................ 31
3.3.2.4 Mơ hình ....................................................................................... 31
3.3.2.5 Thủ tục huấn luyện Generalized iterative scaling ........................ 32
3.3.2.6 Giai đoạn phân lớp ..................................................................... 34
5. Tài liệu tham khảo .......................................................................................... 35
1
1. Tĩm tắt đồ án
Phần này trình bày sơ lược về bài tốn “Phân loại văn bản” được đề
cập đến trong cuốn sách “Foundations Of Statistical Natural
Language Processing” và các phương pháp để thực thi bài tốn phân
loại văn bản theo phương pháp thống kê.
Phân loại văn bản là một vấn đề quan trọng trong lĩnh vực xử lý ngơn ngữ.
Nhiệm vụ của bài tốn này là gán các tài liệu văn bản vào nhĩm các chủ đề cho
trước. Đây là một bài tốn rất thường gặp trong thực tế điển hình như : một nhà
chuyên phân tích thị thường chứng khốn, anh ta cần phải tổng hợp rất nhiều tài
liệu, bài viết về thị trường chứng khốn để đọc và đưa ra phán đốn của mình.
Tuy nhiên, anh ta khơng thể đọc tất cả các bài viết, bài báo hay các tài liệu để rồi
phân loại chúng đâu là tài liệu chứng khốn sau đĩ anh ta mới đọc kỹ chúng cho
mục đích của anh ta. Lý do của vấn đề này là bởi ví số lượng bào viết, bài báo
hiện nay rất nhiều, đặc biệt là trên internet, nếu để đọc hết được tất cả tài liệu đĩ
thì sẽ mất rất nhiều thời gian. Một ví dụ khác trong thực tế là việc phân loại spam
mail. Khi một mail được gửi đến hộp thư, nếu để người dùng phải đọc tất cả các
mail thì sẽ tốn rất nhiều thời gian vì spam mail rất nhiều. Vì vậy, cần cĩ một hệ
thống phân loại đâu là spam mail và đâu là mail tốt.
Để giải bài tốn này đã cĩ rất nhiều phương pháp được đưa ra như : thuật
tốn Nạve Bayes, K-NN (K-Nearest-Neighbor), Cây quyết định (Decision Tree),
Mạng Neuron nhân tạo (Artificial Neural Network) và SVM (Support Vector
Machine). Mỗi phương pháp đều cho kết quả khá tốt cho bài tốn này, tuy nhiên
để cĩ được sự so sánh đầy đủ, ở các phân sau chúng ta sẽ đi vào chi tiết từng
phương pháp.
Đồ án nêu ra chi tiết các bước thực hiện bài tốn “Phân Loại Văn Bản” trong
lĩnh vực xử lý ngơn ngữ tự nhiên và một số cách tiếp cận để giải quyết bài tốn
cũng những kết quả đã đạt được dựa trên một số những ví dụ thử nghiệm của tác
giả trong cuốn sách này.
2
2. Bài tốn phân loại văn bản
Phần này trình bày về chi tiết các bước thực hiện bài tốn phân loại
văn bản như mơ hình biểu diễn, các độ đo cũng như các phương pháp
đánh giá kết quả thực hiện bài tốn phân loại văn bản.
2.1 Giới thiệu
Như đã trình bày ở trên, bài tốn phân loại văn bản là một bài tốn quan trọng
trong xử lý ngơn ngữ. Cĩ khá nhiều bài tốn phân loại trong lĩnh vực xử lý ngơn
ngữ tự nhiên như : gán nhãn từ loại (POS tagging), khử nhập nhằng nghĩa từ
vựng (Word Sense Disambiguation) và gán nhãn ngữ tính từ (Prepositional
Phrase Attachment)…
Mỗi bài tốn phân loại đều cĩ các đối tượng thao tác khác nhau và mục tiêu
phân loại khác nhau. Trong bài tốn gán nhãn từ loại (POS tagging) và khử nhập
nhằng nghĩa từ vựng (Word Sense Disambiguation), thì từ được xem là đối tượng
nội dung cần thao tác (mức độ từ). Trong gán nhãn ngữ tính từ (Prepositional
Phrase Attachment) thì một ngữ là đối tượng nội dung cần thao tác. Cịn trong bài
tốn phân loại văn bản thì một văn bản (document hay text) là đối tượng nội dung
cần thao tác.
Hình 2.1: Các bài tốn phân loại trong xử lý ngơn ngữ tự nhiên
2.2 Phát biểu bài tốn
Bài tốn phân loại văn bản cĩ thể được phát biểu như sau : Cho trước một tập
văn bản D={d1,d2,…,dn} và tập chủ đề được định nghĩa C={c1,c2,…,cn}.
Nhiệm vụ của bài tốn là gán lớp di thuộc về cj đã được định nghĩa. Hay nĩi
cách khác, mục tiêu của bài tốn là đi tìm hàm :
3
: DxC Boolean
( ) {
( ) nếu d thuộc về lớp c
( ) nếu d khơng thuộc về lớp c
Trong các thử nghiệm của tác giả, ơng đã sử dụng các bài viết tin tức của
hãng tin Reuters, cũng như danh sách các chủ đề tin tức của hãng này.
Hình 2.2: Ví dụ về một bản tin tức của Reuters
Các chủ đề tin tức của Hãng Reuters với hơn 100 chủ đề và số lượng bài viết
(văn bản) tác giả sử dụng trong các thử nghiệm này là 12,902 bài viết.
2.3 Mơ hình tổng quát
Cĩ rất nhiều hướng tiếp cận bài tốn phân loại văn bản đã được nghiên cứu
như: tiếp cận bài tốn phân loại dựa trên lý thuyết đồ thị, cách tiếp cận sử dụng lý
thuyết tập thơ, cách tiếp cận thống kê… Tuy nhiên, tất cả các phương pháp trên
đều dựa vào các phương pháp chung là máy học đĩ là : học cĩ giám sát, học
khơng giám sát và học tăng cường.
4
Vấn đề phân loại văn bản theo phương pháp thống kê dựa trên kiểu học cĩ
giám sát được đặc tả bao gồm 2 giai đoạn : giai đoạn huấn luyện và giai đoạn
phân lớp.
2.3.1 Giai đoạn huấn luyện
Chúng ta cĩ một tập huấn luyện, mỗi phần tử trong tập huấn luyện được gán
vào một hoặc nhiều lớp mà chúng ta sẽ thể hiện chúng bằng một mơ hình mã hố
(được trình bày chi tiết ở Phương pháp biểu diễn văn bản). Thơng thường, mỗi
phần tử trong tập huấn luyện được thể hiện theo dạng ( ⃗⃗⃗ ). Trong đĩ, là vector
biểu diễn cho văn bản trong tập huấn luyện.
Sau đĩ, chúng ta định nghĩa một lớp mơ hình và một thủ tục huấn luyện. Lớp
mơ hình là họ các tham số của bộ phân loại, thủ tục huấn luyện là một giải thuật
(hay thuật tốn) để chọn ra một họ các tham số tối ưu cho bộ phân loại. Nhưng
làm thế nào để đánh giá được họ các tham số là tối ưu ? Câu hỏi này sẽ được
trình bày trong phần Đánh giá bộ phân lớp.
Hình 2.3: Mơ hình giai đoạn huấn luyện
Đầu vào : ngữ liệu huấn luyện và thuật tốn huấn luyện
Đầu ra : mơ hình phân lớp (bộ phân lớp – classifier)
Một ví dụ về một họ các tham số cho bộ phân loại nhị phân : ( ) ⃗⃗ .
Ở đây, bộ phân loại nhị phân chỉ phân loại cho 2 lớp. Chúng ta gọi lớp c1 là lớp
với các văn bản cĩ ( ) và lớp c2 là lớp với các văn bản cĩ ( ) .Họ các
tham số cần xác định là vector ⃗⃗ và ngưỡng .
Chi tiết giai đoạn huấn luyện bộ phân lớp
5
Hình 2.4: Chi tiết giai đoạn huấn luyện
Trong đĩ :
Ngữ liệu huấn luyện : kho ngữ liệu thu thập từ nhiều nguồn khác
nhau.
Tiền xử lý : chuyển đổi tài liệu trong kho ngữ liệu thành một hình thức
phù hợp để phân loại.
Vector hố : mã hố văn bản bởi một mơ hình trọng số (chi tiết ở phần
Phương pháp biểu diễn văn bản).
Trích chọn đặc trưng : loại bỏ những từ (đặc trưng) khơng mang
thơng tin khỏi tài liệu nhằm nâng cao hiệu suất phân loại và giảm độ
phức tạp của thuật tốn huấn luyện.
Thuật tốn huấn luyện : Thủ tục huấn luyện bộ phân lớp để tìm ra họ
các tham số tối ưu.
Đánh giá : bước đánh giá hiệu suất (chất lượng) của bộ phân lớp (chi
tiết trong phần Đánh giá bộ phân lớp).
Thủ tục huấn luyện sẽ được thực thi lặp nhiều lần để tìm họ các tham số tối
ưu sau mỗi lần lặp. Tuy nhiên, do ban đầu họ các tham số được gán với một giá
trị khởi tạo, do đĩ nếu giá trị khởi tạo ban đầu được gán sai thì kết quả tối ưu của
họ các tham số cĩ thể chỉ là tối ưu cục bộ.
2.3.2 Giai đoạn phân lớp
Sau khi đã hồn thành giai đoạn huấn luyện, mơ hình phân lớp sẽ được áp
dụng cho các văn bản mới cần phân loại.
6
Hình 2.5: Mơ hình giai đoạn phân lớp
Chi tiết giai đoạn phân lớp
Hình 2.6: Mơ hình giai đoạn phân lớp
2.4 Tiền xử lý văn bản
Văn bản trước khi được vector hố, tức là trước khi sử dụng, cần phải được
tiền xử lý. Quá trình tiền xử lý sẽ giúp nâng cao hiệu suất phân loại và giảm độ
phức tạp của thuật tốn huấn luyện.
Tuỳ vào mục đích bộ phân loại mà chúng ta sẽ cĩ những phương pháp tiền
xử lý văn bản khác nhau, như :
Chuyển vẳn bản về chữ thường
Loại bỏ dấu câu (nếu khơng thực hiện tách câu)
Loại bỏ các kí tự đặc biệt biệt([ ],[.], [,], [:], [“], [”], [;], [/], [[]], [~], [`], [!],
[@], [#], [$],[%],[^],[&],[*],[(],[)]), các chữ số, phép tính tốn số học
Loại bỏ các stopword (những từ xuất hiện hầu hết trong các văn bản)
khơng cĩ ý nghĩa khi tham gia vào phân loại văn bản.
…
7
2.5 Phương pháp biểu diễn văn bản
Một trong những nhiệm vụ đầu tiền trong việc xử lý phân loại văn bản là chọn
được một mơ hình biểu diễn văn bản thích hợp. Một văn bản ở dạng thơ (dạng
chuỗi) cần được chuyển sang một mơ hình khác để tạo thuận lợi cho việc biểu
diễn và tính tốn. Tuỳ thuộc vào từng thuật tốn phân loại khác nhau mà chúng ta
cĩ mơ hình biểu diễn riêng. Một trong những mơ hình đơn giản và thường được
sử dụng trong nhiệm vụ này là mơ hình khơng gian vector. Một văn bản trong
nhiệm vụ này được biểu diễn theo dạng , với là một vector n chiều để đo
lường giá trị của phần tử văn bản.
2.5.1 Mơ hình khơng gian vector
Mơ hình khơng gian vector là một trong những mơ hình được sử dụng rộng
rãi nhất cho việc tìm kiếm (truy hồi) thơng tin. Nguyên nhân chính là bởi vì sự đơn
giản của nĩ.
Trong mơ hình này, các văn bản được thể hiện trong một khơng gian cĩ số
chiều lớn, trong đĩ mỗi chiều của khơng gian tương ứng với một từ trong văn bản.
Phương pháp này cĩ thể biểu diễn một cách hình tượng như sau : mỗi văn bản D
được biểu diễn dưới dạng (vector đặc trưng cho văn bản D). Trong đĩ,
( ), và n là số lượng đặc trưng hay số chiều của vector văn bản, là
trọng số của đặc trưng thứ i (với 1 i n).
Như vậy, nếu trong kho ngữ liệu của quá trình huấn luyện nhiều văn bản, ta kí
hiệu Dj, là văn bản thứ j trong tập ngữ liệu, và vector ⃗⃗ ⃗ ( ) là
vector đặc trưng cho văn bản Dj, và xij là trọng số thứ i của vector văn bản .
2.5.2 Khái niệm trọng số
Một vấn đề quan trọng nữa trong việc biểu diễn một văn bản đĩ là tính trọng
số cho vector đặc trưng của văn bản. Cĩ nhiều cách khác nhau để tính trọng số
này như :
Word frequency weighting
Boolean weighting
tf*idf weighting
8
Entropy weighting
Tuy nhiên, để đơn giản cho vấn đề này, chúng ta sẽ chỉ xem xét cách tính
Word frequency weighting (trọng số tần suất từ) và tf*idf, một cách đơn giản đĩ là
đếm số từ đĩ trong văn bản. Tuy nhiên vẫn cĩ nhiều cách khác nhau để tính trọng
số dạng này.
Hình 2.7: Ba giá trị trong cách tính trọng số thuật ngữ (từ) thường dùng
Cĩ ba thơng tin được sử dụng trong cách tính trọng số bằng tần suất từ là :
term frequency (tfij số lần suất hiện của từ wi trong văn bản dj), document
frequency (dfi số văn bản cĩ chứa từ wi), collection frequency (cfi số lần suất hiện
của từ wi trong cả tập ngữ liệu). Trong đĩ, và ∑ .
Thơng tin được nắm bắt bởi term frequency là sự nổi bật của thơng tin (hay
từ) trong một văn bản. Term frequency càng cao (số lần xuất hiện càng nhiều
trong văn bản) thì đĩ là từ miêu tả tốt cho nội dung văn bản. Giá trị thứ hai,
document frequency, cĩ thể giải thích như là một bộ chỉ định nội dung thơng tin.
Một từ được tập trung ngữ nghĩa thường xảy ra nhiều lần trong một văn bản nếu
nĩ cũng xuất hiện trong tất cả các văn bản khác. Nhưng từ khơng được tập trung
ngữ nghĩa trải đều đồng nhất trong tất cả các văn bản.
Hãy xem xét một ví dụ sau, kho ngữ liệu của báo New York Times, và hai từ
try và insurance được thống kế như sau :
Hai từ try và insurance cĩ giá trị gần như nhau. Nhưng ngược lại, với giá trị
, từ insurance chỉ xuất hiện trong hẫu như chỉ một nửa kho ngữ liệu. Điều này
giải thích là bởi vì, từ try cĩ thể được sử dụng trong hầu hết các chủ đề, nhưng từ
insurance chỉ được dùng để ám chỉ đến một khái niệm nhỏ mà chỉ liên quan đến
một số lượng nhỏ các chủ đề. Một tính chất nữa của từ được tập trung ngữ nghĩa
đĩ là, nếu chúng xuất hiện trong một văn bản thì chúng sẽ xuất hiện vài lần.
9
Để thể hiện trọng số phản ánh hết thơng tin của từ, thường ta sẽ kết hợp cả
hai loại trọng số là và trong một đơn vị chung. Dạng biểu diễn trọng số này
được gọi là . Cơng thức kết hợp hai giá trị trọng số :
( ) {
( ( )) (
)
Trong đĩ, N là tổng số văn bản. Biểu thức thứ nhất áp dụng cho các từ cĩ
xuất hiện trong văn bản, cịn biểu thức thứ hai cho các từ khơng xuất hiện trong
văn bản.
2.6 Đánh giá bộ phân lớp
Sau khi đã tìm được họ các tham số tối ưu cho bộ phân lớp (hay cĩ thể nĩi là
bộ phân lớp đã được huấn luyện xong), nhiệm vụ tiếp theo là cần phải đánh giá
(kiểm tra) bộ phân lớp đĩ cho kết quả như thế nào? Tuy nhiên, quá trình kiểm tra
phải được thực hiện trên một tập ngữ liệu khác với tập ngữ liệu huấn luyện, cịn
được gọi với cái tên là tập ngữ liệu kiểm tra (a test set). Việc kiểm tra bộ phân lớp
là một sự đánh giá trên một tập ngữ liệu chưa được biết vì thế đĩ là sự đo lường,
đánh giá duy nhất cho biết khả năng thực sự của một bộ phân lớp.
Để đơn giản, ta sẽ xem xét một bộ phân lớp nhị phân (phân hai lớp). Những
bộ phân lớp thường được đánh giá bằng cách lập một bảng thống kê sau :
Trong đĩ,
a : là số lượng đối tượng thuộc về lớp đang xét và được bộ phân lớp
gán vào lớp.
b : là số lượng đối tượng khơng thuộc về lớp đang xét nhưng được bộ
phân lớp gán vào lớp.
c : là số lượng đối tượng thuộc về lớp đang xét nhưng được bộ phân
lớp loại khỏi lớp.
10
d : là số lượng đối tượng khơng thuộc về lớp đang xét và được bộ phân
lớp loại khỏi lớp.
Để đánh giá chất lượng bộ phân lớp, hai đơn vị đo lường quan trọng đĩ là độ
đúng đắn (accuracy) được đo bằng cơng thức
và độ sai lỗi (Error) được
tính bằng cơng thức
. Độ đo này phản ánh đầy đủ chất lượng của bộ phân
lớp. Tuy nhiên, khi đánh giá bộ phân lớp, thường người ta chỉ xem xét những đối
tượng thuộc về lớp và được phân lớp đúng, cịn những đối tượng khơng thuộc về
lớp thường sẽ ít được quan tâm. Do đĩ, một số độ đo khác đã được định nghĩa.
Các độ đo bao gồm :
Precision (độ chính xác) :
Recall (Độ bao phủ, độ đầy đủ) :
Fallout (Độ loại bỏ) :
Tuy nhiên, trong một số trường hợp thực tế, nếu tính độ precision và độ recall
riêng rẽ sẽ cho kết quả khơng cân đối. Do đĩ, để thuận tiện, người ta kết hợp hai
độ đo này vào một đơn vị đo tổng quát duy nhất. Để làm điều này, người ta sử
dụng đơn vị đo lường F được định nghĩa như sau :
( )
Trong đĩ:
P là độ chính xác Precision
R là độ bao phủ Recall
là một hệ số xác định sự cân bằng của độ quyết định và độ bao phủ.
Giá trị =5 thường được chọn cho sự cân bằng giữa P và R. Với giá trị
này độ đo được tính đơn giản là ( ).
Những độ đo trên được dùng để đánh giá cho những bộ phân lớp nhị phân
(phân hai lớp). Tuy nhiên, trong thực tế, thường các bộ phân lớp phải phân chia
nhiều lớp, chính vì vậy để đánh giá tổng thể tồn bộ các lớp phân loại, sau khi lập
11
bảng thống kê cho từng lớp, hai phương pháp nữa đã được áp dụng để đánh giá
đĩ là micro-averaging và macro-averaging.
2.6.1 Macro-Averaging
Đây là phương pháp tính trung bình các độ đo precious và recall của từng lớp.
Các lớp sau khi đã lập bảng thống kê và tính các độ đo precious và recall cho
từng lớp. Các độ đo này sẽ được tính trung bình lại.
Cơng thức tính macro-averaging :
| |
∑
| |
| |
∑
| |
Trong đĩ : |C| là số lớp cần phân loại.
2.6.2 Micro-Averaging
Đây là phương pháp tính trung bình các kết quả thống kê của từng lớp. Các
lớp sau khi đã lập bảng thống kê. Các bảng này sẽ được cộng này lại tương ứng
theo từng ơ. Sau đĩ, sẽ tính độ đo Precision và Recall cho bảng thống kê lớn đĩ.
Cơng thức micro-averaging :
∑
| |
∑ ( )
| |
∑
| |
∑ ( )
| |
12
3. Các phương pháp phân loại văn bản
Phần này trình bày một số phương pháp phân loại văn bản phổ biến hiện
nay theo phương pháp thống kê : thuật tốn Nạve Bayes, Cây quyết định,
Maximun Entropy Modeling và KNN. Phần này cũng trình bày một số ví dụ về
cách thực hiện các phương pháp phân loại.
3.1 Thuật tốn Nạve Bayes
3.1.1 Định lý
Đây là thuật tốn được xem là đơn giản nhất trong các phương pháp. Bộ
phân lớp Bayes cĩ thể dự báo các xác suất là thành viên của lớp, chẳng hạn xác
suất mẫu cho trước thuộc về một lớp xác định. Chúng giả định các thuộc tính là
độc lập nhau (độc lập điều kiện lớp).
Thuật tốn Nạve Bayes dựa trên định lý Bayes được phát biểu như sau :
( | )
( | ) ( )
( )
Trong đĩ:
Y đại diện một giả thuyết, giả thuyết này được suy luận khi cĩ được
chứng cứ mới X.
P(X) : xác xuất X xảy ra (Xác suất biên duyên của X).
P(Y) : xác xuất Y xảy ra (Điều kiện tiên nghiệm của Y).
P(X|Y) : xác xuất X xảy ra khi Y xảy ra (xác suất cĩ điều kiện, khả năng
của X khi Y đúng).
P(Y|X) : xác suất hậu nghiệm của Y nếu biết X.
Áp dụng trong bài tốn phân loại, các dữ kiện cần cĩ :
D: tập dữ liệu huấn luyện đã được vector hố dưới dạng
( )
Ci : tập các tài liệu của D thuộc lớp Ci với i={1,2,3,…}
Các thuộc tính x1,x2,…xn độc lập xác suất đơi một với nhau.
Theo định lý Bayes :
13
( | )
( | ) ( )
( )
Theo tính chất độc lập điều kiện :
( | ) ∏ ( | ) ( | ) ( | )
( | )
Khi đĩ, luật phân lớp cho các tài liệu mới Xnew = {x1,x2,…,xn} là:
( ( )∏ ( | )
)
Trong đĩ :
P(Ci) : được tính dựa trên tần suất xuất hiện tài liệu trong tập huấn
luyện.
P(xk|Ci) : được tính từ những tập thuộc tính đã được tính trong quá
trìnhuấn luyện.
3.1.2 Thuật tốn
Các bước thực hiện thuật tốn Nạve Bayes:
Bước 1 :
Huấn luyện Nạve Nayes(dựa vào tập dữ liệu
o Tính xác suất P(Ci)
o Tính xác suất P(xk|Ci)
Bước 2 :
Xnew được gán vào lớp cĩ giá trị lớn nhất theo cơng thức
( ( )∏ ( | )
)
Xét một ví dụ kinh điển là ví dụ dự đốn xem quyết định của người chơi cĩ đi
chơi Tennis hay khơng với các điều kiện về thời tiết đã được biết trước. Trong ví
dụ này, ta cĩ một bảng dữ liệu huấn luyện như sau :
14
Bước 1 :
Tính các xác suất P(Ci)
Với C1 = “yes”
P(C1) = P(“yes”) = 9/14
Với C2 = “no”
P(C2) = P(“no”) = 5/14
Tính xác suất P(xk|Ci)
Với thuộc tính Outlook : cĩ các giá trị sunny, overcast, rain
P(sunny|yes) = 2/9
P(sunny|no) = 3/5
P(overcast|yes) = 4/9
P(overcast|no) = 0/5
P(rain|yes) = 3/9
P(rain|no) = 2/5
Với thuộc tính Temp : cĩ các giá trị Hot, Cold, Mild
P(hot|yes) = 2/9
15
P(hot|no) = 2/5
P(cold|yes) = 3/9
P(cold|no) = 1/5
P(mild|yes) = 4/9
P(mild|no) = 2/5
Với thuộc tính Humidity : cĩ các giá trị Normal,High
P(normal|yes) = 6/9
P(normal|no) = 1/5
P(high|yes) = 3/9
P(high|no) = 4/5
Với thuộc tính Wind : cĩ các giá trị Weak, Strong
P(weak|yes) = 6/9
P(weak|no) = 2/5
P(strong|yes) = 3/9
P(strong|no) = 3/5
Bước 2 : Phân lớp Xnew = {sunny, cool, high, strong}
Tính các xác suất
P(yes)*P(Xnew|yes) = 0.005
P(no)* P(Xnew|no) = 0.021
Xnew thuộc vào lớp No
3.1.3 Áp dụng trong phân loại văn bản
Để áp dụng thuật tốn Nạve Bayes vào phân loại văn bản, ta cần thực hiện
các bước tiền xử lý và vector hố các văn bản trong tập huấn luyện. Các phương
pháp tiền xử lý và vector hố đã được trình bày ở những phần trước. Tuy nhiên,
do thuật tốn Nạve Bayes dựa trên xác suất văn bản và xác suất đặc trưng, do
đĩ ở phương pháp này, chúng ta sẽ sử dụng phương pháp vector hố bằng cách
đếm tần suất từ (Word frequency weighting).
16
Sau khi đã vector hố các văn bản, ta cần thực hiện rút chọn các đặc trưng
cho các văn bản huấn luyện. Ta cũng cĩ rất nhiều cách để thực hiện rút chọn đặc
trưng như sử dụng các độ đo (xem thêm trong sách [1]), sử dụng Heuristic, sử
dụng từ điển…
Sau khi đã rút chọn đặc trưng, ta sẽ thực hiện thuật tốn huấn luyện. Ta cĩ
thể tĩm tắt các bước như sau :
Bước 1 : Huấn luyện
Từ tập huấn luyện, ta rút trích tập từ vựng (các đặc trưng)
Tính xác suất P(Ci) và P(xk|Ci)
( )
| |
| |
docsi : số tài liệu của tập huấn luyện thuộc lớp ci.
: số tài liệu cĩ trong tập huấn luyện.
( | )
| |
hoặc
( | )
| |
(làm mịn với luật Laplace)
n : tổng số từ đơi một khác nhau của lớp ci.
nk : tổng số từ xk trong tập từ vựng trong lớp Ci.
|Texti|: tổng số từ vựng (khơng phân biệt đơi một) trong lớp Ci.
Bước 2 : Phân lớp
| |
( ( ) ∏ ( ( | ) | |
)
)
positions : tập từ vựng trong bộ huấn luyện.
Xét ví dụ : ta cĩ tập tài liệu để huấn luyện sau khi đã vector hố (sử dụng
phương pháp đơn giản đếm sơ lần xuất hiện) và rút trích đặc trưng như sau :
Bộ từ vựng (đặc trưng) : var, bit, chip, log
17
Docs Var Bit Chip Log Class
Doc1 42 25 7 56 Math
Doc2 10 28 45 2 Comp
Doc3 11 25 22 4 Comp
Doc4 33 40 8 48 Math
Doc5 28 32 9 60 Math
Doc6 8 22 30 1 Comp
Bước huấn luyện :
Tính xác xuất các lớp Ci trong tập huấn luyện
( )
( )
Tính xác xuất P(xk|Ci)
Lớp C1 = “Comp”
Tổng = 208
( | )
( | )
( | )
( | )
Lớp C2 = “Math”
Tổng = 388
( | )
( | )
( | )
18
( | )
Bước phân lớp : cho văn bản cĩ vector đặc trưng sau
( )
Xác định lớp cho văn bản mới ?
Tính các xác xuất :
( ) , ( | ) ( | ) ( | )
( | ) -
( ) , ( | ) ( | ) ( | )
( | ) -
Kết quả :
Văn bản Docnew thuộc về lớp Math do max(P
new )= 598,62
3.2 Cây quyết định (Decision Tree)
3.2.1 Khái niệm
Cây quyết định là một cấu trúc cây với :
Mỗi nút trong (internal node) ứng với một phép kiểm tra trên một thuộc
tính.
Mỗi nhánh biểu diễn một kết quả của phép kiểm tra.
Các nút lá (leaf node) biểu diễn các lớp hay các phân bố lớp.
Nút cao nhất trong cây là nút gốc (root node).
Hình 3.1: Cây quyết định cho phân lớp mua máy tính hay khơng ?
19
3.2.2 Thuật tốn xây dựng cây
3.2.2.1 Thuật to|n ID3
Sườn chung về quy nạp trên cây quyết định :
1. Chọn thuộc tính tốt nhất theo một độ đo lựa chọn cho trước.
2. Mở rộng cây bằng thêm các nhánh mới cho từng thuộc tính.
3. Sắp xếp các mẫu huấn luyện vào nút lá.
4. Nếu các mẫu được phân lớp rõ thì dừng ngược lại lặp lại các bước 1-4
cho các nút lá.
5. Tỉa các nút lá khơng ổn định.
Hình 3.2: Một ví dụ chi tiết về cây quyết định
Chi tiết chiến lược để xây dựng cây quyết định theo thuật tốn ID3
Bắt đầu từ nút đơn biểu diễn tất cả các mẫu
Nếu các mẫu thuộc về cùng một lớp, nút trở thành nút lá và được gán
nhãn bằng lớp đĩ
Ngược lại, dùng độ đo thuộc tính để chọn thuộc tính sẽ phân tách tốt
nhất các mẫu vào các lớp
Một nhánh được tạo cho từng giá trị của thuộc tính được chọn và các
mẫu được phân hoạch theo
Dùng đệ quy cùng một quá trình để tạo cây quyết định
Tiến trình kết thúc chỉ khi bất kỳ điều kiện nào sau đây là đúng
20
o Tất cả các mẫu cho một nút cho trước đều thuộc về cùng một
lớp.
o Khơng cịn thuộc tính nào mà mẫu cĩ thể dựa vào để phân
hoạch xa hơn.
3.2.2.2 C|c độ đo trong thuật to|n :
Entropy : đặc trưng cho độ hỗ tạp của (tinh khiết) của một tập bất kỳ
các mẫu thử.
( ) ∑
Trong đĩ :
o S : tập các mẫu thử (tập huấn luyện)
o c : là phân lớp trong mẫu thử
o pi : xác suất (tỉ lệ) các mẫu thử thuộc phân lớp ci
Information Gain : đo sự giảm sút mong muốn của Entropy gây ra bởi
một thuộc tính A.
( ) ( ) ∑
| |
( )
( )
Trong đĩ :
o Value(A) : tập các giá trị cĩ thể cho thuộc tính A.
o Sv : tập con của S mà A nhận giá trị v.
3.2.2.3 Ví dụ
Xét lại ví dụ về phân lớp cho quyết định chơi Tennis đã được nêu ở phương
pháp Nạve Bayes như sau :
21
Ta gọi các mẫu thuộc lớp “Yes” là lớp dương và các mẫu thuộc lớp “No” là lớp
âm, vậy ta cĩ 9 mẫu dương và 5 mẫu âm, kí hiệu [9+,5-].
Theo thuật tốn ID3, ta cĩ nút đầu tiên thể hiện tất cả các mẫu của tập huấn
luyện.
Tính Entropy cho nút S :
( )
Tính Information Gian cho các thuộc tính trong tập huấn luyện :
( ) ( ) ∑
| |
( )
* +
( )
( )
( )
Trong đĩ :
22
( )
( )
Tính tương tự cho các thuộc tính cịn lại, ta cĩ kết quả như sau :
( )
( )
( )
( )
Dựa vào kết quả trên, ta sẽ chọn thuộc tính Outlook làm điều kiện phân tách
cây.
Làm tiếp theo cho hai tập con :
Ssunny={D1, D2, D3, D9, D11}
Srain={D4, D5, D6, D10, D14}
Cuối cùng ta được cây quyết định hồn chỉnh :
23
Sử dụng cây quyết định để phân lớp văn bản mới sau :
Xnew = {sunny, cool, high, strong}
Áp dụng cây phân lớp, từ nút gốc là thuộc tính outlook , Xnew cĩ giá trị Sunny,
ta sẽ rẽ nhánh trái của cây. Đến nút Humidity, Xnew cĩ giá trị high, tiếp tục rẽ
nhánh trái => Xnew thuộc lớp No.
3.2.3 Áp dụng vào phân loại văn bản
3.2.3.1 Biểu diễn văn bản
Như đã trình bày, cĩ nhiều phương pháp để biểu diễn (vector hố) văn bản.
Trong phạm vi tài liệu đang tham khảo, tác giá đã sử dụng một cách đơn giản để
biểu diễn văn bản như sau :
Gọi ( ) là vector biểu diễn văn bản, và wij là các trọng số
của các đặc trưng trong văn bản. Trọng số của các đặc trưng được tính theo cơng
thức sau :
(
( )
( )
)
Trong đĩ
: tần suất của từ i trong văn bản j
: chiều dài của văn bản j
Nếu từ i khơng xuất hiện trong văn bản thì wij sẽ được gán là 0
Ví dụ, trong một văn bản từ “profit” xuất hiện 6 lần, và chiều dài của văn bản là
89 từ, thì trọng số cho từ “profit” là
và được làm trịn là 5.
Mặc dù đã cĩ phương pháp để biểu diễn văn bản, tuy nhiên vấn đề là sử dụng
bao nhiêu đặc trưng và nhưng đặc trưng nào để biểu diễn cho văn bản đĩ. Cách
đơn giản là ta chọn những từ xuất hiện nhiều nhất trong văn bản làm được trưng
và số lượng chọn phải hợp lý. Tuy nhiên, trong phân loại văn bản, khơng phải
những từ xuất hiện nhiều trong văn bản là những đặc trưng tốt. Do đĩ, ta cần phải
sử dụng một độ đo tốt hơn để quyết định chọn xem đặc trưng nào.
24
Trong chương này, tác giả đã sử dụng độ đo 2 (đọc là chi-square test). 20
đặc trưng cĩ độ đo 2 = ∑
( )
cao nhất được sử dụng để
biểu diễn văn bản. Ở phần này, chúng ta khơng tập trung chi tiết vào tìm hiểu độ
này, nếu cần đọc chi tiết cĩ thể xem ở phần 5.3.3 của cuốn sách.
Hình 3.3: Một ví dụ biểu diễn văn bản
3.2.3.2 Giai đoạn huấn luyện
Như đã trình bày ở phân thuật tốn, để xây dựng cây phân lớp, chúng ta sẽ đi
từ nút gốc chứa tất cả các văn bản cần phân loại. Trong thử nghiệm của tác giá,
ơng đã dùng 7681 văn bản để huấn luyện. Và mục tiêu là phân lớp văn bản thuộc
về chủ đề “earning”. Trong đĩ cĩ, 2304 văn bản thuộc chủ đề cần phân loại, cịn
lại là 5377 văn bản khơng thuộc nhĩm chủ đề đĩ.
Biểu diễn nút gốc như sau :
25
Trong đĩ :
P(c|n1) : xác suất một văn bản tại node 1 thuộc về lớp c. Xác suất được
tính bằng cơng thức
( | )
| |
( |C| số lượng lớp)
Để mở rộng nút gốc ta sẽ tính độ lợi thơng tin cho từng đặc trưng của văn
bản. Tuy nhiên, trong ví dụ ở phần trên, các thuộc tính của tập mẫu cĩ giá trị rời
rạc, cịn trong tập mẫu ngữ liệu văn bản, các đặc trưng được biểu diễn bằng một
lượng liên tục. Vậy làm thế nào để chọn một giá trị làm giá trị để phân tách tập
ngữ liệu ? Vấn đề này vấn chưa cĩ một lời giải cụ thể. Trong thực tế, người ta vẫn
dùng một giải thuật Heuristic để tìm ra giá trị tối ưu cho từng thuộc tính. Cơng thức
để tính độ lợi thơng tin cho một đặc trưng trong tập ngữ liệu :
Trong đĩ :
G(a,y) : độ lợi thơng tin của đặc trưng a với giá tị phân tách là y.
H(t) : Entropy tại node cha (node đang xét).
pL : tỉ lệ các phần tử được truyền qua node trái.
pR : tỉ lệ các phần tử được truyền qua node phải.
H(tL) : Entropy của node trái.
H(tR) : Entropy của node phải.
Ví dụ, trong tập ngữ liệu trên, ta chọn đặc trưng “cts”, và ta chọn được giá trị
phân tách tối ưu cho đặc trưng này là 2. Khi đĩ, nhánh trái sẽ là nhánh chứa
những văn bản cĩ giá trị =2. Ta
sẽ tính độ lợi thơng tin cho đặc trưng “cts” ứng với giá trị 2 như sau :
Entropy node 1 :
( ) ( ) ( )
Entropy node trái :
26
( ) ( ) ( )
Entropy node phải :
( ) ( ) ( )
Suy ra, độ lợi thơng tin đặc trưng “cst” với giá trị 2 là :
( ) ( ) ( | ) (
)
Tính tương tự cho các đặc trưng cịn lại trong văn bản, ta sẽ thấy rằng độ lợi
thơng tin của “cts” là cao nhất. Do đĩ, “cts” sẽ được chọ làm đặc trưng phân tách
với giá trị là 2. Cây quyết định được hình thành tăng lên như sau :
Lặp lại những bước tính tốn trên cho từng nhánh trái và phải của cây đẻ tiếp
tục phát triển cây cho đến khi các node đều xác định rõ văn bản tại node đĩ thuộc
về lớp nào. Những node chỉ chứa văn bản thuộc về một lớp chính là điều kiện
dừng của thuật tốn và được gọi là node lá hay điều kiện dừng của thuật tốn.
27
Hình 3.4: Một cây quyết định đơn giản
Tuy nhiên, sau khi cây quyết định được xây dựng đầy đủ, chúng ta phải thực
hiện cắt tỉa cây để tránh tình trạng quá khớp cho cây. Tình trạnh quá khớp cĩ thể
hiểu là cây chỉ cĩ thể nhận diện đúng cho tập dữ liệu đĩ cịn đối với những tập
khác sẽ khĩ cĩ thể phân loại đúng. Cĩ 2 phương pháp tiếp cận cho việc cắt tỉa
cây : tỉa trước và tỉa sau.
Tỉa trước : phương pháp tiếp cận ngừng xây dựng cây trước khi nĩ đạt
tới điểm phân loại các dữ liệu huấn luyện.
Tỉa sau : phương pháp tiếp cận sau khi hồn thành cây và sau đĩ tita
cây.
Mặc dầu phương pháp đầu tiên cĩ vẽ chính xác hơn nhưng cách tiếp cận thứ
2 của việc xén sau cho thấy thành hữu dụng hơn trong thực tế. Điều này là do
những khĩ khăn trong tiếp cận đầu tiên của việc ước tính chính xác khi ngừng xây
dựng cây.
Bất chấp của việc lựa chọn phương pháp xén trước hay xén sau, một câu hỏi
đặt ra là tiêu chuẩn nào sẽ được dùng để xác định kích thước cuối cùng của cây.
Một vài cách tiếp cận như : Xén giảm bớt lỗi (reduced-error-pruning, Quinlan
1987) và xén sau (C4.5, Quinlan 1993). Và để đánh giá việc tỉa cây, ta cần cĩ một
bộ ngữ liệu để đánh giá, được gọi là bộ ngữ liệu xác nhận (validation data set). Bộ
28
ngữ liệu này được rút ra từ bộ huấn luyện. Trong thử nghiệm của tác giá với tổng
cộng 9603 bài viết, ơng xử dụng 80% (7681) để huấn luyện và 20% để đánh giá
việc tỉa nhánh.
Xén giảm bớt lỗi : xem xét từng node trên cây và quyết định cho việc
cắt tỉa, cắt một node cây con bao gồm loại bỏ cây con cĩ gốc tại nút đĩ,
làm cho nĩ một node lá và gán nĩ phân lớp phổ biến nhất của các mẫu
huấn luyện liên kết với node đĩ. Các nút chỉ được xén khi kết quả thực
hiện khơng tồi tệ hơn so với bản gốc. Việc cắt được lặp lại, luơn luơn
chọn nút mà sau khi loại bỏ làm tăng độ chính xác cây quyết định. Cắt
tỉa các nút được tiếp tục cho đến khi việc cắt tỉa là cĩ hại (giảm độ
chính xác của cây).
Xén sau : Chuyển đổi việc học cây quyết định thành một tập các quy
tắc tương đương bằng cách tạo ra quy tắc cho từng con đường từ
node gốc đến một node lá. Xén mỗi quy tắc bằng cách loại bỏ bất cứ
điều kiện nào cĩ kết quả làm tăng tính chính xác của cây. Sắp xếp các
quy tắc theo tính chính xác, và xem xét chúng trong khi phân loại cho
các trường hợp tiếp theo.
3.2.3.3 Cross-validation
Trong thực tế, nếu ta chia bộ ngữ liệu huấn luyện làm 2 phần : 80% để huấn
luyện và 20% để xác nhận tỉa cây thì độ chính xác huấn luyện sẽ bị giảm và sự
chính xác trong tỉa cây quyết định cũng khơng đảm bảo. Vì vậy, để tối ưu hố vấn
đề này, người ta thường dùng quá trình Cross-validation.
Cross-validation là quán trình xác nhận chéo. Tức là là khơng chỉ tạo 1 cây
quyết định, mà thực hiện nhiều cây. Mỗi lần ta cũng thực hiện trên bộ ngữ liệu đĩ
nhưng với mỗi 20% khác nhau của bộ ngữ liệu. Cĩ thể hiểu một cách đơn giản là
bộ ngữ liệu gồm 100%. Mỗi lần, ta lấy 80% huấn luyện tạo cây, và 20% để tỉa cây.
Lần khác ta cũng thực hiện như vậy nhưng vớ 20% là những dữ liệu khác trong
bộ ngữ liệu. Vì vậy, ta cĩ thể thực hiện 5 lần huấn luyện (5-fold cross-validation).
Sau khi cĩ được 5 cây quyết định đã được tỉa, ta sẽ tính ra kích thước trung
bình của chúng. Với kích thước này, ta sẽ huấn luyện lại cây với 100% dữ liệu, và
29
xén tỉa cây ho vừa với kích thước trung bình đĩ. Sau cùng chúng ta sẽ thu được
cây quyết định cuối cùng. Quá trình cuối cùng là sử dụng một bộ ngữ liệu test mới
để đánh giá độ chính xác của cây quyết định.
Hình 3.5: Sử dụng tập ngữ liệu trong Cross-validation
3.2.3.4 Giai đoạn ph}n lớp
Từ cây quyết định, chúng ta sẽ rút ra được các luật bằng cách đi từ node gốc
theo một nhánh đến node lá. Các luật sẽ được áp dụng để phân lớp.
3.3 Mơ hình xác xuất Entropy tối đại (Maximum Entropy Modeling)
3.3.1 Entropy
3.3.1.1 Kh|i niệm
Entropy thơng tin là một khái niệm mở rộng của entropy trong nhiệt động lực
học sang cho lý thuyết thơng tin (Claude E. Shannon, 1948)
Entropy là một đại lượng dùng để đo lượng thtin khơng chắc chắn
(uncertaincy) của một biến cố hay một phân phối ngẫu nhiên cho trước.
Ví dụ :
Một dịng chữ luơn chỉ cĩ các ký tự "a" sẽ cĩ entropy bằng 0, vì ký tự
tiếp theo sẽ luơn là "a".
Một dịng chữ chỉ cĩ hai ký tự 0 và 1 ngẫu nhiên hồn tồn sẽ cĩ
entropy là 1 bit cho mỗi ký tự.
30
3.3.1.2 Entropy của biến ngẫu nhiên
Entropy của một biến ngẫu nhiên X cũng là giá trị mong đợi của các độ ngạc
nhiên của các giá trị mà X cĩ thể nhận.
Xét một biến ngẫu nhiên X cĩ phân phối :
Cơng thức tính Entropy của X :
Nhận xét :
Một phân phối xác suất càng lệch nhiều (cĩ xác xuất rất nhỏ và rất lớn)
thì tính khơng chắc chắn càng nhỏ entropy càng thấp
Một phân phối xác suất càng đều thì tính khơng chắc chắn càng lớn =>
entropy càng cao
Định lý cực đại của Entropy :
Ta cĩ : H(p1,p2,…,pM)<=log(M)
Trong đĩ : đẳng thức xảy ra khi và chỉ khi p1=p2=…=pM=1/M, khi đĩ entropy
đạt giá trị cực đại.
3.3.2 Áp dụng vào phân loại văn bản
3.3.2.1 Biểu diễn văn bản
Để biểu diễn văn bản, chúng ta vẫn sử dụng phương pháp đã được trình bày
ở trên. Trong thì nghiệm này, tác giả vẫn biểu diễn văn bản bằng một vector với
20 chiều là 20 từ cĩ độ đo 2 cao nhất, mỗi chiều là trọng số của từ đĩ được đo
bằng độ đo tf.idf
( )
31
3.3.2.2 H{m đặc trưng v{ r{ng buộc
Trong mơ hình Maximum Entropy, chúng ta sử dụng dữ liệu huấn luyện để tạo
các ràng buộc. Mỗi ràng buộc biểu diễn một đặc tính của dữ liệu huấn luyện. Mỗi
ràng buộc được định nghĩa bằng một hàm đặc trưng. Dạng chung của hàm đặc
trưng như sau :
( ) {
Trong nhiệm vụ phân loại này, chúng ta định nghĩa hàm đặc trưng trên cặp giá
trị ( ), với là vector biểu diễn một văn bản trong tập huấn luyện và c là một giá
trị trong tập phân lớp C.
( ) {
Trong đĩ : wij là trọng số của từ thứ i trong văn bản j.
Ở đây chúng ta sử dụng hàm đặ trưng nhị phân thể hiện sự cĩ hay khơng cĩ
của từ trong văn bản. Tuy nhiên, chúng ta cĩ thể sử dụng hàm đặc trưng thể hiện
độ lớn của trọng số.
3.3.2.3 Một số kí hiệu :
S : tập huấn luyện
̃( ) : xác suất thực nghiệm của x trong tập S
( ) : xác suất của x
̃ : giá trị kì vọng thực nghiệm của đặc trưng
: giá trị kì vọng của đặc trưng
3.3.2.4 Mơ hình
Cĩ nhiều mơ hình khác nhau cho việc phân lớp bằng Entropy cực đại. Ở đây,
chúng ta sẽ sử dụng mơ hình Loglinear cĩ cơng thức như sau :
( ⃗ )
∏
( ⃗ )
Trong đĩ :
K : số lượng hàm đặc trưng đặc.
32
: trọng số (giá trị) của hàm đặc trưng
: là hằng số chuẩn hố
Vấn đề của mơ hình là xác định các trọng số tối ưu và dùng chúng để
phân lớp. Trong trường hợp đơn giản nhất, để phân lớp cho một văn bản mới,
dựa vào bộ đã huấn luyện, chúng ta tính ( ) và ( ). Sau đĩ
chúng ta sẽ chọn lớp cĩ xác suất lớn hơn làm phân lớp cho xnew.
3.3.2.5 Thủ tục huấn luyện Generalized iterative scaling
Generalized iterative scaling (GIS) là một thủ tục để tìm kiếm phân bố xác
suất p sao cho entropy đạt giá trị cực đại của dạng mơ hình LogLinear. Mục chính
của giải thuật là tìm ra bộ trọng số tối ưu sao cho thoả tập ràng buộc :
̃
Trong đĩ, giá trị kì vọng được định nghĩa như sau :
∑ ( ⃗ ) ( ⃗ )
⃗⃗⃗
Cơng thức tính xấp xỉ như sau :
∑∑ ( | ⃗ ) ( ⃗ )
Trong đĩ,
( | ⃗ )
(∑ ( ⃗ ) )
∑ (∑ ( ⃗ ) )
Và giá trị kì vọng thực nghiệm được định nghĩa như sau :
̃ ∑ ̃( ⃗ ) ( ⃗ )
⃗⃗⃗
∑ ( ⃗ )
Trong đĩ, N là số văn bản trong tập huấn luyện. Chú ý rằng hai giá trị kì vọng
của các hàm đặc trưng này khơng phải là giá trị nhị phân, mà là giá trị thực để đo
khả năng của các ràng buộc.
Thuật giải địi hỏi tổng giá trị của các hàm đặc trưng ứng với mỗi vector và
mỗi lớp c phải là một hằng số C.
33
⃗ ∑ ( ⃗ )
Để hồ thành yêu cầu này, chúng ta định nghĩa C là giá trị lớn của các giá trị
của các hàm đặc trưng
⃗
∑ ( ⃗⃗⃗ )
Tuy nhiên, khơng phải tất cả các tổng giá trị các hàm đặc trưng đều bằng
hằng số C, do đĩ, chúng ta add thêm vào tập các hàm đặc trưng một hàm đặc
trưng như sau :
( ⃗ ) ∑ ( ⃗ )
Thủ tục huấn luyện được thực hiện như sau :
1. Khởi tạo tập trọng số {
( )
} ( với 1 i K+1, và (1) là tập trọng số thứ 1
ứng với lần khởi tạo và sẽ tăng dần lên ứng với từng lần lặp). Cĩ thể
khởi tạo với bất kì giá trị nào, tuy nhiên thường chúng ta sẽ khởi tạo với
giá trị 1, tức là {
( )
}.
Tính giá trị kì vọng thực nghiệm của các hàm đặc trưng ̃
Khởi tạo n=1.
2. Tính xác suất cho từng vector văn bản với từng lớp trong tập phân lớp
( )( ⃗ ), sử dụng tập trọng số i tại thời điểm đang xét và tính theo
cơng thức :
( )( ⃗ )
∏.
( )/
( )
3. Tính giá trị kì vọng (với 1 i K+1) cho các hàm đặc trưng theo
cơng thức xấp xỉ đã trình bày ở trên
34
∑∑ ( | ⃗ ) ( ⃗ )
4. Cập nhật giá trị cho tập trọng số i
( )
(
̃
( )
)
5. Nếu các trọng số đã hội tụ thì dừng chương trình, ngược lại tăng n lên 1
và quay lại bước 2.
Kết quả sau khi chạy giải thuật là tập các trọng số I .
3.3.2.6 Giai đoạn ph}n lớp
Cho một vector văn bản mới ( ).
Sử dụng tập mơ hình trọng số đã huấn luyện, tín hai xác suất P(c| ) và
P(c| ) theo cơng thức :
( | ⃗ )
(∑ ( ⃗ ) )
∑ (∑ ( ⃗ ) )
Sau khi tính hai xác suất, lớp nào cĩ xác suất cao hơn sẽ là lớp cho văn bản
mới.
35
5. Tài liệu tham khảo
[1] Christopher D.Manning, Hinrich Schutze, Foundations of Statistical
Natural Language Processing, 1999, The MIT Press.
[2] Hồ Văn Quân, Khoa CNTT, ĐH Bách Khoa TPHCM, Bài Giảng Lý Thuyết
Thơng Tin.
[3] Kostas Fragos, Yannis Maistros, Christos Skourlas, A Weighted
Maximum Entropy Language Model for Text Classification.
[4] Kamal Nigam, John Laerty, Andrew McCallum, Using Maximum Entropy
for Text Classication.
…
Các file đính kèm theo tài liệu này:
- text_categorization.pdf