Luận văn Phân cụm dựa trên tri thức theo từng cặp
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
ĐỖ VĂN VIỆT
PHÂN CỤM DỰA TRÊN TRI THỨC THEO TỪNG CẶP
Ngành: Hệ thống Thông tin
Chuyên ngành: Hệ thống Thông tin
Mã Số: 8480104.01
LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. HOÀNG XUÂN HUẤN
Hà Nội – 09/2020
i
LỜI CAM ĐOAN
Tôi Đỗ Văn Việt xin cam đoan những nội dung trình bày trong luận văn
này là kết quả tìm hiểu, nghiên cứu của bản thân dưới sự hướng dẫn của
PGS.TS. Hoàng Xuân Huấn. Mọi thông tin tham khảo sử dụng trong luận văn
đều được trích dẫn đầy đủ và hợp pháp.
Nếu có gì sai phạm, tôi xin hoàn toàn chịu trách nhiệm.
Hà Nội, tháng 09 năm 2020
Đỗ Văn Việt
ii
LỜI CẢM ƠN
Trong quá trình thực hiện luận văn, tôi đã gặp rất nhiều khó khăn. Nhưng
tôi luôn nhận được sự ủng hộ, giúp đỡ từ các thầy cô, bạn bè và gia đình. Khi
hoàn thành xong luận văn này, tôi thực sự rất biết ơn họ.
Tôi xin gửi lời cảm ơn chân thành tới PGS.TS. Hoàng Xuân Huấn đã tận
tình hướng dẫn và chỉ bảo tôi trong suốt quá trình thực hiện luận văn. Được
nhận sự giúp đỡ của Thầy, với em là một món quà vô cùng quý giá trong cuộc
đời này. Một lần nữa em gửi lời cảm ơn, lời biết ơn tới Thầy.
Tôi xin chân thành cảm ơn các quý Thầy Cô trường Đại học Công nghệ –
Đại học Quốc gia Hà Nội đã tận tình dạy bảo, truyền đạt những kiến thức quý
báu giúp tôi hoàn thành nhiệm vụ học tập trong suốt thời gian theo học tại
trường. Quý Thầy Cô đã giúp tôi có được những kiến thức nền tảng quý báu và
quan trọng trong ngành nghề mà tôi đang theo đuổi.
Tôi xin chân thành cảm ơn anh chị em đồng nghiệp đã giúp đỡ, ủng hộ
tinh thần trong thời gian tôi tham gia học tập. Cuối cùng, tôi xin gửi lời cảm ơn,
biết ơn tới những người thân yêu trong gia đình bé nhỏ của tôi. Những người đã
phụ giúp tôi rất nhiều công việc, trách nhiệm trong gia đình để tôi có thể có thời
gian, sức lực để học tập và hoàn thành luận văn.
Hà Nội, tháng 09 năm 2020
Đỗ Văn Việt
iii
MỤC LỤC
LỜI CAM ĐOAN ................................................................................................. i
LỜI CẢM ƠN......................................................................................................ii
MỤC LỤC...........................................................................................................iii
DANH SÁCH HÌNH VẼ.................................................................................... vi
LỜI NÓI ĐẦU ..................................................................................................... 1
1.1. Phân cụm là gì .............................................................................................. 3
1.2.1. Phương pháp phân hoạch ........................................................................... 4
1.2.2. Phương pháp phân cấp ............................................................................... 6
1.2.3. Phương pháp dựa trên mật độ .................................................................... 8
1.2.4. Phương pháp dựa trên lưới....................................................................... 10
2.1. Mạng nơ-ron............................................................................................... 13
2.1.1. Nơ-ron sinh học......................................................................................... 13
2.1.2. Perceptron................................................................................................. 14
2.1.3. Mạng truyền tới nhiều tầng....................................................................... 16
2.2. Huấn luyện mạng nơ-ron........................................................................... 17
2.3. Hàm kích hoạt............................................................................................. 19
2.4. Hàm mất mát .............................................................................................. 21
2.4.1. Hàm mất mát dùng cho hồi quy ................................................................ 21
2.4.2. Hàm mất mát dùng cho phân lớp.............................................................. 21
2.4.3. Hàm mất mát dùng cho tái tạo.................................................................. 22
3.1. Phân cụm dựa trên ràng buộc................................................................... 24
3.1.1. Phân loại các ràng buộc ........................................................................... 24
3.2. Phương pháp S3C2..................................................................................... 27
3.2.1. Giới thiệu sơ lược...................................................................................... 27
3.2.2 Chi tiết mô hình.......................................................................................... 28
3.3. Đánh giá mô hình ....................................................................................... 31
iv
4.1. Giới thiệu..................................................................................................... 33
4.2. Chương trình .............................................................................................. 33
4.2.1. Module dataset.......................................................................................... 33
4.2.3. Module clunet............................................................................................ 34
4.3. Dữ liệu thử nghiệm..................................................................................... 34
4.3.1. Dữ liệu hoa Iris ......................................................................................... 34
4.3.2. Dữ liệu chữ số viết tay MNIST.................................................................. 35
4.4. Thử nghiệm trên bộ dữ liệu hoa Iris ........................................................ 35
4.4.1. Kịch bản thử nghiệm ................................................................................. 35
4.4.2. Kết quả thử nghiệm ................................................................................... 37
4.4.3. Nhận xét..................................................................................................... 39
4.5.1. Kịch bản thử nghiệm ................................................................................. 39
4.5.2. Kết quả thử nghiệm ................................................................................... 41
4.5.3. Nhận xét..................................................................................................... 43
v
DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT
STT
Từ viết tắt
Từ hoặc cụm từ
Business Intelligence
1
2
3
4
5
6
7
8
9
BI
CRM
MSE
SSC
Customer Relationship Management
Mean Squared Error
Semi-Supervised Clustering
Semi-Supervised Siamese Classifiers for Clustering
Labeling Network
S3C2
LabNet
CluNet
SNN
DNNs
Clustering Network
Siamese Neural Networks
Dense Deep Neural Networks
Normalized Mutual Information
Adjusted Rand Index
10 NMI
11 ARI
12 SSGC
Semi-Supervised Graph-based Clustering
vi
DANH SÁCH HÌNH VẼ
Hình 1.1 Phân cụm k-Means................................................................................. 6
Hình 2.1 Nơ-ron sinh học.................................................................................... 13
Hình 2.2 Single-layer perceptron........................................................................ 15
Hình 2.6 Sigmoid activation function................................................................. 20
Hình 3.1 Mô hình S3C2........................................................................................ 28
Hình 3.2 Cấu trúc mạng LabNet ......................................................................... 29
Hình 3.3 Cấu trục mạng CluNet.......................................................................... 30
Hình 4.1 Hoa Iris................................................................................................. 35
Hình 4.2 Một mẫu chữ số 2 viết tay.................................................................... 35
1
LỜI NÓI ĐẦU
Thế kỉ 21, là kỉ nguyên mà nhân loại được chứng kiến sự thay đổi chóng
mặt của công nghệ thông tin. Công nghệ thay đổi đã làm thay đổi mọi mặt trong
đời sống của con người. Những sản phẩm công nghệ đã xuất hiện trên khắp mọi
miền quê, khắp mọi nẻo đường, từ nông thôn đến thành thị. Công nghệ làm thay
đổi thói quen sinh hoạt, vui chơi, giải trí của con người. Công nghệ làm thay đổi
phương thức, quy trình sản xuất của các cá nhân, tập thể. Người ta sử dụng công
nghệ cho mọi việc, ở mọi nơi, mọi lúc. Dẫn đến, một lượng dữ liệu khổng lồ
được sinh ra hàng giờ, hàng phút, thẫm chí là hàng giây.
Vì vậy mà lĩnh vực khai phá dữ liệu cũng như phát hiện tri thức ngày càng
được quan tâm nhiều hơn, và cũng đang phát triển mạnh mẽ hơn bao giờ hết.
Trong đó, phân cụm dữ liệu là một kĩ thuật quan trọng trong lĩnh vực này.
Phân cụm (Clustering) là chia các tập dữ liệu thành các cụm sao cho các
đối tượng trong cùng một cụm giống nhau hơn các đối tượng ở cụm khác. Bài
toán phân cụm dữ liệu có được ứng dụng rộng rãi và đa dạng trong nhiều lĩnh
vực, như kinh doanh thông minh (Business Intelligence: BI), nhận dạng mẫu,
tìm kiếm web, sinh học, bảo mật và mạng xã hội, … Bài toán này đã thu hút
nhiều người nghiên cứu trong 5 thập kỷ qua, cùng với sự bùng nổ dữ liệu, càng
ngày nó càng được quan tâm trong xử lý dữ liệu lớn (Big Data).
Thoạt tiên, phân cụm dữ liệu được xét dưới dạng học không giám sát, việc
phân cụm chỉ dựa vào tính tương tự của các đối tượng dữ liệu và kết quả phân
cụm khó giải thích rõ ràng. Để tăng chất lượng phân cụm, trên thực tế, người
dùng thường dùng thêm một số thông tin, tri thức nền tảng ban đầu nào đó về
các đối tượng trong tập dữ liệu, chẳng hạn các đối tượng nên/không nên cùng
một cụm. Hướng tiếp cận này được gọi là phân cụm bán giám sát. Hiện nay, các
thông tin bổ trợ thường được cho dưới dạng tập giống (Seed) và ràng buộc
(Constraint). Tập giống là tập gồm các đối tượng đã cho trước chúng thuộc cụm
nào. Các ràng buộc có thể được gắn cho trên các cặp dữ liệu, như must-link hoặc
cannot-link để cho biết chúng có thuộc cùng cụm hay không. Chúng cũng có thể
là các ràng buộc trên các cụm, như ràng buộc về số lượng, kích thước hay hình
dạng các cụm, …
Trong luận văn này, sau khi tìm hiểu hướng tiếp cận phân cụm dựa trên
các ràng buộc theo từng cặp, chúng tôi tập trung vào phương pháp phân cụm
dựa trên tri thức mới có tên là S3C2 [1], trong đó tri thức được cho dưới dạng
ràng buộc theo từng cặp. Phương pháp này sử dụng mạng nơ-ron cùng với các
thuật toán học sâu để phân cụm, cho hiệu quả cao. Chúng tôi thực hiện cài đặt
thực nghiệm để so sánh với các thuật toán khác, kết quả cho thấy được các ưu
2
điểm nổi trội của thuật toán so với các thuật toán tiên tiến đã có, chẳng hạn như
SSGC, SSDBSCAN, SSK-Means, MCSSGC [5,6]; kết quả cài đặt so sánh được
với thực nghiệm trong bài báo vừa công bố.
Ngoài phần kết luận, nội dung của luận văn bố cục như sau:
- Chương 1. Giới thiệu bài toán phân cụm dữ liệu, các khái niệm và các tiếp
cận cơ bản.
- Chương 2. Giới thiệu kiến thức về mạng nơ-ron cần dùng để đi sâu vào
tìm hiểu việc ứng dụng chúng cho bài toán phân cụm dựa trên tri thức
được trình bày ở chương 3.
- Chương 3. Trình bày phương pháp S3C2, một mô hình phân lớp sử dụng
mạng nơ-ron cho bài toán phân cụm dựa trên ràng buộc theo từng cặp.
- Chương 4. Trình bày kết quả cài đặt chương trình cho phương pháp S3C2,
và chạy thử nghiệm trên tập dữ liệu hoa Iris, MNIST; đưa ra kết quả thực
nghiệm của S3C2 đồng thời so sánh kết quả với các phương pháp khác:
SSGC, SSDBSCAN, SSK-Means, MCSSGC [5,6].
3
CHƯƠNG 1. PHÂN CỤM DỮ LIỆU
Trước khi đi sâu vào phân cụm bán giám sát dựa trên tri thức theo từng
cặp, cũng như phương pháp S3C2 [1], chương này chúng tôi sẽ trình bày sơ lược
về phân cụm dữ liệu, các phương pháp phân cụm dữ liệu.
1.1. Phân cụm là gì
Phân cụm là quá trình phân tách một tập các đối tượng dữ liệu thành các
tập con. Mỗi tập con là một cụm, sao cho các đối tượng trong cùng một cụm thì
giống nhau, nhưng không giống so với các đối tượng ở các cụm khác [2].
Phân cụm được sử dụng rộng rãi trong nhiều lĩnh vực, như BI, nhận dạng
mẫu, tìm kiếm web, sinh học và bảo mật, … Trong BI, phân cụm có thể được sử
dụng để sắp xếp một số lượng lớn các khách hàng vào các nhóm, trong đó các
khách hàng trong cùng một nhóm sẽ có sự tương tự lớn về một số đặc điểm.
Điều này tạo điều kiện cho phát triển các chiến lược kinh doanh để tăng cường
quản lý quan hệ khách hàng (Customer Relationship Management: CRM) [2].
Trong nhận dạng mẫu, phân cụm cũng được sử dụng cho nhiều bài toán
có tính ứng dụng cao, và rất thực tiễn, như nhận dạng chữ ký, nhận dạng chữ
viết tay, nhận dạng vân tay, nhận diện khuôn mặt, … Sản phẩm của phân cụm
được triển khai trong rất nhiều hệ thống, và ngày càng trở nên phổ biến. Từ các
ứng dụng của các cá nhân, tới các hệ thống lớn hơn của các doanh nghiệp, ngân
hàng, các tập đoàn đa quốc gia, thậm chí là các hệ thống chính phủ, … đều có sự
hiện diện của phân cụm. Chẳng hạn như, ngày nay nhận dạng vân tay được sử
dụng làm cơ chế xác thực cho hầu hết các thiết bị và ứng dụng.
Phân cụm cũng được ứng dụng khá nhiều trong tìm kiếm web. Ví dụ như:
một từ khóa tìm kiếm có thể cho ra một số lượng rất lớn các kết quả, do số
lượng trang web là vô cùng lớn. Phân cụm có thể được sử dụng để sắp các kết
quả đó vào các nhóm và trình bày các kết quả một cách ngắn gọn. Giúp người
dùng có trải nghiệm tốt hơn, tìm kiếm dễ dàng và hiệu quả hơn. Hơn nữa, các kỹ
thuật phân cụm cũng đã được phát triển để phân loại các tài liệu thành các chủ
đề, kết quả của nó thường được sử dụng trong truy hồi thông tin.
Trong khai phá dữ liệu, phân cụm được sử dụng như một công cụ độc lập
để hiểu rõ hơn về phân phối của dữ liệu, để quan sát các đặc điểm của từng cụm
và tập trung vào một nhóm cụ thể để phân tích thêm. Ngoài ra, nó cũng đóng vai
trò là bước tiền xử lý cho các thuật toán khác như phân lớp, trích chọn đặc
trưng, … [2].
4
Bởi vì mỗi cụm là một tập các đối tượng tương tự nhau và không tương tự
với các đối tượng thuộc lớp khác, nên mỗi cụm có thể được hiểu là một lớp ẩn.
Theo nghĩa này, phân cụm đôi khi còn được gọi là phân lớp tự động.
Trong một số ứng dụng, phân cụm còn được gọi là phân đoạn dữ liệu
(Data Segmentation), bởi nó phân chia dữ liệu thành các nhóm dựa trên độ
tương tự của chúng. Phân cụm cũng có thể được sử dụng để phát hiện ngoại lệ
(các đối tượng cách xa bất kỳ cụm nào). Ví dụ như phát hiện gian lận thẻ tín
dụng, giám sát các hoạt động tội phạm trong thương mại điện tử.
Trong học máy, phân lớp được gọi là học có giám sát (Supervised
Learning) vì thông tin nhãn lớp được sử dụng trong thuật toán học. Còn phân
cụm được gọi là học không giám sát, do không sử dụng thông tin nhãn lớp. Vì lý
do này, phân cụm là hình thức học tập dựa trên quan sát thay vì học qua các ví
dụ [2].
1.2. Một số phương pháp phân cụm dữ liệu cơ bản
Tùy theo đặc điểm về tính tương đồng của các đối tượng trong các bài
toán đang xét, có nhiều cách tiếp cận cho thuật toán phân cụm. J. Han và M.
Kamber [2] phân các thuật toán này thành 4 loại chính:
- Phương pháp phân hoạch (Partitioning methods)
- Phương pháp phân cấp (Hierarchical methods)
- Phương pháp dựa trên mật độ (Density-based methods)
- Phương pháp dựa trên lưới (Grid-based methods)
1.2.1. Phương pháp phân hoạch
Cho tập dữ liệu D gồm n đối tượng, phương pháp phân hoạch phân phối
các đối tượng thuộc D thành k cụm, C1, C2, …, Ck, sao cho Ci ∈ D và 퐶푖 ∩ 퐶 =
푗
∅ với 1 ≤ 푖, 푗 ≤ 푘. Một hàm mục tiêu được sử dụng để đánh giá chất lượng
phân cụm sao cho các đối tượng trong cùng một cụm thì tương tự nhau nhưng
khác so với các đối tượng ở các cụm khác. Ở đây, hàm mục tiêu sẽ nhắm đến
việc làm tăng cao độ tương tự nội bộ (Intracluster Similarity) và giảm thấp độ
tương tự liên kết (Intercluster Similarity).
Hầu hết các phương pháp phân hoạch đều dựa trên khoảng cách
(Distance-based). Ban đầu chúng khởi tạo một phân vùng. Sau đó, nó lặp đi lặp
lại việc di chuyển các đối tượng từ nhóm này sang nhóm khác để cố gắng cải
thiện chất lượng phân vùng.
Phân cụm phân hoạch thường rất khó để đạt được tối ưu toàn cục mà
thường thực hiện tối ưu cục bộ bằng các cách tiếp cận tham lam như thuật toán
k-Means và k-medoids. Chúng thường hoạt động tốt khi được sử dụng để tìm
5
các cụm có hình cầu (Spherical Shaped Cluster) trong cơ sở dữ liệu có kích
thước từ nhỏ đến trung bình [2].
Thuật toán k-Means [2]
K-Means là một thuật toán phân cụm phân hoạch dựa trên trọng tâm.
Chúng sử dụng trọng tâm của một cụm để đại diện cho cụm đó. Trọng tâm có
thể được định nghĩa theo nhiều cách khác nhau, chẳng hạn như giá trị trung bình
của các đối tượng trong cụm.
Giả sử ta có cụm Ci với tâm ci. Gọi dist(p, ci) là khoảng cách giữa điểm p
và tâm ci. Chất lượng của cụm Ci có thể được đo bằng tổng bình phương khoảng
cách giữa tất các các đối tượng trong cụm và tâm ci, được định nghĩa như sau:
퐸퐶 = ∑ 푑푖푠푡(푝, 푐푖)2
푖
푝 ∈퐶
푖
퐸퐶 càng nhỏ thì chất lượng của cụm càng tốt. Từ đó, chất lượng của một
푖
kết quả phân cụm hay một bộ phân hoạch có thể được tính bởi công thức sau:
푘
퐸 = ∑ ∑ 푑푖푠푡(푝, 푐푖)2
푖=1 푝 ∈퐶
푖
Tối ưu hóa E là một việc rất khó khăn. Trong trường hợp xấu nhất, chúng
ta sẽ phải liệt kê một số lượng là lũy thừa của số cụm các phân hoạch có thể có.
Bài toán là NP-hard trong không gian Euclide nói chung (chưa biết số chiều),
thẫm chí ngay cả khi số cụm k=2. Trong trường hợp, các đối tượng dữ liệu là
các vec-tơ trong không gian Euclide 2 chiều, nhưng chưa biết số cụm k, thì việc
tối ưu E cũng là NP-hard. Để khắc phục điều này, k-Means sử dụng cách tiếp
cận tham lam và thực hiện tối ưu cục bộ.
Thuật toán k-Means định nghĩa trọng tâm của cụm là giá trị trung bình
của các điểm trong cụm. Lược đồ giải thuật của thuật toán như sau:
Input:
. k: số lượng các cụm
. D: tập dữ liệu gồm n đối tượng
Output: Một tập gồm k cụm.
Phương thức:
(1) tùy chọn k đối tượng trong D làm tâm khởi tạo cho k cụm
(2) lặp cho tới khi không có sự thay đổi nào nữa
(2.1) gán (hoặc gán lại) mỗi đối tượng vào cụm mà nó gần tâm nhất
(2.2)cập nhật lại tâm các cụm, bằng cách tính giá trị trung bình của các đối
tượng trong cụm.
Hình bên dưới mô phỏng giải thuật phân cụm k-Means
6
Hình 1.1 Phân cụm k-Means
1.2.2. Phương pháp phân cấp
Phân cụm phân cấp còn được gọi là phân cụm cây, trong đó 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. Tùy theo cách xây dựng
cây phân cấp, mà phân cụm phân cấp được chia thành hai phương pháp kết tụ
(Agglomerative) hoặc phân tách (Divisive). Phương pháp kết tụ, còn được gọi là
phương pháp từ dưới lên (Bottom-up), bắt đầu với mỗi đối tượng tạo thành một
nhóm riêng biệt. Sau đó, nó liên tiếp trộn các đối tượng hoặc các nhóm gần nhau
lại, cho tới khi tất cả các nhóm được trộn thành một, hoặc đạt tới một điều kiện
kết thúc nào đó [2].
Phương pháp tách còn được gọi là phương pháp từ trên xuống (Top-
down), bắt đầu với tất cả các đối tượng trong cùng một cụm. Trong mỗi lần lặp
liên tiếp, một cụm lại được chia thành các cụm nhỏ hơn, kết thúc khi mỗi đối
tượng nằm trong một cụm hoặc đạt tới điều kiện kết thúc nào đó.
Phân cụm phân cấp có thể dựa trên khoảng cách hoặc dựa trên mật độ. Nó
có mặt hạn chế bởi thực tế một khi một bước trộn (merge) hoặc tách (split) được
thực hiện, nó không bao giờ có thể được hoàn tác và các bước tiếp theo của quá
trình sẽ được thực hiện trên các cụm vừa mới được tạo. Do đó, nếu các quyết
định trộn hoặc tách không được lựa chọn tốt sẽ dẫn đến chất lượng phân cụm
không được tốt. Song sự cứng nhắc này cũng hữu ích ở chỗ nó dẫn đến chi phí
tính toán nhỏ hơn bởi không phải lo lắng về tổ hợp của các lựa chọn khác nhau.
Dù không thể sửa các quyết định sai lầm, tuy nhiên nhiều cách thức cải thiện
chất lượng phân cụm phân cấp đã được đề xuất. Trong đó, một hướng đi đầy hứa
hẹn là tích hợp phân cụm phân cấp với các kỹ thuật phân cụm khác, được gọi là
phân cụm đa pha (Multiphase Clustering). Trong đoạn sau của tiểu mục này,
chúng tôi sẽ giới thiệu một phương pháp như vậy, đó là Chameleon.
Có một số cách để phân loại các phương pháp phân cụm phân cấp. Ví dụ,
có thể phân chúng thành các loại: [2]
- Phương pháp thuật toán (Algorithmic methods)
- Phương pháp xác suất (Probabilistic methods)
7
- Phương pháp Bayes (Bayesian methods)
Các phương pháp kết tụ, phân tách và multiphase thuộc nhóm các phương
pháp thuật toán, chúng coi các đối tượng dữ liệu là xác định và tính toán các
cụm thông qua việc xác định khoảng cách của các đối tượng. Các phương pháp
xác suất sử dụng các mô hình xác suất để mô tả các cụm và đo lường chất lượng
của các cụm bằng sự phù hợp của các mô hình.
Thuật toán Chameleon [2]
Nhiều thuật toán phân cụm như CURE, Rock, … chỉ tìm thấy các cụm
phù hợp với một số mô hình tĩnh. Mặc dù hiệu quả trong một số trường hợp,
song các thuật toán này có thể cho kết quả phân cụm với chất lượng không tốt
nếu người dùng lựa chọn các tham số mô hình tĩnh không thích hợp. Các thuật
toán dễ bị hỏng khi dữ liệu chứa các cụm có hình dạng, mật độ và kích thước đa
dạng.
Chameleon là một thuật toán phân cụm phân cấp đa pha sử dụng mô hình
động để xác định độ tương tự giữa các cặp cụm. Trong Chameleon, độ tương tự
cụm được đánh giá dựa trên hai tiêu chí:
- Mức độ kết nối của các đối tượng trong cụm
- Mức độ gần gũi của các cụm
Hai cụm được merge nếu mức độ kết nối của các đối tượng trong chúng
cao và hai cụm đó gần gũi với nhau. Do đó, Chameleon không phụ thuộc vào
một mô hình tĩnh, do người dùng cung cấp mà có thể tự động thích ứng với các
đặc điểm bên trong của các cụm được trộn. Quá trình trộn tạo điều kiện phát
hiện các cụm tự nhiên, đồng nhất và áp dụng cho tất cả các loại dữ liệu miễn là
có thể chỉ định một hàm tương tự (similarity function).
Hình bên dưới mô phỏng cách Chameleon hoạt động:
Hình 1.2 Chameleon
Ban đầu, Chameleon khởi tạo một đồ thị k-nearest-neighbor (knn graph),
ở đó mỗi nút của đồ thị biểu thị cho một đối tượng dữ liệu, và tồn tại một cạnh
giữa hai nút của đồ thị nếu một đối tượng nằm trong số k đối tượng tương tự
nhất với đối tượng kia. Các cạnh được đánh trọng số (weight) để phản ảnh mức
độ tương tự giữa các đối tượng. Chameleon sử dụng thuật toán phân hoạch đồ
thị để phân tách knn graph thành một số lượng lớn các phân vùng, sao cho nó tối
8
thiểu edge cut. Nghĩa là, một cụm C được phân chia thành các cụm con Ci và Cj
sao cho tối thiểu trọng số của các cạnh sẽ bị cắt để C được chia thành Ci và Cj,
tương đương tối thiểu mức độ kết nối của hai cụm Ci, Cj.
Sau đó, Chameleon sử dụng thuật toán phân cụm phân cấp kết tụ, lặp đi
lặp lại việc trộn các cụm con. Để xác định các cặp tương tự nhau nhất, thuật toán
tính cả mức độ kết nối và mức độ gần của các cụm. Cụ thể, để xác định sự tương
tự của cặp cụm Ci và Cj, Chameleon dựa trên hai chỉ số:
Relative interconnectivity, 푅퐼(퐶푖, 퐶 ), giữa hai cụm, Ci và Cj, được định
푗
nghĩa như sau:
|퐸퐶{퐶 ,퐶 }
|
푖
푗
푅퐼(퐶푖, 퐶 ) =
푗
1
2
(|퐸퐶퐶 | + |퐸퐶퐶 | )
푖
푗
trong đó, 퐸퐶{퐶 ,퐶 } là tổng trọng số các edge cut của cụm cha, trước khi bị phân
푖
푗
tách thành hai cụm con Ci và Cj. Tương tự, 퐸퐶퐶 (hoặc 퐸퐶퐶 ) là cự tiểu tổng
푖
푗
trọng số các edge cut nếu phân tách cụm Ci (hoặc Cj) thành hai phần.
Relative closeness, 푅퐶(퐶푖, 퐶 ), giữa hai cụm, Ci và Cj, được định nghĩa
푗
như sau:
̅
푆퐸퐶
{퐶 ,퐶 }
푖
푗
푅퐶(퐶푖, 퐶 ) =
푗
|퐶 |
| |
퐶푖
푗
̅
̅
푆퐸퐶
퐶
푗
푆퐸퐶
+
퐶
푖
| |
퐶푖 + |퐶 |
| |
퐶푖 + |퐶 |
푗
푗
̅
trong đó, 푆퐸퐶
là trung bình trọng số của các cạnh nối các nút trong cụm Ci
푗
{퐶 ,퐶 }
푖
̅
̅
và các nút trong cụm Cj, và 푆퐸퐶 (hoặc 푆퐸퐶 ) là trung bình trọng số của các
퐶
푖
퐶
푗
cạnh bị cắt nếu cụm Ci (hoặc Cj) bị phân tách làm hai phần.
Chameleon đã được chứng minh có năng lực tốt hơn trong việc khám phá
cám cụm có hình dạng tùy ý với chất lượng cao hơn so với các thuật toán điển
hình khác như BIRCH hay DBSCAN. Tuy nhiên, chi phí cho xử lý dữ liệu có số
chiều lớn có thể cần thời gian 푂(푛2) trong trường hợp xấu nhất.
1.2.3. Phương pháp dựa trên mật độ
Hầu hết các phương pháp phân hoạch dựa trên khoảng cách giữa các đối
tượng, nên thường chỉ có thể tìm thấy các cụm có hình cầu và gặp khó khăn
trong việc phát hiện các cụm có hình dạng tùy ý.
Các phương pháp phân cụm dựa trên mật độ đã được phát triển để khắc
phục các nhược điểm này. Để tìm được các cụm có hình dạng tùy ý, chúng mô
hình hóa các cụm như các vùng có mật độ dày đặc trong không gian dữ liệu,
được phân tách bởi các vùng thưa thớt. Ở đây, mật độ của một vùng được hiểu là
9
số lượng các đối tượng dữ liệu nằm trong vùng đó. Lược đồ chung của các
phương pháp phân cụm dựa trên mật độ là từ một cụm cho trước, có thể là một
điểm, chúng thực hiện mở rộng cụm đó cho tới khi mật độ trong vùng lân cận
(neighborhood) vượt quá một ngưỡng nào đó.
Không chỉ được dùng để khám phá các cụm có hình dạng tùy ý, phân cụm
dựa trên mật độ còn được sử dụng để lọc nhiễu hoặc ngoại lệ [2].
Thuật toán DBSCAN [2]
Để hiểu rõ hơn về DBSCAN, trước tiên chúng tôi sẽ trình bày các khái niệm
được sử dụng trong thuật toán này.
- Vùng lân cận của một đối tượng: Cho ɛ là một tham số do người dùng chỉ
định, ɛ-lân cận của một đối tượng o là không gian với bán kính ɛ, tâm là
o.
- Mật độ của vùng ɛ-lân cận tâm o là số lượng các đối tượng nằm trong
vùng đó, hay là số lượng các đối tượng có trong tập dữ liệu có khoảng
cách tới o nhỏ hơn hoặc bằng ɛ.
- Cho MinPts là một tham số người dùng, một vùng ɛ-lân cận tâm o được
gọi là dày đặc nếu mật độ của nó lớn hơn hoặc bằng MinPts.
- Đối tượng lõi (core object): Đối tượng o trong tập dữ liệu được gọi là đối
tượng lõi nếu ɛ-lân cận của nó là một vùng có mật độ dày đặc.
Ban đầu thuật toán tìm các đối tượng lõi, và các vùng dày đặc. Sau đó nó
thực hiện tạo các vùng dày đặc lớn hơn từ các vùng dày đặc nhỏ tập trung quanh
đối tượng lõi. Để thực hiện được điều này, DBSCAN đưa ra ba khái niệm:
- directly density-reachable, được phát biểu như sau: đối tượng p directly
density-reachable được từ q khi và chỉ khi q là đối tượng lõi và p thuộc ɛ-
lân cận của q
- density-reachable, được phát biểu như sau: đối tượng p density-reachable
được từ q nếu có một chuỗi các đối tượng p1, …, pn sao cho p1 = q, pn = p,
và pi+1 directly density-reachable được từ pi với 1 ≤ 푖 ≤ 푛
- density-connectedness, được phát biểu như sau: hai đối tượng p1, p2 ∈ D
được gọi là density-connected nếu có một đối tượng 푞 ∈ 퐷 sao cho cả p1
và p2 đều density-reachable được từ q
Tập con 퐶 ∈ 퐷 là một cụm nếu thỏa mãn hai điều kiện sau:
- với mọi o1, o2 ∈ C, thì o1 và o2 density-connected với nhau
- không tồn tại đối tượng o ∈ C và 표′ ∈ (퐷 − 퐶) sao cho o và 표′ là density-
connected
Hình dưới đây mô tả các mối quan hệ density-reachable và density-
connectivity trong phân cụm dựa trên mật độ:
10
Hình 1.3 Density-reachability và density-connectivity
Lược đồ giải thuật bên dưới sẽ giúp chúng ta hiểu một cách hoàn chỉnh về thuật
toán DBSCAN:
Input:
- Tập hợp gồm n đối tượng cần phân cụm
- ɛ: tham số bán kính
- MinPts: ngưỡng mật độ dày đặc cho các lân cận
Output: Tập các cụm
Method:
(1) đánh dấu mọi đối tượng với nhãn unvisited;
(2) thực hiện
(3) lựa chọn ngẫu nhiên một đối tượng unvisited p;
(4)
đánh dấu p là visited
(5)
nếu ɛ-lân cận của p có ít nhất MinPts đối tượng
tạo mới cụm C, và thêm p vào cụm C
gọi N là tập các đối tượng trong ɛ-lân cận của p
với mỗi đối tượng p’ trong N
(6)
(7)
(8)
(9)
nếu p' unvisited
(10)
(11)
(12)
(13)
(14)
đánh dấu p’ là visited
nếu ɛ-lân cận của p’ có ít nhất MinPts điểm
add toàn bộ các điểm thuộc ɛ-lân cận vào tập N
nếu p’ chưa thuộc bất kỳ cụm nào, thì thêm p’ vào cụm C
nhận được cụm C;
(15) ngược lại thì đánh dấu p với nhãn noise;
(16) cho tới khi không còn đối tượng nào có nhãn unvisited
1.2.4. Phương pháp dựa trên lưới
Các phương pháp dựa trên lưới định lượng không gian các đối tượng
thành một số hữu hạn các ô tạo thành cấu trúc lưới. Tất cả các hoạt động phân
cụm được thực hiện trên cấu trúc lưới đó. Ưu điểm chính của phương pháp này
là thời gian xử lý nhanh, thường không phụ thuộc vào số lượng dữ liệu và chỉ
11
phụ thuộc vào số lượng các ô của mỗi chiều trong không gian được lượng tử hóa
[2].
Sử dụng lưới thường là một cách hiệu quả cho các bài toán khai phá dữ
liệu không gian, bao gồm cả phân cụm. Do đó, các phương pháp dựa trên lưới
có thể được tích hợp với các phương pháp phân cụm khác như phương pháp dựa
trên mật độ và phương pháp phân cấp.
Thuật toán STING (STatistical INformation Grid) [2]
Không gian được chia thành các ô hình chữ nhật. Các ô có cấu trúc phân
cấp, và các cấp bậc khác nhau của các ô tương ứng với độ phân giải (resolution)
khác nhau. Các ô ở mức cao hơn, được phân hoạch thành một số ô ở mức thấp
hơn. Các thông tin thống kê của mỗi ô được tính toán và lưu trữ trước và được
sử dụng để trả lời các câu truy vấn.
Hình bên dưới, mô tả cấu trúc phân cấp trong phân cụm STING:
Hình 1.4 Hierarchical structure for STING clustering
Mỗi cell có các tham số attribute-dependent và attribute-independent. Tham số
attribute-independent là số lượng (count) các đối tượng trong một ô. Còn với
tham số attribute-dependent, ta cần giả định rằng với mỗi đối tượng, thì các đặc
trưng của nó có giá trị kiểu số. Với mỗi đặc trưng chúng ta có 5 tham số như
sau:
- mean: trung bình của tất các các giá trị trong ô đó,
- stdev: độ lệch chuẩn (standard deviation) của tất các các giá trị trong ô đó,
- min: giá trị cực tiểu của đặc trưng trong ô đó,
- max: giá trị cực đại
- kiểu phân phối mà các giá trị trong ô tuân theo, chẳng hạn như normal,
uniform, exponential hoặc none (nếu không xác định được phân phối)
Các tham số thống kê của các ô mức cao hơn có thể dễ dàng được tính từ
các tham số của các ô ở mức thấp hơn. Khi dữ liệu được load vào cơ sở dữ liệu
thì các tham số count, mean, stdev, min, max của các ô ở mức thấp nhất
(bottom-level cell) được tính trực tiếp từ dữ liệu. Còn kiểu phân phối có thể
12
được chỉ định bởi người dùng (nếu đã biết trước) hoặc thu được từ các kĩ thuật
trong thống kê. Nếu kiểu phân phối của các ô mức thấp không đồng nhất với
nhau, thì kiểu phân phối của ô cấp cao được đặt là none.
Tiếp theo chúng ta sẽ tìm hiểu việc truy vấn trên cấu trúc phân cấp để thực
hiện phân cụm. Nếu cấu trúc phân cấp không thể trả lời được truy vấn, thì có thể
sử dụng cơ sở dữ liệu ban đầu. SQL được sử dụng như là một ngôn ngữ để mô tả
các truy vấn. Có hai kiểu truy vấn phổ biến:
- truy vấn để tìm các vùng (region) thỏa mãn một số ràng buộc nào đó
- truy vấn vào một vùng nào đó, và trả về các đặc trưng của vùng đó
Ví dụ 1: Truy vấn tìm các vùng có mật độ nhà tối thiểu là 100, tối thiểu 70% số
nhà có giá lớn hơn $400k và với tổng area tối thiểu 100 đơn vị độ tin cậy
(confidence) tối thiểu là 0.9.
select
region
from house-map
where
density in (100, ∞)
and price range (40000, ∞)
with percent (0.7, 1)
and area (100, ∞)
and with confidence 0.9
Ví dụ 2: Truy vấn lấy thông tin khoảng tuổi của các nhà trong region thỏa mãn
các điều kiện: mật độ tối thiểu 100 nhà, tối thiểu 70% số nhà có giá trong
khoảng từ $150k đến $300k với area tối thiểu 100 đơn vị trong California
select
range(age)
from house-map
where
density in (100, ∞)
and price range (150000, 30000)
with percent (0.7, 1)
and area (100, ∞)
and location california
13
CHƯƠNG 2. MẠNG NƠ-RON
Để dễ dàng hơn khi tiếp cận phương pháp S3C2, một lược đồ mạng nơ-ron
nhân tạo xử lý tri thức theo từng cặp, chương này giới thiệu tóm tắt về mạng nơ-
ron nhân tạo.
2.1. Mạng nơ-ron
Mạng nơ-ron (neural network) là một mô hình tính toán có chung một số
tính chất với bộ não động vật, ở đó nhiều đơn vị hoạt động một cách song song
mà không cần một đơn vị điều khiển trung tâm. Trọng số giữa các đơn vị này là
cách thức chính để lưu trữ thông tin dài hạn trên mạng nơ-ron. Việc cập nhật các
trọng số này là cách thức chính mà mạng nơ-ron học các thông tin mới [3].
Cách hành xử của mạng nơ-ron được định hình bởi kiến trúc mạng của nó.
Kiến trúc của mạng nơ-ron được xác định (một phần) bởi các yếu tố sau:
- Số lượng nơ-ron
- Số lượng các lớp (layer)
- Kiểu kết nối giữa các lớp
2.1.1. Nơ-ron sinh học
Nơ-ron sinh học là một tế bào thần kinh cung cấp đơn vị chức năng cơ
bản cho hệ thần kinh của tất cả các loại động vật.
Hình 2.1 Nơ-ron sinh học
Các nơ-ron tồn tại để giao tiếp với nhau và truyền các xung điện hóa (electro-
chemial impulse) qua các khớp thần kinh (synapse), từ tế bào này sang tế bào
khác, miễn là các xung lực đủ mạnh để kích hoạt sự giải phóng các hóa chất
(chemical) qua một khe sinap. Độ mạnh của xung lực phải vượt qua ngưỡng tối
thiểu thì các hóa chất mới được giải phóng. Hình 2.2 trình bày các thành phần
chính của tế bào thần kinh, bao gồm:
Tải về để xem bản đầy đủ
53 trang
15880
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Phân cụm dựa trên tri thức theo từng cặp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_van_phan_cum_dua_tren_tri_thuc_theo_tung_cap.pdf
