Tài liệu Phương pháp phân cụm và ứng dụng

ĐẠ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 : Mã số : KHOA HỌC MÁY TÍNH 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 http://www.lrc-tnu.edu.vn ĐẠ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 : Mã số : KHOA HỌC MÁY TÍNH 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 http://www.lrc-tnu.edu.vn -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 -5LỜ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 -6LỜ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 :  x11   x 21 D   x  n1 x12  x1d   x 22  x 2 d  ,      x n 2  x nd  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. Khai phá dữ liệu Phân loại Ước lượng Dự đoán Khai phá dữ liệu trực tiếp Khai phá dữ liệu gián tiếp Phân cụm Luật kết hợp Diễn giải và trực quan hóa 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 -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 -10cho 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- 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 Hình 2. Biểu đồ các dạng dữ liệu Quy mô dữ liệu Định lượng Danh nghĩa Định tính Giới hạn Tỷ lệ Khoảng 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 D  x1 , x 2  , x n  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 -12miề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 DOM v j   A j1 , A j 2 ,  , A jn j với j = 1, 2, … ,d. Gọi Ajl 1  l  n j 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  l  d ) là vecto định nghĩa là s j  A j1 , A j 2 ,, A jn j . T 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à Tf C    f1 C , f 2 C , , f d C , (2.2) Nơi f j C  là một vecto được định nghĩa   T f C   f j1 C , f j 2 C ,, f jn j C  , T (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 AA A A B B   B B C C C C    D D D D   Bảng 3 : Bảng biểu tượng của bộ dữ liệu trong bảng 1.  AB D A B C     B AC C C B   A D D D   Nơi fjr(C) (1  j  d ,1  r  n j ) là số điểm dữ liệu trong cụm C mà giá trị Ajr tại mảng thứ j, v.v f jr C   x  C : x j  A jr , (2.4) -13Nơ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 f jr D    f jr Ci  i 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 xi  0,11  i  d  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à xI x , 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 S ij x, y  i, j  0,1 biểu thị số lần xuất hiện của i trong x và j trong y tương ứng, ví dụ Sij x, y   k : xk  i và yk  j , k  1,2,, d  . (2.6) -14Sau đó, rõ ràng chúng ta có đẳng thức sau : d S11 x, y   x. y   xi yi , i 1 _ _ (2.7a) d S00 x, y   x . y   1  xi 1  yi , (2.7b) i 1 d _ S01 x, y   x . y   1  xi  yi , (2.7c) i 1 _ d S10 x, y   x. y   xi 1  yi , i 1 (2.7d) Ta cũng có : d  S 00  x, y   S 01  x, y   S10  x, y   S11  x, y . (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  3 3 3 311    0 0 0 011  0 011   Bảng5: Bảng tính toán tần số từ bảng biểu tượng trong bảng 3  3 0 0 311    0 3 0 011  3 011   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ụ D  t i : t i  I , i  1,2,  n. . 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à -15mộ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 D*  x1* , x2* ,, xn*  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 x , x ,, x  * 1 * T n * 2  x11*  * x   21    x*  n1 x12* * x22  xn* 2  x1*d    x2*d     *   xnd  (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à, xij  xij*  L j Mj (4.2) -18nơi xij biểu thị giá trị đã được chuẩn hóa, L j là vị trí đo, và M j 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 x *j , R *j 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à 1 n x   xij* n i 1 * j R*j  max xij*  min xij* , 1i  n 1i  n (4.3a) (4.3b) 1  1 n * 2  *j   ( xij  x *j )2    n  1 i 1  (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à   xij  Z1 x  * ij xij*  x *j  *j (4.4) Nơi x *j ,  *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 -19sẽ đượ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 x *j , R *j và  *j được định nghĩa trong biểu thức 4.3 Tên Lj Lj z-score x *j  *j USTD 0  *j Maxium 0 max xij* Mean x *j 1 1 i  n x *n 1 nếu n là lẻ Median 2 j 1  1 *  xn  x*n  2  nếu n là chẵn  j 2 2j 2  Sum 0 n x * ij i 1 min xij* Range 1i  n R *j 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à   xij  Z 2 xij*  xij*  *j (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:   xij  Z 3 x * ij xij* max xij* 1i  n (4.6)