1
LỜI CẢM ƠN
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ện Công nghệ thông tin Việt Nam, các thầy cô trong trường Đại học sư
phạm Hà Nội 2 đã 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ũng đã 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ứu 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ứu và hoàn
thành đề tài này.
Hà Nội, tháng 11 năm 2013
Học viên
Nguyễn Thị Hồng Thu
2
LỜI CAM ĐOAN
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ễn Thị Hồng Thu
3
MỤC LỤC
LỜI CẢM ƠN .................................................................................................. 1
LỜI CAM ĐOAN ............................................................................................ 2
MỤC LỤC ........................................................................................................ 3
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ................................... 5
DANH MỤC CÁC HÌNH MINH HỌA......................................................... 5
MỞ ĐẦU .......................................................................................................... 7
CHƯƠNG I: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU.......................... 10
1.1. Khái niệm và mục tiêu của phân cụm dữ liệu .......................................... 10
1.1.1. Khái niệm về phân cụm dữ liệu ..................................................... 10
1.1.2. Mục tiêu của phân cụm dữ liệu ..................................................... 10
1.1.3. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu ............................ 11
1.1.4. Các kiểu dữ liệu và các thuộc tính trong phân cụm ..................... 13
1.2. Một số thuật toán trong phân cụm dữ liệu .............................................. 15
1.2.1. Các thuật toán trong phân cụm phân hoạch................................. 15
1.2.2. Các thuật toán trong phân cụm phân cấp..................................... 22
1.2.3.Các thuật toán phân cụm dựa trên mật độ .................................... 23
1.2.4. Phân cụm dựa trên lưới ................................................................ 25
1.2.5.Phân cụm dựa trên mô hình ........................................................... 26
1.2.6. Phân cụm có dữ liệu ràng buộc .................................................... 26
1.3. Phân cụm cụm mờ .................................................................................... 28
1.3.1. Tổng quan về phân cụm mờ .......................................................... 28
1.3.2. Các thuật toán phân cụm mờ ........................................................ 29
CHƯƠNG II: MẠNG NƠRON KOHONEN VÀ ỨNG DỤNG CHO
PHÂN CỤM DỮ LIỆU ................................................................................. 33
2.1. Giới thiệu chung về mạng nơron.............................................................. 33
2.1.1. Mô hình Nơron sinh học ............................................................... 33
2.1.2. Mô hình Nơron nhân tạo ............................................................... 35
2.1.3. Mô hình Mạng Nơron nhân tạo .................................................... 37
4
2.1.4. Đặc trưng của Mạng Nơron.......................................................... 41
2.1.5. Phân loại mạng ............................................................................. 42
2.1.6. Ứng dụng mạng nơron nhân tạo ................................................... 46
2.1.7. Kết luận ......................................................................................... 47
2.2. Mạng Nơron nhân tạo Kohonen (SOM- Self Organized Maps) .............. 47
2.2.1. Tổng quan về SOM ........................................................................ 48
2.2.2. Mô hình SOM ................................................................................ 49
2.2.3. Thuật toán của mạng SOM ........................................................... 50
2.2.4. Một vài biến thể của giải thuật SOM ............................................ 57
2.2.5. Một số ứng dụng của SOM ........................................................... 59
CHƯƠNG III: GIẢI BÀI TOÁN PHÂN CỤM ẢNH ỨNG DỤNG MẠNG
KOHONEN .................................................................................................... 60
3.1. Bài toán phân cụm ảnh ............................................................................. 60
3.1.1 Giới thiệu....................................................................................... 60
3.1.2. SOM cho phân cụm ảnh ................................................................ 61
Thiết kế mạng .................................................................................. 61
Thuật toán học mạng....................................................................... 62
3.2. Giới thiệu môi trường cài đặt................................................................... 64
3.3. Cài đặt và sử dụng .................................................................................... 64
3.3.1. Cài đặt ........................................................................................... 64
3.3.2. Sử dụng.......................................................................................... 69
3.4. So sánh SOM với các phương pháp phân cụm khác. ............................... 76
3.4.1. Thuật toán K-means ...................................................................... 73
3.4.2. Phân cụm mờ ................................................................................. 73
3.4.3. Mạng nơ ron Kohonen (SOM) ...................................................... 73
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................... 75
TÀI LIỆU THAM KHẢO ............................................................................ 77
5
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT
Cơ sở dữ liệu
Phân cụm dữ liệu
Khai phá dữ liệu
Phần tử nơron chiến thắng
MultiLayer Perception
Bidirectional Associative Memory
Self Organizing Map
Vector Quantization
Learning Vector Quantization
Minimal Spanning Tree
CSDL
PCDL
KPDL
BNU
MLP
BAM
SOM
VQ
LVQ
MST
DANH MỤC CÁC HÌNH MINH HỌA
Hình
Hình 1.1
Hình 1.2
Hình 1.3
Hình 1.4
Hình 1.5
Hình 1.6
Hình 1.7
Hình 1.8
Hình 2.1
Hình 2.2
Hình 2.3
Hình 2.4
Hình 2.5
Hình 2.6
Hình 2.7
Hình 2.8
Hình 2.9
Hình 2.10
Nội dung
Biểu đồ các dạng dữ liệu
Biểu đồ quy mô dữ liệu
Thiết lập để xác định danh giới các cụm ban đầu
Tính toán trọng tâm các cụm mới
Khái quát thuật toán Cure
Các cụm dữ liệu được khám phá bởi thuật toán Cure
Hình dạng các cụm được tạo bởi thuật toán DBSCAN
Các cách mà cụm có thể đưa ra
Mô hình nơron sinh học
Mô hình nơron nhân tạo cơ bản
Mô hình mạng nơron 3 lớp
Mô hình học giám sát
Mô hình học không giám sát
Mô hình mạng perceptron một lớp
Mô hình Mạng perceptron nhiều lớp
Mô hình mạng hồi quy một lớp
Cấu trúc của mạng Hopfield
Cấu trúc của mạng BAM
6
Hình 2.11
Hình 2.12
Hình 2.13
Hình 2.14
Hình 2.15
Hình 3.1
Hình 3.2
Hình 3.3
Hình 3.4
Hình 3.5
Hình 3.6
Hình 3.7
Hình 3.8
Hình 3.9
Hình 3.10
Mô hình Mạng Nơron Kohonen
Mô hình Mạng Nơron Kohonen thông thường
Phần tử nơron chiến thắng BMU
Các vùng lân cận
U- matrix biểu diễn cho SOM
Giải nén file ‘PHANCUMANH.rar’ và mở file
‘setup_PHANCUMANH’
Sau đó vào Debug và cài đặt file ‘setup.exe’
Bắt đầu quá trình cài đặt
Close để hòa tất quá trình cài đặt
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
‘WindowsFormsApplication1.exe’
Giao diện của chương trình
Nhấn nút chọn ảnh để phân cụm ảnh được chọn
Kết quả phân cụm ảnh vừa chọn
Phân cụm ảnh ngẫu nhiên với Ngang 20, dọc 30 và
ngưỡng là 500
Ngẫu nhiên với ngang 70, dọc 30, ngưỡng 50
7
MỞ ĐẦU
1. Lý do chọn đề tài
Trong bối cảnh ứng dụng công nghệ thông tin ngày càng tăng, dữ liệu
phát sinh từ hoạt động quản lý, kinh doanh, tổ chức ngày càng nhiều. Các
công ty, tổ chức cần phải nhanh chóng đưa ra các quyết định bằng cách xử lý
nhiều yếu tố với quy mô và tính phức tạp ngày càng tăng. Để có quyết định
chính xác nhất. Ngoài việc dựa trên các yếu tố liên quan trực tiếp đến vấn đề,
người ra quyết định còn dựa trên kinh nghiệm bản thân và thông tin có được
từ các hoạt động 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.
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. 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ụ…
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ư:
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ố.
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í.
8
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].
Mạng noron cho phân cụm [1], [4].
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ứu 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ứu 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ử dụng mạng noron cho phân cụm dữ
liệu và ứng dụng”.
2. Mục đích nghiên cứu
Tìm hiểu các đặc trưng của mạng nơ-ron nhân tạo, khả năng và các
nguyên tắc để ứng dụng thành công mạng nơ-ron nhân tạo trong thực tế. Tìm
hiểu về phân cụm dữ liệu. Nghiên cứu ứng dụng mạng nơ-ron nhân tạo vào
lớp bài toán phân cụm dữ liệu.
3. Nhiệm vụ nghiên cứu
Tìm hiểu nghiên cứu về mạng noron nhân tạo và phân cụm dữ liệu. Xây
dựng phần mềm cho phép người sử dụng mô phỏng và ứng dụng nhanh chóng
mạng noron nhân tạo để giải quyết các bài toán thuộc lớp bài toán phân cụm
dữ liệu.
4. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu là lớp bài toán phân cụm dữ liệu, sử dụng mạng
nơron nhân tạo. Phạm vi nghiên cứu là lý thuyết ứng dụng mạng nơ-ron nhân
tạo cho bài toán phân cụm dữ liệu. Ứng dụng mạng noron kohonen trong
phân cụm dữ liệu.
9
5. Phương pháp nghiên cứu
Phương pháp nghiên cứu tài liệu: nghiên cứu lý thuyết và ứng dụng
mạng nơron nhân tạo trong phân cụm dữ liệu.
Phương pháp thực nghiệm: đi sâu nghiên cứu ứng dụng mạng nơ-ron
nhân tạo bắt đầu từ bước chuẩn bị dữ liệu, bao gồm các kỹ thuật cho việc trích
chọn đặc trưng, làm sạch dữ liệu, tiền xử lý, kiến trúc mạng, cách huấn luyện
và kiểm tra mạng. Thực hiện phân tích ứng dụng mạng nơ-ron vào một số bài
toán của mỗi lớp bài toán. Từ các phân tích từng bài toán, tác giả xây dựng
thành quy trình, các chỉ dẫn mang tính ứng dụng thực tiễn cao có thể ứng
dụng nhanh chóng cho các bài toán tương tự của các lớp bài toán trên.
Xây dựng phần mềm mô phỏng mạng nơ-ron: phân tích, thiết kế phần
mềm hướng đối tượng với các tính năng cho phép người sử dụng thực hiện
giải các bài toán thực tế bằng mạng nơ-ron nhân tạo. Lập trình phần mềm,
phần mềm có giao diện trực quan chạy trên hệ điều hành Windows.
6. Giả thuyết khoa học
Đề tài làm rõ khả năng ứng dụng của mạng nơ-ron trong phân cụm dữ
liệu. Cách để xác định bài toán nào thích hợp để giải bằng mạng nơ-ron. Xây
dựng 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.
10
CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU
1.1. Khái niệm và mục tiêu của phân cụm dữ liệu
1.1.1. Khái niệm về phân cụm dữ liệ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 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.
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ụ …
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ục tiêu của phân cụm dữ liệu
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à
11
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.
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 chọn vẹn cho tất cả các dạng cấu trúc dữ liệu. Hơn nữa, các phương
pháp phân cụm cần có một cách thức biểu diễn cấu trúc của dữ liệu, và với
mỗi cách thức biểu khác nhau sẽ có tương ứng một thuật toán phân cụm phù
hợp.
1.1.3. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu
Phân cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ những
ứng dụng tiềm năng của chúng được đưa ra ngay chính những yêu cầu đặc
biệt của chúng. Sau đây là những yêu cầu cơ bản của phân cụm trong KPDL:
Có khả năng mở rộng: Nhiều thuật toán phân cụm dữ liệu làm việc tốt
với những tập dữ liệu nhỏ chứa ít hơn 200 đối tượng, tuy nhiên một cơ sở dữ
liệu lớn có thể chứa tới hàng triệu đối tượng. Việc phân cụm với một tập dữ
liệu lớn có thể làm ảnh hưởng tới kết quả. Vậy làm thế nào để chúng ta phát
triển các thuật toán phân cụm có khả năng mở rộng cao đối với các CSDL
lớn?
Khả năng thích nghi với các kiểu thuộc tính khác nhau: Nhiều thuật
toán được thiết kế cho việc phân cụm dữ liệu có kiểu khoảng (kiểu số). Tuy
nhiên, nhiều ứng dụng có thể đòi hỏi việc phân cụm với nhiều kiểu dữ liệu
khác nhau, như kiểu nhị phân, kiểu tường minh (định danh - không thứ tự), và
dữ liệu có thứ tự hay dạng hỗn hợp của những kiểu dữ liệu này.
Khám phá các cụm với hình dạng bất kỳ: Nhiều thuật toán phân cụm xác
định các cụm dựa trên các phép đo khoảng cách Euclidean và khoảng cách
Manhattan. Các thuật toán dựa trên các phép đo như vậy hướng tới việc tìm
kiếm các cụm hình cầu với mật độ và kích cỡ tương tự nhau. Tuy nhiên, một
12
cụm có thể có bất cứ một hình dạng nào. Do đó, việc phát triển các thuật toán
có thể khám phá ra các cụm có hình dạng bất kỳ là một việc làm quan trọng.
Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: Nhiều
thuật toán phân cụm yêu cầu người dùng đưa vào những tham số nhất định
trong phân tích phân cụm (như số lượng các cụm mong muốn). Kết quả của
phân cụm thường khá nhạy cảm với các tham số đầu vào. Nhiều tham số rất
khó để xác định, nhất là với các tập dữ liệu có lượng các đối tượng lớn. Điều
này không những gây trở ngại cho người dùng mà còn làm cho khó có thể
điều chỉnh được chất lượng của phân cụm.
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.
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.
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.
13
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 kiểu dữ liệu và các thuộc tính trong phân cụm
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 giá trị có thể, vì thế kiểu dữ liệu nhị phân là một trường hợp
đặc biệt của dữ liệu rời rạc. Quy mô dữ liệu chỉ ra tầm quan trọng tương đối
của các con số, cũng là một vấn đề quan trọng trong phân cụm dữ liệu. Vì vậy
dữ liệu được chia thành các kiểu như sau:
Hình 1.1 : Biểu đồ các dạng dữ liệu
14
Hình 1.2: biểu đồ quy mô dữ liệu
Bao gồm các kiểu dữ liệu:
+ Dữ liệu dựa trên kích thước miền:
Thuộc tính liên tục (Continuous Attribute): nếu miền giá trị của nó là
vô hạn không đếm được.
Thuộc tính rời rạc (DiscretteAttribute): Nếu miền giá trị của nó là tập
hữu hạn, đếm được.
Lớp các thuộc tính nhị phân: là trường hợp đặc biệt của thuộc tính rời
rạc mà miền giá trị của nó chỉ có 2 phần tử được diễn tả như: Yes / No hoặc
Nam/Nữ, False/true,…
+ Thuộc tính định danh (nominal Scale): đây là dạng thuộc tính khái
quát hoá của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân
biệt thứ tự và có nhiều hơn hai phần tử - nghĩa là nếu x và y là hai đối tượng
thuộc tính thì chỉ có thể xác định là x ¹ y hoặc x = y.
+ Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm
tính thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính
thứ tự thì ta có thể xác định là x ¹ y hoặc x = y hoặc x > y hoặc x yi thì ta nói x cách y một khoảng xi – yi tương
15
ứng với thuộc tính thứ i.Sau khi chuẩn hoá, độ đo phi tương tự của hai đối
tượng dữ liệu x, y được xác định bằng các metric khoảng cách như sau:
Khoảng cách Minskowski:
1/ q
n
q
d ( x, y ) = ( å | x i - y | )
i
i =1
, trong đó q là số
tự nhiên dương.
Khoảng cách Euclide: d ( x , y ) =
n
2
å ( x i - y i)
i =1
, đây là trường hợp đặc
biệt của khoảng cách Minskowski trong trường hợp q=2.
n
Khoảng cách Manhattan: d ( x, y ) = å | xi - yi | , đây là trường hợp đặc
i =1
biệt của khoảng cách Minskowski trong trường hợp q=1.
Khoảng cách cực đại: d ( x, y ) = Max n
| - | , đây là trường hợp của
i = 1 xi yi
khoảng cách Minskowski trong trường hợp q-> ¥.
+ 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ệ.
Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và
thuộc tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), thuộc
tính khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số (Numeric).
1.2. Một số thuật toán trong phân cụm dữ liệu
1.2.1. Các thuật toán trong phân cụm phân hoạch
Ý tưởng chung của thuật toán trong phân cụm phân cụm phân hoạch:
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 một phần tử dữ liệu. Thuật toán phân cụm phân hoạch tối ưu cục bộ
là sử dụng chiến lược ăn tham để tìm kiếm nghiệm.
16
Dưới đây là một số thuật toán được sử dụng rộng rãi:
Thuật toán K-Means:
Ý tưởng: dựa trên độ đo khoảng cách của các đối tượng dữ liệu trong
cụm. Thực tế, nó đo khoảng cách tới giá trị trung bình của các đối tượng dữ
liệu trong cụm. Nó được xem như là trung tâm của cụm. Như vậy, nó khởi tạo
một tập trung tâm các cụm trung tâm ban đầu và thông qua đó nó lặp lại các
bước gồm gán mỗi đối tượng tới cụm mà trung tâm gần nhất và tính toán tại
trung tâm của mỗi cụm trên cơ sở gán mới cho các đối tượng. Quá trình lặp
này dừng khi các trung tâm hội tụ.
Hình 1.3: Thiết lập để xác định danh giới các cụm ban đầu
Mục đích: sinh ra k cụm dữ liệu {C1,C2…, Ck} từ một tập dữ liệu ban
đầu gồm n đối tượng trong không gian d chiều Xi = (xi1,xi2, …, xid) )(i=1..n),
sao cho hàm tiêu chuẩn:
k
2
E = å å xÎ C D ( x - m i )
i
i =1
đạt giá trị tối thiểu.
Với mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tượng.
17
Hình 1.4: Tính toán trọng tâm các cụm mới
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
{C1, C2, …,Ck} từ một tập dữ liệu chứa n đối tượng trong không gian d chiều
Xi = (xi1, xi2, …, xid) ( i = 1, n ), sao cho hàm tiêu chuẩn :
k
2
E = å å xÎ C D ( x - m i )
i
i =1
(2.1)
Đạt giá trị tối thiểu. Trong đó: mi là trọng tâm của cụm Ci, D là khoảng
cách giữa hai đối tượng (khoảng cách Euclide). Trọng tâm của một cụm là
một véc tơ, trong đó giá trị của mỗi phần tử của nó là trung bình cộng của các
thành phần tương ứng của các đối tượng vectơ dữ liệu trong cụm đang xét.
Tham số đầu vào của thuật toán là số cụm k, và tham số đầu ra của thuật toán
là các trọng tâm của các cụm dữ liệu. K-means bao gồm các bước cơ bản như
sau:
InPut: Số cụm k và các trọng tâm cụm {mj}kj=1 ;
-
OutPut: Các cụm Ci æç i = 1, k ö÷ và hàm tiêu chuẩn E đạt giá trị tối thiểu
è
ø
18
Begin
Bước 1: Khởi tạo
Chọn k trọng tâm {mj}kj=1 ban đầu trong không gian Rd (d là số chiều
của dữ liệu, việc chọn có thể ngẫu nhiên hoặc theo kinh nghiệm)
Bước 2: Tính toán khoảng cách:
Đối với mỗi điểm Xi (1<=i<=n), tính toán khoảng cách của nó tới mỗi
trọng tâm mj j=1,k. Tìm trọng tâm gần nhất đối với mỗi điểm.
Bước 3: Cập nhật lại trọng tâm :
Đối với mỗi j=1,k, cập nhật trọng tâm cụm mj bằng các xác định trung
bình cộng của các vectơ đối tượng dữ liệu.
Bước 4: Điều kiện dừng:
Lặp các bước 2 và 3 cho đến khi các trọng tâm của cụm không thay đối.
Nhận xét: Độ phức tạp của thuật toán là O(Tkn) với T là số lần lặp, n số
đối tượng của tập dữ liệu đưa vào.
Ưu điểm:
Độ 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 giản nên có thể áp dụng đối với tập dữ liệu lớn.
Nhược điểm:
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.
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.
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
19
Thuật toán K-tâm:
Ý 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 K-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ự
và xác định khoảng cách giữa các đối tượng.
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:
( )
k
j
p = å å d 2j x, z
j =1 xÎC
Ta xét D là tập N đối tượng {x
i
}
N
i=1
(2.2)
i , xi ,...,xi )
trong đó ( xi = x1i ,...,xm
n
m+1
là phần tử của quan hệ r trên lược đồ quan hệ R = {A1,..., An} và xij Î
Dom(Aj) với mỗi j £ m là các giá trị thực còn với m + 1 £ j £ n là các giá trị
định danh.
Dưới đây em xin đưa ra một số khái niệm sử dụng trong dữ liệu hỗn
hợp:
a) Mode của tập dữ liệu hỗn hợp.
Định nghĩa. Giả sử C là tập con của tập dữ liệu hỗn hợp D.
i) Với mọi j £ n, j-mode của C ( kí kiệu là j-mode(C)) là giá trị có tần
xuất nhiều nhất trong thuộc tính Aj của C nếu A là thuộc tính định danh và là
trung bình cộng của các giá trị thuộc tính Aj của C khi Aj là thuộc tính số. Nếu
Aj là thuộc tính định danh và có nhiều giá trị có tần xuất như nhau trong C thì
j-mode (C) có thể không duy nhất và ta chọn giá trị nào cũng được.
ii) Mode của tập hợp C ký hiệu là mode(C) là phần tử z = (z1,..., zn)
trong đó: zj = j-mode(C), "j £ n
b) Metric trên dữ liệu hỗn hợp.
Trong lược đồ quan hệ R, miền giá trị của các thuộc tính Aj có thể là
tập số thực, định danh hay là tập có thứ tự.
20
Định nghĩa 1: Giả sử DOM(Aj) là miền giá trị của thuộc tính Aj. Ta có các
khái niệm sau:
i) Thuộc tính định danh: Aj được gọi là thuộc tính định danh nếu
DOM(Aj) là tập không có thứ tự, tức là " a,b Î DOM(Aj), hoặc a = b hay
a ¹ b.
ii) Thuộc tính số: Aj thuộc tính số nếu DOM(Aj) là tập số thực.
ii) Thuộc tính thứ tự: Nếu DOM(Aj) là tập hữu hạn và có thứ tự hoàn
toàn thì Aj được gọi là thuộc tính có thứ tự (chẳng hạn: DOM(Aj) = {không
đau, hơi đau, đau và rất đau}..
Trên miền giá trị DOM(Aj) của một thuộc tính Aj ta xác định các
khoảng cách như sau:
Định nghĩa 2: " x,yÎ DOM(Aj) hàm dj(x,y) xác định bởi :
Nếu Aj là thuộc tính số thì dj(x,y)= x - y
(2.3)
Nếu Aj là thuộc tính thứ tự và DOM(Aj) = {a1j ,..., a kj } với a 1j < a 2j < ... < a kj ,
ta lấy một hàm đơn điệu fj: DOM(Aj)→ [0,1] sao cho f j (a 1j ) = 0; f j (a kj ) = 1
(Hàm này có thể là: f j (a ij ) =
i -1
). Khi đó dj(x,y)= │fj(x) - fj(y) │
k -1
ì0 khi : x = y
î 1 khi : x ¹ y
Nếu Aj là dữ liệu định danh thì dj(x,y)= í
(2.4)
(2.5)
Định nghĩa khoảng cách giữa hai đối tượng dữ liệu hỗn hợp:
Định nghĩa 3: Giả sử x = (x1,..., xn) và y = (y1,..., yn) là hai đối tượng dữ liệu
hỗn hợp trên D, khoảng cách d(x, y) được tính bởi công thức:
d ( x, y ) =
n 2 2
å r j d j (x j , y j )
j =1
(2.6)
Trong đó các dj (xj, yj) được tính theo các công thức (2.3 -2.5) và r j là
các trọng số dương cho bởi các chuyên gia.
- Xem thêm -