Đề tài Phân cụm dữ liệu dựa trên mật độ

BÁO CÁO TỐT NGHIỆPĐề tài: PHÂN CỤM DỮ LIỆU DỰA TRÊN MẬT ĐỘGiáo viên hướng dẫn: ThS. Nguyễn Thị Xuân HươngSinh viên thực hiện: Nguyễn Thị NgọcTRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNGBỘ MÔN: CÔNG NGHỆ THÔNG TINNỘI DUNG BÁO CÁO1. Tìm hiểu về phân cụm dữ liệu.2. Phân cụm dữ liệu dựa trên mật độ.3. Thuật toán DBSCAN.4. Cài đặt thực nghiệm.5. Kết luận.21. Tìm hiểu phân cụm dữ liệu1.1. Phân cụm dữ liệu:Phân cụm:Bài toán phân cụm: Cho cơ sở dữ liệu D={t1, t2,,tn}, phân cụm dữ liệu là bài toán xác định ánh xạ f: D→{1, 2, ,k} sao cho mỗi ti được gán vào một nhóm Kj với 1≤ j≤ k. 31.2. Các kiểu dữ liệu và độ đoBiến liên tục: Khoảng cách Minkowsky: Khoảng cách Euclidean: Khoảng cách Manhattan: Khoảng cách cực đại:41.2. Các kiểu dữ liệu và độ đo (tiếp)Biến nhị phân:Biến tập hợp:Biến thứ tự:Biến tỷ lệ:Biến hỗn hợp nhiều kiểu:51.3. Một số phương pháp phân cụm Phương pháp phân hoạch. Phương pháp phân cấp. Phương pháp dựa trên mật độ. Phương pháp dựa trên lưới. Phương pháp dựa trên mô hình.62. Phân cụm dữ liệu dựa trên mật độ2.1. Giới thiệu: Ý tưởng chính: Phương pháp này nhóm các đối tượng theo hàm mật độ xác định. Mật độ được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu theo một ngưỡng nào đó. Một số thuật toán tiêu biểu: DBSCAN OPTICS DENCLUE72.1. Giới thiệu (tiếp)2.1.1. Thuật toán DBSCANMột lớp được coi là một tập cực đại các kiểu liên thông. Ưu điểm: có thể phát hiện các cụm có hình dáng bất kỳ và làm việc với CSDL không gian chứa nhiễu.Nhược điểm: phải nhập vào 2 tham số đầu vào.82.1.2. Thuật toán OPTICS:Thuật toán OPTICS khởi tạo một thứ tự trong CSDL với việc thêm vào lưu trữ core – distance và reachability – distance cho phù hợp với mỗi đối tượng. Mỗi đối tượng trong CSDL sẽ dễ dàng tham gia vào thủ tục mở rộng cụm.OPTICS khắc phục nhược điểm của thuật toán DBSCAN.OPTICS tính toán tham số thứ tự lớp để phân tích lớp tự động, tương tác và biểu diễn cấu trúc chia lớp dựa vào mật độ thu được từ dải rộng các tham số.2.1. Giới thiệu (tiếp)92.1. Giới thiệu (tiếp)2.1.3. Thuật toán DENCLUESự tác động của một đối tượng tới láng giềng của nó được xác định bởi hàm ảnh hưởng.Mật độ toàn cục của không gian các đối tượng được mô hình như là tổng tất cả các hàm ảnh hưởng của đối tượng.Các cụm được xác định bởi các đối tượng mật độ cao toàn cục.102.1.3. Thuật toán DENCLUEThuật toán DENCLUE phụ thuộc nhiều vào ngưỡng nhiễu và tham số mật độ.Tuy nhiên, ưu điểm của thuật toán: - Có cơ sở toán học vững chắc. - Có khả năng xử lý các phần tử ngoại lai. - Cho phép khám phá các cụm có hình dạng bất kỳ. - Độ phức tạp O(nlogn).112.2. Một số khái niệm cơ bản Eps: MinPts: Mật độ: Đối tượng nòng cốt (core point): Đối tượng biên (border point): Đối tượng nhiễu (noise point):122.3. Một số định nghĩa Định nghĩa 1: Lân cận với ngưỡng Eps của một điểm: Ký hiệu Neps(p) = { q  D | khoảng cách Dist(p,q) ≤ Eps } D là tập dữ liệu cho trước. Định nghĩa 2: Đến được trực tiếp theo mật độ:132.3. Một số định nghĩa (tiếp) Định nghĩa 3: Đến được mật độ Định nghĩa 4: Liên thông mật độ:142.3. Một số định nghĩa (tiếp) Định nghĩa 5: CụmGiả sử D là một tập các điểm dữ liệu. Tập con C khác D được gọi là một cụm (cluster) theo một Eps và MinPts nếu: - p, q D, nếu pC và q có thể đến được từ p theo Eps và MinPts thì qC. - p, q  C, p liên thông mật độ với q theo Eps và MinPts.152.3. Một số định nghĩa (tiếp) Định nghĩa 6: Nhiễu Giả sử C1, C2, , Ck là các cụm trong tập dữ liệu D theo tham số Eps và MinPts Điểm dữ liệu nhiễu là điểm dữ liệu không thuộc vào cụm nào trong các cụm C1, C2, Ck, tức là noise = { p | với mọi i = 1 k, p  Ci}.163. Thuật toán DBSCAN3.1. Một số bổ đề: Bổ đề 1: Giả sử p là một điểm trong DTrong đó || Neps(p) || ≥ MinPtsTập O = { o|oD và o có thể đến được mật độ từ p theo Eps và MinPts} là một cụm thỏa mãn Eps và MinPts. 173.1. Một số bổ đề (tiếp) Bổ đề 2:Gọi C là một cụm thỏa mãn Eps và MinPts p là một đối tượng thuộc cụm C sao cho || Neps(p) || ≥ MinPts. Khi đó tập C tương đương với tập O = { o|oD và o có thể đến được mật độ từ p theo Eps và MinPts}.183.2. Thuật toánInput: CSDL D, Eps, MinPts.Output: CSDL D đã được phân vào các cụm sao cho các cụm có khả năng hỗ trợ cho ra quyết định. Độ đo khoảng cách sử dụng trong thuật toán là độ đo Euclidean:193.2. Thuật toán (tiếp)Thuật toán:Bước 1: Chọn ngẫu nhiên một đối tượng p.Bước 2: Tìm tất cả các đối tượng có mật độ có thể đạt được từ p theo Eps và MinPts.Bước 3: Nếu p là đối tượng nòng cốt thì hình thành một cụm (bổ đề 2). Nếu p là đối tượng biên (không có đối tượng nào là đối tượng có mật độ đạt được từ p) thì DBSCAN xem xét đối tượng tiếp theo trong CSDL.Bước 4: Tiếp tục cho đến khi tất cả các đối tượng trong CSDL được xử lý hết. 203.3. Xác định tham số Eps, MinPtsGọi d là khoảng cách từ điểm p tới k láng giềng gần nhất.Với k cho trước ta định nghĩa một hàm k-dist từ CSDL D tới các số thực.Sắp xếp giảm dần các giá trị k-dist trên một đồ thị.Chọn điểm p bất kỳ gán Eps=k-dist và gán MinPts=k213.4. Ưu nhược điểmCho 3 CSDL:Kết quả của DBSCAN:223.4. Ưu nhược điểm (tiếp)Ưu điểm:Khám phá các cụm có hình dáng bất kỳ.Làm việc tốt với CSDL lớn và có nhiễu.Độ phức tạp của thuật toán là O(nlogn).233.4. Ưu nhược điểm (tiếp)Nhược điểm: Không thích hợp với dữ liệu nhiều chiều. Không phù hợp với dữ liệu có mật độ khác nhau nhiều.244. Cài đặt thực nghiệm4.1. Dữ liệu đầu vàoCác điểm ảnh được lưu trữ trên CSDL với các thuộc tính:Trong đó ID: số thứ tự điểm ảnh x : tọa độ x điểm ảnh y : tọa độ y điểm ảnh254.2. Giao diện chính chương trình264.3. Kết quả chạy của thuật toán274.4. Nhận xétCho ra kết quả phân cụm của thuật toán DBSCAN đối với dữ liệu không gian lớn nhiều đối tượng, thời gian chạy nhanh.Hạn chế: phải nhập vào 2 tham số Eps và MinPts từ người dùng làm giảm hiệu quả và tính tự động hóa của thuật toán. 28KẾT LUẬNNội dung đã đạt được:Nghiên cứu về PCDL và kỹ thuật PCDL dựa trên mật độ.Tìm hiểu một số thuật toán PCDL dựa trên mật độ như DBSCAN, OPTICS, DENCLUE.Cài đặt chương trình thực nghiệm cho thuật toán DBSCAN.2. Hướng phát triển của đề tàiTiếp tục hoàn thiện chương trình.Cài đặt thực nghiệm cho thuật toán OPTICS, DENCLUE.Phát triển cài đặt với dữ liệu ảnh thực. 29Thank You !Ngọc30