ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
o0o
BÁO CÁO TIỂU LUẬN
KHAI PHÁ DỮ LIỆU
ĐỀ TÀI:
PHÂN LỚP VĂN BẢN
Bộ Môn : KHAI PHÁ DỮ LIỆU
Giảng viên : PGS-TS ĐỖ PHÚC
Học viên : NGUYỄN NGỌC TÚ
Mã Số Học Viên : CH1101053
Lớp : CH CNTTQM - 06
TP. Hồ Chí Minh, tháng 11 năm 2012
Lời nói đầu
Trong sự phát triển không ngừng của xã hội ngày nay, cùng với sự bùng nổ mạnh mẽ của
Internet thì mọi thông tin, giai dịch và trao đổi đều được số hóa. Trong đó, văn bản là một
hình thức lưu trữ thông tin phổ biến nhất hiện nay. Vì vậy mà lượng văn bản được lưu trữ
trong các cơ sở dữ liệu cũng như trên Internet hiện nay là một kho dữ liệu khổng lồ. Cùng
với sự phát triển đó là nhu cầu tìm kiếm dữ liệu của con người ngày càng phát triển. Vì thế
việc hỗ trợ tìm kiếm, thu thập thông tin, văn bản với nội dung chính xác, nhanh chóng là
nhu cầu cần thiết hiện nay cho người sử dụng máy tính cũng như Internet.
Vì vậy, vấn đề phân loại văn bản hiện nay là một nhu cầu cần thiết nhằm cung cấp cho
người sử dụng một công cụ giúp cho việc tìm kiếm chính xác hơn, nhanh chóng hơn.
Lời cảm ơn
Tôi xin chân thành cảm ơn sự giúp đỡ nhiệt tình của thầy PGS.TS ĐỖ PHÚC trong suốt
thời gian học cũng như quá trình làm đồ án môn học:”KHAI PHÁ DỮ LIỆU”, và cũng xin
cảm ơn các bạn trong khoa đã có nhiều đóng góp để tôi hoàn thành môn học này. Tuy
nhiên do thời gian hạn hẹp, và sự hiểu biết của chúng em về môn học này chưa được sâu,
cho nên đề tài vẫn còn nhiều thiếu sót, nhiều vấn đề chưa được giải quyết hoàn chỉnh và
phù hợp với thực tế hiện nay. Vì vậy, tôi mong nhận được sự đóng góp của thầy và các bạn
để chương trình được hoàn thiện hơn.

với nó nhất theo hướng tiếp cận text data mining.
B.HƯỚNG TIẾP CẬN VÀ PHƯƠNG PHÁP XỬ LÝ
I. Phương pháp biểu diễn văn bản
Vấn đề lớn nhất đối với dữ liệu văn bản, cũng như đối với bất kỳ kiểu
dữ liệu nào khác, đó là việc tìm kiếm một sự biểu diễn thích hợp, hay một mô
hình cho những dữ liệu đang tồn tại, với những tài nguyên hiện hữu trong một
thời gian hữu hạn. Cho nên, hiệu năng của mô hình yêu cầu cả chất lượng lẫn
tốc độ.
1. Mô hình biểu diễn văn bản
Hầu hêt phần lớn các tiếp cận trong lĩnh vực khai khoáng văn bản khai thác
dữ liệu văn bản đều xem văn bản được đặc trưng bởi một tập hợp từ vựng.Cách
tiếp cận này thường được gọi là mã hóa kiểu “gói từ” (bag of words), bỏ qua
trật tự của từ và những thông tin về cấu trúc câu, nhưng ghi nhận lại số lần mỗi
từ xuất hiện
Mã hóa như vậy thực ra đã làm đơn giản hóa rất nhiều thông tin phong phú
được thể hiện trong văn bản, cách làm này đơn thuần chỉ là sự thống kê từ
vựng hơn là sự mô tả trung thực nội dung. Việc phát triển những mô hình tốt
hơn nhưng vẫn khả thi về tính toán và cho phép đánh giá được dữ liệu trên thực
tế vẫn còn là một vấn đề thách thức.
Mặc dù độ phức tạp chỉ dừng lại ở cấp độ từ vựng của ngôn ngữ nhưng việc
mã hóa dựa trên từ vựng vẫn tạm được xem là có khả năng cung cấp một tượng
thông tin ít nhiều thích đáng về những mối kết hợp giữa từ vựng và văn bản, có
thể trong chừng mực nào đó đủ cho việc gom nhóm theo chủ đề cũng như việc
tìm kiếm thông tin từ những cơ sở dữ liệu lớn.
2. Mô hình không gian vector (Vector Space Model)
Mô hình này biểu diễn văn bản như những điểm (hay những vector) trong
không gian Euclide t-chiều, mỗi chiều tương ứng với một từ trong vốn từ vựng.
Thành phần thứ i, là di, của vector văn bản cho biết số lần mà từ vị có chỉ mục i
xuất hiện trong văn bản. Hơn nữa, mỗi từ có thể có một trọng số tương ứng để
mô tả sự quan trọng của nó. Sự tương tự giữa hai văn bản được định nghĩa hoặc

}: với t
i
là một từ đặc trưng, nếu nó xuất hiện ít
nhất trong 3 văn bản
• d
j
= {w
1j
,w
2j
…w
mj
}: với w
ij
là trọng số giữa từ đặc trưng t
i
và
văn bản d
j
.
3. Gom nhóm từ vựng
Trong khi xem xét ngữ nghĩa của một văn bản người ta cảm thấy rằng dường
như là một số từ thể hiện ngữ nghĩa nhiều hơn là những từ khác. Hơn nữa, có
sự phân biệt cơ bản giữa những từ ngữ chức năng và những từ ngữ mang nội
dung, trong đó có một số từ ngữ mang nội dung dường như thể hiện nhiều về
các chủ đề hơn những từ khác.
Bất kể phương pháp nào được dùng để giảm chiều hay để suy ra những chiều
tiềm ẩn, việc gán trọng số cho từ vựng chỉ cần đòi hỏi miễn sao nguyên tắc gán
trọng số có thể diễn giải được tốt về tầm quan trọng của từ vựng đối với việc
biểu diễn văn bản. Trọng số có thể dựa trên mô hình phân bố từ, chẳng hạn như

Trong lĩnh vực khai khoáng văn bản hầu như cho đến nay đều sử dụng những
phương pháp tiền xử lý khá đơn giản trong việc loại bỏ dữ liệu dữ thừa và chọn
lựa đặc trưng. Trong các thực nghiệm như vậy, những tiêu đề văn bản, những
chữ số, công thức, và tất cả những ký hiệu phi ngôn ngữ đều bị loại bỏ. Văn
bản được xem là đặc trưng bởi một tập hợp các từ vựng có tần số tuyệt đối lớn,
những từ ít xuất hiện bị loại bỏ theo một tần số ngưỡng nào đó (thông thường
sẽ chọn ngưỡng trong khoảng từ 5% - 60% tùy vào từng trường hợp cụ thể).
7
II. GIẢI QUYẾT VẤN ĐỀ
1. Biều diễn tài liệu
Mô hình không gian vector dựa trên số học tuyến tính và xem các tài liệu, các
câu truy vấn như các vector có nhiều chiều, Mỗi chiều của vector có giá trị số
biểu thị sự tồn tại và tần suất xuất hiện của các từ vựng trong các tài liệu tương
ứng hoặc trong toàn bộ tập tài liệu. Để biểu diễn tất cả tài liệu trong cùng một
từ vựng( n vị từ trong cùng một không gian vector), ta phải rút tất cả toàn bộ
các từ vựng tìm thấy trong mọi tài liệu để hình thành một không gian vector
chung.
Đặt n là kích thước của tập các thuật ngữ, và n là kích thước của tập các tài
liệu. Khi đó tất cả các tài liệu Di ( i = 1,2,…,t) có thể được thể hiện thành các
vector n chiều:
Di = [ a
i1
, a
i2
, a
i3 ,
……., a
i n
]
Trong đó, các hệ số a

6
: Image Models Sample
• Tập các từ vựng xuất hiện trong tập tài liệu: The,
Sample, Project, Code, Site, Contents, of, Word, Document,
Templates, Problems, Trigonometric, Functions, Washington, Models.
Tập từ vựng gồm 15 từ, như vậy không gian vector sẽ có 15 chiều. Trong ví
dụ này, nếu từ vựng có xuất hiện nhiều lần thì hệ số tương ứng trong tài
liệu đó vẫn được tính là 1, ngược lại 0.
Ta thấy từ “Code” xuất hiện trong tài liệu thứ nhất và trong tập từ vựng
chung, từ này ở vị trí thứ tư, nên trong vector thứ nhất vị trí thứ 4 có giá trị là 1.
8
“Code” cũng xuất hiện trong tài liệu thứ 3, nên vị trí thứ tư của vector thứ 3
cũng có giá trị là 1. Tương tự ta tính cho các phần tử khác. Như vậy, ma trận
thuật ngữ tài liệu được hình thành như sau:
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 1 1 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 1 1 1 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 1 1
Ma trận thuật ngữ - tài liệu
Các điểm mạnh và yếu của mô hình
Ưu điểm của mô hình:
Nền tảng mô hình là số học tuyến tính: sau khi chuyển đổi các tài liệu thành
các vector, ta có thể thực hiện các thao tác toán học trên đó một cách dễ dàng,
và các công thức toán học áp dụng trên vector là rất phổ biến.
Có thể dùng các cấu trúc dữ liệu đơn giản, hiệu quả để lưu trữ dữ liệu: ví dụ
như có thể lưu trữ các vector bằng cấu trúc mảng. Tuy nhiên, thường các
vector khá thưa, nghĩa là hầu hết các chiều của vector là 0 ( khi xét một tập rất
lớn các tài liệu, chưa đựng nhiều từ). Các phương pháp lưu trữ và xử lý đặc

- Tiến hành loại bỏ tất cả những “tag” của HTML trong file văn bản,
chuyển tất cả chúng về các file dưới dạng TXT, để chuẩn bị cho giai đoạn
trích đặc trưng và mã hóa văn bản.
10
*.HTML
Chuyển đổi về dạng font chữ đồng nhất
*.HTML
Loại bỏ những <tag> html, lấy nội dung
*.TXT
Mô tả bước tiền xử lý
b. Rút trích đặc trưng
Có rất nhiều phương pháp chọn đặc trưng để mã hóa cho văn bản, như
những phương pháp chọn đặc trưng là từ vựng (đơn, ghép), những phương
pháp tìm cụm từ phổ biến, phương pháp dùng ngữ đoạn( trong tiếng việt) để
làm đặc trưng cho văn bản, và một số phương khác.
Giai đoạn này đóng vai trò hết sức quan trọng trong tiến trình khám phá tri
thức. Tùy vào việc chúng ta lựa chọn cách lấy đực trưng nào để đảm bảo tính
hiệu quả cho bài toán( giải quyết ở phần sau).
Dưới đây ta dùng phương pháp cơ bản chỉ lựa chọn đặc trưng là từ và loại
bỏ những “stop word”( dùng trong tiếng anh).
11
*.TXT
Rút trích những từ trong file và loại bỏ những từ “stop word ”
Tập các thuật ngữ( từ vựng) rút được
Loại bỏ những từ vựng tầm thường( thường dùng ngưỡng > 60% và < 5%)
Tập những từ vựng tầm thường
Tập những từ vựng dùng để mã hóa
c. Gán trọng số cho tài liệu
Như phân tích ở phần III.1 ta thấy các giá trị tại các vị trí thành phàn của
vector thể hiện sự tồn tại của thuật ngữ tương ứng trong tài liệu. Các giá trị

i j
) * log n/ df
i.
Công thức này gán trọng số cực đại cho những từ chỉ xuất hiện trong
một văn bản duy nhất.
Vì trọng số của từ vựng trong mô hình không gian vector ảnh hưởng trực
tiếp đến khoảng cách giữa các văn bản, do vậy các kết quả cụ thể phụ thuộc
chủ yếu vào phương pháp gán trọng số.

Những công thức gán trọng số toàn cục nói trên chỉ nhằm mô tả tầm quan
trọng của một từ bất kể ngữ cảnh riêng của nó, chẳng hạn như những từ lân
cận hay vị trí của từ trong cấu trúc văn bản. Thông tin về cấu trúc của văn bản
cũng chưa được tận dụng, ví dụ như nhấn mạnh lên những từ tiêu đề hay
những từ xuất hiện đầu văn bản.
3. Độ tương tự của các tài liệu
Giải quyết cho vấn đề tìm kiếm những văn bản có nội dung giống nhau là
quá trình mô tả việc xử lý ban đầu của các phương pháp phân nhóm tài liệu
trong một tập tài liệu ban đầu. Nhân tố góp phần cho sự thành công của giải
thuật gom nhóm tài liệu là đo độ tương tự giữa hai văn bản( mô hình đại
diện).
Độ tương tự của các tài liệu: Có thể thực hiện đo độ tương tự bằng nhiều
cách, cách tiếp cận phổ biến là đo độ tương tự giữa hai vector nhiều chiều.
Sử dụng mô hình không gian vector, ta có thể dể dàng tính toán sự tương
quan giữa các tài liệu bằng cách tính giá trị tương tự( khoảng cách) giữa các
vector thể hiện các tài liệu đó. Tính toán độ tương tự giữa hai vector t chiều là
một bài toán phổ biến, có thể thực hiện bằng nhiều cách, ta sẽ áp dụng một số
phương pháp tính độ tương tự giữa hai vector nhiều chiều.
Cách tính khoảng cách phổ biến là họ khoảng cách Minkowski có các
phương pháp đo độ tương tự giữa hai vector :
13

- Để lưu trữ tập hợp các từ vựng ( không gian vector thuât ngữ): dùng
mảng( array) một chiều ( size = 300) để lưu 300 từ vựng chung( có thể
ít hoặc nhiều hơn).
- Biểu diễn vector đặc trưng( một văn bản): dùng cấu trúc dữ liệu bảng
băm ( hashTable) chỉ để lưu trữ những từ vựng có tồn tại trong “không
gian vector thuât ngữ” và có trong văn bản đó( những từ không có ta
sẽ không lưu trữ), một thành phần của giá trị băm gồm 2 miền:
o Nội dung của từ( String Word ): giá trị để băm tới.
o Trọng số của từ( double termWeighting!= 0), nếu như từ có
trong “không gian vector thuât ngữ”( 300 từ chung) mà không
có trong vector này thì sẽ cho giá trị là 0.
( Có thể dùng các cấu trúc dữ liệu khác với tính chất tương tự)
Ánh xạ mảng hai chiều( ma trận thuật ngữ - tài liệu) bằng một mảng 1 chiều (
size = n văn bản) với mỗi phần tử của mảng là một vector đặc trưng có cấu
trúc như trên.
2. Mã hóa văn bản
B1:Xử lý lấy nội dung( body) của file *.HTML chuẩn hóa về dạng
chuẩn sau đó lưu vào file *.TXT
B2:Từ n văn bản có n file *.TXT ta sẽ lọc bỏ các “ stop word” . Từ tổng
số từ còn lại ta tính tần xuất xuất hiện của mỗi loại từ có trong tổng các từ
chung đó để loại bỏ bớt những tập từ vựng tầm thường, lọc lấy những từ còn
lại để mã hóa ( ngưỡng để lọc bỏ > 60% và < 5% tùy vào điều kiện mà chọn
ngưỡng cụ thể).
Ta có thể định nghĩa các stop word như sau: ( tuỳ vào tập stop word
định nghĩa khác nhau)
15
already
although
always
among

necessarily
neither
next
none
nor
normally
not
noted
said
same
seem
seen
several
shall
should
show
showed
shown
shows
significantly
similar
similarly
slightly
so
sometime
somewhat
soon
specifically
state
16

perhaps
please
poorly
possible
possibly
potentially
predominantly
present
previously
primarily
probably
prompt
states
strongly
substantially
successfully
sufficiently
their
theirs
them
they
though
through
throughout
too
toward
unless
until
use
used

respectively
resulted
resulting
results
usually
various
very
was
were
what
while
who
whose
why
widely
will
would
yet
B3: Gán trọng số cho tập tài liệu: Chọn phương pháp gán trọng số tf-idf
Có thể chọn một trong 2 công thức này để gán trọng số cho mỗi từ trong vector
đặc trưng của mỗi văn bản.
CT1: W
i j
= tf
i j
* log
n
( n / df
i
)

Về việc biểu diễn dữ liệu đã khắc phục được tình trạng vector khá thưa,
nghĩa là hầu hết các chiều của vector là 0 ( khi xét một tập rất lớn các tài liệu,
chứa đựng nhiều từ). Giảm thiểu thời gian tính toán và vùng nhớ (sẽ không
lưu và đánh trọng số cho những từ không có trong văn bản).
Ở giai đoạn tiền xử lý đã loại bỏ được nhiều từ mang ý nghĩa không
cần thiết( loại các stop word) và đã chọn ngưỡng để loại bớt những từ quá
đặc biệt hay tầm thường để trích chọn được những từ cần thiết cho việc mã
hóa. Tuy nhiên việc trích chọn đặc trưng theo từ vựng đem lại hiệu quả
không cao( đặc biệt là trong tiếng việt). Bỏ xót nhiều yếu tố quan trọng trong
1 văn bản như nhấn mạnh lên những từ tiêu đề hay những từ xuất hiện đầu
văn bản. Và khuyết điểm nữa là chưa xây dựng được một từ điến lĩnh
vực( domain dictionary) để hạn chế được việc thay đổi về hình thái học của
từ trong tiếng Anh và những từ đồng nghĩa…( điều này là rất quan trọng
mang lại tính đúng đắng cho chương trình).
Việc sử dụng phương pháp đánh trọng số tf – idf đã khắc phục được
tình trạng thông tin lưu trữ trong cấu trúc của tài liệu bị thiếu hụt: trong mô
hình không gian vector cơ bản, chỉ có sự tồn tại của thuật ngữ trong tài liệu là
quan trọng, còn thứ tự xuất hiện và số lần xuất hiện lại không được nhắc tới,
dẫn đến bỏ qua nhiều yếu tố quan trọng gây mất nhiều thông tin để tìm đặc
trưng cho từ.
Việc xác định hai văn bản có nội dung gần giống nhau bằng phương
pháp tính khoảng cách giữa 2 vector bằng công thức Euclide là khá phổ biến
và mang lại hiệu quả cao.
Nhưng điều quan trọng ở đây là để xác định được các văn bản có nội
dung giống nhau hay không có đúng theo yêu cầu của ta hay không thì cái
chính này nằm ở giai đoạn tiền xử lý văn bản và trích chọn đực trưng, để hệ
thống mang lại hiệu quả cao thì xử lý ở giai đoạn này phải tốt.
20
C. GIAO DIỆN
Hình 1: Giao diện chính của chương trình