hongchau1088
New Member
Link tải luận văn miễn phí cho ae Kết nối
Miêu tả:Luận văn ThS. Công nghệ phần mềm -- Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2011
Phân cụm dữ liệu nhằm phân chia dữ liệu thành nhiều cụm, trong đó các phẩn tử trong một cụm giống nhau nhiều hơn các phần tử khác cụm, là một phần quan trọng trong phân tích thống kê nhiều chiều và học máy không giám sát. Bài toán này có nhiều ứng dụng trong các lĩnh vực khác nhau như: Gian lận tài chính, chẩn đoán trong y tế, xử lý hình ảnh, tìm kiếm thông tin, tin sinh học.
CHƢƠNG 1: GIỚI THIỆU VỀ KHÁM PHÁ TRI THỨC VÀ PHÂN CỤM DỮ LIỆU. 11
1.1. Khám phá tri thức ....................................................................................................11
1.2. Phân cụm dữ liệu .....................................................................................................12
1.3. Vấn đề chuẩn hóa dữ liệu ........................................................................................13
1.4. Các ứng dụng của phân cụm dữ liệu........................................................................15
1.5. Mêtric trên dữ liệu hỗn hợp. ....................................................................................16
1.6. Độ tƣơng đồng .........................................................................................................19
CHƢƠNG 2. MỘT SỐ PHƢƠNG PHÁP PHÂN CỤM CHÍNH..................................... 22
2.1. Phƣơng pháp phân hoạch.........................................................................................22
2.1.1. Thuật toán K-Means..........................................................................................24
2.1.2. Thuật toán phân cụm K-centroid ......................................................................26
2.2. Phƣơng pháp phân cấp.............................................................................................26
2.2.1. Thuật toán BIRCH ............................................................................................28
2.2.2. Thuật toán ROCK .............................................................................................30
2.3. Phƣơng pháp phân cụm dựa trên mật độ. ................................................................31
2.4. Phƣơng pháp phân cụm dựa trên lƣới......................................................................33
CHƢƠNG 3: PHÂN CỤM DỮ LIỆU VỚI THUỘC TÍNH ĐỊNH DANH ..................... 36
3.1. Mode và thuật toán k-modes....................................................................................37
3.1.1. Mode của tập dữ liệu hỗn hợp...........................................................................37
3.1.2. Thuật toán k-modes...........................................................................................40
2
3.2. Thuật toán K-Prototypes..........................................................................................40
3.3. Thuật toán k-modes có trọng số...............................................................................41
3.4. Thuật toán k-modes cho dữ liệu hỗn hợp có trọng số. ............................................46
3.5. Entropy và thuật toán COOLCAT...........................................................................55
3.5.1. Entropy và cụm .................................................................................................55
3.5.2. Vấn đề về công thức..........................................................................................58
3.5.3. Thuật toán COOLCAT ......................................................................................59
3.6. Tiêu chuẩn đánh giá chất lƣợng phân cụm..............................................................64
CHƢƠNG 4: KẾT QUẢ THỬ NGHIỆM......................................................................... 64
4.1. Giới thiệu .................................................................................................................64
4.2. Chƣơng trình và dữ liệu thử nghiệm........................................................................64
4.2.1. Chƣơng trình .....................................................................................................64
4.2.2. Dữ liệu thử nghiệm. ..........................................................................................65
4.3. Kết quả thử nghiệm ................................................................................................ 67
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ........................................................................ 74
TÀI LIỆU THAM KHẢO ................................................................................................. 75
PHỤ LỤC .......................................................................................................................... 78
Phân cụm dữ liệu nhằm chia tập dữ liệu thành nhiều cụm, trong đó các phần tử trong một
cụm giống nhau nhiều hơn các phần tử khác cụm, là một phần quan trọng trong phân tích
thống kê nhiều chiều và học máy không giám sát. Bài toán này có nhiều ứng dụng trong
các lĩnh vực khác nhau nhƣ: gian lận tài chính, chẩn đoán trong y tế, xử lý hình ảnh, tìm
kiếm thông tin, tin sinh học.
Những thuật toán phân cụm đầu tiên làm việc với các đặc trƣng số nhƣ là một phần
của thống kê toán [15]. Cùng với sự phát triển của ứng dụng công nghệ thông tin, khối
lƣợng dữ liệu tăng nhanh đòi hỏi phát triển các kỹ thuật khám phá tri thức trên các dạng
dữ liệu khác nhau trên dữ liệu lớn với độ phức tạp thấp. Mặt khác các kỹ thuật khám phá
tri thức thƣờng phải làm việc với dữ liệu quan hệ nhiều chiều với các thuộc tính giá trị
định danh [16]. Trong trƣờng hợp đó việc phân dữ liệu thành các nhóm con có độ tƣơng
tự cao trong mỗi nhóm để xử lý sẽ giảm đáng kể thời gian chạy cho các thuật toán và tăng
chất lƣợng của kỹ thuật khám phá tri thức.
Bài toán phân cụm dữ liệu thuộc loại “thiết lập không đúng đắn” theo nghĩa lời giải
thƣờng không duy nhất và thay đổi nhiều khi dữ liệu thay đổi ít. Vì vậy ngƣời ta có nhiều
cách tiếp cận dựa trên quan sát tổng thể tập dữ liệu để áp dụng thuật toán thích hợp. Khi
số chiều cao, ngoài khối lƣợng tính toán tăng lên, dữ liệu phân bố “thƣa” nên việc quan
sát dữ liệu để phân tích đặc điểm hình học cũng rất khó khăn nên phân cụm khó hiệu quả.
Một cách tiếp cận cho dữ liệu chiều cao là chiếu chúng lên không gian có chiều thấp hơn,
chẳng hạn, các phƣơng pháp: CLIQUE[2], ENCLUS[6], MAFIA[19], Proclus[4],
ORCLUS[5], FINDIT[13], DOC [7], d-clusters[9], HARP[14] và LDR[11] cho dữ liệu
số.
Trong các phƣơng pháp phân cụm, thuật toán k-means do MacQueen (1967 ) đề
xuất có độ phức tạp thấp, thích hợp với dữ liệu lớn và có số chiều cao. Ban đầu thuật toán
này đƣợc dùng cho dữ liệu số sau đó đƣợc phát triển thành thuật toán k-modes cho các
dữ liệu định danh. Tuy nhiên khi dữ liệu nhiều chiều, việc xem đồng thời các thuộc tính
nhƣ nhau khi phân cụm ở thuật toán này không thích hợp và ngƣời ta phát triển nhiều
thuật toán mới.
Để giải quyết hiệu quả vấn đề này, luận văn đã trình bày một số thuật toán tối ƣu
hoá để so sánh phân nhóm dữ liệu phân loại chiều cao.
Trong các thuật toán trình bày, một kỹ thuật trọng số mới phân loại dữ liệu đƣợc
đƣa ra để tính toán trọng số cho mỗi thuộc tính (hay chiều) trong mỗi cụm và sử dụng
các giá trị trọng số để xác định tập hợp con cuả các thuộc tính quan trọng mà phân loại
cụm khác nhau.
Các nghiên cứu thực nghiệm cho thấy rằng các thuật toán đề xuất có hiệu quả
trong nhóm phân loại tập hợp dữ liệu và cũng có khả năng mở rộng dữ liệu lớn với độ
phức tạp là tuyến tính.
Ngoài phần kết luận luận văn đƣợc trình bày thành 4 chƣơng với nội dung đƣợc
trình bày nhƣ sau:
Chƣơng 1: Giới thiệu về khám phá tri thức và phân cụm dữ liệu. Trình bày cách biểu
diễn dữ liệu trong máy tính nhằm phục vụ cho quá trình phân cụm, giới thiệu độ tƣơng
đồng giữa các đối tƣợng trong tập dữ liệu, các phƣơng pháp phân cụm dữ liệu.
Chƣơng 2: Một số phƣơng pháp phân cụm chính.
Ở chƣơng này với mỗi phƣơng pháp phân cụm sẽ trình bày một số thuật toán
chính. Tƣ tƣởng của phƣơng pháp phân hoạch là tìm cách phân chia tập dữ liệu thành các
tập không giao nhau, thỏa mãn điều kiện làm tối ƣu hàm đánh giá. Trong mỗi tập con
thƣờng có ít nhất một phần tử đại diện, phần tử thay mặt thƣờng là tâm của tập con đó.
Mỗi đối tƣợng trong tập dữ liệu đƣợc phân vào cụm có điểm thay mặt gần với đối tƣợng
đó nhất. Quá trình này lặp đi lặp lại cho tới khi hàm mục tiêu không thay đổi. Phƣơng
pháp phân cấp phân tách các tập đối tƣợng theo hai cách: Tiếp cận từ dƣới lên (Bottom
Up) hay trên xuống (Top-Down). Tiếp cận từ dƣới lên bắt đầu với mỗi đối tƣợng đƣợc
xem nhƣ một nhóm, sau đó gộp các đối tƣợng hay các nhóm theo các hàm nhƣ hàm
khoảng cách giữa các tâm của hai nhóm và điều này đƣợc thực hiện cho tới khi tất cả các
nhóm đƣợc gộp vào làm một nhóm hay cho tới khi điều kiện kết thúc đƣợc thỏa mãn.
Tiếp cận theo phƣơng pháp từ trên xuống bắt đầu với tất cả các đối tƣợng nằm trong cùng
một cụm. Trong mỗi lần lặp, một cụm đƣợc tách ra thành các cụm nhỏ hơn theo một ƣớc
lƣợng nào đó. Điều này đƣợc thực hiện cho tới khi mỗi đối tƣợng là một cụm, hay cho
tới khi điều kiện kết thúc thỏa mãn. Đối với phƣơng pháp đƣợc phát triển dựa trên quan
niệm về mật độ. Các cụm tiêu biểu đƣợc xét là các vùng có các đối tƣợng tập trung đậm
đặc và đƣợc phân chia bởi các vùng có mật độ thấp (đặc trƣng cho nhiễu). Các phƣơng
pháp dựa trên mật độ có thể sử dụng để lọc ra các nhiễu (phần tử ngoại lai), và khám phá
ra các cụm có hình dạng bất kỳ. Cách tiếp cận dựa trên lƣới sử dụng cấu trúc lƣới của dữ
liệu. Nó lƣợng tử hóa khoảng cách vào một số hữu hạn các ô là cấu trúc dạng lƣới để tất
cả các phép toán phân cụm thực hiện đƣợc.
Chƣơng 3: Phân cụm dữ liệu với thuộc tính định danh
Với dữ liệu tồn tại trong tự nhiên là rất lớn và phong phú. Trong khuôn khổ luận
văn quan tâm đến việc phân cụm dữ liệu định danh. Ở chƣơng này chúng tui có trình bày
một số thuật toán, trong đó đi sâu vào hai thuật toán COOLCAT và MWKM để phân cụm
dữ liệu định danh với nhiều thuộc tính. Luận văn cũng đã so sánh đƣợc ƣu, nhƣợc điểm
của hai thuật toán này thông qua kết quả thực nghiệm ở chƣơng 4.
Chƣơng 4: Kết quả thực nghiệm
Luận văn đã trình bày kết quả thực nghiệm so sánh hai thuật toán COOLCAT và
MWKM với 5 bộ dữ liệu với nhiều thuộc tính: Cơ sở dữ liệu đậu tƣơng, cơ sở dữ liệu
nấm, cơ sở dữ liệu ung thƣ phổi, CSDL về thuê bao di động phát sinh của thành phố Hà
Nội và CSDL điều tra dân số của Mỹ năm 1990. Các hàm mục tiêu để đánh giá chất
lƣợng phân cụm là CU, ARI và ER đã đƣợc trình bày kỹ trong chƣơng 3.
Cuối cùng là kết luận, hƣớng phát triển, tài liệu tham khảo và phụ lục. Phần kết luận trình
bày tóm tắt kết quả thu đƣợc và đề xuất hƣớng nghiên cứu tiếp theo.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Miêu tả:Luận văn ThS. Công nghệ phần mềm -- Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2011
Phân cụm dữ liệu nhằm phân chia dữ liệu thành nhiều cụm, trong đó các phẩn tử trong một cụm giống nhau nhiều hơn các phần tử khác cụm, là một phần quan trọng trong phân tích thống kê nhiều chiều và học máy không giám sát. Bài toán này có nhiều ứng dụng trong các lĩnh vực khác nhau như: Gian lận tài chính, chẩn đoán trong y tế, xử lý hình ảnh, tìm kiếm thông tin, tin sinh học.
CHƢƠNG 1: GIỚI THIỆU VỀ KHÁM PHÁ TRI THỨC VÀ PHÂN CỤM DỮ LIỆU. 11
1.1. Khám phá tri thức ....................................................................................................11
1.2. Phân cụm dữ liệu .....................................................................................................12
1.3. Vấn đề chuẩn hóa dữ liệu ........................................................................................13
1.4. Các ứng dụng của phân cụm dữ liệu........................................................................15
1.5. Mêtric trên dữ liệu hỗn hợp. ....................................................................................16
1.6. Độ tƣơng đồng .........................................................................................................19
CHƢƠNG 2. MỘT SỐ PHƢƠNG PHÁP PHÂN CỤM CHÍNH..................................... 22
2.1. Phƣơng pháp phân hoạch.........................................................................................22
2.1.1. Thuật toán K-Means..........................................................................................24
2.1.2. Thuật toán phân cụm K-centroid ......................................................................26
2.2. Phƣơng pháp phân cấp.............................................................................................26
2.2.1. Thuật toán BIRCH ............................................................................................28
2.2.2. Thuật toán ROCK .............................................................................................30
2.3. Phƣơng pháp phân cụm dựa trên mật độ. ................................................................31
2.4. Phƣơng pháp phân cụm dựa trên lƣới......................................................................33
CHƢƠNG 3: PHÂN CỤM DỮ LIỆU VỚI THUỘC TÍNH ĐỊNH DANH ..................... 36
3.1. Mode và thuật toán k-modes....................................................................................37
3.1.1. Mode của tập dữ liệu hỗn hợp...........................................................................37
3.1.2. Thuật toán k-modes...........................................................................................40
2
3.2. Thuật toán K-Prototypes..........................................................................................40
3.3. Thuật toán k-modes có trọng số...............................................................................41
3.4. Thuật toán k-modes cho dữ liệu hỗn hợp có trọng số. ............................................46
3.5. Entropy và thuật toán COOLCAT...........................................................................55
3.5.1. Entropy và cụm .................................................................................................55
3.5.2. Vấn đề về công thức..........................................................................................58
3.5.3. Thuật toán COOLCAT ......................................................................................59
3.6. Tiêu chuẩn đánh giá chất lƣợng phân cụm..............................................................64
CHƢƠNG 4: KẾT QUẢ THỬ NGHIỆM......................................................................... 64
4.1. Giới thiệu .................................................................................................................64
4.2. Chƣơng trình và dữ liệu thử nghiệm........................................................................64
4.2.1. Chƣơng trình .....................................................................................................64
4.2.2. Dữ liệu thử nghiệm. ..........................................................................................65
4.3. Kết quả thử nghiệm ................................................................................................ 67
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ........................................................................ 74
TÀI LIỆU THAM KHẢO ................................................................................................. 75
PHỤ LỤC .......................................................................................................................... 78
Phân cụm dữ liệu nhằm chia tập dữ liệu thành nhiều cụm, trong đó các phần tử trong một
cụm giống nhau nhiều hơn các phần tử khác cụm, là một phần quan trọng trong phân tích
thống kê nhiều chiều và học máy không giám sát. Bài toán này có nhiều ứng dụng trong
các lĩnh vực khác nhau nhƣ: gian lận tài chính, chẩn đoán trong y tế, xử lý hình ảnh, tìm
kiếm thông tin, tin sinh học.
Những thuật toán phân cụm đầu tiên làm việc với các đặc trƣng số nhƣ là một phần
của thống kê toán [15]. Cùng với sự phát triển của ứng dụng công nghệ thông tin, khối
lƣợng dữ liệu tăng nhanh đòi hỏi phát triển các kỹ thuật khám phá tri thức trên các dạng
dữ liệu khác nhau trên dữ liệu lớn với độ phức tạp thấp. Mặt khác các kỹ thuật khám phá
tri thức thƣờng phải làm việc với dữ liệu quan hệ nhiều chiều với các thuộc tính giá trị
định danh [16]. Trong trƣờng hợp đó việc phân dữ liệu thành các nhóm con có độ tƣơng
tự cao trong mỗi nhóm để xử lý sẽ giảm đáng kể thời gian chạy cho các thuật toán và tăng
chất lƣợng của kỹ thuật khám phá tri thức.
Bài toán phân cụm dữ liệu thuộc loại “thiết lập không đúng đắn” theo nghĩa lời giải
thƣờng không duy nhất và thay đổi nhiều khi dữ liệu thay đổi ít. Vì vậy ngƣời ta có nhiều
cách tiếp cận dựa trên quan sát tổng thể tập dữ liệu để áp dụng thuật toán thích hợp. Khi
số chiều cao, ngoài khối lƣợng tính toán tăng lên, dữ liệu phân bố “thƣa” nên việc quan
sát dữ liệu để phân tích đặc điểm hình học cũng rất khó khăn nên phân cụm khó hiệu quả.
Một cách tiếp cận cho dữ liệu chiều cao là chiếu chúng lên không gian có chiều thấp hơn,
chẳng hạn, các phƣơng pháp: CLIQUE[2], ENCLUS[6], MAFIA[19], Proclus[4],
ORCLUS[5], FINDIT[13], DOC [7], d-clusters[9], HARP[14] và LDR[11] cho dữ liệu
số.
Trong các phƣơng pháp phân cụm, thuật toán k-means do MacQueen (1967 ) đề
xuất có độ phức tạp thấp, thích hợp với dữ liệu lớn và có số chiều cao. Ban đầu thuật toán
này đƣợc dùng cho dữ liệu số sau đó đƣợc phát triển thành thuật toán k-modes cho các
dữ liệu định danh. Tuy nhiên khi dữ liệu nhiều chiều, việc xem đồng thời các thuộc tính
nhƣ nhau khi phân cụm ở thuật toán này không thích hợp và ngƣời ta phát triển nhiều
thuật toán mới.
Để giải quyết hiệu quả vấn đề này, luận văn đã trình bày một số thuật toán tối ƣu
hoá để so sánh phân nhóm dữ liệu phân loại chiều cao.
Trong các thuật toán trình bày, một kỹ thuật trọng số mới phân loại dữ liệu đƣợc
đƣa ra để tính toán trọng số cho mỗi thuộc tính (hay chiều) trong mỗi cụm và sử dụng
các giá trị trọng số để xác định tập hợp con cuả các thuộc tính quan trọng mà phân loại
cụm khác nhau.
Các nghiên cứu thực nghiệm cho thấy rằng các thuật toán đề xuất có hiệu quả
trong nhóm phân loại tập hợp dữ liệu và cũng có khả năng mở rộng dữ liệu lớn với độ
phức tạp là tuyến tính.
Ngoài phần kết luận luận văn đƣợc trình bày thành 4 chƣơng với nội dung đƣợc
trình bày nhƣ sau:
Chƣơng 1: Giới thiệu về khám phá tri thức và phân cụm dữ liệu. Trình bày cách biểu
diễn dữ liệu trong máy tính nhằm phục vụ cho quá trình phân cụm, giới thiệu độ tƣơng
đồng giữa các đối tƣợng trong tập dữ liệu, các phƣơng pháp phân cụm dữ liệu.
Chƣơng 2: Một số phƣơng pháp phân cụm chính.
Ở chƣơng này với mỗi phƣơng pháp phân cụm sẽ trình bày một số thuật toán
chính. Tƣ tƣởng của phƣơng pháp phân hoạch là tìm cách phân chia tập dữ liệu thành các
tập không giao nhau, thỏa mãn điều kiện làm tối ƣu hàm đánh giá. Trong mỗi tập con
thƣờng có ít nhất một phần tử đại diện, phần tử thay mặt thƣờng là tâm của tập con đó.
Mỗi đối tƣợng trong tập dữ liệu đƣợc phân vào cụm có điểm thay mặt gần với đối tƣợng
đó nhất. Quá trình này lặp đi lặp lại cho tới khi hàm mục tiêu không thay đổi. Phƣơng
pháp phân cấp phân tách các tập đối tƣợng theo hai cách: Tiếp cận từ dƣới lên (Bottom
Up) hay trên xuống (Top-Down). Tiếp cận từ dƣới lên bắt đầu với mỗi đối tƣợng đƣợc
xem nhƣ một nhóm, sau đó gộp các đối tƣợng hay các nhóm theo các hàm nhƣ hàm
khoảng cách giữa các tâm của hai nhóm và điều này đƣợc thực hiện cho tới khi tất cả các
nhóm đƣợc gộp vào làm một nhóm hay cho tới khi điều kiện kết thúc đƣợc thỏa mãn.
Tiếp cận theo phƣơng pháp từ trên xuống bắt đầu với tất cả các đối tƣợng nằm trong cùng
một cụm. Trong mỗi lần lặp, một cụm đƣợc tách ra thành các cụm nhỏ hơn theo một ƣớc
lƣợng nào đó. Điều này đƣợc thực hiện cho tới khi mỗi đối tƣợng là một cụm, hay cho
tới khi điều kiện kết thúc thỏa mãn. Đối với phƣơng pháp đƣợc phát triển dựa trên quan
niệm về mật độ. Các cụm tiêu biểu đƣợc xét là các vùng có các đối tƣợng tập trung đậm
đặc và đƣợc phân chia bởi các vùng có mật độ thấp (đặc trƣng cho nhiễu). Các phƣơng
pháp dựa trên mật độ có thể sử dụng để lọc ra các nhiễu (phần tử ngoại lai), và khám phá
ra các cụm có hình dạng bất kỳ. Cách tiếp cận dựa trên lƣới sử dụng cấu trúc lƣới của dữ
liệu. Nó lƣợng tử hóa khoảng cách vào một số hữu hạn các ô là cấu trúc dạng lƣới để tất
cả các phép toán phân cụm thực hiện đƣợc.
Chƣơng 3: Phân cụm dữ liệu với thuộc tính định danh
Với dữ liệu tồn tại trong tự nhiên là rất lớn và phong phú. Trong khuôn khổ luận
văn quan tâm đến việc phân cụm dữ liệu định danh. Ở chƣơng này chúng tui có trình bày
một số thuật toán, trong đó đi sâu vào hai thuật toán COOLCAT và MWKM để phân cụm
dữ liệu định danh với nhiều thuộc tính. Luận văn cũng đã so sánh đƣợc ƣu, nhƣợc điểm
của hai thuật toán này thông qua kết quả thực nghiệm ở chƣơng 4.
Chƣơng 4: Kết quả thực nghiệm
Luận văn đã trình bày kết quả thực nghiệm so sánh hai thuật toán COOLCAT và
MWKM với 5 bộ dữ liệu với nhiều thuộc tính: Cơ sở dữ liệu đậu tƣơng, cơ sở dữ liệu
nấm, cơ sở dữ liệu ung thƣ phổi, CSDL về thuê bao di động phát sinh của thành phố Hà
Nội và CSDL điều tra dân số của Mỹ năm 1990. Các hàm mục tiêu để đánh giá chất
lƣợng phân cụm là CU, ARI và ER đã đƣợc trình bày kỹ trong chƣơng 3.
Cuối cùng là kết luận, hƣớng phát triển, tài liệu tham khảo và phụ lục. Phần kết luận trình
bày tóm tắt kết quả thu đƣợc và đề xuất hƣớng nghiên cứu tiếp theo.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links