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



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
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
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


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-10-26-luan_van_phuong_phap_phan_cum_va_ung_dung.28FLXZbohl.swf /tai-lieu/de-tai-ung-dung-tren-liketly-42382/
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đă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:

đề 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ố thay mặt 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 hay 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...

---