Trước tiên em gửi lời cảm ơn chân thành sâu sắc tới các thầy cô giáo ở Vi , các thầy cô
trong trường
ph à N đã tận tình truyền đạt, giảng dạy cho em những kiến thức, kinh nghiện quý báu trong suốt
thời gian qua.
Đặc biệt em xin gửi lời cảm ơn đến PGS.TS Lễ Bá D đã tận tình giúp đỡ, trực tiếp chỉ bảo
em trong suốt thời gian làm luận văn. Trong thời gian làm việc với Thầy, em không những tiếp thu
thên nhiều kiến thức bổ ích mà còn học được tinh thần làm việc, thái độ nghiên cún khoa học
nghiêm túc, hiệu quả. Đây là những điều rất cần thiết cho em trong quá trình học tập và công tác.
Sau cùng xin gửi lời cảm ơn chân thành tới gia đình, bạn bè đã động viên, đóng góp ý kiến
và giúp đỡ trong quá trình học tập, nghiên cún và hoàn thành đề tài này.
Hà N
Học viên
Nguy
L
Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là trung thực và
không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện
luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc.
Học viên
Nguy Th
м
1.1.1.
41
2.1.5.
2.1.6.
2.1.7. DANH M
2.1.8.
2.1.9. DANH M CÁC HÌNH MINH H
2.1.5. CSDL 2.1.6. Cơ sở dữ liệu
2.1.7. PCDL 2.1.8. Phân cụm dữ liệu
2.1.9. KPDL 2.1.10. Khai phá dữ liệu
2.1.11. B

thường
2.1.67.
Hình
2.1.68. Phân tử nơron chiên thăng BMU
2.1.69.
Hình
2.1.70. Các vùng lân cận
2.1.71.
Hình
2.1.72. Ư- matrix biêu diên cho SOM
2.1.73.
Hình 3.1
2.1.74. Giải nén file ‘PHANCUMANH.rar’ và
mở file ‘ setup_PH ANCUM ANH’
2.1.75.
Hình 3.2
2.1.76. Sau đó vào Debug và cài đặt file
‘setup.exe’
2.1.77.
Hình 3.3
2.1.78. Băt đâu quá trình cài đặt
2.1.79.
Hình 3.4
2.1.80. Close đê hòa tât quá trình cài đặt
2.1.81.
Hình 3.5
2.1.82. Chương trình đã cài đặt xong và file chạy
chương trình nằm trên màn hình destop
‘WindowsFormsApplicationl .exe’
2.1.83.

2.1.32. Thiết lập đế xác định danh giới các
cụm ban đầu
2.1.33.
Hình 1.4
2.1.34. Tính toán trọng tâm các cụm mới
2.1.35.
Hình 1.5
2.1.36.Khái quát
thuật toán Cure
2.1.37.
Hình 1.6
2.1.38. Các cụm dừ liệu được khám phá bởi
thuật toán Cure
2.1.39.
Hình 1.7
2.1.40. Hình dạng các cụm được tạo bởi thuật
toán DBSCAN
2.1.41.
Hình 1.8
2.1.42. Các cách mà cụm có thê đưa ra
2.1.43.
Hình 2.1
2.1.44.Mô hình nơron
sinh học
2.1.45.
Hình 2.2
2.1.46. Mô hình nơron nhân tạo cơ bản
2.1.47.
Hình 2.3
2.1.48. Mô hình mạng nơron 3 lớp

trước đó. Dần đến một nhu cầu thực tế là cần có các phương pháp phân cụm, xử lí dữ liệu thu thập
được để làm căn cứ ra quyết định.
2.1.14. Phân cụm dữ liệu (PCDL) 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 là một ví dụ của phương
pháp học không có thầy. Không giống như phân lớp 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. Yì thế, có thế coi phân cụm dữ liệu là một cách học
bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví dụ
2.1.15. Hiện nay, các phương pháp phân cụm đã và đang được phát triển [7] và áp dụng
nhiều trong các lĩnh vực khác nhau và đã có một số nhánh nghiên cứu được phát triển trên cơ sở
của các phương pháp đó như:
2.1.16. Phân cụm thống kê: Dựa trên các khái niệm phân tích hệ thống, nhánh nghiên cứu
này sử dụng các độ đo tương tự để phân hoạch các đối tượng, nhưng chúng chỉ áp dụng cho các dữ
liệu có thuộc tính số.
2.1.17. Phân cụm khái niệm: Kỹ thuật này được phát triến áp dụng cho dữ liệu hạng mục,
chúng phân cụm các đối tượng theo các khái niệm mà chúng xử lí.
4
2.1.18. Phân cụm mờ: Sử đụng kỹ thuật mờ để PCDL. Các thuật toán thuộc
loại này chỉ ra lược đồ phân cụm thích họp với tất cả các hoạt động đời sống hàng
ngày, chúng chỉ xử các dữ liệu không chắc chắn [1], [3].
2.1.19. Mạng noron cho phân cụm [1], [4].
2.1.20. Một trong số các trở ngại gặp phải khi ứng dụng mạng nơ-ron cho phân
cụm cần phải có sự hỗ trợ đầy đủ kiến thức lý thuyết và phương pháp ứng dụng.
Trong khi các nghiên cún về mạng nơ-ron nhân tạo thường úng dụng vào một bài
toán cụ thể, kết quả nghiên cún khó có khả năng kế thừa, phát triển để ứng dụng
rộng rãi cho các bài toán tương tự. Vì vậy việc nghiên cứu chuyên sâu, đầy đủ và
mang tính ứng dụng thực tiễn cao là hết sức cần thiết. Với các lí do trên em chọn đề
tài “S noron cho phân c
2.1.21.li à
2. M ên c

thành quy trình với các bước thực hiện cụ thể cho việc giải bài toán phân cụm dữ liệu
bằng mạng nơ-ron.
2.1.30. т
1.1. Khái ni vàm êu с
1.1.1. Khái ni
2.1.31. 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.
2.1.32. Phân cụm dữ liệu là một kỹ thuật trong Khai phá dữ liệu 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 quan trọng trong tập dữ
liệu lớn tò đó cung cấp thông tin tri thức hũu ích cho việc ra quyết định.
2.1.33. Không giống như phân lóp 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 trong khi phân lớp dữ liệu là học bằng ví dụ
2.1.34. 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ư là phân loại và mô tả đặc
điểm, có tác dụng trong việc phát hiện ra các cụm. Phân cụm dữ liệu đang là vấn đề
mở và khó vì người ta cần phải đi giải quyết nhiều vấn đề cơ bản về dữ liệu để nó
phù họp với nhiều dạng dữ liệu khác nhau như dữ liệu chứa nhiễu do quá trình thu
thập thiếu 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ề môt số thuộc tính hoặc dữ liệu hỗn họp đang ngày càng tăng trong các
hệ quản trị dữ liệu [7].
1.1.2. M êu с
2.1.35. Mục tiêu của phân cụm dữ liệu là xác định được
bản chất nhóm trong tập dữ liệu chưa có nhãn. Nó có
thế là không có tiêu chuấn tuyệt đối “tốt” mà
2.1.36. 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 phân cụm một cách rõ ràng theo cách mà kết
quả phân cụm sẽ đáp ứng yêu cầu.
2.1.37. Hiện nay chưa có một phương pháp phân cụm tồng quát nào có thể

2.1.43. Khả năng thích nghi với dữ liệu nhiễu: Hầu hết những CSDL thực đều
chứa đựng dữ liệu ngoại lai, dữ liệu lỗi, dữ liệu chưa biết hoặc dữ liệu sai. Một số
thuật toán phân cụm nhạy cảm với dữ liệu như vậy và có thể dẫn đến chất lượng
phân cụm thấp. ít nhạy cảm với thứ tự của các dữ liệu vào: Một số thuật toán phân
cụm nhạy cảm với thứ tự của dữ liệu vào, ví dụ như với cùng một tập dữ liệu, khi
được đưa ra với các thứ tự khác nhau thì với cùng một thuật toán có thể sinh ra các
cụm rất khác nhau. Do đó, việc quan trọng là phát triến các thuật toán mà ít nhạy
cảm với thứ tự vào của dữ liệu.
2.1.44. Số chiều lớn: Một CSDL hoặc một kho dữ liệu có thể chứa một số
chiều hoặc một số các thuộc tính. Nhiều thuật toán phân cụm áp dụng tốt cho dữ liệu
với số chiều thấp, bao gồm chỉ từ hai đến 3 chiều. Người ta đánh giá việc phân cụm
là có chất lượng tốt nếu nó áp dụng được cho dữ liệu có từ 3 chiều trở lên. Nó là sự
thách thức với các đối tượng dữ liệu cụm trong không gian với số chiều lớn, đặc biệt
vì khi xét những không gian với số chiều lớn có thể rất thưa và có độ nghiêng lớn.
2.1.45. Phân cụm ràng buộc: Nhiều ứng dụng thực tế có thể cần thực hiện
phân cụm dưới các loại ràng buộc khác nhau. Một nhiệm vụ đặt ra là đi tìm những
nhóm dữ liệu có trạng thái phân cụm tốt và thỏa mãn các ràng buộc.
2.1.46. Dễ hiểu và dễ sử dụng: Người sử dụng có thể chờ đợi những kết quả
phân cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể cần được
giải thích ý nghĩa và ứng dụng rõ ràng. Với những yêu cầu đáng lưu ý này, nghiên
cứu của ta về phân tích phân cụm diễn ra như sau: Đầu tiên, ta nghiên cứu các kiểu
dữ liệu khác và cách chúng có thể gây ảnh hưởng tới các phương pháp phân cụm.
Thứ hai, ta đưa ra một cách phân loại chung trong các phương pháp phân cụm. Sau
đó, ta nghiên cứu chi tiết mỗi phương pháp phân cụm, bao gồm các phương pháp
phân hoạch, phân cấp, dựa trên mật độ, Ta cũng khảo sát sự phân cụm trong không
gian đa chiều và các biến thể của các phương pháp khác.
1.1.4. Các kỉ à các thu c tính trong phân c
2.1.47. Thuật toán phân cụm dữ liệu có rất nhiều kiểu dữ liệu. Một thuộc tính
duy nhất có thế được có như nhị phân, rời rạc, hoặc liên tục. Thuộc tính nhị phân có
chính xác hai giá trị, như là đúng hoặc sai. Thuộc tính rời rạc có một số hữu hạn các

được xác định bằng các metric khoảng cách như sau:
2.1.59. \ / q
2.1.60. Khoảng cách Minskowski: d ( x y ) { " \ ■ y. \
q
) , trong đó q là
sô
2.1.61. /1 '
2.1.62.tự nhiên dương.
2.1.63. Khoảng cách Euclide:í/(x y) \
n
(
đây là trườnghợp đặc
2.1.64.V/ 1
2.1.65.biệt của khoảng cách Minskowski trong trường họp q=2.
2.1.66.n
2.1.67. Khoảng cách Manhattan: d { x , y ) \
X
ị ỵ . \ , đây là trường họp đặc
2.1.68.biệt của khoảng cách Minskowski trong trường hợp q= 1.
2.1.69. Khoảng cách cực đại: d ( x , y ) M a x Ị J I
X
ị y. I, đây là trường họp
của
2.1.70. khoảng cách Minskowski trong trường họp q->
.
2.1.71. + Thuộc tính tỉ lệ (Ratio Scale): là thuộc tính khoảng nhưng được xác
định một cách tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc cân
nặng lấy điểm 0 làm mốc. Có nhiều cách khác nhau để tính độ tương tự giữa các
thuộc tính tỷ lệ.
2.1.72. Trong các thuộc tính dữ liệu

c D

2
(X .) đạt giá trị tối thiểu.
2.1.83.i \ ỉ m
1
2.1.84. Với mị là trọng tâm của cụm Cj, D là khoảng cách
giữa hai đối tượng.
2.1.85.
2.1.86.
2.1.87.
2.1.88.
2.1.89.
2.1.90.
2.1.91.
2.1.92.
2.1.93.
2.1.94.
2.1.95.
2.1.96. Hình 1.4: Tính toán tr
2.1.97. Thuật toán phân hoạch K-means do MacQeen đề xuất trong lĩnh vực
thống kê năm 1967, mục đích của thuật toán K-means là sinh ra k cụm dữ liệu {Ci,
c
2
, .,CkỊ từ một tập dữ liệu chứa n đối tượng trong không gian d chiều Xi = (Xji Xj2,
. . X j d ) 0' 1, n ), sao cho hàm tiêu chuẩn :
2.1.98. E X c. D
2
( x m ị )
2.1.99. / 1

đối.
2.1.112. Nhận xét: Độ phức tạp của thuật toán là o T k n với T là số lần
lặp, n số đối tượng của tập dữ liệu đưa vào.
2.1.113. Độ phức tạp nhỏ: O(nkd.t), với :d là số chiều, t số vòng lặp. K-
means phân tích phân cụm đơn gỉản nên có thẻ áp dụng đối với tập dữ Hậu lớn.
2.1.114. K-means không có khả năng tìm ra các cụm không lồi hoặc các
cụm có hình dạng phức tạp, chỉ áp dụng với dữ liệu số. Nó không khắc phục được
nhiễu và các phần tử ngoại lai.
2.1.115. Chất lượng phân cụm phụ thuộc vào nhiều tham số đầu vào
như: số cụm k và k trọng tâm khởi tạo ban đầu.
2.1.116. Số lượng và các tham số là do người dùng nhập, nên nếu đầu
vào khác nhau thì kết quả các cụm sẽ khác nhau
1
2.1.117. -tâm:
2.1.118. Ý tưởng: Thuật toán K-tâm phân cụm dữ liệu hỗn hợp là mở
rộng của thuật toán К-means cho dữ liệu hỗn họp trong đó có sử dụng khái niệm
Mode của dữ liệu hỗn hợp, khi đã mở rộng các miền giá trị của thuộc tính có thứ tụ1
và xác định khoảng cách giữa các đối tượng.
2.1.119. Thuật toán này hội tụ sau một số hữu hạn bước lặp tới điểm
cực tiểu địa phương của hàm p như sau:
2.1.120.(2.2)
2.1.121. Ta xét D là tập N đối tượng X ‘ f , trong đó (x
l
xy ,x
l
m
,x
l
2.1.122. là phần tử của quan hệ r trên lược đồ quan hệ R = {Aị, , An} và x)
Dom(Aj) với mỗi j m là các giá trị thực còn với ml j n là các giá trị định danh.

(2.3)
2.1.134. Nếu Aj là thuộc tính
thứ tự và DOM(Aj) = với a ) a
2
j
a ) ,
2.1.135. ta lấy một hàm đơn điệu fỊ: DOM(Aj)—► [0,1] sao chof j ( a ' j )
0; f j ( a
k
j ) 1
2.1.136. (Hàm này có thể là: /. { а . ) -—- ). Khi đó dj(x,y)= I fj(x) = fj(y) I
(2.4)
2.1.137. J J k ì
2.1.138. NếuAj là dữ liệu định danh thì
dj(x,y)= 0
k h í : x y
(2.5)
2.1.139. 1 k h i : X
V
2.1.140. Định nghĩa khoảng cách giữa hai đối tượng dữ liệu hỗn hợp:
2.1.141. : Gi X = (xb , xn) và у =
(yi, , Уп) là haiđối tượng dữ liệu
2.1.142. hỗn hợp trên D, khoảng cách d(x, y) được
1
tính bởi công thức:
2.1.143. d ( x , y ) P 2 d 2 ( x y )
(2.6)
2.1.144. \ j I
J J 1 1
2.1.145. Trong đó các dj (Xj, Ỵj) được tính theo các công thức (2.3

với thuật toán di truyền hoặc khởi tạo tâm ban đầu bằng phương pháp chuyên gia
(theo cách nửa giám sát).
2.1.162. Thu
2.1.163. Thuật toán này là sự mở rộng của K-means, đế khắc phục được
dữ liệu nhiễu hoặc các phần tử ngoại lai. PAM sử dụng các đối tượng medoid để biểu
diễn cho các cụm dữ liệu, một đối tượng medoid là đối tượng đặt tại vị trí trung tâm
nhất bên trong của mỗi cụm.
2.1.164. Xác định medoid: Chọn k đối tượng medoid bất kỳ. Sau mỗi
bước thực hiện, PAM cố gắng hoán chuyển giữa đối tượng medoid Om và một đối
tượng Op không phải là medoid, miễn là sự hoán chuyển này nhằm cải tiến chất
lượng của phân cụm, quá trình này kết thúc khi chất lượng phân cụm không thay đổi.
2.1.165. Ngoài ra, phân cụm phân hoạch còn có thêm một số thuật toán
CLARA, thuật toán CLARANS.
1.2.2. Các thu toán trong phân c
2.1.166. Thu
2.1.167. Phân cụm phân cấp sắp xếp một tập dữ liệu đã cho thành một
cấu trúc có dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Cây
phân cụm có thế được xây dựng theo hai phương pháp tông quát: Phương pháp Top-
down và phương pháp Bottom-up.
2.1.168. cf) ( Draw random sample ) cfV' Partition sample ) (Partially
ctuMCT partitions)
2.1.169. <^3 { L iibrl ill tli\k ) (rim

ter partial dusters )
2
<^3 f Eliminate outliers 1
2.1.170.Hình 1.5: Khái quát thu
2.1.171. Thuật toán CURE được thực hiện như sau:
2.1.172. Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu. Phân hoạch
mẫu này thành nhiều nhóm dữ liệu có kích thước bàng nhau.

2.1.183. Tư tưởng:
2.1.184. Tìm các đối tượng có số đối tượng láng giêng lớn hơn một
ngưỡng tối thiểu. Mỗi ngưỡng được xác định bằng tập tất cả các đối tượng liên thông
mật độ với các láng giêng của nó.
2.1.185. Thuật toán:
2.1.186. Chọn một đối tượng p tùy ý.
2.1.187. Lấy tất cả các đối tượng mật độ đến được từ p với Eps và
MinPts
2.1.188. Neu p là điểm nhân tạo thì tạo ra một cụm theo Eps và MinPts
2.1.189. Neu p là một điểm biên, không có điểm nào là mật độ đến
được mật độ từ p và DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu.
2.1.190. Quá trình tiếp tục cho đến khi tất cả các đối tượng được xử lý.
2
2.1.191. Nếu ta chọn sử dụng giá trị toàn cục Eps và MinPts, DBSCAN
có thế hòa nhập hai cụm thành một cụm nếu mật độ của hai cụm gần bằng nhau. Độ
phức tạp của tính toán trung bình của mỗi truy vấn là O(nlogn).
2.1.192.
2.1.193. Hình 1.7: Hình d
2.1.194. Ngoài thuật toán DBSCAN ra còn có thuật toán OPTICS, thuật
toán DENCLUE.
1.2.4. Phân c
2.1.195. Ý ng: cách tiếp cận dựa trên lưới này không di chuyển các đối
tượng trong các ô mà xây dựng nhiều mức phân cấp của nhóm các đối tượng trong
một ô. Các cụm không dựa trên độ đo khoảng cách mà nó được quyết định bởi một
tham số xác định trước, phương pháp này chủ yếu tập trung áp dụng cho lóp dữ liệu
không gian.
2.1.196. : Thời gian xử lý nhanh và độc lập với số đối tượng dữ
liệu trong tập dữ liệu ban đầu. Thay vào đó là chúng phụ thuộc vào số ô trong mỗi
chiều của không gian lưới.
2.1.197. Thu

2.1.109. 2.1.110.
liên quan hoặc không liên quan.
2.1.201. B4: nếu lớp này là lớp dưới cùng, chuyển sang bước 6; nếu
khác thì chuyên sang bước 5.
2.1.202. B5: duyệt xuống dưới của cấu trúc cây phân cấp một mức.
Chuyển sang B2 cho các ô mà hình thành các ô liên quan của lớp có mức cao hơn.
2.1.203. B6: Neu đặc tả câu truy vấn, chuyển B8; Neu không chuyển
sang B7.
2.1.204. B7: Truy lục dữ liệu vào trong các ô liên quan và thực hiện xử
lý. Trả lại kết quả phù hợp yêu cầu truy vấn. Chuyển sang B9.
2.1.205. B8: Tìm thấy các miền có các ô liên quan. Trả lại miền mà phù
hợp với yêu cầu của truy vấn. chuyến sang B9.
2.1.206. B9: Dừng.
2.1.207. Ngoài thuật toán STING ra còn có thêm thuật toán phân cụm
dựa trên lưới là CLIQUE có khả năng áp dụng tốt với dữ liệu đa chiều, nhưng lại
nhạy cảm với thứ tự của dữ liệu vào. Độ phức tạp của nó là O(n).
1.2.5. Phân c ên mô hình
2.1.208. Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của
các tham số mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thế sử
dụng chiến lược phân cụm phân hoạch hoặc chiến lược phân cụm phân cấp, dựa trên
cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách mà chúng tinh chỉnh
các mô hình này để nhận dạng ra các phân hoạch. Các thuật toán áp dụng theo
phương pháp này:
2.1.209. Thu : là sự mở rộng của K-means, nó
các đối tượng cho
2.1.210. các cụm đã cho theoxác suất phân phốithànhphần của đối
tượng đó. Phân
2
2.1.211. phối xác suất được sử dụng là phân phối xác suất Gaussian với mục
đích là khám phá lặp các giá trị tốt cho các tham số của nó bằng hàm tiêu chuẩn là