TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA: CÔNG NGHỆ THÔNG TIN
BÀI TẬP LỚN
MÔN: KHAI PHÁ DỮ LIỆU
ĐỀ TÀI: NGHIÊN CỨU GIẢI THUẬT GOM CỤM CLARA
VÀ ỨNG DỤNG TRONG GOM CỤM VĂN BẢN
GVHD: Bùi Thanh Hùng
LỚP: KTPM2 – K6
NHÓM:
• Nguyễn Trường Sơn
• Đỗ Văn Huy
Hà Nội, Tháng 5/2015
LỜI CẢM ƠN
Để hoàn thành đề tài này, chúng em xin được gửi lời cảm ơn tới những
người bạn đã góp ý và giúp đỡ nhóm, và đặc biệt là cảm ơn thầy Bùi Thanh
Hùng, người đã tận tình hướng dẫn và chỉ bảo chúng em xác định được những yêu
cầu và mục tiêu đề tài, truyền dạy các kĩ năng cũng như hướng dẫn cho chúng em,
từ phong cách báo cáo đến cách thức thực hiện đề tài. Với vốn kiến thức thu được
trong quá trình thực hiện bài tập này, không chỉ là nền tảng cho quá trình nghiên
cứu mà còn là hành trang quý báu để chúng bước vào cuộc sống một cách tự tin và
vững chắc. Rất mong rằng thầy và các bạn vẫn tiếp tục đồng hành cùng nhóm
chúng em và những lời góp ý và nhận xét nhiều hơn nữa để nhóm có thể tiếp tục
hoàn thiện đề tài của mình ngày một tốt hơn.
Một lần nữa chúng em kính chúc quý thầy cô dồi dào sức khỏe và thành
công trong sự nghiệp trồng người cao quý.
Trân trọng cảm ơn !
Nhóm thực hiện
Nguyễn Trường Sơn
Đỗ Văn Huy
2
MỤC LỤC

thông tin với yêu cầu chất lượng ngày càng cao cho người làm quyết định trong
các tổ chức chính phủ, tài chính, thương mại, khoa học,…
Đúng như John Naisbett đã cảnh báo “Chúng ta đang chìm ngập trong dữ
liệu mà vẫn đói tri thức”. Lượng dữ liệu khổng lồ này thực sự là một nguồn tài
nguyên có nhiều giá trị bởi thông tin là yếu tố then chốt phục vụ cho mọi hoạt động
quản lý, kinh doanh, phát triển sản xuất và dịch vụ, … nó giúp người điều hành và
quản lý có những hiểu biết về môi trường và tiến trình hoạt động của tổ chức mình
trước khi ra quyết định để tác động đến quá trình hoạt động nhằm đạt được các
mục tiêu một cách hiệu quả và bền vững.
Khai phá dữ liệu là một lĩnh vực mới được nghiên cứu, nhằm tự động khai
thác thông tin, tri thức mới hữu ích, tiềm ẩn từ những Cơ sở dữ liệu lớn cho các
đơn vị, tổ chức, doanh nghiệp,…. từ đó làm thúc đẩy khả năng sản xuất, kinh
doanh, cạnh tranh cho các đơn vị, tổ chức này. Các kết quả nghiên cứu khoa học
cùng những ứng dụng thành công trong Khám phá tri thức cho thấy Khai phá dữ
liệu là một lĩnh vực phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển
vọng, đồng thời có ưu thế hơn hẵn so với các công cụ tìm kiếm phân tích dữ liệu
truyền thống. Hiện nay, Khai phá dữ liệu đã ứng dụng ngày càng rộng rãi trong các
lĩnh vực như thương mại, tài chính, y học, viễn thông, tin – sinh,….
Các kỹ thuật chính được áp dụng trong lĩnh vực Khai phá dữ liệu phần lớn
được thừa kế từ lĩnh vực Cơ sở dữ liệu, học máy, trí tuệ nhân tạo, lý thuyết thông
tin, xác suất thống kê và tính toán hiệu năng cao,
Khám phá tri thức là mục tiêu chính của Khai phá dữ liệu, do vậy hai khái
niệm Khai phá dữ liệu và Khám phá tri thức được các nhà khoa học trên hai lĩnh
vực xem là tương đương với nhau. Thế nhưng nếu phân chia một cách chi tiết thì
Khai phá dữ liệu là một bước chính trong quá trình Khám phá tri thức.
5
2. Quá trình khám phá tri thức
Quá trình khá phá tri thức có thể chia thành 5 bước như sau:
Đánh giá,
biểu diễn

dạng thuận lợi nhất nhằm phục vụ quá trình khai phá ở bước sau.
Khai phá dữ liệu: Đây là bước áp dụng những kỹ thuật phân tích (như các kỹ
thuật của học máy) nhằm để khai thác dữ liệu, trích chọn được những mẫu thông
tin, những mối liên hệ đặc biệt trong dữ liệu. Đây được xem là bước quan trọng và
tốn nhiều thời gian nhất của toàn quá trình Khám phá tri thức.
Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ
liệu đã được khám phá ở bước trên được biến đổi và biểu diễn ở một dạng gần gũi
với người sử dụng như đồ thị, cây, bảng biểu, luật, Đồng thời bước này cũng
đánh giá những tri thức khám phá được theo những tiêu chí nhất định.
3. Khai phá dữ liệu và các lĩnh vực liên quan
Khai phá dữ liệu là một lĩnh vực liên quan tới thống kê, học máy, Cơ sở dữ
liệu, thuật toán, tính toán song song, thu nhận tri thức từ hệ chuyên gia và dữ liệu
trừu tượng. Đặc trưng của hệ thống khám phá tri thức là nhờ vào các phương pháp,
thuật toán và kỹ thuật từ những lĩnh vực khác nhau để Khai phá dữ liệu.
Lĩnh vực học máy và nhận dạng mẫu trong Khám phá tri thức nghiên cứu
các lý thuyết và thuật toán của hệ thống để trích ra các mẫu và mô hình từ dữ liệu
lớn. Khám phá tri thức tập trung vào việc mở rộng các lý thuyết và thuật toán cho
các vấn đề tìm ra các mẫu đặc biệt (hữu ích hoặc có thể rút ra tri thức quan trọng)
trong Cơ sở dữ liệu lớn.
Ngoài ra, Khám phá tri thức có nhiều điểm chung với thống kê, đặc biệt là
phân tích dữ liệu thăm dò (Exploratory Data Analysis - EDA). Hệ thống Khám phá
tri thức thường gắn những thủ tục thống kê cho mô hình dữ liệu và tiến trình nhiễu
trong khám phá tri thức nói chung.
Một lĩnh vực liên quan khác là phân tích kho dữ liệu. Phương pháp phổ biến
để phân tích kho dữ liệu là OLAP (On-Line Analytical Processing). Các công cụ
OLAP tập trung vào phân tích dữ liệu đa chiều.
7
4. Các kỹ thuật áp dụng trong khai phá dữ liệu
Khám phá tri thức là một lĩnh vực liên ngành, bao gồm: Tổ chức dữ liệu, học
máy, trí tuệ nhân tạo và các khoa học khác. Sự kết hợp này có thể được diễn tả như

Phân cụm: Xếp các đối tượng theo từng cụm dữ liệu tự nhiên. Phân cụm còn
được gọi là học không có giám sát.
Mô tả và tóm tắt khái niệm: Thiên về mô tả, tổng hợp và tóm tắt khái niệm,
ví dụ như tóm tắt văn bản.
Do Khai phá dữ liệu được ứng dụng rộng rãi nên nó có thể làm việc với rất
nhiều kiểu dữ liệu khác nhau. Sau đây là một số dạng dữ liệu điển hình: Dữ liệu
quan hệ, dữ liệu đa chiều, dữ liệu dạng giao dịch, dữ liệu quan hệ - hướng đối
tượng, dữ liệu không gian và thời gian, dữ liệu chuỗi thời gian, dữ liệu đa phương
tiện, dữ liệu văn bản và Web,…
5. Những chức năng chính của khai phá dữ liệu
Hai mục tiêu chính của Khai phá dữ liệu là mô tả và dự báo. Dự báo là dùng
một số biến hoặc trường trong Cơ sở dữ liệu để dự đoán ra các giá trị chưa biết
hoặc sẽ có của các biến quan trọng khác. Việc mô tả tập trung vào tìm kiếm các
mẫu mà con người có thể hiểu được để mô tả dữ liệu. Trong lĩnh vực Khám phá tri
thức, mô tả được quan tâm nhiều hơn dự báo, nó ngược với các ứng dụng học máy
và nhận dạng mẫu mà trong đó việc dự báo thường là mục tiêu chính. Trên cơ sở
mục tiêu chính của Khai phá dữ liệu, các chức năng chính của Khám phá tri thức
gồm:
Mô tả lớp và khái niệm: Dữ liệu có thể được kết hợp trong lớp và khái
niệm. Thí dụ, trong kho dữ liệu bán hàng thiết bị tin học, các lớp mặt hàng bao
gồm máy tính, máy in,…và khái niệm khách hàng bao gồm khách hàng mua sỉ và
khách mua lẻ. Việc mô tả lớp và khái niệm là rất hữu ích cho giai đoạn tổng hợp,
9
tóm lược và chính xác hoá. Mô tả lớp và khái niệm được bắt nguồn từ đặc trưng
hoá dữ liệu và phân biệt dữ liệu. Đặc trưng hoá dữ liệu là quá trình tổng hợp những
đặc tính hoặc các thành phần chung của một lớp dữ liệu mục tiêu. Phân biệt dữ liệu
là so sánh lớp dữ liệu mục tiêu với những lớp dữ liệu đối chiếu khác. Lớp dữ liệu
mục tiêu và các lớp đối chiếu là do người dùng chỉ ra và tương ứng với các đối
tượng dữ liệu nhận được nhờ truy vấn.
Phân tích sự kết hợp: Phân tích sự kết hợp là khám phá các luật kết hợp thể

trong suốt quá trình huấn luyện dữ liệu, nó phân cụm có thể được sử dụng để đưa
ra nhãn của lớp. Sự phân cụm thực hiện nhóm các đối tượng dữ liệu theo nguyên
tắc: Các đối tượng trong cùng một nhóm thì giống nhau hơn các đối tượng khác
nhóm. Mỗi cụm được tạo thành có thể được xem như một lớp các đối tượng mà
các luật được lấy ra từ đó. Dạng của cụm được hình thành theo một cấu trúc phân
cấp của các lớp mà mỗi lớp là một nhóm các sự kiện tương tự nhau.
Phân tích các đối tượng ngoài cuộc: Một Cơ sở dữ liệu có thể chứa các đối
tượng không tuân theo mô hình dữ liệu. Các đối tượng như vậy gọi là đối tượng
10
ngoài cuộc. Hầu hết các phương pháp Khai phá dữ liệu đều coi các đối tượng ngoài
cuộc là nhiễu và loại bỏ chúng. Tuy nhiên trong một số ứng dụng, chẳng hạn như
phát hiện nhiễu, thì sự kiện hiếm khi xảy ra lại được chú ý hơn những gì thường
xuyên gặp phải. Sự phân tích dữ liệu ngoài cuộc được coi như là sự khai phá các
đối tượng ngoài cuộc. Một số phương pháp được sử dụng để phát hiện đối tượng
ngoài cuộc: sử dụng các test mang tính thống kê trên cơ sở một phân phối dữ liệu
hay một mô hình xác suất cho dữ liệu, dùng các độ đo khoảng cách mà theo đó các
đối tượng có một khoảng cách đáng kể đến cụm bất kì khác được coi là đối tượng
ngoài cuộc, dùng các phương pháp dựa trên độ lệch để kiểm tra sự khác nhau trong
những đặc trưng chính của các nhóm đối tượng.
Phân tích sự tiến hoá: Phân tích sự tiến hoá thực hiện việc mô tả và mô
hình hoá các qui luật hay khuynh hướng của những đối tượng mà hành vi của
chúng thay đổi theo thời gian. Phân tích sự tiến hoá có thể bao gồm cả đặc trưng
hoá, phân biệt, tìm luật kết hợp, phân lớp hay PCDL liên quan đến thời gian, phân
tích dữ liệu theo chuỗi thời gian, so sánh mẫu theo chu kỳ và phân tích dữ liệu dựa
trên độ tương tự.
6. Ứng dụng của khai phá dữ liệu
o Khai phá dữ liệu là một lĩnh vực được quan tâm và ứng dụng rộng rãi.
Một số ứng dụng điển hình trong Khai phá dữ liệu có thể liệt kê như
sau: Phân tích dữ liệu và hỗ trợ ra quyết định, điều trị y học, KPVB,
khai phá Web, tin-sinh, tài chính và thị trường chứng khoán, bảo

- Xây dựng mô hình cho cấu trúc dữ liệu.
- Lựa chọn thuật toán gom cụm phù hợp
- Xây dựng các thủ tục biểu diễn và đánh giá kết quả Gom cụm
2. Các cách thức đo lường dữ liệu
Cách thức đo lường dữ liệu tùy thuộc vào mẫu hình dữ liệu. Một tập dữ liệu
X là không gian metric nếu:
- Với mỗi cặp x, y thuộc X đều xác định được một số thực d(x,y) theo một
quy tắc nào đó và được gọi là khoảng cách của x,y.
- Mô hình không gian metric phải thỏa các điều kiện sau:
o D(x,y) > 0 nếu x ≠ y.
o D(x,y) = 0 nếu x = y.
o D(x, y) = D(y, x).
12
o D(x, y) ≤ D(x, z) + D(z, y).
Các mẫu dữ liệu với các dạng thuộc tính phổ biến:
- Mẫu dữ liệu có thuộc tính nhị phân: Thuộc tính nhị phân chỉ có 2 giá trị (0
và 1). Trong đó, 1 có nghĩa là đúng và 0 có nghĩa là sai.
Hệ số đo lường thông dụng thường chỉ áp dụng cho thuộc tính nhị phân là hệ
số đo lường Jaccard:
Trong đó, A và B là 2 đối tượng có các thuộc tính nhị phân.
- Mẫu dữ liệu có thuộc tính là giá trị số (khoảng giá trị): đây là mẫu dữ liệu có
thuộc tính là các giá trị cụ thể (1, 2,5 ,…) có thể áp dụng trực tiếp các công
thức tính toán trên dạng số như:
o Khoảng cách Minkowski:
1/ *
1
( , ) ( ) ,
n
q
q

thuộc tính nhị phân, trong đó miều giá trị là rời rạc không phân biệt thứ tự.
Nếu x và y là hai thuộc tính định danh thì có thể xác định theo dạng nhị phân
như sau: x = y, và x ≠ y. Ví dụ: nơi sinh, quê quán…
13
Có thể đo độ không tương tự (khác nhau) thông qua công thức tính phần
trăm sự khác biệt
( , )
p m
d x y
p
−
=
. Trong đó, m là số thuộc tính đối sánh
tương ứng trùng nhau và p là tổng số các thuộc tính.
14
3. Phân loại các phương pháp gom cụm dữ liệu
Các phương pháp gom cụm dữ liệu hiện nay đều cố gắn hướng tới hai mục
tiêu chung: chất lượng của các cụm khám phá được và tốc độ thực hiện của thuật
toán. Các phương pháp phâm cụm dữ liệu có thể phân loại theo các cách tiếp cận
chính sau:
- Gom cụm phân hoạch
Ý tưởng chính của kỹ thuật này là phân một tập dữ liệu có n phần tử cho
trước thành k nhóm dữ liệu sao cho mỗi phần tử dữ liệu chỉ thuộc về một nhóm dữ
liệu và mỗi nhóm dữ liệu có tối thiểu ít nhất một phần tử dữ liệu. Các thuật toán
phân hoạch có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề
PCDL, vì nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Chính vì vậy,
trên thực tế người ta thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng
cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của các cụm cũng như
để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu.
Với chiến lược này, thông thường người ta bắt đầu khởi tạo một phân hoạch

phân cấp, các ràng buộc sẽ thay đổi để tiến hành ở các mức khác nhau của gom
cụm dữ liệu phân hoạch.
- Gom cụm dữ liệu dựa trên mật độ
Phương pháp này nhóm các đối tượng theo hàm mật độ xác định. Mật độ
được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu theo
một ngưỡng nào đó. Trong cách tiếp cận này, khi một cụm dữ liệu đã xác định thì
nó tiếp tục được phát triển thêm các đối tượng dữ liệu mới miễn là số các đối
tượng lân cận của các đối tượng này phải lớn hơn một ngưỡng đã được xác định
trước. Phương pháp phân cụm dựa vào mật độ của các đối tượng để xác định các
cụm dữ liệu và có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Tuy vậy,
việc xác định các tham số mật độ của thuật toán rất khó khăn, trong khi các tham
số này lại có tác động rất lớn đến kết quả PCDL. Hình minh hoạ về các cụm dữ
liệu với các hình thù khác nhau dựa trên mật độ được khám phá từ 3 Cơ sở dữ liệu
khác nhau:
16
Cơ sở dữ liệu 1 Cơ sở dữ liệu 2 Cơ sở dữ liệu 3
Hình 2.16. Một số hình dạng khám phá bởi phân cụm dưa trên mật độ
Các cụm có thể được xem như các vùng có mật độ cao, được tách ra bởi các
vùng không có hoặc ít mật độ. Khái niệm mật độ ở đây được xem như là các số
các đối tượng láng giềng.
Một số thuật toán PCDL dựa trên mật độ điển hình như: DBSCAN,
OPTICS, DENCLUE, SNN,….
- Gom cụm dữ liệu dựa trên dạng lưới
Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu nhiều chiều,
để giải quyết cho đòi hỏi này, người ta đã sử dụng phương pháp phân cụm dựa
trên lưới. Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để PCDL, phương
pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không gian. Thí dụ như dữ
liệu được biểu diễn dưới dạng cấu trúc hình học của đối tượng trong không gian
cùng với các quan hệ, các thuộc tính, các hoạt động của chúng. Mục tiêu của
phương pháp này là lượng hoá tập dữ liệu thành các ô (Cell), các ô này tạo thành

việc gom cụm theo tiêu chí khác nhau. Bao gồm các dạng khác như:
18
Gom cụm dựa trên thống kê: dựa trên các khái niệm phân tích thống kê.
Phương pháp này chỉ áp dụng cho các đối tượng có thuộc tính là giá trị số.
Gom cụm dựa trên nguyên lý mờ: sử dụng các nguyên lý trong tập mờ để
gom cụm dữ liệu, trong đó một đối tượng dữ liệu có thể thuộc nhiều cụm khác
nhau. Phương pháp này thường được áp dụng để xử lý cho các dữ liệu thuộc dạng
không chắc chắn. Ví dụ: dữ liệu có thuộc tính mang tính tương đối như nhanh,
chậm …
Gom cụm dựa trên mạng Kohonen: mạng Kohonen là một dạng biến thể của
mạng nơron. Trong đó, mạng Kohonen chỉ bao gồm 2 lớp: đầu vào và đầu ra. Mỗi
nơron của đầu vào tương ứng với mỗi thuộc tính của dữ liệu và kết nối với tất cả
các nơron của đầu ra. Mỗi liên kết được gắn liền với một trọng số nhằm xác định
vị trí của nơron ra tương ứng. Quá trình gom cụm này tương tự như mạng nơron
sẽ cho học tập mẫu huấn luyện đã được gom cụm trước để điều chỉnh các trọng số
để qua đó khi sử dụng vào thực tế sẽ gom cụm sẽ trên các trọng số đã được điều
chỉnh nhờ vào tập mẫu huấn luyện.
Tóm lại, các phương pháp gom cụm dữ liệu đã được áp dụng rộng rãi trong
thực tế. Như trong thương mại, gom cụm sẽ cho phép các công ty tìm kiếm ra
được các nhóm khác hàng. Trong sinh học – hóa học, gom cụm dữ liệu cho phép
thành lập các nhóm gene, cấu trúc hóa học tương tự để trù bị các biến đổi, tương
tác với nhau
19
CHƯƠNG 3. THUẬT TOÁN CLARA VÀ
ỨNG DỤNG TRONG GOM CỤM VĂN BẢN
1. Giới thiệu về thuật toán
CLARA (Clustering LARge Application) được Kaufman và Rousseeuw đề
xuất năm 1990, thuật toán này nhằm khắc phục nhược điểm của thuật toán PAM
trong trường hợp giá trị của k và n lớn. CLARA tiến hành trích mẫu cho tập dữ liệu
có n phần tử và áp dụng thuật toán PAM cho mẫu này và tìm ra các các đối tượng

thể thực hiện đối với tập dữ liệu lớn. Chú ý đối với kỹ thuật tạo mẫu trong PCDL:
kết quả phân cụm có thể không phụ thuộc vào tập dữ liệu khởi tạo nhưng nó chỉ
đạt tối ưu cục bộ.
1. Xử lý dữ liệu văn bản
3.2.1. Dữ liệu văn bản
Trong các loại dữ liệu hiện nay thì văn bản là loại dữ liệu phổ biến nhất và
nó có mặt khắp mọi nơi, đặc biệt là đối với dữ liệu trên Web. Do vậy, các bài toán
xử lý văn bản đã được đặt ra từ rất sớm và hiện nay nó vẫn là vấn đề rất được
nhiều nhà nghiên cứu quan tâm, một trong những bài toán đó là tìm kiếm và trích
dẫn văn bản, biểu diễn và phân loại văn bản,….
CSDL văn bản có thể chia làm 2 loại chính:
+ Dạng không có cấu trúc: Đây là những tài liệu văn bản thông thường mà ta đọc
thường ngay trên các sách, báo, internet,… đây là dạng dữ liệu của ngôn ngữ tự
nhiên của con người và nó không theo một khuôn mẫu định sẵn nào cả.
+ Dạng nữa cấu trúc: Đây là những văn bản được tổ chức dưới dạng cấu trúc lỏng,
nhưng vẫn thể hiện nội dung chính của văn bản, như văn bản HTML, Email,
3.2.2. Một số vấn đề trong xử lý dữ liệu văn bản
Mỗi văn bản được biểu diễn bằng một vector Boolean hoặc vector số.
Những vector này được xét trong một không gian đa chiều, trong đó mỗi chiều
tương ứng với một từ mục riêng biệt trong tập văn bản. Mỗi thành phần của vector
được gán một hàm giá trị f, nó là một số chỉ mật độ tương ứng của chiều đó trong
văn bản. Nếu thay đổi giá trị hàm f ta có thể tạo ra nhiều trọng số khác nhau.
Một số vấn đề liên quan đến việc biểu diễn văn bản bằng mô hình không
gian vector:
+ Không gian vector là một tập hợp bao gồm các từ.
+ Từ là một chuỗi các ký tự (chữ cái và chữ số); ngoại trừ các khoảng trống
(space, tab), ký tự xuống dòng, dấu câu (như dấu chấm, phẩy, chấm phẩy, dấu
cảm, ). Mặt khác, để đơn giản trong quá trình xử lý, ta không phân biệt chữ hoa
21
và chữ thường (nếu chữ hoa thì chuyển về chữ thường).

Để giảm số chiều của vector biểu diễn văn bản hơn nữa ta dựa vào một quan
sát sau: Nhiều từ trong văn bản xuất hiện rất ít lần, nếu mục tiêu của ta là xác định
độ tương tự và sự khác nhau trong toàn bộ tập hợp các văn bản thì các từ xuất hiện
một hoặc hai lần (tần số xuất hiện nhỏ) thì ảnh hưởng rất bé đến các văn bản.
Tiền đề cho việc lý luận để loại bỏ những từ có tần suất nhỏ được đưa ra bởi
Zipf năm 1949. Zipf phát biểu dưới dạng một quan sát nhưng ngay trong thời điểm
đó, quan sat đó đã được gọi là định luật Zipf, mặc dù nó thực sự không phải là một
định luật mà đúng hơn đó là một hiện tượng xấp xỉ toán học.
Để mô tả định luật Zipf, ta gọi tổng số tần số xuất hiện của từ t trong tài liệu
D là f
t
. Sau đó sắp xếp tất cả các từ trong tập hợp theo chiều giảm dần của tần số
xuất hiện f và gọi thứ hạng của mỗi từ t là r
t
.
Định luật Zipf được phát biểu dưới dạng công thức như sau:
r
t
.f
t
» K (với K là một hằng số).
Trong tiếng Anh, người ta thấy rằng hằng số K » N/10 trong
đó N là số các từ trong văn bản. Ta có thể viết lại định luật Zipf
như sau: r
t
» K/ f
t
Giả sử từ t
i
được sắp xếp ở vị trí thấp nhất với tần số xuất

Theo các nghiên cứu về cách biểu diễn khác nhau trong xử lý văn bản thì
cách biểu diễn tốt nhất là bằng các từ riêng biệt được rút ra từ tài liệu gốc và cách
biểu diễn này ảnh hưởng tương đối nhỏ đối với kết quả.
Các cách tiếp cận khác nhau sử dụng mô hình toán học khác nhau để tính
toán, ở đây ta sẽ trình bày một số mô hình phổ biến và được đăng nhiều trong các
bài báo gần đây
Trong các bài toán xử lý văn bản, ta thấy rằng vai trò của biểu diễn văn bản
rất lớn, đặc biệt trong các bài toán tìm kiếm, phân cụm,…
Theo các nghiên cứu về cách biểu diễn khác nhau trong xử lý văn bản thì
cách biểu diễn tốt nhất là bằng các từ riêng biệt được rút ra từ tài liệu gốc và cách
24
biểu diễn này ảnh hưởng tương đối nhỏ đối với kết quả.
Các cách tiếp cận khác nhau sử dụng mô hình toán học khác nhau để tính
toán, ở đây ta sẽ trình bày một số mô hình phổ biến và được đăng nhiều trong các
bài báo gần đây.
■ Mô hình Boolean
Đây là mô hình biểu diễn vector với hàm f nhận giá trị rời rạc với duy nhất
hai giá trị đúng/sai (true/false). Hàm f tương ứng với thuật ngữ t
i
sẽ cho giá trị đúng
khi và chỉ khi t
i
xuất hiện trong tài liệu đó.
Giả sử rằng có một CSDL gồm m văn bản, D={d
1
, d
2
, , d
m
}. Mỗi văn bản

trong tài liệu d
j
, khi đó w
ij
có thể được tính theo một trong các công
thức sau:
- W
ij
= tf
ij

- W
ij
= 1+log(tf
ij
)
25