Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số thuật toán phân cụm dữ liệu nửa giám sát và ứng dụng phân đoạn ảnh X-quang

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

Thêm vào BST

Báo xấu

26
lượt xem 2
download

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

Mục tiêu của luận văn là nghiên cứu, tìm hiểu một số thuật toán phân cụm nửa giám sát và xây dựng được một ứng dụng thử nghiệm cho thuật toán phân đoạn ảnh X-quang hỗ trợ chuẩn đoán bệnh trong lĩnh vực nha khoa. 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ột số thuật toán phân cụm dữ liệu nửa giám sát và ứng dụng phân đoạn ảnh X-quang

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LÊ THỊ MAI HƯƠNG NGHIÊN CỨU MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU NỬA GIÁM SÁT VÀ ỨNG DỤNG PHÂN ĐOẠN ẢNH X-QUANG 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 CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LÊ THỊ MAI HƯƠNG NGHIÊN CỨU MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU NỬA GIÁM SÁT VÀ ỨNG DỤNG PHÂN ĐOẠN ẢNH X-QUANG Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Giáo viên hướng dẫn: TS.Nguyễn Đình Dũng THÁI NGUYÊN - 2017
LỜI CAM ĐOAN Tôi xin cam đoan luận văn này do chính tôi thực hiện, dưới sự hướng dẫn khoa học của TS. Nguyễn Đình Dũng, các kết quả lý thuyết được trình bày trong luận văn là sự tổng hợp từ các kết quả đã được công bố và có trích dẫn đầy đủ, kết quả của chương trình thực nghiệm trong luận văn này được tác giả thực hiện là hoàn toàn trung thực, nếu sai tôi hoàn toàn chịu trách nhiệm. Thái Nguyên, tháng 6 năm 2016 Học viên Lê Thị Mai Hương i
LỜI CẢM ƠN Luận văn này được hoàn thành tại Trường Đại học Công nghệ Thông tin và Truyền thông dưới sự hướng dẫn của TS. Nguyễn Đình Dũng. Tác giả xin bày tỏ lòng biết ơn tới các thầy cô giáo thuộc Trường Đại học Công nghệ Thông tin và Truyền thông, các thầy cô giáo thuộc Viện Công nghệ Thông tin – Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện, giúp đỡ tác giả trong quá trình học tập và làm luận văn tại Trường, đặc biệt tác giả xin bày tỏ lòng biết ơn tới TS. Nguyễn Đình Dũng đã tận tình hướng dẫn và cung cấp nhiều tài liệu cần thiết để tác giả có thể hoàn thành luận văn đúng thời hạn. Xin chân thành cảm ơn anh chị em học viên cao học và bạn bè đồng nghiệp đã trao đổi, khích lệ tác giả trong quá trình học tập và làm luận văn tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên. Cuối cùng tác giả xin gửi lời cảm ơn đến gia đình, những người đã luôn bên cạnh, động viên và khuyến khích tôi trong quá trình thực hiện đề tài. Thái Nguyên, ngày tháng năm 2017 Học viên Lê Thị Mai Hương ii
MỤC LỤC LỜI CẢM ƠN ........................................................................................................ i LỜI CAM ĐOAN................................................................................................... i DANH MỤC TỪ VIẾT TẮT ................................................................................ v DANH MỤC HÌNH VẼ ....................................................................................... vi LỜI MỞ ĐẦU ....................................................................................................... 1 CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU VÀ BÀI TOÁN PHÂN ĐOẠN ẢNH X-QUANG NHA KHOA ................................................. 3 1.1. Khai phá dữ liệu........................................................................................ 3 1.1.1. Khái niệm khai phá dữ liệu ................................................................ 3 1.1.2. Quá trình khai phá tri thức trong cơ sở dữ liệu .................................. 3 1.1.3. Các kỹ thuật tiếp cận trong khai phá dữ liệu: ........................................ 5 1.2. Phân cụm dữ liệu ...................................................................................... 6 1.2.1. Khái niệm phân cụm dữ liệu .............................................................. 6 1.2.2. Các bước cơ bản để phân cụm dữ liệu ............................................... 6 1.2.3. Các kiểu dữ liệu và độ đo tương tự, độ đo phi tương tự .................... 7 1.2.3.1. Phân loại kiểu dữ liệu dựa trên kích thước miền ......................... 7 1.2.3.2. Phân loại kiểu dữ liệu dựa trên hệ đo .......................................... 7 1.2.3.3. Khái niệm và phép đo độ tương tự .............................................. 9 1.2.4. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu ............................... 12 1.2.5. Ứng dụng của phân cụm dữ liệu ...................................................... 14 1.3. Cấu trúc giải phẫu răng ........................................................................... 15 1.3.1. Cấu trúc giải phẫu răng .................................................................... 15 1.3.2. Phân loại ảnh X - quang nha khoa ................................................... 17 1.4. Bài toán phân đoạn ảnh X - quang nha khoa .......................................... 19 1.4.1. Phân đoạn ảnh .................................................................................. 19 1.4.2. Phân loại các phương pháp phân đoạn ảnh ...................................... 20 1.4.3. Phân đoạn ảnh X – quang nha khoa ................................................. 21 KẾT LUẬN CHƯƠNG 1 .................................................................................... 23 CHƯƠNG 2: MỘT SỐ THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT ... 24 2.1. Phân cụm mờ .......................................................................................... 24 2.1.1. Các khái niệm cơ bản về tập mờ ...................................................... 24 iii
2.1.2. Thuật toán phân cụm mờ FCM (Fuzzy C-Means) ........................... 28 2.2. Thuật toán phân cụm nửa giám sát mờ bằng phương pháp học tích cực31 2.3. Thuật toán phân cụm nửa giám sát mờ chuẩn (SSSFC) ......................... 33 2.4. Thuật toán phân cụm nửa giám sát mờ theo quy tắc entropy (eSFCM) 35 2.5. Thuật toán nửa giám sát mờ lai ghép ..................................................... 36 2.5.1. Lược đồ tổng quan lai ghép .............................................................. 36 2.5.2. Thuật toán tách ngưỡng Otsu ........................................................... 38 2.5.3. Thuật toán phân cụm nửa giám sát mờ lai ghép .............................. 40 KẾT LUẬN CHƯƠNG 2 .................................................................................... 41 CHƯƠNG 3: XÂY DỰNG ỨNG DỤNG PHÂN ĐOẠN ẢNH X – QUANG NHA KHOA ....................................................................................................... 42 3.1. Đặc tả yêu cầu......................................................................................... 42 3.1.1. Yêu cầu thực tế ................................................................................. 42 3.1.2. Mục đích của ứng dụng .................................................................... 43 3.2. Đặc tả dữ liệu .......................................................................................... 43 3.3. Các bước phân đoạn ảnh......................................................................... 44 3.4. Thiết kế hệ thống .................................................................................... 45 3.4.1. Chức năng phân đoạn ảnh X – quang nha khoa ............................... 45 3.4.2. Chức năng xem chi tiết kết quả ........................................................ 46 3.4.3. Chức năng đánh giá chất lượng phân đoạn ...................................... 47 3.5. Minh họa các chức năng của ứng dụng .................................................. 48 3.5.1. Giao diện chính của ứng dụng.......................................................... 48 3.5.2. Chọn ảnh cần phân đoạn .................................................................. 49 3.5.3. Phân đoạn ảnh bằng thuật toán FCM ............................................... 49 3.5.4. Phân đoạn ảnh bằng thuật toán nửa giám sát mờ ............................. 50 3.5.5. Chọn độ đo đánh giá kết quả phân cụm ........................................... 50 3.6. Đánh giá kết quả phân đoạn ................................................................... 51 KẾT LUẬN CHƯƠNG 3 .................................................................................... 52 KẾT LUẬN ........................................................................................................ 53 TÀI LIỆU THAM KHẢO ................................................................................ 54 PHỤ LỤC ........................................................................................................... 57 CODE MATLAB CỦA ỨNG DỤNG PHÂN ĐOẠN ẢNH BẰNG THUẬT TOÁN BÁN GIÁM SÁT MỜ LAI GHÉP ...................................................... 57 iv
DANH MỤC TỪ VIẾT TẮT Từ viết tắt Từ viết đầy đủ DB Davies-Bouldin eSFCM Semi-supervised Entropy regularized Fuzzy Clustering FCM Fuzzy C-Mean PBM Pakhira, Bandyopadhyay and Maulik SSFCM Semi-Supervised Fuzzy C-Mean SSSFC Semi-Supervised Standard Fuzzy Clustering SSWC Simplified Silhouete Width Criterion CSDL Cơ sở dữ liệu PCDL Phân cụm dữ liệu v
DANH MỤC HÌNH VẼ Hình 1.1. Quá trình khám phá tri thức trong CSDL ............................................. 4 Hình 1.2. Cơ quan răng (răng và nha chu) .......................................................... 15 Hình 1.3. Một số loại ảnh X-Quang nha khoa .................................................... 19 Hình 1.4. Những khó khăn trong việc phân đoạn ảnh nha khoa......................... 22 Hình 2.1. Hàm thuộc tuyến tính .......................................................................... 25 Hình 2.2. Hàm thuộc dạng sin. ............................................................................ 25 Hình 2.3. Hàm thuộc Gauss ................................................................................ 26 Hình 2.4. Bao trong của tập mờ .......................................................................... 26 Hình 2.5. Phép hợp tập mờ dạng 1 ...................................................................... 27 Hình 2.6. Phép giao tập mờ dạng 1 ..................................................................... 28 Hình 2.7. Phần bù của tập mờ trung bình ........................................................... 28 Hình 2.8. Lược đồ tổng quan của thuật toán lai ghép ......................................... 37 Hình 3.1: Ảnh dữ liệu đầu vào của ứng dụng ..................................................... 44 Hình 3.2: Biểu đồ usecase mô tả chức năng của ứng dụng ................................ 45 Hình 3.3: Biểu đồ trình tự chức năng phân đoạn ảnh ......................................... 46 Hình 3.4: Biểu đồ trình tự chức năng xem kết quả ............................................. 47 Hình 3.5: Biểu đồ trình tự chức năng đánh giá kết quả ..................................... 48 Hình 3.6: Giao diện chính của phần mềm .......................................................... 48 Hình 3.7: Chọn ảnh cần phân đoạn .................................................................... 49 Hình 3.8. Kết quả phân đoạn bằng FCM ............................................................ 49 Hình 3.9. Kết quả phân đoạn bằng SSSFC ......................................................... 50 Hình 3.10. Đánh giá kết quả phân đoạn .............................................................. 50 vi
LỜI MỞ ĐẦU Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng lồ và phức tạp đồng thời cũng tìm ra các mẫu tiềm ẩn trong dữ liệu đó. Hiện nay việc khai phá dữ liệu được nghiên cứu theo các hướng mô tả khái niệm, luật kết hợp, phân lớp và dự đoán, phân cụm (xem [1], [2], [7]) và có nhiều ứng dụng trong thực tế, trong đó phân đoạn ảnh X-Quang trong lĩnh vực y tế là một ứng dụng điển hình [13]. Ngày nay, việc xử lý các hình ảnh y tế có vai trò quan trọng trong việc tự động hóa phân tích, hỗ trợ chẩn đoán và điều trị các bệnh khác nhau. Trong đó, quá trình phân đoạn thường được yêu cầu như là giai đoạn sơ bộ. Tuy nhiên các phân vùng trong hình ảnh y tế rất phức tạp nên việc phân đoạn chính xác là rất quan trọng. Trong các phương pháp phân đoạn ảnh hiện có, phân cụm là một phương pháp được sử dụng rộng rãi bởi tính đơn giản và hiệu quả mà nó mang lại (xem [8]-[12]). Phân cụm dữ liệu là lĩnh vực học máy không giám sát, nó có chức năng tổ chức một tập đối tượng dữ liệu thành các cụm sao cho những đối tượng trong cùng một cụm thì tương tự như nhau còn các đối tượng ở các cụm khác nhau thì kém tương tự nhau hơn. Nhược điểm chung của thuật toán phân cụm là chất lượng phân cụm phụ thuộc nhiều vào các tham số và thông tin khởi tạo. Để giảm thiểu các hạn chế này, gần đây đã có nhiều tác giả (xem [8]-[12]) giải quyết theo cách tiếp cận nửa giám sát, trong đó việc phân cụm được thực hiện dựa vào các thông tin bổ trợ đóng vai trò điều khiển quá trình phân cụm, nhờ đó mà chất lượng phân cụm được nâng lên đáng kể. Mục tiêu của luận văn là nghiên cứu, tìm hiểu một số thuật toán phân cụm nửa giám sát và xây dựng được một ứng dụng thử nghiệm cho thuật toán phân đoạn ảnh X-quang hỗ trợ chuẩn đoán bệnh trong lĩnh vực nha khoa. Các kết quả đạt được trong luận văn này là kết quả trong quá trình học tập và nghiên cứu của tác giả tại Trường Đại học Công nghệ Thông tin và Truyền thông. Ngoài phần 1
mở đầu, kết luận và tài liệu tham khảo, nội dung luận văn được trình bày thành ba chương: Chương 1 trình bày các khái niệm cơ bản về phân cụm dữ liệu và bài toán phân đoạn ảnh X-quang nha khoa. Chương 2, tác giả tìm hiểu một số thuật toán phân cụm dữ liệu trong đó tập trung nghiên cứu thuật toán phân cụm dữ liệu nửa giám sát. Chương 3 là kết quả thực nghiệm cho thuật toán phân cụm nửa giám sát đối với bài toán phân đoạn ảnh X-quang nha khoa. 2
CHƯƠNG 1 TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU VÀ BÀI TOÁN PHÂN ĐOẠN ẢNH X-QUANG NHA KHOA Chương này gồm 3 mục, mục 1.1 là các khái niệm cơ bản về Khai phá dữ liệu. Mục 1.2 trình bày về các khái niệm về phân cụm dữ liệu, yêu cầu đối với kỹ thuật phân cụm dữ liệu (xem [1], [2], [4]). Mục 1.3 là cấu tạo về răng, phân loại ảnh X-quang và bài toán phân đoạn ảnh X-quang nha khoa [3]. 1.1. Khai phá dữ liệu 1.1.1. Khái niệm khai phá dữ liệu Khai phá dữ liệu là một công đoạn quan trọng nhất trong quá trình khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD). Do sự phát triển mạnh mẽ của khai phá dữ liệu về phạm vi các lĩnh vực ứng dụng trong thực tế và các phương pháp tìm kiếm nên có rất nhiều khái niệm khác nhau. Tuy nhiên, ở đây có thể hiểu khai phá dữ liệu là một quá trình tìm kiếm, chắt lọc các tri thức mới, tiềm ẩn, hữu dụng trong tập dữ liệu lớn. 1.1.2. Quá trình khai phá tri thức trong cơ sở dữ liệu Các yêu cầu về thông tin trong các loại hoạt động như công tác quản lý, hoạt động kinh doanh, phát triển sản xuất và dịch vụ, đặc biệt là trong việc ra quyết định giải quyết một vấn đề ngày càng đòi hỏi chất lượng cao hơn. Người làm quyết định không những cần dữ liệu mà còn cần có thêm hiểu biết, nhiều tri thức để hỗ trợ cho việc ra quyết định của mình. Để giải quyết vấn đề đó thì kỹ thuật khám phá tri thức trong cơ sở dữ liệu (KDD) đã ra đời. Khám phá tri thức trong cơ sở dữ liệu là lĩnh vực liên quan đến các ngành như: xác suất thống kê, học máy, trực quan hóa dữ liệu, tính toán song song ... Quá trình KDD có thể chia thành 5 bước thực hiện như sau: Trích chọn dữ liệu: Xác định mục đích của quy trình khai phá dữ liệu dựa trên quan điểm của người dùng, thu thập và chuẩn bị dữ liệu để khai phá. 3
Tiền xử lý dữ liệu: Nhằm mục đích loại bỏ sự trùng lặp dữ liệu, cắt lìa những thông tin có thể gây nhiễu, tập hợp những thông tin cần thiết cho mô hình hóa, chọn các phương pháp xử lý những thông tin bị khiếm khuyết. Chuyển đổi dữ liệu: Thực hiện thu gọn dữ liệu, phép ánh xạ dữ liệu, tìm những đặc trưng phù hợp để mô tả và khai phá dữ liệu. Khai phá dữ liệu: Chọn nhiệm vụ khai phá dữ liệu như phân lớp, gom cụm, hồi quy, kết hợp, ... Từ nhiệm vụ đã chọn, sử dụng các thuật toán và các phương pháp đã biết để tìm kiếm các mẫu trong dữ liệu, chọn ra các mẫu hữu ích. Trình bày và đánh giá: Từ các mẫu khai phá được tiến hành đánh giá hoặc phiên dịch thành những tri thức hiểu được. Trình bày, đánh giá Tri thức Khai phá Chuyển đổi Tiền xử lý DL Trích chọn DL Hình 1.1. Quá trình khám phá tri thức trong CSDL 4
1.1.3. Các kỹ thuật tiếp cận trong khai phá dữ liệu: Các kỹ thuật áp dụng trong khai phá dữ liệu phần lớn được kế thừa từ các lĩnh vực như: Cơ sở dữ liệu, Học máy, Trí tuệ nhân tạo, Xác suất thống kế, ... vì vậy ta có hai hướng tiếp cận sau đây: Theo quan điểm của học máy, các kỹ thuật trong Khai phá dữ liệu gồm: - Học có giám sát (Supervised learning): Là quá trình gán nhãn lớp cho các đối tượng trong tập dữ liệu dựa trên một bộ các đối tượng huấn luyện và các thông tin về nhãn lớp đã biết. - Học không giám sát (Unsupervised learning): Là quá trình phân chia một tập dữ liệu thành các lớp hay cụm (cluster) dữ liệu tương tự nhau mà chưa biết trước các thông tin về nhãn lớp. - Học nửa giám sát (Semi- Supervised learning): Là quá trình chia một tập dữ liệu thành các lớp con dựa trên một số thông tin bổ trợ cho trước. Theo các lớp bài toán cần giải quyết, các kỹ thuật trong khai phá dữ liệu gồm: - Phân lớp và dự toán (Classification and Prediction): Đưa một đối tượng vào một trong các lớp đã biết trước. Phân lớp và dự đoán còn được gọi là học có giám sát. - Luật kết hợp (Association rules): Là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Một luật kết hợp được mô tả như sau:Nếu a thì b với xác suất p - Phân tích chuỗi theo thời gian: Giống như khai phá luật kết hợp nhưng có thêm tính thứ tự và thời gian. - Phân cụm (Clustering): Nhóm các đối tượng thành từng cụm dữ liệu. Đây là phương pháp học không giám sát. - Mô tả khái niệm: Mô tả, tổng hợp và tóm tắt khái niệm, ví dụ như tóm tắt văn bản. 5
1.2. Phân cụm dữ liệu 1.2.1. Khái niệm phân cụm dữ liệu Phân cụm dữ liệu (PCDL) là một kỹ thuật phát triển mạnh mẽ trong nhiều năm trở lại đây do các ứng dụng và lợi ích to lớn của nó trong các lĩnh vực thực tế. Ở mức độ cơ bản nhất có thể hiểu Phân cụm dữ liệu là một kỹ thuật trong khai phá 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 dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định. 1.2.2. Các bước cơ bản để phân cụm dữ liệu PCDL là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các đối tượng trong một cụm thì “tương tự” nhau và các đối tượng trong các cụm khác nhau thì “phi tương tự” với nhau. Số cụm dữ liệu được xác định bằng kinh nghiệm hoặc bằng một số phương pháp phân cụm. Sau khi xác định các đặc tính của dữ liệu, người ta đi tìm cách thích hợp để xác định “khoảng cách” giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây chính là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự(Dissimilar) giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống nhau giữa đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ nghịch với hàm tính độ tương tự. Trong quá trình PCDL thì vấn đề trở ngại lớn nhất đó là nhiễu (noise). Nhiễu xuất hiện do trong quá trình thu thập thông tin, dữ liệu thiếu chính xác hoặc không đầy đủ. Vì vậy chúng ta cần phải khử nhiễu trong quá trình tiến hành phân cụm dữ liệu. Các bước của một bài toán phân cụm dữ liệu gồm: - Xây dựng hàm tính độ tương tự - Xây dựng các tiêu chuẩn phân cụm - Xây dựng mô hình cho cấu trúc dữ liệu 6
- Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo - Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm 1.2.3. Các kiểu dữ liệu và độ đo tương tự, độ đo phi tương tự Trong phần này ta phân tích các kiểu dữ liệu thường được sử dụng trong PCDL. Trong PCDL, các đối tượng dữ liệu cần phân tích có thể là con người, nhà cửa, tiền lương, các thực thể phần mềm, ... Các đối tượng này thường được diễn tả dưới dạng các thuộc tính của nó. Các thuộc tính này là các tham số cần cho giải quyết vấn đề PCDL và sự lựa chọn chúng có tác động đáng kể đến các kết quả của phân cụm. Phân loại các kiểu thuộc tính khác nhau là một vấn đề cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các phương tiện thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Dưới đây là cách phân lớp dựa trên hai đặc trưng là: kích thước miền và hệ đo. 1.2.3.1. Phân loại kiểu dữ liệu dựa trên kích thước miền - Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm được, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Thí dụ như các thuộc tính về màu, nhiệt độ hoặc cường độ âm thanh. - Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn hoặc đếm được. Thí dụ như các thuộc tính về số serial của một cuốn sách, số thành viên trong một gia đình, ... 1.2.3.2. Phân loại kiểu dữ liệu dựa trên hệ đo Giả sử 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. Ta có các lớp kiểu dữ liệu như sau: - Thuộc tính định danh: Dạng thuộc tính khái quát hóa 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à 𝑥 ≠ 𝑦 hoặc 𝑥 = 𝑦. - Thuộc tính có thứ tự: 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ể 7
xác định là 𝑥 ≠ 𝑦 hoặc 𝑥 = 𝑦 hoặc 𝑥 > 𝑦 hoặc 𝑥 < 𝑦. Thí dụ như thuộc tính Huy chương của vận động viên thể thao. - Thuộc tính khoảng: Nhằm để đo các giá trị theo xấp xỉ tuyến tính. Với thuộc tính khoả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. Ví dụ, thuộc tính số Serial của một đầu sách trong thư viện hoặc thuộc tính số kênh trên truyền hình. - Thuộc tính tỉ lệ: 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 giá trị 0 làm gố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, thuộc tính khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số. Người ta còn đặc biệt quan tâm đến dữ liệu không gian. Đây là loại dữ liệu có các thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên quan đến không gian chứa đựng các đối tượng, thí dụ như thông tin về hình học, ... Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc: Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều chiều và cho phép ta xác định được khoảng cách giữa các đối tượng dữ liệu trong không gian. Dữ liệu không gian liên tục: Bao gồm một vùng trong không gian. Thông thường, các thuộc tính số được đo bằng các đơn vị xác định như là Kilogams hoặc Centimeter. Tuy nhiên, các đơn vị đo có ảnh hưởng đến các kết quả phân cụm. Thí dụ như thay đổi độ đo cho thuộc tính cân nặng từ Kilogams sang Pound có thể mang lại kết quả khác nhau trong phân cụm. Để khắc phục điều này người ta phải chuẩn hóa dữ liệu, tức là sử dụng các thuộc tính dữ liệu không phụ thuộc vào đơn vị đo. Thực hiện chuẩn hóa phụ thuộc vào ứng dụng và người dùng, thông thường chuẩn hóa dữ liệu được thực hiện bằng cách thay 8
thế mỗi một thuộc tính bằng thuộc tính số hoặc thêm các trọng số cho các thuộc tính. 1.2.3.3. Khái niệm và phép đo độ tương tự Khi các đặc tính của dữ liệu được xác định, người ta tìm cách thích hợp để xác định “khoảng cách” giữa các đối tượng (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ự hoặc là tính độ phi tương tự giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống nhau giữa đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ nghịch với hàm tính độ tương tự. Độ tương tự hoặc độ phi tương tự có nhiều cách để xác định, chúng thường được đo bằng khoảng cách giữa các đối tượng. Tất cả các cách đo độ tương tự đều phụ thuộc vào kiểu thuộc tính mà ta phân tích. Thí dụ, đối với thuộc tính hạng mục người ta không sử dụng độ đo khoảng cách mà sử dụng một hướng hình học của dữ liệu. Tất cả các độ đo dưới đây được xác định trong không gian độ đo metric. Bất kỳ một metric nào cũng là một độ đo, nhưng điều ngược lại không đúng. Để tránh sự nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tương tự. 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ỳ) gồm các đối tượng dữ liệu trong CSDL 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 một số thực δ(x, y), được gọi là khoảng cách giữa x và y thỏa mãn hệ tính chất sau:  ( x, y)  0 nếu x ≠ y;  ( x, y)  0 nếu x = y;  ( x, y)   ( y, x) với mọi x, y;  ( x, y)   ( x, z) +  ( z, y) . 9
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. Một số phép đo độ tương tự áp dụng đối với các kiểu dữ liệu khác nhau: + Thuộc tính khoảng: Sau khi chuẩn hóa, độ đ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 như sau: |xi – yi|q   1 Khoảng cách Minskowski: d  x, y   , với q là số nguyên n q xi  yi q i 1 dương. Khoảng cách Euclide: d  x, y    x  y  , (trường hợp đặc biệt của n 2 i 1 i i khoảng cách Minskowski trong trường hợp q = 2. Khoảng cách Manhattan: d  x, y   in1 xi  yi , trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q = 1. Khoảng cách cực đại: d  x, y   Maxin1 xi  yi , đây là trường hợp của khoảng cách Minskowski trong trường hợp . +Thuộc tính nhị phân: Trước hết ta có xây dựng bảng tham số sau: y: 1 y: 0 x: 1 x: 0 Bảng 1. Bảng tham số thuộc tính nhị phân Trong đó:          , các đối tượng x, y mà tất cả các thuộc tính của nó đều là nhị phân biểu thị bằng 0 và 1. Bảng trên cho ta thông tin sau: -  là tổng số các giá trị thuộc tính có giá trị là 1 trong cả hai đối tượng x, y. -  là tổng số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y. -  là tổng số các giá trị thuộc tính có giá trị là 0 trong x và 1 trong y. -  là tổng số các giá trị thuộc tính có giá trị là 0 trong cả hai đối tượng x, y. Các phép đo độ tương tự đối với dữ liệu thuộc tính nhị phân được định nghĩa như sau: 10
- Hệ số đối sánh đơn giản: d  x, y      , ở đây cả hai đối tượng x và y có  vai trò như nhau, nghĩa là chúng đối xứng và có cùng trọng số.  - Hệ số Jacard: d  x, y   , tham số này bỏ qua số các đối sánh     giữa 0-0. Công thức tính này được sử dụng trong trường hợp mà trọng số của các thuộc tính có giá trị 1 của đối tượng dữ liệu có giá trị cao hơn nhiều so với các thuộc tính có giá trị 0, như vậy các thuộc tính nhị phân ở đây là không đối xứng. + Thuộc tính định danh: Độ đo phi tương tự giữa hai đối tượng x và y pm được định nghĩa như sau: d  x, y   , trong đó m là số thuộc tính đối sánh p tương ứng trùng nhau và p là tổng số các thuộc tính. + Thuộc tính có thứ tự: Phép đo độ phi tương tự giữa các đối tượng dữ liệu với thuộc tính thứ tự được thực hiện như sau, ở đây ta giả sử i là thuộc tính thứ tự có M i giá trị ( M i kích thước miền giá trị): Các trạng thái M i được sắp thứ tự như sau: 1...M i  , 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,..., M i  . Mỗi một thuộc tính thứ tự có các miền giá trị khác nhau, vì vậy 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 ri j   1 mỗi thuộc tính: zi j   , với M i 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ị zi j  , đây cũng chính là độ phi tương tự của thuộc tính có thứ tự. + 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 xi , thí dụ qi  log  xi  , lúc này qi đóng vai trò như thuộc tính khoảng. Phép biến đổi logarit này thích hợp trong trường hợp các giá trị của thuộc tính là số mũ. 11
Trong thực tế, khi tính độ đo tương tự dữ liệu, người ta chỉ xem xét một phần các thuộc tính đặc trưng đối với các kiểu dữ liệu hoặc đánh trọng số cho tất cả các thuộc tính dữ liệu. Trong một số trường hợp, người ta loại bỏ đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hóa 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. Các trọng số này có thể sử dụng trong các độ đo khoảng cách trên, thí dụ với mỗi thuộc tính dữ liệu đã được gán trọng số tương ứng wi 1  i  k  , độ tương tự dữ liệu được xác định như sau: d  x, y    wi  xi  yi  . n 2 i 1 Người ta có thể chuyển đổi giữa các mô hình cho các kiểu dữ liệu trên, thí dụ dữ liệu kiểu hạng mục có thể chuyển đổi thành dữ liệu nhị phân và ngược lại. Nhưng giải pháp này rất tốn kém về chi phí tính toán, cần phải cân nhắc khi áp dụng cách thức này. Tùy từng trường hợp dữ liệu cụ thể mà người ta sử dụng các mô hình tính độ tương tự khác nhau. Việc xác định độ tương tự dữ liệu thích hợp, chính xác, đảm bảo khách quan là rất quan trọng và góp phần xây dựng thuật toán PCDL có hiệu quả cao trong việc đảm bảo chất lượng cũng như chi phí tính toán của thuật toán. 1.2.4. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu Việc xây dựng, lựa chọn một thuật toán phân cụm là bươc then chốt cho việc giải quyết vấn đề phân cụm, sự lựa chọn này phụ thuộc vào đặc tính dữ liệu cần phân cụm, mục đích của ứng dụng thực tế hoặc xác định độ ưu tiên giữa chất lượng của các cụm hay tốc độ thực hiện thuật toán, ... Hầu hết các nghiên cứu và phát triển thuật toán PCDL đều nhằm thỏa mãn các yêu cầu cơ bản sau: Có khả năng mở rộng: Một số thuật toán có thể ứng dụng tốt cho tập dữ liệu nhỏ (khoảng 200 bản ghi dữ liệu) nhưng không hiệu quả khi áp dụng cho tập dữ liệu lớn (khoảng 1 triệu bản ghi). 12