Luận văn Phương pháp phân cụm và ứng dụng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN  Nguyễn Trung Sơn PHƢƠNG PHÁP PHÂN CỤM VÀ ỨNG DỤNG 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 NGƯỜI HƯỚNG DẪN KHOA HỌC 1. PGS. TS VŨ ĐỨC THI Thái Nguyên – 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN  Nguyễn Trung Sơn PHƢƠNG PHÁP PHÂN CỤM VÀ ỨNG DỤNG 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 NGƯỜI HƯỚNG DẪN KHOA HỌC 1. PGS. TS VŨ ĐỨC THI Thái Nguyên – 2009 -2- MỤC LỤC TRANG LỜI CẢM ƠN 5 LỜI MỞ ĐẦU 6 CHƢƠNG I : TỔNG QUAN THUYẾT VỀ PHÂN CỤM DỮ LIỆU 7 1. Phân cụm dữ liệu 7 1.1 Định nghĩa về phân cụm dữ liệu 7 1.2 Một số ví dụ về phân cụm dữ liệu 7 2. Một số kiểu dữ liệu 10 2.1 Dữ liệu Categorical 10 2.2 Dữ liệu nhị phân 13 2.3 Dữ liệu giao dịch 14 2.4 Dữ liệu Symbolic 15 2.5 Chuỗi thời gian(Time Series) 16 3. Phép Biến đổi và Chuẩn hóa dữ liệu 16 3.1 Phép chuẩn hóa dữ liệu 17 3.2 Biến đổi dữ liệu 21 3.2.1 Phân tích thành phần chính 21 3.2.2 SVD 23 3.2.3 Phép biến đổi Karhunen-Loève 24 CHƢƠNG II. CÁC THUẬT TOÁN PHÂN CỤM DỮ LIỆU 28 1. Thuật toán phân cụm dữ liệu dựa vào phân cụm phân cấp 28 1.1 Thuật toán BIRCH 28 1.2 Thuật toán CURE 30 1.3 Thuật toán ANGNES 32 1.4 Thuật toán DIANA 33 1.5 Thuật toán ROCK 33 1.6 Thuật toán Chameleon 34 -3- 2. Thuật toán phân cụm dữ liệu mờ 35 2.1 Thuật toán FCM 36 2.2 Thuật toán εFCM 37 3. Thuật toán phân cụm dữ liệu dựa vào cụm trung tâm 37 3.1 . Thuật toán K – MEANS 37 3.2 Thuật toán PAM 41 3.3 Thuật toán CLARA 42 3.4 Thuật toán CLARANS 44 4. Thuật toán phân cụm dữ liệu dựa vào tìm kiếm 46 4.1 Thuật toán di truyền (GAS) 46 4.2 J- Means 48 5. Thuật toán phân cụm dữ liệu dựa vào lƣới 49 5.1 STING 49 5.2. Thuật toán CLIQUE 51 5.3. Thuật toán WaveCluster 52 6. Thuật toán phân cụm dữ liệu dựa vào mật độ 53 6.1 Thuật toán DBSCAN 53 6.2. Thuật toán OPTICS 57 6.3. Thuật toán DENCLUDE 58 7. Thuật toán phân cụm dữ liệu dựa trên mẫu 60 7.1 Thuật toán EM 60 7.2 Thuật toán COBWEB 61 CHƢƠNG III :ỨNG DỤNG CỦA PHÂN CỤM DỮ LIỆU 62 1. Phân đoạn ảnh 62 1.1. Định nghĩa Phân đoạn ảnh 63 1.2 Phân đoạn ảnh dựa vào phân cụm dữ liệu 65 2. Nhận dạng đối tƣợng và ký tự 71 2.1 Nhận dạng đối tượng 71 -4- 2.2 Nhận dạng ký tự. 75 3. Truy hồi thông tin 76 3.1 Biểu diễn mẫu 78 3.2 Phép đo tương tự 79 3.3 Một giải thuật cho phân cụm dữ liệu sách 80 4. Khai phá dữ liệu 81 4.1 Khai phá dữ liệu bằng Phương pháp tiếp cận. 82 4.2 Khai phá dữ liệu có cấu trúc lớn. 83 4.3 Khai phá dữ liệu trong Cơ sở dữ liệu địa chất. 84 4.4 Tóm tắt 86 KẾT LUẬN ,HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI 90 PHỤ LỤC 91 TÀI LIỆU THAM KHẢO 99 -5- LỜI CẢM ƠN Em xin chân thành cảm ơn PGS. TS Vũ Đức Thi đã tận tình hướng dẫn khoa học, giúp đỡ em hoàn thành tốt luận văn tốt nghiệp này. Em cũng xin gửi lời cảm ơn tới các thầy, cô giáo đã dạy dỗ, và truyền đạt kiến thức cho em trong suốt quá trình học tập và nghiên cứu HỌC VIÊN NGUYỄN TRUNG SƠN -6- LỜI MỞ ĐẦU Trong những năm gần đây, sự phát triển mạnh mẽ của CNTT đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó, việc tin học hóa một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ khổng lồ. Hàng triệu CSDL đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lý..., trong đó có nhiều CSDL cực lớn cỡ Gigabyte, thậm chí là Terabyte. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích. Từ đó, các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền CNTT thế giới hiện nay nói chung và Việt Nam nói riêng. Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau: marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet… Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích to lớn. Các kỹ thuật khai phá dữ liệu thường được chia thành 2 nhóm chính: - Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. - Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Bản luận văn này trình bày một số vấn đề về Phân cụm dữ liệu, một trong những kỹ thuật cơ bản để Khai phá dữ liệu. Đây là hướng nghiên cứu có triển vọng chỉ ra những sơ lược trong việc hiểu và khai thác CSDL khổng lồ, khám phá thông tin hữu ích ẩn trong dữ liệu; hiểu được ý nghĩa thực tế của dữ liệu. Luận văn đƣợc trình bày trong 3 chƣơng và phần phụ lục : Chương 1 : Trình bày tổng quan lý thuyết về Phân cụm dữ liệu, các kiểu dữ liệu, Phép biến đổi và chuẩn hóa dữ liệu. Chương 2 : Giới thiệu, phân tích, đánh giá các thuật toán dùng để phân cụm dữ liệu Chương 3 : Trình bày một số ứng dụng tiêu biểu của phân cụm dữ liệu. Kết luận : Tóm tắt các vấn đề được tìm hiểu trong luận văn và các vấn đề liên quan trong luận văn, đưa ra phương hướng nghiên cứu tiếp theo. -7- CHƢƠNG I : TỔNG QUAN LÝ THUYẾT VỀ PHÂN CỤM DỮ LIỆU 1. Phân cụm dữ liệu 1.1 Định nghĩa về phân cụm dữ liệu Phân cụm dữ liệu(Data Clustering) hay phân cụm, cũng có thể gọi là phân tích cụm, phân tích phân đoạn, phân tích phân loại, là quá trình nhóm một tập các đối tượng thực thể hay trừu tượng thành lớp các đối tượng tương tự. Một cụm là một tập hợp các đối tượng dữ liệu mà các phần tử của nó tương tự nhau cùng trong một cụm và phi tương tự với các đối tượng trong các cụm khác. Một cụm các đối tượng dữ liệu có thể xem như là một nhóm trong nhiều ứng dụng. 1.2 Một số ví dụ về phân cụm dữ liệu 1.2.1 Phân cụm dữ liệu phục vụ cho biểu diễn dữ liệu gene Phân cụm là một trong những phân tích được sử dụng thường xuyên nhất trong biểu diễn dữ liệu gene (Yeung et al., 2003; Eisen at al., 1998). Dữ liệu biểu diễn gene là một tâp hợp các phép đo được lấy từ DNA microarray (còn gọi là DNA chip hay gene chip) là một tấm thủy tinh hoặc nhựa trên đó có gắn các đoạn DNA thành các hàng siêu nhỏ. Các nhà nghiên cứu sử dụng các con chip như vậy để sàng lọc các mẫu sinh học nhằm kiểm tra sự có mặt hàng loạt trình tự cùng một lúc. Các đoạn DNA gắn trên chip được gọi là probe (mẫu dò). Trên mỗi điểm của chip có hàng ngàn phân tử probe với trình tự giống nhau. Một tập hợp dữ liệu biểu diễn gene có thể được biểu diễn thành một ma trận giá trị thực : , 21 22221 11211                ndnn d d xxx xxx xxx D     Trong đó : - n là số lượng các gen - d là số lượng mẫu hay điều kiện thử - xij là thước đo biểu diễn mức gen i trong mẫu j -8- Bởi vì các biểu ma trận gốc chứa nhiễu, giá trị sai lệch, hệ thống biến thể, do đó tiền xử lý là đòi hỏi cần thiết trước khi thực hiện phân cụm. Hình 1 Tác vụ của Khai phá dữ liệu Dữ liệu biểu diễn gen có thể được phân cụm theo hai cách. Cách thứ nhất là nhóm các các mẫu gen giống nhau, ví dụ như gom các dòng của ma trận D. Cách khác là nhóm các mẫu khác nhau trên các hồ sơ tương ứng, ví dụ như gom các cột của ma trận D. 1.2.2 Phân cụm dữ liệu phục trong sức khỏe tâm lý Phân cụm dữ liệu áp dụng trong nhiều lĩnh vực sức khỏe tâm lý, bao gồm cả việc thúc đẩy và duy trì sức khỏe, cải thiện cho hệ thống chăm sóc sức khỏe, và công tác phòng chống bệnh tật và người khuyết tật (Clatworthy et al., 2005). Trong sự phát triển hệ thống chăm sóc sức khỏe, phân cụm dữ liệu được sử dụng để xác định các nhóm của người dân mà có thể được hưởng lợi từ các dịch vụ cụ thể (Hodges và Wotring, 2000). Trong thúc đẩy y tế, nhóm phân tích được sử dụng để lựa chọn nhắm mục tiêu vào nhóm sẽ có khả năng đem lại lợi ích cho sức khỏe cụ thể từ các chiến dịch quảng bá và tạo điều kiện thuận lợi cho sự phát triển của quảng cáo. Ngoài ra, phân cụm dữ liệu Khai phá dữ liệu Khai phá dữ liệu trực tiếp Khai phá dữ liệu gián tiếp Phân loại Ước lượng Dự đoán Phân cụm Luật kết hợp Diễn giải và trực quan hóa -9- được sử dụng để xác định các nhóm dân cư bị rủi ro do phát triển y tế và các điều kiện những người có nguy cơ nghèo. 1.2.3 Phân cụm dữ liệu đối với hoạt đông nghiên cứu thị trường Trong nghiên cứu thị trường, phân cụm dữ liệu được sử dụng để phân đoạn thị trường và xác định mục tiêu thị trường (Chrisoppher, 1969; Saunders, 1980, Frank and Green, 1968). Trong phân đoạn thị trường, phân cụm dữ liệu thường được dùng để phân chia thị trường thành nhưng cụm mang ý nghĩa, chẳng han như chia ra đối tượng nam giới từ 21-30 tuổi và nam giới ngoài 51 tuổi, đối tượng nam giới ngoài 51 tuổi thường không có khuynh hướng mua các sản phẩm mới. 1.2.4 Phân cụm dữ liệu đối với hoạt động Phân đoạn ảnh Phân đoạn ảnh là việc phân tích mức xám hay mầu của ảnh thành các lát đồng nhất (Comaniciu and Meer, 2002). Trong phân đoạn ảnh, phân cụm dữ liệu thường được sử dụng để phát hiện biên của đối tượng trong ảnh. Phân cụm dữ liệu là một công cụ thiết yếu của khai phá dữ liệu, khai phá dữ liệu là quá trình khám phá và phân tích một khối lượng lớn dữ liệu để lấy được các thông tin hữu ích (Berry and Linoff, 2000). Phân cụm dữ liệu cũng là một vấn đề cơ bản trong nhận dạng mẫu (pattern recognition). Hình 1.1 đưa ra một danh sách giản lược các tác vụ đa dạng của khai phá dữ liệu và chứng tỏ vai trò của phân cụm dữ liệu trong khai phá dữ liệu. Nhìn chung, Thông tin hữu dụng có thể được khám phá từ một khối lượng lớn dữ liệu thông qua phương tiện tự động hay bán tự động (Berry and Linoff, 2000). Trong khai phá dữ liệu gián tiếp, không có biến nào được chọn ra như một biến đích, và mục tiêu là để khám phá ra một vài mối quan hệ giữa tất cả các biến. Trong khi đó đối với khai phá dữ liệu gián tiếp một vài biến lại được chọn ra như các biến đích. Phân cụm dữ liệu là khai phá dữ liệu gián tiếp, bởi vì trong khai phá dữ liệu, ta không đảm bảo chắc chắn chính xác cụm dữ liệu mà chúng ta đang tìm kiếm, đóng vai trò gì trong việc hình thành các cụm dữ liệu đó, và nó làm như thế nào. Vấn đề phân cụm dữ liệu đã được quan tâm một cách rộng rãi, mặc dù chưa có định nghĩa đồng bộ về phân cụm dữ liệu và có thể sẽ không bao giờ là một và đi đến thống nhất.(Estivill-Castro,2002; Dubes, 1987; Fraley and Raftery, 1998). Nói một cách đại khái là : Phân cụm dữ liệu, có nghĩa là ta -10- cho một tập dữ liệu và một phương pháp tương tự, chúng ta nhóm dữ liệu lại chẳng hạn như điểm dữ liệu trong cùng một nhóm giống nhau và điểm dữ liệu trong các nhóm khác nhau về sự không đồng dạng. Rõ ràng là vấn đề này được bắt gặp trong nhiều ứng dụng, chẳng hạn như khai phá văn bản, biểu diễn gen, phân loại khách hàng, xử lý ảnh… 2. Một số kiểu dữ liệu Thuật toán phân cụm dữ liệu có nhất rất nhiều liên kết với các loại dữ liệu. Vì vậy, sự hiểu biết về quy mô, bình thường hoá, và gần nhau là rất quan trọng trong việc giải thích các kết quả của thuật toán phân cụm dữ liệu. Kiểu dữ liệu nói đến mức độ lượng tử hóa trong dữ liệu (Jain và Dubes, 1988; Anderberg, 1973) - một thuộc tính duy nhất có thể được gõ như nhị phân, rời rạc, hoặc liên tục. thuộc tính nhị phân có chính xác hai giá trị, như là đúng hoặc sai. Thuộc tính rời rạc có một số hữu hạn các giá trị có thể, vì thế các loại nhị phân là một trường hợp đặc biệt của các loại rời rạc (xem hình 2). Dữ liệu quy mô, mà chỉ ra tầm quan trọng tương đối của các con số, cũng là một vấn đề quan trọng trong phân cụm dữ liệu. Vậy liệu có thể được chia thành quy mô định lượng và quy mô định tính. quy mô định lượng bao gồm quy mô danh nghĩa và quy mô giới hạn; quy mô định tính bao gồm quy mô khoảng và quy mô khoảng tỷ lệ (hình 3). các kiểu dữ liệu sẽ được xem xét trong phần này . 2.1 Dữ liệu Categorical Thuộc tính Categorical cũng được gọi là thuộc tính danh nghĩa, thuộc tính này đơn giản là sử dụng như tên, chẳng hạn như các thương hiệu xe và tên của các chi nhánh ngân hàng. Chúng ta xem xét các dữ liệu tập hợp với một số hữu hạn các điểm dữ liệu, một thuộc tính trên danh nghĩa của các điểm dữ liệu trong tập dữ liệu có thể chỉ có một số hữu hạn các giá trị; như vậy, các loại danh nghĩa cũng là một trường hợp đặc biệt của kiểu rời rạc. -11- Hình 2. Biểu đồ các dạng dữ liệu Hình 3. Biểu đồ quy mô dữ liệu Trong phần này, chúng ta sẽ giới thiệu các bảng biểu tượng và bảng tần số và ký hiệu một số bộ dữ liệu Categorical. Bảng 1 Mẫu ví dụ của tập dữ liệu Categorical Bản ghi Giá trị x1 (A, A, A, A, B, B) x2 (A, A, A, A, C, D) x3 (A, A, A, A, D, C) x4 (B, B, C, C, D, C) x5 (B, B, D, D, C, D) Cho  nxxxD ,, 21  là một tập dữ liệu tuyệt đối với khoảng cách n, được mô tả bởi d thuộc tính Categorical v1, v2,…vd. Đặt DOM(vj) thuộc Kiểu dữ liệu Rời rạc Liên tục Danh nghĩa Nhị phân Đối xứng Bất đối xứng Quy mô dữ liệu Định lượng Danh nghĩa Giới hạn Định tính Tỷ lệ Khoảng -12- miền thuộc tính vj . Trong tập dữ liệu Categorical đã cho trong bảng 2.1, ví dụ miền của v1 và v4 là DOM(v1) = {A, B} và DOM(v4) ={A, C, D}, tách biệt. Cho một tập dữ liệu Categorical D, giả sử rằng     jjnjjj AAAvDOM ,,, 21  với j = 1, 2, … ,d. Gọi Ajl jnl 1 là trạng thái thuộc tính Categorical vj đã cho trong tập dữ liệu D. Một bảng Ts của tập dữ liệu được định nghĩa Ts = (s1, s2, … , sd), (2.1) Nơi sj )1( dl  là vecto định nghĩa là  Tjnjjj jAAAs ,,, 21  . Vì có nhiều trạng thái có thể là các giá trị (hoặc) cho một biến, một bảng biểu tượng của một tập dữ liệu thường là không duy nhất. Ví dụ, đối với bộ dữ liệu trong bảng 1, cả hai bảng 2 và Bảng 3 là bảng biểu tượng của nó. Bảng tần số được tính theo một bảng biểu tượng và nó đã chính xác cùng kích thước như bảng biểu tượng. Đặt C là một cụm. Sau đó, bảng tần số Tf (C) của các cụm C được định nghĩa là         ,,,, 21 CfCfCfCT df  (2.2) Nơi  Cf j là một vecto được định nghĩa          ,,,, 21 Tjnjjf CfCfCfCT j (2.3) Bảng 2. Một trong những bảng biểu tượng của bộ dữ liệu trong bảng 1           D C B D C B D C A D C A B A B A Bảng 3 : Bảng biểu tượng của bộ dữ liệu trong bảng 1.           D B C D C B D C A A C D A B B A Nơi fjr(C) )1,1( jnrdj  là số điểm dữ liệu trong cụm C mà giá trị Ajr tại mảng thứ j, v.v    ,: jrjjr AxCxCf  (2.4) -13- Nơi xj là giá trị bộ phận j của x Đối với một bảng biểu tượng cho trước của bộ dữ liệu, bảng tần số của mỗi cụm là duy nhất lên đến rằng bảng biểu tượng. Ví dụ, đối với bộ dữ liệu trong bảng 2.1, cho C được một cụm, trong đó C = (x1, x2, x3). Sau đó, nếu sử dụng các biểu tượng trình bày trong bảng 2 bảng tần số tương ứng cho các nhóm C được cho trong bảng 2.4. Nhưng nếu sử dụng bảng biểu tượng trình bày trong Bảng 2.3, sau đó là bảng tần số cho các nhóm C được cho trong bảng 2.5. Để có được bộ dữ liệu Categorical D, chúng ta thấy rằng Tf(D) là một bảng tính toán tần số trên cơ sở dữ liệu toàn bộ thiết lập. Giả sử D là phân vùng không chồng chéo vào k cụm C1, C2,..., Ck. Sau đó chúng ta có       k i ijrjr CfDf 1 (2.5) Với tất cả r = 1, 2, … , nj và j = 1, 2, …d. 2.2 Dữ liệu nhị phân Một thuộc tính nhị phân là một thuộc tính có hai giá trị chính xác nhất có thể, chẳng hạn như "Đúng" hay "Sai" Lưu ý rằng các biến nhị phân có thể được chia thành hai loại:. biến nhị phân Đối xứng và các biến nhị phân bất đối xứng. Trong một biến nhị phân đối xứng, hai giá trị có quan trọng không kém nhau. Một ví dụ là "nam-nữ". Biến nhị phân đối xứng là một biến danh nghĩa. Trong một biến không đối xứng, một trong những giá trị của nó mang tầm quan trọng hơn biến khác . Ví dụ, "có" là viết tắt của sự hiện diện của một thuộc tính nhất định và "không" nghĩa là sự vắng mặt của một thuộc tính nhất định. Một vecto nhị phân x với kích thước d được định nghĩa là (x1, x2,…, xd)(Zhang and Srihari 2003), nơi   dixi  11,0 là giá trị thành phần j của x. Vecto khối nhị phân I của kích thước d là một vecto nhị phân với mỗi giá trị nhập vào bằng 1. Việc bổ xung một vecto nhị phân x được định nghĩa là xIx  , nơi I là một đơn vị vecto nhị phân có cùng kích thước như x. Xét hai vecto nhị phân x và y trong không gian d, và cho  yxSij ,   1,0, ji biểu thị số lần xuất hiện của i trong x và j trong y tương ứng, ví dụ    ixkyxS kij  :, và dkjyk ,,2,1,  . (2.6) -14- Sau đó, rõ ràng chúng ta có đẳng thức sau :      d i ii yxyxyxS 1 11 ,., (2.7a)        d i ii yxyxyxS 1 __ 00 ,11., (2.7b)       d i ii yxyxyxS 1 _ 01 ,1., (2.7c)       d i ii yxyxyxS 1 _ 10 ,1., (2.7d) Ta cũng có :        .,,,, 11100100 yxSyxSyxSyxSd  (2.8) Bảng 4: Bảng tính toán tần số từ bảng biểu tượng trong bảng 2           1 1 1 1 1 1 0 0 3 0 0 3 0 3 0 3 Bảng5: Bảng tính toán tần số từ bảng biểu tượng trong bảng 3           1 1 1 1 1 1 0 0 3 3 0 0 3 0 0 3 2.3 Dữ liệu giao dịch Cho một tập hợp các phần tử I = (I1, I2,. . . , Im), một giao dịch là một tập hợp con của I (Yang et al, 2002b.; Wang et al, 1999a.; Xiao và Dunham, 2001). Một tập dữ liệu giao dịch là một tập hợp các giao dịch, ví dụ  .,2,1,: niIttD ii  . Giao dịch có thể được đại diện bởi vector nhị phân, trong đó mỗi mục biểu thị các có hay không có mục tương ứng. Ví dụ, chúng ta có thể đại diện cho một giao dịch ti do véc tơ nhị phân (bi1, bi2,.., bim.), nơi bij = 1 nếu IJ ∈ ti và bij = 0 nếu Ij  ti. Từ điểm này, các dữ liệu giao dịch là -15- một trường hợp đặc biệt của dữ liệu nhị phân. Ví dụ phổ biến nhất của dữ liệu giao dịch là thị trường dữ liệu trong giỏ hàng. Trong một thị trường thiết lập dữ liệu trong giỏ hàng, giao dịch có chứa một tập hợp con của tập tổng số mặt hàng mà có thể được mua. Ví dụ, sau đây là hai giao dịch: (táo, bánh), (táo, món ăn, trứng, cá,). Nói chung, nhiều giao dịch được thực hiện các mục thưa thớt phân phối. Ví dụ, một khách hàng chỉ có thể mua một số mặt hàng từ một cửa hàng với hàng nghìn mặt hàng. Như đã chỉ ra bởi Wang et al. (1999a), cho các giao dịch được thực hiện các mục thưa thớt phân phối, cặp tương tự là không cần thiết, cũng không đủ để đánh giá xem một cụm giao dịch là tương tự. 2.4 Dữ liệu Symbolic Dữ liệu Categorical và dữ liệu nhị phân là loại dữ liệu cổ điển, và dữ liệu symbolic là một phần mở rộng của các kiểu dữ liệu cổ điển. Trong bộ dữ liệu thông thường, các đối tượng đang được coi là cá nhân (lần đầu các đối tượng tự) (Malerba et al, 2001.), trong khi đó tại tập dữ liệu symbolic , các đối tượng là nhiều hơn "thống nhất" do có nghĩa là các mối quan hệ. Như vậy, các dữ liệu symbolic được nhiều hơn hoặc ít hơn đồng nhất hoặc các nhóm của các cá nhân (thứ hai đối tượng tự) (Malerba et al, 2001.). Malerba et al. (2001) được xác định một dữ liệu symbolic được thiết lập để một lớp hoặc nhóm của các cá nhân mô tả bởi một số thiết lập giá trị hoặc biến phương thức. Biến A được gọi là giá trị thiết lập nếu nó đóng vai trò giá trị của nó trong thiết lập miền của nó. Một biến phương thức là một thiết lập giá trị biến với một biện pháp hoặc phân phối một (tần số, xác suất, hoặc trọng lượng) kết hợp với mỗi đối tượng. Gowda và Diday (1992) tóm tắt sự khác biệt giữa dữ liệu symbolic và dữ liệu thông thường như sau: • Tất cả các đối tượng trong một dữ liệu symbolic có thể không được định nghĩa về các biến tương tự. • Mỗi biến có thể mất nhiều hơn một giá trị hoặc thậm chí khoảng một giá trị. • Các biến trong một dữ liệu symbolic phức tạp có thể mất giá trị bao gồm một hoặc nhiều đối tượng cơ bản. -16- • Các mô tả của một đối tượng tượng trưng có thể phụ thuộc vào mối quan hệ hiện tại giữa các đối tượng khác. • Các giá trị các biến mất có thể cho thấy tần suất xuất hiện, khả năng tương đối, mức độ quan trọng của các giá trị, vv. Dữ liệu Symbolic có thể được tổng hợp từ các dữ liệu khác thường vì lý do đó là riêng tư. Trong số liệu điều tra dân số, ví dụ, các dữ liệu được tạo sẵn ở dạng tổng hợp để đảm bảo rằng các nhà phân tích dữ liệu không thể xác định một cá nhân hay một doanh nghiệp duy nhất thành lập. 2.5 Chuỗi thời gian(Time Series) Chuỗi thời gian là những hình thức đơn giản nhất của dữ liệu tạm thời. Chính xác, một chuỗi thời gian là một chuỗi của số thực đại diện cho các phép đo của một biến thực tế tại các khoảng thời gian bằng (Gunopulos và Das, 2000). Ví dụ, giá cổ phiếu các phong trào, nhiệt độ tại một điểm nào đó, và khối lượng bán hàng theo thời gian tất cả đo là các chuỗi thời gian. Một chuỗi thời gian là rời rạc nếu biến được xác định trên một tập hữu hạn các điểm thời gian. Nhiều nhất của chuỗi thời gian gặp phải trong phân tích cụm là thời gian rời rạc. Khi một biến được định nghĩa ở tất cả các điểm trong thời gian, sau đó là chuỗi thời gian là liên tục. Nói chung, một chuỗi thời gian có thể được coi là một hỗn hợp của bốn thành phần sau (Kendall và Ord, 1990): 1. Một xu hướng, ví dụ., các phong trào lâu dài; 2. Biến động về xu hướng đều đặn hơn hoặc ít hơn; 3. Một thành phần theo mùa; 4. Một hiệu ứng dư hoặc ngẫu nhiên. 3. Phép biến đổi và chuẩn hóa dữ liệu Trong nhiều ứng dụng của phân cụm dữ liệu, dữ liệu thô, hoặc đo đạc thực tế, không được sử dụng trực tiếp, trừ khi một mô hình xác suất cho các thế hệ khuôn mẫu có sẵn (Jain và Dubes, 1988). Việc chuẩn bị cho việc phân cụm dữ liệu yêu cầu một số loại chuyển đổi, chẳng hạn như biến đổi và chuẩn hóa dữ liệu. Một số phương pháp biến đổi dữ liệu thường được sử dụng để phân cụm dữ liệu sẽ được thảo luận trong phần. Một số phương pháp chuẩn hoá dữ liệu được trình bày trong Phần 4.1. -17- Để thuận tiện hãy cho  **2*1* ,,, nxxxD  biểu thị tập dữ liệu thô d-chiều. Từ đó ma trận dữ liệu là một ma trân n x d được cho bởi                  ** 2 * 1 * 2 * 22 * 21 * 1 * 12 * 11 ** 2 * 1 ,,, ndnn d d T n xxx xxx xxx xxx      (4.1) 3.1 Phép chuẩn hóa dữ liệu Chuẩn hoá làm cho dữ liệu giảm kích thước đi. Nó có ích để xác định tiêu chuẩn hoá chỉ số. Sau chuẩn hóa, tất cả các kiến thức về vị trí và quy mô của các dữ liệu gốc có thể bị mất. Nó là cần thiết để chuẩn hóa các biến trong trường hợp các biện pháp không giô ́ng nhau, chẳng hạn như khoảng cách Euclide, là nhạy cảm với những khác biệt trong độ lớn hoặc quy mô của các biến đầu vào (Milligan và Cooper, 1988). Các phương pháp tiếp cận các chuẩn hoá của các biến bản chất của hai loại: Chuẩn hóa toàn cục và chuẩn hoá trong cụm. Chuẩn hóa hóa toàn cục làm chuẩn các biến trên tất cả các yếu tố trong các tập dữ liệu. Trong vòng-cụm tiêu chuẩn hoá dùng để chỉ tiêu chuẩn hóa xảy ra trong các cụm biến mỗi ngày. Một số hình thức tiêu chuẩn hoá có thể được sử dụng trong các chuẩn hóa toàn cục và chuẩn hóa trong phạm vi rất tốt, nhưng một số hình thức chuẩn hoá chỉ có thể được sử dụng trong chuẩn hoá toàn cục. Không thể trực tiếp chuẩn hóa các biến trong các cụm trong phân cụm, bởi vì các cụm không được biết trước khi chuẩn hóa. Để khắc phục khó khăn này, khác phương pháp phải được thực hiện. Tổng thể và Klett (1972) đề xuất một cách tiếp cận lặp rằng các cụm thu được đầu tiên dựa trên số ước lượng tổng thể và sau đó sử dụng các cụm để giúp xác định các biến bên trong nhóm chênh lệch đối với chuẩn hoá trong một phân cụm thứ hai. Để chuẩn hóa dữ liệu thô được đưa ra trong phương trình (4,1), ta có thể trừ một thước đo vị trí và phân chia một biện pháp quy mô cho mỗi biến. Đó là, j jij ij M Lx x   * (4.2) -18- nơi ijx biểu thị giá trị đã được chuẩn hóa, jL là vị trí đo, và jM là quy mô đo. Chúng tôi có thể có được phương pháp tiêu chuẩn hoá khác nhau bằng cách chọn khác nhau LJ và MJ trong phương trình (4,2). Một số phương pháp chuẩn hoá nổi tiếng trung bình, tiêu chuẩn độ lệch, phạm vi, Huber của dự toán, dự toán biweight Tukey's, và Andrew ước tính của sóng. Bảng 4,1 cho một số hình thức tiêu chuẩn hoá, nơi * jx , * jR và * j , có nghĩa là, phạm vi, và độ lệch chuẩn của biến thứ j, tương ứng, nghĩa là    n i ijj x n x 1 ** 1 (4.3a) ,minmax * 1 * 1 * ij ni ij ni j xxR   (4.3b) 2 1 2 1 *** )( 1 1            n i jijj xx n  (4.3c) Bây giờ chúng ta thảo luận về một số chi tiết các hình thức chung của tiêu chuẩn hoá và thuộc tính .z-score là một hình thức của tiêu chuẩn hoá được sử dụng để chuyển biến thể bình thường để tạo điểm chuẩn. Cho một tập hợp các dữ liệu thô D*, các Z-score công thức chuẩn được định nghĩa là   * ** * 1 j jij ijij xx xZx    (4.4) Nơi * jx , * j có nghĩa là các mẫu và độ lệch chuẩn của các thuộc tính thứ j, tương ứng. Biến đổi sẽ có một ý nghĩa của 0 và phương sai một trong số 1. Vị trí quy mô và thông tin của biến gốc đã bị mất. Chuyển đổi này cũng là trình bày trong (Jain và Dubes, 1988, trang 24). Một điều quan trọng hạn chế của chuẩn hóa Z1 là nó phải được áp dụng trong tiêu chuẩn toàn cầu và không ở trong phạm vi-cụm tiêu chuẩn hoá (Milligan và Cooper, 1988). Trong thực tế, hãy xem xét trường hợp hai cụm tách ra cũng tồn tại trong các dữ liệu. Nếu một mẫu có vị trí mỗi hai cụm trung tâm, sau đó trong vòng-cụm chuẩn sẽ chuẩn hóa các mẫu nằm tại cụm trung tâm về không vectơ. Bất kỳ thuật toán clustering sẽ nhóm hai số không vectơ với nhau, có nghĩa là hai nguyên mẫu -19- sẽ được được nhóm cho một cluster. Điều này tạo ra một kết quả phân nhóm rất gây hiểu nhầm. Bảng 4.1 Một vài phép chuẩn hóa dữ liệu, nơi * jx , * jR và * j được định nghĩa trong biểu thức 4.3 Tên Lj Lj z-score * jx * j USTD 0 * j Maxium 0 * 1 max ij ni x  Mean * jx 1 Median * 2 1 j nx  nếu n là lẻ           * 2 2 * 2 2 1 j n j n xx nếu n là chẵn 1 Sum 0   n i ijx 1 * Range * 1 min ij ni x  * jR Chuẩn hóa USTD (Độ lệch chuẩn các trọng không chính xác) cũng tương tự như chuẩn hoá điểm z-score và được định nghĩa là   * * * 2 j ij ijij x xZx   (4.5) Nơi * j được định nghĩa trong biểu thức (4.3c) Biến đổi bởi Z2 sẽ có một phương sai của 1. Kể từ khi có điểm số không được trung tâm bằng cách trừ đi có nghĩa là, các thông tin vị trí giữa các điểm vẫn còn. Như vậy, chuẩn hóa Z2 sẽ không phải chịu những vấn đề của sự mất thông tin về các Cụm centroids. Phương pháp chuẩn hoá thứ ba trình bày trong Milligan và Cooper (1988) là sử dụng điểm tối đa về biến:   * 1 * * 3 max ij ni ij ijij x x xZx   (4.6) -20- Một X biến đổi bởi Z3 sẽ có một ý nghĩa )max( X X và độ lệch chuẩn , )max( X X nơi X và X là trung bình và độ lệch chuẩn của biến gốc. Z3 là nhạy cảm với sự hiện diện của Outliers (Milligan và Cooper, 1988). Nếu một đơn lớn quan sát trên một biến được trình bày, Z3 sẽ chuẩn hóa các giá trị còn lại để gần 0. Z3 có vẻ là có ý nghĩa chỉ khi biến này là một biện pháp trong một phạm vi tỷ lệ (Milligan và Cooper, 1988). Hai quy chuẩn có liên quan đến việc sử dụng phạm vi của biến đã được trình bày trong (Milligan và Cooper, 1988):   * * * 4 j ij ijij R x xZx  (4.7a)   , min * * 1 * * 5 j ij ni ij ijij R xx xZx    (4.7b) Nơi * jR là phạm vi thuộc tính thứ j được định nghĩa trong biểu thức (4.3b) Một biến X biến đổi bởi Z4 và Z5 sẽ có nghĩa là )min()max( XX X  và )min()max( )min( XX XX   , tương ứng, và có cùng độ lệch chuẩn )min()max( XX X   . Cả hai Z4 và Z5 dễ phải sự hiện diện của Outliers. Một tiêu chuẩn hoá trên cơ sở bình thường hóa với tổng của các quan sát trình bày trong (Milligan và Cooper, 1988) được định nghĩa là   , 1 * * * 6    n i ij ij ijij x x xZx (4.8) Các Z6 chuyển đổi sẽ bình thường hóa tổng giá trị chuyển thành sự thống nhất và các chuyển có nghĩa là sẽ có n 1 . Như vậy, có nghĩa là sẽ được liên tục trên tất cả các biến. -21- Một cách tiếp cận rất khác nhau của chuẩn hoá mà bao gồm việc chuyển đổi các điểm đến đánh giá cao được trình bày trong (Milligan và Cooper, 1988) và được định nghĩa là    ,**7 ijijij xRankxZx  (4.9) Nơi Rank(X) là cấp chỉ định cho X Một biến chuyển bởi Z7 sẽ có một ý nghĩa của 2 1n và một phương sai của           4 1 6 12 1 nn n . Việc chuyển đổi cấp bậc làm giảm tác động của Outliers trong dữ liệu. Conover và Iman (1981) đề xuất bốn loại chuyển đổi cấp bậc. Hạng nhất chuyển đổi trình bày được xếp hạng từ nhỏ đến lớn nhất, với điểm số nhỏ nhất có hạng nhất, điểm thứ hai nhỏ nhất có thứ hạng hai, vv. Cấp bậc trung bình được chỉ định trong trường hợp quan hệ. 3.2 Biến đổi dữ liệu Biến đổi Dữ liệu có gì đó để làm gì với dữ liệu chuẩn hoá, nhưng nó là phức tạp hơn hơn so với chuẩn hoá dữ liệu. Chuẩn hoá dữ liệu tập trung vào các biến, nhưng Biến đổi dữ liệu tập trung vào các dữ liệu toàn bộ thiết lập. Theo Chuẩn hoá dữ liệu như vậy, có thể được được xem như là một trường hợp đặc biệt của Biến đổi dữ liệu i. Trong phần này, trình bày một số dữ liệu kỹ thuật Biến đổi có thể được sử dụng trong phân cụm dữ liệu. 3.2.1 Phân tích thành phần chính Mục đích chính của phân tích thành phần chính (PCA) (Ding và He, 2004; Jolliffe, 2002) là giảm chiều cao của một chiều đặt dữ liệu bao gồm một lượng lớn số biến tương quan và đồng thời giữ lại càng nhiều càng tốt của biến đổi hiện diện trong tập dữ liệu. Các thành phần chính (PC) là các biến mới được không tương quan và ra lệnh như vậy là người đầu tiên giữ lại vài phần lớn các biến thể hiện diện trong tất cả các bản gốc biến. Các PC được định nghĩa như sau. Cho   dvvvv ,,, 21  là một vectơ của d ngẫu nhiên biến, nơi ’ là hoạt động transpose. Bước đầu tiên là tìm một hàm tuyến tính một va1 của các yếu tố của v có tối đa các phương sai, mà a1 là một vectơ d-chiều  daaa 11211 ,,,  do đó, -22-    d i iivava 1 1 ' 1 Sau khi tìm vavava j 121 ,,,   , chúng tôi tìm một hàm tuyến tính va j không tương quan với vavava j 121 ,,,   và có phương sai tối đa. Sau đó chúng ta sẽ tìm thấy d chức năng như vậy tuyến tính sau khi bước d. Biến bắt nguồn thứ j PC . Nhìn chung, hầu hết các biến thể trong v sẽ được chiếm bởi các PC vài lần đầu tiên. Để tìm mẫu của PC, chúng ta cần phải biết ma trận hiệp phương sai  của v Trong hầu hết các trường hợp thực tế, ma trận hiệp phương sai  chưa được biết, và nó sẽ được thay thế bằng một mẫu ma trận hiệp phương sai . Đối với j = 1, 2,. . . , d, nó có thể được cho thấy thứ j PC được cho bởi zj = va j , nơi aj là một eigenvector của  tương ứng với các thứ giá trị j lớn nhất λj. Trong thực tế, ở bước đầu tiên, z1 = va j có thể tìm thấy bằng cách giải quyết tối ưu hoá vấn đề sau đây: Maximize  va1var  11 aa , Nơi  va1var  được tính như sau    1'1'1var aava Để giải quyết vấn đề tối ưu hóa ở trên, các kỹ thuật của nhân đấu Lagrange có thể được sử dụng. Cho λ là một số nhân Lagrange. Ta muốn tối đa hóa  .1'11'1  aaaa  (4.10) Phương trình khác(4.10) với a1, chúng ta có 011  aa    01  aId Nơi Id là ma trận nhận dạng d x d Vì  là giá trị riêng của  và a1 là vecto đặc trưng đồng vị. ,1 ' 11 ' 1   aaaa -23- a1 là vecto đặc trưng đồng vị với giá trị riêng lớn nhất của  . Trong thực tế nó có thể được biểu diễn là một PC thứ j là va j , nơi aj là một vecto đặc trưng của tương ứng với thứ j lớn nhất giá trị riêng j (Jolliffe, 2002). Trong (Dinh và He, 2004), PCA là làm việc để giảm chiều của dữ liệu thiết lập và sau đó thuật toán K-means được áp dụng trong không gian con PCA. Các ví dụ khác của PCA áp dụng trong phân tích cụm dữ liệu có thể được tìm thấy trong (Yeung và Ruzzo, 2001). Trình diễn PCA là tương đương với giá trị thực hiện phân hủy từ (SVD) trên các hiệp phương sai ma trận của dữ liệu. ORCLUS sử dụng SVD (Kanth et al, 1998) kỹ thuật. Để tìm hiểu tùy tiện theo định hướng không gian con với phân cụm dữ liệu tốt. 3.2.2 SVD SVD là một kỹ thuật mạnh mẽ trong tính toán ma trận và phân tích, chẳng hạn như việc giải quyết các hệ thống phương trình tuyến tính và xấp xỉ ma trận. SVD cũng là một kỹ thuật nổi tiếng chiếu tuyến tính và đã được sử dụng rộng rãi trong nén dữ liệu và ảo (Andrews và Patterson, 1976a, b). trong mục này, phương pháp SVD là phương pháp tóm tắt. Cho  nxxxD ,,, 21  là một số dữ liệu được đặt trong một không gian d-chiều. Sau đó, D có thể được đại diện bởi một n x n ma trận X là   , dnij xX   Nơi ijx giá trị thành phần của xi Cho  d ,,, 21  là cột của X,      n i ijj djx n 1 ,,,2,1, 1 1  và để cho en là một vectơ cột của n chiều dài với tất cả các yếu tố tương đương với nó. Sau đó, SVD thể hiện neX  là, T n USVeX   (4.11) trong đó U là một ma trận n × n trực giao, ví dụ, nghĩa là, UTU = I là ma trận đơn vị. S là một ma trận chéo chứa các giá trị số ít, và V là một ma trận unita d × d , ví dụ, VHV = I, nơi VH là ma trận chuyển vị liên hợp của V. -24- Các cột của ma trận V là vecto đặc trưng của ma trận hiệp phương sai C của X; chính xác TTT VVXX n C  1 (4.12) Kể từ khi C là ma trận chéo đối diện d × d, nó có d là số tự nhiên vecto đặc trưng trực giao. Mà không mất tổng quát, để cho các giá trị riêng của C giảm : λ1 ≥ λ2 ≥ … ≥ λd. Hãy σj (j = 1,2 ,..., d) là độ lệch chuẩn của cột thứ j của X, nghĩa là,   .1 2 1 1 2          n i jijj x n   của C là bất biến theo luân phiên, nghĩa là,    d j j d j j 11 2  Chú ý rằng nXeTn  và nee n T n  từ phương trình (4.11) và (4.12), chúng ta có TTTTT USVUVSSVVS      nTn eXeX   nTnTnTTnTT eeeXXeXX   TT nXX  TVnV . (4.13) Kể từ khi V là một ma trận trực giao, từ phương trình (4,13), các giá trị từ có liên quan đến các giá trị riêng bởi .,2,1, 2 djns jj   Các vecto đặc trưng chiếm các máy tính của X, và các tính năng không tương quan sẽ được thu được do chuyển đổi  VeXY n . PCA chọn các tính năng với giá trị riêng cao nhất. 3.2.3 Phép biến đổi Karhunen-Loève Các phép biến đổi Karhunen-Loève (KL) có liên quan với các giải thích cấu trúc dữ liệu thông qua một số tuyến tính kết hợp của các biến. Giống như PCA, phép biến đổi KL cũng là cách tối ưu cho dự án d- chiều điểm để giảm điểm chiều sao cho sai số của dự án (tức là tổng của khoảng cách bình phương (SSD)) là tối thiểu (Fukunaga, 1990). -25- Cho  nxxxD ,,, 21  là một tập dữ liệu không gian d chiều, và X là đồng vị ma trận d x d. nghĩa là   dnij xX   với ijx là giá trị j thành phân của xi.  nixi ,,2,1  là vecto d chiều. Chúng có thể hiển thị không lỗi bằng phép tính tổng vecto tuyến tính độc lập như    d j T i T jiji yyx 1  hoặc ,TYX  (4.14) nơi  ,, ,,21 idiii yyyy  và  d dy y y Y  ,,,, 21 2 1                   Các ma trận d × d cơ sở  và chúng ta biết thêm có thể cho rằng những hàng  hình thức một bộ trực giao, nghĩa là,       ,0 ,1 jifor jifor T ji hay ,dd T I  Nơi ddI  là ma trận đơn vị ddI  Sau đó , từ phương trình (4.14), bộ phận của yj có thể được tính toán bằng ,,,2,1, nixy ii   hoặc XY  Vì vậy, Y chỉ đơn giản là một biến đổi trực giao của X. j được gọi là véc tơ thứ j tính năng và yij là thành phần thứ j của mẫu xi trong không gian tính năng này. Để giảm bớt chiều, chúng ta chỉ chọn m(m<d) tính năng vectơ có thể gần đúng X tốt. Xấp xỉ có thể được thu được bằng cách thay thế các thành phần của yj với hằng chọn trước (Fukunaga, 1990, trang 402): ,)(ˆ 1 1      d j d mj T jij T jiji bymx  -26- hoặc ,),1()(ˆ 11                        T d T m T m T i mYmx      nơi ),1( mY là ma trận n x m có được bằng cột m đầu tiên của Y, có nghia là   mnij y  m)Y(1, , và một ma trận )( dmn  với (i, j) nhập từ bi,m+j. Mà không mất tổng quát, chúng ta giả định rằng chỉ có các thành phần m đầu tiên của mỗi yj được tính toán. Sau đó, các lỗi của các kết quả là xấp xỉ ,)()(ˆ)( 1    d mj T jijijiii bymxxmx  shoặc ,)),1(()( 1             T d T m BdmYmX    Nơi )),1( dmY  là ma trận )( dmn  được hình thành bởi cột cuối m-d cột của Y Chú ý rằng X  và X là các ma trận ngẫu nhiên, bởi vậy lỗi vuông xấp xr là  22 )()( mXEm   ))()(( mXmXTrE T  ))),1()(),1(( TBdmYBdmYTrE    . 1 1 2      n i d mj ijij byE (4.15) Với mỗi lựa chọn điều kiện hằng số bij, Ta nhận được giá trị )(2 m . Lựa chọn tối ưu cho bij là một trong )(2 m nhỏ nhất. Từ phương trình (4.15) Lựa chọn tối ưu cho bij, là    ,02)(2    ijij ij byEm b  Mà đã cho     ,jiijij xEyEb  hoặc   ).,,)((,)1( 1 dmXEdmmYEB   -27- Cho x là ma trận hiệp phương sai của X, do đó chúng ta có    )()( XEXXEX T x                                           nn T n TT n T xE xE x x XEXExx  11 1 ),),,(    ).()( 1 ii n i T ii xExXEx   Do đó )(2 m có thể được viết lại như sau :        n i d mj ijij byEm 1 1 22 )(           n i d mj jii T ii T j xExxEx 1 1        j n mj n i ii T ii T j xExxEx            1 1     d mj X j T j 1 . (4.16) Nó có thể chỉ ra lựa chọn tối ưu thỏa mãn j (Fukunaga,1990) .jjX j   Do đó j là vecto đặc trưng của x .Do đó phương trình (4.16) trở thành    d Mj jm 1 2 )(  Từ ma trận hiệp phương sai của X, x là semidefinite đối diện, nó có giá trị riêng d không âm. Nếu chúng tôi chọn vecto đặc trưng m tương ứng với các giá trị riêng m lớn nhất, sau đó là lỗi vuông sẽ được giảm thiểu. -28- CHƢƠNG II CÁC THUẬT TOÁN PHÂN CỤM DỮ LIỆU 1. Thuật toán phân cum dữ liệu dựa vào phân cụm phân cấp 1.1 Thuật toán BIRCH Thuật toán phân cụm khác cho tập dữ liệu lớn, được gọi là BIRCH. Ý tưởng của thuật toán là không cần lưu toàn bộ các đối tượng dữ liệu của các cụm trong bộ nhớ mà chỉ lưu các đại lượng thống kê. Thuật toán đưa ra hai khái niệm mới để theo dõi các cụm hình thành , phân cụm đặc trưng là tóm tắt thông tin về một cụm và cây phân cụm đặc trưng(cây CF) là cây cân bằng được sử dụng lưu trữ cụm đặc trưng( được sử dụng để mô tả cụm tóm tắt). Trước tiên được gọi là cụm đặc trưng, là một bộ ba(n, LS, SS), trong đó n là số các điểm trong phân hoạch cụm con, LS là tổng số các giá trị thuộc tích và SS là tổng bình phương của các điểm đó. Đặc trưng tiếp theo là cây CF, mà đơn giản là cây cân bằng mà lưu bộ ba này. Có thể chứng mình rằng, các đại lượng thống kê chuẩn, như là độ đo khoảng cách, có thể xác định từ cây CF. Hình 4.10 dưới đây biểu thị một ví dụ về cây CF. Có thể thấy rừng, tất cả các nút trong cây lưu tổng các đặc trưng cụm CF, các nút con, trong khi đó các nút là lưu trữ các đặc trưng của các cụm dữ liệu. Cây CF chứa các nút trong và nút là, nút trong là nút chứa các nút con và nút lá thì không có con. Nút trong lưu trữ các tổng đặc trưng cụm(CF) của các nút con của nó. Một cây (CF) được đặc trưng bởi hai tham số : - Yếu tố nhánh (Braching Factor – B) : Nhằm xác định tối đa các nút con của một nút lá trong của cây - Ngưỡng(Threshold – T) : khoảng cách tối đa giữa bất kỳ một cặp đối tượng trong nút lá của cây, khoảng cách này còn gọi là đường kính của các cụm con được lưu tại các nút lá. Hai tham số này có ảnh hưởng đến kích thước của cây CF. thuật toán BIRCH thực hiện gồm hai giai đoạn: Giai đoạn 1 : BIRCH quét tất cả các đối tượng trong CSDL để xây dựng cây CF khởi tọa, mà được lưu trữ trong bộ nhớ. Trong giai đoạn này , các đối tượng lần lượt được chèn vào nút lá gần nhất của cây CF(nút lá của cây đóng vai trò là cụm con), sau khi chèn xong thì tất cả các nút trong cây CF được cập nhật thông tin. Nếu đường kính của cụm con sau khi chèn là lớn -29- hơn ngưỡng T, thì nút lá được tách. Quá trình lặp lại cho đến khi tất cả các đối tượng trong cây chỉ được đọc một lần, để lưu toàn bộ cây CF trong bộ nhớ thì cần phải điều chỉnh kích thước của cây CF thông qua điều chỉnh ngưỡng T. Giai đoạn 2 : BIRCH lựa chọn một thuật toán phân cụm(như thuật toán phân cụm phân hoạch) để thực hiện phân cụm cho các nút lá của cây CF Hình 4.10 : Cây CF sử dụng trong BIRCH Thuật toán BIRCH thực hiện qua các bƣớc cơ bản nhƣ sau : 1. Các đối tượng dữ liệu lần lượt được chèn vào cây C, sau khi chèn hết các đối tượng thì thu được cây CF khởi tạo. Một đối tượng được chèn vào nút là gần nhất tạo thành cụm con. Nếu đường kính của cụm con này lớn hơn T thì nút lá được tách ra. Khi một đối tượng thích hợp được chèn vào nút lá, tất cả các nút trỏ tới gốc của cây được cập nhật với thông tin cần thiết 2. Nếu cây CF hiện thời không có đủ bộ nhớ trong khi tiến hành xây dựng một cây CF nhỏ hơn: Kích thước của cây CF được điều khiển bởi tham số F và vì vậy việc chọn một giá trị lớn hơn cho nó sẽ hòa nhập một số cụm con thành một cụm, điều này làm cho cây CF nhỏ hơn. Bước này không cần yêu cầu đọc dữ liệu lại từ đầu nhưng vẫn đảm bảo hiệu chỉnh cây dữ liệu nhỏ hơn. 3. Thực hiện phân cụm: Các nút lá cây CF lưu trữ các đại lượng thống kê -30- của các cụm con. Trong bước này, BIRCH sử dụng các đại lượng thống kê này để áp dụng một số kỹ thuật phân cụm, ví dụ K-means và tạo ra một khởi tạo cho phân cụm. 4. Phân phối lại các đối tượng dữ liệu bằng cách dùng các đối tượng trọng tâm cho các cụm được khám phá từ bước 3: Đây là một bước tùy chọn để duyệt lại tập dữ liệu và gán lại nhãn cho các đối tượng dữ liệu tới các trọng tâm gần nhất. Bước này nhằm để gán nhãn cho các dữ liệu khởi tạo và loại bỏ các đối tượng ngoại lai Với cấu trúc cây CF được sử dụng, BIRCH có tốc độ thực hiện PCDL nhanh và có thể áp dụng đối với tập CDSL lớn, BIRCH cũng có hiệu quả khi áp dụng với tập dữ liệu tăng trưởng theo thời gian. BIRCH thực hiện tính toán khá tốt, độ phức tạp tính toán của BIRCH là tuyến tính tỷ lệ với số các đối tượng, do BIRCH chỉ duyệt toàn bộ dữ liệu một lần với một lần quét thêm tùy chọn( thực hiện phân cụm lại các nút lá cây của CF), có thể được đo trong thời gian O(n) với n là số đối tượng dữ liệu. thuật toán này kết hợp các cụm gần nhau và xây dựng lại cây CF, tuy nhiên mỗi nút trong cây CF có thể chỉ lưu trữ một số hữu hạn bởi kích thước của nó. BIRCH vẫn có một hạn chê : thuật toán này có thể không xử lý tốt nếu các cụm không có hình dạng cầu, bởi vì nó sử dụng khái niệm bán kính hoặc đường kính để kiểm soát ranh giới các cụm và chất lượng của các cụm được khám phá không được tốt. Nếu BIRCH sử dụng khoảng cách Eucle, nó thực hiện tốt chỉ với các dữ liệu số, mặt khác tham số vào T có ảnh hưởng rất lớn tới kích thước tự nhiên của cụm. Việc ép các đối tượng dữ lieeujlamf cho các đối tượng của cụm có thể là đối tượng kết thúc của cụm khác, trong khi các đối tượng gần nhau có thể bị hút bởi các cụm khác nếu chúng được biểu diễn cho thuật toán theo một thứ tự khác. BIRCH không thích hợp với dữ liệu đa chiều. 1.2 Thuật toán CURE Trong khi hầu hết các thuật toán thực hiện phân cụm với các cụm hình cầu và kích thước tương tự, như vậy là không hiệu quả khi xuất hiện các phần tử ngoại lai. Thuật toán này định nghĩa một số cố định các điểm đại diễn nằm rải rác trong toàn bộ không gian dữ liệu và được chọn để mô tả các cụm được hình thành. Các điểm này được tạo ra bởi trước hết lựa chọn các đối tượng -31- nằm rải rác trong cụm và sau đó “ co lại” hoặc di chuyển chúng về trung tâm cụm bằng nhân tố co cụm. Quá trình này được lặp lại và như vậy trong quá trình này, có thể đo tỷ lệ gia tăng của cụm. Tại mỗi bước của thuật toán, hai cụm có cặp các điểm đại diện gần nhau(mỗi điểm trong cặp thuộc về mỗi cụm khác nhau) được hòa nhập Như vậy, có nhiều hơn một điểm đại diện mỗi cụm cho phép CURE khám phá được các cụm có hình dạng không phải là hình cầu. Việc co lại các cụm có tác dụng làm giảm tác động của các phần tử ngoại lai. Như vậy, thuật toán này có khả năng xử lý tốt trong trường hợp có các phần tử ngoại lại và làm cho hiệu quả với những hình dạng không phải là hình cầu và kích thước độ rộng biến đổi. Hơn nữa, nó tỷ lệ tốt với CSDL lớn mà không làm giảm chất lượng phân cụm. Hình 3.14 dưới đây là ví dụ về quá trình xử lý của CURE Hình 3.14 : Cụm dữ liệu khai phá bởi thuật toán CURE Để xử lý được các CSDL lớn, CURE sử dụng ngẫu nhiên và phân hoạch, một mẫu là được xác định ngẫu nhiên trước khi được phân hoạch, và sau đó được tiến hành phân cụm trên mỗi phân hoạch, như vậy mỗi phân hoạch là từng phần đã được phân cụm, các cụm thu hoạch, như vậy mỗi phân hoach là từng phần đã được phân cụm, các cụm thu được lại được phân cụm lần thứ hai để thu được các cụm con mong muốn, nhưng mẫu ngẫu nhiên không nhất thiết đưa ra một mô tả tốt cho toàn bộ tập dữ liệu. -32- Thuật toán CURE đƣợc thực hiện qua các bƣớc cơ bản sau : 1. Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu. 2. Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thước bằng nhau : ý tưởng ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng nhau, kích thước của mỗi phân hoạch là n’/p(n’ là kích thước mẫu). 3. Phân cụm các điểm của mỗi nhóm : Thực hiện PCDL cho các nhóm cho đến khi mỗi nhóm được phân thành n’/pq(với q>1). 4. Loại bỏ các phần tử ngoại lai : Trước hết, khi các cụm được hình thành cho đến khi số các cụm giảm xuống một phần so với số các cụm ban đầu. Sau đó, trong trường hợp các phần tử ngoại lai được lấy mẫu cùng với quá trình pha khởi tạo mẫu dữ liệu, thuật toán sẽ tự động loại bỏ các nhóm nhỏ 5. Phân cụm các cụm không gian : các đối tượng đại diện cho các cụm di chuyển về hướng trung tâm cụm, nghĩa là chúng được thay thế bởi các đối tượng gần trung tâm hơn. 6. Đánh dấu dữ liệu với các nhãn tương ứng. Độ phức tạp tính toán của thuật toán CURE là O(n2log(n)). CURE là thuật toán tin cậy trong việc khám phá ra các cụm với hình thù bất kỳ và có thể áp dụng tốt đối với dữ liệu có phần tử ngoại lai và trên các tập dữ liệu hai chiều. Tuy nhiên, nó lại rất nhạy cảm với các tham số như số các đối tượng đại diện, tỉ lệ co của các phần tử đại diện. 1.3 Thuật toán ANGNES Phương pháp phân hoạch ANGNES là kỹ thuật kiểu tích tụ. ANGNES bắt đầu ở ngoài với mỗi đối tượng dữ liệu trong các cụm riêng lẻ. Các cụm được hòa nhập theo một số loại của cơ sở luật, cho đến khi chỉ có một cụm ở đỉnh của phân cấp, hoặc gặp điều kiện dừng. Hình dạng này của phân cụm phân cấp cũng liên quan đến tiếp cận bottom-up bắt đầu ở dưới với các nút lá trong mỗi cụm riêng lẻ và duyệt lên trên phân cấp tới nút gốc, nơi tìm thấy cụm đơn cuối cùng với tất cả các đối tượng dữ liệu được chứa trong cụm đó. -33- 1.4 Thuật toán DIANA DIANA thực hiện đối lập với AGNES. DIANA bắt đầu với tất cả các đối tượng dữ liệu được chứa trong một cụm lớn và chia tách lặp lại, theo phân loại giống nhau dựa trên luật, cho đến khi mỗi đối tượng dữ liệu của cụm lớn được chia tách hết. Hình dang của cụm phân cấp cùng liên quan đế tiếp cận top-down bắt đầu tại mức đỉnh nút gốc, với tất cả các đối tượng dữ liệu, trong một cụm, và duyệt xuống các nút lá dưới cùng nơi tất cả các đối tượng dữ liệu từng cái được chứa trong cụm của chính mình. Trong mỗi phương pháp của hai phương pháp, có thể số các cụm dẫn tới các mức khác nhau trong phân cấp bằng cách duyệt lên hoặc xuống cây. Mỗi mức có thể khác nhau số các cụm và tất nhiên kết quả cũng khác nhau. Một hạn chế lớn của cách tiếp cận này là các cụm được hòa nhập hoặc phân chia một lần, không thể quay lại quyết định đó, cho dù hòa nhập hoặc phân chia không phải là thích hợp ở mức đó 1.5 Thuật toán ROCK --------Main module--------- Procedure cluster(S,k) Begin 1. link:=compute_links(S) 2. for each s  S do 3. q[s]:= build_local heap(link, s) 4. Q:=build_global heap(S, q) 5. while size(Q)> k do{ 6. w:= extract_max(Q) 7. v:= max(q[u]) 8. delete(Q, v) 9. w:= merge(u,v) 10. for each x  q[u]  q[v] do { 11. link[x, w]:=link[x, u]+ link[x, v] 12. delete(q[x], u); delete(q[x], v) 13. insert(q[x], w, g(x, w); insert(q[x], w, g(x, w) 14. update(Q, x, q[x]) 15. } -34- 16. insert(W, w, q[w] 17. deallocate(q[u]); deallocate(q[v]) 18. } end ---------------------Compute_links Procedure------------- Procedure compute_links(S) Begin 1. Compute nbrlist[i] for every point i in S 2. Set link[i,j] to be zero all i,j 3. for i:=1 to n do { 4. N:= nbrlist[i] 5. for j:=1 to [N]-1 do 6. for 1:= j+1 to [N]-1 do 7. link[N[j], N[l]:=link[N[j], N[l]+1 8. } End 1.6 Thuật toán Chameleon Phương pháp Chameleon một cách tiếp cận khác trong việc sử dụng mô hình động để xác định các cụm nào được hình thành. Bước đầu tiên của Chameleon là xây dựng một đồ thị mật độ thưa và sau đó ứng dụng một thuật toán phân hoạch đồ thị để PCDL với số lớn của các cụm con. Tiếp theo, Chameleon thực hiện tích tụ phân cụm phân cấp, như AGNES, bằng hòa nhập các cụm con nhỏ theo hai phép đo, mối quan hệ liên thông và mối quan hệ gần nhau của các nhóm con. Do đó, thuật toán không phụ thuộc vào người sử dụng các tham số như K-means và có thể thích nghi. Thuật toán này khảo sát mô hình động trong phân cụm phân cấp. Trong đó, hai cụm được hòa nhập nêu giữa hai cụm có liên quan mật thiết tới quan hệ kết và gần nhau của các đối tượng trong các cụm. Quá trình hòa nhập dễ dàng khám phá các cụm tự nhiên và đồng nhất, ứng dụng cho tất cả các kiểu dữ liệu miễn là hàm tương tự được xác định. -35- Nó khắc phục được nhược điểm các phương pháp CURE và ROCK. Lý do là CURE và lược đồ liên quan lờ đi thông tin về liên kết của các đối tượng trong hai cụm khác nhau, trong khi ROCK lược đồ liên quan lờ đi thông tin về gần nhau của hai cụm mà lại chú trọng quá về liên kết. CURE sử dụng thuật toán phân hoạch đồ thị để phân cụm các đối tượng dữ liệu vào trong một số lớn một cách tương đối nhỏ của các cụm con. Chameleon sử dụng thuật toán phân cụm phân cấp để tìm các cụm xác thực bằng cách lặp nhiều lần kết hợp hoặc hòa nhập các cụm con. Để xác định các cặp của nhiều cụm con tương tự, phải tính toán cả hai liên kết và gần nhau của các cụm, đặc biệt các đặc trưng bên trong của các cụm đang được hòa nhập. Như vậy, nó không phụ thuộc vào mô hình tĩnh và có thể từ động thích nghi với đặc trưng bên trong của các cụm đang được hòa nhập. Nó có khả năng hơn để khám phá các cụm có hình thù bất kỳ có chất lượng cao hơn CURE và DBSCAN nhưng chi phí xử lý dữ liệu đa chiều phụ thuộc vào O(n2) thời gian cho n các đối tượng trong trường hợp xấu nhất. 2. Thuật toán phân cụm dữ liệu mờ Phân cụm dữ liệu mờ (FCM) là phương pháp phân cụm dữ liệu cho phép mỗi điểm dữ liệu thuộc về hai hoặc nhiều cụm thông qua bậc thành viên. Ruspini(1969) giới thiệu khái quát khái niệm phân hoạch mờ để mô tả cấu trúc cụm của tập dữ liệu và đề xuất một thuật toán để tính toán tối ưu phân hoạch mờ. Dunn(19730 mở rộng phương pháp phân cụm và đã phát triển thuật toán phân cụm mờ. Ý tưởng của thuật toán là xây dựng một phương pháp phân cụm mờ dựa trên tối thiểu hóa hàm mục tiêu. Bezdek(1981) cải tiến và tổng quát hóa hàm mục tiêu mờ bằng cách đưa ra trọng số mũ m để xây dựng thuật toán phân cụm mờ Fuzzy C-means(FCM), và được chứng minh độ hội tụ của các thuật toán là cực tiểu cục bộ. Thuật toán FCM đã được áp dụng thành công trong giải quyết một số lớn các bài toán PCDL như trong nhận dạng mẫu, xử lý ảnh, y học,… Tuy nhiên, nhược điểm lớn nhất của FCM là nhạy cảm với nhiễu và phần tử ngoại lai trong dữ liệu, nghĩa là các trung tâm cụm có thể nằm xa so với trung tâm thực của cụm. Đã có nhiều phương pháp đề xuất cải tiến cho nhược điểm trên của thuật toán FCM bao gồm : phân cụm dựa trên xác suất (Kellet, 1993), -36- phân cụm nhiễu mờ ( Dave, 1991), phân cụm dựa trên toán tử Lp, Norm(Kerten, 1999) và thuật toán Insensitive Fuzzy C-means( PCM ). 2.1 Thuật toán FCM Thuật toán FCM gồm một chuỗi các phép lặp qua lại giữa phương trình (5) và (6). Như vậy FCM sử dụng phép lặp để tối ưu hàm mục tiêu, dựa trên đo đạc độ tương tự có trọng số giưa xk và cụm trung tâm Vi, sau mỗi vòng lặp, thuật toán tính toán và cập nhật phân tử ujk trong ma trân phân hoạch U. Phép lặp sẽ dừng khi  ,max 1  kijkijij uu trong đó  là chuẩn kết thúc giữa 0 và 1, trong khi k là các bước lặp. Thủ tục này hội tụ tới cực tiểu cục bộ hay điểm yên ngựa của Jm(u, V). Thuật toán FCM tính toán ma trận phân hoạch U và kích thước của các cụm để thu được các mô hình mờ từ ma trận này. Các bƣớc thực hiện của thuật toán FCM nhƣ sau: Input : Số cụm c và tham số mũ m cho hàm mục tiêu J; Output : c cụm dữ liệu sao cho hàm mục tiêu trong (1) đạt giá trị cực tiểu; Begin 1. Nhập tham số c (1<c<n)   ,1m . Khởi tạo mà trận   ;0,, )0(  jRVvV sxcij 2. Repeat j:=j+1 Tính ma trận phân hoạch mờ U(j) theo công thức (5) Cập nhật các trung tâm  )()(2)(1)( ,...,, jcjjj vvvV  dựa vào (6) và U(j) 3. Until   F jj Uu )()1( ; 4. Trình diễn các cụm kết quả; End Trong đó , F * là tiêu chuẩn Frobenious được định nghĩa như sau:  i k ik T F uUUTr 2 2 )(* và tham số  trước. Việc chọn các tham số cụm rất ảnh hưởng đến kết quả phân cụm, tham số này thường được chọn theo phép ngẫu nhiên hoặc theo Heuristic. Đối với 1m thì thuật toán K-means trở thành thuật toán rõ. Đối với m thì thuật toán FCM trở thành thuật toán phân cụm mờ với : c uik 1  -37- Chưa có quy tắc nào nhằm lựa chọn tham số m đảm bảo việc phân cụm hiệu quả, thông thường chọn m = 2 Độ phức tạp của thuật toán FCM tương đương với độ phức tạp của thuật toán K-means trong trường hợp số đối tượng của tập dữ liệu cần phân cụm là rất lớn. Tóm lại, thuật toán phân cụm mờ FCM là một mở rộng của thuật toán K-means nhằm để khám phá ra các cụm chồng lên nhau, tuy nhiên, FCM vẫn chứa đựng các nhược điểm của thuật toán K-means trong việc xử lý đối với các phần tử ngoại lai và nhiễu trong dữ liệu. Thuật toán εFCM được trình bày dưới đây là một mở rộng của thuật toán FCM nhằm khắc phục các nhược điểm này. 2.2 Thuật toán εFCM Input : Số cụm c và các tham số m, ε cho hàm mục tiêu J; Output : Các cụm dữ liệu sao cho hàm mục tiêu trong (2) đạt giá trị cực tiểu; Begin 1. Nhập tham số c(1<c<n),   ,1m và 0 . Khởi tạo ma trận V=[vij], V (0) , thiết lập j = 0; 2. Repeat j:=j+1; Tính ma trận phân hoạch mờ U(j) Cập nhật các trung tâm  )()(2)(1)( ,...,, jcjjj vvvV  3. Until   FUu jj )()1( ; 4. Trình diễn các cụm kết quả; End. 3. Thuật toán phân cụm dữ liệu dựa vào cụm trung tâm 3.1 . Thuật toán K – means K- means là thuật toán phân cụm mà định nghĩa các cụm bởi trung tâm của các phương tử. Phương pháp này dựa trên độ đo khoảng cách của các đối tượng dữ liệu trong cụm. Nó được xem như là trung tâm của cụm. Như vậy, nó cần khởi tạo một tập trung tâm các trung tâm cụm ban đầu, và thông qua đó nó lặp lại các bước gồm gán mỗi đối tượng tới cụm mà trung tầm gần, và tính toán tại trung tâm của mỗi cụm trên cơ sở gán mới cho các đối tượng. Quá trình này dừng khi các trung tâm hội tụ -38- Hình 3.2 : Các thiết lập để xác định danh giới các cụm ban đầu Trong phương pháp K-means, chọn một giá trị k và sau đó chọn ngẫu nhiên k trung tâm của các đối tượng dữ liệu. Tính toán khoảng cách giữa đối tượng dữ liệu trung bình mỗi cùm để tìm kiếm phần tử nào là tương tự và thêm vào cụm đó. Từ khoảng cách này có thể tính toán trung bình mới của cụm và lặp lại quá trình cho đến khi mỗi các đối tượng dữ liệu là một bộ phận của các cụm k Mục đích của thuật toán K-means là sinh k cụm dữ liệu {C1, C2,…, Ck} từ một tập dữ liệu chứa n đối tượng trong không gian d chiều Xi = {xi1, xi2,…xid}, i = 1  n, sao cho hàm tiêu chuẩn :  2 1 i k ix C i E D x m     đạt giá trị tối thiểu, Trong đó : Mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tượng. Trọng tâm của cụm là một vecto, trong đó giá trị của mỗi phần tử của nó là trung cộng của các thành phần tương ứng của các đối tượng vecto dữ liệu trong cụm đang xét. Tham số đầu vào của thuật toán là số cụm k, và tham số đầu ra của thuật toán là các trọng tâm của các cụm dữ liệu. Độ đo khoảng cách D giữa các đối tượng dữ liệu thường được sử dụng là khoảng cách Euclide vì đây là mô hình khoảng cách nên dễ lấy đạo hàm và xác định các cực trị tối thiểu. Hàm tiêu chuẩn và độ đo khoảng cách có thể được xác định cụ thể hơn tùy ý vào ứng dụng hoặc quan điểm của người dùng. -39- Hình 3.3 Tính toán trọng tâm của các cụm mới Các bƣớc cơ bản của thuật toán K – means Input : Số cụm k và các trọng tâm cụm   1 k j j m  Output : các cụm   1C i i k  và hàm tiêu chuẩn E đạt giá trị tối thiểu. Begin Bƣớc 1 : Khởi tạo Chọn k trọng tâm   1 k j j m  ban đầu trong không gian Rd (d là số chiều của dữ liệu). Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm. Bƣớc 2 : Tính toán khoảng cách Đối với mỗi điểm  1iX i k  , tính toán khoảng cách của nó tới mỗi trọng tâm  1jm i k  . Sau đó tìm trọng tâm gần nhất đối với điểm. Bƣớc 3 : Cập nhật lại trọng tâm Đối với mỗi  1 i k  , cập nhật trọng tâm cụm mj bằng cách xác định trung bình cộng các vecto đối tượng dữ liệu. Điều kiện dừng : Lặp lại các bước 2 và 3 cho đến khi các trọng tâm của cụm không thay đổi. End. -40- K- means biểu diễn các cụm bởi các trọng tâm của các đối tượng trong cụm đó Thuật toán K-means chi tiết được trình bày : BEGIN 1. Nhập n đối tượng dữ liệu 2. Nhập k cụm dữ liệu 3. MSE =  4. For I = 1 to k do  ( 1)* /i i i n km X   ; // khởi tạo k trọng tâm 5. Do { 6. OldMSE = MSE 7. MSE’ = 0 8. for j = 1 to k do 9. {m’[j]=0; n’[j]=0} 10. End for 11. For I =1 to n do 12. For j =1 to k do 13. Tính toán khoảng cách Euclide bình phương : D 2 (x[i]; m[j] 14. Endfor 15. Tìm trọng tâm gần nhất m[h] tới X[i] 16. m’[h] = m’[h] + X[i] ; n’[h] = n’[h]+1; 17. MSE’=MSE’ + D2(x[i]; m[j] 18. Endfor 19. n[j] = max(n’[j], 1); m[j] = m’[j]/n[j]; 20. MSE’=MSE’ 21. } while (MSE’<=OldMSE) END. Trong đó : - MSE : Sai số bình phương trung bình hay là hàm tiêu chuẩn - D 2 (x[i]; m[j] : Khoảng cách Euclide từ đối tượng thứ i tới trọng tâm j; - OldMSE m’[j], n’[j] : Biến tạm lưu giá trị cho trạng thái trung gian cho các biến tương ứng -41- Hình 3.6 : Ví dụ hình dạng cụm dữ liệu sau khi phân cụm bằng K-means Chất lượng của thuật toán K –mean phụ thuộc nhiều vào các tham số đầu vào như : số cụm k, và k trọng tâm khởi tạo ban đầu. Trong trường hợp các trọng tâm khởi tạo ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên thì kết quả phân cụm của K – means là rất thấp, nghĩa là các cụm dữ liệu được khám phá rất lệch so với các cụm trong thực tế. Trên thực tế, chưa có một giải pháp nào để chọn tham số đầu vào, giải pháp thường được sử dụng nhất là thử nghiệm với các giá trị đầu vào , giải pháp thường được sử dụng nhất là thử nghiệm với giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất. 3.2 Thuật toán PAM Thuật toán PAM là thuật toán mở rộng của thuật toán K-means nhằm có khả năng xử lý hiệu quả đối với dữ liệu nhiễu hoặc phần tử ngoại lai, PAM sử dụng các đối tượng medoid để biểu diễn cho các cụm dữ liệu, một đối tượng medoid là đối tượng đặt tại vị trí trung tâm nhất bên trong mỗi cụm. Vì vậy, đối tượng medoid ít bị ảnh hưởng của các đối tượng ở rất xa trung tâm, trong khi đó các trọng tâm của thuật toán K – means lại rất bị tác động bởi các điểm xa trung tâm này. Ban đầu, PAM khởi tạo k đối tượng medoid và phân phối các đối tượng còn lại vào các cụm với đối tượng medoid đại diện tương ứng sao cho chúng tương tự đối với medoid trong cụm nhất. Giả sử Oj là đối tượng không phải medoid mà Om là một đối tượng medoid, khi đó ta nói Oj thuộc về cụm có đối tượng medoid là Om làm đại diện nếu d(Oj, Om) = minOe(Oj, Oe); trong đó d(Oj, Om) là độ phi tương tự giữa Oj và Oe, minOe là giá trị nhỏ nhất của độ phi tương tự giữa Oj và tất cả các đối tượng medoid của các cụm dữ liệu. chất lượng của mỗi cụm được khám phá được đánh giá thông qua độ phi tương tự trung bình giữa một đối tượng và đối tượng medoid tương ứng với cụm của nó, nghĩa là chất lượng phân cụm được đánh giá thông qua chất lượng của tất cả các đối tượng medoid. Độ -42- phi tương tự được xác định bằng độ đo khoảng cách, thuật toán PAM được áp dụng cho dữ liệu không gian. Để xác định các medoid, PAM được áp dụng cho dữ liệu không gian. Để xác định các medoid, PAM bắt đầu bằng cách lựa chon k đối tượng medoid bất kỳ. Sau mỗi bước thực hiện , PAM cố gắng hoán chuyển giữa đối tượng Medoid Om và một đối tượng Op, không phải là medoid, miễn là sự hoán chuyển này nhằm cải tiến chất lượng của phân cụm, quá trình này kết thúc khi chất lượng phân cụm không thay đổi. Chất lượng phân cụm được đánh giá thông qua hàm tiêu chuẩn, chất lượng phân cụm tốt nhất khi hàm tiêu chuẩn đạt giá trị tối thiểu. PAM tính giá trị Cjmp cho tất cả các đối tượng Oj để làm căn cứ cho việc hoán chuyển giữa Om và Op. Om : là đối tượng medoid hiện thời cần được thay thế : Op : là đối tượng medoid mới thay thế cho Om; Oj : Là đối tượng dữ liệu ( Không phải medoid) có thể được di chuyển sang cụm khác; Oj,2 : Là đối tượng medoid hiện thời gần đối tượng Oj nhất Các bước thực hiện thuật toán PAM Input : Tập dữ liệu có n phần tử, số cụm k. Output : k cụm dữ liệu sao cho chất lượng phân hoạch là tốt nhất. BEGIN 1. Chọn k đối tượng medoid bất kỳ; 2. Tính TCmp cho tất cả các cặp đối tượng Om, Op. Trong đó, Om là đối tượng medoid và Op là đối tượng không phải medoid; 3. Chọn cặp đối tượng Om và Op. Tính MinOm, MinOp, TCmp, nếu TCmp là âm thay thế Om bởi Op và quay lại bước 2. Nếu TCmp dương, chuyển sang bước 4; 4. Với mỗi đối tượng không phải medoid, xác định đối tượng medoid tương tự với nó nhất đồng thời gán nhãn cụm cho chúng. END. 3.3 Thuật toán CLARA Thuật toán CLARA được đưa ra nhằm khắc phục nhược điểm của thuật toán PAM trong trường hợp giá trị k và n là lớn. CLARA tiến hành trích mẫu cho tập dữ liệu có n phần tử, nó áp dụng thuật toán PAM cho mẫu này và tìm -43- ra các đối tượng trung tâm medoid cho mẫu được trích ra từ dữ liệu này. Nếu mẫu dữ liệu được trích theo một cách ngẫu nhiên, thì các medoid của nó xấp xỉ với các medoid của toàn bộ tập dữ liệu ban đầu. Để tiến tới một xấp xỉ tốt hơn, CLARA đưa ra nhiều cách lấy mẫu và thực hiện phân cụm cho mỗi trường hợp, sau đó tiến hành chọn kết quả phân cụm tốt nhất khi thực hiên phân cụm trên mẫu này. Để đo chính xác, chất lượng của các cụm được đánh giá thông qua độ phi tương tự trung bình của toàn bộ các đối tượng dữ liệu trong tập đối tượng dữ liệu ban đầu. Kết quả thực nghiệm chỉ ra rằng, 5 mẫu dữ liệu có kích thước 40 +2k cho kết quả tốt. Các bước thực hiện của thuật toán CLARA : CLARA (5); BEGIN 1. For i = 1 to 5 do 2. Lấy một mẫu có 40 + 2k đối tượng dữ liệu ngẫu nhiên từ tập dữ liệu và áp dụng thuật toán PAM cho mẫu dữ liệu này nhằm để tìm các đối tượng medoid đại diện cho các cụm. 3. Đối với mỗi tượng Oj trong tập dữ liệu ban đầu, xác định đối tượng medoid tương tự nhất trong số k đối tượng medoid. 4. Tính đố phi tương tự trung bình cho phân hoạch các đối tượng thu được ở bước trước, nếu giá rị này bé hơn giá trị tối thiểu hiện thời thì sử dụng giá trị này thay cho giá trị tối thiểu ở trạng thái trước, như vậy, tập k đối tượng medoid xác định ở bước này là tốt nhất cho đến thời điểm này. 5. Quay về bước 1 END Phương pháp medoid không hiệu quả với trường hợp tập dữ liệu lớn, như vậy, phương pháp dựa trên mẫu được gọi là CLARA. Ở đây, một phần nhỏ dữ liệu hiện thời được chọn như một đại diện của dữ liệu thay vì sử dụng toàn bộ dữ liệu và sau đó medoid được chọn từ mẫu sử dụng PAM. Nếu mẫu được chọn theo cách ngẫu nhiên thì nó có thể cần phải đại diện tập dữ liệu gốc. Các đối tượng đại diện (medoids) được chọn là tương tự mà đã được chọn từ tập dữ liệu. Nó đưa ra nhiều mẫu của tập dữ liệu, áp dụng PAM trên -44- mỗi mẫu, và trả lại cụm tốt nhất ở đầu ra, như vậy, CLARA có thể xử lý với tập dữ liệu lớn hơn PAM. 3.4 Thuật toán CLARANS CLARANS cũng sử dụng kiểu k-medoids , nó kết hợp thuật toán PAM với chiến lược tìm kiếm kinh nghiệm mới. Ý tưởng cơ bản của CLARANS là không xem xét tất cả các khả năng có thể thay thế các đối tượng tâm medoids bới một đối tượng khác, nó ngay lập tức thay thế các đối tượng tâm này nếu việc thay thế này có tác động tốt đến chất lượng phân cụm chứ không cần xác định cách thay thế tối ưu nhất. CLARANS lấy ngẫu nhiên một đối tượng của k đối tượng medoid trong tâm cụm và cố gắng thay thế nó với một đối tượng chọn ngẫu nhiên trong (n-k) đối tượng còn lại. Cụm thu được sau khi thay thế đối tượng trung tâm được gọi là một láng giềng của phân hoạch cụm trước đó. Số các láng giềng được hạn chế bởi tham số do người dùng đưa vào là Maxneighbor, quá trình lựa chọn các láng giềng này hoàn toàn ngẫu nhiên. Tham số Numlocal cho phép người dùng xác định số vòng lặp tối ưu cục bộ được tìm kiếm. Không phải tất cả các láng giếng được duyệt mà chỉ có Maxneighbor số láng giềng được duyệt. Nếu một láng giềng tốt hơn được tìm thấy, thì CLARANS di chuyển láng giềng đó tới nút và quá trình bắt đầu lặp lại; nếu không kết quả cụm hiện thời là tối ưu cục bộ. Nếu tối ưu cục bộ được tìm thấy, thì CLARANS bắt đầu với lựa chọn nút ngẫu nhiên mới trong tìm kiếm tối ưu cục bộ mới. CLARANS không thích hợp với tập dữ liệu lớn bởi vì nó lấy phần nhỏ của toàn bộ tập dữ liệu và phần này được chọn để đại diện toàn bộ tập dữ liệu và thực hiện sau đó. CLARANS không bị giới hạn không gian tìm kiếm như đối với CLARA, và trong cùng một lượng thời gian thì chất lượng của các cụm phân được là lớn hơn CLARA. Một số khái niệm sử dụng trong thuật toán CLARANS được định nghĩa như sau: Giả sử O là một tập có n đối tượng và M O là tập các đối tượng tâm mediod, NM = O- M là tập các đố tượng không phải tâm. Các đối tượng dữ liệu sử dụng trong thuật toán CLARANS là các khối đa diện. Mỗi đối tượng được diễn tả bằng một tập các cạnh, mỗi cạnh được xác định bằng hai điểm. -45- Giả sử 3P R là một tập tất cả các điểm . Nói chung, các đối tượng ở đây là các đối tượng dữ liệu không gian và chúng ta định nghĩa tâm của một đối tượng chính là trung bình cộng toán học của tất cả các đỉnh hay còn gọi là trọng tâm : :center O P Giả sử dist là một hàm khoảng cách, khoảng cách thường được chọn ở đây là khoảng cách Eucliean : 0:dist PxP R  Hàm khoảng cách dist có thể mở rộng cho các điểm của khối đa diện thông qua hàm tâm : 0:dist OxO R  sao cho ist(o , ) is ( ( ), ( ))i j i jd o d t center o center o Mỗi đối tượng được gán cho một tâm medoid của cụm nếu khoảng cách từ trọng tâm của đối tượng đó tới tâm medoid của nó là nhỏ nhất. Vì vậy, định nghĩa tâm medoid như sau : medoid : O M sao cho ( ) , , : is( , ) is ( , ),i i i i jmedoid o m m M m M d o m d t o m o O      . Cuối cùng định nghĩa một cụm tới tâm mediod mi tương ứng là một tập con các đối tượng trong O với medoid(o) = mi Giả sử C0 là tập tất cả các phân hoạch của O. Hàm tổng để đánh giá chất lượng một phân hoạch được định nghĩa như sau : total_distance : 0 0C R  sao cho total_distance(c)= is ( , )id t o m với , ( )i im M o cluster m  Thuật toán chi tiết CLARANS : Input : O,k, dist, numlocal và maxneighbor;’ Output : k cụm dữ liệu; CLARANS(int k, function dist, int numlocal, int maxneighbor) BEGIN For (i = 1 ; 1 <= numlocalk; i++{ current.creat_randomly(k); j = 1 ; while (j <= maxneighbor) { current.select_radom(old, new); diff = current.caculate_distance_difference(old, new); if (diff < 0){ current.exchange(old, new); -46- j = 1; } Else j++; //end if } //end while Dist = current.caculate_total_distance(); If (disr < smallest_dist) { Best = current; Smallest_dist= dist; } // end if }// end for END. 4. Thuật toán phân cụm dữ liệu dựa vào tìm kiếm 4.1 Thuật toán di truyền (GAS) Thuật toán di truyền GAS lần đầu tiên được đề xuất bởi Holland (1975) là một họ tính toán mô hình lấy cảm hứng từ tương tự của sự tiến hóa và di truyền dân số. Gas vốn song song và đặc biệt thích hợp cho việc giải quyết vấn đề tối ưu hóa phức tạp.Filho et al. (1994) trình bày một cuộc khảo sát của khí cùng với một GA đơn giản viết bằng C ngôn ngữ. Thông thường, chỉ có hai thành phần chính của GAS được vấn đề phụ thuộc: các vấn đề mã hóa và chức năng đánh giá (ví dụ, khách quan chức năng). Ngay cả đối với cùng một vấn đề, có thể sử dụng mã hóa khác nhau. Ví dụ, trong các k-có nghĩa là thuật toán di truyền, Krishna và Narasimha (1999) làm việc string-of-group-số mã hóa, trong khi Maulik và Bandyopadhyay (2000) được mã hóa các chuỗi sao cho mỗi chuỗi là một chuỗi các thực số đại diện cho các trung tâm cụm. Trong GAS, các tham số của không gian tìm kiếm được mã hoá trong các hình thức gọi là chuỗi nhiễm sắc thể. AGA maintains dân (set) của N chuỗi mã hoá cho một số dân số cố định kích thước N và tiến hóa qua các thế hệ. Trong mỗi thế hệ, ba nhà khai thác di truyền, nghĩa là, tự nhiên, lựa chọn, xuyên chéo , và đột biến, được áp dụng cho dân số hiện nay để sản xuất một số dân mới. Mỗi chuỗi trong dân số liên kết với một giá trị thể dục tùy thuộc vào giá trị của hàm mục tiêu. Dựa trên nguyên tắc sống còn của các lắp rắp , -47- một chuỗi vài trong số dân hiện hành được lựa chọn và từng được phân công một số bản sao, và sau đó một thế hệ mới của dây đang mang lại bằng cách áp dụng chéo và đột biến để các chuỗi được chọn. Nói chung, một GA điển hình có những năm thành phần cơ bản: mã hóa, khởi tạo, lựa chọn, crossover, và đột biến. Mã hóa là phụ thuộc vào vấn đề dưới xem xét. Trong giai đoạn khởi, dân số (set) của chuỗi sẽ được ngẫu nhiên tạo ra. Sau giai đoạn khởi, có một lặp của các thế hệ. Số lượng của các thế hệ được xác định bởi người sử dụng. Trong khí, chuỗi tốt nhất thu được cho đến nay được lưu trữ trong một vị trí riêng biệt bên ngoài dân số và sản lượng cuối cùng là chuỗi tốt nhất trong số tất cả có thể có chuỗi kiểm tra trong toàn bộ quá trình. Murthy và Chowdhury (1996) đề xuất một GA trong một nỗ lực để đạt được tối ưu giải pháp cho các vấn đề clustering. Trong thuật toán này, các chức năng đánh giá được xác định như là tổng của bình phương khoảng cách Euclide của các điểm dữ liệu từ các cụm tương ứng của họ trung tâm. Ngoài ra, đơn điểm chéo (Michalewicz, 1992), nghĩa là, các nhà điều hành chéo giữa hai dây, được thực hiện tại một vị trí, và các chiến lược elitist, nghĩa là, các chuỗi hay nhất được mang từ trước đến dân số kế tiếp, được sử dụng. Tseng và Yang (2001) đề xuất một cách tiếp cận di truyền được gọi là clustering đến tự động phân nhóm vấn đề. Clustering là phù hợp với phân nhóm dữ liệu với nhỏ gọn cụm hình cầu, và số cụm có thể được kiểm soát gián tiếp bởi một tham số w. Thuật toán sẽ sản xuất một số lượng lớn các cụm nhỏ gọn với một giá trị nhỏ của w và nó sẽ sản xuất một số lượng nhỏ hơn của cụm lỏng hơn với một giá trị lớn của w. A di truyền phân nhóm dựa trên thuật toán nhằm tìm ra các cụm nonspherical đã được đề xuất bởi Tseng và Yang (2000). Garai và Chaudhuri (2004) đề xuất một phân nhóm di truyền được hướng dẫn theo cấp bậc thuật toán mà có thể tìm thấy tùy tiện có hình cụm. Thuật toán này bao gồm hai giai đoạn. Lúc đầu, tập dữ liệu gốc là bị phân hủy thành một số nhóm phân mảnh để lây lan trong quá trình GAsearch ở giai đoạn thứ hai trong toàn bộ không gian. Sau đó, các thứ bậc Cụm trộn thuật toán (HCMA) được sử dụng. Trong quá trình sát nhập, một kỹ thuật gọi là các -48- cluster liền kề kiểm tra thuật toán (ACCA) được sử dụng để thử nghiệm kề của hai cụm phân đoạn để họ có thể được sáp nhập vào một nhóm. Krishna và Narasimha (1999) và Bandyopadhyay và Maulik (2002) đề xuất hai thuật toán phân nhóm khác nhau dựa trên GAS và k phổ biến có nghĩa là thuật toán. Trong di truyền k-có nghĩa là thuật toán (GKA), Krishna và Narasimha (1999) được sử dụng k-có nghĩa là nhà điều hành thay vì các nhà điều hành chéo để tăng tốc độ hội tụ, trong khi ở kga-clustering, Bandyopadhyay và Maulik (2002) được sử dụng các nhà điều hành crossover- đơn điểm. Cowgill et al. (1999) đề xuất một thuật toán-based clustering di truyền được gọi là COWCLUS. Trong COWCLUS, chức năng đánh giá là tỷ lệ phương sai (VR) được định nghĩa trong điều kiện cô lập cụm bên ngoài và tính đồng nhất cụm nội bộ. Mục tiêu của thuật toán là để tìm các phân vùng với VR tối đa. 4.2 J- Means Cho  1 2, , , nD x x x  là một tập đối tượng và SD được hiểu là tất cả các phần của D. 2 1 min D D i k i P S i x C x z     Nơi k là số lượng cụm , . được hiểu là Euclidean chuẩn tắc, và zi là tâm của cụm Ci 1 i i x Ci Z x C    Với i = 1, 2,…k Thuật toán J-mean : Bước 1 (khởi) Hãy để PD = (C1, C2,. . . , Ck) là một phân vùng ban đầu của D, zi là trọng tâm của cụm Ci, và fopt được mục tiêu hiện chức năng giá trị; S2 (điểm chiếm đóng) Tìm điểm trống, nghĩa là, điểm trong D không trùng với một cụm trọng tâm trong một dung sai nhỏ; -49- S3 (Bước khu phố) Tìm phân vùng tốt nhất DP và mục tiêu tương ứngchức năng giá trị f  trong các khu phố nhảy của giải pháp hiện tại PD: S31 (khai phá láng giềng) Đối với mỗi j (j = 1, 2,..., N), lặp lại sau bước sau: (a) tái định cư. Thêm một cụm mới centroid Z k+1 tại một số điểm trống xj vị trí và tìm thấy những chỉ số i của trọng tâm tốt nhất để xóa; cho vij biểu sự thay đổi trong giá trị hàm mục tiêu; (b) Giữ tốt nhất. Giữ đôi chỉ số i và j nơi vij là tối thiểu; S32 (chuyển hay thay thế) Nếu trọng tâm zi’ bởi xj và cập nhật các thành viên nhóm cho phù hợp để có được P phân vùng mới DP ; đặt ' ': opt i jf f v   S4 (Chấm dứt hoặc di chuyển) Nếu optf f  , dừng; nếu không, di chuyển đến láng giềng tốt nhất Giải pháp DP ; đặt DP là giải pháp hiện hành và quay về bước S2. 5. Thuật toán phân cụm dữ liệu dựa vào lƣới 5.1 STING STING là kỹ thuật phân cụm đa phân giải dựa trên lưới, trong đó vùng không gian dữ liệu được phân rã thành số hữu hạn các cells chữ nhât, điều này có ý nghĩa là các cells lưới được hình thành từ các cells lưới con để thực hiện phân cụm. Có nhiều mức của các cells chữ nhật tương ứng với các mức khác nhau của phân giải trong cấu trúc lưới, và các cells này hình thành cấu trúc phân cấp : mỗi cells ở mức cao được phân hoạch thành các số các cells nhỏ ở mức thấp hơn tiếp theo trong cấu trúc phân cấp. Các điểm dữ liệu được nạp từ CSDL, giá trị của các tham số thống kê cho các thuộc tính của đối tượng dữ liệu trong mỗi ô lưới được tính toán từ dữ liệu và lưu trữ thông qua các tham số thống kê ở các cell mức thấp hơn (điều này giống với cây CF). Các giá trị của các tham số thống kê gồm : số trung bình – mean, số tối đa – max, số tối thiểu – min, số đếm –count , độ lệch chuẩn –s,… Các đối tượng dữ liệu lần lượt được chèn vào lưới và các tham số thống kê ở trên được tính trực tiếp thông qua các đối tượng dữ liệu này. Các truy vấn không gian được thực hiện bằng cách xét các cells thích hợp tại mỗi mức -50- phân cấp. Một truy vấn không gian được xác định như là một thông tin khôi phục lại của dữ liệu không gian và các quan hệ của chúng. STING có khả năng mở rộng cao , nhưng do sử dụng phương pháp đa phân giải nên nó phụ thuộc chặt chẽ vào trọng tâm của mức thấp nhất. Đa phân giải là khả năng phân rã tập dữ liệu thành các mức chi tiết khác nhau. Khi hòa nhập các cells của cấu trúc lưới để hình thành các cụm, nó không xem xét quan hệ không gian giữa các nút của mức con không được hòa nhập phù hợp( do chúng chỉ tương ứng với các cha của nó) và hình dạng của các cụm dữ liệu khám phá là isothetic, tất cả ranh giới của các cụm có các biên ngang và dọc, theo biên của các cells và không có đường biên chéo được phát hiện ra. Các lợi thế của cách tiếp cận này so với các phương pháp phân cụm dữ liêu khác : - Tính toán dựa trên lưới là truy vấn độc lập vi thông tin thống kê được bảo quản trong mỗi cells đại diện nên chỉ cần thông tin tóm tắt của dữ liệu trong cells chứ không phải là dữ liệu thực tế và không phụ thuộc vào câu truy vấn. - Cấu trúc dữ liệu lưới thuận tiện cho quá trình xử lý song song và cập nhật liên tục. - Duyệt toàn bộ CSDL một lần để tính toán các đại lượng thống kê cho mỗi cells, nên nó hiệu quả và do đó độ phức tạp thời gian để tạo các cụm xấp xỉ O(n), trong đó n là tổng số các đối tượng. Sau khi xây dựng cấu trúc phân cấp, thời gian xử lý cho các truy vấn là O(g), trong đó g là tổng số cells lưới ở mức thấp (g<<n) Các hạn chế của thuật toán này : - Trong khi sử dụng cách tiếp cận đa phân giải để thực hiện phân tích cụm chất lượng của phân cụm STING hoàn toàn phụ thuộc vào tính chất hộp ở mức thấp nhất của cấu trúc lưới. Nếu tính chất hộp là mịn, dẫn đến chi phí thời gian xử lý tăng, tính toán trở nên phức tạp và nếu mức dưới cùng là quá thô thì nó có thể làm giảm bớt chất lượng và độ chính xác của phân tích cụm. Thuật toán STING : 1. Xác định tầng để bắt đầu 2. Với mỗi cái của tầng này, tính toán khoảng tin cậy (hoặc ước lượng khoảng) của xác suất mà cells này liên quan tới truy vấn 3. Từ khoảng tin cậy của tính toán trên,gán nhãn cho là có liên quan hoặc -51- không liên quan. 4. Nếu lớp này là lớp cuối cùng , chuyển sang Bước 6; nếu khác thì chuyển sang Bước 5 5. Duyệt xuống dưới của cấu trúc cây phân cấp một mức. Chuyển sang Bước 2 cho các cells mà hình thành các cells liên quan của lớp có mức cao hơn. 6. Nếu đặc tả được câu truy vấn, chuyển sang bước 8; nếu không thì chuyển sang bước 7. 7. Truy lục lại dữ liệu vào trong các cells liên quan và thực hiện xử lý. Trả lại kết quả phù hợp yêu cầu của truy vấn. Chuyển sang Bước 9. 8. Tìm thấy các miền có các cells liên quan. Trả lại miền mà phù hợp với yêu cầu của truy vấn. Chuyển sang bước 9 9. Dừng 5.2. Thuật toán CLIQUE Trong không gian đa chiều, các cụm có thể tồn tại trong tập con của các chiều hay còn gọi là không gian con. Thuật toán CLIQUE là thuật toán hữu ích cho PCDL không gian đa chiều trong các CSDL lớn thành các không gian con. Thuật toán này bao gồm các bước : - Cho n là tập lớn của các điểm dữ liệu đa chiều; không gian dữ liệu thường là không giống nhau bởi các điểm dữ liệu. Phương pháp này xác định những vùng gần, thưa và “đặc” trong không gian dữ liệu nhất định, bằng cách đó phát hiện ra toàn thể phân bố mẫu của tập dữ liệu. - Một đơn vị là dày đặc nếu phần nhỏ của tất cả các điểm dữ liệu chứa trong nó vượt quá tham số mẫu đưa vào. Trong thuật toán CLIQUE, cụm được định nghĩa là tập tối đa liên thông các đơn vị dày đặc. Các đặc trƣng của CLINQUE - Tự động tìm kiếm không gian con của không gian đa chiều, sao cho mật độ đặc của các cụm tồn tại trong không gian con. - Mẫn cảm với thứ tự của dữ liệu vào và không phù hợp với bất kỳ quy tắc phân bố dữ liệu nào. - Phương pháp này tỷ lệ tuyến tính với kích thước vào và có tính biến đổi tốt khi số chiều của dữ liệu tăng. -52- Nó phân hoạch tập dữ liệu thành các hình hộp chữ nhật và tìm các hình hộp chữ nhật đặc, nghĩa là các hình hộp này chứa một số các đối tượng dữ liệu trong số các đối tượng láng giếng cho trước. Hợp các hình hộp này tạo thành các cụm dữ liệu. Tuy nhiên , CLINQUE được bắt đầu bằng cách tiếp cận đơn giản do đó chính xác của kết quả phân cụm có thể bị ảnh hưởng dẫn tới chất lượng của các phương pháp này có thể giảm. Phương pháp bắt đầu nhận dạng các cells đặc đơn chiều trong không gian dữ liệu và tim kiếm phân bố của dữ liệu, tiếp đến CLINQUE lần lượt tìm các hình chữ nhật 2 chiều, 3 chiều,…., cho đến khi hình hộp chữ nhật đặc k chiều được tìm thấy, độ phức tạp tính toán của CLIQUE là O(n) 5.3. Thuật toán WaveCluster Thuật toán WaveCluster là phương pháp gần giống với STING, tuy nhiên thuật toán sử dụng phép biến đổi dạng sóng đẻ tìm ô đặc trong không gian. Đầu tiên kỹ thuật này tóm tắt dữ liệu bằng việc tận dụng cấu trúc dạng lưới đa chiều lên trên không gian dữ liệu. Tiếp theo nó sử dụng phép biến đổi dạng sóng để biến đổi không gian có đặc trưng gốc, tìm kiếm ô đặc trong không gian đã được biến đổi. Phương pháp này là phức tạp với các phương pháp khác chính là ở phép biến đổi. Ở đây, mỗi cells lưới tóm tắt thông tin các điểm của một nhóm ánh xạ vào trong cells. Đây là thông tin tiêu biểu thích hợp đưa vào bộ nhớ chính để sử dụng phép biến đổi dạng sóng đa phân giải và tiếp theo là phân tích cụm. Một phép biến đổi dạng sóng là kỹ thuật dựa trên cơ sở xử lý tín hiệu và xử lý ảnh bằng phân tích tín hiệu với tần số xuất hiện trong bộ nhớ chính. Bằng việc thực hiện một loạt các phép biến đổi ngược phức tạp cho nhóm này,nó cho phép các cụm trong dữ liệu trở thành rõ ràng hơn. Các cụm này có thể được xác định bằng tìm kiếm ô đặc trong vùng mới. Phương pháp này phức tạp, nhưng lại có những lợi thế : - Cung cấp cụm không giám sát, khử nhiễu các thông tin bên ngoài biên của cụm. Theo cách đó, vùng đặc trong không gian đặc trưng gốc hút các điểm ở gần và ngăn chặn các điểm ở xa. Vì vậy, các cụm tự động nổi bật và làm sạch khu vực xung quanh nó, do đó các kết quả tự động loại phần tử ngoại lai. -53- - Đa phân giải là thuộc tính hỗ trợ dò tìm các cụm có các mức biến đổi chính xác. - Thực hiện nhanh với độ phức tạp của thuật toán là O(n), trong đó n là số đối tượng trong CSDL. Thuật toán có thể thích hợp với xử lý song song. - Xử lý tập dữ liệu lớn có hiệu quả, khám phá các cụm có hình dạng bất kỳ, xử lý phần tử ngoại lai, mẫn cảm với thứ tự vào, và không phụ thuộc vào các tham số vào như số các cụm hoặc bán kính láng giềng. 6. Thuật toán phân cụm dữ liệu dựa vào mật độ 6.1 Thuật toán DBSCAN Thuật toán DBSCAN thích nghi với mật độ dầy để phân cụm và khám phá ra các cụm có hình dạng bất kỳ trong không gian CSDL có nhiễu. Nó có định nghĩa cụm là tập tối đa các điểm liên thông mật độ. Phân cụm dựa vào mật độ là tập các đối tương liên thông mật độ mà tối đa về liên lạc mật độ; mỗi đối tượng không được chứa trong cụm là được xem xét nhiễu. Trên thực tế DBSCAN tìm kiếm cho các cụm bằng cách kiểm tra các đối tượng mà có số đối tượng láng giềng nhỏ hơn một ngưỡng tối thiểu, tức là có tối thiểu MinPts đối tượng và mối đối tượng trong cụm tồn tại một đối tượng khác trong cụm giống nhau với khoảng cách nhỏ một ngưỡng Eps. Tìm tất cả các đối tượng mà các láng giềng của nó thuộc về lớp các đối tượng đã xác định ở trên, một cụm được xác định bằng một tập tất cả các đối tượng liên thông mật độ các láng giềng của nó. DBSCAN lặp lại tìm kiếm ngay khi các đối tượng liên lạc mật độ từ các đối tượng trung tâm, nó có thể bao gồm việc kết hợp một số cụm có mật độ liên lạc. Quá trình kết thúc khi không tìm được điểm mới nào có thể thêm vào bất cứ cụm nào. DBSCAN có thể tìm ra các cụm với hình thù bất kỳ, trong khi đo tại cùng một thời điểm ít bị ảnh hưởng bởi thứ tự của các đối tượng dữ liệu nhập vào. Khi có một đối tượng được chèn vào chỉ tác động đến một láng giếng xác định. Mặt khác , DBSCAN sử dụng tham số Eps và MinPts trong thuật toán để kiểm soát mật độ của các cụm . DBSCAN bắt đầu với một điểm tùy ý và xây dựng mật độ láng giềng có thể được đối với Eps và MinPts, Vì vậy, DBSCAN yêu cầu người dùng xác định bán kính Eps của láng giềng và số các láng giềng tối thiểu MinPts, các tham số này khó mà xác định được tối ưu, thông thường nó được xác định bằng phép chọn ngẫu nhiên hoặc theo kinh -54- nghiệm. Độ phức tạp của DBSCAN là O(n2), nhưng nếu áp dụng chỉ số không gian để giúp xác định các láng giềng của một đối tượng dữ liệu thì độ phức của DBSCAN được cải tiến là O(nlogn). Thuật toán DBSCAN có thể áp dụng cho các tập dữ liệu không gian lớn đa chiều, khoảng cách Eucle có thể áp dụng cho tập dữ liệu không gián lớn đa chiều, khoảng cách Eclide được sử dụng để đo sự tương tự giữa các đối tượng nhưng không hiệu quả đối với dữ liệu đa chiều [10][15] - Định nghĩa 1 : Lân cận với ngưỡng Eps của một điểm p ký hiệu NEps(p) được xác định như sau : NEps(p)={q D} khoảng cách dist(p,q)  Eps. D là tập dữ liệu cho trước. Một điểm p muốn nằm trong một cụm C nào đó thì NEps(p) phải có tối thiểu MinPts điểm. Số điểm tối thiểu được chọn là bao nhiêu cũng là bài toán khó vì nếu số điểm tối thiểu lớn thì chỉ những điểm nằm thực sự trong cụm C mới đạt đủ tiêu chuẩn, trong khi đó những điểm nằm ngoài biên của cụm không thể đạt được điều đó. Ngược lại, nếu số điểm tối thiểu là nhỏ thì mọi điểm sẽ rơi vào một cụm. Theo định nghĩa trên, chỉ những điểm nằm trong cụm mới thỏa mãn điều kiện là điểm thuộc vào cụm. Những điểm nằm ở biên của cụm thì không thỏa mãn điều kiện đó, bởi vì thông thường thì lân cận với ngưỡng Eps của điểm biên thì bé hơn lân cận với ngưỡng của Eps của điểm nhân. Để tránh được điều này, có thể đưa ra một tiêu chuẩn khác để định nghĩa một điểm thuộc vào một cụm như sau : Nếu một điểm p muốn thuộc một cụm C phải tồn tại một điểm thuộc một cụm như sau: Nếu một điểm p muốn thuộc một cụm C phải tồn tại một điểm q mà p  NEps (q) và số điểm trong p  NEps (q) phải lớn hơn điểm tối thiểu. Điều này dẫn ba phép đo được sử dụng để mô tả thuộc tính cảu các điểm dữ liệu, là mật độ liên lạc trực tiếp, mật độ liên lạc và mật độ liên lạc và mật độ liên thông được định nghĩa như sau : - Định nghĩa 2 : Mật độ liên lạc trực tiếp Một điểm p được gọi là liên lạc trực tiếp từ điểm q với ngưỡng Eps nếu : 1. p  NEps (q) 2.  EspN q MinPts (điều kiện nhân), điểm q gọi là điểm nhân. -55- Có thể thấy liên lạc trực tiếp là một hàm phản xạ và đối xứng với hai điểm nhân và bất đối xứng nếu một trong hai điểm đó không phải là điểm nhân. - Định nghĩa 3 : Mật độ liên lạc Một điểm p được gọi là liên lạc từ một điểm q theo tham số Eps và MinPts nếu tồn tại một dãy p = p1, p2,…, pn = q thỏa mãn pi+1 là có thêm liên lạc trực tiếp từ pi với 1 1i n   Hai điểm biên của một cụm C có thể không liên lạc được với nhau bởi vì cả hai đều không thỏa mãn điều kiện nhân. - Định nghĩa 4 : Mật độ liên thông Một điểm p được gọi là liên thông với điểm q theo tham số Eps và MinPts nếu tồn tại một điểm O mà cả hai điểm p, q đều có thể liên lạc được theo tham số Eps và MinPts. Mật độ liên thông có tính chất đối xứng và phản xạ. - Định nghĩa 5 : Cụm Giả sử D là một tập cá điểm dữ liệu. Một tập con C khác rỗng của D được gọi là một cụm theo Eps và MinPts nếu thỏa mãn hai điều kiện : 1. Với ,p q D , nếu p C và q có thể liên lạc được từ p theo Eps và MinPts thì q C 2. Với ,p q C ,p liên thông với q theo Eps và MinPts. - Đị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à N ={p/ với mọi I = 1,…,k  Ci}. Với hai tham số Eps và MinPts cho trước, có thể khám phá các cụm theo hai bước : - Bước 1 : Chọn một điểm bất kỳ từ tập dữ liệu ban đầu thỏa mãn điều kiện nhân. - Bước 2 : Lấy tất cả các điểm liên lạc với điểm nhân đã chọn để tạo thành cụm. Bổ đề 1 : Giả sử p là một điểm trong D, Es ( )pN p MinPts tập O ={o/o  D và có thể liên lạc từ p theo Eps và MinPts} là một cụm theo Eps và MinPts. Như vậy, cụm C không hoàn toàn là duy nhất, tuy nhiên, mỗi điểm trong C liên lạc từ bất cứ một điểm nhân nào của C, vì vậy C chứa đúng một số điểm liên thông với điểm nhân tùy ý. -56- Bổ đề 2 : Giả sử C là một cum theo Eps và MinPts, p là một điểm bất kỳ trong C với Es ( )pN p MinPts . Khi đó, C trùng với tập O ={o/o  D và o có thể liên lạc từ p theo Eps và MinPts}. Thuật toán : DBSCAN khởi tạo điểm p tùy ý và lấy tất cả các điểm liên lạc mật độ từ p tới Eps và MinPts. Nếu p là điểm nhân thì thủ tục trên tạo ra một cụm theo Eps và MinPts ( bổ đề 2), nếu p là một điểm biên, không có điểm nào liên lạc mật độ từ p và DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu. Nếu sử dụng giá trị toàn cục Eps và Minpts, DBSCAN có thể hòa nhập hai cụm ( Định nghĩa 5) thành một cụm nếu mật độ của hai cụm gần bằng nhau. Giả sử khoảng cách giữa hai tập dữ liệu S1 và S2 được định nghĩa là dist(S1, S2) = min{dist(p, q) {p  S1 và p  S2}. Thuật toán DBSCAN --------------main Module---------------- DBSCAN(SetOfPoints, Eps, MinOts) //SetOfPoints is UNCLASSIFIED Clusterid:=NextId(NOISE); FOR i FROM 1 TO SetOfPoints.size DO Point := SetOfPoints.get(i); IF PointClId = UNCLASSIFIED THEN IF ExpandCluster (SetOfPoints, Point, ClusterId, Eps, MinPts ) THEN ClusterId.= nextld(ClusterId) END IF END IF END FOR FOR END; I/DBSCAN --------ExpandCluster Procedure ------- ExpandClusster(SetOfPoints, Points, ClId, Eps, MinPts): Boolean; seeds:= SetOfPoints.regionQuery(Point, E ps) IF seeds.size < MinPts THEN // no core point SetOfPoints.changeclId(Point, NOISE), RETURN False; ELSE //all points in seeds are density-reachable from Point SetOfPoints.changeClId(seeds, ClId); seeds.delete(Point); WHILE -57- seeds Empty DO currentP:= seeds.firstO; result:= SetOfPoints.regionQuery(CurrentP, Eps); IF result.size >= MinPts THEN FOR i FROM 1 to result.size 00 resultpP:= result.get(i); IF resultp.ClId IN {UNCLASSIFIED, NOISE) THEN IF resultp.ClId = UNCLASSIFIED THEN seeds.append(resultP); END IF SetOfPoints.changeC1Id(resultP, C1Id), ENDIF; //UNCLASSIFIED or NOISE END FOR; END IF ;// result.size >= Minpts Seed.delete(CurrentP) END WHILE ;//seeds Empty RETURN True; END IF; END ;//ExpandCluster Trong đó SetOfPoints hoặc là tập dữ liệu ban đầu hoặc là cụm được khám phá từ bước trước, C1Id (ClusterId) là nhãn đánh dấu phần tử dữ liệu nhiễu có thể thay đổi nếu chúng có thể liên lạc mật độ từ một điểm khác trong CSDL, điều này chỉ xảy ra đối với các điểm biên của dữ liệu. hàm SetOfPoints.get(i) trả về phần tử thứ I của SetofPoints. Thủ tục SetOfPoints.regionQuery(Point, Eps) trả về một danh sách các điểm dữ liệu lân cận với điểm Point trong ngưỡng Eps từ tập dữ liệu SetOfPoint. Trừ một số trường hợp ngoại lệ, kết quả của DBSCAN là độc lập với thứ tự duyệt các đối tượng dữ liệu. Eps và MinPts là hai tham số toàn cục được xác định bằng thủ công hoặc theo kinh nghiệm. Tham số Eps được đưa vào là nhỏ so với kích thước của không gian dữ liệu, thì độ phức tạp tính toán trung bình của mỗi truy vấn là O(logn). 6.2. Thuật toán OPTICS Thuật toán này là mở rộng của DBSCAN, tuy nhiên nó cải tiến bằng cách giảm bớt các tham số đầu vào. Thuật toán này không phân cụm các điểm -58- dữ liệu mà thực hiện tính toán và sắp xếp trên các điểm dữ liệu theo thứ tự tăng dần nhằm tự động PCDL và phân tích cụm tương tác hơn là đưa ra phân cụm một tập dữ liệu rõ ràng. Đây là thứ tự mô tả cấu trúc phân dữ liệu cụm dựa trên mật độ của dữ liệu, nó chứa thông tin tương ứng với phân cụm dựa trên mật độ từ một dãy các tham số được thiết lập và tạo thứ tự của các đối tượng trong CSDL, đồng thời lưu trữ khoản cách lõi và khoảng cách liên lạc phù hợp của mỗi đối tượng. Hơn nữa, thuật toán được đề xuất rút ra các cụm dựa trên thứ tự thông tin. Như vậy thông tin đủ cho trích ra tất cả các cụm dựa trên mật độ khoảng cách bất kỳ  mà nhỏ hơn khoảng cách  được sử dụng trong sinh thứ tự. Việc sắp xếp thứ tự được xác định bởi hai thuộc tính riêng của các điểm dữ liệu đó là khoảng cách nhân và khoảng cách liên lạc. Các phép đo này chính là kích thước mà có liên quan đến quá trình của thuật toán DBSCAN, tuy nhiên, chúng được sử dụng để xác định thứ tự của các điểm dữ liệu đã được xắp xếp. Thứ tự dựa tren cơ sở các điểm dữ liệu mà có khoảng cách nhân nhỏ nhất và tăng dần độ lớn. Điều duy nhất về phương pháp này là người sử dụng không phải xác định giá trị  hoặc MinPts phù hợp. Thuật toán này có thể phân cụm các đối tượng đã cho với các tham số đầu vào như  và MinPts, nhưng nó vẫn cho phép người sử dụng tùy ý lựa chon các giá trị tham số mà sẽ dãn đến khám phá các cụm chấp nhận được. Các thiết lập tham số thường dựa theo kinh nghiệm tập hợp và khó xác định, đặc biệt là với các tập dữ liệu đa chiều. Tuy nhiên, nó cũng có độ phức tạp thời gian thực hiện như DBSCAN bởi vì có cấu trúc tương đương với DBSCAN : O(nlogn)- n là kích thước của tập dữ liệu. Thứ tự cụm của tập dữ liệu có thể được biểu diễn bằng đồ thị, và được minh họa trong hình sau, có thể thấy ba cụm, giá trị  quyết định số cụm 6.3. Thuật toán DENCLUDE DENCLUDE đưa ra cách tiếp cận khác với các thuật toán phân cụm dựa trên mật độ trước đó, cách tiếp cận này xem xét mô hình được sử dụng một công thức toán để mô tả mỗi điểm dữ liệu sẽ ảnh hưởng trong mô hình như thế nào được gọi là hàm ảnh hưởng có thể xem như một hàm mà mô tả ảnh hưởng của điểm dữ liệu với các đối tượng làng giếng của nó. Ví dụ về hàm ảnh hưởng là các hàm parabolic, hàm sóng ngang, hoặc hàm Gaussian. -59- Như vậy , DENCLUDE là phương pháp dựa trên một tập các hàm phân phố mật độ và được xây dựng ý tưởng chính như sau : - Ảnh hưởng của mỗi điểm dữ liệu có thể là hình thức được mô hình sử dụng một hàm tính toán, được gọi là hàm ảnh hưởng, mô tả tác động của điểm dữ liệu với các đối tượng láng giềng của nó; - Mật độ toàn cục của không gian dữ liệu được mô hình phân tích như là tổng các hàm ảnh hưởng của tất cả các điểm dữ liệu; - Các cụm có thể xác định chính xác bởi việc xác định mật độ cao (density attractors), trong đó mật độ cao là các điểm cực đại hàm mật độ toàn cục. Sử dụng các cells lưới không chỉ giữ thông tin về các cells lưới mà thực tế nó còn chứa đựng cả các điểm dữ liệu. Nó quản lý các cells trong một cấu trúc truy cập dựa trên cây, và như vậy nó nhanh hơn so với một số các thuật toán có ảnh hưởng, như DBSCAN. Tuy nhiên, phương pháp này đòi hỏi chọn lựa kỹ lưỡng tham biến mật độ và ngưỡng nhiễu, việc chọn lựa tham số là quan trọng ảnh hưởng tới chất lượng của các kết quả phân cụm. Định nghĩa : Cho x, y là hai đối tượng trong không gian d chiều ký hiệu là Fd. Hàm ảnh hưởng của đối tượng dy F lên đối tượng x là một hàm 0: y d Bf F R  mà được định nghĩa dưới dạng một hàm ảnh hưởng cwo bản ( ) ( , )yB bf X f x y . Hàm ảnh hưởng có thể là một hàm bất kỳ; cơ bản là xác định khoảng cách của hai vecto d(x, y) trong không gian d chiều, ví dụ như khoảng cách Euclide. Hàm khoảng cách có tính chất phản xạ và đối xứng. Ví dụ về hàm ảnh hưởng như sau : - Hàm ảnh hưởng sóng ngang : 0 if ( , ) ( , ) 1 if ( , ) square d x y f x y d x y       Trong đó  là một ngưỡng. - Hàm ảnh hưởng Gaussian: 2 2 ( , ) 2( , ) d x y squaref x y e  Mặt khác, hàm mật độ tại điểm dx F được đinh nghĩa là tổng các hàm ảnh hưởng của tất ả các điểm dữ liệu. Cho n là các đối tượng dữ liệu được mô tả bởi một tập vecto  1,..., d nD x x F  hàm mật độ được định nghĩa như sau : ( ) 1 ( ) ( ) n D x i B B i F x F x   -60- Hàm mật độ được thành lập dựa trên ảnh hưởng Gauss được xác định như sau : 2 2 ( , ) 2 1 ( ) id x xn D Gauss i F d e    DENCLUE phụ thuộc nhiều vào ngưỡng nhiễu và tham số mật độ, nhưng DENCLUE có các lợi thế chính được so sánh với các thuật toán phân cụm khác sau đây : - Có cơ sở toán học vững chắc và tổng quát hóa các phương pháp phân cụm khác, bao gồm các phương pháp phân cấp, dựa trên phân hoạch - Có các đặc tính phân cụm tốt cho các tập dữ liệu với số lượng lớn và nhiễu - Cho phép các cụm có hình dạng bất kỳ trong tập dữ liệu đa chiều được mô tả trong công thức toán. Độ phức tạp tính toán của DENCLUDE là O(nlogn). Các thuật toán dựa trên mật độ không thực hiện kỹ thuật phân mẫu trên tập dữ liệu như trong các thuật toán phân cụm phân hoạch, vì điều này có thể làm tăng thêm độ phức tạp đã có sự khác nhau giữa mật độ của các đối tượng trong mẫu với mật độ của toàn bộ dữ liệu. 7. Thuật toán phân cụm dữ liệu dựa trên mẫu 7.1 Thuật toán EM Thuật toán EM được xem như là thuật toán dựa trên mẫu hoặc là mở rộng của thuật toán K-means. Thật vậy, EM gán các đối tượng cho các cụm đã cho theo xác suất phân phỗi thành phần của đối tượng đó. Phân phối xác suất thường được sử dụng là phân phối xác suất Gaussian với mục đích là khám phá lặp các giá trị tốt cho các tham số của nó bằng hàm tiêu chuẩn là hàm logarit khả năng của đối tượng dữ liệu, đây là hàm tốt để mô hình xác suất cho các đối tượng dữ liệu. EM có thể khám phá ra nhiều hình dạng cụm khác nhau, tuy nhiên do thời gian lặp của thuật toán khá nhiều nhằm xác định các tham số tốt nên chi phí tính toán của thuật toán khá cao. Đã có một số cải tiến được đề xuất cho EM dựa trên các tính chất của dữ liệu : có thể nén, có thể sao lưu trong bộ nhớ và có thể hủy bỏ. Trong các cải tiến này, các đối tượng bị hủy bỏ khi biết chắc chắn được nhãn phân cụm của nó, chúng được -61- nén khi không loại bỏ và thuộc về một cụm quá lớn so với bộ nhớ và chúng sẽ được lưu lại trong các trường hợp còn lại. Thuật toán được chia thành hai bước và quá trình đó được lặp lại cho đến khi vấn đề được giải quyết : - hbhaE         2 1 , 2 1 2 1 : - )(6 ,: dcb ba baM     1. Khởi tạo tham số :  )0()0(2)0(1)0()0(2)0(10 ,,,,,,, kK ppp    2. Bước E              k t j t iik t i t iik tk tjtjk tkj PxP PxP xP PxP xP )(2)( )(2)( ,, ,, , ,, ,     3. Bước M :       k tki kk tkit i xP xxP    , , )1(   R xP p k tkit i    , )1( 4. Lặp lại bước 2, 3 cho đến khi đạt kết quả 7.2 Thuật toán COBWEB COBWEB là cách tiếp cận để biểu diễn các đối tượng dữ liệu theo kiểu cặp thuộc tí