TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
PHAN MINH HẢI
CÁC KỸ THUẬT PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU
SỬ DỤNG TÍNH TOÁN TIẾN HÓA
Ngành: Công nghệ thông tin
Chuyên ngành: Công nghệ phần mềm
Mã số: 60.48.10
LUẬN VĂN THẠC SĨ CÔNG NGHỆ PHẦN MỀM
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. BÙI THU LÂM
Hà Nội, 2013
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của bản thân, được xuất phát từ
yêu cầu phát sinh trong công việc để hình thành hướng nghiên cứu. Các số liệu
có nguồn gốc rõ ràng tuân thủ đúng nguyên tắc và kết quả trình bày trong luận
văn được thu thập được trong quá trình nghiên cứu là trung thực chưa từng được
ai công bố trước đây.
Hà Nội, tháng 9 năm 2013
Tác giả luận văn
Phan Minh Hải
2
LỜI CẢM ƠN
Luận văn được thực hiện dưới sự hướng dẫn của TS. Bùi Thu Lâm – Học viện
Kỹ thuật Quân sự. Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy đã hướng dẫn và
có ý kiến chỉ dẫn quý báu trong quá trình em làm luận văn. Em xin chân thành
cảm ơn các Thầy giáo trong bộ môn Công nghệ phần mềm. Em cũng xin cảm ơn
các thầy cô giáo trong Khoa, cán bộ thuộc phòng Khoa học và Đào tạo sau Đại
học, Trường Đại học Công nghệ đã tạo điều kiện trong quá trình học tập và
nghiên cứu tại Trường.
Cuối cùng xin bày tỏ lòng cảm ơn tới những người thân trong gia đình, bạn bè
đã động viên và giúp đỡ để tôi hoàn thành bản luận văn này.

2.4.3. Phương pháp phân cụm dựa trên mật độ 29
2.4.4. Phương pháp phân cụm dựa trên lưới 29
2.4.5. Phương pháp phân cụm dựa trên mô hình 30
2.4.6. Phương pháp phân cụm có dữ liệu ràng buộc 30
2.5. Một số thuật toán cơ bản trong phân cụm dữ liệu 31
2.5.1. Các thuật toán phân cụm phân hoạch 31
2.5.2. Các thuật toán phân cụm phân cấp 34
2.5.3. Các thuật toán phân cụm dựa trên mật độ 35
2.5.4. Các thuật toán phân cụm dựa trên lưới 38
2.5.5. Các thuật toán phân cụm dựa trên mô hình 40
2.5.6. Giải thuật phân cụm dựa trên giải thuật di truyền 41
CHƯƠNG 3 GIẢI THUẬT PHÂN CỤM DỰA TRÊN LAI GHÉP GIẢI THUẬT
DI TRUYỀN VÀ KMEANS 42
4
CHƯƠNG 4 CÀI ĐẶT VÀ THỬ NGHIỆM 42
4.1. Chuẩn bị dữ liệu 42
4.2. Kết quả và phân tích 43
4.2.1. Thí nghiệm với giải thuật Kmeans 43
4.2.2. Thí nghiệm với giải thuật Kmeans có sử dụng giải thuật di truyền 44
KẾT LUẬN 46
TÀI LIỆU THAM KHẢO 48
5
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
CDL Cụm dữ liệu
CNTT Công nghệ thông tin
CSDL Cơ sở dữ liệu
CX Lai ghép chu trình Cycle Crossover
DE Thuật tiến hóa vi phân
Differential Evolution
DL Dữ liệu

Hình 2.3: Cấu trúc phân cấp 28
Hình 2.4: Các cách mà các cụm có thể đưa ra 29
Hình 2.5: Các thiết lập để xác định ranh giới các cụm ban đầu 31
Hình 2.6: Tính toán trọng tâm của các cụm mới 31
Hình 2.7: Khái quát thuật toán CURE 33
Hình 2.8: Các cụm dữ liệu được khám phá bởi CURE 33
Hình 2.9: Hình dạng các cụm được khám phá bởi thuật toán DBSCAN 35
8
MỞ ĐẦU
Phân cụm dữ liệu là quá trình nhóm một tập 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 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 không giám sát (unsupervised
learning). Các Kỹ thuật phân cụm được ứng dụng rất nhiều trong các lĩnh vực tài
chính ngân hành để phân lọai các nhóm khách hàng khác nhau. 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 như phân loại và mô tả đặc điểm, có tác dụng phát hiện ra
các cụm.
Theo các nghiên cứu cho thấy thì hiện nay chưa có một phương pháp phân cụm
tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc của các
CSDL. Hơn nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc
của các CSDL, với mỗi cách thức biểu diễn khác nhau sẽ có một thuật toán phân
cụm phù hợp. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì
phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều
dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng
trong các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn
trong KPDL. Một điểm khác nữa là các hàm mục tiêu của các thuật toán phân
cụm như K-means thường tồn tại nhiều điểm tối ưu cục bộ. Do đó mà đề tài tập
trung vào tìm hiểu “Các kỹ thuật phân cụm trong khai phá dữ liệu sử dụng tính

thuật toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính
toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu.
Nói cách khác, mục tiêu của Khai phá dữ liệu là tìm kiếm các mẫu hoặc mô hình
tồn tại trong CSDL nhưng ẩn trong khối lượng lớn dữ liệu.

10
1.1.2. Quá trình khám phá tri thức
Hình 1.1: Quá trình KPTT
Bao gồm các bước sau:
Làm sạch dữ liệu (Data Cleaning): Loại bỏ dữ liệu nhiễu và dữ liệu không
nhất quán.
Tích hợp dữ liệu (Data Intergation): Dữ liệu của nhiều nguồn có thể được tổ
hợp lại.
Lựa chọn dữ liệu (Data Selection): Lựa chọn những dữ liệu phù hợp với
nhiệm vụ phân tích trích rút từ cơ sở dữ liệu.
Chuyển đổi dữ liệu (Data Transformation): Dữ liệu được chuyển đổi hay được
hợp nhất về dạng thích hợp cho việc khai phá.
Khai phá dữ liệu (Data Mining): Đây là một tiến trình cốt yếu trong đó các
phương pháp thông minh được áp dụng nhằm trích rút ra mẫu dữ liệu.
Đánh giá mẫu (Pattern Evaluation): Dựa trên một độ đo nào đó xác định lợi
ích thực sự, độ quan trọng của các mẫu biểu diễn tri thức.
Biểu diễn tri thức (Knowledge Presentation): Ở giai đoạn này các kỹ thuật
biểu diễn và hiển thị được sử dụng để đưa tri thức lấy ra cho người
dùng.
11
1.1.3. Quá trình khai phá dữ liệu
KPDL là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất, nó là giai
đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong CSDL chủ
yếu phục vụ cho mô tả và dự đoán.
Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những

o Phân tích sự phát triển và độ lệch (Evolution and deviation analyst)
o Phương pháp tìm kiếm (Search Method)
Có nhiều phương pháp khai phá dữ liệu được nghiên cứu ở trên, trong đó có ba
phương pháp được các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết
hợp, Phân lớp dữ liệu và Phân cụm dữ liệu.
1.1.5. Các lĩnh vực ứng dụng thực tiễn của KPDL
KPDL là một lĩnh vực mới phát triển nhưng thu hút được khá nhiều nhà nghiên
cứu nhờ vào những ứng dụng thực tiễn của nó. Sau đây là một số lĩnh vực ứng
dụng thực tế điển hình của KPDL:
- Phân tích dữ liệu và hỗ trợ ra quyết định
- Phân lớp văn bản, tóm tắt văn bản, phân lớp các trang Web và phân
cụm ảnh màu
- Chuẩn đoán triệu chứng, phương pháp trong điều trị y học
- Tìm kiếm, đối sánh các hệ Gene và thông tin di truyền trong sinh học
- Phân tích tình hình tài chính, thị trường, dự báo gía cổ phiếu trong tài
chính, thị trường và chứng khoán
- Phân tích dữ liệu marketing, khách hàng.
- Điều khiển và lập lịch trình
- Bảo hiểm
- Giáo dục
1.1.6. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL.
Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp cận
chính sau:
- Phân lớp và dự đoán (classification &prediction): Là quá trình xếp một đối
tượng vào một trong những lớp đã biết trước (ví dụ: phân lớp các bệnh nhân
theo dữ liệu hồ sơ bệnh án, phân lớp vùng địa lý theo dữ liệu thời tiết ). Đối
với hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây
quyết định (decision tree), mạng nơron nhân tạo (neural network), Hay lớp
bài toán này còn đươc gọi là học có giám sát - Học có thày (supervised
13

trên quan niệm cho rằng quá trình tiến hóa tự nhiên là quá trình hoàn hảo và hợp
lý nhất và tự nó đã mang tính tối ưu. Đây là một tiên đề đúng, không thể chứng
minh được nhưng phù hợp với thực tế khách quan. Trong tính tối ưu trong tự
nhiên thể hiện ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước nhờ hai quá
trình cơ bản là sinh sản và chọn lọc tự nhiên. Những cá thể nào phát triển thích
nghi với môi trường sẽ tồn tại và ngược lại, những cá thể nào không thích nghi
14
với môi trường sẽ bị đào thải. Sự thay đổi của môi trường sẽ tác động đến quá
trình tiến hóa và bản thân quá trình tiến hóa cũng có tác động và làm thay đổi
môi trường. Cá thể mới sinh ra trong quá trình tiến hóa nhờ vào sự lai ghép ở thế
hệ cha-mẹ. Một cá thể mới có thể mang những đặc tính của cha-mẹ ở thế hệ
trước (di truyền) hoặc mang những đặc tính mới hoàn toàn (đột biến). Di truyền
và đột biến là hai cơ chế quan trọng như nhau trong quá trình tiến hóa mặc dù
xác suất để xảy ra hiện tượng đột biến nhỏ nhiều (hàng chục đến hàng trăm lần
tùy từng quá trình) so với hiện tượng di truyền. Mặc dù cơ chế là ngẫu nhiên
nhưng thuật toán di truyền không phải là một thuật toán ngẫu nhiên. Thuật toán
khai thác và tận dụng được một cách hiệu quả thông tin quá khứ để có được
những kết quả mới đạt kết quả như mong muốn. Các cải tiến trong việc sử dụng
thuật toán di truyền đã làm tăng thêm hiệu quả của việc sử dụng thuật toán trong
các bài toán phức tạp. Điều này thể hiện ở việc giảm thời gian tính toán ngày
càng hiệu quả mà ta sẽ tìm hiểu cụ thể hơn ở dưới đây.
1.2.1.1. Các quá trình cơ bản trong thuật toán di truyền
a, Mã hóa dữ liệu: hay còn gọi là biểu diễn di truyền cho lời giải của bài toán:
Đây là bước đầu tiên và rất quan trọng đối với việc tìm ra lời giải của bài toán.
Mỗi lời giải của bài toán được biểu diễn dưới dạng một chuỗi ký tự hữu hạn hay
còn được gọi là một nhiễm sắc thể. Các ký tự có thể là số nhị phân, số thập
phân, … tùy vào từng bài toán cụ thể. Trong quá trình này, việc mã hóa cái gì,
mã hóa như thế nào, trật tự các thành phần trong nhiễm sắc thể ra sao,… luôn là
những thách thức cho những người giải bài toán.
b, Khởi tạo quần thể (xây dựng tập hợp nghiệm ban đầu) có thể ngẫu nhiên

Hình 1.3: Lai ghép hai cá thể
Tuy nhiên trong quá trình tồn tại và phát triển, thuật toán di truyền đã được bổ
sung rất nhiều các phương pháp lai ghép để nhằm thích ứng với nhiều kiểu bài
toán và cũng là để tăng hiệu quả của thuật toán. Có thể kể một số phép lai cải
tiến như sau:
Lai ghép có xét tới các đặc tính trội và lặn trong tự nhiên. Các đặc tính này được
quy định trước trong khi biểu diễn cấu trúc nhiễm sắc thể. Bằng việc xem xét tới
các đặc tính trội-lặn, quá trình sản sinh ra các "quần thể chất lượng tốt" sẽ nhanh
hơn và do đó thời gian tính toán cũng được rút ngắn.
o Lai ghép từng phần: Việc giữ lại những đoạn mã đã "tối ưu" trong nhiễm
sắc thể cũng là một cách để quá trình lai ghép trở nên hiệu quả hơn
o Lai ghép có trật tự
o Lai ghép dựa trên vị trí
o Lai ghép chu trình
o Lai ghép thứ tự tuyến tính
16
o Lai ghép đa điểm: Với phương pháp này, chúng ta có thể cho 2 cá thể lai
ghép ở 2 hay nhiều điểm lai ghép. Phương thức này làm cho thuật toán trở
nên linh hoạt hơn, nhờ đó các thế hệ cá thể con cũng sẽ có chất lượng tốt
hơn.
e, Quá trình đột biến là quá trình cá thể con mang một bay một số tính trạng
không có trong mã di truyền của cha-mẹ. Quá trình này xảy ra với xác suất p
2
(nhỏ hơn nhiều so với p
1
) có thể được mô tả như sau:
o Chọn ngẫu nhiên một cá thể bất kỳ trong quần thể
o Chọn một gen bất kỳ của cá thể vừa chọn
o Thay đổi giá trị gen đó (đối với cách mã hóa gen theo số nhị phân thì quá
trình thay đổi giá trị là đổi giá trị từ 0 thành 1 hoặc từ 1 thành 0) rồi trả về

khoảng 0,5-0,95 nhưng giá trị thông thường của xác suất đột biến thấp hơn
nhiều, chỉ ở khoảng 0,001-0,05. Điều này cũng phản ánh đúng xác suất xảy ra
hai quá trình trong thực tế.
Từ một ví dụ trên đây có thể tính được một số ưu điểm của thuật toán di truyền
như phương pháp này tìm từ một quần thể các điểm chứ không phải một điểm.
Điều này làm cho việc giải các bài toán đa mục tiêu hay việc tìm một tập hợp
các phương án lân cận nghiệm trở nên dễ dàng. Thêm vào đó, việc đánh giá
thông tin bằng hàm mục tiêu chứ không dùng đạo hàm hay các tri thức bổ sung
cũng là một ưu điểm của thuật toán.
18
Hình 1.5: Sơ đồ quá trình tính toán của thuật toán di truyền
Nhận xét cụ thể các bước trong lưu đồ trên:
Bước 1: Khởi tạo/lựa chọn các thông số cho quá trình tính toán: Bước này người
lập trình tính toán phải lựa chọn các thông số như: Số lượng cá thể trong quần
thể, cách thức hóa bài toán cần tính toán dưới dạng các nhiễm sắc thể (độ dài
của nhiễm sắc thể, kiểu số biểu diễn dữ liệu,…), số thế hệ tính toán, xác suất lai
ghép, xác suất đột biến, hàm thích nghi,…
Bước 2: Khởi tạo quần thể ban đầu: xác định bằng phương pháp tạo số ngẫu
nhiên để tạo giá trị cho các nhiễm sắc thể cho quần thể ban đầu. Tùy vào cách
biểu diễn của các nhiễm sắc thể mà ta chọn phương pháp tạo số ngẫu nhiên phù
hợp
19
Bước 3: Đánh giá các nhiễm sắc thể bằng hàm thích nghi đã xác định ở bước 1.
Trong bước này, ngoài việc đánh giá các nhiễm sắc thể riêng rẽ, chúng ta còn có
thể đánh giá độ thích nghi của một nhiễm sắc thể hay cả quần thể. Nếu một
nhóm hay cả quần thể có độ thích nghi "trung bình" (theo tiêu chí của từng
trường hợp của người lập trình) thấp thì có thể loại nhóm nhiễm sắc thể hay
quần thể đó ra khỏi quá trình di truyền.
Bước 4: Thực hiện quá trình di truyền thông qua các cơ chế lai ghép và đột biến.
Có thể thực hiện lần lượt hai quá trình này hoặc thực hiện đồng thời theo các

1.2.2.2. Xây dựng sơ đồ thuật toán
Sơ đồ thuật toán được trình bày trên hình 1.6
Hình 1.6: Sơ đồ thuật toán tiến hóa vi phân
Cũng như thuật toán GA đã trình bày ở trên, thuật toán tiến hoá vi phân cũng
khởi tạo quần thể các điểm ban đầu P(t) theo quy luật ngẫu nhiên phân bố đều
trong miền xác định bài toán sau khi cho các thông số ban đầu (khối 1, 2). Mỗi
phần tử trong quần thể ban đầu này cũng được DE thực hiện trên miền tham số
thực với công thức sau [5]:
21
Cho tham
số ban đầu
Tạo quần thể ban
đầu P(t)
Đột biến
Lai ghép
Chọn lọc
Tái sinh
Sth > [Sth]
Eps < [Eps]
Kết thúc
In kết quả
Đúng
Đúng
Sai
Sai
3
2
1
5
4

v = x + F*(x - x )
ij ro,j r1,j r2,j
(2)
Trong đó:
r0, r1, r2 - các giá trị ngẫu nhiên khác nhau được chọn theo luật phân bố
đều trong khoảng [0, n_popsize];
F - hằng số tỷ lệ.
F ∈ (0,1) là một số thực dương điều khiển mức độ tiến hóa của quần thể.
Trong quá trình lai ghép (khối 4), DE cũng tiến hành lai ghép theo kiểu cặp đôi
(dual crossover) tạo ra một quần thể lai ghép [U] có giá trị các tham số được lựa
chọn ngẫu nhiên từ các quần thể [X] và [V] ban đầu. Kỹ thuật lai ghép sử dụng
trong lập trình của DE có thể biểu diễn như sau:
v ; if rand(0,1) £ C or j = rand(j)
r
ij
u =
x ; otherwise
ij
ij





(3)
Trong đó:
C
r
- xác suất lai ghép.
C

với các sai lệch của quá trình tính. Biểu thức điều kiện dừng của thuật toán DE
có thể viết như sau:
N
p
F(x)
i
i=1
F(x) - £ε;
min
N
p
∑
(5)
Trong đó:
F(x)
min
- giá trị nhỏ nhất của hàm mục tiêu tại thế hệ xét;
F(x)
i
- giá trị hàm mục tiêu của cá thể thứ i;
N
p
(= n_popsize) - tổng số cá thể trong quần thể đang xét;
ε - giá trị vô cùng bé cho trước (thường chọn = 10
-4
÷ 10
-6
tùy theo loại bài
toán).
1.3. Kết luận

Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho phân cụm
đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc
thiếu đầy đủ, vì vậy cần phải xây dựng chiến lược cho bước tiền xử lí dữ liệu
nhằm khắc phục hoặc loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích
cụm dữ liệu. Nhiễu ở đây được hiểu là các đối tượng dữ liệu không chính xác,
không tường minh hoặc là các đối tượng dữ liệu khuyết thiếu thông tin về
24
một số thuộc tính, Một trong các kỹ thuật xử lí nhiễu phổ biến là việc
thay thế giá trị các thuộc tính của đối tượng nhiễu bằng giá trị thuộc
tính tương ứng. Ngoài ra, dò tìm phần tử ngoại lai cũng là một trong những
hướng nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác
định một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ liệu trong
CSDL, tức là các đối tượng dữ liệu không tuân theo các hành vi hoặc mô hình
dữ liệu nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả của phân
cụm.
Mục tiêu của phân cụm là xác định được bản chất nhóm trong tập DL chưa có
nhãn. Nó có thể được chỉ ra rằng không có tiêu chuẩn tuyệt đối “tốt” mà
có thể không phụ thuộc vào kết quả phân cụm. Vì vậy, nó đòi hỏi người sử
dụng phải cung cấp tiêu chuẩn này, theo cách mà kết quả phân cụm sẽ đáp ứng
yêu cầu.
Theo các nghiên cứu cho thấy thì hiện nay chưa có một phương pháp phân cụm
tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc CDL. Hơn
nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc của các
CDL, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng một thuật toán
phân cụm phù hợp. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở,
vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều
dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng
tăng trong các hệ quản trị dữ liệu và đây cũng là một trong những thách
thức lớn trong lĩnh vực KPDL.
2.2. Các ứng dụng của phân cụm dữ liệu