ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Công Nghệ Tri Thức
và Ứng Dụng
Phân cụm dữ liệu và ứng dụng tìm
những website tương tự
Giáo viên hướng dẫn
GS.TSKH. Hoàng Kiếm
Học viên: Huỳnh Lê Quốc Vương MHV: CH1101158
06 - 2012
LỜI MỞ ĐẦU: 3
I.QUÁ TRÌNH KHAI MỎ DỮ LIỆU: 4
1. Các bước khai khá dữ liệu: 4
1.1. Trích chọn dữ liệu 4
1.2. Tiền xử lý dữ liệu 6
1.3. Biến đổi dữ liệu 6
1.4. Khai thác dữ liệu 8
1.5. Đánh giá và biểu diễn tri thức 8
2. Một số bài toán trong Data Mining 8
II.PHÂN CỤM DỮ LIỆU: 9
1. Khái niệm về phân cụm dữ liệu 9
2. Độ đo tương tự 10
3. Những kỹ thuật tiếp cận trong phân cụm dữ liệu 11
3.1. Phương pháp phân chia 11
3.2. Phương pháp phân cấp 12
3.3. Phương pháp dựa trên mật độ 13
3.4. Phương pháp dựa trên lưới 13
4. Phân cụm dữ liệu bán giám sát 14
4.1. Giải thuật K-Means 15
4.2. Giải thuật Seeded-Kmeans 16
4.3. Thuật toán cho chương trình 17

Bằng cách gom lại các website, chủ đề tương tự nhau. Ta sẽ kết hợp các dữ
liệu đó lại với nhau, lọc loại bỏ các nội dung giống nhau để đưa cho người
dùng một kết quả đầy đủ và tốt nhất. Điều này thì liên quan khá chặt chẽ đến
khái niệm data mining. Do đó chúng ta cùng tìm hiểu xem data mining là gì,
chương trình sẽ ứng dụng chúng như thế nào để đạt được vấn đề đặt ra.
3
I. Quá trình khai mỏ dữ liệu:
Trong vài thập kỷ gần đây, số lượng dữ liệu lưu trữ trong các hệ thống cơ
sở dữ liệu cũng như các ứng dụng cơ sở dữ liệu trong các lĩnh vực kinh doanh và
khoa học đã tăng lên một cách không ngờ. Những cơ sở dữ liệu rất lớn ra đời lên
đến hàng trăm hàng ngàn Terabyte. Trong khi công nghệ cho việc lưu trữ dữ liệu
có những bước tiến mạnh mẽ để đáp ứng kịp với yêu cầu phát triển thì các kỹ
thuật để phân tích dữ liệu phát triển chậm chạp cho tới khi một số công ty nhận
ra rằng các tri thức tiềm ẩn trong các nguồn dữ liệu khổng lồ của họ là một mỏ
quý cần phải được khai thác nhằm hỗ trợ công việc kinh doanh vốn càng ngày
càng phải đối mặt với những điều kiện cạnh tranh khốc liệt. Họ nhận ra rằng dữ
liệu được lưu trữ trong cơ sở dữ liệu chỉ là phần nổi của một núi băng thông tin.
Kỹ thuật rút trích tri thức từ các kho, cơ sở dữ liệu lớn được gọi là Data Mining.
Các lợi ích thấy rõ của Data Mining đã thúc đẩy chúng phát triển nhanh chóng
và rộng lớn trong những năm gần đây. Quá trình khai phá dữ liệu có thể chia
thành các bước thực hiện như sau:
1. Các bước khai khá dữ liệu:
1.1. Trích chọn dữ liệu
- Ở bước này các dữ liệu liên quan trực tiếp đến nhiệm vụ của quá trình
KDD sẽ được thu thập từ các nguồn dữ liệu ban đầu.
- Với giao thức http ta sẽ kết nối tới các URL để thu thập nguồn dữ liệu
như (html, image, pdf, …).
- Ta sẽ có nhiều luồng kết nối tới nhiều URL để thu thập dữ liệu. Từ
nguồn dữ liệu này ta sẽ lấy được những URL khác, ta đưa những URL
đó vào hàng đợi để chờ kết nối đến. Giống như hình dưới đây

1.3. Biến đổi dữ liệu
- Nhằm chuẩn hóa và làm mịn dữ liệu để chuyển dữ liệu về dạng thuận
lợi nhất phục vụ cho việc khai phá.
- Lấy n từ xuất hiện nhiều nhất, chuyển số lần xuất hiện về %
Bước 2 và 3 có thể được tóm tắt như hình dưới đây
Lưu trữ thông tin của webiste
6
Các trang HTML
của một website
Chuyển về dạng văn bản
Kho lưu trữ các
trang dạng văn
bản
Vì sau này thuật toán phân tích câu, tách từ có thể thay đổi hay ta cần
phải chạy nhiều thuật toán một lúc để tìm kết quả tốt nhất, cho nên phải lưu
trữ lại các trang HTML (ở dạng văn bản)
Phân tích lấy các top-word của website
7
Từ điển / bộ phân
tích cú pháp câu
Tách văn bản thành các câu
Loại bỏ các câu thừa
Tách các câu thành các từ
Loại bỏ các stop-word
Danh sách các
stop-word
Đếm số lần xuất hiện của
các từ
Kho lưu trữ các
trang dạng văn bản

một luật có dạng nối tiếp. Những luật loại này rất có ích cho công việc
dự báo.
8
- Phân cụm (Clustering): Nhóm các đối tượng thành từng cụm dữ liệu.
Đây là phương pháp học không giám sát. Ví dụ trong lập quy hoạch đô
thị, phân cụm giúp cho việc nhận dạng cá nhóm nhà theo kiến trúc và vị
trí địa lý để lập quy hoạch đô thị hợp lý.
- Mô tả khái niệm: 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.
Ở đây ta quan tâm về phân cụm dữ liệu chứ không phải phân loại dữ
liệu bởi vì ta sẽ không biết xác định được các đặc tính chính xác của một
cụm dữ liệu là gì, bao nhiêu lớp, chủ đề được phân loại.
II. Phân cụm dữ liệu:
1. Khái niệm về phân cụm dữ liệu
Phân cụm dữ liệu là một kỹ thuật phát triển mạnh mẽ trong nhiều năm
trở lại đây do các ứng dụng và lợi ích to lớn của nó trong các lĩnh vực trong
thực tế. Ở một mức cơ bản nhất người ta định nghĩa phân cụm dữ liệu như
sau :
- Phân cụm dữ liệu là một kỹ thuật trong Data mining nhằm tìm kiếm,
phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong
tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết
định.
- Do đó, phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu
thành các cụm dữ liệu sao cho các đối tượng trong một cụm thì “tương
tự” nhau và các đối tượng trong các cụm khác nhau thì “phi tương tự”
với nhau. Số cụm dữ liệu được xác định bằng kinh nghiệm hoặc bằng
một số phương pháp phân cụm.
9
Sau khi xác định các đặc tính của dữ liệu, người ta đi tìm cách thích hợp
để xác định "khoảng cách" giữa các đối tượng, hay là phép đo tương tự dữ

o d(x,y) = d(y,x)
o d(x,y) <= d(x,z) + d(z,y)
Ví dụ vài top-word của http://www.tuoitre.vn
Key = xã hội Value = 1.9525532
Key = bạn đọc Value = 1.5920393
Key = ý kiến Value = 1.4715848
Key = tài chính Value = 1.4375942
… …
Thì khoảng cách giữa 2 website dựa trên top-word được tính như sau:
d(x, y)
Với x là website A, y là website B. Gọi s là tổng top-word của x và y, n
là tổng số top-word của s, px
i
là phần trăm của từ thứ i của s trong x, py
i
là
phần trăm của từ thứ i của s trong y.
3. Những kỹ thuật tiếp cận trong phân cụm dữ liệu
3.1. Phương pháp phân chia
Cho trước một cơ sở dữ liệu với n đối tượng hay các bộ dữ liệu, một
phương pháp phân chia được xây dựng để chia dữ liệu thành k phần, mỗi
phần đại diện cho một cụm, k ≤ n. Đó là phân loại dữ liệu vào trong k
nhóm, chúng thoả các yêu cầu sau: Mỗi nhóm phải chứa ít nhất một đối
11
tượng, mỗi đối tượng phải thuộc về chính xác một nhóm. Cho trước k là số
lượng các phần chia cần xây dựng, phương pháp phân chia tạo lập phép
phân chia ban đầu. Sau đó nó dùng kỹ thuật lặp lại việc định vị, kỹ thuật
này cố gắng cải thiện sự phân chia bằng cách gỡ bỏ các đối tượng từ nhóm
này sang nhóm khác. Tiêu chuẩn chung của một phân chia tốt là các đối
tượng trong cùng cụm là "gần" hay có quan hệ với nhau, ngược lại, các đối

Hầu hết các phương pháp phân chia cụm các đối tượng dựa trên khoảng
cách giữa các đối tượng. Các phương pháp như vậy có thể chỉ tìm được các
cụm có hình cầu và sẽ gặp khó khăn khi các cụm đang khám phá lại có hình
dạng tuỳ ý. Các phương pháp phân cụm được phát triển dựa trên khái niệm
mật độ. Ý tưởng chung đó là tiếp tục phát triển cụm cho trước với điều kiện
là mật độ (số các đối tượng hay các điểm dữ liệu) trong "lân cận" vượt quá
ngưỡng, tức là đối với mỗi điểm dữ liệu trong phạm vi một cụm cho trước
thì lân cận trong vòng bán kính đã cho chứa ít nhất một số lượng điểm tối
thiểu. Một phương pháp như vậy có thể được dùng để lọc ra nhiễu (các
outlier) và khám phá ra các cụm có hình dạng bất kỳ.
BSCAN là một phương pháp dựa trên mật độ điển hình, nó tăng trưởng
các cụm theo một ngưỡng mật độ. OPTICS là một phương pháp dựa trên
mật độ, nó tính toán một thứ tự phân cụm tăng dần cho phép phân tích cụm
tự động và tương tác.
3.4. Phương pháp dựa trên lưới
Một phương pháp dựa trên lưới lượng tử hoá không gian đối tượng vào
trong một số hữu hạn các ô hình thành nên một cấu trúc lưới. Sau đó nó
thực hiện tất cả các thao tác phân cụm trên cấu trúc lưới (tức là trên không
gian đã lượng tử hoá). Thuận lợi chính của tiếp cận này là thời gian xử lý
13
nhanh chóng của nó độc lập với số các đối tượng dữ liệu và chỉ tuỳ thuộc
vào số lượng các ô trong mỗi chiều của không gian lượng tử. STING là một
ví dụ điển hình của phương pháp dựa trên lưới. WaveCluster và CLIQUE là
hai giải thuật phân cụm dựa trên cả lưới và mật độ.
Nhiều giải thuật phân cụm tích hợp các ý tưởng của một vài phương
pháp phân cụm, bởi vậy việc phân loại giải thuật đó không dễ như loại giải
thuật chỉ phụ thuộc vào duy nhất một loại phương pháp phân cụm. Hơn
nữa, nhiều ứng dụng có thể có giới hạn phân cụm với yêu cầu tích hợp một
số kỹ thuật phân cụm.
4. Phân cụm dữ liệu bán giám sát

E = |x – m
i
|
2
với x là điểm trong không gian, đại diện cho đối tượng cho trước, mi là
trung bình cụm Ci (cả x và mi đều là nhiều chiều). Tiêu chuẩn này cố gắng
cho kết quả k cụm càng đặc, càng riêng biệt càng tốt.
Giải thuật xác định k phần phân chia thoả mãn tối thiểu hoá bình
phương hàm sai số. Nó làm việc tốt khi các cụm là các đám mây đặc tách
biệt so với những cụm khác. Phương pháp này có thể mở rộng có hiệu quả
khi xử lý các tập dữ liệu lớn bởi độ phức tạp tính toán của giải thuật là
O(nkt), với n là số đối tượng, k là số cụm, t là số lần lặp. Thông thường k
<< n và t << n. Phương pháp thường kết thúc tại một điểm tối ưu cục bộ.
Giải thuật k-means đối với việc phân chia dựa trên giá trị trung bình của
các đối tượng trong cụm.
Đầu vào: Số cụm k và một tập dữ liệu chứa n đối tượng
15
Đầu ra: Một tập k cụm - cụm tối thiểu hoá bình phương sai số tiêu
chuẩn.
Giải thuật:
o Chọn tuỳ ý k đối tượng với tư cách là các tâm cụm ban đầu
o Repeat
 Ấn định (lại) mỗi đối tượng về một cụm mà đối tượng đó giống nhất,
dựa trên giá trị trung bình của các đối tượng trong cụm
 Cập nhật các trung bình cụm, tức là tính giá trị trung bình của các
đối tượng trong cụm đó
o Until không có sự thay đổi nào
Tuy nhiên, phương pháp k-means chỉ áp dụng khi trung bình của một
cụm được xác định. Không phải ứng dụng nào cũng có thể áp dụng kỹ thuật
này, ví dụ những dữ liệu bao hàm các thuộc tính xác thực. Về phía các user,

Giải thuật k-means, seed-kMeans rất nhạy với các giá trị nhiễu, do vậy
thay vì lấy tất cả các đối tượng trong cụm để tính giá trị trung bình cụm thì
từ các đối tượng giống ban đầu ta chỉ chọn thêm một đối tượng mà làm
giảm hàm mục tiêu (là tổng các độ đo không tương đồng của tất cả các đối
tượng tới giá trị trung bình cụm). Ta có thể xét duyệt tất cả các đối tượng
của cụm để có được hàm mục tiêu tốt nhất
Giải thuật
Đầu vào: Số cụm k, tập giống và một tập dữ liệu chứa n đối tượng
Đầu ra: Một tập k cụm - cụm tối thiểu hoá bình phương sai số tiêu
chuẩn.
o Khởi tạo k cụm từ tập giống
o Repeat
 Ấn định (lại) mỗi đối tượng về một cụm mà đối tượng đó giống nhất,
dựa trên giá trị tâm cụm
 Tính hàm mục tiêu
17
 Thêm một đối tượng vào tâm cụm nếu như việc này làm giảm hàm
mục tiêu
o Until không có sự thay đổi nào;
Tuy nhiên, vì để đạt được mục đích như phần mở đầu đặt ra thì tất nhiên
số k cụm không thể do người dùng xác định. Vì vậy, với mỗi website mà ta
thu thập dữ liệu ta sẽ xác định các chủ đề trong website và mỗi chủ đề sẽ
chiếm bao nhiêu phần trăm của website. Ví dụ website tuoitre.vn chủ đề
“thế giới” chiếm 20%, “kinh tế” chiếm 15%, … Như thế việc phân cụm
website sẽ được thực hiện trên những chủ đề này. Thông thường một
website sẽ có nhiều chủ đề, do đó các website nhiều chủ đề này sẽ không
được phân cụm vào một chủ đề cụ thể nào hết. Mà sẽ được phân cụm vào
nhiều chủ đề, mỗi chủ đề sẽ ứng với bao nhiêu phần trăm đó. Do đó người
dùng sẽ dễ dàng tìm được một website chuyên về chủ đề nào đó (có nghĩa
là phần trăm về chủ đề đó cao) hay một website tổng hợp.

Chú ý: Vì JRE mặc định bộ nhớ heap hơi nhỏ, nên trong quá trình thu
thập dữ liệu website dễ bị thông quá lỗi OutOfMemory (Java Heap
Space). Để khắc phục lỗi này thì ta tăng bộ nhớ heap cho JRE bằng cách
thêm tham số “Xmx1000m” vào sau từ khóa java.
Ví dụ:
20
java -Xmx1000m -jar E:\ClusteringSites.jar E:\DATA_STORAGE -a
http://tuoitre.vn
Số 1000 ở đây là số Mb ta yêu cầu bộ nhớ heap cho JRE.
Khi chương trình gặp lỗi OutOfMemory (Java Heap Space) thì chương
trình vẫn tiếp tục thu thập dữ liệu, nhưng những dữ liệu thu thập được
trước đó sẽ bị mất.
1.2. Tìm các website tương tự
Trong cmd của Windows ta nhập lệnh sau
java -jar file_jar folder -fs website_name
Ví dụ:
java -jar E:\ClusteringSites.jar E:\DATA_STORAGE -fs http://tuoitre.vn
Ta tìm được các website tương tự như http://tuoitre.vn:
1.3. Tìm các website theo chủ đề
Ta mở file topic.txt trong thư mục DATA_STORAGE để nhập vào
chủ đề (một hay hai từ). Ví dụ ở đây ta nhập vào hai từ “nhạc trẻ”.
21
Chú ý: File topic.txt được lưu lại dưới bảng mã Unicode (Unicode 16)
Trong cmd của Windows ta nhập như sau
java -jar file_jar folder -ft
Ví dụ:
java -jar E:\ClusteringSites.jar E:\DATA_STORAGE -ft
Kết quả thu được cho các website liên quan đến “nhạc trẻ”
1.4. Phân cụm các website
Như đã nói trong phần Thuật toán của chương trình, việc phân