Đại Học Quốc Gia TP.HCM
Trường Đại Học Công Nghệ Thông Tin
BÀI TIỂU LUẬN MÔN
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU
ĐỀ TÀI:
KỸ THUẬT PHÂN CỤM TRONG
KHAI PHÁ DỮ LIỆU
GVHD: PGS.TS Đỗ Phúc
Người thực hiện: Tô Hồ Hải
Mã số: CH1101011
Lớp: Cao học khóa 6
TP.HCM – 11/2012
MỤC LỤC

MỤC LỤC 1
LỜI NÓI ĐẦU 2
TỔNG QUAN 3
PHẦN I: TỔNG QUAN PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ LIỆU 5
PHẦN II. KỸ THUẬT GOM CỤM – PHƯƠNG PHÁP GOM CỤM BẰNG K-
MEANS 13
5.2. Minh họa thuật giải K-Means: 16
PHẦN III. CÀI ĐẶT MINH HỌA THUẬT TOÁN 20
K-MEANS 20
1. Giao diện: 20
2. Thực hiện chương trình: 20
} 29
PHẦN IV. TỔNG KẾT 30
TÀI LIỆU THAM KHẢO 31
Trang 1
LỜI NÓI ĐẦU
Trong chương trình cao học ngành công nghệ thông tin, nhóm các môn

truyền thống ngày càng không đáp ứng được yêu cầu của thực tế. Từ đây phát
triển ra một kỹ thuật mới đó là Kỹ thuật phát hiện tri thức và khai phá dữ liệu
(KDD – Knowledge Discovery and Data Mining). Kỹ thuật phát hiện tri thức và
khai phá dữ liệu đã và đang được nghiên cứu, phát triển và ứng dụng trong nhiều
lĩnh vực khác nhau ở các nước trên thế giới. Tại Việt Nam kỹ thuật này tương đối
còn mới, tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng. Bước
quan trọng nhất của quá trình này là Khai phá dữ liệu (Data Mining - DM), giúp
người sử dụng thu được những tri thức hữu ích từ những CSDL hoặc các nguồn
dữ liệu khổng lồ khác. Rất nhiều doanh nghiệp và tổ chức trên thế giới đã ứng
dụng kỹ thuật khai phá dữ liệu vào hoạt động sản xuất kinh doanh của mình và
đã thu được những lợi ích to lớn. Nhưng để làm được điều đó, sự phát triển của
các mô hình toán học và các giải thuật hiệu quả là chìa khoá quan trọng. Và hiện
nay có rất nhiều kỹ thuật được đưa ra để giải quyết vấn đề này. Trong bài tiểu
luận này em xin trình một trong những cách mà em đã được học trong môn học
Trang 3
“Khai phá dữ liệu và Kho dữ liệu” do thầy Đỗ Phúc phụ trách, đó là “Kỹ thuật
phân cụm trong khai phá dữ liệu”.
Trang 4
PHẦN I: TỔNG QUAN PHÁT HIỆN TRI THỨC VÀ
KHAI PHÁ DỮ LIỆU
1. Giới thiệu chung.
Trong những năm gần đây, sự phát triển mạnh mẽ của CNTT và ngành
công nghiệp phần cứng đã làm cho khả năng thu thập và lưu trữ thông tin của các
hệ thống thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó việc tin học hoá
một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như
nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ
khổng lồ. Hàng triệu CSDL đã được sử dụng trong các hoạt động sản xuất, kinh
doanh, quản lí , trong đó có nhiều CSDL cực lớn cỡ Gigabyte, thậm chí là
Terabyte. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kỹ
thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành các

4.1. Khai phá Luật kết hợp (Association Rules)
- Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ
giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là
tập luật kết hợp tìm được.
- Phương pháp này được sử dụng rất hiệu quả trong các lĩnh vực như
marketing có chủ đích, phân tích quyết định, quản lí kinh doanh, …
- Tiếp cận cho kỹ thuật này thường sử dụng thuật toán Apriori.
- Nhiều bài báo đã được công bố về đề tài này
4.2. Khai phá luật Episode:
- Các luật Episode mô tả quan hệ thời gian giữa các sự vật
Trang 6
- Hai cách tiếp cận:
* WINEPI với cửa sổ trượt
* MINEPI với việc tìm sự xuất hiện nhỏ nhất
- Mở rộng thuật toán tăng cường cho bài toán Sequential Pattern Mining
4.3. Gom cụm
Mục tiêu chính của phương pháp phân cụm dữ liệu là nhóm các đối tượng
tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng
một cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không
tương đồng. Phân cụm dữ liệu là một ví dụ của phương pháp học không giám sát.
Không giống như phân loại dữ liệu, phân cụm dữ liệu không đòi hỏi phải định
nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là
một cách học bằng quan sát (learning by observation), trong khi phân loại dữ liệu
là học bằng ví dụ (learning by example). Trong phương pháp này bạn sẽ không
thể biết kết quả các cụm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy,
thông thường cần có một chuyên gia về lĩnh vực đó để đánh giá các cụm thu
được. Kỹ thuật phân cụm dữ liệu được sử dụng rất nhiều trong các ứng dụng về
nhận dạng mẫu, phân loại email, phân loại khách hàng, phân đoạn thị trường…
Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho
các thuật toán khai phá dữ liệu khác.

5.1 Khai phá dữ liệu mô tả:
Kỹ thuật này có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung
của dữ liệu trong CSDL hiện có.
- Cho biết điều gì là hữu ích có thể tìm thấy được trong dữ liệu
- Giải thích dữ liệu đó
Khai phá dữ liệu mô tả bao gồm các kỹ thuật: phân cụm (clustering), phân tích
luật kết hợp (association rules)
Trang 8
5.2 Khai phá dữ liệu dự báo:
• Dựa trên dữ liệu quá khứ, dự báo tương lai
• Xu thế phát triển!
6. Lợi thế của khai phá dữ liệu so với các phương pháp khác
Khai phá dữ liệu là một lĩnh vực liên quan tới rất nhiều ngành học khác
như: hệ CSDL, thống kê, Hơn nữa, tuỳ vào cách tiếp cận được sử dụng, khai
phá dữ liệu còn có thể áp dụng một số kỹ thuật như mạng nơ ron, lý thuyết tập
thô hoặc tập mờ, biểu diễn tri thức… Như vậy, khai phá dữ liệu thực ra là dựa
trên các phương pháp cơ bản đã biết. Tuy nhiên, sự khác biệt của khai phá dữ
liệu so với các phương pháp đó là gì? Tại sao khai phá dữ liệu lại có ưu thế hơn
hẳn các phương pháp cũ? Ta sẽ lần lượt xem xét và giải quyết các câu hỏi này.
6.1 Học máy (Machine Learning):
So với phương pháp học máy, khai phá dữ liệu có lợi thế hơn ở chỗ, khai
phá dữ liệu có thể sử dụng với các cơ sở dữ liệu thường động, không đầy đủ, bị
nhiễu và lớn hơn nhiều so với các tập dữ liệu học máy điển hình. Trong khi đó
phương pháp học máy chủ yếu được áp dụng trong các CSDL đầy đủ, ít biến
động và tập dữ liệu không quá lớn. Thật vậy, trong học máy, thuật ngữ cơ sở dữ
liệu chủ yếu đề cập tới một tập các mẫu được lưu trong tệp. Các mẫu thường là
các vectơ với độ dài cố định, thông tin về đặc điểm, dãy các giá trị của chúng đôi
khi cũng được lưu lại như trong từ điển dữ liệu. Một giải thuật học sử dụng tập
dữ liệu và các thông tin kèm theo tập dữ liệu đó làm đầu vào và đầu ra biểu thị
kết quả của việc học. Học máy có khả năng áp dụng cho cơ sở dữ liệu, lúc này,

dữ liệu và thống kê ở chỗ khai phá dữ liệu là một phương tiện được dùng bởi
người sử dụng đầu cuối chứ không phải là các nhà thống kê. Khai phá dữ liệu đã
khắc phục được các yếu điểm trên của thống kê, tự động quá trình thống kê một
cách hiệu quả, vì thế giảm bớt công việc của người dùng đầu cuối, tạo ra một
công cụ dễ sử dụng hơn.
7. Các ứng dụng và thách thức của việc khai mỏ dữ liệu.
7.1 Các ứng dụng của Khai mỏ dữ liệu:
Trang 10
Các kỹ thuật khai mỏ dữ liệu có thể được áp dụng vào trong nhiều lĩnh
vực:
• Thông tin thương mại: Phân tích dữ liệu tiếp thị và bán hàng, phân tích
vốn đầu tư, chấp thuận cho vay, phát hiện gian lận,
Thông tin sản xuất: Điều khiển và lập lịch, quản lý mạng, phân tích kết
quả thí nghiệm,
• Thông tin khoa học:
Địa lý: Phát hiện động đất,
•
7.2 Những thách thức đối với khai mỏ dữ liệu:
• Các cơ sở dữ liệu lớn hơn rất nhiều: cơ sở dữ liệu với hàng trăm trường
và bảng, hàng triệu bản ghi và kích thước lên tới nhiều gigabyte là vấn đề hoàn
toàn bình thường và cơ sở dữ liệu terabyte (1012bytes) cũng đã bắt đầu xuất
hiện.
• Số chiều cao: Không chỉ thường có một sốlượng rất lớn các bản ghi
trong cơ sở dữ liệu mà còn có một số lượng rất lớn các trường (các thuộc tính,
các biến) làm cho số chiều của bài toán trở nên cao. Thêm vào đó, nó tăng thêm
cơ hội cho một giải thuật khai phá dữ liệu tìm ra các mẫu không hợp lệ. Vậy nên
cần giảm bớt hiệu quả kích thước của bài toán và tính hữu ích của tri thức cho
trước để nhận biết các biến không hợp lệ.
• Over-fitting (quá phù hợp): Khi giải thuật tìm kiếm các tham số tốt nhất
cho một mô hình đặc biệt sử dụng một tập hữu hạn dữ liệu, kết quả là mô hình

mô tả các nhóm khách hàng dựa trên các mẫu mua sắm. Trong sinh vật học, nó
có thể được dùng để có được các nguyên tắc phân loại thực vật và động vật, phân
loại gien theo chức năng giống nhau và có được sự hiểu biết thấu đáo các cấu
trúc kế thừa trong các mẫu. Phân cụm cũng có thể được dùng để nhận biết các
vùng đất giống nhau dùng trong cơ sở dữ liệu quan sát trái đất và nhận biết các
nhóm có hợp đồng bảo hiểm ô tô với mức chi phí trung bình cao, cũng như nhận
biết các nhóm nhà trong thành phố theo kiểu nhà, giá trị và khu vực địa lý. Nó có
thể cũng giúp cho việc phân loại dữ liệu trên WWW để khai thác thông tin. Như
một hàm khai phá dữ liệu, phép phân tích cụm được dùng như là một công cụ độc
lập để có thể nhìn thấu được bên trong sự phân bố dữ liệu, để quan sát các đặc
điểm của mỗi cụm và tập trung trên một tập đặc biệt các cụm cho phép phân tích
Trang 13
xa hơn. Tiếp theo, nó phục vụ như là một bước tiền xử lý cho các giải thuật khác
như phân loại và mô tả, thao tác trên các cụm đã dò được.
3. Các kiểu dữ liệu trong phép phân cụm
3.1. Kiểu số
 khoảng cách Minkowski
q
q
jpip
q
ji
q
ji
xxxxxxjid ) (),(
2211
−++−+−=
i = (x
i1
, x

+
=),(
 khoảng cách bất đối xứng:
cba
cb
jid
++
+
=),(
 hệ số Jaccard bất đối xứng:
cba
a
jisim
Jaccard
++
=),(
3.3. Kiểu loại (nominal type)
 ví dụ: thuộc tính color có giá trị là red, green, blue, . . .
Trang 14
 phương pháp matching đơn giản, m là số lượng matches và p là tổng số
biến (thuộc tính), khoảng cách được định nghĩa:
p
mp
jid
−
=),(
3.4. Kiểu symbol
4. Phân loại các phương pháp phân cụm chính
- Các phương pháp phân chia
- Các phương pháp phân cấp

chương trình.
- Chương trình demo như sau:
Trang 20
3. Phần code chương trình:
Phần mềm cài đặt: Chương trình minh họa được viết bằng ngôn ngữ C# 2008
và được biên dịch sẵn để chạy trực tiếp.
Một số code cơ bản xử lý thuật toán K-Means
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace K_MEANS
{
public partial class Form1 : Form
Trang 21
{
public Form1()
{
InitializeComponent();
}
#region Gán hai ma trận có 2 dòng, DataGridview.Rowcount-1 cột
public void gan(ref int[,] A, int[,] B)
{
for (int i = 0; i < 2; i++)// Chỉ có 2 hàng(2 cụm)
{
for (int j = 0; j < dataGridView.RowCount - 1; j++)

a = b;
b = tam;
}
#endregion
#region Khai báo ma trận chứa các điểm nhập vào
double[,] dataInput; int i, j;
#endregion
private void button1_Click(object sender, EventArgs e)
{
StringBuilder sb = new StringBuilder();
#region Bước 1: nhận giá trị các điểm nhập vào. Lưu trữ vào ma trận dataInput
int dong= dataGridView.RowCount-1;
int cot = dataGridView.ColumnCount;
dataInput = new double[dong,cot];
Trang 23
for (i = 0; i <dong; i++)
for (j = 0; j < cot; j++)
dataInput[i, j] = double.Parse(dataGridView[j, i].Value.ToString());
#endregion
#region Bước 2: ma trận U random
int[,] Usau = new int[2, dong];
int[,] U = new int[2,dong];
Random rand = new Random();
for (j = 0; j < dong; j++)
U[0, j] = rand.Next(2);
for (j = 0; j < dong; j++)
if (U[0, j] == 1)
U[1, j] = 0;
else
{