Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị dữ liệu

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:87

Thêm vào BST

Báo xấu

22
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của đề tài nhằm cài đặt các thuật toán phân cụm có thứ bậc đã nghiên cứu, tiến hành thực nghiệm trên các bộ dữ liệu chuẩn (các mạng xã hội) nhằm đánh giá kết quả của từng thuật toán, qua đó lựa chọn thuật toán phù hợp cho việc phân cụm các mạng xã hội. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị dữ liệu

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT & TT THÁI NGUYÊN NGUYỄN THẾ ĐẠT NGHIÊN CỨU MÔ HÌNH PHÂN CỤM CÓ THỨ BẬC CÁC ĐỒ THỊ DỮ LIỆU LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên – 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT & TT THÁI NGUYÊN NGUYỄN THẾ ĐẠT NGHIÊN CỨU MÔ HÌNH PHÂN CỤM CÓ THỨ BẬC CÁC ĐỒ THỊ DỮ LIỆU Chuyên ngành: Khoa học máy tính Mã số: 60 48 0101 LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS ĐOÀN VĂN BAN Thái Nguyên – 2017
i LỜI CAM ĐOAN Tên tôi là: Nguyễn Thế Đạt Sinh ngày: 09/01/1979 Học viên lớp cao học CK14 - Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên. Hiện đang công tác tại: Trường THCS Hạp Lĩnh – TP Bắc Ninh – Bắc Ninh Xin cam đoan: Đề tài “Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị dữ liệu” do Thầy giáo PGS.TS Đoàn Văn Ban hướng dẫn là công trình nghiên cứu của riêng tôi. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng. Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng như nội dung trong đề cương và yêu cầu của thầy giáo hướng dẫn. Nếu sai tôi hoàn toàn chịu trách nhiệm trước hội đồng khoa học và trước pháp luật. Thái Nguyên, ngày 15 tháng 5 năm 2017 Tác giả luận văn Nguyễn Thế Đạt
ii LỜI CẢM ƠN Sau một thời gian nghiên cứu và làm việc nghiêm túc, được sự động viên, giúp đỡ và hướng dẫn tận tình của Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban, luận văn với đề tài “Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị dữ liệu”đã hoàn thành. Tôi xin bày tỏ lòng biết ơn sâu sắc đến: Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban đã tận tình chỉ dẫn, giúp đỡ tôi hoàn thành luận văn này. Khoa sau Đại học Trường Đại học công nghệ thông tin và truyền thông đã giúp đỡ tôi trong quá trình học tập cũng như thực hiện luận văn. Tôi xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã động viên, khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện và hoàn thành luận văn này. Thái Nguyên, ngày 15 tháng 5 năm 2017 Tác giả luận văn Nguyễn Thế Đạt
iii MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ............................................................................................................ii MỤC LỤC ................................................................................................................ iii DANH MỤC BẢNG .................................................................................................. v DANH MỤC CÁC TỪ VIẾT TẮT ......................................................................... vi DANH MỤC CÁC HÌNH VẼ.................................................................................vii MỞ ĐẦU .................................................................................................................... 1 CHƯƠNG 1: PHÂN CỤM DỮ LIỆU VÀ PHÂN CỤM ĐỒ THỊ DỮ LIỆU ...... 4 1.1. Phân cụm dữ liệu................................................................................................4 1.1.1. Khái niệm và mục tiêu của phân cụm dữ liệu ............................................4 1.1.2. Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu.........................7 1.1.3. Một số kỹ thuật trong phân cụm dữ liệu ..................................................10 1.1.4. Các ứng dụng của phân cụm dữ liệu ........................................................16 1.2. Phân cụm đồ thị dữ liệu ...................................................................................17 1.2.1. Mô hình đồ thị dữ liệu ..............................................................................17 1.2.2. Các loại độ đo ...........................................................................................18 1.2.3. Một số kỹ thuật phân cụm đồ thị dữ liệu ..................................................23 1.3. Kết luận chương 1 ............................................................................................28 CHƯƠNG 2: PHÂN CỤM CÓ THỨ BẬC CÁC ĐỒ THỊ DỮ LIỆU ................ 29 2.1. Thuật toán CHAMELEON ..............................................................................29 2.2. Thuật toán CURE .............................................................................................31 2.3. Thuật toán Girvan-Newman ............................................................................34 2.3.1. Giới thiệu về độ đo modularity ................................................................34 2.3.2. Độ đo trung gian .......................................................................................35 2.3.3. Thuật toán phân cụm Girvan-Newman ....................................................36 2.4. Thuật toán CNM (Clauset-Newman-Moore) ...................................................39 2.5. Thuật toán Rosvall-Bergstrom .........................................................................42
iv 2.6. Thuật toán INC (Incre-Comm-Extraction). .....................................................47 2.6.1. Nội dung thuật toán ..................................................................................47 2.6.2. Độ phức tạp của thuật toán .......................................................................49 2.6.3. Độ đo chất lượng phân cụm của thuật toán ..............................................50 2.7. Kết luận chương 2 ............................................................................................51 CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN PHÂN CỤM CÓ THỨ BẬC TRONG PHÂN CỤM ĐỒ THỊ DỮ LIỆU CÁC MẠNG XÃ HỘI ..................... 52 3.1. Bài toán phân cụm mạng xã hội .......................................................................52 3.2. Xây dựng chương trình ứng dụng phân cụm đồ thị các mạng xã hội ..............53 3.2.1. Giai đoạn 1: Thu thập dữ liệu ...................................................................53 3.2.2. Giai đoạn 2: Xử lý dữ liệu ........................................................................54 3.2.3. Giai đoạn 3: Xây dựng ứng dụng phân cụm có thứ bậc đồ thị các mạng xã hội ..................................................................................................................55 3.3. Các kết quả thực nghiệm và đánh giá ..............................................................56 3.3.1. Thời gian thực thi thuật toán ....................................................................57 3.3.2. Số cụm được phân chia ............................................................................58 3.3.3. Chất lượng phân cụm ...............................................................................58 3.4. Phân cụm đồ thị mạng xã hội dựa trên mối quan tâm của người dùng ...........58 3.4.1. Giới thiệu ..................................................................................................58 3.4.2. Mô hình hóa dữ liệu .................................................................................60 3.4.3. Xây dựng dữ liệu ......................................................................................62 3.4.4. Xây dựng ứng dụng ..................................................................................66 3.4.5. Thực nghiệm và đánh giá INC .................................................................69 3.5. Kết luận chương 3 ............................................................................................74 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................. 75 TÀI LIỆU THAM KHẢO ...................................................................................... 76
v DANH MỤC BẢNG Bảng 3.1: Kết quả thực thi các thuật toán…………………………………………57 Bảng 3.2: Kết quả thực thi 2 thuật toán INC và CNM…………………………….69
vi DANH MỤC CÁC TỪ VIẾT TẮT Từ hoặc Từ tiếng Anh Từ tiếng Việt cụm từ CNM Clauset-Newman-Moore Phân cụm có thứ bậc tích tụ CSDL Cơ sở dữ liệu Clustering Using CURE Phân cụm dữ liệu sử dụng điểm đại diện Representatives GN Girvan-Newman Phân cụm phân chia INC Incre-Comm-Extraction MCL Markov Clustering Phân cụm theo mô hình Markov RB Rosvall-Bergstrom
vii DANH MỤC CÁC HÌNH VẼ Hình 1.1: Ví dụ về phân cụm dữ liệu .........................................................................4 Hình 1.2: Ví dụ phân cụm các ngôi nhà dựa trên khoảng cách .................................5 Hình 1.3: Ví dụ phân cụm các ngôi nhà dựa trên kích cỡ ..........................................6 Hình 1.4: Các chiến lược phân cụm có thứ bậc .......................................................11 Hình 1.5: Ví dụ về phân cụm dựa theo mật độ ........................................................12 Hình 1.6: Cấu trúc phân cụm dựa trên lưới ..............................................................13 Hình 1.7: Ví dụ về phân cụm dựa trên mô hình .......................................................14 Hình 1.8: Các cách mà các cụm có thể đưa ra ..........................................................16 Hình 1.9: (a) Tối ưu đường kính cực tiểu hoặc tổng cực tiểu tạo ra cụm B nhưng A lại tốt hơn trên thực tế. (b) Tối ưu K-means tạo ra cụm B nhưng A lại tốt hơn . .....20 Hình 1.10: Minh họa mô hình đồ thị cho bước đi ngẫu nhiên …………………….25 Hình 2.1: Phân cụm Chameleon ...............................................................................31 Hình 2.2: Sự di chuyển về trung tâm cụm ...............................................................32 Hình 2.3: Sự sáp nhập của các cụm .........................................................................32 Hình 2.4: Cụm dữ liệu khai phá bởi thuật toán CURE ............................................33 Hình 2.5: Ví dụ phát hiện cụm sử dụng thuật toán Girvan - Newman . ...................38 Hình 2.6: Khung làm việc cơ sở để phân cụm đồ thị như quá trình truyền thông…42 Hình 2.7: Ví dụ về mã Huffman ...............................................................................43 Hình 2.8: Phân hoạch vào một lượng tối ưu các modul . ..........................................45 Hình 3.1: Các bước thực hiện chương trình .............................................................53 Hình 3.2: Ví dụ về tập dữ liệu Dolphins.gml ...........................................................54 Hình 3.3: Tập dữ liệu Dolphins.txt ..........................................................................54 Hình 3.4: Nạp file dữ liệu đầu vào ............................................................................55 Hình 3.5: Kết quả chạy thuật toán phân cụm CNM cho bộ dữ liệu dolphins.txt ......56 Hình 3.6: Kết quả chạy thuật toán Girvan-Newman cho bộ dữ liệu dolphins.txt.....56 Hình 3.7: Biểu đồ so sánh thời gian thực thi thuật toán ............................................57 Hình 3.8: Biểu đồ so sánh số lượng cụm .................................................................58
viii Hình 3.9: Biểu đồ so sánh chất lượng phân cụm.......................................................58 Hình 3.10: Đăng tin và bình luận trên Facebook ......................................................60 Hình 3.11: Một phần danh sách tài khoản Facebook ................................................62 Hình 3.12: Giao diện đăng ký một ứng dụng trên Facebook API ...........................63 Hình 3.13: Thu thập dữ liệu thủ công với Graph API Explorer ................................63 Hình 3.14: Thu thập dữ liệu tự động với Facebook API ...........................................64 Hình 3.15: Một phần dữ liệu thu thập được cập nhật trên SQL Server ....................64 Hình 3.16: Một phần dữ liệu về danh sách và số lượng ID người dùng đã bình luận trên các tường Facebook tương ứng. .........................................................................65 Hình 3.17: Một phần dữ liệu mạng xã hội dựa trên mối quan tâm của người dùng .66 Hình 3.18: Giao diện tự động thu thập bộ dữ liệu ....................................................67 Hình 3.19: Kết quả chạy chương trình phân cụm với INC và CNM. .......................68 Hình 3.20: Một phần biểu đồ dendrogram kết quả phân cụm với INC ....................68 Hình 3.21: Đồ thị so sánh thời gian thực thi INC và CNM ......................................69 Hình 3.22: Đồ thị so sánh số lượng cụm theo INC và CNM ....................................70 Hình 3.23: Đồ thị tương quan số lượng cụm với giá trị s .........................................70 Hình 3.24: Đồ thị so sánh chất lượng phân cụm theo INC và CNM ........................70 Hình 3.25: Đồ thị tương quan chất lượng cụm với giá trị s ......................................71 Hình 3.2.6: Kết quả phân chia cụm lớn thành các cụm con (bất động sản, chứng khoán, ô tô, xe máy...). ..............................................................................................72 Hình 3.27: Kết quả phân chia cụm lớn yêu thích đồ nội thất, lưu niệm, thời trang thành các cụm con (giày dép, đồng hồ,hoa tươi, quà lưu niệm, ngân hàng...). ........72 Hình 3.28: Kết quả phân cộng động quan tâm tới Phật giáo ....................................73 Hình 3.29: Kết quả phân cộng động quan tâm tới mỹ phẩm, thẩm mỹ, bệnh viện thẩm mỹ đã được phân chia theo INC................................................................................73
1 MỞ ĐẦU 1. Lý do chọn đề tài Trong những năm gần đây, cùng với sự phát triển vượt bậc của công nghệ thông tin, khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin không ngừng được nâng cao. Theo đó, lượng thông tin được lưu trữ trên các thiết bị nhớ không ngừng tăng lên. Khai phá dữ liệu là quá trình khám phá các tri thức mới có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. Quá trình khám phá tri thức là một chuỗi lặp gồm các bước: làm sạch dữ liệu, tích hợp dữ liệu, chọn lựa dữ liệu, đánh giá mẫu, biểu diễn tri thức. Khai phá dữ liệu liên quan đến nhiều lĩnh vực khác nhau như: công nghệ cơ sở dữ liệu, lý thuyết thống kê, học máy, khoa học thông tin, trực quan hóa, ... Những đồ thị lớn và mạng (networks) là những mô hình toán học tự nhiên cho những đối tượng tương tác với nhau như mối quan hệ giữa con người trong mạng xã hội, các cấu trúc phân tử trong mạng sinh học, mạng biểu diễn gene, ... Trong thực tế, cỡ của các mạng như thế khá lớn mà khả năng phân tích, khai thác các tính chất của chúng lại rất hạn chế. Hiện nay, các mạng xã hội ngày càng phát triển và trở nên vô cùng phổ biến. Trên thế giới hiện có hàng trăm trang mạng xã hội trực tuyến khác nhau, tiêu biểu như Facebook, Google+, Twitter, MySpace, YouTube, Instagram ...hay ở Việt Nam như Zing Me, Tamtay kết nối hàng trăm triệu người trên toàn thế giới. Các mạng xã hội này được người dùng sử dụng để giải trí, kinh doanh, chia sẻ thông tin, bày tỏ các quan điểm, mối quan tâm đến các lĩnh vực khác nhau cũng như để giao lưu, kết bạn, mở rộng các mối quan hệ... Việc phân cụm người dùng trong mạng có ý nghĩa vô cùng to lớn trong thực tế như: giúp cho việc truyền tải thông tin, tiếp thị bán hàng cũng như các hoạt động kinh doanh ... nhắm đến một lượng đông đảo các đối tượng quan tâm (thuộc cùng một cộng đồng) một cách dễ dàng hơn, ...[12]. Đã có nhiều thuật toán phân cụm khác nhau được đề xuất để phân cụm các đồ thị dữ liệu nói chung và đồ thị mạng xã hội nói riêng, trong đó các thuật toán phân cụm có thứ bậc tỏ ra rất hiệu quả với lớp bài toán này. Chính vì vậy, tôi đã chọn đề
2 tài "Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị dữ liệu" với mục đích tìm hiểu sâu hơn về phương pháp phân cụm có thứ bậc áp dụng cho các đồ thị dữ liệu, mà cụ thể trong luận văn là đồ thị dữ liệu các mạng xã hội. 2. Mục tiêu của đề tài • Tìm hiểu sâu về các thuật toán phân cụm có thứ bậc các đồ thị dữ liệu. • Cài đặt các thuật toán phân cụm có thứ bậc đã nghiên cứu, tiến hành thực nghiệm trên các bộ dữ liệu chuẩn (các mạng xã hội) nhằm đánh giá kết quả của từng thuật toán, qua đó lựa chọn thuật toán phù hợp cho việc phân cụm các mạng xã hội. 3. Đối tượng và phạm vi nghiên cứu ▪ Đối tượng nghiên cứu:  Tập đồ thị dữ liệu.  Các cụm trên đồ thị.  Các mạng xã hội. ▪ Phạm vi nghiên cứu  Phân cụm có thứ bậc trên đồ thị dữ liệu.  Nắm bắt và vận dụng lý thuyết đồ thị để biểu diễn mạng xã hội.  Tìm hiểu các độ đo trên đồ thị.  Nghiên cứu một số kỹ thuật phân cụm có thứ bậc trong khai phá đồ thị dữ liệu nói chung và đồ thị mạng xã hội nói riêng. 4. Phương pháp luận và phương pháp nghiên cứu Kết hợp lý thuyết được thu nhận từ nhiều nguồn như các bài báo, tài liệu, các công trình nghiên cứu liên quan đến các độ đo trong phân cụm, phân cụm có thứ bậc các đồ thị dữ liệu và các kỹ thuật phân cụm đồ thị dữ liệu, tiến hành xây dựng ứng dụng thử nghiệm đánh giá hiệu quả của các thuật toán, làm nổi bật kết quả nghiên cứu của luận văn.
3 5. Ý nghĩa khoa học của đề tài Phân cụm có thứ bậc đồ thị dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập đồ thị dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định. Ngoài ra, phân cụm có thứ bậc đồ thị dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu đồ thị khác như là phân loại và mô tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm, các mẫu theo yêu cầu. Luận văn gồm có phần mở đầu, kết luận và 03 chương, cụ thể như sau: Chương I. Phân cụm dữ liệu và phân cụm đồ thị dữ liệu Nghiên cứu tổng quan về các kỹ thuật phân cụm dữ liệu nói chung, ứng dụng của phân cụm dữ liệu. Qua đó làm tiền đề để nghiên cứu sâu hơn về phân cụm đồ thị dữ liệu: khái niệm đồ thị dữ liệu, các độ đo trong phân cụm dữ liệu nói chung và đồ thị dữ liệu nói riêng, các kỹ thuật phân cụm đồ thị. Chương II: Phân cụm có thứ bậc các đồ thị dữ liệu Nghiên cứu, trình bày một số thuật toán phổ biến sử dụng kỹ thuật phân cụm có thứ bậc trong phân cụm đồ thị dữ liệu như: thuật toán Chameleon, CURE, Girvan- Newman, CNM (Clauset Newmen Moore), Rosvall Bergtrom và INC (Incre-Comm- Extraction), đánh giá sơ bộ các ưu, nhược điểm của từng thuật toán. Chương III. Ứng dụng thuật toán phân cụm có thứ bậc trong phân cụm đồ thị dữ liệu các mạng xã hội Giới thiệu tổng quan về bài toán phân cụm mạng xã hội, các bộ dữ liệu mạng xã hội được sử dụng trong thực nghiệm. Tiến hành cài đặt các thuật toán đã nghiên cứu ở chương 2 và thực nghiệm trên các bộ dữ liệu chuẩn để đánh giá các kết quả đạt được, so sánh các thuật toán về thời gian thực thi, chất lượng phân cụm.
4 CHƯƠNG 1: PHÂN CỤM DỮ LIỆU VÀ PHÂN CỤM ĐỒ THỊ DỮ LIỆU 1.1. Phân cụm dữ liệu 1.1.1. Khái niệm và mục tiêu của phân cụm dữ liệu 1.1.1.1. Khái niệm phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật trong Data mining nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định. Phân cụm dữ liệu là sự phân chia một cơ sở dữ liệu lớn thành các nhóm dữ liệu với trong đó các đối tượng tương tự như nhau. Trong mỗi nhóm, một số chi tiết có thể không quan tâm đến để đổi lấy dữ liệu đơn giản hóa. Hay ta có thể hiểu “Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành từng nhóm mà các đối tượng ở mỗi nhóm đều tương tự nhau theo một tính chất nào đó, những đối tượng không tương tự tính chất sẽ ở nhóm khác” [3]. Phân cụm dữ liệu là một ví dụ của phương pháp học không có thầy. Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví dụ, ... Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu khác như là phân loại và mô tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm. Chúng ta có thể thấy điều này với một ví dụ đơn giản như sau: Hình 1.1: Ví dụ về phân cụm dữ liệu [3].
5 Trong trường hợp này, chúng ta dễ dàng xác định được 4 cụm dựa vào các dữ liệu đã cho; các tiêu chí “tương tự” để phân cụm trong trường hợp này là khoảng cách: hai hoặc nhiều đối tượng thuộc nhóm của chúng được “đóng gói” theo một khoảng cách nhất định. Điều này được gọi là phân cụm dựa trên khoảng cách. Một kiểu khác của phân cụm dữ liệu là phân cụm dữ liệu dựa vào khái niệm: hai hay nhiều đối tượng thuộc cùng nhóm nếu có một định nghĩa khái niệm chung cho tất cả các đối tượng trong đó. Nói cách khác, đối tượng của nhóm phải phù hợp với nhau theo miêu tả các khái niệm đã được định nghĩa, không phải theo những biện pháp đơn giản tương tự. 1.1.1.2. Mục tiêu của phân cụm dữ liệu Mục tiêu của phân cụm dữ liệu là để xác định các nhóm nội tại bên trong một bộ dữ liệu không có nhãn. Nhưng để có thể quyết định được cái gì tạo thành một cụm tốt. Nhưng làm thế nào để quyết định cái gì đã tạo nên một phân cụm dữ liệu tốt ? Nó có thể được hiển thị rằng không có tiêu chuẩn tuyệt đối “tốt nhất” mà sẽ là độc lập với mục đích cuối cùng của phân cụm dữ liệu. Do đó, mà người sử dụng phải cung cấp tiêu chuẩn, theo cách như vậy mà kết quả của phân cụm dữ liệu sẽ phù hợp với nhu cầu của họ cần. Ví dụ, chúng ta có thể quan tâm đến việc tìm kiếm đối tượng đại diện cho các nhóm đồng nhất trong “các cụm tự nhiên” và mô tả thuộc tính không biết của chúng trong việc tìm kiếm các nhóm hữu ích và phù hợp hoặc trong việc tìm kiếm các đối tượng bất thường trong dữ liệu (cá biệt, ngoại lệ, nhiễu). Hình 1.2: Ví dụ phân cụm các ngôi nhà dựa trên khoảng cách [3].
6 Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho phân cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì vậy cần phải xây dựng chiến lược cho bước tiền xử lí dữ liệu nhằm khắc phục hoặc loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích cụm dữ liệu. Nhiễu ở đây được hiểu là các đối tượng dữ liệu không chính xác, không tường minh hoặc là các đối tượng dữ liệu khuyết thiếu thông tin về một số thuộc tính, ... Một trong các kỹ thuật xử lí nhiễu phổ biến là việc thay thế giá trị các thuộc tính của đối tượng nhiễu bằng giá trị thuộc tính tương ứng. Ngoài ra, dò tìm đối tượng ngoại lai cũng là một trong những hướng nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác định một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ liệu trong cơ sở dữ liệu, tức là các đối tượng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả của phân cụm. Hình 1.3: Ví dụ phân cụm các ngôi nhà dựa trên kích cỡ [3]. Theo các nghiên cứu đến thời điểm hiện nay thì chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cơ sở dữ liệu. Hơn nữa, đối với các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc của cơ sở dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng một thuật toán phân cụm phù hợp. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu.
7 1.1.2. Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu 1.1.2.1. Phân loại các kiểu dữ liệu Cho một CSDL D chứa n đối tượng trong không gian k chiều trong đó x, y, z là các đối tượng thuộc D : x = (x1,x2,..,xk ); y = (y1,y2,..,yk); z = (z1,z2,..,zk), trong đó xi, yi, zi với i = 1…k là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng x, y, z. Sau đây là các kiểu dữ liệu: a. Phân loại các kiểu dữ liệu dựa trên kích thước miền - Thuộc tính liên tục (Continuous Attribute) : nếu miền giá trị của nó là vô hạn không đếm được - Thuộc tính rời rạc (DiscretteAttribute): Nếu miền giá trị của nó là tập hữu hạn, đếm được - Lớp các thuộc tính nhị phân: là trường hợp đặc biệt của thuộc tính rời rạc mà miền giá trị của nó chỉ có 2 phần tử được diễn tả như : Yes/No hoặc Nam/Nữ, False/true,… b. Phân loại các kiểu dữ liệu dựa trên hệ đo Giả sử rằng chúng ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau : - Thuộc tính định danh (Nominal Scale): đây là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử -nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x ≠ y hoặc x = y. - Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì ta có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x < y. - Thuộc tính khoảng (Interval Scale): Với thuộc tính khoảng, chúng ta có thể xác định một thuộc tính là đứng trước hoặc đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi > yi thì ta nói x cách y một khoảng xi - yi tương ứng với thuộc tính thứ i.
8 - Thuộc tính tỉ lệ (Ratio Scale): là thuộc tính khoảng nhưng được xác định một cách tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc cân nặng lấy điểm 0 làm mốc. Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), thuộc tính khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số (Numeric). 1.1.2.2. Độ đo tương tự và phi tương tự Để phân cụm, người ta phải đi tìm cách thích hợp để xác định “khoảng cách” giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu. 1. Không gian metric Tất cả các độ đo dưới đây được xác định trong không gian độ đo metric. Một không gian metric là một tập trong đó có xác định các “khoảng cách” giữa từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học. Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) các đối tượng dữ liệu trong CSDL D như đã đề cập ở trên được gọi là một không gian metric nếu: - Với mỗi cặp phần tử x, y thuộc X đều xác định, theo một quy tắc nào đó, một số thực δ(x,y), được gọi là khoảng cách giữa x và y. - Quy tắc nói trên thoả mãn hệ tính chất sau : δ(x,y) > 0 nếu x ≠ y ; (ii) δ(x, y) = 0 nếu x = y; (iii) δ(x,y) = δ(y,x) với mọi x,y; (iv) δ(x,y) ≤ δ(x,z) + δ(z,y). Hàm δ(x,y) được gọi là một metric của không gian. Các phần tử của X được gọi là các điểm của không gian này. 2. Thuộc tính khoảng cách: Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x,y được xác định bằng các metric khoảng cách như sau [6]: - Khoảng cách Minskowski: trong đó q là số tự nhiên dương. 1/ q  n q d  x, y     xi  yi  (1.1)  i 1 
9 - Khoảng cách Euclide: Đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q = 2. n d  x, y   x y 2 i i (1.2) i 1 - Khoảng cách Manhattan: Đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q = 1. n d  x, y    xi  yi (1.3) i 1 - Khoảng cách cực đại: là trường hợp của khoảng cách Minskowski trong trường hợp q = ∞. d  x, y   Maxin1 xi  yi (1.4) 3. Thuộc tính có thứ tự: Giả sử i là thuộc tính thứ tự có Mi giá trị (Mi kích thước miền giá trị): Các trạng thái Mi được sắp thứ tự như sau : [1…Mi], chúng ta có thể thay thế mỗi giá trị của thuộc tính bằng giá trị cùng loại ri, với ri ∈{1…Mi}. Mỗi một thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy chúng ta chuyển đổi chúng về cùng miền giá trị [0,1] bằng cách thực hiện phép biến đổi sau cho mỗi thuộc tính: (𝑗) (𝑗) 𝑟 −1 𝑍𝑖 = 𝑖 ) (1.5) 𝑀𝑖 − 1 Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với các giá (𝒋) trị 𝒁𝒊 , đây cũng chính là độ phi tương tự của thuộc tính có thứ tự. 4. Thuộc tính tỉ lệ: Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ. Một trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính. Hoặc loại bỏ đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hoá chúng, hoặc gán trọng số cho mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Với mỗi thuộc tính dữ liệu đã được gán trọng số tương ứng wi (1
10 𝑛 𝑑 (𝑥, 𝑦) = √∑ 𝑤𝑖 (𝑥𝑖 − 𝑦𝑖 )2 (1.6) 𝑖=1 1.1.3. Một số kỹ thuật trong phân cụm dữ liệu Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực tế, nó đều hướng tới hai mục tiêu chung đó là chất lượng của các cụm khám phá được và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật phân cụm có thể phân loại theo các phương pháp tiếp cận chính như sau: phân cụm phân họach (Partitioning Methods); phân cụm có thứ bậc (Hierarchical Methods); phân cụm dựa trên mật độ (Density-Based Methods); phân cụm dựa trên lưới (Grid-Based Methods); phân cụm dựa trên mô hình phân cụm (Model-Based Clustering Methods) và phân cụm có dữ liệu ràng buộc (Binding data Clustering Methods) [5]. 1.1.3.1. Phương pháp phân cụm phân hoạch Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k nhóm cho đến khi xác định số các cụm được thiết lập. Số các cụm được thiết lập là các đặc trưng được lựa chọn trước. Phương pháp này là tốt cho việc tìm các cụm hình cầu trong không gian Euclidean. Ngoài ra, phương pháp này cũng phụ thuộc vào khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là gần nhau với mỗi điểm khác và các điểm dữ liệu nào không có quan hệ hoặc có quan hệ là xa nhau so với mỗi điểm khác. Tuy nhiên, phương pháp này không thể xử lí các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc. Các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề phân cụm dữ liệu, do nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Chính vì vậy, trên thực tế thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của cụm cũng như để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Như vậy, ý tưởng chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược ăn tham (Greedy) để tìm kiếm nghiệm.