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



MỤC LỤC
MỤC LỤC 1
CHƯƠNG 1. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 2
1.1. Phân cụm dữ liệu ? 2
1.2. Bài toán phân cụm 2
1.3. Các kiểu dữ liệu và độ tương tự trong PCDL 2
1.3.1. Phân loại các kiểu dữ liệu dựa trên kích thước miền 2
1.3.2. Phân loại các kiểu dữ liệu dựa trên hệ đo 2
1.3.3. Độ tương tự và phi tương tự 2
1.4. Các ứng dụng của phân cụm dữ liệu 3
CHƯƠNG 2. LÝ THUYẾT MỜ 4
2.1. Tập mờ 4
2.2. Số mờ 4
2.3. Quan hệ mờ 4
CHƯƠNG 3. THUẬT TOÁN PHÂN CỤM DỮ LIỆU VÀ PHÂN CỤM MỜ C-MEANS 6
3.1. Vấn đề phân cụm mờ 6
3.2. Thuật toán K-means 7
3.3. Thuật toán phân cụm mờ C-means (FCM) 8
3.3.1. Xây dựng hàm tiêu chuẩn 8
3.3.2. Thuật toán FCM 9
3.3.3. Ưu nhược điểm của thuật toán FCM 9
3.3.4. Ứng dụng của thuật toán FCM trong phâm cụm Gen chip (Microarray data) 10
CHƯƠNG 4. CÀI ĐẶT THỰC NGHIỆM 12
4.1. Các hàm của chương trình 12
4.2. Các biến của chương trình 12
4.3. Các lệnh thực hiện trong Matlab 13
CHƯƠNG 5. KẾT LUẬN 15
TÀI LIỆU THAM KHẢO 16
 
 


http://s1.liketly.com/flash/edoc/web-viewer.html?file=jh2i1fkjb33wa7b577g9lou48iyvfkz6-demo-2016-01-14-do_an_thuat_toan_phan_cum_du_lieu_mo_c_means_va_ung_dung_Ye4tG29ACR.png /tai-lieu/do-an-thuat-toan-phan-cum-du-lieu-mo-c-means-va-ung-dung-87358/


Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn.

Ket-noi - Kho tài liệu miễn phí lớn nhất của bạn


Ai cần tài liệu gì mà không tìm thấy ở Ket-noi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

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 hay là để tính độ tương tự (Similar) hay 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 hay 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 hay 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 ...

---