Luận văn Nghiên cứu và cài đặt một số giải thuật phân cụm, phân lớp

,( ),( 'min),( ',max ' ',min ppCCd ppnnCCd mmCCd ppCCd ji i j ji CpCpji Cp Cpjijiavg jijimean CpCpji −= −= −= −= ∈∈ ∈ ∈ ∈∈ ∑ ∑ Ví dụ 3.4: Giả sử có một tập đối tượng được định vị trong một hình chữ nhật như hình 3.5. Phương pháp phân cụm phân cấp tích đống AGNES làm việc như sau: Ban đầu mọi đối tượng được đặt vào trong một cụm của bản thân nó. Sau đó các cụm này được hoà nhập từng bước theo một số nguyên tắc như hoà nhập các cụm với khoảng cách Euclidean tối thiểu giữa các đối tượng gần nhất trong cụm. Hình 3.5 a) chỉ ra rằng các cụm đối tượng đơn gần nhất (tức là với khoảng cách Euclidean tối thiểu) trước tiên được hoà nhập vào trong hai cụm đối tượng. Xử lý hoà nhập cụm này được lặp lại và các cụm gần nhất lại được hoà nhập sau đó, như hình 3.5 b) và c). Cuối cùng, tất cả các đối tượng được hoà nhập vào trong một cụm lớn. Hình 3.5: Phân cụm một tập các điểm dựa trên phương pháp "Tích đống lồng" Phương pháp phân cụm phân cấp phân ly DIANA làm việc theo trật tự ngược lại. Đó là, trước tiên tất cả các đối tượng được đặt vào trong một cụm. Sau đó cụm được chia theo một số nguyên tắc, như là chia các cụm theo khoảng cách Euclidean cực đại giữa các đối tượng láng giềng gần nhất trong cụm. Hình 3.5 c) có thể được quan sát như là kết quả của phép phân chia đầu tiên. Xử lý phân chia cụm này được lặp lại và mỗi cụm lại tiếp tục được chia theo cùng tiêu -87- chuẩn. Hình 3.5 b) và a) có thể được quan sát như là snapshot của phân chia. Cuối cùng mỗi cụm sẽ chứa chỉ một đối tượng đơn. Trong phân cụm phân cấp tích đống hay phân ly, ta có thể chỉ định số lượng các cụm cần có như một điều kiện kết thúc để xử lý phân cụm phân cấp dừng khi xử lý tiến đến số lượng cụm cần thiết. Phương pháp phân cụm phân cấp mặc dầu đơn giản nhưng thường gặp khó khăn khi ra các quyết định tới hạn cho việc lựa chọn của các điểm hoà nhập hay phân chia một cách chính xác. Quyết định như vậy gọi là tới hạn bởi một khi một nhóm các đối tượng được hoà nhập hay chia, xử lý tại bước tiếp theo sẽ làm việc trên các cụm mới được sinh ra. Nó sẽ không bao giờ huỷ những gì đã làm trước đó và cũng không thực hiện chuyển đổi đối tượng giữa các cụm. Do vậy các quyết định hoà nhập hay phân chia nếu không đủ sáng suốt ở mỗi bước thì có thể dẫn tới chất lượng của các cụm sẽ kém. Hơn nữa, phương pháp này khả năng mở rộng không được tốt nên quyết định hoà nhập hay phân chia cần kiểm định và đánh giá một số lượng tốt các đối tượng hay các cụm. Một hướng hứa hẹn để cải thiện chất lượng phân cụm của phương pháp phân cấp là tích hợp phân cụm phân cấp với các kỹ thuật phân cụm khác để có phân cụm nhiều pha. Một vài phương pháp như vậy được giới thiệu trong các mục con dưới đây. Thứ nhất là BIRCH, trước tiên sử dụng cấu trúc cây để phân chia phân cấp các đối tượng, sau đó áp dụng các giải thuật phân cụm khác để hình thành nên các cụm cải tiến. Thứ hai là CURE, đại diện cho mỗi cụm là một số lượng nào đó các điểm đại diện đã được ấn định, sau đó co chúng lại về phía tâm cụm bởi một phân số đã chỉ định. Thứ ba là ROCK, hoà nhập các cụm dựa trên liên kết nối của chúng. Thứ tư là CHAMELEON, khảo sát mô hình hoá động trong phân cụm phân cấp. 3.5.2 BIRCH: Dùng các cấp, cân bằng giữa giảm số lần lặp và phân cụm Một phương pháp phân cụm phân cấp được tích hợp thú vị gọi là BIRCH (Balanced Iterative Reducing and Clustering using Hierachies) (Zhang, Ramakrishnan và Livny 1996). Nó đưa ra hai khái niệm: đặc trưng phân cụm -88- (CF - Clustering Feature) và cây CF (Clustering Feature tree), sử dụng cây CF đại diện một cụm tóm tắt để có được tốc độ và khả năng mở rộng phân cụm tốt trong các cơ sở dữ liệu lớn. Nó cũng tốt đối với phân cụm tăng trưởng động của các điểm dữ liệu đầu vào. Một đặc trưng phân cụm CF là một bộ ba thông tin tóm tắt về cụm con các điểm. Cho trước N điểm có hướng {Xi} trong một cụm con, CF được định nghĩa như sau: ),,( SSLSNCF = (3.23) với N là số các điểm trong cụm con, LS là tổng tuyến tính trên N điểm∑ =Ni iX1 r và SS là tổng bình phương của các điểm dữ liệu 21 iNi X∑ = r . Một cây CF là một cây cân bằng chiều cao, nó lưu trữ các đặc trưng phân cụm. Nó có hai tham số: hệ số phân nhánh B và ngưỡng T. Hệ số phân nhánh chỉ rõ số lượng tối đa các con. Tham số ngưỡng chỉ rõ đường kính tối đa của các cụm con được lưu trữ tại các nút lá. Bằng cách thay đổi giá trị ngưỡng, nó có thể thay đổi kích thước của cây. Các nút không phải là lá lưu trữ tổng các CFs của các nút con, do vậy, tóm tắt thông tin về các con của chúng. Giải thuật BIRCH có hai pha sau đây: • Pha 1: Quét cơ sở dữ liệu để xây dựng một cây CF bộ nhớ trong ban đầu, nó có thể được xem như là nén đa mức của dữ liệu mà nó cố gắng bảo toàn cấu trúc phân cụm vốn có của dữ liệu. • Pha 2: Áp dụng một giải thuật phân cụm (đã lựa chọn) để phân cụm các nút lá của cây CF. Trong pha 1, cây CF được xây dựng động khi các điểm dữ liệu được chèn vào. Do vậy, phương pháp này là một phương pháp tăng trưởng. Một điểm được chèn vào tới entry (cụm con) lá gần nhất. Nếu như đường kính của cụm con đã lưu trữ nút lá sau khi chèn lớn hơn giá trị ngưỡng, thì nút lá và các nút có thể khác bị chia. Sau khi chèn một điểm mới, thông tin về nó được đưa qua theo hướng gốc của cây. Ta có thể thay đổi kích thước cây CF bằng cách thay đổi -89- ngưỡng. Nếu như kích thước bộ nhớ cần thiết để lưu trữ cây CF là lớn hơn kích thước bộ nhớ chính thì một giá trị nhỏ hơn của ngưỡng được chỉ định và cây CF được xây dựng lại. Xử lý xây dựng lại này được biểu diễn bằng cách xây dựng một cây mới từ các nút lá của cây cũ. Do vậy, xử lý xây dựng lại cây được làm mà không cần đọc lại tất cả các điểm. Bởi vậy, để xây dựng cây, dữ liệu chỉ phải đọc một lần. Nhiều heuristic và các phương pháp cũng được giới thiệu để giải quyết các outlier và cải thiện chất lượng cây CF bởi các lần quét thêm vào của dữ liệu. Sau khi cây CF được xây dựng, bất kỳ một giải thuật phân cụm nào, ví dụ như giải thuật phân chia điển hình có thể được dùng với cây CF trong pha 2. BIRCH cố gắng đưa ra các cụm tốt nhất với các tài nguyên có sẵn. Với số lượng giới hạn của bộ nhớ chính, một xem xét quan trọng là cần tối thiểu hoá thời gian yêu cầu đối với I/O. Nó áp dụng kỹ thuật phân cụm nhiều pha: quét đơn tập dữ liệu mang lại một cơ sở phân cụm tốt, và một hay nhiều lần quét thêm vào (tuỳ ý) được dùng để cải thiện xa hơn chất lượng. Bởi vậy độ phức tạp tính toán của giải thuật là O(N), với N là số các đối tượng được phân cụm. Bằng các thử nghiệm đã thấy được khả năng mở rộng tuyến tính của giải thuật về mặt số lượng các điểm và chất lượng tốt của phân cụm dữ liệu. Tuy nhiên, mỗi nút trong cây CF có thể chỉ nắm giữ một số lượng giới hạn các entry bởi kích thước của nó, một nút cây CF không phải luôn luôn tương đương với một cụm tự nhiên. Hơn nữa, nếu các cụm không phải có hình cầu, BIRCH sẽ không thực hiện tốt bởi nó sử dụng khái niệm bán kính hay đường kính để điều khiển đường bao một cụm. 3.5.3 CURE: Phân cụm sử dụng các đại diện Hầu hết các giải thuật phân cụm hoặc là có ưu đãi các cụm có dạng hình cầu và kích thước giống nhau, hoặc là rất mong manh với sự hiện diện của các outlier. Một phương pháp thú vị gọi là CURE (Clustering Using REpresentatives) (Guha, Rastogi và Shim 1998), tích hợp các giải thuật phân -90- chia và phân cấp, khắc phục vấn đề ưu đãi các cụm có dạng hình cầu và kích thước giống nhau. CURE cung cấp một giải thuật phân cụm phân cấp mới lạ theo vị trí giữa (middle ground) giữa việc dựa trên trọng tâm và tất cả các cực điểm. Thay vì sử dụng một trọng tâm đơn đại diện một cụm, CURE ấn định một số lượng các điểm đại diện được lựa chọn để miêu tả một cụm. Các điểm đại diện này được sinh ra bằng cách trước tiên lựa chọn các điểm rải rác đều trong cụm, sau đó co chúng lại về phía tâm cụm bởi một phân số (hệ số co). Các cụm với cặp các điểm đại diện gần nhất sẽ được hoà nhập tại mỗi bước của giải thuật. Mỗi cụm có hơn một điểm đại diện cho phép CURE điểu chỉnh tốt hình học của các hình không phải hình cầu. Việc co lại giúp làm giảm đi hiệu quả của các outlier. Bởi vậy, CURE thực sự mạnh hơn đối với các outlier và nhận biết các cụm không có dạng hình cầu với kích thước khác nhau nhiều. Để vận dụng các cơ sở dữ liệu lớn, CURE dùng kết hợp lấy mẫu và phân chia ngẫu nhiên: Một mẫu ngẫu nhiên trước tiên được phân chia và mỗi phân chia được phân cụm cục bộ. Các cụm cục bộ sau đó được phân cụm lần thứ hai để có được các cụm mong muốn. Các bước chính của giải thuật CURE được phác hoạ vắn tắt như sau: (1) Lấy một mẫu ngẫu nhiên s; (2) Phân chia mẫu s thành p phần, mỗi phần có kích thước s/p; (3) Cụm cục bộ phân chia thành s/pq cụm q>1; (4) Khử các outlier bằng cách lấy mẫu ngẫu nhiên: Nếu một cụm tăng trưởng quá chậm, loại bỏ nó; (5) Phân cụm các cụm cục bộ, một xử lý co nhiều điểm đại diện về phía trọng tâm bằng một phân số α được chỉ định bởi người dùng, tại đó các đại diện có được hình dạng của cụm; (6) Đánh dấu dữ liệu với nhãn cụm tương ứng. Sau đây ta biểu diễn một ví dụ để thấy cách làm việc của CURE. Ví dụ 3.5: Giả sử có một tập các đối tượng được định vị trong một hình chữ nhật. Cho p = 2, người dùng cần phân cụm các đối tượng vào trong hai cụm. -91- Hình 3.6: Phân cụm một tập các điểm bằng CURE Trước tiên, 50 đối tượng được lấy mẫu như hình 3.6 a). Sau đó, các đối tượng này được phân chia ban đầu vào trong hai cụm, mỗi cụm chứa 50 điểm. Ta phân cụm cục bộ các phần chia này thành 10 cụm con dựa trên khoảng cách trung bình tối thiểu. Mỗi đại diện cụm được đánh dấu bởi một chữ thập nhỏ, như hình 3.6 b). Các đại diện này được di chuyển về phía trọng tâm bởi một phân số α, như hình 3.6 c).Ta có được hình dạng của cụm và thiết lập thành 2 cụm. Do vậy, các đối tượng được phân chia vào trong hai cụm với các outlier được gỡ bỏ như biểu diễn ở hình 3.6 d). CURE đưa ra các cụm chất lượng cao với sự hiện hữu của các outlier, các hình dạng phức tạp của các cụm với các kích thước khác nhau. Nó có khả năng mở rộng tốt cho các cơ sở dữ liệu lớn mà không cần hy sinh chất lượng phân cụm. CURE cần một ít các tham số được chỉ định bởi người dùng, như kích thước của mẫu ngẫu nhiên, số lượng các cụm mong muốn và hệ số co α. Độ nhạy một phép phân cụm được cung cấp dựa trên kết quả của việc thay đổi các tham số. Mặc dầu nhiều tham số bị thay đổi mà không ảnh hưởng tới chất lượng phân cụm nhưng tham số thiết lập nhìn chung có ảnh hưởng đáng kể. Một giải thuật phân cụm phân cấp tích đống khác được phát triển bởi (Guha, Rastogi và Shim 1999) gọi là ROCK, nó phù hợp cho việc phân cụm các thuộc tính xác thực. Nó đo độ tương đồng của 2 cụm bằng cách so sánh toàn bộ liên kết nối của 2 cụm dựa trên mô hình liên kết nối tĩnh được chỉ định bởi người dùng, tại đó liên kết nối của hai cụm C1 và C2 được định nghĩa bởi số -92- lượng các liên kết chéo giữa hai cụm và liên kết link(pi, pj) là số lượng các láng giềng chung giữa hai điểm pi và pj. ROCK trước tiên xây dựng đồ thị thưa từ một ma trận tương đồng dữ liệu cho trước, sử dụng một ngưỡng tương đồng và khái niệm các láng giềng chia sẻ, và sau đó biểu diễn một giải thuật phân cụm phân cấp trên đồ thị thưa. 3.5.4 CHAMELEON: Một giải thuật phân cụm phân cấp sử dụng mô hình động Một giải thuật phân cụm thú vị khác gọi là CHAMELEON, nó khảo sát mô hình hoá động trong phân cụm phân cấp, được phát triển bởi Karypis, Han và Kumar (1999). Khi xử lý phân cụm, 2 cụm được hoà nhập nếu liên kết nối và độ chặt (độ gần) giữa hai cụm được liên kết cao với liên kết nối và độ chặt nội tại của các đối tượng nằm trong phạm vi các cụm. Xử lý hoà nhập dựa trên mô hình động tạo điều kiện thuận lợi cho sự khám phá ra các cụm tự nhiên và đồng nhất, nó áp dụng cho tất cả các kiểu dữ liệu miễn là hàm tương đồng được chỉ định. CHAMELEON có được dựa trên quan sát các yếu điểm của hai giải thuật phân cụm phân cấp: CURE và ROCK. CURE và các lược đồ quan hệ bỏ qua thông tin về liên kết nối tổng thể của các đối tượng trong 2 cụm; ngược lại, ở ROCK, các lược đồ quan hệ lờ đi thông tin về độ chặt của 2 cụm trong khi nhấn mạnh liên kết nối của chúng. CHAMELEON trước tiên sử dụng một giải thuật phân chia đồ thị để phân cụm các mục dữ liệu vào trong một số lượng lớn các cụm con tương đối nhỏ. Sau đó dùng giải thuật phân cụm phân cấp tập hợp để tìm ra các cụm xác thực bằng cách lặp lại việc kết hợp các cụm này với nhau. Để xác định các cặp cụm con giống nhau nhất, cần đánh giá cả liên kết nối cũng như độ chặt của các cụm, đặc biệt là các đặc tính nội tại của bản thân các cụm. Do vậy nó không tuỳ thuộc vào một mô hình tĩnh được cung cấp bởi người dùng và có thể tự động thích ứng với các đặc tính nội tại của các cụm đang được hoà nhập. -93- Hình 3.7: CHAMELEON: Phân cụm phân cấp dựa trên k-láng giềng gần và mô hình hoá động Như hình 3.7, CHAMELEON miêu tả các đối tượng dựa trên tiếp cận đồ thị được dùng phổ biến: k-láng giềng gần nhất. Mỗi đỉnh của đồ thị k-láng giềng gần nhất đại diện cho một đối tượng dữ liệu, tại đó tồn tại một cạnh giữa hai đỉnh (đối tượng), nếu một đối tượng là giữa k đối tượng giống nhau so với các đối tượng khác. Đồ thị k-láng giềng gần nhất Gk có được khái niệm láng giềng động: Bán kính láng giềng của một điểm dữ liệu được xác định bởi mật độ của miền mà trong đó các đối tượng cư trú. Trong một miền dày đặc, láng giềng được định nghĩa hẹp, và trong một miền thưa thớt, láng giềng được định rộng hơn. So sánh với mô hình định nghĩa bởi phương pháp dựa trên mật độ như DBSCAN (giới thiệu ở mục sau), DBSCAN dùng mật độ láng giềng toàn cục, Gk có được láng giềng tự nhiên hơn. Hơn nữa, mật độ miền được ghi như trọng số của các cạnh. Cạnh của một miền dày đặc theo trọng số lớn hơn so với của một miền thưa thớt. CHAMELEON chỉ rõ sự tương đồng giữa mỗi cặp các cụm Ci và Cj theo liên kết nối tương đối RI(Ci,Cj) và độ chặt tương đối RC(Ci,Cj) của chúng. Liên kết nối tương đối RI(Ci,Cj) giữa hai cụm Ci và Cj được định nghĩa như liên kết nối tuyệt đối giữa Ci và Cj đã tiêu chuẩn hoá đối với liên kết nối nội tại của hai cụm Ci và Cj. Đó là: ( ) { }( ) ji ji CC CC ji ECEC EC CCRI + = 2 1, , (3.24) với { }ji CCEC , là cạnh cắt (edge-cut) của cụm chứa cả Ci và Cj để cụm này được rơi vào trong Ci và Cj, và tương tự như vậy, ECCi (hay ECCj) là kích thước -94- của min-cut bisector (tức là tổng trọng số của các cạnh mà chia đồ thị thành hai phần thô bằng nhau). Độ chặt tương đối giữa một cặp các cụm Ci và Cj là RC(Ci,Cj) được định nghĩa như là độ chặt tuyệt đối giữa Ci và Cj được tiêu chuẩn hoá đối với liên kết nối nội tại của hai cụm Ci và Cj. Đó là: ( ) { } jCiC ji EC ji j EC ji i CCEC ji S CC C S CC C S CCRC +++ = ,, (3.25) với { }jCiCECS , là trọng số trung bình của các cạnh kết nối các đỉnh trong Ci tới các đỉnh Cj và iCECS (hay jCECS ) là trọng số trung bình của các cạnh thuộc về min-cut bisecter của cụm Ci (hay Cj). Như vậy, CHAMELEON có nhiều khả năng khám phá ra các cụm có hình dạng tuỳ ý với chất lượng cao hơn so với DBSCAN và CURE. Tuy vậy, thời gian chi phí xử lý cho dữ liệu có chiều cao có thể là O(n2) cho n đối tượng trong tình huống xấu nhất. 3.6 Các phương pháp phân cụm dựa trên mật độ Để tìm ra các cụm với hình dạng tuỳ ý, các phương pháp phân cụm dựa trên mật độ đã được phát triển, nó kết nối các miền với mật độ đủ cao vào trong các cụm hay phân cụm các đối tượng dựa trên phân bố hàm mật độ. 3.6.1 DBSCAN: Phương pháp phân cụm dựa trên mật độ trên các miền có kết nối với mật độ đủ cao DBSCAN (Density-Based Spatial Clustering of Applications with Noise) là một giải thuật phân cụm dựa trên mật độ, được phát triển bởi Ester, Kriegel, Sander và Xu (1996). Giải thuật này tăng trưởng các miền với mật độ đủ cao vào trong các cụm và tìm ra các cụm với hình dạng tuỳ ý trong cơ sở dữ liệu không gian có nhiễu. Một cụm được định nghĩa như là một tập cực đại các điểm có kết nối dựa trên mật độ. -95- Ý tưởng cơ bản của phân cụm dựa trên mật độ như sau: Đối với mỗi đối tượng của một cụm, láng giếng trong một bán kính cho trước (ε) (gọi là ε -láng giềng) phải chứa chứa ít nhất một số lượng tối thiểu các đối tượng (MinPts). Một đối tượng nằm trong một bán kính cho trước (ε) chứa không ít hơn một số lượng tối thiểu các đối tượng láng giềng (MinPts), được gọi là đối tượng nòng cốt (core object) (đối với bán kính ε và số lượng tối thiểu các điểm MinPts). Một đối tượng p là mật độ trực tiếp tiến (directly density-reachable) từ đối tượng q với bán kính ε và số lượng tối thiểu các điểm MinPts trong một tập các đối tượng D nếu p trong phạm vi ε -láng giềng của q với q chứa ít nhất một số lượng tối thiểu các điểm MinPts. Một đối tượng p là mật độ tiến (density-reachable) từ đối tượng q với bán kính ε và MinPts trong một tập các đối tượng D nếu như có một chuỗi đối tượng p1,p2,...,pn, p1=q và pn=p với 1 ≤ i ≤ n, pi ∈ D và pi+1 là mật độ trực tiếp tiến từ pi đối với ε và MinPts. Một đối tượng p là mật độ liên kết với đối tượng q đối với ε và MinPts trong một tập đối tượng D nếu như có một đối tượng o ∈ D để cả p và q là mật độ tiến từ o đối với ε và MinPts. Ví dụ 3.6: Trong hình 3.8, ε cho trước đại diện cho bán kính các đường tròn, cho MinPts=3, M là mật độ trực tiếp tiến từ P; Q là mật độ (không trực tiếp) tiến từ P. Tuy nhiên P không phải là mật độ tiến từ Q. Tương tự như vậy, R và S là mật độ tiến từ O; và O, R và S tất cả là mật độ liên kết. Hình 3.8: Mật độ tiến và mật độ liên kết trong phân cụm dựa trên mật độ -96- Lưu ý rằng mật độ tiến là bắc cầu đóng (transitive closure) của mật độ trực tiếp tiến, và quan hệ này là không đối xứng. Chỉ các đối tượng nòng cốt là mật độ tiến lẫn nhau (giao hoán). Mật độ liên kết là một quan hệ đối xứng. Một cụm dựa trên mật độ là một tập các đối tượng mật độ liên kết là tối đa đối với mật độ tiến; mọi đối tượng không chứa trong bất kỳ một cụm nào là nhiễu. Dựa trên khái niệm mật độ tiến, giải thuật phân cụm dựa trên mật độ DBSCAN được phát triển để phân cụm dữ liệu trong cơ sở dữ liệu. Nó kiểm soát ε -láng giềng của mỗi điểm trong cơ sở dữ liệu. Nếu như ε -láng giềng của một điểm p chứa nhiều hơn MinPts, một cụm mới với p là đối tượng nòng cốt được thiết lập. Sau đó lặp lại việc tập hợp các đối tượng trực tiếp từ các đối tượng nòng cốt này, nó có thể bao gồm việc hoà nhập một vài cụm mật độ tiến. Xử lý này dừng khi không có điểm mới nào được thêm vào ở bất kỳ cụm nào. 3.6.2 OPTICS: Sắp xếp các điểm để nhận biết cấu trúc phân cụm Mặc dầu giải thuật phân cụm dựa trên mật độ DBSCAN có thể tìm ra cụm các đối tượng với việc lựa chọn các tham số đầu vào như ε và MinPts, người dùng vẫn chịu trách nhiệm lựa chọn các giá trị tham số tốt để tìm ra các cụm chính xác. Trên thực tế, đây là bài toán có sự kết hợp của nhiều giải thuật phân cụm khác. Các thiết lập tham số như vậy thường khá khó để xác định, đặc biệt trong thế giới thực, các tập dữ liệu số chiều cao. Hầu hết các giải thuật rất nhạy với các giá trị tham số: các thiết lập có sự khác biệt nhỏ có thể dẫn tới các phân chia dữ liệu rất khác nhau. Hơn nữa, các tập dữ liệu thực số chiều cao thường có phân bố rất lệch, thậm chí ở đó không tồn tại một thiết lập tham số toàn cục cho đầu vào, kết quả của một giải thuật phân cụm có thể mô tả bản chất cấu trúc phân cụm một cách chính xác. Để khắc phục khó khăn này, một phương pháp sắp xếp cụm gọi là OPTICS (Ordering Points To Identify the Clustering Structure) được phát triển bởi (Ankerst, Breunig, Kriegel và Sander 1999). Nó tính một sắp xếp phân cụm tăng dần cho phép phân tích cụm tự động và tương tác. Sắp xếp phân cụm này chứa -97- đựng thông tin tương đương với phân cụm dựa trên mật độ phù hợp với một phạm vi rộng các thiết lập tham số. Bằng cách khảo sát giải thuật phân cụm dựa trên mật độ, DBSCAN có thể dễ dàng thấy rằng đối với một giá trị hằng số MinPts, các cụm dựa trên mật độ đối với mật độ cao hơn (tức là một giá trị ε thấp hơn) được chứa hoàn toàn trong các tập mật độ liên kết đối với một mật độ thấp hơn. Bởi vậy, để đưa ra các cụm dựa trên mật độ với một tập các tham số khoảng cách, giải thuật cần lựa chọn các đối tượng để xử lý theo một trật tự cụ thể để đối tượng là mật độ tiến đối với giá trị ε thấp nhất được kết thúc trước tiên. Dựa trên ý tưởng này, hai giá trị cần được lưu trữ đối với mỗi đối tượng: khoảng cách nòng cốt (core-distance) và khoảng cách tiến (reachability- distance). Khoảng cách nòng cốt của một đối tượng p là khoảng cách nhỏ nhất ε' giữa p và một đối tượng trong ε - láng giềng của nó để p sẽ là một đối tượng nòng cốt đối với ε' nếu như láng giềng này được chứa trong ε - láng giềng của p. Nếu không thì khoảng cách nòng cốt là không xác định. Khoảng cách tiến của một đối tượng p đối với một đối tượng o khác là khoảng cách nhỏ nhất để p là mật độ trực tiếp tiến từ o nếu o là một đối tượng nòng cốt. Nếu o không phải là một đối tượng nòng cốt, ngay cả tại khoảng cách phát sinh ε, khoảng cách tiến của một đối tượng p đối với o là không xác định. Giải thuật OPTICS tạo lập trật tự của một cơ sở dữ liệu, thêm vào đó là lưu trữ khoảng cách nòng cốt và một khoảng cách tiến phù hợp với mỗi đối tượng. Thông tin như vậy là đủ cho sự rút trích của tất cả các phân cụm dựa trên mật độ đối với bất kỳ một khoảng cách ε' nhỏ hơn khoảng cách phát sinh ε từ trật tự này. Sắp xếp cụm của một tập dữ liệu có thể được trình bày và hiểu bằng đồ thị. Ví dụ, hình 3.9 là một biểu đồ tiến cho một tập dữ liệu hai chiều đơn giản, nó biểu diễn một cái nhìn tổng quát về dữ liệu được cấu trúc và phân cụm như thế -98- nào. Các phương pháp cũng được phát triển để quan sát các cấu trúc phân cụm cho dữ liệu số chiều cao. Hình 3.9: Sắp xếp cụm trong OPTICS Bởi tương đương cấu trúc của giải thuật OPTICS tới DBSCAN, giải thuật OPTICS có cùng độ phức tạp thời gian chạy như của DBSCAN. Các cấu trúc đánh chỉ số không gian có thể được dùng để nâng cao khả năng biểu diễn của nó. 3.6.3 DENCLUE: Phân cụm dựa trên các hàm phân bố mật độ DENCLUE (DENsity -based CLUstEring - phân cụm dựa trên mật độ) (Hinneburg và Keim 1998) là phương pháp phân cụm dựa trên một tập các hàm phân bố mật độ. Phương pháp được dựa trên ý tưởng sau: (1) Tác động của mỗi điểm dữ liệu có thể được làm mô hình chính thức sử dụng một hàm toán học gọi là hàm tác động, hàm tác động được xem như là một hàm mô tả tác động của một điểm dữ liệu trong phạm vi láng giềng của nó; (2) Toàn bộ mật độ của không gian dữ liệu có thể được làm mô hình theo phép phân tích tổng các hàm tác động của tất cả các điểm dữ liệu; (3) Các cụm sau đó có thể được xác định chính xác bằng cách nhận biết các attractor mật độ, tại đó các attractor mật độ cực đại cục bộ của toàn bộ hàm mật độ. Hàm tác động của một điểm dữ liệu y ∈ Fd, với Fd là một không gian đặc trưng d chiều, là một hàm cơ bản +→ 0: RFf dyB , được định nghĩa dưới dạng một hàm tác động cơ bản fB: -99- ( )yxff ByB ,= (3.26) Theo nguyên tắc, hàm tác động có thể là một hàm tuỳ ý nhưng nó nên là phản xạ và đối xứng. Nó có thể là một hàm khoảng cách Euclidean, một hàm tác động wave bình phương: ( ) ⎩⎨ ⎧ >= otherwise yxdif yxfSquare 1 ),(0 , σ (3.27) hay một hàm tác động Gaussian: ( ) 2 2 2 , ),( σ yxd Gause eyxf −= (3.28) Hình 3.10: Hàm mật độ và attractor mật độ Một hàm mật độ được định nghĩa là tổng các hàm tác động của tất cả các điểm dữ liệu. Cho trước N đối tượng dữ liệu được mô tả bởi một tập các vectơ đặc trưng D = {x1,...,xN} ⊂ FD, hàm mật độ được định nghĩa như sau: ( )∑ == Ni xBDB xff i1 (3.29) Ví dụ, hàm mật độ cho kết quả từ hàm tác động Gaussian (3.28) là: ( ) ∑ = −= Ni yxd D Gaussian exf 1 2 , 2 2 )( σ (3.30) Từ hàm mật độ, ta có thể định nghĩa độ dốc (gradient) của một hàm và attractor mật độ (attractor mật độ là cực đại cục bộ của toàn bộ hàm mật độ). Đối với một hàm tác động liên tục và phân biệt, một giải thuật leo đồi (hill climbing), được chỉ ra bởi độ dốc (gradient), có thể được dùng để xác định attractor mật độ của một tập các điểm dữ liệu. -100- Dựa trên các khái niệm này, cả cụm được định nghĩa trung tâm và cụm hình dạng tuỳ ý có thể được định nghĩa chính thức. Một cụm có định nghĩa trung tâm là một tập con C đang là mật độ được rút trích, với hàm mật độ không ít hơn một ngưỡng ξ, ngược lại (tức là nếu hàm mật độ nhỏ hơn ngưỡng ξ) thì nó là một outlier. Một cụm hình dạng tuỳ ý là một tập của tập con của C, mỗi tập đang là mật độ được rút trích, với hàm mật độ không ít hơn một ngưỡng ξ, và tồn tại một đường đi P từ mỗi miền tới những miền khác và hàm mật độ cho mỗi điểm dọc theo đường đi không ít hơn ξ. DENCLUE có các thuận lợi chính sau đây khi so sánh với các giải thuật phân cụm khác: (1) Nó có một nền tảng toán học vững chắc, tổng quát hoá các phương pháp phân cụm khác, bao gồm các phương pháp dựa trên phân chia, phân cấp và dựa trên vị trí; (2) Nó có các đặc tính phân cụm tốt đối với các tập dữ liệu với số lượng nhiễu lớn; (3) Nó cho phép một mô tả toán học cô đọng của các cụm có hình dạng tuỳ ý trong các tập dữ liệu số chiều cao; (4) Nó sử dụng các ô lưới nhưng chỉ giữ thông tin về các ô lưới mà thực sự chứa đựng các điểm dữ liệu và quản lý các ô này trong một cấu trúc truy cập dựa trên cây và do vậy nó nhanh hơn đáng kể so với các giải thuật tác động, như nó nhanh hơn DBSCAN tới 45 lần. Tuy vậy, phương pháp cần sự chọn lựa cẩn thận các tham số, tham số mật độ σ và ngưỡng nhiễu ξ, việc lựa chọn các tham số như vậy có ảnh hưởng đáng kể chất lượng của các kết quả phân cụm. Hình 3.11: Các cụm được định nghĩa trung tâm và các cụm có hình dạng tuỳ ý -101- 3.7 Các phương pháp phân cụm dựa trên lưới Một tiếp cận dựa trên lưới dùng cấu trúc dữ liệu lưới đa phân giải. Trước tiên nó lượng tử hoá không gian vào trong một số hữu hạn các ô mà đã hình thành nên cấu trúc lưới, sau đó thực hiện tất cả các thao tác trong cấu trúc lưới đó. Thuận lợi chính của tiếp cận này là thời gian xử lý nhanh, điển hình là độc lập của số lượng các đối tượng dữ liệu nhưng độc lập chỉ trên số lượng các ô trong mỗi chiều trong không gian lượng tử hóa. Các ví dụ điển hình của tiếp cận dựa trên lưới bao gồm STING - khảo sát thông tin thống kê được lưu trữ trong các ô lưới; WaveCluster - các cụm đối tượng sử dụng phương pháp biến đổi wavelet; CLIQUE - miêu tả một tiếp cận dựa trên lưới và mật độ cho phân cụm trong không gian dữ liệu số chiều cao. 3.7.1 STING: Một tiếp cận lưới thông tin thống kê STING (STatistical INformation Grid) (Wang, Yang và Munz 1997) là một tiếp cận đa phân giải dựa trên lưới. Trong tiếp cận này, miền không gian được chia thành các ô hình chữ nhật. Thường có một vài mức các ô hình chữ nhật tương ứng với các mức khác nhau của phân giải và các ô này thiết lập nên một cấu trúc phân cấp: mỗi ô tại một mức cao được phân chia để hình thành nên một số lượng các ô tại mức thấp hơn tiếp theo. Hơn nữa, các phần quan trọng của thông tin thống kê như mean, max, min, count, độ lệch chuẩn (standard deviation), v.v... đã kết hợp với các giá trị thuộc tính trong mỗi ô lưới được tính toán trước và được lưu trữ trước khi một truy vấn được submit tới một hệ thống. Hình 3.12 cho thấy một cấu trúc phân cấp đối với phân cụm STING. Hình 3.12: Một cấu trúc phân cấp đối với phân cụm STING -102- Tập các tham số dựa trên thống kê bao gồm: - tham số độc lập với thuộc tính n (count) và các tham số phụ thuộc thuộc tính m (mean), s (độ lệch chuẩn), min (minimum), max (maximum), và kiểu của phân bố mà giá trị thuộc tính trong ô tiếp theo như normal- bình thường, uniform-đồng nhất, exponential- số mũ, hay none (nếu phân bố không được biết). Khi dữ liệu được tải vào trong cơ sở dữ liệu, tập các tham số n, m, s, min, max của các ô mức đáy được tính toán trực tiếp từ dữ liệu. Giá trị của phân bố có thể được ấn định bởi người dùng nếu như kiểu phân bố không được biết trước hay có được bởi các kiểm định giả thuyết như kiểm định χ2. Các tham số của các ô mức cao hơn có thể dễ dàng được tính từ các tham số ở các ô mức thấp hơn. Kiểu phân bố của các ô mức cao hơn có thể được tính toán dựa trên các kiểu phân bố theo số đông của các ô tương đương mức thấp hơn của nó cộng với một ngưỡng xử lý lọc. Nếu như các phân bố của ô mức thấp hơn không giống nhau và thiếu ngưỡng kiểm định, kiểu phân bố của ô mức cao được đặt là "none". Thông tin thống kê có được sẽ rất hữu ích khi trả lời các truy vấn. Top- down là phương pháp trả lời truy vấn dựa trên lưới thông tin thống kê có thể khái quát như sau: Trước tiên nó có thể xác định một lớp để bắt đầu, nó thường bao gồm một số lượng nhỏ các ô. Đối với mỗi ô trong lớp hiện thời, ta tính toán khoảng tin cậy (hay phạm vi được đánh giá) khả năng mà ô này có liên quan tới truy vấn. Các ô không liên quan sẽ được gỡ bỏ khỏi xem xét sau này, và xử lý ở mức sâu hơn sẽ chỉ xem xét các ô liên quan. Xử lý này được lặp lại cho tới khi nó tiến đến lớp đáy. Tại thời điểm này, nếu đạt được truy vấn chỉ định thì sẽ trả lại các miền các ô liên quan đáp ứng yêu cầu của truy vấn; mặt khác, lấy ra dữ liệu nằm trong các ô liên quan, tiếp tục xử lý; và trả lại các kết quả thoả mãn yêu cầu của truy vấn. Tiếp cận này đưa ra một số thuận lợi so với các phương pháp phân cụm khác: (1) Tính toán dựa trên lưới là truy vấn độc lập, từ đó thông tin thống kê được lưu trữ trong mỗi ô đại diện cho thông tin tóm tắt của dữ liệu trong ô lưới, độc lập với truy vấn; (2) Cấu trúc lưới làm cho xử lý song song và cập nhật tăng -103- trưởng được thuận lợi; (3) Thuận lợi chủ yếu của phương pháp này hiệu quả của phương pháp: STING xuyên suốt dữ liệu một lần để tính toán các tham số thống kê của các ô, và do vậy độ phức tạp thời gian phát sinh các cụm là O(N), với N là tổng số các đối tượng. Sau khi phát sinh cấu trúc phân cấp này, thời gian xử lý truy vấn là O(G), với G là tổng số các ô lưới tại mức thấp nhất, nó thường nhỏ hơn nhiều so với N - tổng số các đối tượng. Tuy vậy, từ khi STING sử dụng tiếp cận đa phân giải để thực hiện phép phân tích cụm, chất lượng của phân cụm STING sẽ tuỳ thuộc vào độ sần (granularity) của mức thấp nhất của cấu trúc lưới. Nếu độ sần là rất tốt, chi phí xử lý về cơ bản sẽ tăng lên; tuy nhiên nếu như mức đáy của cấu trúc lưới quá thô, nó có thể giảm chất lượng tốt (độ mịn) của phép phân cụm. Hơn nữa, STING không xem xét mối quan hệ không gian giữa các ô con và các ô láng giềng của chúng để xây dựng các ô cha. Kết quả là hình dạng của các cụm kết quả là nhất quán (isothetic), tất cả các đường bao cụm theo chiều ngang hoặc theo chiều dọc, không có chiều chéo nào được dò thấy. Điều này có thể dẫn tới chất lượng và độ chính xác các cụm thấp hơn nhưng có thời gian xử lý nhanh hơn. 3.7.2 WaveCluster: Phân cụm sử dụng phép biến đổi wavelet WaveCluster (Sheikholeslami, Chatterjee và Zhang 1998) là một tiếp cận phân cụm đa phân giải, trước tiên tóm tắt dữ liệu bằng cách lợi dụng cấu trúc lưới đa phân giải trên không gian dữ liệu, sau đó biến đổi không gian đặc trưng gốc bằng phép biến đối wavelet và tìm các miền đông đúc trong không gian đã biến đổi. Trong tiếp cận này, mỗi ô lưới tóm tắt thông tin của một nhóm các điểm, thông tin tóm tắt này vừa đủ để đưa vào trong bộ nhớ chính cho phép biến đổi wavelet đa phân giải và phép phân tích cụm sau đó. Trong cấu trúc lưới, các thuộc tính số của một đối tượng không gian có thể được đại diện bởi một vectơ đặc trưng, tại đó mỗi phần tử của vectơ tương đương với một thuộc tính số, hay -104- đặc trưng. Cho một đối tượng với n thuộc tính số, vectơ đặc trưng sẽ là một điểm trong không gian đặc trưng n chiều. Phép biến đổi wavelet là một kỹ thuật xử lý tín hiệu, nó phân tích một tín hiệu vào trong các dải tần số con. Mô hình wavelet cũng làm việc trên các tín hiệu n chiều bằng cách áp dụng phép biến đổi 1 chiều n lần. Trong phép biến đổi wavelet, dữ liệu không gian được chuyển đổi vào trong miền tần số. Kết hợp với một hàm nòng cốt thích hợp cho kết quả trong một không gian biến đổi, tại đó các cụm tự nhiên trong dữ liệu trở nên dễ phân biệt hơn. Các cụm sau đó có thể được nhận biết bằng cách tìm ra các miền đông đúc trong vùng biến đổi. Phép biến đổi wavelet cung cấp các đặc trưng thú vị sau: Trước tiên nó cung cấp phân cụm không giám sát. Các lọc dạng nón làm nổi bật các miền mà tại đó các điểm phân cụm, nhưng đồng thời cũng có khuynh hướng ngăn chặn các thông tin yếu hơn trong đường bao của chúng. Do vậy, các miền đông đúc trong không gian đặc trưng gốc đóng vai trò như là các miền thu hút (attractor) đối với các điểm gần đó và như là miền hạn chế (inhibitor) đối với các điểm không đủ gần. Điều này nghĩa là các cụm trong dữ liệu tự động nổi bật lên và làm sạch các miền xung quanh chúng. Thứ hai, các lọc thông thấp được dùng trong phép biến đổi wavelet sẽ tự động loại bỏ các outlier. Hơn nữa, đặc tính đa phân giải của phép biến đổi wavelet có thể giúp dò các cụm tại các độ chính xác khác nhau. Cuối cùng, ứng dụng phép biến đổi wavelet là rất nhanh và việc xử lý như vậy có thể cũng được thực hiện song song. Giải thuật phân cụm dựa trên wavelet phác thảo như sau: Giải thuật 3.7.1: Giải thuật phân cụm dựa trên wavelet đối với phân cụm đa phân giải bằng phép biến đổi wavelet. Đầu vào: Các vectơ đặc trưng của các đối tượng dữ liệu đa chiều Đầu ra: Các đối tượng đã phân cụm Giải thuật: 1) Lượng tử hoá không gian đặc trưng, sau đó phân các đối tượng vào các -105- unit; 2) Áp dụng phép biến đổi wavelet trong không gian đặc trưng; 3) Tìm các phần hợp thành đã kết nối (các cụm) trong các dải con của không gian đặc trưng đã biến đổi tại các mức khác nhau; 4) Gắn các nhãn vào các unit; 5) Làm các bảng tra cứu và ánh xạ các đối tượng vào các cụm. Hình 3.13: Giải thuật phân cụm dựa trên wavelet Độ phức tạp tính toán của giải thuật này là O(N) với N là số các đối tượng trong cơ sở dữ liệu. Hình 3.14: Một mẫu không gian đặc trưng 2 chiều Ví dụ: Hình 3.14 (lấy từ Sheikholeslami, Chatterjee và Zhang (1998)) cho thấy một mẫu không gian đặc trưng 2 chiều, tại đó, mỗi điểm trong ảnh đại diện cho các giá trị đặc trưng của một đối tượng trong các tập dữ liệu không gian. Hình 3.15 (lấy từ Sheikholeslami, Chatterjee và Zhang (1998)) cho thấy kết quả của các phép biến đổi wavelet tại các tỷ lệ khác nhau, từ mịn (tỷ lệ 1) cho tới thô (tỷ lệ 3). Tại mỗi mức, dải con LL (bình thường) chỉ ra tại cung phần tư phía trên bên trái, dải con LH (các cạnh nằm ngang) chỉ ra tại cung phần tư phía trên bên phải và dải con HL (các cạnh nằm dọc) chỉ ra tại cung phần tư phía dưới bên trái và dải con HH (các góc) chỉ ra tại cung phần tư phía dưới bên phải. WaveCluster là một giải thuật dựa trên mật độ và lưới. WaveCluster thích hợp với tất cả các yêu cầu của các giải thuật phân cụm tốt: nó xử lý các tập dữ liệu lớn một cách hiệu quả, tìm ra các cụm với hình dạng tuỳ ý, thành công trong việc xử lý các outlier, và không nhạy cảm đối với trật tự đầu vào. So với -106- BIRCH, CLARANS và DBSCAN, WaveCluster làm tốt hơn các phương pháp này ở cả hiệu suất và chất lượng phân cụm. Hình 3.15: Đa phân giải của không gian đặc trưng trong hình 3.14. a) tỷ lệ 1; b) tỷ lệ 2; c) tỷ lệ 3 3.7.3 CLIQUE: Phân cụm không gian số chiều cao Một giải thuật phân cụm khác, CLIQUE, Agrawal et al. (1998), tích hợp phương pháp phân cụm dựa trên lưới và mật độ theo một cách khác. Nó rất hữu ích cho phân cụm dữ liệu với số chiều cao trong các cơ sở dữ liệu lớn. Cho trước một tập lớn các điểm dữ liệu đa chiều, các điểm dữ liệu này thường nằm không đồng nhất trong không gian dữ liệu. Phân cụm dữ liệu nhận biết các vị trí thưa thớt hay đông đúc, do vậy tìm ra toàn bộ các mẫu phân bố của tập dữ liệu. Một unit là dày đặc nếu như phần nhỏ của các điểm dữ liệu chứa trong unit vượt quá một tham số mô hình đầu vào. Một cụm là một tập lớn nhất các unit dày đặc có kết nối. CLIQUE phân chia không gian dữ liệu m chiều thành các unit hình chữ nhật không chồng lên nhau, nhận biết các unit dày đặc, và tìm ra các cụm trong toàn bộ các không gian con của không gian dữ liệu gốc, sử dụng phương pháp phát sinh candidate (ứng cử) giống với giải thuật Apriori cho khai phá các luật kết hợp. CLIQUE thực hiện phân cụm đa chiều theo hai bước: Trước tiên, CLIQUE nhận biết các cụm bằng cách xác định các unit dày đặc trong toàn bộ các không gian con của các interest và sau đó xác định các unit dày đặc có kết nối trong toàn bộ các không gian con của các interest. -107- Một heuristic quan trọng mà CLIQUE thông qua đó là nguyên lý Apriori trong phân cụm số chiều cao: Nếu một unit k chiều là dày đặc thì các hình chiếu (project) của nó trong không gian (k-1) chiều cũng vậy. Đó là nếu bất kỳ unit thứ (k-1) không phải là dày đặc, thì unit thứ k tương ứng của nó không phải là một unit ứng cử dày đặc (candidate dense). Bởi vậy, tất cả các unit dày đặc k chiều ứng cử có thể được sinh từ các unit dày đặc (k-1) chiều. Thứ hai, CLIQUE sinh ra mô tả tối thiểu cho các cụm như sau: Trước tiên nó xác định các miền tối đa phủ một cụm các unit dày đặc có kết nối cho mỗi cụm và sau đó xác định phủ tối thiểu cho mỗi cụm. CLIQUE tự động tìm các không gian con số chiều cao nhất để các cụm mật độ cao tồn tại trong các không gian con này. Nó không nhạy cảm với trật tự các bản ghi trong đầu vào và không đoán được phân bố dữ liệu tiêu chuẩn. Nó tỷ lệ tuyến tính với kích thước của đầu vào và có một khả năng mở rộng tốt như số các chiều trong dữ liệu được tăng lên. Tuy nhiên, độ chính xác của kết quả phân cụm có thể bị suy giảm tại phụ phí bởi tính đơn giản của phương pháp. 3.8 Kết luận Chương này đề cập tới các phương pháp phân cụm truyền thống và các cải tiến phương pháp phân cụm truyền thống. Ngoài ra chương này còn đề cập tới khái niệm độ không tương đồng (hay tương đồng) của các đối tượng. Qua đó ta có thể thấy được khả năng phân cụm của từng phương pháp, khả năng áp dụng vào các bài toán thực tiễn. -108- CHƯƠNG 4: CÀI ĐẶT THỬ NGHIỆM Chương này đưa ra kết quả cài đặt thử nghiệm bằng các giải thuật Kmeans và Kmedoids trên các bộ dữ liệu của UCI và đánh giá kết quả thực nghiệm. 4.1 Thiết kế tổng thể Chương trình gồm các khối chức năng chính sau: - Khối chức năng tiền xử lý - Khối chức năng phân cụm 4.1.1 Khối chức năng tiền xử lý Nhiệm vụ của khối chức năng này là đọc dữ liệu, xác định số mẫu, số thuộc tính, số lớp, các giá trị thuộc tính của từng mẫu dữ liệu. 4.1.2 Khối chức năng phân cụm Khối chức năng này tiến hành phân cụm các mẫu dữ liệu. Dữ liệu được học không giám sát (unsupervised learning) theo hai giải thuật khác nhau: Kmeans và Kmedoids. Cuối cùng gắn nhãn lớp cho các cụm. Sau khi gắn nhãn lớp cho các cụm sẽ tiến hành xác định hiệu quả phân lớp, phân loại. 4.2 Chuẩn bị dữ liệu Dữ liệu đầu vào chương trình là các tệp văn bản và được chia thành hai loại: - Tệp định dạng dữ liệu (*.names): Định nghĩa tên các lớp, tên các thuộc tính, các giá trị của từng thuộc tính, kiểu thuộc tính. - Tệp mẫu dữ liệu (*.data): Gồm các mẫu dữ liệu chứa đầy đủ thông tin giá trị các thuộc tính và giá trị lớp. 4.2.1 Tệp định dạng dữ liệu - Dòng 1: liệt kê các giá trị lớp. Các giá trị này cách nhau bởi dấu phẩy "," và kết thúc bằng dấu chấm ".". - Từ dòng 2: + Mỗi mẫu một dòng -109- + Bắt đầu bằng tên một thuộc tính, dấu ":", sau đó là các giá trị rời rạc của thuộc tính (nếu thuộc tính là xác thực hay nhị phân) hoặc kiểu thuộc tính (nếu thuộc tính có kiểu liên tục). - Tất cả các phần chú thích được đặt sau dấu "|" Bảng 4.1: Một ví dụ tệp định dạng dữ liệu *.names 1, 2, 3. 1: continuous. 2: 1, 2, 3, 4. |categorical 3: continuous. 4: 0, 1. |binary 4.2.2 Tệp mẫu dữ liệu Mỗi mẫu một dòng. Các giá trị thuộc tính của mẫu ghi trước, cuối cùng là giá trị lớp. Mỗi một giá trị này cách nhau bởi dấu ",". Bảng 4.2: Một ví dụ tệp dữ liệu *.data 4.2.3 Nguồn dữ liệu Trong khuôn khổ luận văn, dữ liệu được lấy từ địa chỉ web site: - ftp://ftp.ics.uci.edu/pub/ 4.3 Thiết kế chương trình Với các khối chức năng và dữ liệu ở trên, chương trình được thiết kế như sau: 0,0,1,0,0,1,1,1,1,0,0,1,0,1,0,1,4 0,0,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1 0,1,1,0,1,0,0,0,1,1,0,0,2,1,1,0,2 0,1,1,0,1,1,0,0,1,1,0,0,2,1,0,0,2 1,0,0,1,0,0,0,1,1,1,0,0,4,1,0,1,1 0,1,1,0,1,0,0,0,1,1,0,0,2,1,0,1,2 -110- Hình 4.1: Thiết kế chương trình 4.4 Kết quả thực nghiệm và đánh giá 4.4.1 Các bước tiến hành thực nghiệm - Phân cụm dữ liệu bằng giải thuật Kmeans và Kmedoids - Gắn nhãn cho các cụm, đánh giá, so sánh hiệu quả gắn nhãn giữa hai giải thuật trên cho các bộ số liệu UCI (chỉ dùng các dữ liệu có thuộc tính liên tục). - Gắn nhãn cho các cụm, đánh giá hiệu quả gắn nhãn cho dữ liệu có thuộc tính hỗn hợp - Cải tiến hiệu quả phân lớp - So sánh chất lượng phân loại với chương trình See5. Chương trình See5 (phiên bản 2.03) là công cụ sử dụng kỹ thuật cây quyết định với giải thuật C5.0 dùng để phân loại dữ liệu được viết bởi Ross Quinlan. Tính hiệu quả của chương trình này đã được nhiều người công nhận. Vì thế, luận văn đã sử dụng nó làm công cụ để so sánh với các kết quả phân loại đã thực hiện. Hạn chế của See5 (phiên bản 2.03) chỉ dùng được tối đa 400 mẫu dữ liệu. Tệp định dạng dữ liệu Module GetNames Tệp mẫu dữ liệu Module GetData Các thông tin: - Số lớp, tên các lớp - Số thuộc tính, tên thuộc tính, kiểu thuộc tính hay các giá trị rời rạc của thuộc tính - Số mẫu, giá trị các thuộc tính và tên lớp của mỗi mẫu Các module phân cụm Phân loại Phân lớp Hiển thị kết quả Kết quả phân lớp, phân loại Cải tiến phân lớp -111- 4.4.2 Thực nghiệm Dưới đây là các kết quả đạt được: 4.4.2.1 Bài toán phân lớp: được thực hiện với số lượng các cụm là K = 2, 4, 6,8,10, 16. (Kmeans: ma; Kmedoids: md) Bảng 4.3: Kết quả thí nghiệm phân lớp Số mẫu phân lớp đúng K=2 K=4 K=6 K=8 K=10 K=16 Tên DL Số mẫu ma md ma md ma md ma md ma md ma md Brea 500 328 480 485 481 484 481 481 482 481 482 481 482 Haber 306 225 225 229 226 230 231 228 232 233 234 237 240 Iris 150 100 51 126 53 126 55 125 57 121 59 142 65 Pima 768 532 504 539 537 541 528 525 554 554 558 558 561 Glass 214 78 82 105 84 117 86 117 88 125 90 140 96 Wine 178 107 72 173 80 169 85 168 84 166 87 173 93 Balan 625 293 369 407 423 448 441 503 451 438 453 483 459 So sánh Kmeans và Kmedoids 0 20 40 60 80 100 120 bre as tca nc el ha be rm an iris pim a gla ss win e ba lan ce Các bộ dữ liệu P hầ n tr ăm p hâ n lớ p đú ng Kmeans Kmedoids Hình 4.2: Biểu đồ so sánh Kmeans và Kmedoids trong bài toán phân lớp với K=10 Biểu đồ trên cho thấy với dữ liệu kiểu liên tục khả năng phân lớp của Kmedoids trong bộ dữ liệu UCI thường thấp hơn so với Kmeans bởi điểm đại diện trong Kmedoids là một điểm đối tượng gần tâm cụm, tâm cụm trong -112- Kmeans là giá trị trung bình của các phần tử trong cụm. Nếu như dữ liệu ít nhiễu thì Kmeans sẽ cho kết quả hiệu quả hơn Kmedoids, trong trường hợp ngược lại, nếu một nhiễu với giá trị cực lớn, về cơ bản nó sẽ bóp méo phân bố dữ liệu nếu như dùng Kmeans, lúc này dùng Kmeadoids sẽ hiệu quả hơn. Theo biểu đồ so sánh ở trên ta nhận thấy dữ liệu ít nhiễu. Tuy nhiên, phép đo độ tương đồng của các đối tượng trong Kmedoids dường như chưa được hiệu quả lắm, do vậy phần trăm phân lớp đúng chưa được cao. Để cải thiện độ chính xác phân lớp, luận văn đưa ra phương pháp sau: Với mỗi mẫu bị phân lớp sai trong mỗi cụm, ta sẽ đưa nó vào cụm thích hợp (giả sử là cụm A) nếu thoả mãn điều kiện: + Khoảng cách từ nó tới cụm hiện thời bằng khoảng cách tới cụm A + Nhãn lớp cụm A giống nhãn lớp của mẫu đó + Nếu thêm mẫu này vào cụm A, tâm cụm không thay đổi (hoặc thay đổi một khoảng cách epsilon đủ bé cho trước). Thực nghiệm cho thấy độ chính xác phân lớp đã được tăng lên. Ví dụ ở một số bộ dữ liệu sau: (Cũ: C; Mới: M) Bảng 4.4: Kết quả cải thiện chất lượng phân lớp Tên DL Iris Wine Balance Haberman C 53 80 423 226 K=4 M 54 89 447 226 C 55 85 441 231 K=6 M 57 85 459 231 C 57 84 451 232 K=8 M 61 86 475 233 C 59 87 453 234 K=10 M 65 90 477 237 C 65 93 459 240 K=16 M 77 102 483 249 C 69 97 463 244 K=20 M 85 110 487 257 C 74 102 468 249 K=25 M 95 120 492 267 -113- 4.4.2.2 Bài toán phân loại Bảng 4.5: Kết quả thí nghiệm phân loại của Kmeans và Kmedoids Số mẫu phân loại đúng Tỷ lệ phân loại đúng (%) Tên dữ liệu Số mẫu ma md ma md Breastcancel 500 318 480 63.6 96 Haberman 306 179 115 58.4967 50.6536 Iris 150 125 52 83.3333 34.6667 Pima 768 532 504 69.2708 65.625 Glass 214 93 72 43.4579 33.6449 Soybean 47 32 22 68.0851 46.8085 Wine 178 172 70 96.6292 39.3258 Balance 625 313 336 50.08 53.76 So sánh Kmeans và Kmedoids 0 20 40 60 80 100 120 bre as tca nc el ha be rm an iris pim a gla ss so yb ea n win e ba lan ce Các bộ dữ liệu Ph ần tr ăm p hâ n lo ại đ ún g Kmeans Kmedoids Hình 4.3: Biểu đồ so sánh Kmeans và Kmedoids trong bài toán phân loại Bảng 4.6: Kết quả thí nghiệm phân loại của Kmedoids và See5 Số mẫu phân loại đúng Tỷ lệ phân loại đúng (%) Tên dữ liệu Số mẫu See5 md See5 md Breastcancel 400 391 344 97.75 86 Haberman 306 236 115 77.12418 50.6536 -114- Iris 150 106 52 83.3333 34.6667 Pima 400 307 262 76.75 65.5 Car 298 289 202 72.25 67.7852 Balance 400 336 238 84 64.8501 So sánh Kmedoids và See5 0 20 40 60 80 100 120 Br ea stc an ce l Ha be rm an Iris Pim a Ca r Ba lan ce Các bộ dữ liệu P hầ n tră m p hâ n lo ại đ ún g Kmedoids See5 Hình 4.4: Biểu đồ so sánh Kmedoids và See5 trong bài toán phân loại Theo biểu đồ trên ta nhận thấy hiệu quả phân loại của See5 tốt hơn bởi nó có một mô hình phân loại dạng cây thực sự hiệu quả, mô hình này đã hạn chế được những nhánh phản ánh nhiễu nên chất lượng phân loại cao. Còn Kmedoids tuy đã xử lý được dữ liệu kiểu hỗn hợp nhưng chất lượng tính độ tương đồng của các đối tượng chưa cao nên khả năng phân loại kém hơn See5. 4.5 Kết luận Như vậy, sau khi tiến hành thực nghiệm trên một số bộ dữ liệu của UCI ta nhận thấy kết quả phân lớp, phân loại các dữ liệu có thuộc tính liên tục của Kmeans tốt hơn so với Kmedoids. Với dữ liệu có thuộc tính hỗn hợp, Kmeans không xử lý được. Kmedoids với phương pháp tính độ tương đồng giữa hai mẫu do Ducker (1965) đề xuất, Kaufman và Rousseeuw cải tiến (1990) đã xử lý được dữ liệu này với độ chính xác trên trung bình và chi phí tính toán là O(k(n-k)2). -115- Đối với các giá trị n và k lớn, chi phí như vậy sẽ cao. Vậy nên việc cải tiến độ chính xác và tốc độ tính toán là hướng phát triển sau này. -116- KẾT LUẬN Luận văn tập trung nghiên cứu lý thuyết và áp dụng một số kỹ thuật khai phá dữ liệu trên bộ dữ liệu của UCI. Đây là bước khởi đầu trong quá trình tìm hiểu những vấn đề cần quan tâm khi giải quyết các bài toán khai phá dữ liệu trong thực tế. Trong khuôn khổ luận văn chưa áp dụng cụ thể vào một CSDL thực tế nào, mới chỉ dừng lại trên bộ dữ liệu UCI nên kết quả thực nghiệm chưa mang ý nghĩa thực tế. Tuy nhiên cũng có một số kết quả ban đầu là phát hiện tri thức từ bộ dữ liệu này. Những kết quả mà luận văn đã thực hiện: + Về lý thuyết, luận văn tập trung tìm hiểu các kỹ thuật phân loại, phân cụm truyền thống và các phương pháp cải tiến chúng. + Về thực tiễn, luận văn đã đưa ra các kết quả cài đặt thử nghiệm trên bộ dữ liệu UCI bao gồm các kết quả phân loại, phân lớp, cải tiến chất lượng phân lớp. Qua quá trình thực nghiệm và nghiên cứu lý thuyết có thể đưa ra một số kết luận như sau: • Mỗi một giải thuật phân loại, phân cụm áp dụng cho một số mục tiêu và kiểu dữ liệu nhất định. • Mỗi giải thuật có một mức độ chính xác riêng và khả năng thực hiện trên từng kích thước dữ liệu là khác nhau. Điều này còn tuỳ thuộc vào cách thức tổ chức dữ liệu ở bộ nhớ chính, bộ nhớ ngoài... của các giải thuật. • Khai phá dữ liệu sẽ hiệu quả hơn khi bước tiền xử lý, lựa chọn thuộc tính, mô hình được giải quyết tốt. Với những gì mà luận văn đã thực hiện, các hướng phát triển sau này của luận văn như sau: -117- • Độ chính xác phân lớp, phân loại phụ thuộc vào nhiều yếu tố như chất lượng dữ liệu, thuật toán cài đặt, phương pháp tính độ tương đồng của các đối tượng dữ liệu. Ngoài ra, các giá trị khuyết hay các thuộc tính dư thừa cũng phần nào làm ảnh hưởng đến chúng. Vì vậy hướng phát triển sau này là xử lý các giá trị khuyết, phát hiện và loại bỏ các thuộc tính dư thừa, cải tiến phương pháp tính độ tương đồng,... nhằm nâng cao chất lượng và tốc độ phân lớp, phân loại. • Tiến hành cài đặt và tiếp tục nghiên cứu nhiều kỹ thuật khai phá dữ liệu hơn nữa, đặc biệt là triển khai giải quyết các bài toán cụ thể trong thực tế. -118- TÀI LIỆU THAM KHẢO 1. Anil K. Jain and Richard C. Dubes (1988), Algorithms for clustering data, Prentice-Hall, Inc., USA. 2. Ho Tu Bao (1998), Introduction to knowledge discovery and data mining. 3. Jiawei Han and Micheline Kambel (2000), Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers. 4. Joydeep Ghosh (2003), Scalable Clustering, Chapter 10, pp. 247-278, Formal version appears in: The Handbook of Data Mining, Nong Ye (Ed). 5. J.Ross Quinlan (1993), C4.5: Programs for Machine Learning, Morgan Kaufmann Publishers. 6. Mercer (2003), Clustering large datasets, Linacre College. 7. Pavel Berkhin, Survey of Clustering Data Mining Techniques. Accrue Software, Inc., San Jose.