ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

-------------------------------------------

TRẦN QUANG HÀO

PHÂN CỤM DỮ LIỆU DỰA TRÊN ĐỒ THỊ

SỬ DỤNG CÂY KHUNG CỰC TIỂU

LUẬN VĂN THẠC SỸ C NG NGHỆ TH NG TIN

Hà Nội – 2014

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ --------------------- TRẦN QUANG HÀO PHÂN CỤM DỮ LIỆU DỰA TrRÊN ĐỒ THỊ

SỬ DỤNG CÂY KHUNG CỰC TIỂU

Ngành: Công Nghệ Thông Tin

Chuyên ngành: Kỹ thuật Phần mềm (Software Engineering)

Mã số: 60480103

LUẬN VĂN THẠC SỸ C NG NGHỆ TH NG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. HOÀNG XUÂN HUẤN

Hà Nội – 2014

LỜI CẢM ƠN

Điều ầu ti n tôi xin gửi lời cảm ơn sâu sắc nhất ến PGS.TS Hoàng Xuân Huấn.

Thầy ã cung cấp cho tôi những kiến thức, tài liệu, phƣơng pháp khi nghi n cứu v l m

luận v n. Tôi xin cảm ơn thầy về sự hỗ trợ chân thành và nhiệt tình trong suốt thời gian

qua. Đối với t i thầy l một ngƣời thầy áng k nh v lu n hết l ng v học vi n

T i xin gửi lời cảm ơn chân th nh ến các thầy c ộ ã giảng y các cán ộ

trong kho c ng nghệ th ng tin kho s u i học ph ng t chức h nh ch nh

T i xin gửi lời cảm ơn ến gi nh ng nghiệp v n những ngƣời ã

ộng vi n t i rất nhiều trong quá tr nh học tập

Hà Nội, ngày 2 tháng 12 n m 2014

Học viên

1

Trần Quang Hào

LỜI CAM ĐOAN

T i xin c m o n những kiến thức trình bày trong luận v n n y l o t i t m hiểu,

nghiên cứu và trình bày theo cách hiểu của bản thân ƣới sự hƣớng dẫn trực tiếp của

PGS.TS Hoàng Xuân Huấn. Trong quá trình làm luận v n t i có th m khảo các tài liệu

có li n qu n v ã ghi rõ ngu n gốc tham khảo tài liệu ó Mọi sao chép không hợp lệ,

vi ph m quy chế o t o tôi xin chịu hoàn toàn trách nhiệm.

Hà Nội, ngày 2 tháng 12 n m 2014

Học viên

2

Trần Quang Hào

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 CHỮ VIẾT TẮT ................................................... 5

DANH MỤC HÌNH VẼ .................................................................................................... 6

LỜI MỞ ĐẦU .................................................................................................................... 7

CHƢƠNG 1: GIỚI THIỆU VỀ KH M PH TRI TH C V PH N CỤM Ữ LIỆU

............................................................................................................................................ 8

1.1. Khám phá tri thức ....................................................................................................... 8

1.2. Vai trò và các mục tiêu chính của KDD .................................................................... 9

1.3. Khái niệm phân cụm ữ liệu: ..................................................................................... 10

1.4. Các ứng dụng của phân cụm ...................................................................................... 11

1 5 Một số phƣơng pháp phân cụm iển h nh ................................................................... 12

1 5 1 Phƣơng pháp phân cụm phân ho ch ........................................................................ 12

1 5 2 Phƣơng pháp phân cụm phân cấp............................................................................. 13

1 5 3 Phƣơng pháp phân cụm dựa trên mật ộ ................................................................. 16

1 5 4 Phƣơng pháp phân cụm dự tr n lƣới ...................................................................... 17

1.6. Một số vấn ề li n qu n ến phân cụm ...................................................................... 18

1.6.1. Mêtric trên dữ liệu hỗn hợp. .................................................................................... 18

1.6.2.Độ tƣơng ng. ......................................................................................................... 20

1.6.3. Entropy ..................................................................................................................... 23

CHƢƠNG 2: THU T TO N PH N CỤM S ỤNG C Y KHUNG CỰC TIỂU ... 24

2.1.Cây khung cực tiểu ...................................................................................................... 24

2 1 1 Đ nh ngh cây khung cực tiểu ................................................................................ 24

2 1 2 Thuật toán xây ựng cây khung cực tiểu ................................................................. 24

2.2. Một số khái niệm cần dùng ....................................................................................... 26

2.3. Cụm ƣợc mô tả bởi Zahn v H n l .......................................................................... 27

2.4. Thiết lập i toán phân cụm ng thị: ................................................................... 28

3

2 5 Độ phức t p củ thuật toán 2-MSTs ...................................................................... 35

CHƢƠNG 3: THỰC NGHIỆM NG ỤNG ................................................................. 37

3 1 Giới thiệu..................................................................................................................... 37

3.2 Chƣơng tr nh v kết quả thử nghiệm .......................................................................... 37

3 2 1 Chƣơng tr nh ............................................................................................................ 37

3.2.2 Kết quả thử nghiệm ................................................................................................. 38

KẾT LU N ........................................................................................................................ 48

4

TÀI LIỆU THAM KHẢO ................................................................................................. 49

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

Từ viết tắt

Từ tiếng anh

Từ hoặc cụm từ

CSDL Database Cơ sở dữ liệu

CQĐ Decision Tree Cây quyết ịnh

KPDL Data mining Khai phá dữ liệu

PCDL Clustering Data Phân cụm dữ liệu

TB Average Trung bình

CLS ConceptLearning System Hệ thống học khái niệm

DW Data Warehouse Kho dữ liệu

DM Data Mart Kho dữ liệu cục bộ

KDD Knowledge Discovery in Data Khám phá tri thức trong dữ liệu

MDL Minimum Description Length Chiều dài tối thiểu

5

MST Minimum spanning tree Cây khung cực tiểu

DANH MỤC HÌNH VẼ

Hình 1.1 Quá trình phát hiện tri thức trong CSDL ............................................................. 9

Hình 1.2: Mô phỏng vấn ề PCDL ................................................................................... 10

Hình 1.3: Phân cụm tập S = { c e} theo phƣơng pháp “ ƣới l n” ...................... 15

Hình 1.4: Hai cụm ƣợc tìm bởi thuật toán DBSCAN. .................................................... 17

Hình 1.5: Hai cụm dữ liệu có thể t m ƣợc nhờ DBSCAN. ............................................. 17

Hình 1.6: Ba tầng liên tiếp nhau của cấu trúc STING. ..................................................... 18

Hình 2.1: Một số hình minh họa phân cụm bởi Zahn ....................................................... 27

Hình 2.2. Một số hình minh họa phân cụm bởi Handl ..................................................... 27

Hình 2.3. Minh họa MSTs hai vòng ................................................................................. 30

Hình 2.4. Minh họa cụm tách về mật ộ ........................................................................... 32

Hình 2.5. Minh họa cụm không thể t ch ƣợc hơn nữa ................................................... 32

Hình 2.6. Minh họa cụm với tỉ lệ cut khác nhau ............................................................... 33

Hình 3.1. Giao diện co e chƣơng tr nh ............................................................................. 38

Hình 3.2. Giao diện khi ch y chƣơng tr nh ....................................................................... 38

H nh 3 3 ảng kế ho ch khai thác bay ........................................................................... 39

H nh 3 4 ảng s u khi t nh toán T1 v T2 nhận ng tách cụm .................................... 39

Hình3.5: Bảng Gain của các thuộc tính ........................................................................... 40

Hình 3.5 : Bảng với f10 nhận giá trị 0 ............................................................................. 40

Hình 3.6: Bảng với f10 nhận giá trị 1 ............................................................................... 41

Hình 3.7: Bảng t nh G in củ các thuộc t nh lần 2 .......................................................... 41

Hình 3.8: Bảng f13 nhận giá trị b ng 0 ............................................................................ 42

Hình 3.9: Bảng f13 nhận giá trị b ng 1 ............................................................................. 42

Hình 3.10. Bảng kết quả phân cụm s u khi t nh entropy lần 1........................................ 43

6

Hình 3.11. Bảng kết quả phân cụm s u khi t nh entropy lần 1........................................ 44

Hình 3.12. Bảng kết quả phân cụm s u khi t nh entropy lần 2......................................... 45

Hình 3.13. Bảng kết quả phân cụm s u khi t nh entropy lần 2........................................ 45

H nh 3 14 ảng dữ liệu thử nghiệm lần 2 ....................................................................... 46

H nh 3 15 ảng s u khi t nh toán T1 v T2 nhận ng tách cụm .................................. 46

Hình 3.16. Bảng kết quả phân cụm s u khi t nh enropy lần 1 .......................................... 47

7

Hình 3.17. Bảng kết quả phân cụm s u khi t nh enropy lần 2 .......................................... 47

LỜI MỞ ĐẦU

Ng y n y o sự phát triển m nh củ các ứng ụng c ng nghệ th ng tin trong

các l nh vực nhƣ kinh tế xã hội kho học … ã t o r khối lƣợng cơ sở ữ liệu kh ng

l Để kh i thác th ng tin hiệu quả i hỏi phải có một số kỹ thuật xử lý c o cấp ó l

phân ho ch ữ liệu h y các cụm.

Hiện nay, phân cụm dữ liệu vẫn là bài toán ng ƣợc nhiều ngƣời quan tâm

nghiên cứu, tuy nhiên, trong các thuật toán thƣờng yêu cầu ngƣời ùng xác ịnh trƣớc

số lƣợng cụm. Số cụm là một tham số quan trọng và ảnh hƣởng nhiều tới kết quả của

quá trình phân cụm, ứng với số lƣợng cụm khác nhau sẽ cho ra các kết quả phân cụm

khác nhau, thật khó kh n ể quyết ịnh kết quả phân cụm nào là tốt nhất.

Trong luận v n n y em tr nh y khảo cứu của tác giả về tiếp cận phân cụm dữ

liệu sử dụng cây khung cực tiểu Đặc biệt i sâu v o kỹ thuật phân cụm của thuật

toán 2-MSTs.

Ngo i phần mở ầu và kết luận, cấu trúc luận v n có 3 chƣơng:

 Chƣơng 1: Gi i thi u về h m ph tr th c v ph n cụm ữ i u

Chƣơng n y sẽ tr nh y các khái niệm cơ ản về khám phá tri thức v phân cụm ữ

liệu tóm tắt một số phƣơng pháp phân cụm ữ liệu iển h nh

 Chƣơng 2: Thuật to n ph n cụm sử ụng c hung cực tiểu

Trong chƣơng n y ể l m rõ hơn kỹ thuật phân cụm dữ liệu dựa trên đồ thị sử

dụng cây khung cực tiểu , một số vấn ề li n qu n ến cây khung cực tiểu ƣợc tr nh

y ngoài ra sẽ phân tích kỹ thuật phân cụm cây khung cực tiểu, tìm hiểu thuật toán

phân cụm 2-MSTs.

 Chƣơng 3: Thực nghi m ng ụng

Trong phần thực nghiệm c i ặt thuật toán 2-MSTs v m phỏng thuật toán

qu v ụ kh i thác y củ ng nh h ng kh ng.

Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận v n ng

7

thời ƣ r các vấn ề nghiên cứu tiếp cho tƣơng l i

CHƢƠNG 1: GIỚI THIỆU VỀ H M PH TRI TH C V

PH N CỤM DỮ IỆU

1.1. Khám phá tri th c

Khám phá tri thức trong các cơ sở dữ liệu là một quy trình nhận biết các mẫu

hoặc các mô hình trong dữ liệu với những t nh n ng: hợp thức, mới, khả ích và có thể

hiểu ƣợc Đây l một quá trình nghiên cứu một khối lƣợng dữ liệu lớn b ng các

phƣơng tiện tự ộng. Mục ch của sự phát hiện tri thức và khai phá dữ liệu chính là

tìm ra các mẫu v các m h nh ng t n t i trong các cơ sở dữ liệu nhƣng vẫn còn bị

che khuất bởi hàng núi dữ liệu.

Các thông tin và kiến thức thu ƣợc có thể ƣợc sử dụng cho các ứng dụng khác

nhau, ví dụ nhƣ phân t ch thị trƣờng, phát hiện gian lận v uy tr khách h ng ể kiểm

soát sản xuất và khoa học th m dò. Khai phá dữ liệu có thể ƣợc xem nhƣ l một kết

quả của sự tiến hóa tự nhiên của công nghệ thông tin

Khái niệm KDD (Knowledge Discovery in Databases) ƣợc ịnh ngh l quá

trình trích chọn các mẫu hoặc tri thức hấp dẫn, Quá trình KDD có thể phân thành các

gi i o n sau:

1. Lựa chọn dữ liệu: L ƣớc ta lựa chọn tập dữ liệu n ầu theo một số tiêu chí nhất

ịnh từ tập dữ liệu lớn nhƣ: t se t w rehouses h y t repositories

2. Tiền xử lý dữ liệu: ƣớc này làm s ch dữ liệu (xử lý với dữ liệu kh ng ầy ủ, dữ liệu

nhiễu, dữ liệu không nhất quán …) rút gọn dữ liệu (sử dụng hàm nhóm và tính t ng,

các phƣơng pháp nén ữ liệu, sử dụng histograms, lấy mẫu … ) rời r c hóa dữ liệu (rời

r c hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng ) Qu ƣớc này,

dữ liệu sẽ nhất quán ầy ủ ƣợc rút gọn v ƣợc rời r c hóa.

3. Đổi dạng: L ƣớc chuẩn hóa và làm mịn dữ liệu ể ƣ ữ liệu về d ng phù hợp

nhất nh m phục vụ cho các kỹ thuật khai phá ở ƣớc sau.

4. Khai phá dữ liệu (Data mining): Đây l ƣớc áp dụng những kỹ thuật phân tích (phần

nhiều là các kỹ thuật của học máy) nh m ể khai thác dữ liệu, trích chọn ƣợc những

mẫu thông tin, những mối liên hệ ặc biệt trong dữ liệu Đây ƣợc xem l ƣớc quan

trọng và tốn nhiều thời gian nhất của toàn quá trình KDD.

5. Biểu diễn: Các mẫu thông tin và mối liên hệ trong dữ liệu ã ƣợc khám phá ở ƣớc

tr n ƣợc chuyển d ng và biểu diễn ở một d ng gần gũi với ngƣời sử dụng nhƣ thị, 8

cây, bảng biểu, luật Đ ng thời ƣớc n y cũng ánh giá những tri thức khám phá

ƣợc theo những tiêu chí nhất ịnh [7,12,13]

Biểu diễn tri

Các mẫu

Data Mining

Tri thức

Các ƣớc thực hiện trong quá tr nh khám phá tri thức

Đ nh gi v giải thíchBiến đổi dữ li u Biến đổi dữ li u

Dữ liệu

Dữ liệu thô

Tr ch chọn ữ i u

Biến đổi ữ i u

Tiền xử ý ữ i u

Dữ liệu Tiền xử lý

Hình 1.1 Quá trình phát hiện tri thức trong CSDL

1.2. Vai trò và các mục tiêu chính của KDD

 Thu thập các tri thức từ dữ liệu có sẵn

- Nhiều cơ qu n ã thu nhập ƣợc nhiều n m một khối lƣợng lớn các dữ liệu họ

sẽ phải làm gì và có thể làm gì với chúng?.

- Ngƣời t lƣu trữ các dữ liệu vì họ ngh r ng có thể có những của cải áng quý

n o nó ng tiềm ẩn trong chúng. Về ý ngh kho học thì dữ liệu chính là những quan

sát ã ƣợc tập hợp l i một cách cẩn thận và công phu về một hiện tƣợng tự nhiên hay

xã hội n o ó cần phải ƣợc nghiên cứu.

- Trong kinh doanh, dữ liệu hàm chứa các thông tin về thị trƣờng, về các ối

thủ và về các khách hàng. Trong kỹ nghệ, dữ liệu chứa các thông tin về sản xuất, về

vận hành và các khả n ng tối ƣu cũng nhƣ các giải pháp chủ yếu ể cải tiến các quy

trình và giải quyết các sự cố.

- Chỉ có một lƣợng khá nhỏ (th ng thƣờng vào khoảng 5% ến 10%) dữ liệu ã

ƣợc thu thập lu n lu n ƣợc phân tích.

- Các dữ liệu có thể chƣ o giờ ƣợc phân tích vẫn tiếp tục ƣợc thu thập rất

tốn kém với ý ngh lo x r ng sau này sẽ có một cái g ó rất quan trọng có thể bỏ qua.

- Lƣợng dữ liệu quá lớn ối với cách thức phân tích c iển Đ i khi t kh ng

9

thể xem ƣợc hoặc chứ ƣợc tất cả trong bộ nhớ.[9]

1.3. Khái ni m phân cụm ữ i u:

Phân cụm dữ liệu (Data clustering) là quá trình phân chia một tập dữ liệu n ầu thành

các cụm dữ liệu sao cho các phần tử trong một cụm "tƣơng tự" với nhau và các phần tử

trong các cụm khác nhau sẽ "kém tƣơng tự " với nhau. Số các cụm dữ liệu ƣợc phân ở

ây có thể ƣợc xác ịnh trƣớc hoặc có thể ƣợc tự ộng xác ịnh theo phƣơng pháp

phân cụm. [6]

Trong học máy PC L ƣợc xem là vấn ề học không có giám sát (unsupervised

learning), vì nó phải giải quyết vấn ề tìm một cấu trúc trong tập hợp dữ liệu chƣ iết

trƣớc các thông tin về cụm hay các thông tin về tập huấn luyện mà chỉ ơn thuần dựa

v o t nh tƣơng ng củ các ối tƣợng dữ liệu. Trong nhiều trƣờng hợp, nếu phân lớp

ƣợc xem là vấn ề học có giám sát thì PCDL là một ƣớc trong phân lớp dữ liệu, nó sẽ

khởi t o các lớp cho phân lớp b ng cách xác ịnh các nhãn cho các nhóm dữ liệu. [6].

V ụ minh họ về phân cụm ữ liệu:

Hình 1.2: Mô phỏng vấn đề PCDL

Các yêu cầu của phân cụm trong khai phá dữ liệu

Hầu hết các nghiên cứu và phát triển thuật toán PC L ều nh m thỏa mãn các yêu cầu

cơ ản sau:

 Giảm dữ liệu: Giả sử ta có một lƣợng lớn dữ liệu (N). Phân cụm sẽ nhóm các dữ liệu

này thành m cụm dữ liệu dễ nhận thấy và m << N.

 Có tính mở rộng

 Thích nghi với các kiểu dữ liệu khác nhau

 Tối thiểu lƣợng tri thức cần cho xác ịnh các tham số vào

10

 Thích nghi với dữ liệu nhiễu

 Có khả n ng phân cụm với dữ liều có số chiều cao

 Dễ hiểu c i ặt và khả dụng.

1.4. Các ng dụng của phân cụm

Hiện nay, phân cụm dữ liệu ng ƣợc nghiên cứu, ứng dụng trong nhiều l nh vực khác

nhau, các kỹ thuật phân cụm dữ liệu ã ƣợc áp dụng cho một số ứng dụng iển hình

trong các l nh vực:

 Thƣơng m i: Trong thƣơng m i, phân cụm có thể giúp các thƣơng nhân khám

phá ra các nhóm khách hàng quan trọng có các ặc trƣng tƣơng ng nh u v ặc tả họ

từ các mẫu mu án trong cơ sở dữ liệu khách hàng.

 Sinh học: Trong sinh học, phân cụm ƣợc sử dụng ể xác ịnh các lo i sinh vật,

phân lo i các Gen với chức n ng tƣơng ng v thu ƣợc các cấu trúc trong các mẫu.

 Phân tích dữ liệu không gian: Do sự sộ của dữ liệu kh ng gi n nhƣ ữ liệu thu

ƣợc từ các hình ảnh chụp từ vệ tinh các thiết bị y học hoặc hệ thống th ng tin ịa lý

(GIS) …l m cho ngƣời dùng rất khó ể kiểm tra các dữ liệu không gian một cách chi

tiết. Phân cụm có thể trợ giúp ngƣời dùng tự ộng phân tích và xử lý các dữ liệu không

gi n nhƣ nhận d ng và chiết xuất các ặc tính hoặc các mẫu dữ liệu quan tâm có thể t n

t i trong cơ sở dữ liệu không gian.

 Lập quy ho ch thị: Nhận d ng các nhóm nhà theo kiểu và vị tr ị lý …

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

 Nghiên cứu trái ất: Phân cụm ể theo õ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.

 Tóm tắt và giải thích dữ liệu bài toán: Nhiều bài toán, dữ liệu có thể ƣợc tóm

tắt nhờ xem xét thuộc tính của các cụm dữ liệu mà không cần thiết xem xét thuộc tính

của từng mẫu. Trong nhiều lý thuyết khoa học, việc giải thích theo cụm cũng rất có ý

ngh chẳng h n việc phân tích tiến hóa sinh học có thể thực hiện theo loài và nhóm.

 T o mẫu cho tiếp cận phân lớp thống kê: Trong nhiều bài toán phân lớp, việc thu

thập dữ liệu mất nhiều thời gian và chi phí lớn. Việc phân cụm dữ liệu ƣợc thực hiện ở

gi i o n ầu ể ƣớc lƣợng phân phối lớp cho các tập mẫu nhỏ.

 Để t o tâm cho các nơron nhân t o trong các bộ phân lớp lo i này: Khi dùng

11

m ng nơron nhân t o ể phân lớp ngƣời t thƣờng dùng vector trung bình của các

vector ặc trƣng trong cụm làm tâm củ các nơron ể nhận biết các mẫu có ặc trƣng

gần ó

 Thƣ viện: Theo õi ộc giả, sách, dự oán nhu cầu củ ộc giả…

 Bảo hiểm: Phân nhóm các ối tƣợng sử dụng bảo hiểm và các dịch vụ tài chính,

dự oán xu hƣớng của khách hàng, phát hiện gian lận tài chính;

 Địa lý: Phân lớp các ộng vật và thực vật ƣ r ặc trƣng của chúng.

 Web Mining: Phân cụm có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý

ngh trong m i trƣờng Web. Các lớp tài liệu này trợ giúp cho việc khám phá tri thức

từ dữ liệu … [1,6]

1.5.M t s phƣơng ph p ph n cụm điển h nh

1.5.1.Phƣơng ph p ph n cụm phân hoạch

Với số lƣợng cụm ã ịnh, phƣơng pháp phân ho ch sẽ lần lƣợt phân các ối tƣợng

dữ liệu vào các cụm s u ó thực hiện lặp quá tr nh iều chỉnh ể cực tiểu hàm mục

ti u ƣợc chọn. Thuật toán k-mean l thuật toán thông dụng nhất trong phƣơng pháp

n y. Trong các thuật toán này, số lƣợng cụm k thƣờng ƣợc xác ịnh trƣớc hoặc ặt

ƣới d ng tham số. Với tập dữ liệu D g m n ối tƣợng trong không gian s chiều, các

ối tƣợng ƣợc phân thành c cụm sao cho t ng nh phƣơng ộ lệch của mỗi mẫu tới

tâm của nó là nhỏ nhất.

S u ây l thuật toán k-means, thuật toán iển hình củ phƣơng pháp n y

Thuật toán k-means

Thuật toán k-means (MacQueue, 1967) chia tập dữ liệu cho trƣớc thành c cụm

{ }, sao cho t ng nh phƣơng khoảng cách của mỗi ối tƣợng dữ liệu tới

tâm cụm chứ nó t cực tiểu. Nhƣ vậy, hàm mục tiêu của thuật toán này là:

(1.1)

Trong ó: l tâm củ cụm tƣơng ứng

Thuật toán n y thực hiện nhƣ s u:

ƣớc 0: Xác ịnh trƣớc số lƣợng cụm c v iều kiện ừng;

ƣớc 1: Khởi t o ngẫu nhi n c iểm l m các tâm cụm;

12

ƣớc 2: Lặp khi iều kiện ừng chƣ thỏ mãn:

2 1 Phân ho ch th nh c cụm ng cách gán mỗi ối tƣợng v o cụm m nó

gần tâm nhất;

2 2 T nh l i các tâm theo các ối tƣợng ã ƣợc phân ho ch ở ƣớc 2 1

Điều kiện ừng củ thuật toán thƣờng chọn từ các iều kiện s u:

- Số lần lặp t = trong ó l số cho trƣớc;

- Giá trị củ h m E nhỏ hơn một ngƣỡng n o ó ( ảm ảo chất lƣợng củ các

cụm ủ tốt h y nó ã ch y ƣợc ủ số v ng lặp cần thiết)

- Tới khi các cụm kh ng i

Khi tập dữ liệu không quá lớn th ngƣời t ùng iều kiện dừng 3.

Nếu tập dữ liệu D g m n mẫu với số thuộc tính là s, phân thành c cụm và số lần

lặp ở ƣớc 2 là t th ộ phức t p của thuật toán chỉ là O(tnsc) [14] nên rất thích hợp khi

tập D g m lƣợng dữ liệu lớn.

1.5.2. Phƣơng ph p ph n cụm phân cấp

Trong phƣơng pháp n y tập dữ liệu ƣợc sắp xếp thành một cấu trúc có d ng hình

cây gọi là cây phân cụm. Cây này có thể ƣợc xây dựng nhờ kỹ thuật ệ quy theo hai

phƣơng pháp t ng quát: phƣơng pháp ƣới l n ( ottom up) v phƣơng pháp tr n xuống

(top down).

 Phƣơng pháp ƣới lên (bottom up)

Các thuật toán theo phƣơng pháp ƣới lên còn gọi là các thuật toán trộn n ầu,

ngƣời ta khởi t o mỗi ối tƣợng làm một cụm và dùng thủ tục ệ quy ể trộn hai cụm

gần nhất với nhau trong mỗi ƣớc ể có kết quả chia cụm mới. Thủ tục ệ quy kết thúc

ta có tập duy nhất là toàn bộ dữ liệu. Các thuật toán phân biệt với nhau ở tiêu chuẩn

ánh giá h i cụm nào là gần nhất dựa trên khoảng cách các cụm chọn trƣớc. Quy tắc ể

chọn các cụm trộn n y ƣợc gọi là quy tắc liên kết. Quá trình thực hiện thuật toán ƣợc

biểu diễn thành cây và quyết ịnh phân dữ liệu thành bao nhiêu cụm sẽ o ngƣời dùng

quyết ịnh Ngƣời ùng cũng ự tr n cây n y ể nhận ƣợc kết quả phân cụm.

Cụ thể, với cách tính khoảng cách ể chọn cặp cụm trộn với nh u cho trƣớc, các

13

thuật toán trộn bao g m các ƣớc sau:

, c = n

Khởi t o mỗi phần tử làm một cụm Khi c ≠ 1 thực hiện lặp:

2.1. Chọn hai cụm gần nhất và theo quy tắc ã chọn

2.2. Trộn và thành // còn c-1 cụm

c-1 2.3. c Phƣơng pháp tr n xuống (top down). Phƣơng pháp tr n xuống còn gọi l phƣơng pháp tách ƣợc thực hiện theo trình tự

ngƣợc với phƣơng pháp trộn. Trong mỗi ƣớc ngƣời ta chọn một cụm ể tách thành

cụm con theo quy tắc ánh giá v tách cụm cho trƣớc Phƣơng pháp n y phức t p và lâu

hơn phƣơng pháp ƣới l n v thƣờng chỉ ƣợc áp dụng khi ngƣời ta có thêm thông tin

về phân bố cụm ể có phƣơng pháp tách phù hợp.

Ví dụ:

Trong ví dụ này, ta giải thiết ã có quy tắc liên kết và không bàn cụ thể tới cách

chọn cụm trộn. Quá trình thực hiện phƣơng pháp “ ƣới l n” phân cụm tập dữ liệu S = {a,

c e} ƣợc mô tả trong ph ƣới cụ thể nhƣ s u:

ƣớc 0: Mỗi ối tƣợng dữ liệu ƣợc gán cho mỗi cụm nhƣ vậy các cụm n ầu

là: {a},{b},{c},{d},{e}.

ƣớc 1: { } v { } l ƣợc gộp vào thành một cụm lớn hơn l { } v các cụm

thu ƣợc là: {a,b},{c},{d},{e}.

ƣớc 2: Gộp cụm {d},{e} thành {d,e}, các cụm thu ƣợc là {a,b},{c},{d,e}.

ƣớc 3: Gộp cụm {c} với {d,e} thành {c,d,e}, các cụm thu ƣợc là {a,b}, {c,d,e}.

14

ƣớc 4: Gộp cụm hai cụm {c,d,e} với {a,b} thành {a,b,c,d,e}.

Bƣớc 0 Bƣớc 1 Bƣớc 2 Bƣớc 3 Bƣớc 4

a a b Chiều từ ƣới lên b a b c d e

c c d e d

e d e

Hình 1.3: Phân cụm tập S = {a, b, c, d, e} theo phương pháp “dưới lên”.

Các quy tắc liên kết

Kết quả phân cụm của một thuật toán phụ thuộc v o m tric ƣợc ùng ể tính

khoảng cách củ các ối tƣợng. Kết quả phân cụm phân cấp cũng phụ thuộc quy tắc liên

kết hay cách tính khoảng cách (hoặc giả khoảng cách) giữa hai cụm và ể t m v

trộn h i cụm có khoảng cách nhỏ nhất trong mỗi ƣớc

Với m tric trong kh ng gi n ặc trƣng xác ịnh ởi một chuẩn ã có s u ây

l một số quy tắc li n kết th ng ụng

a) Liên kết đơn

Ký hiệu l NN (Ne rest Neigh our) Trong quy tắc n y khoảng cách giữ h i cụm

ƣợc xác ịnh nhờ khoảng cách nhỏ nhất giữ h i mẫu ( ối tƣợng) tƣơng ứng với h i

cụm:

(1.2a)

b) Liên kết đầy

Ký hiệu l FN (Furthest Neigh our) Trong quy tắc n y khoảng cách giữ h i cụm

ƣợc xác ịnh nhờ khoảng cách lớn nhất giữ h i mẫu tƣơng ứng với h i cụm:

(1.2b)

c) Liên kết trung bình giữa các nhóm

Ký hiệu l UPGMA (Un-Weighted Pair-Group Method using Arithmetic averages).

Nhƣ t n gọi củ nó khoảng cách l trung nh củ khoảng cách giữ các cặp

ối tƣợng thuộc h i cụm tƣơng ứng:

(1.2c)

15

Trong ó: và l số phần tử củ các cụm tƣơng ứng

Một số thuật toán phân cụm phân cấp iển h nh nhƣ CURE IRCH AGNES…

1.5.3. Phƣơng ph p ph n cụm dựa trên mật đ

Phƣơng pháp phân cụm dựa vào mật ộ xem các cụm nhƣ l các vùng có mật ộ

các ối tƣợng lớn trong không gian dữ liệu Các phƣơng pháp ựa vào mật ộ có thể sử

dụng ể lo i bỏ nhiễu và phát hiện ra các cụm có hình d ng tự nhiên.

Thuật toán dựa vào mật ộ ầu tiên là thuật toán DBSCAN (Ester et al, 1996),

thuật toán này xem xét mật ộ theo lân cận của mỗi ối tƣợng, nếu số lƣợng các ối

tƣợng trong khoảng cách của một ối tƣợng lớn hơn ngƣỡng MinPts th ối tƣợng ó

ƣợc xem là n m trong một cụm.

Thuật toán DBSCAN (Density – Based Spatial Clustering of Applications with Noise)

Thuật toan DBSCAN nhóm các vùng có mật ộ ủ cao vào trong một cụm và thác triển

dự tr n các ối tƣợng lõi ể có các cụm với hình d ng tự nhiên trong các tập không

gi n ặc trƣng Thuật toán yêu cầu xác ịnh trƣớc hai tham số ầu vào là và Minpts.

Phân cụm dữ liệu theo thuật toán DBSCAN áp dụng các luật s u ây:

Các ối tƣợng n m trong hình cầu bán kính ε (ε–lân cận) của một ối tƣợng ƣợc gọi là

ε–láng giềng củ ối tƣợng ó Đối tƣợng có ít nhất l Minpts ối tƣợng khác là ε–láng

giềng th ƣợc gọi l ối tƣợng nhân.

Một ối tƣợng có thể n m trong một cụm khi và chỉ khi nó n m trong ε –lân cận của

một ối tƣợng nhân thuộc cụm ó

Một ối tƣợng lõi o là ε–láng giềng của một ối tƣợng nhân p thì o thuộc cùng cụm với

p.

Hai cụm có giao khác rỗng thì nhập thành một cụm

 Một ối tƣợng không là nhân r và không là –láng giềng của một ối

tƣợng nhân n o th ƣợc xem là phần tử ngo i l i h y l ối tƣợng nhiễu.

Ví dụ:

Hình sau minh họa một trƣờng hợp với là bán kính của hình tròn và Minpts = 3,

tập dữ liệu g m hai cụm và các phần tử ngo i lai rải rác Các ối tƣợng {o, p, q, r} là

nhân c n s kh ng l ối tƣợng nhân nhƣng nó thuộc cụm vì là –láng giềng của một ối

16

tƣợng là nhân.

Hình 1.4: Hai cụm được tìm bởi thuật toán DBSCAN.

Hình sau minh họa một ví dụ về tập dữ liệu g m hai cụm ƣợc nhận biết nhờ

phƣơng pháp n y m kh ng ùng phƣơng pháp phân ho ch ƣợc.

Hình 1.5: Hai cụm dữ liệu có thể tìm được nhờ DBSCAN.

1.5.4. Phƣơng ph p ph n cụm dựa trên ƣ i

Để nâng c o hiệu quả củ phân cụm một cách tiếp cận l phân chi miền kh ng

gi n ặc trƣng chứ ữ liệu th nh một số hữu h n các t o n n ng h nh lƣới v sử

ụng các ặc trƣng thống k ể phân t ch các ữ liệu trong mỗi v quyết ịnh tách h y

nhập chúng T l m quen với thuật toán STING ể hiểu cách tiếp cận n y

Thuật to n STING (A STatistical INformation Grid approach)

STING o W W ng v các cộng sự (1997) ề xuất phƣơng pháp n y t chức

miền kh ng gi n chứ ữ liệu th nh lƣới h nh hộp mức ể phân t ch cụm theo thống

k phân cấp tr n từng n ầu t chi miền ữ liệu th nh các h nh chữ nhật (hoặc

h nh hộp khi kh ng gi n có số chiều c o) với chiều i các c nh ở mức 1 Việc phân t ch

th ng tin ự tr n các ặc iểm thống k củ tập ữ liệu trong mỗi nhƣ:

 Count: số ối tƣợng trong

 M: vectơ trung nh củ ữ liệu trong

 S: ộ lệch chuẩn củ mọi giá trị thuộc t nh trong

 Min: giá trị cực tiểu củ các thuộc t nh trong

 M x: giá trị cực i củ các thuộc t nh trong

17

 istri ution: kiểu phân phối củ các giá trị thuộc t nh trong

Việc phân t ch n y giúp t quyết ịnh có chi ng xét ở mức mịn hơn kh ng

h y l ã ủ ể phân cụm trong từng hoặc kết hợp với các cụm ở liền kề Cách phân

chi nhƣ vậy t o r một cấu trúc phân cấp: mỗi ở mức c o ƣợc phân chi th nh một

số ở mức thấp hơn trong ƣớc tiếp theo

Hình 1.6 m tả 3 mức lƣới li n tiếp nh u trong cấu trúc STING mỗi ở mức tr n

ƣợc phân th nh ốn ở mức tiếp theo Các th m số thống k ở mức c o khi chƣ xác

ịnh ƣợc sẽ ƣợc t nh toán từ các th m số trong các ở mức thấp hơn

Kiểu phân ố ở mức c o ƣợc t nh toán ự tr n các kiểu phân ố ở các tƣơng

ứng ở mức thấp Nếu các phân ố ở mức thấp kh ng cho iết phân ố mức c o th phân

ố ở mức c o sẽ l kh ng xác ịnh ( ƣợc ặt l none)

Hình 1.6: Ba tầng liên tiếp nhau của cấu trúc STING.

Việc phân tích thống kê thực hiện phân cấp theo các ô từ tầng trên. Tầng này bao

g m một số lƣợng nhỏ các ô. Với mỗi ô trong tầng, tính khoảng chắc chắn mà các ô

trong ó sẽ trở thành một cụm ể quyết ịnh. Các ô không chắc chắn sẽ phân chia tiếp

hoặc lo i bỏ. Tiến tr nh n y ƣợc lặp l i cho ến khi tính chất cụm của dữ liệu trong mỗi

xác ịnh rõ. Việc phân cụm sẽ hoàn tất khi xác ịnh ƣợc quan hệ cụm giữa dữ liệu

trong các ô. [1,6].

1.6. M t s vấn đề iên quan đến ph n cụm

1.6.1. Mêtric trên dữ li u hỗn hợp.

Trong phân cụm các ối tƣợng dữ liệu thƣờng ƣợc diễn tả ƣới d ng các ặc tính hay

còn gọi là thuộc tính, các thuộc tính này là các tham số ể giải quyết vấn ề phân cụm

và sự lựa chọn chúng có tác ộng áng kể ến kết quả phân cụm.

Phân lo i các kiểu thuộc tính khác nhau là vấn ề cần giải quyết ối với hầu hết các tập

dữ liệu nh m cung cấp các phƣơng tiện thuận lợi ể nhận d ng sự khác nhau của các

phần tử dữ liệu. Các thuật toán phân cụm thƣờng sử dụng một trong hai cấu trúc dữ liệu

18

sau:

Ma trận dữ liệu (Data matrix, object-by-variable structure): Là mảng n hàng, p

cột trong ó p l số thuộc tính của mỗi ối tƣợng. Mỗi hàng biểu diễn một ối tƣợng,

các phần tử trong mỗi hàng chỉ giá trị thuộc t nh tƣơng ứng củ ối tƣợng ó Mảng

ƣợc cho nhƣ s u:

Ma trận phi tương tự (Dissimilarity matrix, object-by-object structure): Là mảng

n hàng, n cột. Phần tử d(i,j) chứa khoảng cách h y ộ khác biệt giữ các ối tƣợng i và

ối tƣợng j, d(i,j) là một số kh ng âm trong ó nếu d(i,j) xấp xỉ 0 th h i ối tƣợng i và j

là khá "gần" nhau, nếu d(i,j) càng lớn th h i ối tƣợng i, j khá khác nhau. Do d(i,j) =

d(j,i) = 0 nên ta có thể biểu diễn ma trận phi tƣơng tự nhƣ s u:

Phần lớn các thuật toán phân cụm sử dụng cấu trúc ma trận phi tƣơng tự. Do vậy,

nếu dữ liệu cần phân cụm ƣợc t chức ƣới d ng ma trận dữ liệu thì cần biến i về

d ng ma trận phi tƣơng tự trƣớc khi tiến hành phân cụm. [11]

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,

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.

 Thuộc tính định danh. Đây l ng thuộc tính khái quát hoá của thuộc tính nhị

phân, Aj ƣợc gọi là thuộc t nh ịnh danh nếu DOM(Aj) là rời r c không phân biệt thứ

tự và có nhiều hơn hai phần tử, tức là a,b DOM(Aj), hoặc a = b hay a b. Chẳng

h n nhƣ thuộc tính nơi sinh hoặc thuộc tính tên gọi của người.

 Thuộc tính số. Aj ƣợc gọi là thuộc tính số nếu DOM(Aj) là tập số thực.

 Thuộc tính thứ tự: Là thuộc t nh ịnh nh nhƣng có th m t nh thứ tự nhƣng

19

chúng kh ng ƣợc ịnh lƣợng. 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 u

hơi u u v rất u}.

Trên miền giá trị DOM(Aj) của một thuộc tính Aj t xác ịnh các khoảng cách nhƣ s u

 Thuộc tính nhị phân là thuộc tính có hai giá trị là 0 và 1.

Định nghĩa 1.1. x,y DOM(Aj) ta hàm dj(x y) xác ịnh bởi :

(1.3a) i) Nếu Aj là thuộc tính số thì dj(x,y) =

với , ta lấy một ii) Nếu Aj là thuộc tính thứ tự và DOM(Aj) =

(Hàm này có thể h m ơn iệu fj: DOM(Aj)→ [0 1] s o cho

là: (1.3b) ) Khi ó j(x,y) = │fj(x)-fj(y) │

(1.3c) iii) Nếu Aj là thuộc t nh ịnh danh thì dj(x,y) =

Bây giờ t ịnh ngh khoảng cách trên

Định nghĩa 1.2. Giả sử x = (x1,...,xn) và y = (y1,...,yn) l h i ối tƣợng dữ liệu hỗn hợp

trên D, khoảng cách (x y) ƣợc tính bởi công thức:

(1.3d)

là các trọng số trong ó các j(xj,yj) ƣợc tính theo các công thức (1.3a -1.3c) và

ƣơng cho ởi các chuyên gia tuỳ theo mức quan trọng của thuộc tính.

Với ịnh ngh tr n t lu n có thể xem các thuộc tính thứ tự có miền giá trị là

o n [0 1] ể tìm mode (các giá trị trên thuộc tính này của D là tập con) và nó cũng

ƣợc xem là thuộc tính số khi không xảy ra nhầm lẫn. [1, 7]

1.6.2. Đ tƣơng đồng.

Độ tƣơng ng giữ các ối tƣợng m tả t nh chất giống nh u hoặc khác nh u giữ

chúng theo một ý ngh n o ó. Phân cụm ữ liệu l phƣơng pháp nhóm các ối tƣợng

có ộ tương tự (Similar) h y ộ tƣơng ng v o trong một nhóm các ối tƣợng ở các

nhóm khác nh u th có ộ tƣơng ng thấp

Có rất nhiều h m ƣợc ùng ể iểu iễn ộ tƣơng ng giữ các ối tƣợng Trong

khu n kh luận v n chỉ tr nh y một số các h m o tƣơng ng ph iến gọi l các

20

h m khoảng cách

Tất cả phƣơng pháp o khoảng cách ều phụ thuộc v o kiểu thuộc t nh (hay

kiểu ữ liệu) củ các ối tƣợng ƣợc phân t ch

Khoảng cách giữ h i mẫu thứ i v mẫu thứ k k hiệu l (i k) phải thỏ mãn

t nh chất s u:

i) d(i, i) = 0 với mọi i

ii) (i k) = (k i) với mọi cặp (i k)

iii) d(i, k) 0 với mọi cặp (i k)

 Thuộc t nh khoảng: S u khi chuẩn hó ộ o phi tƣơng tự củ h i ối tƣợng ữ

Một số phép o ộ tƣơng ng áp ụng cho các kiểu thuộc t nh.

liệu x y ƣợc xác ịnh ng các m tric khoảng cách nhƣ s u:

Đ đo C ng th c Giải th ch

Khoảng cách Minskowski q - số tự nhi n ƣơng

Khoảng cách Eucli e Đây l trƣờng hợp ặc iệt củ

khoảng cách Minskowski

trong trƣờng hợp q = 2

Khoảng cách M nh tt n Đây l trƣờng hợp ặc iệt

củ khoảng cách Minskowski

trong trƣờng hợp q = 1

Khoảng cách cực i Đây l trƣờng hợp củ khoảng

cách Minskowski trong trƣờng

21

hợp q .

 Thuộc t nh nhị phân: Trƣớc hết chúng t có xây ựng ảng th m số s u :

Bảng tham số

y

1 0

+ 1

x

+ 0

Bảng 1 : Bảng ngẫu nhiên + +

Trong ó : = + + + các ối tƣợng x y m tất cả các thuộc t nh t nh củ

nó ều l nhị phân iểu thị ng 0 v 1 ảng tr n cho t các th ng tin s u :

 l t ng số các thuộc t nh có giá trị l 1 trong cả h i ối tƣợng x y.

 l t ng số các giá trị thuộc t nh có giá trị l 1 trong x v 0 trong y

 l t ng số các giá trị thuộc t nh có giá trị l 0 trong x và 1 trong y

 l t ng số các giá trị thuộc t nh có giá trị l 0 trong x v y

Các phép o ộ tƣơng tƣơng ng ối với ữ liệu thuộc t nh nhị phân ƣợc

ịnh ngh nhƣ s u :

o Hệ số đối sánh đơn giản: ở ây cả h i ối tƣợng x v y

có v i tr nhƣ nh u ngh l chúng ối xứng v có cùng trọng số

o Hệ số Jacard: chú ý r ng th m số n y ỏ qu số các

ối sánh giữ 0 - 0 C ng thức t nh n y ƣợc sử ụng trong trƣờng hợp m trọng số

củ các thuộc t nh có giá trị 1 củ ối tƣợng ữ liệu có c o hơn nhiều so với các

 Thuộc t nh ịnh nh: Độ o phi tƣơng tự giữ h i ối tƣợng x v y ƣợc ịnh

thuộc t nh có giá trị 0 nhƣ vậy các thuộc t nh nhị phân ở ây l kh ng ối xứng

ngh nhƣ s u: trong ó m l số thuộc t nh ối sánh tƣơng ứng

trùng nh u p l t ng số các thuộc t nh

Ngƣời t có thể chuyển i giữ các m h nh cho các kiểu ữ liệu tr n th ụ ữ

liệu ịnh nh có thể chuyển i th nh ữ liệu nhị phân v ngƣợc l i Thế nhƣng giải 22

pháp n y rất tốt kém về chi ph t nh toán o vậy cần phải cân nhắc khi áp ụng cách

thức n y [7]

Tóm l i tuỳ từng trƣờng hợp ữ liệu cụ thể m ngƣời t sử ụng các m hình

t nh ộ tƣơng ng khác nhau.

1.6.3. Entropy

Entropy cho chúng ta biết sự ng nhất của một phân cụm. Một phân cụm càng

ng nhất thì entropy của nó càng giảm v ngƣợc l i. Entropy của một phân cụm mà chỉ

chứa một ối tƣợng (cân b ng hoàn hảo) là 0.

Coi P là một kết quả phân chia của một thuật toán phân cụm bao g m m phân

cụm. Với tất cả phân cụm j trong P, chúng ta cần tính toán pij, với pij là khả n ng một

thành viên của phân cụm j thuộc vào lớp i.

Entropy của mỗi phân cụm j ƣợc tính toán sử dụng công thức

chuẩn: trong ó việc tính t ng ƣợc thực hiện với tất cả các lớp. ,

T ng entropy của một tập các phân cụm ƣợc t nh toán nhƣ l t ng cộng entropy của

mỗi phân cụm ƣợc tính toán dựa theo kích cỡ của mỗi phân cụm:

trong ó Nj là kích cỡ của phân cụm j và N là t ng số lƣợng ối

23

tƣợng dữ liệu.

CHƢƠNG 2: THUẬT TO N PH N CỤM SỬ DỤNG C HUNG CỰC TIỂU

2.1.Cây khung cực tiểu

2.1 1 Đ nh ngh a c hung cực tiểu

Cho G=(X, E) la thị v hƣớng liên thông có trọng số T ƣợc gọi là:

i) Cây khung củ thị G nếu T liên thông và không có chu trình

ii) Cây khung cực tiểu củ thị G nếu T liên thông, không có chu trình và

t ng ộ dài các c nh là nhỏ nhất. [2]

2.1.2.Thuật to n x ựng c hung cực tiểu

Để xây ựng cây khung cực tiểu (tìm cây khung cực tiểu) có 2 thuật toán th ng ụng

ƣợc sử ụng l thuật toán Prim v Kruskal

i) Thuật toán Kruskal

Thuật toán Kruskal sẽ xây dựng tập c nh T của cây khung T = (V, K) theo từng

ƣớc nhƣ s u:

Trƣớc hết sắp xếp các c nh củ thị G theo thứ tự không giảm củ dài c nh.

n ầu tập K:= , ở mỗi ƣớc ta sẽ lần lƣợt duyệt trong danh sách các c nh ã sắp

xếp ể tìm ra một c nh có ộ dài nhỏ nhất sao cho việc b xung c nh ó v o tập K

mà không t o thành chu trình. Thuật toán sẽ kết thúc khi ta thu ƣợc tập K có n – 1

canh, thủ tục trình bày thuật toán nhƣ s u:

Procedure Kruskal;

Begin

K:= ;

While |K|<(n-1) and E do

Begin

Chọn e là cạnh có độ dài nhỏ nhất trong E;

E:=E\{e};

If K {e} không chứa chu trình then

K:= {e};

End;

If |K|

Đồ thị không có cây khung;

Else

24

T:=(V,K) là cây khung nhỏ nhất;

End;

ii) Thuật to n Prim nhƣ sau:

Thuật toán Prim sẽ xây dựng cây khung T =(V,P) theo cách sau:

Bắt ầu từ một ỉnh s tùy ý củ thị ầu tiên ta nối s với ỉnh lân cận gần của nó,

chẳng h n l ỉnh u ( ỉnh u là lân cận gần nhất của s nếu nhƣ (u s) l c nh kề có ộ dài

nhỏ nhất củ ỉnh s). Tiếp theo, trong số các trọng số các c nh kề với h i ỉnh s, u ta tìm

c nh có ộ dài nhỏ nhất, c nh này dẫn ến ỉnh thứ 3, chẳng h n l ỉnh v, va ta thu

ƣợc cây bộ phận g m 3 ỉnh 2 c nh. Quá trình này sẽ tiếp tục cho ến khi thu ƣợc cây

g m n ỉnh và n – 1 c nh, cây này sẽ là cây khung nhỏ nhất cần tìm.

Giả sử thị cho bởi ma trận trọng số C = {c[i,j]; I,j =1,2,..,n}. Trong quá trình thực

hiện thuật toán, ở mỗi ƣớc ể nhanh chóng chọn ƣợc các ỉnh và c nh cần b xung

vào cây khung, mỗi ỉnh v củ thị sẽ ƣợc gán một nhãn có d ng [min(v), near (v)],

trong ó min(v) l ộ dài của c nh có ộ dài nhỏ nhất trong số các c nh nối ỉnh v với

các ỉnh củ cây khung ng xây c n ne r( v) l ỉnh của cây khung gần v nhất.

Thuật toán Prim ƣợc mô tả nhƣ s u:

Procedure Prim

Begin

(*bước khởi tạo*)

Chọn s là một đỉnh nào đó của đồ thị;

VT:={s}; P:= ;(*VT là tập đỉnh, P là tập cạnh của cây khung*)

Min(s):=0; near(s):=s;

For v V\VT do

Begin

Min(v):=c[s,v];

Near(v):=s;

End;

(*bước lặp*)

Stop:=false;

While not Stop do

Begin

Tìm u V\VT có min(u) nhỏ nhất;

25

{u}; P:=P {u,near(u))}; VT:=VT

if|VT| = n then

begin

T=(VT, P) là cây khung nhỏ nhất;

Stop:=true;

End

Else

For v V\VT do

If min(v)>c[u,v] then

Begin

Min(v):=c[u,v];

Near(v):=u;

End;

End;

2.1.3. Vai trò của cây khung cực tiểu trong bài toán phân cụm

Các ối tƣợng phải tuân theo qui tắc(luật) của cây khung cực tiểu, từ ó sẽ ƣợc phân

chi ể t m ến cụm của mình.

2.2. M t s h i ni m cần dùng

Định ngh a 1: Với ộ o khoảng cách ã cho, một cụm ƣợc tách tốt là một tập hợp các

iểm mà khoảng cách giữa bất kỳ cặp iểm nào trong cụm t hơn khoảng cách giữa bất

kỳ iểm nào trong cụm và bất kỳ iểm nào không trong cụm.

Định ngh a 2: Một cặp cụm tự ch m nh u là hai cặp iểm ƣợc t o thành từ một c nhỏ,

phần bị lo i bỏ t o ra hai cụm riêng biệt từ hai cụm n y ều lớn hơn so với c .

Nói chung, một ngƣỡng, phụ thuộc v o phƣơng pháp phân cụm cụ thể, ƣợc sử dụng ể

xác ịnh một cụm nhỏ ến mức nào .

Định ngh a 3: Cho một metric khoảng cách, một cụm compact là một cặp iểm sao cho

khoảng cách giữa bất kỳ iểm nào trong cụm và i diện của cụm luôn nhỏ hơn khoảng

cách giữ iểm ó và bất kỳ i diện của cụm khác.

Định ngh a 4: Cho một metric khoảng cách, một cụm kết nối là một tập các iểm s o

cho ối với mỗi iểm trong cụm, luôn t n t i ít nhất một iểm khác trong cụm mà

khoảng cách giữa chúng luôn nhỏ hơn khoảng cách giữ iểm ó v ất cứ iểm n o

26

khác không thuộc cụm.[3]

2.3. Cụm đƣợc mô tả bởi Zahn v Handl

Hình 2.1: Một số hình minh họa phân cụm bởi Zahn

Trong hình minh họa phân cụm bởi Zahn:

 Hình (a) Minh họa hai cụm với hình d ng tƣơng tự k ch thƣớc và mật ộ.

 Hình (a) - (e) là những khoảng phân cách cụm;

 Hình (f) là mật ộ cách nhau về cụm;

 Hình (g) và (h) là mật ộ cách nhau của các cụm.

Trong mô hình của Handl:

Hình 2.2. Một số hình minh họa phân cụm bởi Handl

 Hình (a) là mô hình nhỏ gọn minh họa mục tiêu phù hợp ể ối phó với các bộ

dữ liệu hình cầu.

 Hình (b) là Mô hình gắn kết, mô tả mục tiêu kết nối xử lý bộ dữ liệu hình d ng

tùy ý.

 Hinh (c) là một m h nh ặc biệt.

Trong mô hình của Zahn, các hinh (b), (c) và (d) vẫn còn là khoảng cách phân cách,

ngay cả khi các hình d ng, k ch thƣớc hoặc mật ộ của hai cụm trong mỗi con số rất

d ng. Mật ộ của hai cụm trong hình (e) ng ần dần ng và trở thành cao nhất

27

trong ranh giới liền kề. Từ qu n iểm chung về tỷ lệ của sự th y i mật ộ sự phân

chia vẫn còn một số iểm áng chú ý. Sự khác biệt cơ ản giữa hai cụm ƣợc biểu thị

trong hình (f) n m ở mật ộ chứ không phải là khoảng cách và Zahn gọi nó là mật ộ

gradient.[3]

2.4. Thiết ập i to n ph n cụm ng đồ thị:

Đặt vấn ề:

Giả sử X={x1,x2, ... ,xi , ... ,xN} là một tập dữ liệu, xi =(xi1, xi2, ... ,xij, ... ,xid)T∈Rd

là một véc tơ ặc trƣng v xij l một ặc trƣng xây ựng thị G(X)=(V,E) biểu thị

một thị v hƣớng với ỉnh V=X và c nh E= {(xi,xj)|xi,xj ∈X, i j}. Mỗi c nh

e=(xi,xj) có chiều dài (xi,xj) và chiều dài có thể b ng khoảng cách Euclide,

M h l no is…

Một thuật toán phân cụm t ng quát sẽ chia bộ dữ liệu x vào k cụm: C1,C2, ... ,CK,(trong

ó Ci ≠ Ci ∩Cj =, X=C1∪C2··· ∪CK i=1:K j = 1: K i≠j) Tƣơng ứng thị có

liên quan sẽ ƣợc cắt th nh k thị con.

Định ngh a 5:

Giã sử T1 = fmst(V, E), ký hiệu MST của G(X) = (V, E). Đ thị v ng h i MST của G(X)

ƣợc ịnh ngh l :

(2.1)

Trong ó fmst:(V E) → T là một hàm t o ra MST từ thị.

Nếu t n t i một ỉnh, gọi là v, trong T1 mà mức ộ của v là |V| -1, v cô lập trong G(V,

E-T1) o ó T2 không thể ƣợc t o ra từ ịnh ngh 5 Để khắc phục sự thiếu hụt trong

ịnh ngh c nh nối với v và chiều dài lớn nhất T1 ƣợc bảo to n ể t o ra T2. Kết hợp

T1 và T2, một thị hai vòng MST, ta có:

Gmst (X) = (V, T1 + T2) = (V, Emst).

Độ dài của các c nh từ T1 và T2 có một mối quan hệ ặc biệt (Định lý 3), có thể ƣợc

sử dụng ể phân vùng thị MST hai vòng.

B ề 1:

Cho T(VT,ET) là một cây. Nếu T’(V’T,E’T) là một cây lớn nhất với V’T⊆VT,

28

E’T∩ET=  th |E’T| = |ET|−1 hoặc |E’T| = |ET|

Ch ng minh:

Nếu |VT|−1 ỉnh của T (VT, ET) có bậc1 v ỉnh khác ỉnh v có bậc |VT|−1 Trong

T, từ bất kỳ ỉnh bậc 1 nào, sẽ có tối | VT | -2 c nh kết nối với các ỉnh khác ngo i trừ

ỉnh kề ... và không có bậc c o hơn ể xây dựng T’(V’T E’T ).

T i thời iểm n y V’T = VT\{v} và |E’T|=|VT|−2=|ET|−1

Ngoài ra gọi ỉnh v0 có bậc l 1 ỉnh kề của nó là v1. Từ v0, sẽ có |VT|−2 c nh có thể

ƣợc sử dụng ể xây dựng T’(V’T,E’T). Th m v o ó phải t n t i một c nh giữ ỉnh v1

v ỉnh không kề với v1.

T i thời iểm n y V’T = VT v |E’T| = |VT|−1 = |ET|.

H quả 2:

Cho F(VF , EF) là một chu trình, giả sử F’(V’F E’F) là một chu trình, V’F ⊆VF,

E’F∩EF = v ối với bất kỳ e∈E’F, F(VF, EF∪{e}) thì |E’F|  |EF|.

Định lý 3:

Giả sử T1 và T2 l v ng ầu tiên và vòng thứ hai của MST hai vòng của G(V,E). Nếu

c nh của T1 và c nh của T2 ƣợc sắp xếp theo chiều t ng:

thì trong ó i iểu thị số thứ tự của

c nh và

Ch ng minh :

Giả sử t n t i j mà

Rõ ràng trong thuật toán Kruskal xây dựng một MST,

lý do mà kh ng ƣợc chọn trong ƣớc thứ j ể xây dựng T1 là sự kết hợp

của bất kỳ một trong số các c nh sẽ t o ra một chu kỳ trong T1 Đặt

từ , thì và là từ F(VF, EF) và

ƣợc thành phần của T1 và T2 theo thứ tự. Bởi vì nếu bất cứ c nh nào của

thêm vào , sẽ là chu trình, chúng ta có . Tuy nhiên, |EF|=

j – 1 và |EF|= j, v iều này trái với hệ quả2.

Đối với một cây, bất cứ khi nào lo i bỏ một c nh sẽ dẫn ến một phân vùng.

29

Trong khi ó ể phân vùng một thị MST hai vòng, ít nhất là hai c nh phải lo i bỏ,

trong ó có t nhất một c nh ến từ T1 và T2 tƣơng ứng Theo ó, so với một vết cắt

trên MST, vết cắt tr n thị MST h i v ng i hỏi nhiều b ng chứng hơn v có thể t o

ra một phân vùng vững chắc hơn

Hình 2.3. Minh họa MST hai vòng

 H nh ( ) l v ng ầu tiên của MST, tức là T1, và ab là c nh quan trọng và dự kiến

sẽ bị lo i bỏ trong phƣơng pháp phân cụm MST.

 Hình (b) là vòng thứ hai của MST tức là T2.

 Hình (c) minh họ thị hai vòng MST.

 Hình (d) mô tả 20 c nh trên với trọng lƣợng lớn tr n cơ sở ịnh ngh 2 H i c nh

ầu tiên cho kết quả là một vết cắt thị phù hợp. Trong 20 c nh ầu, 17 c nh ến từ

T2, và 3 từ T1 .

Phân t ch thị hai vòng MST của một số bộ dữ liệu rời v ộ i tƣơng ứng

ƣợc ịnh ngh ở trên, chúng ta thấy r ng thị h i v ng MST v ộ dài có ba tính

n ng tốt:

Thứ nhất: Độ dài các c nh liên cụm lớn hơn so với c nh nội bộ.

Thứ hai: Các c nh liên cụm ƣợc phân phối gần b ng nhau vào T1 và T2 .

Thứ ba: Ngo i trừ các c nh liên cụm, hầu hết các c nh có ộ dài lớn ều i từ T2 ,

30

và nó phù hợp ịnh lý 3.

Xét t nh n ng ầu tiên, một vết cắt thị MST hai vòng có thể t o ra b ng cách

lo i bỏ các c nh lớn nhất từng i một H i t nh n ng tiếp theo cho thấy vết cắt hợp lệ

hay không có thể ƣợc xác ịnh b ng cách phân tích sự phân bố các c nh bị lo i bỏ.

Thuật toán 1. thuật toán nhận dạng tách cụm (gom các cụm rời)

Input: G (X) = (V, E), bộ dữ liệu củ thị ể phân vùng

Output: S, tập hợp các bộ dữ liệu con ƣợc phân vùng.

Bƣ c 1. Tính toán T1 và T2 của G(X), kết hợp 2-MSTs ể xây dựng thị MST hai

v ng Gmst(X) v ặt nó vào một bảng với tên Open, t o thêm một bảng trống mang tên

là Closed.

Bƣ c 2. Nếu bảng Open trống, bộ dữ liệu con tƣơng ứng với thị con trong bảng

Closed sẽ ƣợc ƣ v o S; trả về S . Bƣ c 3. Có ƣợc một thị G’(X) = (V’, E’) ngoài bảng Open, tính toán ộ dài của c nh G’(X’) với biểu thức (2.2), và xây dựng danh sách Rank (E’). Bƣ c 4. Lo i bỏ các c nh của G’(X’) theo thứ tự R nk (E) cho ến khi có ƣợc một vết

cắt.

Bƣ c 5. Nếu vết cắt phù hợp ịnh ngh 8 ặt h i thị con ƣợc t o ra bởi việc cắt

vào trong bảng Open ; nếu kh ng ặt thị G’(X’) v o ảng Closed.

Bƣ c 6. Quay trở l i ƣớc 2.

Thuật toán 1 lặp l i việc kiểm tr thị con v các phân vùng cho ến khi t n t i thị

con không rời.

Định ngh a 6:

Cho Gmst (X) = (V, Emst) là một thị hai vòng dựa trên MST,

eab ∈ Emst và a, b ∈ V, w(eab) là trọng lƣợng của eab với :

và p(e) là khoảng cách Euclide của c nh e .

Định ngh a 7.

31

Cho Rank (Emst) là một danh sách các c nh sắp xếp theo chiều giảm về ộ i nhƣ s u:

Định ngh a 8:

Cho Egcut là một tập các c nh bị lo i bỏ khi t o ra một thị cắt trên một thị MST

hai vòng, nếu ngƣỡng sau:

Trong ó  là một ngƣỡng th thị cắt hợp lệ, nếu không thì không hợp lệ. Nếu thị

Hình 2.4. Minh họa cụm tách về mật độ

cắt ầu tiên hợp lệ, các cụm ƣợc gọi là rời, nếu không thì là không rời.

 Hình (a) minh họ v ng ầu tiên của MST

 Hình (b) mô tả vòng thứ hai của MST.

 Hình (c) l thị hai vòng MST; bu và bv là các c nh nối tới ab bởi véctơ

b, trong khi as và at nối tới ab bởi Độ dài trung bình củ h i nhóm tƣơng ối khác

biệt.

 Hình (d) minh họa vết cắt thị Đƣờng cong ứt là vết cắt thị t o bởi

việc lo i bỏ chín c nh trên dựa trên ịnh ngh 2 tỷ số (Egcut) b ng 0,444 và lớn hơn

Hình 2.5. Minh họa cụm không thể tạch được hơn nữa

ngƣỡng  .

32

 Hình (a) minh họa bộ dữ liệu con của hình 2.4(c);

 Hình (b) thuật toán phân cụm rời ƣợc áp dụng cho các bộ dữ liệu con. Khi t o ra

một vết cắt th nó ƣợc vẽ bởi các ƣờng cong ứt, tỉ số (Egcut) b ng 0,304 và thấp hơn

1 là danh sách củ N−1 phân vùng tr n T1.

ngƣỡng . Định ngh a 9: Cho PT

(2.5)

Trong ó cặp biểu thị các phân vùng t o từ việc lo i bỏ c nh thứ i trong T1,

và là tập con các ỉnh Tƣơng tự, danh sách N-1 phân

vùng trên ƣợc ịnh ngh l :

(2.6)

Rõ ràng là một số phân vùng từ T1 và T2 có thể rất sai lệch. Tuy nhiên, một phân vùng

hợp lệ có thể t o ra hai tập con với các số thành phần cân b ng tƣơng ối trong một số

phƣơng pháp phân vùng thị iển hình, chẳng h n nhƣ tỷ lệ cắt. Vì vậy, các danh sách phân vùng P T1 và PT2 có thể ƣợc lọc b ng cách bỏ qua phân vùng sai lệch ể giảm số

Hình 2.6. Minh họa cụm với tỉ lệ cut khác nhau

l nh sách ã lọc, tất cả các phần tử của RPT1 từ PT1

và tất cả các

so sánh.

nhƣ ƣới ây:

Định ngh a 10: và RPT2 Cho RPT1 phần tử của RPT2 từ PT2

(2.7)

33

(2.8)

Trong ƣớc tiếp theo, phân vùng RPT1 sẽ ƣợc so sánh với những phân vùng trong RPT2 . Vì số lƣợng các ỉnh ối diện giữa hai vết cắt phải nhỏ hơn hoặc b ng

ngƣỡng nếu , so sánh giữa hai phân vùng và có

thể bỏ qua.

Để tiết kiệm chi phí tính toán, chúng ta có thể tiếp tục kết hợp hai danh sách RPT1

và RPT2

và RPT2 và sắp xếp theo thứ tự t ng ần các số thành phần của phần bên trái trong cặp. Định ngh a 11: Cho SP là một tập bao g m tất cả các phần tử của RPT1

(2.9)

Định ngh a 12. Với một sp ∈SP, cho left(sp) biểu thị phần bên trái của sp, soure của

sp ƣợc ịnh ngh l :

1 nếu sp từ T1

(2.10) Soure (Sp) =

0 ến từ iểm khác

Ví dụ : nếu thì và Soure (Sp) =1

Định ngh a 13:

Cho CP(SP)=[(cp11,cp12)…(cp(L+M)1, cp(L+M)2] l nh sách ã sắp xếp :

CP(SP) =[part_min(SP).CP(SP-{part_min(SP)})]. (2.11)

SP|left(sp)| là một toán tử ràng buộc.

Trong ó p rt_min(SP) = agr minsp

Định ngh a 14:

Hai phân vùng (cpi1,cpi2) và (cpj1,cpj2) l tƣơng ƣơng với i  j , nếu thỏa mãn những

yếu tố sau:

(a) source((cpi1, cpi2)) source((cpj1,cpj2)) ;

(b) |cpi1-cpj1|+|cpj1-cpi1| or |cpi1-cpj2|+|cpj2-cpi1|

Điều kiện ầu tiên cho thấy từ h i phân vùng MST khác nh u trong khi iều kiện thứ

hai cho thấy số ỉnh ối diện giữ h i phân vùng l ủ nhỏ.

Thuật toán 2. Thuật toán phân cụm tự đ ng

Input: T1 và T2, hai vòng MST của một bộ dữ liệu con ƣợc t o bởi thuật toán 1.

Output: S , tập hợp các phân vùng dự kiến .

34

Bƣ c 1. T o r các list ã sắp xếp CP (SP) với T1 and T2, t o ra hai tập rỗng S’ v S

Bƣ c 2. Với mỗi (cpi1, cpi2 ) ∈ CP (SP), so sánh nó với (cpj1, cpj2) ∈ CP (SP) và j> i.

Từ ịnh ngh 14, nếu t n t i một phân vùng (cpj1 cpj2) tƣơng ƣơng với (cpi1, cpi2)

th ƣợc ƣ v o S

Bƣ c 3 Đối với mỗi s ∈ S, nếu t n t i một t ∈ S’ t ≠ s v tƣơng ƣơng với

s ƣ s v o S

Bƣ c 4 : Kết hợp các phân vùng tƣơng ƣơng S

Trong thuật toán 2 ƣớc 3 l ể lo i bỏ các phân vùng không mong muốn trong quan

sát 2 Để ơn giản, chỉ những phân vùng kh ng tƣơng tự bị lo i bỏ. Trong ƣớc 3, khi

xác ịnh sự tƣơng ƣơng giữa t và s, chúng ta bỏ qua việc nó ến từ những MST khác

hay không, từ gi i o n này chỉ quan tâm tới số các ỉnh ối diện ƣớc 4 kết hợp các

phân vùng tƣơng ƣơng ng cách xếp các ỉnh ối diện vào hai nhóm về các (tỷ lệ hỗ

trợ) t ch lũy ƣợc từ các phân vùng tƣơng ƣơng [3]

Nhận x t:

Thuật toán 1 tự ộng nhận d ng tách cụm và không ảnh hƣởng ến cặp cụm tự

ch m nh u, thuật toán 1 và 2 có thể dễ dàng kết hợp ể ối phó với bất kỳ vấn ề n o về

cụm. Khi tất cả các tập con phân chia bởi thuật toán 1 ƣợc ƣ v o thuật toán 2, th sự

phân cụm sẽ có ƣợc kết quả phân nhóm thực o ó h i thuật toán có thể dễ dàng kết

hợp ể t o phƣơng pháp 2 – MSTs.

Nhiều thuật toán phân cụm truyền thống không chắc chắn với những kích cỡ cụm,

hình d ng và mật ộ. Tuy nhiên, kể từ khi cụm rời và cụm tự tách ƣợc ề xuất gần nhƣ

có thể thỏ mãn y u cầu bao g m tất cả các lo i cụm (trừ cụm ch ng).

2.5. Đ ph c tạp của thuật to n 2-MSTs:

Sự phức t p trong tính toán của thuật toán 1 ƣợc phân t ch nhƣ s u:

Cho thị G(X) = (V, E), nếu ãy Fi on cci ùng ể thiết lập h ng ợi ƣu ti n nhỏ nhất,

thời gian ch y thuật toán MST củ Prim l O(|E| + |V| log|V|) Nhƣ MST trong một

phƣơng pháp phân cụm tr n thị thƣờng ƣợc xây dựng từ một thị ầy ủ ,| E | = |V| 2 và thời gian tính của thuật toán của Prim là O( |V|2).

Ở ƣớc 1, T1 và T2 ƣợc t o ra trong O(N2) trong khi ƣớc 3 xếp danh sách

35

R nk(E’) trong O(N log N) ƣớc 4 lo i bỏ lặp l i một c nh củ G’(X’) v kiểm tra xem

có vết cắt h y kh ng trong O(| X |log| X’|) trong ó | X |  N. Thời gian lặp từ ƣớc 2

ến ƣớc 6 là số các cụm rời trong bộ dữ liệu, nhìn chung là nhỏ hơn rất nhiều so với N. o ó ộ phức t p của thuật toán 1 là O(N2).

Ở ƣớc 1 của thuật toán 2, xây dựng SP cần O(N2), và sắp xếp CP (SP) cần O(N log N). Kết quả l ƣớc 1 có thể ƣợc thực hiện trong O(N2). Việc lặp trong ƣớc 2 của

thuật toán 2 có thể ƣợc hoàn thành trong O(N log N).

Cả h i ƣớc 3 và 4 trong thuật toán 2 ƣợc thực hiện trong O(N) Độ phức t p

36

tính toán của thuật toán 2 là O(N2). Vậy phƣơng pháp 2-MSTClus g m các thuật toán 1 và 2 có thời gian t ng là O(N2).

CHƢƠNG 3: THỰC NGHIỆM NG DỤNG

3.1. Gi i thi u

Để làm sáng tỏ kỹ thuật phân cụm của thuật toán 2- MSTs ã tr nh y chƣơng tr nh

sẽ thử nghiệm với 2 bộ dữ liệu li n qu n ến ngành hàng không, một bộ dữ liệu thực

ƣợc thu thập từ t ng công ty hàng không Việt Nam, một bộ dữ liệu không thực(tự

t o ể test thử chƣơng tr nh)

3.2. Chƣơng tr nh và kết quả thử nghi m

3.2.1. Chƣơng tr nh

37

Chƣơng tr nh viết b ng ngôn ngữ ASP. net trong môi trƣờng Visual Stadio 2010

Hình 3.1. Giao diện code chương trình

Hình 3.2. Giao diện khi chạy chương trình

3.2.2. ết quả thử nghi m  Từ tập ữ i u 1: Tập dữ liệu g m 21 ối tƣợng và 10 thuộc tính, trong tập thuộc tính của dữ liệu

có 7 thuộc tính có thông tin ảnh hƣởng trực tiếp ến quá trình phân cụm ó l các

thuộc tính có dữ liệu số.

Mỗi thuộc tính có dữ liệu số s u khi t nh toán T1 v T2 ể nhận ng tách cụm

sẽ có 2 tập f i diện trong h nh 3 4 ã thể hiện iều ó.

Ví dụ: Với thuộc tính scbkehoach, có 2 tập f i diện ó l f1 v f2 trong ó f1

= 1 và f2 = 0, với f có giá trị b ng 1 thể hiển có kết nối ến từ T1, và f có giá trị b ng

38

0 thể hiện ến từ iểm khác ( ịnh ngh 12).

Hình 3.3. Bảng kế hoạch khai thác bay

Từ bảng kế ho ch kh i thác y t thu ƣợc bảng nhận d ng tách cụm nhƣ s u:

Hình 3.4. Bảng sau khi tính toán 1 và 2 nhận dạng tách cụm

39

Từ hình 3.4, bảng sau khi tính toán T1 và T2 nhận d ng tách cụm, ta Tính toán

entropy ể tìm giá trị Gain tốt nhất dụng l m ộ o ể lựa chọn thuộc tính phân cụm

(t m iểm chia cụm). Với entropy lần 1 t thu ƣợc bảng G in nhƣ h nh 3 5

Bảng Gain của các thuộc tính với entropy lân 1

Hình3.5: Bảng Gain của các thuộc tính

Từ bảng Gain ta nhận thấy f10 có giá trị lớn nhất nên thuộc tính f10 ƣợc chọn

ể phân cụm. Vì f10 có 2 giá trị 0 và 1 nên ta có:

 Với f10 nhận giá trị 0 ta có cụm

40

Hình 3.6 : Bảng với f10 nhận giá trị 0

 Với f10 nhận giá trị 1 ta có cụm

Hình 3.7: Bảng với f10 nhận giá trị 1

Với kết quả này ta không phải phân cụm cho f10 có giá trị 1 nữa vì nhận thấy các

giá trị trong cụm ã có ộ tƣơng ng khá cao, nếu tiếp tục phân cụm thì sẽ có tính lặp

l i.

Tiếp tục phân cụm f10 nhận giá trị 0 ta có bảng Gian của các thuộc t nh nhƣ s u

41

Hình 3.8: Bảng tính ain của các thuộc tính lần 2

Ta nhận thấy vì Gain của f13 và f14 là lớn nhất, nên ta chọn thuộc tính f13 hoặc

f14 ể phân cụm. Giả sử ta lấy f13, với f13 vì có 2 giá trị 0 và 1 nên ta có:

Hình 3.9: Bảng f13 nhận giá trị bằng 0

Với f13 nhận giá trị b ng 0 ta có cụm:

Hình 3.10: Bảng f13 nhận giá trị bằng 1

Với f13 nhận giá trị b ng 1 ta có cụm:

Với kết quả này ta không phải phân cụm cho f13 có giá trị b ng 0 và b ng 1 nữa

vì nhận thấy các giá trị trong các cụm ã có ộ tƣơng ng khá cao, nếu tiếp tục phân

cụm thì sẽ có tính lặp l i.

Nhƣ vậy với tập dữ liệu 1, sau khi sử dụng thuật toán 2 – MSTs t thu ƣợc 4

42

cụm nhƣ s u:

KẾT QUẢ C C CỤM ĐƢ C PH N CHIA

43

Hình 3.11. Bảng kết quả ph n cụm sau khi tính entropy lần 1

44

Hình 3.12. Bảng kết quả ph n cụm sau khi tính entropy lần 1

Hình 3.13. Bảng kết quả ph n cụm sau khi tính entropy lần 2

Hình 3.14. Bảng kết quả ph n cụm sau khi tính entropy lần 2

Nhận xét:

Trong 4 cụm ã tách ƣợc từ tập dữ liệu, mỗi cụm có một s ặc trƣng ri ng nhƣ

sau: Cụm có số chuyến bay hủy thì không có th y i lịch bay, cụm có th y i lịch bay

thì không có số chuyến bay hủy, hay cụm không có số chuyến bay hủy cũng nhƣ kh ng

có th y i lịch bay,.. từ những tri thức thu ƣợc n y nh iều khiển bay có thể tận dụng

45

ể khai thác trên các sân bay hay thị trƣờng ó ể phục vụ cho lợi ích của mình.

 Từ tập ữ i u 2:

Tập dữ liệu n y ƣợc thử nghiệm với 11 ối tƣợng và 10 thuộc tính, dữ liệu ƣ v o rất

thiếu thực tế, không có tính logic nên t m gọi là dữ liệu không thực.

Hình 3.15. Bảng dữ liệu thử nghiệm lần 2

Hình 3.16. Bảng sau khi tính toán 1 và 2 nhận dạng tách cụm

Với cách thức thử nghiệm tƣơng tự nhƣ với tập dữ liệu 1, sau khi phân cụm thuật

46

toán cũng ƣ r ƣợc 4 cụm nhƣ s u:

KẾT QUẢ C C CỤM ĐƢ C PH N CHIA

Hình 3.17. Bảng kết quả ph n cụm sau khi tính enropy lần 1

Hình 3.18. Bảng kết quả ph n cụm sau khi tính enropy lần 2

Nhận xét:

Vậy với dữ liệu không thực thì sau khi tiến hành thí nghiệm, kết quả vẫn cho ta là 4

cụm nhƣng thực chất là chỉ có 2 cụm vì có sự trùng lặp giữa các cụm. Vậy với dữ liệu

47

xa thực tế với ngƣời sử dụng, không có tính logic thì kết quả sẽ bị sai lệch.

KẾT LUẬN

Sau một thời gian làm việc ƣới sự hƣớng dẫn tận tình của thầy giáo PGS.TS

Hoàng Xuân Huấn luận v n củ em ã t ƣợc các kết quả s u ây:

1. T ng hợp l i kiến thức về khám phá tri thức và phân cụm dữ liệu.

2. Tìm hiểu thuật toán 2-MSTs ã ƣợc ề xuất v c i ặt thuật toán.

3. Thử nghiệm thuật toán với 2 bộ dữ liệu li n qu n ến ng nh h ng kh ng v ƣ

ra kết quả thử nghiệm, so sánh v ánh giá các kết quả.

- Do thời gian nghiên cứu có h n v n ng lực bản thân còn h n chế, luận v n chắc

chắn sẽ còn nhiều thiếu sót. Tôi rất mong nhận ƣợc ý kiến óng góp của các Thầy Cô.

- Trong thời gian tới, tôi sẽ cố gắng tìm hiểu nhiều hơn nữa về các phƣơng pháp

phân cụm dữ liệu ặc biệt l phƣơng pháp phân cụm dữ liệu dự tr n thị sử dụng cây

khung cực tiểu và cố gắng mở rộng ứng dụng của thuật toán vào nhiều bài toán thực tế.

- Em xin cảm ơn Thầy PGS.TS. Hoàng Xuân Huấn về sự hỗ trợ chân thành và

nhiệt tình trong suốt thời gian qua.

- Em xin gửi lời cảm ơn chân th nh ến các thầy c ộ ã giảng y các cán ộ

48

trong kho c ng nghệ th ng tin kho s u i học ph ng t chức h nh ch nh

TÀI LIỆU THAM KHẢO

Tiếng vi t

[1] PGS.TS Hoàng Xuân Huấn (2012), Giáo trình Nhận dạng mẫu Trƣờng Đ i học

công nghệ - Đ i Học Quốc Gia Hà Nội.

[2]. PGS.TS Đỗ Đức Giáo, Toán học rời r c Giáo tr nh kho CNTT ĐHKHTN

ĐHQGHN 1998

Tiếng Anh

[3] Caiming Zhong1,2,3, Duoqian Miao1,2,4, Ruizhi Wang1,2, Agraph-theoretical

clustering method based on two rounds ofminimum spanning trees,

1) Department of Computer Science and Technology, Tongji University,

Shanghai 201804, PR China

2) Key Laboratory of Embedded System & Service Computing, Ministry of

Education of China, Shanghai 201804, PR China

3) College of Science and Technology, Ningbo University, Ningbo 315211, PR

China

4) Corresponding author at: Department of Computer Science and Technology,

Tongji University, Shanghai 201804, PR China.

[4] Alan Rea (1009), Data mining - An introdution, The Parallel Computer Center, The

Queen’s University of elf st

[5] Daniel T.Larose, Discovering knowledge in data, Wiley Publishing 2011.

[6] Jiawei Han, Micheline Kamber, Data Mining Concepts and techniques, Second

Edition, Elsevier Inc, 2011.

[7]

Ji wei H n n Micheline K m er (2001) “ t Mining: Concepts n Techniques” Hacours Science and Technology Company, USA.

[8] L. John, “Operational Data Stores: Building an Effective Strategy”, Data

Warehouse: Practical Advive from the Experts, Prentice Hall, NJ, 2009.

[9] P. Berkhin: Survey of Clustering Data Mining Techniques. Research paper.

49

Accrue Software, Inc, http://www.accrue.com, 2009.

[10] Anil K.Jain, Richard C.Dubes (1988), Algorithms for Clustering Data.

[11] niel r r Juli Couto Yi Li (Octo er 1 2001) “COOLCAT: An entropy-

se lgorithm for c tegoric l clustering” George MasonUniversity Information and

Software Engineering Department Fairfax, VA22030, pp. 582 - 589.

[12] MARIA HALKI I (2001) “On Clustering V li tion Techniques” Kluwer

Academic Publishers, Holland

[13] Usama M. Fayyad, Gregory Piatetsky-Sh piro P hr ic Smyth (1996) “From t

Mining to Knowle ge iscovery”: An Overview, Advances in Knowledge Discovery

and Data Mining 1996, pp. 37 - 54.

50

[14] S. Ghosh, S.K. Dubey (2013), Comparative Analysis of K-Means and Fuzzy C- Means Algorithms, International Journal of Advanced Computer Science and Applications, Vol. 4, No.4, pp. 35-39.