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.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]).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]. Khai phá dữ liệu 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. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.
Quá trình khám phá tri thức trong CSDL 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Phân cụm dữ liệu 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.
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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com - 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. 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. 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,. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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, .