Đồ án Thuật toán phân cụm dữ liệu mờ C-Means và ứng dụng

MỤC LỤC CHƯƠNG 1. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1.1. Phân cụm dữ liệu ? “PCDL là một kỹ thuật trong Data Mining, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập dữ liệu lớn. Từ đó cung cấp thông tin tri thức hữu ích để đưa ra quyết định”. 1.2. Bài toán phân cụm Cho một tập dữ liệu X={X1,X2,,XN}, phân cụm có nhiệm vụ chia tập X thành K phân hoạch {C1,C2,,CK} đôi một tách rời. 1.3. Các kiểu dữ liệu và độ tương tự trong PCDL 1.3.1. Phân loại các kiểu dữ liệu dựa trên kích thước miền Thuộc tính liên tục (Continuons Attribute) Thuộc tính rời rạc (DiscretteAttribute) Thuộc tính nhị phân 1.3.2. Phân loại các kiểu dữ liệu dựa trên hệ đo Giả sử rằng chúng ta có 2 đối tượng x,y và các thuộc tính xi, yi tương ứng với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau: Thuộc tính định danh (Nominal Scale) Thuộc tính có thứ tự (Ordinal Scale) Thuộc tính khoảng (Interval Scale) Thuộc tính tỉ lệ (Ratio Scale) 1.3.3. Độ tương tự và phi tương tự Khi xác định được các đặc tính của dữ liệu, thì người ta tiến hành xác định “khoảng cách” giữa các đối tượng – hay là độ đo tương tự. Đây là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống nhau giữa các đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ nghịch với hàm tính độ tương tự. 1.4. Các ứng dụng của phân cụm dữ liệu Phân cụm dữ liệu là một trong những công cụ chính được ứng dụng trong nhiều lĩnh vực khác nhau như: Thương mại Sinh học Lập quy hoạch đô thị Địa lý Web Mining CHƯƠNG 2. LÝ THUYẾT MỜ 2.1. Tập mờ Định nghĩa: A là tập mờ trên không gian nền X nếu A được xác định bởi hàm: µA : X → [0,1] Trong đó: µA là hàm thuộc. µA(x) là độ thuộc của x vào tập mờ A Có thể ký hiệu A = {( µA(x), x ): x Є X} Việc µA(x) có giá trị bất kỳ trong khoảng [0,1] là điều khác biệt cơ bản giữa tập rõ và tập mờ. Ở tập rõ hàm thuộc chỉ có 2 giá trị: + µA(x) = 1 nếu x Є A + µA(x) ≠ 0 nếu x A 2.2. Số mờ Tập mờ M trên tập số thực R1 là một số thực mờ nếu: + M chuẩn hóa – tức có điểm x’ sao cho µM (x’) = 1. + Ứng với mỗi α Є R1 tập mức {x: µM (x) ≥ α} là đoạn đóng trên R1. Có 3 dạng số mờ cơ bản: - Số mờ hình Singleton - Số mờ hình tam giác - Số mờ hình thang 2.3. Quan hệ mờ Định nghĩa 1: Cho 2 không gian nền X,Y. R là một quan hệ mờ trên X x Y nếu R là một tập mờ trên X x Y, tức có một hàm thuộc µR : X x Y → [0,1] Trong đó, µR ( x,y ) = R(x,y) là độ thuộc (Membership Degree) của x, y vào quan hệ R. Định nghĩa 2: Quan hệ mờ trên những tập mờ Cho: Tập mờ A với µA(x) trên X Tập mờ B với µB(x) trên Y Quan hệ mờ trên các tập A, B là quan hệ mờ R trên X x Y thỏa mãn điều kiện: + µR (x,y) ≤ µA(x) với mọi y Є Y + µR (x,y) ≤ µB (x) với mọi y Є Y CHƯƠNG 3. THUẬT TOÁN PHÂN CỤM DỮ LIỆU VÀ PHÂN CỤM MỜ C-MEANS 3.1. Vấn đề phân cụm mờ Thông thường, mỗi phương pháp phân cụm dữ liệu phân một tập dữ liệu ban đầu thành các cụm dữ liệu có tính tự nhiên và mỗi đối tượng dữ liệu chỉ thuộc về một cụm dữ liệu. Phương pháp này chỉ phù hợp với việc khám phá ra các cụm có mật độ cao và rời nhau. Tuy nhiên, trong thực tế các cụm dữ liệu lại có thể chồng lên nhau, nghĩa là một số các đối tượng dữ liệu thuộc về nhiều cụm khác nhau, người ta áp dụng lý thuyết tập mờ trong PCDL để giải quyết trường hợp này, cách thức kết hợp này gọi là phân cụm mờ. Thuật toán phân cụm mờ C-means được kế thừa và phát triển tư tưởng của thuật toán phân cụm rõ K-means. Cả hai thuật toán này đều sử dụng chung một chiến lược đó là phân cụm dữ liệu. Thuật toán phân cụm dữ liệu mờ C-means hay còn gọi tắt là thuật toán FCM (Fuzzy C-means) đã được áp dụng thành công trong việc giải quyết một số các bài toán như trong nhận dạng mẫu, xử lý ảnh, y học, InPut : Số cụm k và các trọng tâm cụm {mj}kj=1 ; OutPut : Các cụm Ci () 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 {mj}kj=1 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 Xi (1<=i<=n), tính toán khoảng cách của nó tới mỗi trọng tâm mj j=1,k. Và sau đó tìm trọng tâm gần nhất đối với mỗi điểm. Bước 3 : Cập nhật lại trọng tâm Đối với mỗi j=1,k , cập nhật trọng tâm cụm mj bằng các xác định trung bình cộng của các vectơ đối tượng dữ liệu. Bước 4 : Điều kiện dừng Lặp lại bước 2, bước 3 cho đến khi nào các trọng tâm của cụm không thay đối. End 3.2. Thuật toán K-means Nhận xét: Độ phức tạp của thuật toán là với T là số lần lặp, n là số đối tượng của tập dữ liệu đưa vào. Do K-means phân tích phân cụm đơn giản nên có thể áp dụng đối với tập dữ liệu lớn. Tuy nhiên, nhược điểm của K-means đó là chỉ áp dụng được với dữ liệu có thuộc tính số và phát hiện ra các cụm có hình cầu. K-means còn rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Chất lượng phân cụm của thuật toán K-means phụ thuộc nhiều vào tham số đầu vào như: số cụm k và các trọng tâm của cụm. Đến nay, đã có rất nhiều thuật toán kế thừa tư tưởng của thuật toán K-means áp dụng trong khai phá tri thức để giải quyết các tập dữ liệu có kích thước rất lớn đang được áp dụng hiệu quả và phổ biến như: k-modes, PAM, CLARA, k-prototypes,và đặc biệt là C-means. 3.3. Thuật toán phân cụm mờ C-means (FCM) 3.3.1. Xây dựng hàm tiêu chuẩn Trong phân cụm dữ liệu mờ, tổng tất cả các phân hoạch mờ có c cụm dữ liệu của tập dữ liệu có N đối tượng trong không gian D chiều được xác định như sau: (1) Trong đó: - RcN : là không gian của tất cả các ma trận thực cấp c*N. - Uik : là các phần tử của ma trận U. Khi đó, hàm tiêu chuẩn của thuật toán FCM được định nghĩa như sau: (2) Trong đó: - U Є Efc - V = [V1,V2,,Vc] Є Rpc là ma trận mẫu biểu diễn các giá trị đối tượng tâm của cụm. - m : là trọng số mũ trong [1,). - (3) Trong đó: A là ma trận hữu hạn dương. Họ các tiêu chuẩn được xác định trong công thức (2) với tham số mũ m Є [1,) được đề xuất bởi Bezdek (1982). Sau đây là các điều kiện cần thiết nhằm tối thiểu hàm tiêu chuẩn Jm(U,V): Định lý : Nếu m và c là các tham số cố định và Ik là một tập thì được định nghĩa như sau: (4) Khi đó, hàm tiêu chuẩn đạt giá trị tối thiểu khi và chỉ khi: (5) Và (6) Như vậy, để phân hoạch tối ưu thì hàm tiêu chuẩn phải đạt giá trị tối thiểu, nghĩa là phải thỏa mãn (5),(6). Từ đó, người ta tiến hành xây dựng thuật toán phân cụm dữ liệu mờ C-means. 3.3.2. Thuật toán FCM Input : Số cụm c và tham số mũ m cho hàm tiêu chuẩn J OutPut : c cụm dữ liệu sao cho hàm tiêu chuẩn trong (2) đạt giá trị tối thiểu. Begin 1. Nhập giá trị cho hai tham số c (1<c<N), m và khởi tạo ma trận mẫu 2. Repeat 2.1 j=j+1; 2.2 Tính ma trận phân hoạch mờ Uj theo công thức (5) 2.3 Cập nhật các trọng tâm V(j) = [v1(j), v2(j), , vc(j) ] dựa vào (6) và ma trận Uj; 3. Until (|| U(j+1) – U(j) ||F ); 4. Trình diễn các cụm kết quả. End Hiện nay, chưa có quy tắc nào nhằm lựa chọn tham số m đảm bảo cho việc phân cụm hiệu quả, thông thường người ta chọn m = 2. 3.3.3. Ưu nhược điểm của thuật toán FCM Ưu điểm: Cải thiện được chất lượng phân cụm dữ liệu Nhược điểm: Nhạy cảm với nhiễu và các 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 các cụm trong thực tế. Vì vậy, việc khử nhiễu và các phần tử ngoại lai là một vấn đề cần được giải qưyết. 3.3.4. Ứng dụng của thuật toán FCM trong phâm cụm Gen chip (Microarray data) 3.3.4.1. Các tập dữ liệu được sử dụng: Tập dữ liệu Serum: serum.txt Tập dữ liệu Yeast : yeast.txt (sử dụng các dữ liệu ngẫu nhiên) Human cancer dataset : hc728g.txt Iris dataset : iris.txt Synthetic dataset 1 : y3c.txt Synthetic dataset 2 : y14c.txt 3.3.4.2. Dữ liệu thực nghiệm: Sử dụng Tập dữ liệu Iris, chúng ta chạy thuật toán FCM với các giá trị khác nhau cho tham số m. 30 giá trị độc lập được sử dụng. Mỗi lần chạy, trường hợp K=3 hoặc K =2, với tâm khởi tạo là giá trị ngẫu nhiên. Sau khi tập hợp các kết quả thu được, giải pháp đưa ra là giá trị nhỏ nhất cho J(K,m) được lưu giữ, và chúng ta ước lượng được giá trị Umax và Umin. Với các giá trị khác nhau của m ta thu được 2 bảng thống kê sau: FCM Sample statistics of Ym m Umin Umax means(Ym) std(Ym) cv(Ym) cv(Ym)/4 2.0 0.024 0.857 9.1386 9.666 1.0577 0.2644 5.0 0.193 0.524 1.4998 0.5425 0.3617 0.0904 8.0 0.248 0.439 1.2384 0.2706 0.2185 0.0546 10.0 0.267 0.415 1.1758 0.2034 0.173 0.433 13.0 0.283 0.397 1.1258 0.1488 0.1322 0.033 15.0 0.290 0.38 1.1056 0.1264 0.1144 0.0286 18.0 0.297 0.375 1.0851 0.1035 0.0954 0.0286 20.0 0.30 0.37 1.0753 0.0925 0.086 0.0215 25.0 0.30 0.36 1.0585 0.0735 0.0694 0.0174 30.0 0.31 0.35 1.0478 0.0614 0.0694 0.0174 35.0 0.315 0.354 1.0403 0.0531 0.0511 0.0128 40.0 0.315 0.357 1.0349 0.0477 0.0455 0.0114 Bảng 1: Iris dataset, K=3, search for mub FCM Sample statistics of Ym m Umin Umax means(Ym) std(Ym) cv(Ym) cv(Ym)/4 2.0 0.067 0.933 9.1386 9.666 1.0577 0.2644 5.0 0.306 0.693 1.4998 0.5425 0.3617 0.0904 8.0 0.38 0.616 1.2384 0.2706 0.2185 0.0546 10.0 0.409 0.59 1.1758 0.2034 0.173 0.433 13.0 0.431 0.568 1.1258 0.1488 0.1322 0.033 15.0 0.441 0.558 1.1056 0.1264 0.1144 0.0286 18.0 0.451 0.548 1.0851 0.1035 0.0954 0.0286 20.0 0.456 0.543 1.0753 0.0925 0.086 0.0215 25.0 0.465 0.534 1.0585 0.0735 0.0694 0.0174 30.0 0.471 0.528 1.0478 0.0614 0.0694 0.0174 35.0 0.476 0.524 1.0403 0.0531 0.0511 0.0128 40.0 0.478 0.521 1.0349 0.0477 0.0455 0.0114 Bảng 2: Iris dataset, K=2, search for mub Ngoài ra, còn một số tập dữ liệu khác như: Tập dữ liệu Synthetic 1 Tập dữ liệu Synthetic 2 Tập dữ liệu Serum Tập dữ liệu Yeast 3.3.4.3. Lưu đồ tính giá trị cận trên cho m CHƯƠNG 4. CÀI ĐẶT THỰC NGHIỆM Trong chương này tiến hành cài đặt chương trình với thuật toán FCM (Fuzzy C-Means) và chạy thử nghiệm trên bộ dữ liệu chuẩn có sẵn để phân nhóm những nhóm Gen chip. Ngôn ngữ lập trình được sử dụng trong chương trình là ngôn ngữ Matlab. Ngôn ngữ lập trình này hỗ trợ trong rất nhiều ứng dụng như: Dùng để xây dựng các chương trình giải quyết các bài toán về toán học. Xây dựng các chương trình mô phỏng. Xây dựng các chương trình thống kê. Hỗ trợ xây dựng các chương trình đồ họa (2D, 3D) Đặc biệt, nó hỗ trợ hệ logic mờ, cung cấp các thư viện về các hàm dữ liệu logic mờ. Vì vậy, việc chọn lựa ngôn ngữ lập trình Matlab trong chương trình ứng dụng này sẽ tận dụng được các thư viện sẵn có nhằm hỗ trợ trong quá trình xây dựng chương trình. 4.1. Các hàm của chương trình function vDist = calcDataDist(Xdat); function [mub,it] = calcMub(Xdat,seuil,itmax,epsilon); function [moy,dev,cv,cvp] = calcStatYm(Y,m,p); function [Umat,Cmat,it,valJ] = fcm(Xdat,K,mfuz,epsilon,itmax); function Cmat = fcm_calcC(Xdat,K,mfuz,Umat); function Dmat = fcm_calcD(Xdat,Cmat); function Umat = fcm_calcU(mfuz,Dmat); function Cmat = fcm_dataInitC(Xdat,K); function valJ = fcm_evalJ(Umat,mfuz,Dmat); function [mub,it] = searchMub(vDist,cv_mub,epsilon,itmax); 4.2. Các biến của chương trình - Xdat : ma trận có kích thước [M,N] + M: Số các cuộc thí nghiệm + N: Số các Gen it: số lần lặp itmax: Số lần lặp lớn nhất để phân cụm mfuz: Tham số mờ m K: Số các cụm Cmat: Ma trận trọng tâm có kích thước [M,K] Umat: Ma trận phân cụm mờ có kích thước [K,N] Dmat: Ma trận khoảng cách có kích thước [K,N] mub: giá trị cận dưới của tham số m moy: tâm dev: độ lệch chuẩn 4.3. Các lệnh thực hiện trong Matlab % Khởi tạo ma trận Xdat >> Xdat = [M,N] % M: số các cuộc thí nghiệm (M = 150) % N: Số các Gen % Khởi tạo K cụm ngẫu nhiên (thông thường K = 2 hoặc K = 3) >> K = 2 % 1. Xác định giá trị tâm cụm ngẫu nhiên >> Cmat = fcm_dataInitC(Xdat,K) % Khởi tạo các giá trị: mfuz, epsilon, itmax >> mfuz = 2 >> epsilon = 0.001 >> itmax = 500 % 2. Xác định hàm phân cụm mờ >> [Umat,Cmat,it,valJ] = fcm(Xdat,K,mfuz,epsilon,itmax) % 3. Tính khoảng cách giữa các phần tử trong tập dữ liệu >> vDist = calcDataDist(Xdat) % Khởi tạo giá trị cho các biến:Y,m,p >> Y = [M,1] >> m = 2 % m: tham số mờ m >> p = 150 % p: Số các thí nghiệm % 4. Tính tâm, độ lệch chuẩn và hệ số khoảng cách trong tập dữ liệu >> [moy,dev,cv,cvp] = calcStatYm(Y,m,p) % 5. Cập nhật lại các trọng tâm >> Cmat = fcm_calcC(Xdat,K,mfuz,Umat) % 6. Tính ma trận khoảng cách giữa tập dữ liệu và tập các cụm >> Dmat = fcm_calcD(Xdat,Cmat) % 7. Phân chia các phần tử dữ liệu vào các cụm dùng ma trận khoảng cách >> Umat = fcm_calcU(mfuz,Dmat) % 8. Xác định giá trị hàm tiêu chuẩn J >> valJ = fcm_evalJ(Umat,mfuz,Dmat) % Khởi tạo giá trị cho biến seuil >> seuil = 0.03 % 9. Xác định cận trên của tham số m >> [mub,it] = calcMub(Xdat,seuil,itmax,epsilon) % 10. Tìm cận trên cho tham số m >>[mub,it] = searchMub(vDist,cv_mub,epsilon,itmax) CHƯƠNG 5. KẾT LUẬN Từ khi cuộc cách mạng công nghệ số bùng nổ, khối lượng dữ liệu ngày càng lớn, nhu cầu khai thác thông tin hữu ích từ một lượng dữ liệu khổng lồ là rất cần thiết đối với mỗi cá nhân, tổ chức hay bất kỳ một doanh nghiệp nào. Vì vậy, việc nghiên cứu các phương pháp phân cụm dữ liệu là việc làm rất cần thiết và có ý nghĩa quan trọng trong khoa học cũng như trong thực tiễn. Trong luận văn này, tôi đã trình bày tổng quan về phân cụm dữ liệu và những ứng dụng của nó trong các lĩnh vực khác nhau như: Thương mại, Sinh học,Trong chương 2 và chương 3, luận văn đã đi vào nghiên cứu một trong những phương pháp phân cụm dữ liệu, áp dụng lý thuyết mờ, nhằm phát hiện ra các cụm dữ liệu chồng lên nhau. Đó là phương pháp phân cụm mờ C-means được cải tiến từ phương pháp phân hoạch K-means. Cuối cùng, là chương trình thử nghiệm áp dụng thuật toán phân cụm mờ C-means (FCM – Fuzzy C-means) để phân nhóm những nhóm Gen chip DNA Tóm lại, với một lượng thông tin khổng lồ như hiện nay, thì việc các dữ liệu đó bị chồng khít lên nhau là điều không thể tránh khỏi. Vì vậy, việc nghiên cứu phương pháp phân cụm dữ liệu mờ C-means cũng đang bắt đầu được quan tâm – Đây là một lĩnh vực có phạm vi nghiên cứu và ứng dụng rất rộng rãi. Do thời gian nghiên cứu và trình độ có hạn, luận văn không tránh khỏi những hạn chế và thiếu sót. Rất mong được tiếp thu những ý kiến đóng góp, sự đánh giá, chỉ bảo của các thầy cô giáo, bạn bè và đồng nghiệp. TÀI LIỆU THAM KHẢO [1]. Hoàng Hải Xanh - Thuật toán phân cụm dữ liệu trong Data Mining, ĐHQGHN, luận văn thạc sỹ. [2]. Hệ mờ, mạng Nơ ron và ứng dụng - Bùi Công Cường, Nguyễn Doãn Phước, NXB Khoa học Kỹ thuật [3]. R.C.Dubes Algorithms for clustering Data, Prentice-Hall, Englewood Cliffs,1998 [4]. M-S Chen,Wang, Fuzzy clustering analyis for optimizing fuzzy membership function,1999. [5]. N.R.Pal, J.C. Bezdek, On cluster validity for the c-means mode, IEEE Trans.Fuzzy Systems 3 (1995) 370-379 [6]. X.L Xie-Ben, A validity measure for fuzzy clustering, IEEE Trans, Partarn Anal, 1991. [7] Fuzzy C-Means for Clustering Microarray Data [8] [9] [10] [11] ftp://ftp.ics.uci.edu/pub/machine-learning-databases/