Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
BÙI ĐỨC VIỆT

PHÂN CỤM DỮ LIỆU CHO NHẬN DẠNG ẢNH
SỬ DỤNG MẠNG NƠRON LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN, NĂM 2012

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

2


DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT 6
DANH MỤC CÁC HÌNH VẼ 7
LỜI NÓI ĐẦU 9
CHƢƠNG 1. GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU 11
1.1. Khái niệm khai phá dữ liệu 11
1.2. Kiến trúc của một hệ thống khai phá dữ liệu 11
1.3 Các giai đoạn của quá trình khai phá 13
1.4. Các phƣơng pháp khai phá dữ liệu 14
1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu 16
1.6. Các ứng dụng của khai phá dữ liệu 17
1.7. Các thách thức và khó khăn trong khai phá dữ liệu 17
1.8 Mạng nơron cho khai phá dữ liệu 18
CHƢƠNG 2. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 20
2.1. Khái niệm và mục tiêu của phân cụm dữ liệu 20
2.1.1. Khái niệm về phân cụm dữ liệu 20
2.1.1.1. Mục tiêu của phân cụm dữ liệu 20
2.1.1.2. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu 21
2.1.1.3. Các kiểu dữ liệu và các thuộc tính trong phân cụm 23
2.2.Một số thuật toán trong phân cụm dữ liệu 25
2.2.1. Các thuật toán trong phân cụm phân hoạch 25
2.2.2. Các thuật toán trong phân cụm phân cấp 31
2.2.3.Các thuật toán phân cụm dựa trên mật độ 33
2.2.4.Phân cụm dựa trên lƣới 34

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

4
2.2.5.Phân cụm dựa trên mô hình 35
2.2.6. Phân cụm có dữ liệu ràng buộc 36
2.3. Phân cụm cụm mờ 37


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

6
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT

CSDL
Cơ sở dữ liệu
PCDL
Phân cụm dữ liệu
KPDL
Khai phá dữ liệu
BNU
Phần tử nơron chiến thắng
MLP
MultiLayer Perception
BAM
Bidirectional Associative Memory
SOM
Self Organizing Map
VQ
Vector Quantization
LVQ
Learning Vector Quantization
MST
Minimal Spanning Tree Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn


22
22
27
28
30
31
36
37
38
49
53
52
55
55
58
58
59
60
60
63
65
66

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

8
Hình 3.13: Các vùng lân cận
Hình 4.1: Giao diện chƣơng trình
Hình 4.2: Khởi tạo mạng ngẫu nhiên
Hình 4.3: Xác định BMU

mẫu hoặc các mô hình trong dữ liệu với các tính năng: phân tích, tổng hợp, hợp thức,
khả ích và có thể hiểu đƣợc.
Khai phá dữ liệu là một bƣớc trong quá trình khám phá tri thức, gồm các thuật
toán khai thác dữ liệu chuyên dùng dƣới một số quy đị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 các mô hình tồn tại trong CSDL nhƣng
ẩn trong khối lƣợng lớn dữ liệu.
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ữ

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

10
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 trên đã và đang đƣợc phát triển 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í.
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.
Luận văn gồm có 4 chƣơng:

tiến trình lọc, sản sinh những tri thức hoặc các mẫu tiềm ẩn, chƣa biết thông tin hữu ích
từ các cơ sở dữ liệu lớn.
1.2. Kiến trúc của một hệ thống khai phá dữ liệu
Khai phá dữ liệu là quá trình rút trích thông tin bổ ích từ những kho dữ liệu lớn.
Khai phá dữ liệu là quá trình chính trong khai phá tri thức từ cơ sở dữ liệu.
Kiến trúc của một hệ thống khai phá dữ liệu có các thành phần nhƣ sau:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

12

Hình 1.1: Kiến trúc một hệ thống khai phá dữ liệu
CSDL, kho dữ liệu hoặc lƣu trữ thông tin khác: đây là một hay các tập CSDL,
các kiểu dữ liệu hay các dạng khác nhau của thông tin đƣợc lƣu trữ. Các kỹ thuật làm
sạch dữ liệu và tích hợp dữ liệu có thể đƣợc thực hiện.
Cơ sở tri thức (Knowledge-base): đây là miền tri thức dùng để tìm kiếm hay
đánh giá độ quan trọng của các mẫu kết quả thu đƣợc. Tri thức này có thể bao gồm một
sự phân cấp khái niệm dùng để tổ chức các thuộc tính hay các giá trị thuộc tính ở các
mức trừu tƣợng khác nhau.
Công cụ khai thác dữ liệu: là một hệ thống khai phá dữ liệu cần phải có một tập
các công cụ để phục vụ cho việc khai phá, bao gồm các Modul chức năng để thực hiện
công việc nhƣ kết hợp, phân lớp, phân cụm.
Mẫu ƣớc lƣợng: là bộ phận tƣơng tác với các Modul khai phá dữ liệu để tập
trung vào việc duyệt tìm các mẫu đang đƣợc quan tâm. Nó có thể dùng các ngƣỡng về
độ quan tâm để lọc các mẫu đã khám phá đƣợc. Cũng có thể Modul đáng giá mẫu
đƣợc tích hợp vào Modul khai phá dữ liệu, tùy theo cách cài đặt của phƣơng pháp
khai phá dữ liệu đƣợc dùng.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn


hợp và chỉnh sửa. Dữ liệu đƣợc thu thập từ nhiều nguồn khác nhau nên có thể có những
sai sót, dƣ thừa và trùng lặp. Lọc dữ liệu là cắt bỏ dƣ thừa để dữ liệu đƣợc định dạng
thống nhất. Dữ liệu sau khi lọc và chỉnh sửa sẽ nhỏ hơn, xử lý nhanh hơn.
Bƣớc 2: Khai phá dữ liệu là công việc chính, sử dụng các thuật toán khác nhau
để khai phá các kiến thức tiềm ẩn trong dữ liệu.
Bƣớc 3: quá trình ƣớc lƣợng kết quả khai phá theo yêu cầu của ngƣời dùng. Các
kết quả đƣợc ƣớc lƣợng bởi những quy tắc nào đó, nếu kết quả cuối cùng không thỏa
mãn yêu cầu thì phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn.
1.4. Các phƣơng pháp khai phá dữ liệu
Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh doanh
hay cho nghiên cứu khoa học…. Do đó, ta có thể xem mục đích của khai phá dữ liệu sẽ
là mô tả các sự kiện và dự đoán. Dự đoán liên quan đến việc sử dụng các biến hoặc các
đối tƣợng (bản ghi) trong cơ sở dữ liệu để chiết xuất ra các mẫu, dự đoán đƣợc những
giá trị chƣa biết hoặc những giá trị tƣơng lai của các biến đáng quan tâm. Còn mô tả
tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con ngƣời có thể hiểu đƣợc. Với
hai mục đích của khai phá dữ liệu đó, ngƣời ta thƣờng sử dụng các phƣơng pháp cho
Khai phá dữ liệu nhƣ sau:
 Luật kết hợp (Association rules)
 Phân lớp (Classfication)
 Hồi quy (Regression)
 Trực quan hóa (Visualiztion)
 Phân cụm (Clustering)
 Tổng hợp (Summarization)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

15
 Mô hình ràng buộc (Dependency modeling)
 Biểu diễn mô hình (Model Evaluation)
 Phân tích sự phát triển và độ lệch (Evolution and deviation analyst)

Đầu vào: là các cơ sở dữ liệu giao dịch
Đầu ra: tìm ra các mối quan hệ quan trọng giữa các mục trong cơ sở dữ liệu giao dịch.
Có nghĩa là sự hiện diện của một số mục trong một giao dịch sẽ bao hàm sự hiện diện
của một số các mục khác trong cùng một giao dịch.
1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu
Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ liệu
thành các loại khác nhau:
+ Cơ sở dữ liệu quan hệ: Đến nay hầu nhƣ dữ liệu đƣợc lƣu trữ dƣới dạng cơ sở dữ
liệu quan hệ. Cơ sở dữ liệu quan hệ có cấu trúc cao, dữ liệu đƣợc mô tả bởi một tập các
thuộc tính và lƣu trong bảng. Khai phá dữ liệu trên cơ sở dữ liệu quan hệ chủ yếu tập
trung khai phá mẫu.
+ Cơ sở dữ liệu giao tác: là tập hợp những bản ghi giao dịch, trong đa số các trƣờng
hợp chúng là những bản ghi các dữ liệu hoạt động của doanh nghiệp, tổ chức. Khai phá
dữ liệu trên cơ sở dữ liệu giao tác tập trung vào khai phá luật kết hợp tìm mối tƣơng
quan giữa những mục dữ liệu của bản ghi giao dịch.
+ Cơ sở dữ liệu không gian: bao gồm hai phần: dữ liệu quan hệ (hay giao tác) và thông
tin định vị (hoặc thông tin địa lý). Những luật kết hợp trên cơ sở dữ liệu không gian mô
tả mối quan hệ giữa các đặc trƣng trong cơ sở dữ liệu không gian. Dạng của luật kết
hợp không gian có dạng X -> Y với X, Y là tập hợp những vị từ không gian. Những
thuật toán khai phá luật kết hợp không gian tƣơng tự nhƣ khai phá luật kết hợp nhƣng
thêm những vị từ không gian.
+ Cơ sở dữ liệu có yếu tố thời gian: Giống nhƣ cơ sở dữ liệu có yếu tố không gian, cơ
sở dữ liệu này bao gồm hai phần: Dữ liệu quan hệ (hay giao tác) và Thông tin về thời

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

17
gian xuất hiện dữ liệu ở phần 1. Những luật kết hợp thời gian có nhiều thông tin hơn
những luật kết hợp cơ bản.
+ Cơ sở dữ liệu đa phƣơng tiện: số lƣợng trang Web đang bùng nổ trên thế giới, thông

Mức độ nhiễu cao hoặc dữ liệu bị thiếu.
Số chiều các thuộc tính lớn.
Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù
hợp.
Quan hệ giữa các trƣờng phức tạp.
Việc giao tiếp với ngƣời sử dụng và kết hợp các tri thức.
Tích hợp với các hệ thống khác.
Cơ sở dữ liệu có thể lớn về số lƣợng các bản ghi, về số lƣợng các thuộc tính
trong CSDL . Để giải quyết vấn đề này, ngƣời ta đƣa ra một ngƣỡng nào đó cho CSDL
bằng các cách nhƣ chiết xuất mẫu, xấp xỉ hoặc xử lý song song.
Để khắc phục việc dữ liệu thay đổi phụ thuộc theo thời gian ta cần phải chuẩn
hóa,cải tiến, nâng cấp các mẫu, các mô hình và có thể xem các thay đổi này là mục
đích của khai phá và tìm kiếm các mẫu bị thay đổi.
Với thuộc tính không phù hợp, các bộ giá trị không đầy đủ, bị thiếu giá trị trong
các miền thuộc tính… ngƣời ta sẽ coi sự thiếu vắng của các dữ liệu này là giá trị ẩn,
chƣa biết và có thể đƣợc tiên đoán bằng một số phƣơng pháp nào đó.
Với những Quan hệ phức tạp giữa các thuộc tính trong CSDL đòi hỏi phải có
các giải pháp, các kỹ thuật để có thể áp dụng đƣợc, nhận ra đƣợc các mối quan hệ này
trong quá trình khai phá dữ liệu.
1.8 Mạng nơron cho khai phá dữ liệu
Mạng nơron nhân tạo đƣợc coi là một công cụ mạnh để giải quyết các bài toán
có tính phi tuyến, phức tạp và đặc biệt trong trƣờng hợp mối quan hệ giữa các quá trình
không dễ thiết lập một các tƣờng minh. Có nhiều loại mạng nơron khác nhau trong đó
mạng nơron kohonen là một trong những mạng nơron thông dụng nhất. Mạng nơron
kohonen với nhiều ƣu điểm của nó, đã trở thành công cụ hữu ích trong khai phá dữ

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

19
liệu. Với thuật toán SOM tạo ra hàm phân bố xác suất cho tập dữ liệu ban đầu, dễ giải

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à 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

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

21
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.
2.1.1.2. 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 cụm có thể có bất cứ một hình dạng

ứ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.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

23
2.1.1.3. 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 2.1 : Biểu đồ các dạng dữ liệu

Hình 2.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:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

24
Thuộc tính liên tục (Continuous Attribute) : nếu miền giá trị của nó là vô hạn

/1
),(




n
i
q
y
i
x
i
q
yxd
, trong đó q là số tự nhiên
dƣơng.
Khoảng cách Euclide :




n
i
y
i
x
i
yxd
1

x
i
n
i
Maxyxd 


, đây là trƣờng hợp của
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ệ. Có thể
sử dụng công thức tính logarit cho mỗi thuộc tính x
i
.
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).
2.2.Một số thuật toán trong phân cụm dữ liệu
2.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.
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.