..
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
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 Công nghệ thông tin
& Truyền thông - Đại học Thái Nguyê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ũ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.
Thái Nguyên, tháng 10 năm 2012
Học viên
Bùi Đức Việt
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
3
MỤC LỤC
MỤC LỤC ........................................................................................................................ 3
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
2.3.1. Tổng quan về phân cụm mờ ......................................................................... 37
2.3.2. Các thuật toán phân cụm mờ ........................................................................ 38
CHƢƠNG 3: ỨNG DỤNG MẠNG NƠRON KOHONEN CHO PHÂN CỤM DỮ
LIỆU ............................................................................................................................... 42
3.1. Giới thiệu chung về mạng nơron ......................................................................... 42
3.1.2. Mô hình Nơron sinh học ............................................................................... 42
3.1.3. Mô hình Nơron nhân tạo ............................................................................... 44
3.1.4. Mô hình Mạng Nơron nhân tạo .................................................................... 46
3.1.5. Đặc trƣng của Mạng Nơron .......................................................................... 50
3.1.6. Phân loại mạng ............................................................................................. 51
3.2.3. Thuật toán của mạng SOM ........................................................................... 59
3.2.4. Một vài biến thể của giải thuật SOM ............................................................ 65
3.2.5. Một số ứng dụng của SOM ........................................................................... 66
CHƢƠNG 4: CÀI ĐẶT CHƢƠNG TRÌNH THỬ NGHIỆM ....................................... 67
4.1 Giới thiệu ............................................................................................................. 67
4.2 Mạng Nơron SOM cho phân cụm ảnh ................................................................ 68
Thiết kế mạng ......................................................................................................... 68
Thuật toán học mạng .............................................................................................. 68
4.2 Giới thiệu môi trƣờng cài đặt ............................................................................... 70
4.3 Giới thiệu giao diện chƣơng trình ........................................................................ 70
4.3.1 Thử nghiệm 1 ................................................................................................. 70
4.3.2 Thử nghiệm 2 ................................................................................................. 73
4.4 Hạn chế của giải thuật SOM khi áp dụng phân cụm màu trên ảnh ...................... 74
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ..................................................................... 77
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
5
TÀI LIỆU THAM KHẢO .............................................................................................. 77
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
7
DANH MỤC CÁC HÌNH VẼ
Trang
Hình 1.1: Kiến trúc một hệ thống khai phá dữ liệu
11
Hình 1.2: Quá trình khai phá dữ liệu
12
Hình 2.1 : Biểu đồ các dạng dữ liệu
22
Hình 2.2: biểu đồ quy mô dữ liệu
22
Hình 2.3: Cấu trúc phân cấp
27
Hình 2.4: Các cách mà cụm có thể đƣa ra
28
Hình 2.5: Thiết lập để xác định danh giới các cụm ban đầu
30
Hình 2.6: Tính toán trọng tâm các cụm mới
31
Hình 2.7: Khái quát thuật toán Cure
36
Hình 2.8: Các cụm dữ liệu đƣợc khám phá bởi thuật toán Cure
37
Hình 2.9: Hình dạng các cụm đƣợc tạo bởi thuật toán DBSCAN
38
Hình 3.1: Mô hình nơron sinh học
49
Hình 3.2: Mô hình nơron nhân tạo cơ bản
53
Hình 3.2: Mô hình mạng nơron 3 lớp
52
Hình 3.3: Mô hình học giám sát
55
Hình 3.4: Mô hình học không giám sát
55
Hình 3.5: Mô hình mạng perceptron một lớp
58
Hình 3.6: Mô hình Mạng perceptron nhiều lớp
58
Hình 3.7: Mô hình mạng hồi quy một lớp
59
Hình 3.8: Cấu trúc của mạng Hopfield
60
Hình 3.9: Cấu trúc của mạng BAM
60
Hình 3.10: Mô hình Mạng Nơron Kohonen
63
Hình 3.11: Mô hình Mạng Nơron Kohonen thông thƣờng
65
Hình 3.12: Phần tử nơron chiến thắng BMU
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
67
Hình 4.1: Giao diện chƣơng trình
69
Hình 4.2: Khởi tạo mạng ngẫu nhiên
70
Hình 4.3: Xác định BMU
70
Hình 4.4: Kết quả gom cụm
71
Hình 4.5: Giao diện chọn ảnh để phân cụm
71
Hình 4.6: Kết quả sau khi phân cụm
72
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
9
LỜI NÓI ĐẦU
Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong
nhiều lĩnh vực của đời sống, kinh tế xã hội nhiều năm qua cũng đồng nghĩa với lƣợng
dữ liệu đã đƣợc các cơ quan thu thập và lƣu trữ ngày một tích lũy nhiều lên. Nếu cho
rằng, điện tử và truyền thông chính là bản chất của khoa học điện tử thì dữ liệu, thông
tin, tri thức là tiêu điểm của một lĩnh vực mới để nghiên cứu và ứng dụng, đó là khám
phá tri thức và khai phá dữ liệu.
Thông thƣờng, chúng ta coi dữ liệu là một chuỗi các bits, hoặc các số và các ký
hiệu hay các đối tƣợng với một ý nghĩa nào đó khi gửi cho một chƣơng trình dƣới một
dạng nhất định. Các bít thƣờng đƣợc sử dụng để đo thông tin, và xem nó nhƣ là dữ liệu
đã loại bỏ phần tử dƣ thừa, lặp lại và rút gọn tới mức tối thiểu để đặc trƣng một cách cơ
bản cho dữ liệu. Tri thức đƣợc xem nhƣ là những thông tin tích hợp, bao gồm các sự
kiện và các mối quan hệ giữa chúng đã đƣợc nhận thức, khám phá hoặc nghiên cứu.
Nói cách khác, tri thức có thể đƣợc coi là dữ liệu ở mức độ cao của sự trừu tƣợng và
tổng quát.
Khám phá tri thức hay phát hiện tri thức trong CSDL là quy trình nhận biết các
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:
Chương 1: Giới thiệu về khai phá dữ liệu
Chương 2: Tổng quan về phân cụm dữ liệu
Chương 3: Ứng dụng mạng Nơron Kohonen cho phân cụm dữ liệu
Chương 4: cài đặt thử nghiệm
Luận văn đã trình bày một số vấn đề về phân cụm - một trong những kỹ thuật cơ
bản để khai phá dữ liệu và ứng dụng phân cụm cho nhận dạng ảnh sử dụng mạng
nơron. Đây là hƣớng nghiên cứu có triển vọng chỉ ra những sơ lƣợc trong việc hiểu và
khai thác CSDL khổng lồ, khám phá thông tin hữu ích ẩn trong dữ liệu; hiểu đƣợc ý
nghĩa thực tế của dữ liệu và ứng dụng vào bài toán cụ thể.
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
11
CHƢƠNG 1. GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU
1.1. Khái niệm khai phá dữ liệu
Khai phá dữ liệu là một lĩnh vực nghiên cứu nhằm tự động khai thác thông tin
tri thức, tri thức hữu ích, tiềm ẩn từ những CSDL lớn cho các đơn vị tổ chức, doanh
nghiệp,…Vậy khai phá dữ liệu là khám phá tri thức tiềm ẩn trong các cơ sở dữ liệu lớn.
Cụ thể hơn, đó là quá trình trích lọc, sản sinh ra những thông tin hoặc các mẫu không
hiển nhiên, tiểm ẩn nhƣng hữu ích từ các cơ sở dữ liệu lớn.
Các kết quả nghiên cứu khoa học cùng những ứng dụng thành công trong phát
hiện tri thức cho thấy Khai phá tri thức là một lĩnh vực phát triển bền vững, mang lại
nhiều lợi ích và có nhiều triển vọng, đồng thời có ƣu thế hơn hẳn so với công các công
cụ tìm kiếm phân tích dữ liệu truyền thống.
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.
Vậy ta có thể khái quát hóa khái niệm Khai phá dữ liệu là một quá trình tìm
kiếm, phát hiện các tri thức mới, hữu ích, tiềm ẩn trong CSDL lớn. Cụ thể hơn đó là
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
13
Dữ liệu thực: là kết quả cuối cùng của quá trình khai phá, phù hợp với yêu cầu
ngƣời sử dụng.
1.3 Các giai đoạn của quá trình khai phá
Khai phá dữ liệu là một giai đoạn quan trọng trong quá trình khám phá tri thức.
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 thuộc
tính dữ liệu trong kho dữ liệu mà con ngƣời có thể hiểu đƣợc.
Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật đƣợc
phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó 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 quan tâm.
Quá trình khai phá dữ liệu đƣợc thể hiện nhƣ hình sau:
Hình 1.2: Quá trình khai phá dữ liệu
Trong đó :
Xác định nhiệm vụ: xác định chính xác các vấn đề cần giải quyết.
Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp.
Thu thập và tiền xử lý dữ liệu: Thu thập dữ liệu liên quan và tiền xử lý chúng
sao cho thuật toán khai phá dữ liệu có thể hiểu đƣợc. Đây là quá trình khó khăn, có thể
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
14
gặp phải rất nhiều vƣớng mắc nhƣ: dữ liệu phải đƣợc sao ra nhiều bản, quản lí tập các
dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình…
Quá trình khai phá dữ liệu trải qua ba bƣớc:
Bƣớc 1: Lọc dữ liệu đƣợc thực hiện trong quá trình tiền xử lý. Đầu tiên là tích
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)
Phƣơng pháp tìm kiếm (Search method)
Trong số các phƣơng pháp khai phá dữ liệu trên, có 3 phƣơng pháp đƣợc sử
dụng nhiều đó là: Luật kết hợp, Phân lớp dữ liệu và Phân cụm dữ liệu.
Phân lớp dữ liệu: Khái niệm phân lớp dữ liệu đƣợc Han và Kamber đƣa ra
năm 2000. Phân lớp dữ liệu là xây dựng một mô hình mà có thể phân các đối tƣợng
thành những lớp để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay tiên
đoán giá trị của dữ liệu sẽ xuất hiện trong tƣơng lai.
Quá trình phân lớp dữ liệu đƣợc thực hiện qua 2 bƣớc:
Dựa vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc
trƣng của những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có giám sát,
học theo mẫu đƣợc cung cấp trƣớc.
Từ những lớp dữ liệu hoặc những khái niệm đƣợc xác định trƣớc, dự đoán giá trị của
những đối tƣợng quan tâm.
Một kỹ thuật phân lớp dữ liệu đƣợc Han và Kamber đƣa ra là cây quyết định.
Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tƣơng ứng.
Phân nhóm dữ liệu: Phân nhóm là kỹ thuật khai phá dữ liệu tƣơng tự nhƣ phân
lớp dữ liệu. tuy nhiên, sự phân nhóm là quá trình học không giám sát, là quá trình
nhóm những đối tƣợng vào trong những lớp tƣơng đƣơng, những đối tƣợng trong cùng
nhóm phải tƣơng đƣơng nhau và khác với những đối tƣợng khác trong các nhóm khác.
Trong phân nhóm đối tƣợng, những đối tƣợng đƣợc nhóm lại cùng nhau dựa vào sự
giống nhau của chúng. Sự giống nhau giữa những đối tƣợng đƣợc xác định bởi những
chức năng giống nhau. Thông thƣờng sự giống nhau về định lƣợng nhƣ khoảng cách
hoặc độ đo khác đƣợc xác định bởi những chuyên gia trong lĩnh vự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
16
Luật kết hợp: khai phá bằng luật kết hợp là tìm ra các mẫu các quan hệ, các
mối tƣơng quan hoặc quan hệ nhân quả phổ biến giữa các đối tƣợng trong cơ sở dữ liệu
giao dịch, cơ sở dữ liệu quan hệ và các thông tin khác trong kho.
Đầ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
tin trên Web đang phát triển với tốc độ cao vì vậy việc khai phá thông tin trên Web
(Web mining) đã trở thành một lĩnh vực nghiên cứu chính của khai phá dữ liệu và đang
đƣợc quan tâm. Khai phá dữ liệu trên Web đƣợc chia thành 3 phạm trù chính: Khai phá
cách sử dụng Web (Web usage mining), khai phá cấu trúc Web (Web structure mining)
và khai phá nội dung Web (Web content mining). Khai phá cách dùng Web tập trung
vào việc khai phá thông tin của ngƣời truy cập Web.
1.6. Các ứng dụng của khai phá dữ liệu
Khai phá dữ liệu tuy là một lĩnh vực mới nhƣng đang thu hút đƣợc sự quan tâm
của rất nhiều nhà nghiên cứu, nhờ đó nó có nhiều những ứng dụng trong thực
tiễn, điển hình nhƣ:
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 giá 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, Y tế……
1.7. Các thách thức và khó khăn trong khai phá dữ liệu
Khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực trong thực tế, vì vậy
các thách thức và khó khăn ngày càng nhiều, càng lớn hơn. Dƣới đây là một số khó
khăn cần đƣợc quan tâm và giải quyết:
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
18
Các cơ sở dữ liệu lớn, các tập dữ liệu cần xử lý có kích thƣớc lớn. Thực tế, kích thƣớc
của các tập dữ liệu thƣờng ở mức tera- byte .
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
thích và quan trọng nhất là trực quan hóa tốt. Tùy vấn đề giải quyết mà các chuyên gia
khai phá dữ liệu có thể chọn các phƣơng pháp khác nhau để phân tích dữ liệu đƣa ra.
Thế nhƣng với phƣơng pháp SOM có thể làm nhiều công việc cùng lúc và cho kết quả
tƣơng đƣơng với việc kết hợp nhiều phƣơng pháp khác với nhau. SOM rất hiệu quả
trong việc phân cụm và rút gọn kích thƣớc dữ liệu. Đây cũng chính là phƣơng pháp sẽ
đƣợc nghiên cứu và sử dụng trong nội dung của luận văn ở các chƣơng tiếp theo.
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
20
CHƢƠNG 2. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU
2.1. Khái niệm và mục tiêu của phân cụm dữ liệu
2.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.
2.1.1.1. 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à 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
- Xem thêm -