ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN ĐỨC NGỌC
NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP
PHÂN CỤM NỬA GIÁM SÁT ỨNG DỤNG CHO BÀI TOÁN
PHÂN CỤM DỮ LIỆU WEB SERVER LOGS
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN, 2018
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN ĐỨC NGỌC
NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP
PHÂN CỤM NỬA GIÁM SÁT ỨNG DỤNG CHO BÀI
TOÁN PHÂN CỤM DỮ LIỆU WEB SERVER LOGS
Chuyên ngành: Khoa học máy tính
Mã số: 8480101
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn khoa học: TS. Vũ Việt Vũ
THÁI NGUYÊN, 2018
i
LỜI CẢM ƠN
Lời đầu tiên, tôi xin được gửi lời cảm ơn sâu sắc tới TS. Vũ Việt Vũ,
người đã trực tiếp hướng dẫn tôi thực hiện luận văn. Thầy đã tận tình hướng
dẫn, cung cấp tài liệu và định hướng cho tôi trong suốt quá trình nghiên cứu
và thực hiện luận văn.
Tôi xin chân thành cảm ơn các thầy cô đã giảng dạy và quản lý đào tạo
đã tạo điều kiện cho tôi có một môi trường học tập, nghiên cứu tốt trong suốt
2 năm theo học.
Cuối cùng tôi xin được gửi lời cảm ơn tới gia đình, bạn bè và đồng
nghiệp đã giúp đỡ và động viên tôi trong suốt quá trình học tập và hoàn thiện
luận văn.
Xin chân thành cảm ơn!
ii
MỤC LỤC
MỞ ĐẦU ........................................................................................................... 1
Chương 1. TỔNG QUAN ................................................................................. 3
1.1. Khái niệm về học máy và bài toán phân cụm dữ liệu ................................ 3
1.2. Nội dung nghiên cứu của luận văn ............................................................. 6
1.3. Một số phương pháp phân cụm dữ liệu cơ bản .......................................... 9
1.3.1. Phương pháp phân cụm K-Means ................................................... 11
1.3.2. Phương pháp phân cụm DBSCAN ................................................... 12
1.3.3. Phương pháp phân cụm dựa trên đồ thị (GC) ................................... 15
1.3.4. Ứng dụng của phân cụm dữ liệu ....................................................... 17
1.4. Kết luận .................................................................................................... 19
Chương 2. MỘT SỐ THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT CƠ
BẢN................................................................................................................. 20
2.1. Tổng quan về phân cụm nửa giám sát ...................................................... 20
2.2. Thuật toán phân cụm nửa giám sát dựa trên K-Means ............................ 22
2.2.1. Thuật toán COP-KMeans .................................................................. 22
2.2.2. Thuật toán Seed K-Means ................................................................. 24
2.3. Thuật toán phân cụm nửa giám sát dựa trên mật độ: SSDBSCAN ......... 27
2.4. Thuật toán phân cụm nửa giám sát dựa trên đồ thị (SSGC) .................... 33
2.5. Kết luận .................................................................................................... 37
Chương 3. KẾT QUẢ THỰC NGHIỆM ........................................................ 38
3.1. Giới thiệu về dữ liệu web server logs ...................................................... 38
3.1.1. Tiền xử lý dữ liệu .............................................................................. 38
3.1.2. Phương pháp đánh giá chất lượng phân cụm .................................... 42
3.1.3. Thuật toán phân cụm ......................................................................... 43
3.2. Kết quả phân cụm trên tập web server logs ............................................. 43
3.3. Kết luận .................................................................................................... 47
iii
KẾT LUẬN ..................................................................................................... 48
Những kết quả đã đạt được ................................................................. 48
Hướng phát triển tiếp theo của đề tài .................................................. 48
TÀI LIỆU THAM KHẢO ............................................................................... 49
iv
DANH MỤC CÁC BẢNG BIỂU
Bảng 1.1. Ví dụ về dữ liệu sau khi chuyển đổi thành vector ............................ 9
Bảng 3.1. Ví dụ về dữ liệu sau khi chuyển đổi về dạng vector .................... 411
v
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1. Các hướng nghiên cứu của Trí tuệ nhân tạo .................................... 3 Hình 1.2. Các lĩnh vực liên quan với học máy.................................................. 5 Hình 1.3. Các bài toán khai phá dữ liệu trên web (web mining) ..................... 7 Hình 1.4. Ví dụ về dữ liệu log server webs ....................................................... 8 Hình 1.5 Ví dụ về phân cụm dữ liệu ............................................................... 10 Hình 1.6. Minh họa thuật toán K-Means ........................................................ 10 Hình 1.7 Thuật toán K-Means ......................................................................... 11 Hình 1.8. Thuật toán DBSCAN ..................................................................... 13 Hình 1.9. Thuật toán DBSCAN: thủ tục Expandcluster ................................. 14 Hình 1.10 Ví dụ về phân cụm sử dụng thuật toán DBSCAN ......................... 15 Hình 1.11. Ví dụ về phân cụm sử dụng đồ thị ................................................ 16 Hình 2.1.Dữ liệu đầu vào cho 3 loại thuật toán học ....................................... 20 Hình 2.2. Minh họa thuật toán COP-Kmeans ................................................. 23 Hình 2.3. Kết quả so sánh của thuật toán COP-KMeans cho tập dữ liệu tic-tac-toe . 23 Hình 2.4. Kết quả so sánh của thuật toán COP-KMeans cho tập dữ liệu Soybean ........................................................................................................... 24 Hình 2.5 Thuật toán Seed K-Means ................................................................ 25 Hình 2.6. Kết quả phân cụm cho tập dữ liệu Newgroups ............................... 26 Hình 2.7. Kết quả phân cụm cho tập Yahoo ................................................... 27 Hình 2.8. Dữ liệu với 3 cluster A, B, và C. Tuy nhiên không có giá trị phù
hợp MinPts và để DBSCAN có thể phát hiện ra đúng cả ba cluster trên .... 28
Hình 2.9. Kết quả phân cụm của thuật toán SSDBSCAN trên tập dữ liệu từ UCI . 32 Hình 2.10. So sánh tốc độ thực hiện giữa thuật toán SSGC và thuật toán SSDBSCAN .................................................................................................... 36 Hình 2.11. Kết quả của thuật toán SSGC khi so sánh với các thuật toán cùng loại ................................................................................................................... 37 Hình 3.1 Ví dụ về một số dòng dữ liệu log server web .................................. 38 Hình 3.2 Địa chỉ IP truy cập của người dùng ................................................. 39 Hình 3.3 Ký hiệu chỉ mục trên website ........................................................... 40 Hình 3.4 Danh sách các seed sử dụng phân cụm ............................................ 43
1
MỞ ĐẦ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. Việc thu thập thông tin cũng như
nhu cầu lưu trữ thông tin càng ngày càng lớn. Bên cạnh đó việc tin học hoá
một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như
nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu
trữ khổng lồ. Hàng triệu Cơ sở dữ liệu đã được sử dụng trong các hoạt động
sản xuất, kinh doanh, quản lý..., trong đó có nhiều Cơ sở dữ liệu cực lớn cỡ
Gigabyte, thậm chí là Terabyte. Sự bùng nổ này đã dẫn tới một yêu cầu cấp
thiết là cần có những kĩ thuật và công cụ mới để tự động chuyển đổi lượng dữ
liệu khổng lồ kia thành các tri thức có ích. Từ đó, các kĩ thuật Khai phá dữ
liệu đã trở thành một lĩnh vực thời sự của nền Công nghệ thông tin thế giới
hiện nay. Một vấn đề được đặt ra là phải làm sao trích chọn được những thông
tin có ý nghĩa từ tập dữ liệu lớn để từ đó có thể giải quyết được các yêu cầu
của thực tế như trợ giúp ra quyết định, dự đoán,… và Khai phá dữ liệu (Data
mining) đã ra đời nhằm giải quyết các yêu cầu đó.
Khai phá dữ liệu được định nghĩa là: Quá trình trích xuất các thông tin
có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các Cơ sở dữ
liệu, kho dữ liệu… . Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn
dùng một số thuật ngữ khác có ý nghĩa tương tự như: Khai phá tri thức từ Cơ
sở dữ liệu (knowlegde mining from databases), trích lọc dữ liệu (knowlegde
extraction), phân tích dữ liệu/mẫu (data/pattern analysis), khảo cổ dữ liệu
(data archaeology), nạo vét dữ liệu (data dredging). Nhiều người coi khai phá
dữ liệu và một thuật ngữ thông dụng khác là khám phá tri thức trong Cơ sở dữ
2
liệu(Knowlegde Discovery in Databases – KDD) là như nhau. Tuy nhiên trên
thực tế, khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình Khám phá
tri thức trong Cơ sở dữ liệu. Ngay từ những ngày đầu khi xuất hiện, Data
mining đã trở thành một trong những xu hướng nghiên cứu phổ biến trong
lĩnh vực học máy tính và công nghệ tri thức. Nhiều thành tựu nghiên cứu của
Data mining đã được áp dụng trong thực tế. Data mining có nhiều hướng quan
trọng và một trong các hướng đó là phân cụm dữ liệu (Data Clustering ). Phân
cụm dữ liệu là quá trình tìm kiếm để phân ra các cụm dữ liệu, các mẫu dữ liệu
từ tập Cơ sở dữ liệu lớn. Phân cụm dữ liệu là một phương pháp học không
giám sát.
Trong những năm trở lại đây, do phương pháp phân cụm dữ liệu không
giám sát còn một số hạn chế vì vậy dựa trên học không giám sát và học có
giám sát đã ra đời 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.
3
Chương 1. TỔNG QUAN
1.1. Khái niệm về học máy và bài toán phân cụm dữ liệu
Học máy (Machine Learning) là một nhánh nghiên cứu của Trí tuệ nhân
tạo nhằm xây dựng các thuật toán thực hiện trên hệ thống máy tính có thể học
được qua các dữ liệu mẫu thống kê có sẵn. Trí tuệ nhân tạo (artificial
intelligence) gồm rất nhiều lĩnh vực nghiên cứu [1]. Hình 1.1 minh họa các
hướng nghiên cứu trong lĩnh vực trí tuệ nhân tạo. Chúng ta có thể kể đến học
máy, học sâu, nhận dạng đối tượng, các hệ thống tự động, xử lý ngôn ngữ tự
nhiên, trợ lý ảo,… Trí tuệ nhân tạo là một trong ba trụ cột của cuộc cách mạng
công nghiệp 4.0 cùng với dữ liệu lớn (Big Data) và Internet vận vật. (IoT).
Hình 1.1. Các hướng nghiên cứu của Trí tuệ nhân tạo [1]
Trên thực tế có 4 dạng học cơ bản bao gồm:
- Học có giám sát: Máy tính được học một số mẫu gồm đầu vào (Input)
và đầu ra (Output) tương ứng trước. Sau khi học xong các mẫu này, máy tính
4
quan sát một đầu vào mới và tính toán, suy diễn ra kết quả tương ứng cho đầu
vào đó. Đối với loại học này sẽ có hai pha là pha huấn luyện (training) và pha
kiểm thử (testing).
- Học không giám sát: Máy tính chỉ được xem các mẫu thu thập được
không có nhãn tương ứng, sau đó máy tính phải tự tìm cách phân loại các mẫu
này (clustering – phân cụm) hoặc tìm ra mối quan hệ giữa các mẫu
(association rule – luật kết hợp), các điểm dị thường của tập mẫu (outlier),
giảm số chiều của tập mẫu (PCA),…
- Học nửa giám sát: Một dạng lai giữa hai nhóm học trên. Trong trường
hợp này hệ thống sẽ được cung cấp một lượng nhỏ các mẫu và tùy từng mục
tiêu bài toán chúng ta phát triển các phương pháp phân lớp nửa giám sát
(semi-supervised classification) hoặc phân cụm nửa giám sát (semi-
supervised clustering).
- Học tăng cường: Máy tính đưa ra quyết định hành động (action) và
nhận kết quả phản hồi (response/reward) từ môi trường (environment). Sau đó
máy tính tìm cách chỉnh sửa cách ra quyết định hành động của mình.
Ngoài ra trong khoảng 10 năm trở lại đây nghiên cứu về học sâu hay
học đa lớp (Deep learning) đã được quan tâm rất nhiều. Học sâu bản chất là
dựa trên mạng Nơ ron nhiều lớp. Dựa vào sự phát triển rất mạnh mẽ của công
nghệ và các hệ thống tính toán đã đáp ứng được với khối lượng phép tính
khổng lồ của các hệ thống học sâu. Tuy nhiên chất lượng của học sâu đã
chứng minh là tốt hơn hẳn các phương pháp học khác cho một số bài toán như
nhận dạng đối tượng trên ảnh, xử lý ngôn ngữ tự nhiên,… Học sâu cũng được
ứng dụng cho bài toán trích chọn đặc trưng, một dạng bài toán học không
giám sát.
5
Hình 1.2. Các lĩnh vực liên quan với học máy
Hình 1.2 trình bày các lĩnh vực liên quan đến học máy, chúng ta thấy
để nghiên cứu vấn đề học máy cần có có kiến thức về lĩnh vực như xác suất,
đại số tuyến tính, tối ưu hóa, lý thuyết học thống kê,…
Học máy có ứng dụng rộng khắp các ngành khoa học/ sản xuất, đặc biệt
là đối với những ngành cần phân tích khối lượng dữ liệu khổng lồ. Một số
ứng dụng phổ biến của học máy là:
- Xử lý ngôn ngữ tự nhiên (Natural Language Processing): Xử lý văn
bản, giao tiếp người – máy, …
- Nhận dạng (Pattern Recognition): Nhận dạng tiếng nói, chữ viết tay,
vân tay, thị giác máy (Computer Vision) …
- Tìm kiếm (Search Engine)
- Chẩn đoán trong y tế: Phân tích ảnh X-quang, các hệ chuyên gia chẩn
đoán tự động.
6
- Tin sinh học: Phân loại chuỗi gene, quá trình hình thành gene/protein.
- Vật lý: Phân tích ảnh thiên văn, tác động giữa các hạt …
- Phát hiện gian lận tài chính (financial fraud): Gian lận thẻ tín dụng.
- Phân tích thị trường chứng khoán (stock market analysis)
- Chơi trò chơi: Tự động chơi cờ, hành động của các nhân vật ảo, ...
Robot là tổng hợp của rất nhiều ngành khoa học, trong đó học máy tạo
nên hệ thần kinh/ bộ não của người máy.
1.2. Nội dung nghiên cứu của luận văn
Với các khái niệm như đã trình bày, học máy là một lĩnh vực có nhiều
vấn đề cần nghiên cứu cũng như rất nhiều các ứng dụng thực tế. Trong luận
văn của mình tác giả mong muốn tìm hiểu và nghiên cứu các vấn đề sau đây:
- Nghiên cứu và tìm hiểu các thuật toán phân cụm dữ liệu cơ bản.
- Nghiên cứu và nắm bắt một số thuật toán phân cụm nửa giám sát bao
gồm thuật toán phân cụm nửa giám sát K-Means, thuật toán SSDBSCAN, và
thuật toán phân cụm nửa giám sát dựa trên đồ thị SSGC.
- Lập trình ứng dụng cho bài toán phân cụm dữ liệu web server logs –
dữ liệu ghi các truy xuất của khách hàng đến các website.
Bài toán phân cụm dữ liệu người sử dụng web có ý nghĩa rất quan trọng
trong việc xác định các nhóm người sử dụng có cùng sở thích, có cùng xu
hướng truy cập thông tin giúp cho các nhà quản lý bố trí các nội dung trên
web cho tối ưu; chẳng hạn như các trang thương mại điện tử hiện nay thì việc
phân tích dữ liệu khách hàng khi truy cập vào website là không thể bỏ qua.
7
Hình 1.3. Các bài toán khai phá dữ liệu trên web (web mining) [2]
Các bài toán khai phá dữ liệu trên web gồm khai phá nội dung web,
khai phá dữ liệu người dùng web và khai phá dữ liệu cấu trúc web (xem hình
1.3). Với các vấn đề này chúng ta có thể sử dụng các công cụ học máy như
phân cụm, phân lớp, phương pháp luật kết hợp.
Bài toán khai phá nội dung web (web content mining) nhằm mục đích
khai phá các dữ liệu từ các trang web. Dữ liệu thường là văn bản, video,…
Hiện nay số lượng website là rất lớn vấn đề đặt ra là phân loại, trích chọn
thông tin, tìm các thông tin quý là một nhu cầu rất thiết yếu.
Bài toán khai phá dữ liệu cấu trúc website (web structure mining) nhằm
mục đích tìm các mối liên hệ giữa các cấu trúc website. Các loại dữ liệu này
thường biểu diễn dưới dạng đồ thị. Và bài toán khai phá dữ liệu đồ thị là một
trong những lớp bài toán được quan tâm rất nhiều trong nghiên cứu và ứng dụng.
Bài toán khai phá dữ liệu người dùng web (web usage mining) nhằm
mục đích tìm ra các mẫu, các quy luật của người dùng từ các vết truy nhập
8
website của người sử dụng. Quá trình truy nhập website của người dùng sẽ
được ghi lại trên máy chủ và gọi là web server logs. Các thông tin cơ bản
được lưu trữ lại như địa chỉ IP, thời gian truy nhập, tên đường liên kết của
website,… Trong luận văn của mình tôi chọn nghiên cứu tìm hiểu bài toán
phân cụm cho dữ liệu người dùng website.
Cấu trúc của các dữ liệu web server logs như sau:
TT Nội dung web server logs
2006-02-01 00:08:43 1.2.3.4 - GET /classes/cs589/papers.html - 200
9221 HTTP/1.1 maya.cs.depaul.edu 1 Mozilla/4.0+(compatible;+MSIE+6.0;+Windows+NT+5.1;+SV1;+.NET
+CLR+2.0.50727) http://dataminingresources.blogspot.com/
2006-02-02 19:34:45 3.4.5.6 - GET /classes/cs480/announce.html - 200
3794 HTTP/1.1 maya.cs.depaul.edu 2 Mozilla/4.0+(compatible;+MSIE+6.0;+Windows+NT+5.1;+SV1)
http://maya.cs.depaul.edu/~classes/cs480/
2006-02-02 19:34:45 3.4.5.6 - GET/classes/cs480/header.gif - 200 6027
HTTP/1.1 maya.cs.depaul.edu 3 Mozilla/4.0+(compatible;+MSIE+6.0;+Windows+NT+5.1;+SV1)
http://maya.cs.depaul.edu/~classes/cs480/announce.html
Hình 1.4. Ví dụ về dữ liệu log server webs
Sau khi có các dữ liệu như bảng trên chúng ta phải chuyển sang dạng
các vector dạng số dựa trên các trang của website. Giả sử có 5 người sử dụng
(users) và 5 trang kí hiệu là A, B, C, D, E. Dữ liệu sau khi chuyển đổi có dạng
như bảng sau. Các số trong bảng thể hiện thời gian truy cập vào các trang
tương ứng của người sử dụng. Bài toán phân cụm sẽ thực hiện với dữ liệu trên
bảng này.
9
Bảng 1.1. Ví dụ về dữ liệu sau khi chuyển đổi thành vector
A C D E B
User 1 0 3 0 10 8
User 2 10 0 2 6 3
User 3 0 4 0 12 67
User 4 12 0 9 1 9
User 5 3 2 10 9 0
Kết quả của quá trình phân cụm sẽ là các cụm trong đó các phần tử
trong mỗi cụm sẽ cho biết nhóm khách hàng hay vào truy xuất, các nhóm chủ
đề của website hay được xem cùng nhau,... Nếu như thực hiện phân cụm với
dữ liệu này trên các website khác nhau thì các cụm sẽ cho biết nhóm người
truy cập website theo các chủ đề gì, vào các website nào,… Điều này có ý
nghĩa trong việc bố trí cấu trúc của các nội dung website cũng như biết được
mối liên hệ giữa các website mà người dùng hay truy cập.
1.3. Một số phương pháp phân cụm dữ liệu cơ bản
Bài toán phân cụm (clustering) là một dạng của phương pháp học
không giám sát (unsupervised learning) được phát biểu như sau: Cho tập X
gồm n đối tượng, hãy phân rã tập X ra thành k (k ≤ n) cụm (cluster) sao cho
các đối tượng trong cùng một cụm thì tương tự nhau và các đối tượng ở các
cụm khác nhau thì không tương tự nhau theo một tiêu chuẩn nào đó. Hình 1.5
minh họa về tập dữ liệu trong không gian hai chiều với các cụm tương ứng.
Chúng ta có thể thấy các cụm có thể có phân bố Gaussian hoặc có hình dạng
bất kỳ (hình 1.6). Mục đích của quá trình phân cụm dữ liệu giúp cho chúng ta
hiểu rõ cấu trúc phân bố của dữ liệu cũng như mối quan hệ giữa các đối tượng
trong tập dữ liệu, thậm chí có thể phát hiện các dị thường trong dữ liệu (các
phần từ không thuộc cụm nào sau khi phân cụm).
10
Hình 1.5 Ví dụ về phân cụm dữ liệu
Hình 1.6. Minh họa thuật toán K-Means
11
Các thuật toán phân cụm được nghiên cứu và giới thiệu từ những năm
50 của thế kỷ XX. Một số thuật toán phân cụm dữ liệu cơ bản gồm K-Means,
Fuzzy C-Means, thuật toán phân cụm dựa trên đồ thị, thuật toán phân cụm
dựa trên mật độ (DBCSAN), thuật toán phân cụm kiểu thứ bậc. Mỗi phương
pháp có ưu và nhược điểm riêng và sẽ phù hợp với các loại dữ liệu cho các
ứng dụng khác nhau.
1.3.1. Phương pháp phân cụm K-Means
Thuật toán phân cụm K-Means là một trong những thuật toán được giới
thiệu sớm nhất (vào những năm 50 của thế kỷ XX). Ý tưởng của phương pháp
K-Means như sau: Giả sử ta cần phân tách tập dữ liệu X gồm n phần tử thành
k cụm. Thuật toán sẽ đi tìm ngẫu nhiên k trọng tâm đầu tiên và gán các điểm
dữ liệu vào trọng tâm gần nhất với nó để hình thành các cụm ở bước đầu tiên.
Ở các bước tiếp theo thực hiện lặp lại quá trình tính lại các trọng tâm và gán
lại các điểm vào trọng tâm gần nhất. Quá trình sẽ dừng lại khi các trọng tâm
là không thay đổi được nữa.
Algorithm 1: KMeans;
Input: Tập dữ liệu X = {x1, x2,…,xn}, xi Rn, số lượng cụm k, Output: k cụm của X Khởi tạo k trọng tâm ngẫu nhiên từ tập X
Repeat Gán mỗi điểm x vào cụm h* gần nó nhất; Tính toán lại các trọng tâm: t
(t+1)
Until (Thỏa mãn điều kiện hội tụ)
Hình 1.7 Thuật toán K-Means
12
Thuật toán K-Means có độ phức tạp tính toán thấp (O(nk)) tuy nhiên
chất lượng của phân cụm lại phụ thuộc vào việc lựa chọn k trọng tâm đầu tiên
(xem hình 1.6). Một nhược điểm nửa của K-Means là chỉ tìm được các cụm
có dạng hình cầu và kích thước các cụm sẽ gần như tương tự nhau.
1.3.2. Phương pháp phân cụm DBSCAN
Ý tưởng cơ bản của thuật toán DBSCAN là sử dụng tính chất dựa trên
mật độ dữ liệu – các cụm sẽ gồm các điểm liên kết với nhau thông qua các kết
nối dựa trên mật độ của chúng [3]. Các cụm sẽ được xây dựng từ một điểm dữ
liệu bằng cách thêm vào các nhóm có mật độ vượt qua một ngưỡng nào đó.
Thuật toán DBSCAN sử dụng hai tham số là MinPts và . Trong quá trình xây
dựng các cụm, các điểm sẽ được xếp liên tiếp vào ngăn xếp nếu nó thỏa mãn
có ít nhất MinPts hàng xóm nằm trong bán kính .
DBSCAN khởi tạo điểm p tuỳ ý và lấy tất cả các điểm đến được mật độ
từ p với và MinPts. Nếu p là điểm nhân thì thủ tục trên tạo ra một cụm theo
và MinPts, Nếu p là một điểm biên, không có điểm nào đến được mật độ từ
p và DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu.
Nếu chúng ta chọn sử dụng giá trị toàn cục và MinPts, DBSCAN có
thể hoà nhập hai cụm thành một cụm nếu mật độ của hai cụm gần bằng nhau.
Giả sử khoảng cách giữa hai tập dữ liệu S1 và S2 được định nghĩa là
dist(S1,S2) = min{dist(p,q)| pS1 và qS2}. Thuật toán DBSCAN được trình
bày trong hình 1.8 và 1.9.
13
Hình 1.8. Thuật toán DBSCAN [3]
Trong đó, SetOfPoints hoặc là tập dữ liệu ban đầu hoặc là cụm được
khám phá từ bước trước, CLId (clusterId) là nhãn đánh dấu phần tử dữ liệu
nhiễu có thể thay đổi nếu chúng có thể đến được mật độ từ một điểm khác từ
CSDL, điều này chỉ xảy ra đối với các điểm biên của dữ liệu. Hàm
SetOfPoints.get(i) trả về phần tử thứ i của SetOfPoints. Thủ tục
SetOfPoints.regionQuery(point, Eps) trả về một danh sách các điểm dữ liệu
lân cận với điểm Point trong ngưỡng Eps từ tập dữ liệu SetOfPoints. Trừ một
số trường hợp ngoại lệ, kết quả của DBSCAN độc lập với thứ tự duyệt các đối
tượng dữ liệu. và MinPts là hai tham số toàn cục được xác định bằng thủ
công hoặc theo kinh nghiệm. Tham số được đưa vào là nhỏ so với kích
thước của không gian dữ liệu, thì độ phức tạp tính toán trung bình của mỗi
truy vấn là O(log n).
14
Hình 1.9. Thuật toán DBSCAN: thủ tục Expandcluster
Ưu điểm của thuật toán:
- Khám phá được các cụm có hình dáng bất kỳ.
- Có thể thay đổi quy mô, hiệu quả trong cơ sở dữ liệu lớn.
- Có khả năng xử lý được nhiễu.
15
Nhược điểm của thuật toán:
- Phải lựa chọn tham số và MinPts để tìm ra cụm chính xác. Các thiết
lập tham số như vậy thường khó xác định, đặc biệt trong thực tế, khi sự thiết
lập các tham số đầu vào khác biệt nhỏ có thể dẫn đến sự phân chia cụm rất
khác nhau. Trong nhiều trường hợp không thể lựa chọn được tham số ε và
MinPts phù hợp để tiến hành phân cụm.
Hình 1.10 Ví dụ về phân cụm sử dụng thuật toán DBSCAN
Thuật toán DBSCAN có độ phức tạp tính toán là O(n2), tuy nhiên nó lại
có khả năng tìm được các cụm có hình dạng bất kỳ và phát hiện được các
điểm dị thường (xem hình 1.10). Chính vì thế DBSCAN là một trong những
thuật toán có tính ứng dụng và thực tiễn cao, rất nhiều các biến thể của
DBSCAN đã được nghiên cứu và giới thiệu.
1.3.3. Phương pháp phân cụm dựa trên đồ thị (GC)
Lý thuyết đồ thị (graph theory) là một trong những công cụ có nhiều
ứng dụng đối với ngành Công nghệ thông tin. Thuật toán phân cụm dựa trên
đồ thị (GC) được giới thiệu năm 1973. Ý tưởng cơ bản là các điểm sẽ được
kết nối lại thành đồ thị với trọng số có thể là độ tương tự giữa các điểm. Bước
tiếp theo sẽ loại bỏ đi các cạnh có độ tương tự nhỏ hơn một giá trị nào đó,
16
khi đó đồ thị sẽ phân rã thành các thành phần liên thông. Mỗi thành phần liên
thông có thể coi như là một cụm, các thành phần liên thông có số lượng đỉnh
ít có thể coi như là các điểm dị thường.
Hình 1.11. Ví dụ về phân cụm sử dụng đồ thị
Ưu điểm của thuật toán này là có thể phát hiện ra các cụm có hình dạng
bất kỳ, tuy nhiên việc lựa chọn tham số lại là vấn đề khó khăn và sẽ phụ
thuộc vào bản chất của bài toán thực tế.
Mặc dù những thuật toán đầu tiên đưa ra giải quyết vấn đề này như K-
Means, Hierarchical Clustering hay Graph-based Clustering đã xuất hiện vào
những năm 60 của thế kỷ trước, tuy nhiên với sự bùng nổ thông tin như vũ
bão, rất nhiều nguồn dữ liệu khổng lồ xuất hiện ở các lĩnh vực khác nhau đòi
hỏi chúng ta phải có các thuật toán phân cụm dữ liệu hiệu quả để đáp ứng
được các yêu cầu đặt ra cả về tốc độ lẫn chất lượng.
Một trong những hướng nghiên cứu quan trọng trong các năm gần đây
là phát triển các phương pháp phân cụm nửa giám sát (semi-supervised
17
clustering). Các thuật toán phân cụm nửa giám sát sẽ sử dụng các thông tin có
được từ người sử dụng (side information) nhằm mục đích trợ giúp trong quá
trình phân cụm và vì vậy cải tiến đáng kể chất lượng của clustering.
Trên thực tế, có hai loại side information thường được sử dụng là các
dữ liệu đã được gán nhãn (labeled data hay còn gọi là seed) và các ràng buộc
(constraint). Các constraint bao gồm hai loại: must-link(u,v) (u, v X) biểu
thị u và v sẽ được phân vào cùng một cụm và cannot-link(u,v) biểu thị u và v
sẽ được phân về hai cụm khác nhau. Mặc dù đã có rất nhiều nghiên cứu quan
trọng được đưa ra nhưng các thuật toán semi-supervised clustering mới chỉ
dừng lại ở việc tích hợp từng loại side information riêng lẻ, hơn nữa chất
lượng của các bài toán loại này còn phụ thuộc vào việc lựa chọn số lượng và
chất lượng của các side information.
1.3.4. Ứng dụng của phân cụm dữ liệu
Phân cụm dữ liệu có thể được ứng dụng trong nhiều lĩnh vực của cuộc
sống ví dụ như:
- Thương mại: Tìm kiếm nhóm các khách hàng quan trọng có đặc trưng
tương đồng và những đặc tả từ các bản ghi mua bán trong cơ sở dữ liệu khách hàng.
- Phân cụm dữ liệu phục vụ cho biểu diễn dữ liệu gene: Phân cụm là
một trong những phân tích được sử dụng thường xuyên nhất trong biểu diễn
dữ liệu gene. Dữ liệu biểu diễn gene là một tập hợp các phép đo được lấy từ
DNA microarray là một tấm thủy tinh hoặc nhựa trên đó có gắn các đoạn
DNA thành các hàng siêu nhỏ. Một tập hợp dữ liệu biểu diễn gene có thể
được biểu diễn thành một ma trận giá trị thực.
Dữ liệu biểu diễn gene sẽ được phân cụm theo 2 cách. Cách thứ nhất là
nhóm các mẫu gene giống nhau ví dụ như gom cụm dòng của ma trận D.
18
Cách thứ 2 là nhóm các mẫu khác nhau trên các hồ sơ tương ứng, ví dụ như
gom các cột của ma trận D.
- Phân cụm dữ liệu phục vụ trong sức khỏe tâm lý: Phân cụm dữ liệu áp
dụng trong nhiều lĩnh vực sức khỏe, tâm lý, bao gồm cả việc thúc đẩy và duy
trì sức khỏe, cải thiện cho hệ thống chăm sóc sức khỏe và công tác phòng
chống bệnh tật và người khuyết tật. Trong sự phát triển của hệ thống chăm
sóc sức khỏe, phân cụm dữ liệu được sử dụng để xác định các nhóm của
người dân mà có thể được hưởng lợi từ các dịch vụ cụ thể. Trong thúc đẩy y
tế, nhóm phân tích được lựa chọn để nhằm mục tiêu vào nhóm sẽ có khả năng
mang lại lợi ích cho sức khỏe cụ thể từ các chiến dịch quảng cáo và tạo điều
kiện thuận lợi cho sự phát triển của quảng cáo. Ngoài ra, phân cụm dữ liệu
còn được sử dụng để xác định các nhóm dân cư bị rủi ro do phát triển y tế và
các điều kiện những người có nguy cơ nghèo.
- Phân cụm dữ liệu trong hoạt động nghiên cứu thị trường: Trong
nghiên cứu thị trường phân cụm dữ liệu được sử dụng để phân đoạn thị
trường và xác định mục tiêu thị trường. Trong phân đoạn thị trường, phân
cụm dữ liệu được dùng để phân chia thị trường thành những cụm mang ý
nghĩa. Chẳng hạn như chia đối tượng nam giới từ 21 – 30 tuổi và nam giới
ngoài 51 tuổi, đối tượng nam giới ngoài 51 tuổi thường không có xu hướng
mua những sản phẩm mới.
- Phân cụm dữ liệu trong hoạt động phân đoạn ảnh: Phân đoạn ảnh là
việc phân tích mức xám hay mầu của ảnh thành lát đồng nhất. Trong phân
đoạn ảnh phân cụm dữ liệu thường được dùng để phát hiện biên của đối tượng
trong ảnh.
19
1.4. Kết luận
Trong chương này, tác giả trình bày các khái niệm tổng quan về học
máy, trí tuệ nhân tạo cũng như các ứng dụng của chúng. Ba thuật toán phân
cụm cơ bản là K-Means, DBSCAN và GC cũng được giới thiệu chi tiết kèm
theo phân tích các ưu nhược điểm của chúng. Thuật toán K-Means tốc độ
nhanh nhưng chỉ phát hiện ra các cụm có kích thước hình cầu, trong khi thuật
toán DBSCAN và GC có tốc độ tính toán cao hơn nhưng lại phát hiện ra các
cụm có hình dạng bất kỳ. Trong các chương tiếp theo các phương pháp phân
cụm nửa giám sát và ứng dụng cho bài toán phân loại dữ liệu web log sẽ được
giới thiệu.
20
Chương 2.
MỘT SỐ THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT CƠ BẢN
2.1. Tổng quan về phân cụm nửa giám sát
Từ những năm 2000 trở lại đây, phương pháp phân cụm nửa giám sát
bắt đầu được phát triển mạnh mẽ. Thuật toán semi-supervised clustering tích
hợp các thông tin có được từ ban đầu như một lượng nhỏ dữ liệu được gán
nhãn (seed) hoặc một số lượng nhỏ các thông tin về các cặp dữ liệu must-link,
cannot-link: must-link(u,v) thể hiện u và v sẽ thuộc cùng một cụm trong khi
cannot-link(u,v) cho biết u và v sẽ thuộc về hai cụm khác nhau.
Hình 2.1.Dữ liệu đầu vào cho 3 loại thuật toán học [4]
(a) học có giám sát, (b,c) học nửa giám sát, và (d) học không giám sát
Phân cụm nửa giám sát là phương pháp sử dụng các thông tin bổ trợ để
hướng dẫn cho quá trình phân cụm. Các thông tin bổ trợ có thể được cho dưới
dạng tập các cặp ràng buộc hoặc một tập nhỏ một số dữ liệu được dán nhãn.
Công việc xác định những tập ràng buộc hay những tập dữ liệu được dán nhãn
được thực hiện bởi người phân cụm. Việc xác định này tuỳ thuộc vào kinh
nghiệm của người phân cụm hoặc có thể dựa vào các tiêu chuẩn khác nhau
tuỳ theo mục đích của việc phân cụm.
21
Một số thuật toán phân cụm nửa giám sát cơ bản trong thời gian gần đây:
- Thuật toán Seed K-Means, đây là thuật toán K-Means tích hợp với các dữ
liệu đã gán nhãn nhằm trợ giúp trong pha khởi tạo các trọng tâm cho các cụm.
- Thuật toán Constraint K-Means, thuật toán này sử dụng các ràng buộc
giữa các điểm vào trong quá trình phân cụm, trợ giúp quá trình tìm kiếm các cụm.
- Thuật toán MPC K-Means, thuật toán này sử dụng các ràng buộc để
huấn luyện hàm mục tiêu và trợ giúp quá trình tìm kiếm các cụm.
- Thuật toán SSDBSCAN, thuật toán này sử dụng một số điểm đã gán
nhãn sẵn cung cấp để giúp cho thuật toán tìm kiếm được các cụm có mật độ
bất kỳ.
- Thuật toán SSGC, đây là thuật toán phân cụm nửa giám sát dựa trên
đồ thị, với việc sử dụng một số điểm đã gán nhãn để trợ giúp quá trình phân
tách đồ thị thành các thành phần liên thông lớn nhất.
- Thuật toán MCSSDBS, thuật toán này cải tiến thuật toán SSDBSCAN
bằng cách tích hợp các ràng buộc và các điểm đã gán nhãn sẵn vào trong cùng
một quá trình phân cụm làm tăng chất lượng của phân cụm khi so sánh với
thuật toán SSDBSCAN.
- Thuật toán MCSSGC, một cải tiến của thuật toán SSGC, tương tự như
MCSSDBS, thuật toán này tích hợp cả hai loại ràng buộc và các điểm đã gán
nhãn vào trong cùng một thuật toán để cải tiến chất lượng phân cụm khi so
sánh với thuật toán gốc SSGC
Hiện nay có hai hướng tiếp cận phương pháp phân cụm nửa giám sát đó là:
- Huấn luyện khoảng cách giữa các điểm (metric learning): Các thông
tin như ràng buộc sẽ được dùng để huấn luyện hàm tính khoảng cách sao cho
hai điểm mà thuộc ràng buộc must-link nghĩa là sau khi huấn luyện hai điểm
22
đó sẽ gần nhau hơn, ngược lại nếu hai điểm là cannot-link sau khi huấn luyện
chúng sẽ xa nhau ra.
- Hướng tiếp cận thứ hai là dùng trực tiếp các thông tin về ràng buộc
cũng như các điểm đã gán nhãn vào trong quá trình tìm kiếm các cụm. Chẳng
hạn trong thuật toán SSDBSCAN, các điểm nhãn sẽ được dùng để ước lượng
mật độ địa phương.
Trong phần tiếp theo chúng tôi sẽ trình bày bốn thuật toán phân cụm
nửa giám sát gồm: Seed K-Means, Constraint K-Means, SSDBSCAN, SSGC
là các thuật toán điển hình của phương pháp dựa trên tìm kiếm.
2.2. Thuật toán phân cụm nửa giám sát dựa trên K-Means
2.2.1. Thuật toán COP-KMeans
Thuật toán COP-KMeans được giới thiệu năm 2001 có thể xem như là
một trong những thuật toán phân cụm nửa giám sát đầu tiên. Thuật toán này
tích hợp các ràng buộc (must-link và cannot-link) vào trong quá trình xây
dựng các cụm. Trong quá trình lặp để gán nhãn các điểm, sẽ có sự kiểm tra về
tính hợp lệ của điểm được gán vào dựa trên các ràng buộc must-link và
cannot-link.
Thuật toán COP K-Means đạt kết quả tốt khi thực hiện thử nghiệm trên
các tập dữ liệu từ UCI (xem hình 2.2 và 2.3).
23
Hình 2.2. Minh họa thuật toán COP-Kmeans [5]
Hình 2.3. Kết quả so sánh của thuật toán COP-KMeans cho tập dữ liệu tic-tac-toe[5]
24
Hình 2.4. Kết quả so sánh của thuật toán COP-KMeans cho tập dữ liệu
Soybean [5]
2.2.2. Thuật toán Seed K-Means
Thuật toán Seed K-means giới thiệu năm 2002 là thuật toán sử dụng
một số dữ liệu gán nhãn sẵn tên các cụm nhằm trợ giúp quá trình sinh các
trọng tâm đầu tiên cho các cụm của thuật toán K-Means [6].
Trong thuật toán Seed K-Means, tác giả đã sử dụng một số seed nhằm
vượt qua hạn chế của thuật toán K-Means trong vấn đề lựa chọn các trọng tâm
của các cụm – thuật toán K-Means thường có các kết quả khác nhau sau mỗi
lần thực hiện vì chúng phụ thuộc nhiều vào vấn đề lựa chọn các trọng tâm
ngẫu nhiên đầu tiên. Ý tưởng cơ bản của thuật toán Seed-KMeans là sử dụng
các seed vào ngay bước khởi tạo các trọng tâm và vì vậy thuật toán sẽ cho ra
kết quả tốt hơn chỉ sau duy nhất một lần thực hiện. Thuật toán Seed K-Means
được trình bày trong Algorithm 1.
25
Algorithm 1: Seed-KMeans;
Input:
Tập dữ liệu X = {x1, x2,…,xn}, xi Rn, số lượng cụm k,
S = {S1, S2,…Sl}, l = 1,…, k là tập các seed
Output: k cụm của X
Khởi tạo các trọng tâm cho các cụm sử dụng tập các seed
S:
Repeat
Gán mỗi điểm x vào cụm h* gần nó nhất;
Tính toán lại các trọng tâm:
t (t+1)
Until (Thỏa mãn điều kiện hội tụ)
Hình 2.5 Thuật toán Seed K-Means[6]
Bằng cách khởi tạo K cụm từ tập giống, thuật toán Seed K-Means đã
giúp cho người dùng có thể can thiệp và điều chỉnh quá trình phân cụm dữ
liệu nhằm đạt được một kết quả phân cụm theo ý muốn của mình một cách
nhanh nhất.
Thuật toán dựa trên tập giống Seed K-Means do Basu đề xuất vào năm
2002 là thuật toán điển hình hiện nay về phân cụm nửa giám sát. Các thông
tin bổ trợ đều do người dùng cung cấp. Vậy phân cụm nửa giám sát thực chất
là quá trình kết hợp giữa người và máy để làm tăng chất lượng phân cụm.
26
Thuật toán Seed K–Means sử dụng tập giống nhằm vượt qua hạn chế
của thuật toán K-Mean trong vấn đề lựa chọn các trọng tâm của các lớp. Các
tập giống sẽ được sử dụng trong quá trình khởi tạo các trọng tâm. Vì vậy,
thuật toán sẽ cho ra kết quả xác định sau duy nhất một lần thực hiện.
Trong Seed K-Means, việc chọn tâm do người dùng chỉ định có thể
được thay đổi trong quá trình thực hiện thuật toán.
Thuật toán Seed K-Means đã đạt được những kết quả tốt hơn các thuật
toán khác như COP-KMeans, và thuật toán K-Means truyền thống (xem hình
2.6 và 2.7). Hơn nữa khi sử dụng các dữ liệu gán nhãn trong quá trình khởi
tạo các cụm, thuật toán chỉ cần thực hiện duy nhất một lần.
Hình 2.6. Kết quả phân cụm cho tập dữ liệu Newgroups[6]
27
Hình 2.7. Kết quả phân cụm cho tập Yahoo[6]
2.3. Thuật toán phân cụm nửa giám sát dựa trên mật độ: SSDBSCAN
Như đã trình bày trong chương 1, thuật toán DBSCAN là thuật toán rất
hiệu quả trong việc phát hiện các cụm có hình dạng bất kỳ, chất lượng phân
cụm tốt và có nhiều người sử dụng[7]. Tuy nhiên hạn chế lớn nhất của thuật
toán DBSCAN là khả năng làm việc với các tập dữ liệu có các mật độ khác
nhau giữa các cụm. Hình 2.8 chỉ ra sự hạn chế của thuật toán này, với 3 cụm
có mật độ khác nhau như vậy, không có bất kỳ cặp giá trị MinPts và nào để
DBSCAN có thể tìm ra 3 cụm này.
Thuật toán SSDBSCAN được giới thiệu năm 2009 là một semi-
supervised DBSCAN nhằm cải tiến DBSCAN để có thể làm việc với các tập
dự liệu có các cụm với mật độ khác nhau.
28
Hình 2.8. Dữ liệu với 3 cluster A, B, và C. Tuy nhiên không có giá trị phù
hợp MinPts và để DBSCAN có thể phát hiện ra đúng cả ba cluster trên [7]
Bằng cách sử dụng một số điểm gán nhãn sẵn đại diện cho các cụm, với
giả thiết cung cấp ít nhất mỗi cụm một điểm, SSDBSCAN cần duy nhất một
tham số MinPts. Dữ liệu đầu vào sẽ được biểu diễn bởi một đồ thị vô hướng
có trọng số trong đó mỗi đỉnh tương ứng cho một điểm dữ liệu, cạnh giữa hai
đỉnh p và q của đồ thị được xác định bởi giá trị rDist() như sau: rDist() biểu
thị cho giá trị nhỏ nhất của sao cho với hai đỉnh p và q thì p và q sẽ có ít
nhất MinPts điểm nằm trong siêu cầu bán kính , hơn nữa p và q có thể kết
nối trực tiếp được với nhau – tức là p nằm trong siêu cầu bán kính của q và
ngược lại, rDist() được biểu diễn như sau:
p, q X:
rDist(p,q) = max(cDist(p),cDist(q) d(p,q)) (1)
trong đó d(p,q) là khoảng cách giữa p và q theo độ đo Ơcơlit, và
cDist(o) là khoảng cách nhỏ nhất tính từ o mà ở đó o vẫn chứa đủ MinPts
điểm dữ liệu.
29
Sử dụng rDist(), chúng ta xây dựng lần lượt từng cụm C như sau: Sử
dụng một seed đầu tiên p, tiếp đó cluster C sẽ được thêm các điểm thỏa mãn
rDist(), quá trình sẽ tiếp tục đến khi gặp một điểm q có nhãn khác với nhãn
của p. Khi đó thuật toán sẽ tiến hành tìm kiếm ngược lại đến điểm o sao cho
giá trị rDist(o) là lớn nhất. Quá trình xây dựng cluster C hoàn thành. Nếu vẫn
còn các seed chưa được xét chúng ta lại tiếp tục tiến hành xây dựng các cụm
như trên.
Thuật toán SSDBSCAN được trình bày như sau:
) and ( ) then
do ) and ( ) then
list.insert(q) if ( WRITE-OBJECTS(p,list) break end if for all if ( end if end for end while
Thuật toán 1: SSDBSCAN(D, DL) Input: Data set D, a set of seeds DL Output: A partition of D Process: 1: for all 2: for all 3: 4: 5: 6: while 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: end for 20: end for
30
Thuật toán 2: WRITE-OBJECTS(p,list)
Process:
1:
2: for o=1 to i-1
3: list[o].label = p.label
4: write(list[o])
5: list.clean()
Thuật toán bắt đầu xây dựng một MST theo thuật toán Prim từ một
đỉnh bất kỳ và quá trình dừng lại khi hoặc là tất cả các đối tượng được
thêm vào MST hoặc khi một đối tượng với một nhãn khác với nhãn của p
được thêm vào cây. Khi một đối tượng q với một nhãn khác được thêm vào
cây thì thuật toán sẽ tìm kiếm cạnh lớn nhất hiện tại kết nối p và q trong tập
hợp các điểm đã được thêm vào trước q đến cụm MST hiện tại. Trong dòng 8
của thuật toán chúng ta giữ một danh sách của tất cả các đối tượng đã được
thêm vào MST, chúng được sắp xếp theo thứ tự. Danh sách này được đưa vào
WRITE-OBJECTS theo nguyên mẫu cùng với thư mục gốc của MST (danh
sách và p tương ứng). Hai đối tượng với nhãn khác nhau đã được thêm vào và
đối tượng được thêm vào với cạnh của giá trị rDist cao nhất là giá trị nhỏ
nhất mà hai đối tượng kết nối. Trong thủ tục WRITE-OBJECTS, chỉ mục (ký
hiệu bởi i) của đối tượng trong danh sách có trật tự sẽ được trả về (đối tượng
được biểu thị bởi x), và tất cả các đối tượng từ đầu danh sách đến x, trừ x,
được ghi vào một tệp tin đầu ra, gán cùng nhãn với đối tượng gốc p. Sau khi
ghi các đối tượng vào một tệp, các cấu trúc dữ liệu được khởi tạo lại và toàn
bộ quá trình được lặp lại cho một đối tượng khác trong . Cuối cùng, tất cả
các đối tượng thuộc một cụm được ghi vào một tệp tin đầu ra, trong khi các
31
đối tượng chưa được phân cụm bị bỏ lại. SSDBSCAN có thể được xem như là
một thủ tục gọi các thuật toán của Prim một số lần bằng với số lượng các đối
tượng được dán nhãn. Khi tập dữ liệu có nhãn là hữu hạn, thuật toán cuối
cùng sẽ dừng.
SSDBSCAN gọi thuật toán của Prim một số lần bằng với số đối tượng
trong bộ dữ liệu được dán nhãn. Độ phức tạp của thuật toán Prim là O(E lgV),
trong trường hợp của chúng ta tương ứng với O(N2lgN), đối với SSDBSCAN,
độ phức tạp thời gian cuối cùng là O(nN2 lg N), trong đó n là số nhãn các đối
tượng trong bộ dữ liệu có dán nhãn. Độ phức tạp thời gian này có thể được cải
thiện bằng cách thay đổi việc thực hiện thuật toán của Prim. Nếu chúng ta sử
dụng Fibonaci để thực hiện hàng đợi ưu tiên, thời gian chạy của chúng ta
được cải thiện thành O(nN2 + nN lg N), tức là O (nN2). Trong thực tế chúng ta
thấy n có giá trị nhỏ.
Thuật toán SSDBSCAN có 4 đặc tính thú vị như sau:
- Thuật toán chỉ yêu cầu một tham số dữ liệu đầu vào duy nhất.
- Không cần bất kỳ sự can thiệp nào của người dùng.
- Tự động tìm ra các đối tượng là nhiễu dựa theo mật độ.
- Có thể tự động tìm ra cấu trúc của các cụm ngay cả khi mật độ trong
các cụm khác nhau.
Bằng việc sử dụng một số seed (để gán nhãn dữ liệu), với giả thiết cung
cấp ít nhất cho mỗi cụm một seed, thuật toán phân cụm nửa giám sát dựa trên
mật độ SSDBSCAN cần duy nhất một tham số MinPts để tiến hành phân
cụm. Từ đó, thuật toán cho hiệu suất tốt hơn, khắc phục được các hạn chế của
thuật toán DBSCAN đặc biệt là trong các trường hợp phân cụm trong các tập
dữ liệu có mật độ khác nhau giữa các cụm.
32
Hình 2.9. Kết quả phân cụm của thuật toán SSDBSCAN trên tập dữ liệu từ UCI[7]
33
2.4. Thuật toán phân cụm nửa giám sát dựa trên đồ thị (SSGC)
Thuật toán phân cụm nửa giám sát dựa trên đồ thị (SSGC) được giới
thiệu năm 2017[8]. Với việc tích hợp các seed vào đồ thị, kết quả phân cụm
đạt được tốt hơn khi so sánh với phương pháp SSDBSCAN. Ý tưởng cơ bản
của phương pháp SSGC như sau:
Bước 1: Xây dựng đồ thị k-láng giềng gần nhất.
Bước 2: Phân rã đồ thị thành các thành phần liên thông sao cho trong
mỗi thành phần liên thông chỉ có nhiều nhất một loại seed.
Bước 3: Gán nhãn cho các điểm trong các thành phần liên thông có
các seed bằng nhãn của chính seed đó.
Bước 4: Các thành phần chưa có nhãn (hoặc các điểm đơn) tiếp tục
được gán vào các cụm cơ bản.
Thuật toán SSGC chỉ sử dụng một tham số - k láng giềng gần nhất.
Hơn nữa, các thí nghiệm cho thấy, bằng cách sử dụng các seed, SSGC không
chỉ cho kết quả tốt mà còn cải thiện tốc độ tính toán so với thuật toán
SSDBSCAN.
Đầu tiên, chúng ta xác định đồ thị k-NNG được định nghĩa là một đồ
thị vô hướng có trọng số, trong đó mỗi đỉnh đại diện cho một điểm của tập dữ
liệu và sở hữu tối đa k cạnh là k láng giềng gần nhất của nó. Một cạnh được
tạo ra giữa một cặp điểm và khi và chỉ khi hai điểm có chung k láng
giềng gần nhất. Trọng số của cạnh nối 2 điểm và được định
nghĩa là số láng giềng gần nhất của cả 2 điểm, được mô tả như sau:
34
Trong đó biểu thị tập hợp k láng giềng gần nhất của điểm xác
định. Tính chất này được tích hợp tính toán tự động, giúp thích nghi với việc
xử lý tập dữ liệu với mật độ cụm khác nhau.
Dựa trên đồ thị k-NNG được định nghĩa ở trên, thuật toán phân cụm
nửa giám sát dựa trên đồ thị được phát triển, gọi tắt là SSGC. Thuật toán được
mô tả như sau:
Bước 1: Phân chia đồ thị k-NN. Mục đích của bước này là phân chia một
đồ thị thành một số thành phần liên thông được kết nối theo điều kiện cắt sau:
- Điều kiện cắt: “Mỗi thành phần liên thông có nhiều nhất một loại seed”.
Để làm được điều này, một ngưỡng được thiết lập để phân chia đồ
thị k-NN thành các thành phần liên thông. Để tối đa hóa số điểm trong các
thành phần liên thông, chúng ta chọn giá trị ban đầu càng nhỏ càng tốt:
được khởi tạo là 0 và sau mỗi lần lặp, khi điều kiện không thỏa mãn thì
được tăng thêm 1.
Sau khi tìm ra các thành phần liên thông, tất cả các điểm của mỗi thành
phần có nhiều nhất một seed sẽ được nhân giống bởi các nhãn của seed. Bước
này tạo ra các nhóm chính.
Bước 2: Phát hiện nhiễu và xây dựng các cụm cuối.
Các điểm còn lại, không được gán nhãn sẽ được chia thành 2 loại: Các
điểm có các cạnh liên kết đến một hoặc nhiều cụm và các điểm cô lập.
- Đối với các điểm có các cạnh liên kết đến một hoặc nhiều cụm, điểm
sẽ được gán cho nhóm chính với trọng số lớn nhất có liên quan. Quá trình này
giống như cơ chế mở rộng “Cây phân nhánh tối thiểu MST” trong thuật toán
SSDBSCAN.
35
- Đối với các điểm cô lập, có 2 lựa chọn tùy theo mục đích của quá
trình phân cụm: Loại bỏ những điểm đó như là nhiễu hoặc gán nhãn. Trong
trường hợp gán nhãn, nhãn của điểm cô lập sẽ được gán nhãn bởi phần lớn
các nhãn của k láng giềng gần nhất.
Do ngưỡng được tính toán tự động ở mỗi lần lặp. Do đó thuật toán
SSGC có duy nhất một tham số k, là số điểm lân cận của đồ thị.
Thuật toán 3: SSGC
Input: Tập dữ liệu X, số lân cận k, một tập các seed S.
Output: Phân cụm tập X.
Quá trình:
1: Xây dựng biểu đồ k-NN của X
2:
3: repeat
4: Xây dựng thành phần liên thông kết nối với ngưỡng
5:
6: until điều kiện cắt được thỏa mãn.
7: Lan truyền nhãn để hình thành các cụm chính.
8: Xây dựng các cụm cuối cùng.
Độ phức tạp của gian đoạn xây dựng đồ thị k-NN là O(n2) hoặc
O(nlogn). Độ phức tạp của quá trình xây dựng các thành phần kết nối là O(nk)
trong đó k là số lân cận của đồ thị k-NN, sử dụng phương pháp tìm kiếm theo
chiều rộng (BFS) hoặc tìm kiếm theo chiều sâu (DFS). Vì vậy, độ phức tạp
của thuật toán SSGC là O(n2) hoặc O(nlogn).
36
Để đánh giá hiệu quả của thuật toán SSGC, người ta sử dụng kết quả
thu được từ thuật toán phân cụm K-Means làm tham chiếu cơ sở. Sau đó so
sánh thời gian tính toán giữa thuật toán SSGC và thuật toán SSDBSCAN vì
hai thuật toán này hoạt động cùng mục đích phân cụm (phân cụm với kích
thước và hình dạng khác nhau). Các kết quả thực nghiệm đã chứng minh thuật
toán SSGC nhanh hơn thuật toán SSDBSCAN khoảng 20 lần.
Hình 2.10. So sánh tốc độ thực hiện giữa thuật toán SSGC và thuật toán
SSDBSCAN[8]
Bằng các sử dụng k láng giềng gần nhất để xác định khoảng cách tương
đối giữa các đối tượng, thuật toán đã giải quyết được quá trình phân cụm với
hình dạng tùy ý và mật độ khác nhau. Hơn nữa, thời gian tính toán thấp hơn
đáng kể so với thuật toán SSDBSCAN.
37
Hình 2.11. Kết quả của thuật toán SSGC khi so sánh với các thuật toán
cùng loại[8]
2.5. Kết luận
Nội dung chương 2 nhằm mục đích nghiên cứu các thuật toán phân
cụm nửa giám sát cơ bản bao gồm thuật toán phân cụm nửa giám sát K-
Means, thuật toán SSDBSCAN và thuật toán SSGC. Đây là nghiên cứu tiền
đề cho chương 3 để tiến hành thực nghiệm cài đặt phân cụm cho bài toán
phân loại dữ liệu log web.
38
Chương 3. KẾT QUẢ THỰC NGHIỆM
3.1. Giới thiệu về dữ liệu web server logs
3.1.1. Tiền xử lý dữ liệu
Dữ liệu server logs được lưu trữ tại máy chủ, các dữ liệu này lưu các
vết truy xuất của người dùng khi truy cập vào website. Hình 3.1 minh họa một
vài dòng dữ liệu log server lấy từ tập dữ liệu chúng tôi sử dụng cho website
cụ thể (https://www.vnu.edu.vn).
4-03 04:02:34 W3SVC1 112.137.142.4 GET /home/Default.asp C1886/N971/Cac-luan-an-Nganh-Tieng-Anh.htm 443 - 14.239.244.221 Mozilla/5.0+(Windows+NT+10.0;+Win64;+x64)+AppleWebKit/537.36+( KHTML,+like+Gecko)+Chrome/65.0.3325.181+Safari/537.36 200 0 0
2018-04-03 04:02:57 W3SVC1 112.137.142.4 GET /ttsk/Default.asp C1654/N19949/Thu-tuong-Nguyen-Xuan-Phuc-tuyen-duong-hoc-sinh- gioi.htm 80 - 40.77.167.2 Mozilla/5.0+(compatible;+bingbot/2.0;++http://www.bing.com/bingbot.ht m) 200 0 0
2018-04-03 04:04:28 W3SVC1 112.137.142.4 GET /ttsk/Default.asp C1654/N19586/VNU-%E2%80%93-IS:-dao-tao-nguon-nhan-luc-dam- bao-chat-luong-quoc-te.htm 80 - 180.76.15.157 Mozilla/5.0+(compatible;+Baiduspider/2.0;++http://www.baidu.com/search/s pider.html) 200 0 0
2018-04-03 04:03:27 W3SVC1 112.137.142.4 GET /ttsk/Default.asp C2095/N10239/Huong-dan-dich-quoc-hieu,-chuc-danh,-don-vi,-to-chuc...- sang-tieng-Anh.htm 443 - 171.253.181.118 Mozilla/5.0+(iPhone;+CPU+iPhone+OS+11_2_6+like+Mac+OS+X)+App leWebKit/604.5.6+(KHTML,+like+Gecko)+Version/11.0+Mobile/15D10 0+Safari/604.1 200 0 0
Hình 3.1 Ví dụ về một số dòng dữ liệu log server web
39
Để thực hiện được bài toán phân cụm chúng ta phải có quá trình tiền xử
lý dữ liệu, chuyển đổi các dữ liệu trên về dạng vector. Trên thực tế có một số
phương pháp để thực hiện. Trong luận văn của mình tôi chọn phương pháp
thống kê các trang web theo lĩnh vực và xem xét các địa chỉ IP truy cập vào
các trang đó, nếu có thì giá trị sẽ đặt là 1 và không thì giá trị của vector sẽ là 0.
Sau khi trích dẫn các thông tin cần thiết như: Địa chỉ IP người dùng, các
ký hiệu chỉ mục từ logs file truy cập vào website https://www.vnu.edu.vn ngày
03 tháng 4 năm 2018, tôi thu được 4745 địa chỉ IP khá nhau của người dùng và
255 các ký hiệu chỉ mục trên website, kết quả cụ thể như sau:
207.46.13.102 207.46.13.102 207.46.13.102 207.46.13.102
171.255.28.192 171.255.28.192 171.255.28.192 171.255.28.192
207.46.13.170 207.46.13.170 207.46.13.170 207.46.13.170
138.201.68.80 138.201.68.80 138.201.68.80 138.201.68.80
66.249.71.64 66.249.71.64 66.249.71.64 66.249.71.64
216.244.66.201 216.244.66.201 216.244.66.201 216.244.66.201
5.45.207.79 5.45.207.79 5.45.207.79 5.45.207.79
125.209.235.167 125.209.235.167 125.209.235.167 125.209.235.167
40.77.167.2 40.77.167.2 40.77.167.2 40.77.167.2
54.36.148.190 54.36.148.190 54.36.148.190 54.36.148.190
66.249.71.92 66.249.71.92 66.249.71.92 66.249.71.92
54.36.148.129 54.36.148.129 54.36.148.129 54.36.148.129
66.249.71.139 66.249.71.139 66.249.71.139 66.249.71.139
144.76.71.83 144.76.71.83 144.76.71.83 144.76.71.83
..... ..... ..... .....
14.226.232.251 14.226.232.251 14.226.232.251 14.226.232.251
Hình 3.2 Địa chỉ IP truy cập của người dùng
40
C1654 C1654 C1654 C1654
C2107 C2107 C2107 C2107
C1645 C1645 C1645 C1645
C1990 C1990 C1990 C1990
C2091 C2091 C2091 C2091
C2249 C2249 C2249 C2249
C2099 C2099 C2099 C2099
C2096 C2096 C2096 C2096
C1635 C1635 C1635 C1635
C1657 C1657 C1657 C1657
C2090 C2090 C2090 C2090
C1667 C1667 C1667 C1667
C2095 C2095 C2095 C2095
C2160 C2160 C2160 C2160
...... ...... ..... ......
C2097 C2097 C2097 C2097
Hình 3.3 Ký hiệu chỉ mục trên website
Thực tế cho thấy, với website cụ thể của một trường Đại học chúng tôi
có các chuyên mục chính như sau:
- Tin tức sự kiện
- Đào tạo
- Giới thiệu
- Khoa học công nghệ
- Hợp tác phát triển
- Tiêu điểm
41
- Sinh viên
- Con người và thành tựu
- Chính trị xã hội
- Bản tin Đại học
- Đảm bảo chất lượng
- Liên hệ
- Cán bộ
- Tuyển sinh
- Nghiên cứu mới
- …
Tất nhiên còn nhiều chuyên mục khác và với mỗi một chuyên mục lại
còn có nhiều chuyên mục con khác nữa.
Bằng thực nghiệm, tôi có thể dễ dàng nhận ra mỗi một chuyên mục có
thể có một hoặc nhiều ký hiệu chỉ mục khác nhau. Sử dụng phương pháp
thống kê, tôi đã thu gọn 255 ký hiệu chỉ mục thành 24 chuyên mục để quá
trình phân cụm được dễ dàng hơn. Sau đó, dữ liệu sẽ được chuyển đổi về
dạng vector như bảng 3.2. Nói cách khác, dữ liệu dùng thực nghiệm trong
luận văn có 4745 dòng và 24 chiều tương ứng với các chuyên mục của
website.
Bảng 3.1. Ví dụ về dữ liệu sau khi chuyển đổi về dạng vector
1 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0
1 1 1 1 0 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0
1 1 1 1 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0
1 1 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0
42
1 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Mỗi người dùng có thể vào xem một số trang chủ đề cụ thể. Sau khi sử
dụng dữ liệu dạng trên để phân cụm, chúng ta sẽ được nhóm các người dùng
có cùng chủ đề và số lượng người trong từng nhóm. Điều này sẽ giúp cho việc
bố trí trang web được tốt hơn.
3.1.2. Phương pháp đánh giá chất lượng phân cụm
Đối với việc đánh giá kết quả của quá trình phân cụm chúng tôi sử
dụng chỉ số Rand Index. Chỉ số Rand Index dùng để so sánh kết quả giữa hai
phân cụm P1 và P2 có n điểm dữ liệu. Giả sử a là tổng số cặp xi và xj thuộc
cùng một cụm trong cả P1 và P2, b là tổng số cặp xi và xj thuộc hai cụm khác
nhau trong cả P1 và P2, chỉ số RI được tính bằng công thức sau:
RI sẽ có giá trị từ 0 đến 1, RI càng lớn thì độ chính xác của quá trình
phân cụm càng lớn. Chúng tôi cũng lưu ý rằng để thực hiện được việc tính
toán chỉ số RI thì chúng ta phải biết nhãn thực của tập dữ liệu.
43
3.1.3. Thuật toán phân cụm
Như đã trình bày ở chương 2, chúng ta có thể sử dụng các thuật toán
phân cụm như Seed K-Means, SSDBSCAN và SSGC. Trong thực nghiệm này
chúng tôi sử dụng thuật toán Seed K-Means cho tập dữ liệu web server logs.
Chúng tôi sẽ chia ma trận vector trên thành 6 cụm có kích thước khác nhau và
chọn ra 6 seed thỏa mãn điều kiện mỗi cụm có ít nhất một seed.
2111 1260 2174
1402 1001 3032
Hình 3.4 Danh sách các seed sử dụng phân cụm
3.2. Kết quả phân cụm trên tập web server logs
Để thực hiện phân cụm với thuật toán Seed K-Means chúng ta cần
chọn số lượng cụm cần phân tách và một số điểm lấy làm trọng tâm ở bước
khởi động cho thuật toán K-Means.
Chẳng hạn với bộ dữ liệu trên chúng ta phân tách thành 6 cụm, kết quả
sẽ như sau:
Cum 1
1 1 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 0
1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 0 0
…
44
Cum 2
1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
…
Cum 3
0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
…
Cum 4
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
…
Cum 5
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
45
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
…
Cum 6
1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0
1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0
…
Với kết quả như trên chúng ta sẽ thu được kết quả từ chương trình
như sau:
Đối với cụm 1:
- Ty le xuat hien thuoc tinh 1 trong cum 1 la: 89.85 %.
- Ty le xuat hien thuoc tinh 2 trong cum 1 la: 1.21 %.
- Ty le xuat hien thuoc tinh 3 trong cum 1 la: 8.89 %.
- Ty le xuat hien thuoc tinh 4 trong cum 1 la: 0 %.
- Ty le xuat hien thuoc tinh 5 trong cum 1 la: 1.28 %.
- Ty le xuat hien thuoc tinh 6 trong cum 1 la: 0.5 %.
- Ty le xuat hien thuoc tinh 7 trong cum 1 la: 0.26 %.
- Ty le xuat hien thuoc tinh 8 trong cum 1 la: 0.76 %.
- Ty le xuat hien thuoc tinh 9 trong cum 1 la: 0.68 %.
46
- Ty le xuat hien thuoc tinh 10 trong cum 1 la: 0.55 %.
- Ty le xuat hien thuoc tinh 11 trong cum 1 la: 0.6 %.
- Ty le xuat hien thuoc tinh 12 trong cum 1 la: 0.13 %.
- Ty le xuat hien thuoc tinh 13 trong cum 1 la: 0.34 %.
- Ty le xuat hien thuoc tinh 14 trong cum 1 la: 0.05 %.
…
Đối với cụm 2:
- Ty le xuat hien thuoc tinh 1 trong cum 2 la: 100 %.
- Ty le xuat hien thuoc tinh 2 trong cum 2 la: 7.43 %.
- Ty le xuat hien thuoc tinh 3 trong cum 2 la: 12.84 %.
- Ty le xuat hien thuoc tinh 4 trong cum 2 la: 100 %.
- Ty le xuat hien thuoc tinh 5 trong cum 2 la: 7.09 %.
- Ty le xuat hien thuoc tinh 6 trong cum 2 la: 2.7 %.
- Ty le xuat hien thuoc tinh 7 trong cum 2 la: 0.68 %.
- Ty le xuat hien thuoc tinh 8 trong cum 2 la: 2.03 %.
- Ty le xuat hien thuoc tinh 9 trong cum 2 la: 2.03 %.
- Ty le xuat hien thuoc tinh 10 trong cum 2 la: 3.04 %.
- Ty le xuat hien thuoc tinh 11 trong cum 2 la: 3.38 %.
- …
- Tỷ lệ các chủ đề so với tổng sổ lượng các phần tử trong mỗi cụm
- Phân bố các thuộc tính nhiều người truy cập, ít người truy cập
- Số lượng các truy cập vào nhiều trang khác nhau.
47
- Mối liên hệ giữa các chủ để cho từng nhóm người truy cập chẳng hạn
trong cụm 3 phần lớn các chủ để được truy cập sẽ là chủ đề thứ 4, 18, và 23;
trong cụm 6 sẽ là các chủ đề số 1, số 5 và số 17.
3.3. Kết luận
Trong chương này chúng tôi đã thực hiện việc phân cụm cho bài toán
khai phá dữ liệu trên web. Thuật toán được thử nghiệm là Seed KMeans,
tương tự cho các thuật toán SSDBSCAN hay SSGC. Các kết quả thực hiện
cho thấy nhiều điểm có thể khai thác được thông tin từ quá trình phân cụm
chẳng hạn số lượng các chủ đề cho mỗi cụm, số lượng các truy nhập cho mỗi
cụm, mối quan hệ giữa các chủ đề trong từng cụm. Một hướng nghiên cứu
tiếp theo nữa là làm sao hiển thị các sơ đồ biểu thị mối quan hệ giữa các chủ
đề cũng như mối quan hệ giữa các nhòm người có cùng sở thích truy cập
website cũng là một câu hỏi thú vị.
48
KẾT LUẬN
Những kết quả đã đạt được
Sau khi thực hiện luận văn với chủ đề nghiên cứu về bài toán khai phá
dữ liệu web server log bằng phương pháp học máy tôi đã thu được các kết quả
sau đây:
- Nắm được quy trình giải bài toán trong lĩnh vực khai phá dữ liệu và
phát hiện tri thức đặc biệt là bài toán khai phá dữ liệu web đối với tập dữ liệu
ghi vết người dùng.
- Đã nghiên cứu và nắm bắt các thuật toán cơ bản về phân cụm cũng
như phân cụm nửa giám sát. Các thuật toán K-Means, DBSCAN, GC, Seed
K-Means, SSDBSCAN, SSGC đã được trình bày trong luận văn. Đã hiểu
được bản chất của quá trình phân cụm, các khó khăn thách thức đối với bài
toán phân cụm và các nghiên cứu về phân cụm nửa giám sát trong thời gian
gần đây.
- Đã thực hiện thử nghiệm một số kết quả sử dụng phương pháp học có
nửa giám sát cho bài toán phân cụm dữ liệu log server web. Cụ thể đã hiểu
quy trình chuyển dữ liệu về dạng vector từ các vết truy cập người dùng được
ghi trên server.
Hướng phát triển tiếp theo của đề tài
Do thời gian và kiến thức còn hạn chế, trong khuôn khổ của luận văn
tôi không thể nghiên cứu kỹ và toàn diện bài toán phân cụm cũng như vấn đề
khai phá dữ liệu web. Trong tương lai, một số hướng nghiên cứu mà tôi dự
kiến tiếp tục như sau:
- Tiếp tục nghiên cứu và tìm hiểu về lĩnh vực khai phá dữ liệu, đặc biệt
là khai phá dữ liệu web.
- Nghiên cứu triển khai hệ thống khai phá dữ liệu web vào thực tế, cho
các website ở các lĩnh vực khác.
49
TÀI LIỆU THAM KHẢO
[1]. Frost, Sullivan: Artificial Intelligence- R&D and Applications. Road
Map (Dec 2016).
[2]. https://en.wikipedia.org/wiki/Web_mining [Truy cập tháng 5/2018]
[3]. Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu: A Density-
Based Algorithm for Discovering Clusters in Large Spatial Databases
with Noise. In proceeding of SIGKDD Conference on Knowledge
Discovery and Data Mining, pp: 226-231, 1996.
[4]. https://www.lip6.fr/actualite/personnes-fiche.php?ident=D819&LANG=vi
[5]. http://www.cs.cmu.edu/~./dgovinda/pdf/icml-2001.pdf [Truy cập tháng
5/2018]
[6]. Sugato Basu, Arindam Banerjee, Raymond J. Mooney, Semi-supervised
Clustering by Seeding. In proceeding of International Conference on
Machine Learning, 2002.
[7]. Levi Lelis, Jörg Sander: Semi-supervised Density-Based Clustering. In
proceeding of International Conference on Data Mining, pp: 842-847, 2009.
[8]. Vu Viet Vu, An efficient Semi-supervised graph based clustering,
Intelligent Data Analysis, 22 (2018) 297-307.
[9]. https://www.semanticscholar.org/paper/Semi-supervised-Density-Based-
Clustering-Lelis-Sander/03827b4aef6809ac90487ef1a9d27048088db413
[10]. Anil K. Jain: Data clustering: 50 years beyond K-means. Pattern
Recognition Letters, vol. 31(8), pp: 651-666, 2010.
[11]. Anand S.S., Mobasher B. Intelligent Techniques for Web
Personalization. In: Mobasher B., Anand S.S. (eds) Intelligent
50
Techniques for Web Personalization. Lecture Notes in Computer
Science, vol 3169. Springer, Berlin, Heidelberg, 2005.
[12]. Vũ Việt Vũ, Đỗ Hồng Quân, 2017, Density-based clustering with side
information and active learning. In proceeding of International
Conference on Knowledge and Systems Engineering, pp. 174-179.
[13]. Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu: A Density-
Based Algorithm for Discovering Clusters in Large Spatial Databases
with Noise. KDD, 1996.
[14]. S. Basu, I. Davidson, and K. L. Wagstaff, Constrained Clustering:
Advances in Algorithms, Theory, and Applications, Chapman and
Hall/CRC Data Mining and Knowledge Discovery Series, 1st edn., 2008.
[15]. W. M. Rand. Objective criteria for evaluation of clustering methods.
Journal of the American Statistical Association, 66(1971), pp. 846-850.
