Luận văn thạc sĩ Khoa học máy tính: Nghiên cứu các thuật toán gom cụm mờ và cài đặt ứng dụng

Luận văn này giới thiệu một thuật toánhiệu quả dựa trên thuật toán gom cụm mờ động [1], gọi là thuật toán gom cụm mờ động mở rộng, thuật toán này được dùng để gom cụm cho dữ liệu vừa độn

Mai Ngọc Hải

NGHIÊN CỨU CÁC THUẬT TOÁN GOM CỤM MỜ

VÀ CÀI DAT UNG DUNG

LUẬN VAN THAC SĨ CÔNG NGHỆ THONG TIN

Chuyên ngành: KHOA HỌC MAY TÍNH

Mã số: 60.48 01.01

Tp Hồ Chi Minh - 2014

Trong những năm gan đây, khai phá dữ liệu đã và đang được nghiên cứu rộng

rãi và ứng dụng trong nhiều lĩnh vực, chẳng hạn như giám sát môi trường, nghiên cứu thị trường và điều khiển chất lượng, Khai phá dữ liệu là lĩnh vực nghiên cứu

rộng, gồm nhiều bước, nhiều phương pháp Luận văn này giới thiệu một thuật toánhiệu quả dựa trên thuật toán gom cụm mờ động [1], gọi là thuật toán gom cụm mờ

động mở rộng, thuật toán này được dùng để gom cụm cho dữ liệu vừa động vừa

tĩnh, điển hình như dữ liệu sinh viên bao gồm: điểm trung bình thay đổi theo thờigian, trong khi đó các thông tin khác như: thông tin tuyển sinh đầu vào, thông tin lýlịch sinh viên thì không thay đổi Ưu điểm của thuật toán đề xuất là vừa gom cụm

được các đối tượng theo các thuộc tính tĩnh của đối tượng, vừa có thể theo dõi được

sự thay đổi theo thời gian của thuộc tính động Kết quả thực nghiệm được cài đặt trên dit liệu của sinh viên trường đại học Kinh Tế Tài Chính Tp HCM, bước đầu

mang lại kết quả như mong muốn và có thể áp dụng giải quyết các vấn đề trong khai

phá dữ liệu.

Danh mục các hình vẽ

Danh mục từ viết tắt.

Chương1 Tổng quan khai phá dữ liệu

1.1.

1.2 Các phương pháp khai phá dit liệu

1.3 Ứng dụng thực tiễn của khai phá dữ liệu -:vcvssc++ 9

1.4 Gom cụm dữ liỆu St Event 10 14.1 Khái niệm

Chương2 Gom cụm dữ liệu mờ.

2.1 ˆ Thuậttoán FCM oii sassccszscscasasnsatsstsesasassosasassssesassssasassssasossssstsseressevestisssssassn DO

3.1.1 Hàm mục tiêu của bài toán

3.2 Gom cụm mờ động mở rộng

3.2.1 Thuật toán gom cụm mờ truyện thong - : +55 5++s+ce<e++ 34 3.2.2 đÊ NHh dt toán: ZOMICUMTIOTAGI IAM E, dễ UIẾ, 35

3.2.3 Cấu trúc mau dữ liệu

3.2.4 Kết quả gom cụm và sự thay đổi theo thời gian - 38

3.2.5 Trọng số thành phẩhn -ccccccccecccccvvvcerrrrrrrrevecree 38

3.2.6 Ma trận khoảng cách

3.2.7 Thuật toán gom cụm mờ động mở rỘNg -.-. -‹ - SD

3.2.7.1 Giới thiệu

3.2.7.2 Thuật toán EDFC đề xuấT S252 5+ S5c+c+c+++esvsesexv++ 4I

3.2.7225NI2)101DTHEC TAD Của CRUG EOÁN, «Sex uke 42

4.6 So sánh kết quả gom cụm với thuật toán DFC Kết lua

Tài liệu tham khảo

Hình 1.1 - Các bước trong KDD [11]

Hình 1.2 - Một ví dụ gom cụm dữ liệu

Hình 1.3 - Minh họa thuật toán K-Means - - 6 65+ se Sxvxxeeevrvrrrrre 16

Hình 4.1 - File dữ liệu demo

Hình 4.2 - Sự thay đổi của 3 tâm cụm theo thời gian cccccccccccccccccc+2 48Hình 4.3 - Sự thay đổi tâm cụm và một mẫu ““2 Ì” -.-.cc¿¿+222vvvc+zztzcvccse+ 49Hình 4.4 - Sự phụ thuộc trọng số môn học - lần Chạy Ì &, t CÊÀ 50

Hình 4.5 - Sự phụ thuộc trọng số môn học - lần Chạy 2 LL1 coc o 0 51

Hình 4.6 - Sự phụ thuộc trọng số môn học - lần CHẠY 20 TẾ G 52Hình 4.7 - Sự phụ thuộc trọng số thành phần - lần chạy Ï 2Hình 4.8 - Sự phụ thuộc trọng số thành phần - lần Chạy 2 2105: ii 2:2 TP 54

FCM: Fuzzy C-means.

cFCM: c-Insensitive Fuzzy C-Means.

CSDL: Cơ sở dữ liệu.

KDD: Knowleadge Discovery in Database.

DFC: Dynamic Fuzzy Clustering.

EDFC: Extended Dynamic Fuzzy Clustering.

1.1 Khai phá dữ liệu là gì?

Khoảng hơn một thập kỷ trở lại đây, lượng thông tin được lưu trữ trên các

thiết bị điện tử (đĩa cứng, CD-ROM, băng từ, ) không ngừng tăng lên Sự tích lũy

dữ liệu này xảy ra với một tốc độ bùng nổ Người ta ước đoán rằng lượng thông tin

trên toàn cầu tăng gap đôi sau khoảng hai năm và theo đó số lượng cũng như kích cỡ

của các cơ sở dữ liệu (CSDL) cũng tăng lên một cách nhanh chóng Nói một cách

trừu tượng là chúng ta đang “ngập” trong dir liệu nhưng lại “đói” tri thức Câu hỏi

đặt ra là liệu chúng ta có thê khai thác được gì từ những “núi” dữ liệu tưởng chừng

như “bỏ di” ấy không ?

Khám phá tri thức hay phát hiện tri thức trong cơ sở dit liệu là một qui trìnhnhận biết các mẫu hoặc các mô hình trong dữ liệu với các tinh năng: phân tích, tonghợp, hợp thức, khả dụng và có thể hiểu được

Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động khai

thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng

lồ và phức tap, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó

Khai phá dữ liệu là một bước trong bảy bước của quá trình KDD như sau:

> Làm sạch dữ liệu và tiền xử lý: loại bỏ nhiễu và các dữ liệu không cần thiết.

> Tích hợp dữ liệu: quá trình hợp nhất dữ liệu thành những kho dữ liệu sau

khi đã làm sạch và tiền xử lý.

> Trích chon dữ liệu: trích chọn dữ liệu từ những kho dit liệu và sau đó

chuyền đổi về dạng thích hợp cho quá trình khai phá dữ liệu Quá trình này

bao gồm cả việc xử lý với dữ liệu nhiễu, dữ liệu không day đủ

> Khai phá dữ liệu: là một trong các bước quan trọng nhất, trong đó sử dụng những phương pháp thông minh đề chat lọc ra những mẫu dữ liệu.

> Ước lượng mẫu: quá trình đánh giá các kết quả tìm được thông qua các độ

đo nào đó.

> Biểu diễn tri thức: quá trình này sử dụng các kỹ thuật để biểu diễn và thé

hiện trực quan cho người dùng.

1.2 Các phương pháp khai phá dữ liệu

Với hai mục đích chính trong khai phá dit liệu là mô tả và dự đoán, người ta thường sử dụng các phương pháp sau:

> Mô tả khái niệm: thiên về mô tả, tổng hợp và tóm tắt khái niệm Ví dụ: tómtắt văn bản

> Luật kết hợp: là dạng luật biểu diễn tri thức ở dạng khá đơn giản Vi dụ:

“60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua

Vv Phân lớp va dự đoán: 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 vùng địa lý theo dữ liệu thời tiết Hướng tiếp cận

này thường sử dụng một số kỹ thuật của máy học như cây quyết định,mạng nơ ron nhân tạo Người ta còn gọi phân lớp là học có giám sát.

> Gom cụm: xếp các đối tượng theo từng cụm, số lượng cũng như tên của cụm chưa được biết trước Người ta còn gọi gom cụm là học không giám

sát.

> Khai phá chuỗi: tương tự như khai phá luật kết hợp nhưng có thêm tính thứ

tự và tính thời gian Hướng tiếp cận này được ứng dụng nhiều trong lĩnh

vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao.

1.3 Ứng dụng thực tiễn của khai phá dữ liệu

Khai phá dữ liệu tuy là một hướng tiếp cận mới nhưng thu hút được rất nhiều

sự quan tâm của các nhà nghiên cứu và phát triển nhờ vào những ứng dụng thực tiễncủa nó Chúng ta có thé liệt kê ra đây một số ứng dụng điền hình:

Phân tích dữ liệu và hỗ trợ ra quyết định.

1.4 Gom cụm đữ liệu

1.4.1 Khái niệm

Gom cụm dữ liệu là quá trình gom các đối tượng vào các cụm đối tượng mà

trong cùng cụm các đối tượng có độ tương đồng cao nhất, còn giữa các cụm các đối tượng có độ tương đồng thấp nhất hoặc không tương đồng Gom cụm dữ liệu là

phương pháp học không giám sát Không giống như phân lớp, gom cụm không đòihỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện Vì thế, có thé coi gom 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 gom cụm đữ 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 trong

việc phát hiện ra các cụm.

Gom cụm có ý nghĩa rất quan trọng trong hoạt động của con người Gomcụm được sử dụng rộng rãi trong nhiều lĩnh vực như nhận dạng mẫu, phân tích dữliệu, xử lý ảnh, nghiên cứu thị trường, dự báo

Theo nghiên cứu cho thấy thì hiện nay chưa có một phương pháp gom cụmtổng quát nào có thé giải quyết tron vẹn cho tat cả các dang cấu trúc cơ sở dữ liệu

Hơn nữa, các phương pháp gom cụm cần có cách biéu diễn cấu trúc của các cơ sở

dữ liệu, với mỗi cách biểu diễn khác nhau sẽ có tương ứng một thuật toán gom cụm

phù hợp Vì vậy gom cụm dữ liệu vẫn đang là van đề khó và mở

1.4.2 Các ứng dung thực tiễn

Gom cụm dữ liệu hiện đang áp dụng rất nhiều trong thực tiễn như:

> Thương mại: tìm kiếm nhóm các khách hàng quan trọng có đặc trưng tương đồng và những đặc tả họ từ các bản ghi mua bán trong cơ sở dữ liệu.

> Sinh học: phân loại các gen với các chức năng tương đồng và thu được cáccấu trúc trong mẫu

> Thư viện: phân loại các cụm sách có nội dung và ý nghĩa tương đồng nhau

dé cung cấp cho độc giả.

> Bảo hiểm: nhận dạng nhóm tham gia bảo hiểm có chỉ phí bồi thường cao,

nhận dạng gian lận thương mại.

> Qui hoạch đô thị: nhận dạng các nhóm nhà theo kiểu và vị trí dia lý

nhằm cung cấp thông tin cho quy hoạch đô thị.

> Nghiên cứu trái đất: gom cụm dé theo dõi các tâm động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm.

> www: có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý nghĩatrong môi trường web.

> Dự báo: một hướng nghiên cứu mới hoàn toàn trong vai năm trở lại đây vàđược áp dụng hầu như trong mọi lĩnh vực, chẳng hạn: dự báo kết quả học

tập sinh viên, dự báo chỉ số chứng khoán, dự báo thời tiết,

1.4.3 Các yêu cầu của gom cụm

> Có khả năng mở rộng: nhiều thuật toán gom cụm làm việc tốt với nhữngtập dữ liệu nhỏ, 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 gom cụm đối với một tập dữ liệu lớn có thé làm ảnh hưởng

tới kết quả Do đó việc cần thiết là chúng ta phải phát triển các thuật toán gom cụm có khả năng mở rộng cao đối với cơ sở dữ liệu lớn.

> Khả năng thích nghỉ 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 gom cum dir 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 gom cụm với nhiều kiểu dữ liệu

khác nhau.

> Khám phá các cụm với hình dạng bất kỳ: nhiều thuật toán gom cụm xácđịnh các cụm dựa trên hàm đo khoảng cách Euclidean và khoảng cách Manhattan Các thuật toán dựa trên các hàm 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ó bat cứ hình dạng nao 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 dang bat kỳ là một việc làm quan

không những gây trở ngại cho người dùng mà còn làm cho khó có thể điềuchỉnh được chất lượng của gom cụm.

Khả năng thích nghỉ với dữ liệu nhiễu: hầu hết những cơ sở dữ liệu 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ệusai Một số thuật toán gom cụm nhạy cảm với dữ liệu như vậy và dẫn đếnchất lượng gom cụm thấp

Ít nhạy cảm với thứ tự của các dit liệu vào: một số thuật toán gom cụm

nhạy cảm với thứ tự của dit liệu vào, vi 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ácthuật toán ít nhạy cảm với thứ tự dữ liệu vào.

Số chiều lớn: một cơ sở dữ liệu 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 gom cụm áp dụng tốtcho dữ liệu với số chiều thấp, bao gồm chỉ từ 2 đến 3 chiều Người ta đánh

giá việc gom 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, 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ên lớn

Gom cụm ràng buộc: nhiều ứng dụng thực tế có thể cần thực hiện gomcum dưới các loại ràng buộc khác nhau Một nhiệm vụ đặc ra là đi timnhững nhóm dữ liệu có trạng thái gom cụm tốt và thỏa mãn các ràng buộc

Dễ hiểu và dễ sử dụng: người sử dụng có thể chờ đợi những kết quả gomcụm dễ hiểu, dễ lý giải và dễ sử dụng Nghĩa là, sự gom cụm có thể cầnđược giải thích ý nghĩa và ứng dụng rõ ràng.

1.4.4 Các phương pháp gom cụm dữ liệu

Hiện nay các phương pháp gom cụm có thể phân loại theo các cách tiếp cận

chính sau:

1.4.4.1 Gom cụm phân hoạch

Phương pháp này phân hoạch một tập dữ liệu có n phần tử thành k cụm chođến khi xác định số các cụm được thiết lập Số các cụm được thiết lập là các đặc

trưng được lựa chọn trước Phương pháp này là tốt cho các cụm hình cầu trong

không gian Euclidean Ngoài ra, phương pháp này cũng phụ thuộc vào khoảng cách

cơ bản giữa các điểm để lựa chọn các điểm dit liệu nào có quan hệ là gần nhau với

mỗi điểm khác; và các điểm dữ liệu nào là không có quan hệ hoặc có quan hệ là xa

nhau so với mỗi điểm khác Tuy nhiên, phương pháp này không thé xử lý các cụm

có hình dạng bất kỳ hoặc các cụm có mật độ các điểm dày đặc Các thuật toán phân hoạch có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề gom

cụm dữ liệu, do nó phải tìm kiếm tất cả các cách phân hoạch có thể được Chính vìvậy, trên thực tế thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử

dụng một hàm tiêu chuẩn để đánh giá chất lượng của cụm cũng như đề hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu Như vậy, ý tưởng chính của thuật toán

gom cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược tham ăn để tìm kiếm

nghiệm.

s Thuật toán K-Means:

Thuật toán này dựa trên độ đo khoảng cách của các đối tượng dữ liệu trong

cụm Trong 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ụm Như vậy, nó cần được khởi tạomột tập tâm các cụm ban đầu, và thông qua đó nó lặp lại các bước gán các đối tượng

vào cụm mà nó gần tâm nhất Quá trình này dừng khi các tâm hội tụ.

Mục đích của thuật toán K-Means là sinh ra k cum dit liệu {C¡, Cạ, , Cy} từ

một tập dữ liệu chứa n đối tượng trong không gian d chiều X; = {Xịi, Xi2, , Xa}, Ì =

1, 2, , n, sao cho hàm đánh giá:

k

min E = » » D(x— 1j)

j=1x€Cj

Trong đó: vj là tâm cụm C;, D là khoảng cách giữa x và tâm cụm Cj.

"Thuật toán K-Means bao gồm các bước cơ bản sau:

Thuật toán K-Means [9]

Input: tập dữ liệu và số cụm k

Output: các cụm C[i] (1 <i < k) và hàm đánh giá E dat giá trị tối thiểu

Begin

1 Khởi tạo k tâm ban đầu trong không gian RỶ (d là số chiều của dữ liệu) Việc

khởi tạo này có thê là ngẫu nhiên hoặc theo kinh nghiệm

2 Lặp

a Với mỗi điểm x; (1 <i <n), tính khoảng cách của nó tới các tâm cum

vị (1 $j <k) Sau đó gan điểm vào cụm mà nó gần tâm nhất

b Cập nhật lại các tâm cụm bằng cách xác định trung bình cộng cácvector diém dữ liệu thuộc cụm.

3 Cho đến khi các tâm của cụm không thay đồi.

End

Hình 1.3 - Minh họa thuật toán K-Means

A: Khởi tạo k tâm cụm (ở đây là 3)

B: k cụm được tạo ra bằng cách gan các diém vào tâm gần nhất

C: sau mỗi bước lặp, k tâm cụm thay đổi D: Quá trình lặp đi lặp lại cho đến khi các tâm không thay đồi

Thuật toán K-Means trên được chứng minh là hội tụ và có độ phức tạp tính

ệu, da

toán là O(nkdr) [12] Trong đó, n là số đối tượng dữ liệu, k là số cụm dữ

số chiều của dữ liệu, + là số vòng lặp Như vậy, do K-Means phân tích gom cụm don

giản nên có thể áp dụng đối với tập dữ liệu lớn Tuy nhiên, nhược điểm của Means là chỉ áp dụng với dữ liệu có thuộc tính số và khám phá ra các cụm có dang

K-hình cầu, K-Means còn rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữliệu Hơn nữa, chất lượng gom cụm dữ liệu của thuật toán K-Means phụ thuộc nhiềuvào các tham số đầu vào như: số cụm k và k tâm khởi tạo ban đầu Trong trường

hợp các tâm khởi tạo ban đầu mà quá lệch so với các tâm cụm tự nhiên thì kết quả gom cụm của K-Means là rat thấp, nghĩa là các cụm dữ liệu được khám phá rất lệch

so với các cụm thực tế Trên thực tế chưa có một giải pháp tối ưu nào dé chọn các

tham số đầu vào, giải pháp thường được sử dụng nhất là thử nghiệm với các giá trị

đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất

1.4.4.2 Gom cụm phân cấp

Phương pháp này xây dựng một phân cấp trên cơ sở các đối tượng dữ liệuđang xem xét Nghĩa là sắp xếp một tập dữ liệu đã cho thành dạng 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ó hai cáchtiếp cận phổ biến của phương pháp này đó là:

> Gộp nhóm, hay thường được gọi là tiếp cận Bottom-Up

> Phan nhóm, hay thường được gọi là tiếp cận Top-Down

Thực tế áp dụng, có nhiều trường hợp kết hợp cả hai phương pháp gom cụm

phân hoạch và gom cụm phân cấp, nghĩa là kết quả thu được của phương pháp phân cấp có thé cải tiến thông qua bước gom cụm phân hoạch Gom cụm phân hoạch và

gom cụm phân cấp là hai phương pháp gom cụm dữ liệu cổ điển, hiện đã có rấtnhiều thuật toán cải tiến dựa trên hai phương pháp này đã được áp dụng phé biếntrong khai phá dữ liệu.

1.4.4.3 Gom cụm dựa trên mật độ

Phương pháp này nhóm các đối tượng đữ liệu dựa trên hàm mật độ xác định,

mật độ là số các đối tượng lân cận của một đối tượng dir liệu theo một nghĩa nao đó.Trong cách tiếp cận này, khi một dữ liệu đã xác định thì nó tiếp tục được phát triển

thêm các đối tượng dữ liệu mới miễn là số các đối tượng lân cận này phải lớn hơn một ngưỡng đã xác định trước Phương pháp gom cụm dựa trên mật độ của các đối

tượng để xác định các cụm dữ liệu có thể phát hiện ra các cụm dữ liệu với hình thùbat kỳ Kỹ thuật này có thé khắc phục các phan tử ngoại lai hoặc giá trị nhiễu rất tốt,tuy nhiên việc xác định các tham số mật độ của thuật toán là rat khó khăn, trong khi

các tham số này có tác động rất lớn đến kết quả gom cụm.

1.4.4.4 Gom cum dựa trên lưới,

Phương pháp gom cụm dựa trên lưới thích hợp với dữ liệu nhiều chiều, dựatrên cấu trúc dữ liệu lưới để gom cụm, phương pháp này chủ yếu tập trung áp dụngcho lớp dữ liệu không gian Mục tiêu của phương pháp này là lượng hóa dữ liệu

thành các ô tạo thành cấu trúc dữ liệu lưới Sau đó các thao tác gom cụm chỉ cần làm

việc với các đối tượng trong từng ô trên lưới chứ không phải các đối tượng dữ liệu.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ỗi ô Phương pháp này

gần giống với phương pháp gom cụm phân cấp nhưng chúng không trộn các ô, đồngthời giải quyết khắc phục yêu cầu đối với dữ liệu nhiều chiều mà phương pháp gomcụm dựa trên mật độ không giải quyết được Ưu điểm của phương pháp gom cụm

dựa trên lưới là thời gian xử lý nhanh và độc lập với số đối tượng dit liệu trong tap

dữ liệu ban đầu, thay vào đó là chúng phụ thuộc vào các ô trong mỗi chiều của

không gian lưới.

1.4.4.5 Gom cụm dựa trên mô hìnhPhương pháp này cô gắng khám phá các phép x4p xi 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 gom cụm phân hoạch hoặc gom 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 chúng hiệu chỉnh các mô hình này đề nhận racác phân hoạch Phương pháp gom cụm dựa trên mô hình cố gắng khớp giữa các dữ

liệu với mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng hỗn hợp phân phối xác suất cơ bản Các thuật toán gom cụm dựa trên mô hình có hai

hướng tiếp cận chính: mô hình thống kê và mạng Nơ-ron Phương pháp này gầngiống với phương pháp gom cụm dựa trên mật độ, vì chúng phát triển các cụm riêngbiệt nhằm cải tiến các mô hình đã được xác định trước đó, nhưng đôi khi nó không

được bắt đầu với một số cụm cố định và không sử dụng cùng một khái niệm mật độ

cho các cụm.

1.4.4.6 Gom cum có ràng buộc

Sự phát triển của gom cụm đữ liệu không gian trên cơ sở dữ liệu lớn đã cung

cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lý Tuy nhiên, hau hết các thuật toán này cung cấp rat ít cách thức cho người dùng, dé xác định các ràng buộc

trong thế giới thực cần phải được thỏa mãn trong quá trình gom cụm Để gom cụm

dữ liệu không gian hiệu quả hơn, các nghiên cứu bổ sung cần được thực hiện để

cung cấp cho người dùng khả năng kết hợp các ràng buộc trong thuật toán gom cụm.

Chương 2 Gom cụm dữ liệu mờ

Chiến lược gom cụm cứng truyền thống chỉ cho phép mỗi mẫu dữ liệu chỉthuộc về một cụm duy nhất, điều này làm cho kết quả gom cụm kém hiệu quả và

cứng nhắc Lý thuyết tập mờ [8] đưa ra ý tưởng độ thuộc của thành viên thông qua

hàm thành viên Thuật toán gom cụm mờ c-means [7] (phát triển bởi Dunn năm

1973, cải tiến bởi Bezdek năm 1981, Dervis và Ozturk năm 2010) là thuật toán gomcụm mờ phổ biến nhất được sử dụng Thuật toán sử dụng hàm thành viên đề đo độ

thuộc của các mẫu vào các cụm, từ đó có thể kết luận mẫu sẽ thuộc về cụm mà nó có

(1981) cải tiến và tổng quát hóa hàm mục tiêu mờ bằng cách đưa ra trọng số mũ để

xây dựng thuật toán gom cụm mờ và được chứng minh độ hội tụ của các thuật toán

(1 <j <C) sao cho điểm dữ liệu đã cho chi có thể thuộc về một số cụm với bậc đượcxác định bởi độ phụ thuộc giữa [0,1] Như vậy, ma trận U được sử dụng để mô tả

cấu trúc cụm của X bằng cách giải thích uj như bậc thành viên x; (1 <i <n) với

cụm thứ j.

Uy Hạ + Uin

Mại ra + Mạn ChoU=[ ; hà" h

Mẹi Uc2 ++ tem

Dunn định nghĩa hàm mục tiêu mờ như sau:

min:J = » > uj @? (Xp, 9j)

i=1 J=1

Trong đó: yj là tâm cụm thứ j, d là khoảng cách từ x; đến Vị,

Bezdek khái quát hóa hàm mục tiêu mờ bằng cách đưa ra trọng số mũ m > 1

là bất kỳ số thực nào sau đây:

min:]m = XS» ujid? (xi, vj)

i=1 j=

Trong đó :

> X =6u1#¿, ,x„} (xị © RŸ) là n vector mẫu dữ liệu thực d chiều.

> m> 1 là trọng số mũ hay còn được gọi là tham số mờ

ry WE R@ là tâm cụm thứ j

> dj = d(x, v;) là hàm đo khoảng cách giữa điểm dữ liệu x; với tâm cụm

thứ j.

Một trong các nhân tố chính ảnh hưởng tới quyết định gom cụm hợp lý cácđiểm là vấn đề chọn phép đo độ phi tương tự Thực vậy, tính toán bậc thành viên Uj

phụ thuộc vào định nghĩa của phép do khoảng cách dj là tích vô hướng trên RỶ Bình

phương khoảng cách giữa mẫu x; và tâm cụm thứ j được định nghĩa như sau:

đ#(xu,v) = [ba — 4 = (xí ~ 9y) Ai — 9ý)

Trong đó:

> Ala ma trận hữu hạn dương đối xứng (p x p) bắt kỳ

> |lx: — 9;||Ễ biểu diễn độ lệch của dữ liệu x; với vị, d(x,v)) là tích vô hướng

thành C cụm dữ liệu trong không gian R"*€ được viết gọn như sau:

Gy n

Myen = \U € R"X€|Vi,j: uy, € [0,1]; 0 < > <n; } tụ = 1

i=1 j=

Thông thường người ta gọi bài toán gom cụm mờ là bài toán tìm các độ thuộcUji nhằm tối thiểu hàm mục tiêu Jp, ở trên với các điều kiện sau:

Dinh lý 1: Nếu m và C là các tham số cố định, và I, là một tập được định

nghĩa như sau:

I„ ={iI1<j<€,dj =0} 1<¡<nThi hàm mục tiêu Jy, đạt giá trị tối thiểu:

Thuật toán gom cụm mờ là một quá trình lặp liên tục việc cập nhật ma trận U

và tâm cụm theo công thức (2.1) và (2.2) để tối ưu hàm mục tiêu dựa trên độ đo

lu; Œt1) _tương tự, thuật toán sẽ dừng khi mmaz;{{| PHI < eh, trong đó e là điều kiện

dừng giữa 0 và 1, z là bước lặp Thủ tục này hội tụ tới cực tiểu cục bộ hay điểm yên

ngựa J„ Thuật toán gom cụm mờ có các bước thực hiện như sau:

Thuật toán FCM [10]

Input: số cum C và tham số mũ m;

Output: C cum dữ liệu

b Tinh ma trận phân hoạch mờ U theo công thức (2.1);

c Cap nhật tâm cụm V theo công thức (2.2).

3 Cho đến khi (JU — Ul] <e)

4 Xuất kết quả

End

Tóm lại thuật toán gom cụm mờ là một mở rộng của thuật toán K-Means

nhằm dé phát hiện ra các cụm chồng lên nhau Tuy nhiên thuật toán gom cụm mờ vẫn chứa đựng nhược điểm của thuật toán K-Means trong việc xử lý đối với các phần tử ngoại lai và nhiễu trong dit liệu Thuật toán eFCM được trình bay sau đây là

một mở rộng của thuật toán FCM nhằm khắc phục các nhược điểm này

2.2 Thuật toán Epsilon FCM

2.2.1 Khái niệm

Thuật toán gom cụm FCM sử dụng hàm bậc hai để đo độ phi tương tự giữa

dữ liệu và các trung tâm cụm Suy luận sử dụng độ đo này là tính toán thấp và đơn

giản Tuy nhiên, cách tiếp cận này dé bị ảnh hưởng bởi nhiễu và các phần tử ngoạilai Để khắc phục nhược điểm trên, một độ đo cải tiến đã được đề xuất bởi (Vapnik,

1998) sử dụng tham số F (Vapnik gọi là tham số £, tuy nhiên trong thuật toán FCM

đã sử dụng tham số ¢ là điều kiện dừng, nên dé không trùng, ta sử dụng F) như sau:

rete = {yo Qs?

* = Uell— Fy llell > F

Trong đó F là tham số phi nhạy cảm với nhiễu.

Hàm mục tiêu của thuật toán £FCM được định nghĩa như sau:

> Lực lượng của tập A là card(A).

Dinh lý 2: Nếu m, C và F là các tham số có định, hàm mục tiêu J„(U,V) đạt giá trị tối thiểu khi và chỉ khi:

AF = {AFe(0, (uje)”)I minggyagy Deak — Âg)x + FLA Ut — aD}

Với giả thuyết: »Ạ~¡ At = DNL, Ag va At, Aze[0, (uj) |

"Thuật toán eFCM [6]

Input: số cụm C và các tham số m, € cho hàm mục tiêu J.

Output: các cụm dữ liệu sao cho hàm mục tiêu đạt giá trị cực tiểu.

Begin

1 Nhập tham số C (l<c <n), m> I

Khởi tạo ma trận V=[vji], thiết lập =0

2 Lặp

a 7=7+l;

b Tinh ma trận phân hoạch mờ U(?) theo công thức (2.3);

c Cập nhật các tâm V(z) theo công thức (2.5)

3 Cho đến khi (JU — VOI], < e)

4 Hiển thị kết quả.

End

Thuật toán eFCM là một mở rộng của thuật toán FCM trong việc thích nghỉ

với nhiễu và phan tử ngoại lai trong dữ liệu Tuy vậy, hiệu quả của thuật toán £FCM

đối với tập dữ liệu lớn, tập dữ liệu nhiều chiều cũng như cách xác định tham số F lànhững vấn đề tiếp tục cần phải nghiên cứu và hoàn thiện

Chương 3 Gom cụm dữ liệu mờ động

Vào năm 2005, Liao [4] trình bày một khảo sát về gom cụm dữ liệu chuỗithời gian, tác giả đã tổng hợp các công trình nghiên cứu liên quan lúc bấy giờ Các

tiêu chí đánh giá kết quả gom cụm cũng như thước đo độ tương tự / không tương tự cũng được tác giả tổng hợp lại D Chakrabarti, R Kumar, và A Tomkins [3]

lần đầu tiên trình bày một khung chung cho “gom cụm tiến hóa” Ông khẳng định và

chứng minh “một gom cum tiến hóa nên đồng thời tối wu hai tiêu chuẩn có khả năng

xung đột: thứ nhất, 80m cụm tại bắt kỳ thời điểm nào déu nên giữ lại dữ liệu hiện tại

càng nhiều càng tốt, thứ hai, gom cụm không nên thay đổi đáng kể trong một bước

” Xiong và Yeung [5] sử dụng mô hình ARMA (autoregressive moving average)

để gom cụm dữ liệu được biểu diễn dưới dạng chuỗi thời gian có thể có độ dài khácnhau Zhang và các đồng sự [2] đề xuất một phương pháp mới cho hình dạng chuỗi

thời gian, bằng cách sử dụng các nguyên tắc của mạng lưới phức tạp Đầu tiên một

mạng lưới láng giềng gần được xây dựng dựa trên độ tương tự của các đối tượngchuỗi thời gian, tiếp theo các nút có độ đo cao sẽ được sử dụng để gom cụm Nó cóthể làm giảm kích thước của dữ liệu và nâng cao hiệu quả của thuật toán

Gần đây nhất, Ji và các đồng sự đã đề xuất thuật toán DFC; các tác giả đưa ra

các khái niệm Change Point, Key Point từ đó gom cụm được các mẫu theo thờigian.

Các thuật toán gom cụm mờ trình bày trong chương trước có nhược điểm làkhông thé áp dụng dé gom cụm cho các dữ liệu động theo thời gian, ví dụ như nhiệt

độ, chỉ số index Trong chương này sẽ giới thiệu thuật toán gom cum mờ động dégom cụm cho các dữ liệu thay đồi theo thời gian Trên cơ sở đó thuật toán gom cụm

mờ động mở rộng trình bày tiếp sau sẽ có thể áp dụng để gom cụm cho các dữ liệuvừa động vừa tĩnh.

3.1 Gom cụm mờ động

“Gom cụm mờ động (dynamic fuzzy cluster-DFC), dàng cho việc gom cumđộng chuối thời gian bằng cách giới thiệu định nghĩa về điểm khóa (key point) và

cải tiến thuật toán FCM Thuật toán đề xuất làm việc bằng cách quyết định chuỗi

thời gian vào các cụm không gán nhãn và hơn thế nữa còn cho thấy sự thay đổi cụmtheo thời gian Uu điển chính của hướng tiếp cận này so với các thuật toán hiện tại

là thông qua các thuộc tính của chuỗi thời gian có thể thấy được chuỗi thuộc các

cụm khác nhau theo thời gian Kết quả thực nghiệm dựa trên mô phỏng dữ liệu địa

lý chứng mình đã thu được sự thực thi xuất sắc và kết quả mong muốn Thuật toán

đề xuất có thé được áp dụng dé giải quyết các van đề gom cụm khác trong khai phá

Với ràng buộc: YE4 Hic = 1, Hic = 0

Trong đó yj, là độ đo thành viên của Time Series thứ i với tâm cum thứ c;

LỆ, = X7-[Wu (xi = xz)Ÿ là bình phương khoảng cách Euclidean giữa Time

Series thứ i và tâm cụm thứ c dựa trên trong số wij; m> 1 là tham số mờ hóa, thông thường người ta hay lấy m € [2, 2.5].

3.1.2 Time Series

Để có thể gom cụm được các mẫu dữ liệu động theo thời gian, trước hết ta

phải biểu dién được dữ liệu theo thời gian Time Series được định nghĩa là một tập các quan sat x;, mỗi quan sát được lưu trữ vào một thời điểm t; Một các tổng quát ta

có thể biểu diễn Time Series T chiều như sau:

TS = (Œị, t1), (Xa, t2), 0 (Xe, tr)}

Trong trường hợp đơn giản, khi tất cả t¡ — trị bằng nhau, tức là t; — t¡¡ = At (I

=2,3, , T), khi đó ta có thé biểu diễn Time Series đơn giản như sau:

TS = {xu*¿, ,Xr}

3.1.3 Change Point

Các mẫu dữ liệu thay đổi theo thời gian, do đó sẽ có kha năng sẽ có mẫu ngày càng di chuyền xa tâm hiện tại của mình và tiến lại gần một tâm khác Do đó ta phải

ghi nhận lại thời điểm mà ở đó mẫu xảy ra một thay đổi “bất thường”

Change Point là một điểm (x;, t) trong chuỗi Time Series thỏa mãn điều kiện

Trong đó: & = (x; — x1; — tea), B = (rier — Xi tins — fi), và + là một

tham số Như vậy để xác định cos(Ø) ta sử dụng công thức sau:

i = Xia) ina — Xi) + (ti — tis) (tina — ti)

Vi = Xin)? + (te — ya)? V in — MD? + (tind — i)?

cos(@) = cos(#,) =

3.1.4 Key Point

Một Change Point (x;, t;) được gọi là Key Point của chuỗi Time Series khi

thỏa mãn điêu kiện sau:

|t: — ty| = yAt