Đề án tốt nghiệp
Thuật toán Phân cụm
dữ liệu nửa giám sát
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
1
LỜI CẢM ƠN
Trước hết, em xin chân thành gửi lời cảm ơn sâu sắc đến cô giáo ThS.Nguyễn Thị
Xuân Hƣơng , người đã tận tình hướng dẫn và tạo mọi điều kiện cho em trong quá trình làm
tốt nghiệp.
Em xin chân thành cảm ơn các thầy cô giáo trong khoa Công Nghệ Thông Tin
Trường Đại Học Dân Lập Hải Phòng đã quan tâm dạy dỗ và giúp đỡ em trong suốt
bốn năm học vừa qua và trong quá trình làm tốt nghiệp.
Em xin chân trọng cảm ơn thầy Trần Hữu Nghị - Hiệu trưởng trường Đại Học Dân
Lập Hải Phòng đã ủng hộ, động viên, và tạo mọi điều kiện tốt nhất để em có thể hoàn
thành 4 năm đại học vừa qua.
Cuối cùng em xin gửi lời cảm ơn chân thành tới tất cả những người thân cùng
bạn bè đã động viên, giúp đỡ và đóng góp nhiều ý kiến quý báu cho em trong quá trình
học tập cũng như khi làm tốt nghiệp.
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
3
GIỚI THIỆU
Trong vài thập niên gần đây, cùng với sự thay đổi và phát triển không ngừng
của ngành công nghệ thông tin nói chung và trong các ngành công nghệ phần cứng,
phân mềm, truyền thông và hệ thống các dữ liệu phục vụ trong các lĩnh vực kinh tế -
xã hội nói riêng. Thì việc thu thập thông tin cũng như nhu cầu lưu trữ thông tin càng
một phương pháp phân cụm dữ liệu mới đó là phương pháp phân cụm dữ liệu nửa
giám sát. Phương pháp phân cụm nửa giám sát không phải là một phương pháp phân
cụm hoàn thiện nhưng nó đã phần nào khắc phục được những hạn chế và phát huy ưu
điểm của phương pháp phân cụm không giám sát. Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
4
MỤC LỤC
LỜI CẢM ƠN 1
MỤC ĐÍCH CỦA ĐỀ TÀI 2
GIỚI THIỆU 3
Chƣơng 1 : TỔNG QUAN VỀ DATA MINING 6
1.1 Giới thiệu về khám phá tri thức 6
1.2 Khai phá dữ liệu và các khái niệm liên quan 7
1.2.1 Khái niệm khai phá dữ liệu 7
1.2.2 Các kỹ thuật tiếp cận trong khai phá cữ liệu 8
Chƣơng 2 : PHÂN CỤM DỮ LIỆU VÀ CÁC TIẾP CẬN 9
2.1 Khái quát về phân cụm dữ liệu 9
2.2 Các kiểu dữ liệu và độ đo tƣơng tự 10
2.3 Những kỹ thuật tiếp cận trong phân cụm dữ liệu 13
2.3.1 Phân cụm phân hoạch 13
2.3.2 Phân cụm dữ liệu phân cấp 13
2.3.3 Phân cụm dữ liệu dựa trên mật độ 14
2.3.4 Phân cụm dữ liệu dựa trên lưới 15
Lưu Tuấn Lâm – CT702
5
6.1 Bài toán 44
6.2 Các thông tin về các loại bảo hiểm nhân thọ 46
6.3 Cài đặt thuật toán Phân cụm nửa giám sát vời dữ liệu hốn hợp 47
6.4 Các hàm thủ tục chính khi thực hiện thuật toán 48
6.4.1 Hàm khởi tạo tâm từ Tập giống 48
6.4.2 Các hàm tính khoảng cách 49
6.4.3 thuật toán Constrained-Kmeans 51
6.5 Giao diện chƣơng trình 55
KẾT LUẬN 60
Tài liệu tham khảo 61
nhiệm vụ của quá trình KDD sẽ được thu thập từ các nguồn dữ liệu ban đầu.
Bước 2: Tiền xử lý dữ liệu: có nhiệm vụ làm sạch, loại bỏ nhiễu, rút gọn và rời
rạc hóa dữ liệu.
Bước 3: Biến đổi dữ liệu: nhằm chuẩn hóa và làm mịn dữ liệu để chuyển dữ
liệu về dạng thuận lợi nhất phục vụ cho việc khai phá.
Bước 4: Data mining: dùng các kỹ thuật phân tích để khai thác dữ liệu, trích
chọn các mẫu thông tin cần thiết,… Công đoạn này được xem là mất thời gian
nhất và cũng là quan trọng nhất trong quá trình KDD.
Bước 5: Đánh giá và biểu diễn tri thức: Các thông tin và mối liên hệ giữa
chúng vừa khám phá trong công đoạn trước được biểu diễn dưới các dạng trực
quan đồng thời được đánh giá theo những tiêu chí nhất định.
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
7
Biến đổi dữ
liệu
Data mining
Đánh giá và
biểu diễn
Tri thức
Dữ liệu
Dữ liệu
tiền xử lý
Mẫu
Hình 1: Quá trình khám phá tri thức trong CSDL
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
8
1.2.2 Các kỹ thuật tiếp cận trong khai phá cữ liệu
Các kỹ thuật áp dụng trong Data mining phần lớn được kế thừa từ các lĩnh vực
như: Cơ sở dữ liệu (Database), Học máy (Machine learning), Trí tuệ nhân tạo, Xác
suất thống kê,… vì vậy ta có hai hướng tiếp cận sau đây:
Theo quan điểm của học máy, các kỹ thuật trong Data mining gồm:
Học có giám sát (Supervised learning): Là quá trình gán nhãn lớp cho
các đối tượng trong tập dữ liệu dựa trên một bộ các đối tượng huấn
luyện và các thông tin về nhãn lớp đã biết.
Học không giám sát (Unsupervised learning): Là quá trình phân chia
một tập dữ liệu thành các lớp hay cụm (cluster) dữ liệu tương tự nhau
mà chưa biết trước các thông tin về nhãn lớp.
Học nửa giám sát (Semi-Supervised learning): Là quá trình chia một
tập dữ liệu thành các lớp con dựa trên một số thông tin bổ trợ cho
trước.
Theo các lớp bài toán cần giải quyết, các kỹ thuật trong Data mining gồm:
định bằng kinh nghiệm hoặc bằng một số phương pháp phân cụm.
Sau khi xác định các đặc tính của dữ liệu, người ta đi tìm cách thích hợp để xác
định "khoảng cách" giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây chính là
các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm
này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar)
giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống
nhau giữa đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ nghịch
với hàm tính độ tương tự.
Trong quá trình phân cụm dữ liệu thì vấn đề trở ngại lớn nhất đó là nhiễu
(noise). Nhiễu xuất hiện do trong quá trình thu thấp thông tin, dữ liệu thiếu chính xác
hoặc không đầy đủ. Vì vậy chúng ta cần phải khử nhiễu trong quá trình tiến hành phân
cụm dữ liệu.
Các bước của một bài toán phân cụm dữ liệu gồm:
Xây dựng hàm tính độ tương tự
Xây dựng các tiêu chuẩn phân cụm
Xây dựng mô hình cho cấu trúc dữ liệu
Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo
Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
10
2.2 Các kiểu dữ liệu và độ đo tƣơng tự
Sau đây là các kiểu của dữ liệu, và ứng với mỗi kiểu dữ liệu thì có một hàm tính
độ đo tương tự để xác định khoảng cách giữa 2 phân tử của cùng một kiểu dữ liệu. Tất
cả các độ đo đều được xác định trong không gian metric. Bất kỳ một metric nào cũng
là một độ đo nhưng ngược lại thì không đúng. Độ đo ở đây có thể là tương tự hoặc phi
tương tự. Một tập dữ liệu X là không gian metric nếu:
với mỗi cặp x,y thuộc X đều xác định được một số thực d(x,y) theo một
quy tắc nào đó và được gọi là khoảng cách của x,y.
+
+
+
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
11
là tổng số các thuộc tính có giá trị 1 trong x và 0 trong y
là tổng số các thuộc tính có giá trị 0 trong x và 1 trong y
là tổng số các thuộc tính có giá trị là 0 trong cả hai đối tượng x, y
Khi đó độ tương tự được cho như sau:
1. Hệ số đối sánh đơn giản:
( , )d x y
, Ở đây x và y có vai
trò như nhau, tức là chúng đối xứng và cùng trọng số.
2. Hệ số Jacard:
( , )d x y
, công thức này được áp
dụng trong trường hợp mà trọng số của các thuộc tính có giá
2. Khoảng cách Euclide:
2
1/ 2
1
( , ) ( )
n
ii
i
d x y x y
, nó là trường
hợp của khoảng cách Minkowski với q = 2.
3. Khoảng cách Mahattan
1
( , ) ( )
n
ii
i
d x y x y
, nó là trường hợp
của khoảng cách Minkowski với q = 1.
Kiểu thuộc tính định danh (Nominal)
Đây là dạng tổng quat hoá của thuộc tính nhị phân, trong đó miền
giá trị là rời rạc không phân biệt thứ tự. Nếu x và y là hai thuộc tính định
. Ta thay thế mỗi x
if
bởi
giá trị tương ứng r
if
[1,M
f
].
2. Vì mỗi thuộc tính f có thứ tự có số lượng các trạng thái khác nhau
nên ta cần làm cho r
if
thuộc khoảng [0.0,1.0] để mỗi thuộc tính đều
có cùng trọng số. Do đó r
if
được thay thế bởi
if
if
1
z
1
f
r
M
3. Cuối cùng ta sử dụng công thức tính độ phi tương tự của thuộc tính
phân hoạch dữ liệu 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
đề PCDL, 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ế người ta 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ác cụm cũng như để hướng
dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Với chiến lược này, thông thường
người ta bắt đầu khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo phép ngẫu
nhiên hoặc theo heuristic, và liên tục tinh chỉnh nó cho đến khi thu được một phân
hoạch mong muốn, thoả mãn ràng buộc cho trước. Các thuật toán phân cụm phân
hoạch cố gắng cải tiến tiêu chuẩn phân cụm, bằng cách tính các giá trị đo độ tương tự
giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn một
giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Như vậy, ý tưởng
chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược ăn tham
(Greedy) để tìm kiếm nghiệm. Một số thuật toán phân cụm phân hoạch điển hình như
k-means, PAM, CLARA, CLARANS,…sẽ được trình bày chi tiết ở chương sau.
2.3.2 Phân cụm dữ liệu phân cấp
Phân cụm phân cấp sắp xếp một tập dữ liệu đã cho thành 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ây phân cụm có thể
được xây dựng theo hai phương pháp tổng quát : phương pháp trên xuống (Top down)
và phương pháp dưới lên (Bottum up).
Phƣơng pháp “dƣới lên” (Bottom up) : Phương pháp này bắt đầu với
mỗi đối tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó tiến hành nhóm
các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung tâm của hai
nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm được hòa nhập vào
một nhóm (mức cao nhất của cây phân cấp) hoặc cho đến khi các điều kiện kết thúc
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
14
thỏa mãn. Như vậy, cách tiếp cận này sử dụng chiến lược ăn tham trong quá trình phân
cụm. Hình 2 : Một số hình dạng cụm dữ liệu khám phá đƣợc bởi kỹ thuật PCDL dựa
trên mật độ
Một số thuật toán PCDL dựa trên mật độ điển hình như DBSCAN, OPTICS,
DENCLUE, …sẽ được trình bày chi tiết trong chương tiếp theo.
2.3.4 Phân cụm dữ liệu dựa trên lưới
Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu nhiều chiều, để
giải quyết cho đòi hỏi này, người ta đã dử dụng phương pháp phân cụm dựa trên lưới.
Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để PCDL, phương pháp này chủ
yếu tập trung áp dụng cho lớp dữ liệu không gian. Thí dụ như dữ liệu được biểu diễn
dưới dạng cấu trúc hình học của đối tượng trong không gian cùng với các quan hệ, các
thuộc tính, các hoạt động của chúng. Mục tiêu của phương pháp này là lượng hoá tập
dữ liệu thành các ô (Cell), các cell này tạo thành cấu trúc dữ liệu lưới, sau đó các thao
tác PCDL làm việc với các đối tượng trong từng Cell này. 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 cell mà xây dựng nhiều mức phân cấp
của nhóm các đối tượng trong một cell. Trong ngữ cảnh này, phương pháp này gần
giống với phương pháp phân cụm phân cấp nhưng chỉ có điều chúng không trộn các
Cell. Do vậy các cụm không dựa trên độ đo khoảng cách (hay còn gọi là độ đo tương
tự đối với các dữ liệu không gian) mà nó được quyết định bởi một tham số xác định
trước. Ưu điểm của phương pháp PCDL dựa trên lưới là thời gian xử lý nhanh và độc
lập với số đối tượng dữ liệu trong tập dữ liệu ban đầu, thay vào đó là chúng phụ thuộc
vào số cell trong mỗi chiều của không gian lưới. Một thí dụ về cấu trúc dữ liệu lưới
chứa các cell trong không gian như hình 6 sau :
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
phân cụm phân hoạch hoặc chiến lược phân 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 mà chúng tinh chỉnh các mô hình này
để nhận dạng ra các phân hoạch.
Phương pháp PCDL dựa trên mô hình cố gắng khớp giữa 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 phân cụm dựa trên mô hình có hai tiếp cận chính : Mô hình thống
kê và Mạng Nơ ron. Phương pháp này gần giống với phương pháp dựa trên mật độ,
bởi vì chúng phát triển các cụm riêng biệ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 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.
2.3.6 Phân cụm dữ liệu có ràng buộc
Sự phát triển của phân cụm dữ liệu không gian trên CSDL 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 hầu hết các thuật
toán này cung cấp rất ít cách thức cho người dùng để xác định các ràng buộc trong thế
giới thực cần phải được thoả mãn trong quá trình PCDL. Để phân cụm dữ liệu không
Mức 1 (mức cao nhất ) có thể
chỉ chứa một Cell
Cell mức i-1 có thể tương ứng
với 4 cell của mức i
Tầng 1
.
.
.
.
.
Tầng i-1
Tầng i
cho các phương pháp phân cụm PCDL.
2.4 Một số ứng dụng của phân cụm dữ liệu
Phân cụm dữ liệu được ứng dụng vào rất nhiều lĩnh vực như thương mại, sinh
học, phân tích dữ liệu không gian, lập quy hoạch đô thị, nghiên cứu trái đất, địa lý,
Web,…
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
18
Trong thương mại, phân cụm có thể giúp các thương gia tìm kiếm ra các nhóm
khách hàng quan trọng cũng như phân loại khách hàng thành từng nhóm khách hàng
để từ đó có chiến lược kinh doanh hợp lý.
Trong sinh học, phân cụm được dùng để xác định các loài sinh vật cũng như
khám phá ra các kiểu gene quý hiếm.
Trong phân tích dữ liệu không gian: Do sự đồ sộ của dữ liệu không gian như
các hình ảnh vệ tinh hoặc hệ thống thông tin địa lý ,… làm cho người dùng khó khăn
trong phân tích và xử lý chúng. Phân cụm có thể giúp chúng ta tự động nhận dạng và
chiết xuất các đặc tính trong cơ sở dữ liệu không gian.
Trong lập quy hoạch đô thị, phân cụm giúp cho việc nhận dạng cá nhóm nhà
theo kiến trúc và vị trí địa lý để lập quy hoạch đô thị hợp lý.
Trong nghiên cứu trái đất, phân cụm hỗ trợ việc theo dõi các biến động của trái đất
như núi lửa, động đất,… để đưa ra cảnh báo cho chúng ta.
i
Xx
là tập N
đối tượng dữ liệu ta muốn phân cụm, trong đó
d
i
x
. Thuật toán phân cụm có nhiệm
vụ chia nhỏ tập dữ liệu thành K phân hoạch ( K là giá trị cho trước) mà mỗi phân
hoạch đại diện cho một cụm. Các cụm được hình thành trên cơ sở làm tối ưu giá trị
hàm mục tiêu (thường là hàm đo độ tương tự) để sao cho các đối tượng trong một cụm
là tương tự nhau trong khi các đối tượng trong các cụm khác nhau thì phi tương tự
nhau.
Có rất nhiều thuật toán phân cụm phân hoạch như : K-Means, K-Medoids,
PAM (Partition Around Medoids), CLARA (Clustering Large Applications),
CLARANS (Clustering Large Applications based on RAndomized Search), CLASA
(Clustering Large Applications based on Simulated Annealing).Ở đây em xin trình bày
về hai thuật toán K-Means và K-Medoids. Trong K-Means mỗi cụm được đại diện bởi
giá trị tâm (mean) của các đối tượng trong cụm đó. Trong K-Medoids mỗi cụm được
đại diện bởi một trong các đối tượng gần tâm cụm nhất.
3.1.1 Thuật toán K-Means
K-Means lặp lại nhiều lần quá trình bố trí lại vị trí của đối tượng dữ liệu để
phân hoạch một tập dữ liệu thành K cụm và cực tiểu địa phương giá trị bình phương
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
20
trung bình khoảng cách giữa các các đối tượng tới tâm cụm của nó. Cụ thể hơn, với tập
đại diện cho K tâm thì hàm mục tiêu sau:
2
1
|| || (1)
ih
K
kmeans i h
xX
h
Ex
được cực tiểu địa phương.
h
h
X
của
X
sao cho hàm
mục tiêu được tối ưu.
Các bƣớc:
1. Khởi tạo các cụm: các tâm ban đầu
(0)
1
K
h
h
được chọn
ngẫu nhiên
2. Lặp cho tới khi hội tụ
Gán cụm: Gán mỗi đối tượng dữ liệu x vào cụm h
*
(tức là tập
*
( 1)
1
K
t
X
t
t+1
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
21
1. Chọn K đối tượng bất kỳ trong N đối tượng ban đầu làm các medoid
ban đầu
2. Lặp cho tới khi hội tụ
a) Gán mỗi đối tượng còn lại vào cụm có medoid gần nhất với nó
b) Thay thế medoid hiện tại bằng một đối tượng không phải là
medoid sao cho chất lượng phân cụm được cải thiện (Chất lượng
được đánh giá sử dụng hàm chi phí, hàm tính độ phi tương tự
giữa một đối tượng và medoid của cụm chứa đối tượng đó).
K-Medoids tỏ ra hiệu quả hơn K-Means trong trường hợp dữ liệu có nhiễu
hoặc đối tượng ngoại lai (Outlier) . Nhưng so với K-Means thì K-Medoids có độ phức
tạp tính toán lớn hơn. Cả hai thuật toán trên đề có nhược điểm chung là số lượng cụm
K được cung cấp bởi người dùng.
3.2 Phƣơng pháp phân cấp
Sau đây em xin trình bày hai thuật toán điển hình của phương pháp phân cụm
phân cấp đó là: CURE (Clustering Using REpresentatives), BIRCH (Balanced
Interative Reducing and Clustering Hierarchies)
3.2.1 Thuật toán CURE
CURE là thuật toán sử dụng chiến lược bottom-up của phương pháp phân cụm
phân cấp. Khác với hai thuật toán phân cụm phân hoách ở trên thuật toán CURE sử
dụng nhiều đối tượng để biểu diễn cho một cụm thay vì sử dụng các trọng tâm hay đối
tượng tâm. Các đối tượng đại diện của một cụm ban đầu được chọn rải rác đều ở các vị
trí khác nhau, sau đó chúng được di chuyển bằng cách co lại theo một tỉ lệ nhất định
nào đó. Khi hai cụm có cặp đối tượng đại diện gần nhất sẽ được trộn lại thành một
cụm.
Các bước thực hiện của thuật toán CURE:
1. Chọn một mẫu ngẫu nhiên S từ tập dữ liệu ban đầu
2. Phân hoạch mẫu S này thành các nhóm dữ liệu có kích thước bằng
nhau
3. Tiến hành phân cụm riêng rẽ cho mỗi nhóm
bottom-up
step 0
step 1
step 3
step 2
step 4
step 4
step 3
step 1
phá được các cụm có hình thù và kích thước bất kỳ trong tập dữ liệu lớn. Việc
co các đối tượng đại diện có tác dụng làm giảm tác động của các đối tượng
ngoại lai. Do đó CURE có thể xử lý tốt các đối tượng ngoại lai. Tốc độ thực
hiện của CURE nhanh O(N).
Nhƣợc điểm:
CURE là dễ bị ảnh hưởng bởi các tham số cho bởi người dùng như cỡ mẫu, số
cụm mong muốn.
3.2.2 Thuật toán BIRCH
BIRCH là thuật toán phân cụm phân cấp sử dụng chiến lược Top-down. Tư
tưởng của BIRCH là không lưu toàn bộ đối tượng dữ liệu của các cụm trong bộ nhớ
mà chỉ lưu các tham số thống kê. Đối với mỗi cụm dữ liệu, BIRCH chỉ lưu bộ ba (N,
LS, SS), trong đó N là số đối tượng trong cụm, LS là tổng các giá trị thuộc tính của
Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát
Lưu Tuấn Lâm – CT702
24
các đối tượng trong cụm, và SS là tổng bình phương của các giá trị thuộc tính của các
đối tượng trong cụm. Bộ ba này được gọi là đặc trưng cụm (Cluster Feature- CF). Khi
đó các cụm trong tập dữ liệu ban đầu sẽ được cho dưới dạng một cây CF. Người ta đã
chứng minh được rằng các đại lượng thống kê như độ đo có thể xác định từ cây CF.
Hình 4 sau đây mô tả cấu trúc cây CF.
Gốc
……….
Lớp đầu
.
.
.
.
.
Hình 6: Cấu trúc cây CF
Copyright: Tài liệu đại học ©