Các kỹ thuật phân cụm trong khai phá dữ liệu sử dụng tính toán tiến hóa
Các kỹ thuật phân cụm trong khai phá dữ liệu sử dụng tính toán tiến hóa
Xem bên trong

Các kỹ thuật phân cụm trong khai phá dữ liệu sử dụng tính toán tiến hóa

51 tr. + CD-ROM + tóm tắt
Luận văn ThS. Kỹ thuật phần mềm — Trường đại học Công nghệ. Đại học Quốc gia Hà Nội, 2014
Electronic Resources

0.00

Tải về miễn phí bản đầy đủ PDF luận văn tại Link bản đầy đủ 1

TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

PHAN MINH HẢI

CÁC KỸ THUẬT PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU
SỬ DỤNG TÍNH TOÁN TIẾN HÓA

Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60480103

LUẬN VĂN THẠC SĨ KỸ THUẬT PHẦN MỀM

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. BÙI THU LÂM

Hà Nội, 2014
2
LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của bản thân, được xuất phát từ
yêu cầu do giáo viên hướng dẫn đề ra để hình thành hướng nghiên cứu. Các số
liệu có nguồn gốc rõ ràng tuân thủ đúng nguyên tắc và kết quả trình bày trong
luận văn được thu thập được trong quá trình nghiên cứu là trung thực chưa từng
được ai công bố trước đây.

Hà Nội, tháng 10 năm 2014
Tác giả luận văn

Phan Minh Hải
3

LỜI CẢM ƠN

Luận văn được thực hiện dưới sự hướng dẫn của PGS.TS. Bùi Thu Lâm – Học
viện Kỹ thuật Quân sự. Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy đã hướng
dẫn và có ý kiến chỉ dẫn quý báu trong quá trình em làm luận văn. Em xin chân
thành cảm ơn các Thầy giáo trong bộ môn Công nghệ phần mềm. Em cũng xin
cảm ơn các thầy cô giáo trong Khoa, cán bộ thuộc phòng Khoa học và Đào tạo
sau Đại học, Trường Đại học Công nghệ đã tạo điều kiện trong quá trình học tập
và nghiên cứu tại Trường.
Cuối cùng xin bày tỏ lòng cảm ơn tới những người thân trong gia đình, bạn bè
đã động viên và giúp đỡ để tôi hoàn thành bản luận văn này.

Hà Nội, Tháng 10 năm 2014
Học viên thực hiện
Phan Minh Hải
4

LỜI CAM ĐOAN …………………………………………………………………………………………. 2
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ………………………………………… 6
DANH MỤC CÁC BẢNG …………………………………………………………………………….. 7
DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ …………………………………………………….. 8
CHƯƠNG 1 TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC, KHAI PHÁ DỮ LIỆU
VÀ GIẢI THUẬT DI TRUYỀN …………………………………………………………………… 10
1.1. Tổng quan về khám phá tri thức và khai phá dữ liệu ………………………………. 10
1.1.1. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu ………………………………. 10
1.1.2. Quá trình khám phá tri thức ……………………………………………………………………….. 10
1.1.3. Các phương pháp khai phá dữ liệu ………………………………………………………………. 12
1.1.4. Các lĩnh vực ứng dụng thực tiễn của KPDL ………………………………………………….. 12
1.1.5. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL. ………………………….. 13
1.1.6. Các yêu cầu của phân cụm ………………………………………………………………………….. 13
1.1.7. Phân cụm với giải thuật Kmean ………………………………………………………………….. 15
1.2. Tổng quan về giải thuật tiến hóa ……………………………………………………………. 16
1.2.1. Giải thuật di truyền ……………………………………………………………………………………. 16
1.2.1.1. Lịch sử phát triển ………………………………………………………………………………… 18
1.2.1.2. Các bước áp dụng giải thuật di truyền …………………………………………………….. 19
1.2.1.2.1. Mã hóa dữ liệu ……………………………………………………………………………… 19
1.2.1.2.2. Khởi tạo quần thể ………………………………………………………………………….. 19
1.2.1.2.3. Xác định hàm thích nghi ………………………………………………………………… 19
1.2.1.2.4. Quá trình lai ghép………………………………………………………………………….. 20
1.2.1.2.5. Quá trình đột biến …………………………………………………………………………. 21
1.2.1.2.6. Quá trình chọn lọc …………………………………………………………………………. 21
1.2.1.3. Các tham số của giải thuật di truyền ……………………………………………………….. 21
1.2.1.4. Sơ đồ quá trình tính toán của giải thuật di truyền ……………………………………… 22
1.2.2. Giải thuật tiến hóa vi phân ………………………………………………………………………….. 25
1.2.2.1. Nguyên lý hoạt động ……………………………………………………………………………. 25
1.2.2.2. Sơ đồ giải thuật tiến hóa vi phân ……………………………………………………………. 25
1.3. Kết luận ………………………………………………………………………………………………. 28
CHƯƠNG 2 GIẢI THUẬT PHÂN CỤM DỰA TRÊN LAI GHÉP GIẢI THUẬT
TIẾN HÓA VÀ KMEANS ………………………………………………………………………….. 29
2.1. Giải thuật phân cụm trong tính toán tiến hóa …………………………………………. 29
2.1.1.Giải thuật tổng quát cho phân cụm sử dụng giải thuật di truyền …………………………. 29
2.1.2. Biểu diễn cá thể ………………………………………………………………………………………… 30
2.1.3. Tính toán độ thích nghi ………………………………………………………………………………. 30
2.1.4. Phép chọn (Selection) ………………………………………………………………………………… 31
2.1.5. Crossover (lai ghép) ………………………………………………………………………………….. 32
2.1.6. Mutation (Đột biến) …………………………………………………………………………………… 33
2.1.7. Kmeans sử dụng giải thuật di truyền …………………………………………………………….. 34
2.1.8. Minh họa phân cụm Kmeans sử dụng giải thuật di truyền ………………………………… 35
2.1.9. Phân cụm Kmeans sử dụng giải thuật tiến hóa vi phân …………………………………….. 37
5
2.2. So sánh giữa giải thuật Kmeans và Kmeans sử dụng giải thuật di truyền ….. 38
2.3. Kết luận ………………………………………………………………………………………………. 38
CHƯƠNG 3 CÀI ĐẶT VÀ THỬ NGHIỆM ………………………………………………….. 40
3.1. Chuẩn bị dữ liệu …………………………………………………………………………………… 40
3.2. Kết quả và phân tích …………………………………………………………………………….. 41
3.2.1. Thí nghiệm giải thuật Kmeans, Genetic Kmean và DE Kmean ………………………… 41
3.2.1.1. Thí nghiệm giải thuật Kmeans ………………………………………………………………. 41
3.2.1.2. Thí nghiệm giải thuật Genetic Kmean …………………………………………………….. 42
3.2.1.3. Thí nghiệm giải thuật DE Kmean …………………………………………………………… 43
3.2.1.4. Thí nghiệm giải thuật Kmean, Genetic Kmean, DE Kmean với Northwin …….. 44
3.2.2. Phân tích kết quả ………………………………………………………………………………………. 45
3.3. Đánh giá kết quả thử nghiệm chung ………………………………………………………. 46
KẾT LUẬN ……………………………………………………………………………………………….. 48
TÀI LIỆU THAM KHẢO …………………………………………………………………………… 50

6
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

CDL Cụm dữ liệu
CNTT Công nghệ thông tin
CSDL Cơ sở dữ liệu
DE Giải thuật tiến hóa vi phân Differential Evolution
DL Dữ liệu
GA Giải thuật di truyền Genetic Algorithm
KPDL Khai phá dữ liệu
KPTT Khai phá thông tin
PCDL Phân cụm dữ liệu
NST Nhiễm sắc thể

7
DANH MỤC CÁC BẢNG

Bảng 2.1: Bộ dữ liệu số nguyên gồm 6 phần tử ………………………………………. 35
Bảng 2.2: Khởi tạo các NST và tính độ thích nghi …………………………………… 35
Bảng 2.3: Các NST mới thu được bằng cách sử dụng chọn lọc, lai ghép, đột
biến, ……………………………………………………………………………………………….. 36
Bảng 2.4: Các NST đầu vào và độ thích nghi cho đến thế hệ thứ 2 …………….. 36
Bảng 2.5: Các NST đầu vào và độ thích nghi cho đến thế hệ thứ 3 …………….. 36
Bảng 3.1: Bộ dữ liệu tự sinh có 2 trường dữ liệu …………………………………….. 40
Bảng 3.2: Bộ dữ liệu Customers của Northwind ……………………………………… 40
Bảng 3.3: Kết quả thử nghiệm với giải thuật Kmeans ………………………………. 41
Bảng 3.4: Kết quả thử nghiệm với giải thuật Genetic Kmean ……………………. 42
Bảng 3.5: Kết quả thử nghiệm với giải thuật DE Kmean ………………………….. 43
Bảng 3.6: Kết quả thử nghiệm các giải thuật với số cụm bằng 7 ………………… 44

8
DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ

Hình 1.1: Quá trình KPTT ………………………………………………………………….. 11
Hình 1.2: Ví dụ về mã hóa nhiễm sắc thể ……………………………………………… 19
Hình 1.3: Lai ghép hai cá thể ………………………………………………………………. 20
Hình 1.4: Đột biến một nhiễm sắc thể ………………………………………………….. 21
Hình 1.5: Sơ đồ quá trình tính toán của giải thuật di truyền ………………………. 23
Hình 1.6: Sơ đồ giải thuật tiến hóa vi phân …………………………………………….. 26
Biểu đồ 3.1: Tổng hợp kết quả của các giải thuật với giá trị trung bình trong
trường hợp 1 (hình a) và trường hợp 2 (hình b) ………………………………………. 45
9

MỞ ĐẦU

Phân cụm dữ liệu là quá trình nhóm một tập các đối tượng tương tự nhau trong
tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một cụm là tương
đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Phân
cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì
thế, có thể coi phân cụm dữ liệu là một cách học không giám sát (unsupervised
learning). Các Kỹ thuật phân cụm được ứng dụng rất nhiều trong các lĩnh vực tài
chính ngân hành để phân lọai các nhóm khách hàng khác nhau. Ngoài ra phân
cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các giải thuật
khai phá dữ liệu khác như phân loại và mô tả đặc điểm, có tác dụng phát hiện ra
các cụm.
Theo các nghiên cứu cho thấy thì hiện nay chưa có một phương pháp phân cụm
tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc của các
CSDL. Hơn nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc
của các CSDL, với mỗi cách thức biểu diễn khác nhau sẽ có một giải thuật phân
cụm thích nghi. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì
phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và thích nghi với nhiều
dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng
trong các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn
trong KPDL. Một điểm khác nữa là các hàm mục tiêu của các giải thuật phân
cụm như K-means thường tồn tại nhiều điểm tối ưu cục bộ. Do đó mà đề tài tập
trung vào tìm hiểu “Các kỹ thuật phân cụm trong khai phá dữ liệu sử dụng
tính toán tiến hóa”; một kỹ – giải thuật tiến hóa được thiết kế để khắc phục tính
chất cục bộ của các giải thuật phân cụm.
Luận văn gồm có 3 chương chính:
Chương 1: Tổng quan về khám phá tri thức, khai phá dữ liệu và giải thuật
di truyền
Chương 2: Giải thuật phân cụm dựa trên lai ghép giải thuật tiến hóa và
Kmeans
Chương 3: Cài đặt và thử nghiệm
Kết luận định hướng phát triển kết quả nghiên cứu
10
CHƯƠNG 1 TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC, KHAI PHÁ DỮ
LIỆU VÀ GIẢI THUẬT DI TRUYỀN

1.1. Tổng quan về khám phá tri thức và khai phá dữ liệu
1.1.1. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu
Nếu cho rằng, điện tử và truyền thông chính là bản chất của khoa học điện tử, thì
dữ liệu, thông tin, và tri thức hiện đang là tiêu điểm của một lĩnh vực mới để
nghiên cứu và ứng dụng, đó là khám phá tri thức và khai phá dữ liệu.
Thông thường, chúng ta coi dữ liệu như là một chuỗi các bits, hoặc các số và các
ký hiệu hay là các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một
chương trình dưới một dạng nhất định. Các bits thường được sử dụng để đo
thông tin, và xem nó như là dữ liệu đã được loại bỏ phần tử thừa, lặp lại, và
rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Tri thức
được xem như là các thông tin tích hợp, bao gồm các sự kiện và mối quan
hệ giữa chúng, đã được nhận thức, khám phá, hoặc nghiên cứu. Nói cách khác,
tri thức có thể được coi là dữ liệu ở mức độ cao của sự trừu tượng và tổng
quát[2].
Khám phá tri thức hay phát hiện tri thức trong CSDL là một quy trình nhận biết
các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng
hợp, hợp thức, khả ích và có thể hiểu được.
Khai phá dữ liệu là một bước trong quá trình khám phá tri thức, gồm các giải
thuật khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán
chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu.
Nói cách khác, mục tiêu của Khai phá dữ liệu là tìm kiếm các mẫu hoặc mô hình
tồn tại trong CSDL nhưng ẩn trong khối lượng lớn dữ liệu.
1.1.2. Quá trình khám phá tri thức
Quá trình khám phá dữ liệu có thể chia thành các giai đoạn như sau, xem
hình 1.1 [3]:
Giai đoạn 1. Trích chọn dữ liệu: Đây là bước trích chọn những tập dữ liệu cần
được khai phá từ các tập dữ liệu lớn ban đầu theo một số tiêu chí nhất định.
Giai đoạn 2. Tiền xử lý dữ liệu: Đây là bước làm sạch dữ liệu (xử lý những dữ
liệu không đầy đủ, nhiễu, không nhất quán, …), rút gọn dữ liệu (sử dụng hàm
11
nhóm và tính tổng, các phương pháp nén dữ liệu, lấy mẫu, …), rời rạc hóa dữ
liệu.
Flat files: Những tệp dữ liệu không có mối quan hệ về cấu trúc
Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hóa.
Giai đoạn 3. Biến đổi dữ liệu: Đây là bước chuẩn hóa và làm mịn dữ liệu để đưa
dữ liệu về dạng thuận lợi nhất nhằm phục vụ quá trình khai phá ở bước sau.
Giai đoạn 4. Khai phá dữ liệu: Đây là bước áp dụng những kỹ thuật phân
tích (như các kỹ thuật của học máy) nhằm để khai thác dữ liệu, trích chọn
được những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu. Đây
được xem là bước quan trọng và tốn nhiều thời gian nhất của quá trình KDD.
Giai đoạn 5. Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối
liên hệ trong dữ liệu đã được khám phá ở bước trên được biến đổi và biểu
diễn ở một dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật, …
Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những
tiêu chí nhất định.

Hình 1.1: Quá trình khám phá tri thức
Cơ sở dữ liệu
Làm sạch và
tích hợp
Flat files
Kho dữ liệu
Lựa chọn và
biến đổi
Khai phá dữ liệu
Đánh giá và
biểu diễn
Các mẫu
Tri thức
12
1.1.3. Các phương pháp khai phá dữ liệu
Với hai mục đích khai phá dữ liệu là Mô tả và Dự đoán, người ta thường
sử dụng các phương pháp sau cho khai phá dữ liệu [3]:
o Luật kết hợp (association rules)
o Phân lớp (Classfication)
o Hồi qui (Regression)
o Trực quan hóa (Visualiztion)
o Phân cụm (Clustering)
o Tổng hợp (Summarization)
o Mô hình ràng buộc (Dependency modeling)
o Biểu diễn mô hình (Model Evaluation)
o Phân tích sự phát triển và độ lệch (Evolution and deviation analyst)
o Phương pháp tìm kiếm (Search Method)
Có nhiều phương pháp khai phá dữ liệu được nghiên cứu ở trên, trong đó có ba
phương pháp được các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết
hợp, Phân lớp dữ liệu và Phân cụm dữ liệu.
1.1.4. Các lĩnh vực ứng dụng thực tiễn của KPDL
KPDL là một lĩnh vực mới phát triển nhưng thu hút được khá nhiều nhà nghiên
cứu nhờ vào những ứng dụng thực tiễn của nó. Sau đây là một số lĩnh vực ứng
dụng thực tế điển hình của KPDL[2]:
– Phân tích dữ liệu và hỗ trợ ra quyết định
– Phân lớp văn bản, tóm tắt văn bản, phân lớp các trang Web và phân
cụm ảnh màu
– Chuẩn đoán triệu chứng, phương pháp trong điều trị y học
– Tìm kiếm, đối sánh các hệ Gene và thông tin di truyền trong sinh học
– Phân tích tình hình tài chính, thị trường, dự báo gía cổ phiếu trong tài
chính, thị trường và chứng khoán
– Phân tích dữ liệu marketing, khách hàng.
– Điều khiển và lập lịch trình
– Bảo hiểm
– Giáo dục…..
13
1.1.5. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL.
Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp cận
chính sau [3]:
– Phân lớp và dự đoán (classification &prediction): Là quá trình xếp một đối
tượng vào một trong những lớp đã biết trước (ví dụ: phân lớp các bệnh nhân
theo dữ liệu hồ sơ bệnh án, phân lớp vùng địa lý theo dữ liệu thời tiết…). Đối
với hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây
quyết định (decision tree), mạng nơron nhân tạo (neural network),… Hay lớp
bài toán này còn đươc gọi là học có giám sát – Học có thày (supervised
learning).
– Phân cụm (clustering/segmentation): Sắp xếp các đối tượng theo từng cụm
dữ liệu tự nhiên, tức là số lượng và tên cụm chưa được biết trước. Các đối
tượng được gom cụm sao cho mức độ tương tự giữa các đối tượng trong cùng
một cụm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các
cụm khác nhau là nhỏ nhất. Lớp bài toán này còn được gọi là học không giám
sát – Học không thày (unsupervised learning).
– Luật kết hợp (association rules): Là dạng luật biểu diễn tri thức ở dạng khá
đơn giản (Ví dụ: 80% sinh viên đăng ký học CSDL thì có tới 60% trong số họ
đăng ký học Phân tích thiết kế hệ thống thông tin). Hướng tiếp cận này được
ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin sinh học, giáo dục, viễn
thông, tài chính và thị trường chứng khoán,…
– Phân tích chuỗi theo thời gian (sequential/temporal patterns): Cũng tương tự
như khai phá dữ liệu bằng luật kết hợp nhưng có thêm tính thứ tự và tính thời
gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X -> Y, phản ánh sự xuất
hiện của biến cố X sẽ dẫn đến việc xuất hiện biến cố Y. Hướng tiếp cận này
được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán bởi
chúng có tính dự báo cao.
– Mô tả khái niệm (concept desccription & summarization): Lớp bài toán
này thiên về mô tả, tổng hợp và tóm tắt khái niệm (Ví dụ: tóm tắt văn bản).
1.1.6. Các yêu cầu của phân cụm
Phân cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ những ứng
dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc biệt
của chúng. Sau đây là những yêu cầu cơ bản của phân cụm trong KPDL
[3]:
14
Có khả năng mở rộng: Nhiều thuật toán phân cụm làm việc tốt với những
tập dữ liệu khoảng vài trăm đối tượng, tuy nhiên, một CSDL lớn có thể chứa tới
hàng triệu đối tượng. Việc phân cụm với một tập dữ liệu lớn có thể làm ảnh
hưởng tới kết quả. Vậy làm cách nào để chúng ta có thể phát triển các giải
thuật phân cụm có khả năng mở rộng cao đối với các CSDL lớn?
Khả năng thích nghi với các kiểu thuộc tính khác nhau: Nhiều giải thuật
được thiết kế cho việc phân cụm dữ liệu có kiểu khoảng (kiểu số). Tuy nhiên,
nhiều ứng dụng có thể đòi hỏi việc phân cụm với nhiều kiểu dữ liệu khác
nhau, như kiểu nhị phân, kiểu tường minh (định danh – không thứ tự), và
dữ liệu có thứ tự hay dạng hỗn hợp của những kiểu dữ liệu này.
Khám phá các cụm với hình dạng bất kỳ: Nhiều giải thuật phân cụm xác
định các cụm dựa trên các phép đo khoảng cách Euclidean và khoảng
cách Manhattan. Các thuật toán dựa trên các phép đo như vậy hướng tới việc
tìm kiếm các cụm hình cầu với mật độ và kích cỡ tương tự nhau. Tuy nhiên, một
cụm có thể có bất cứ một hình dạng nào. Do đó, việc phát triển các thuật toán
có thể khám phá ra các cụm có hình dạng bất kỳ là một việc làm quan trọng.
Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: Nhiều thuật
toán phân cụm yêu cầu người dùng đưa vào những tham số nhất định trong
phân tích phân cụm (như số lượng các cụm mong muốn). Kết quả của phân
cụm thường khá nhạy cảm với các tham số đầu vào. Nhiều tham số rất khó để
xác định, nhất là với các tập dữ liệu có lượng các đối tượng lớn. Điều này không
những gây trở ngại cho người dùng mà còn làm cho khó có thể điều chỉnh được
chất lượng của phân cụm.
Khả năng thích nghi với dữ liệu nhiễu: Hầu hết những CSDL thực đều chứa
đựng dữ liệu ngoại lai, dữ liệu lỗi, dữ liệu chưa biết hoặc dữ liệu sai. Một số giải
thuật phân cụm nhạy cảm với dữ liệu như vậy và có thể dẫn đến chất lượng phân
cụm thấp.
Ít nhạy cảm với thứ tự của các dữ liệu vào: Một số thuật toán phân cụm
nhạy cảm với thứ tự của dữ liệu vào, ví dụ như với cùng một tập dữ liệu, khi
được đưa ra với các thứ tự khác nhau thì với cùng một giải thuật có thể sinh ra
các cụm rất khác nhau. Do đó, việc quan trọng là phát triển các giải thuật mà ít
nhạy cảm với thứ tự vào của dữ liệu.
Số chiều lớn: Một CSDL hoặc một kho dữ liệu có thể chứa một số chiều
hoặc một số các thuộc tính. Nhiều thuật toán phân cụm áp dụng tốt cho dữ liệu
với số chiều thấp, bao gồm chỉ từ hai đến 3 chiều. Người ta đánh giá việc phân
15
cụm là có chất lượng tốt nếu nó áp dụng được cho dữ liệu có từ 3 chiều trở lên.
Nó là sự thách thức với các đối tượng dữ liệu cụm trong không gian với số
chiều lớn, đặc biệt vì khi xét những không gian với số chiều lớn có thể rất thưa
và có độ nghiêng lớn.
Phân cụm ràng buộc: Nhiều ứng dụng thực tế có thể cần thực hiện phân
cụm dưới các loại ràng buộc khác nhau. Một nhiệm vụ đặt ra là đi tìm những
nhóm dữ liệu có trạng thái phân cụm tốt và thỏa mãn các ràng buộc.
Dễ hiểu và dễ sử dụng: Người sử dụng có thể chờ đợi những kết quả phân cụm
dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể cần được giải
thích ý nghĩa và ứng dụng rõ ràng.
1.1.7. Phân cụm với giải thuật Kmean
Cho tập dữ liệu D gồm n đối tượng trong không gian Euclidean. Phương pháp
này sẽ phân hoạch các đối tượng trong D vào trong k cụm, C1, .., Ck, trong đó Ck
⊂ D và Ci ∩ Cj = ∅ (trong đó, 1 ≤ i, j ≤ k). Hàm mục tiêu được sử dụng để đánh
giá độ các đối tượng trong một cụm tương tự nhau, các đối tượng thuộc các cụm
khác nhau sẽ không tương tự. Sự khác nhau giữa một đối tượng p ∈ Ci và ci
được thể hiện bằng phép đo khoảng cách Euclidean dist(p, ci) [3].
Đặc tính của cụm Ci được xác định bởi sự khác nhau trong cụm theo công thức
sau:

trong đó, ci là trọng tâm cụm của Ci, p là điểm thuộc Ci
Giải thuật phân cụm Kmean:
Input:
k: số cụm
D: tập dữ liệu chứa n đối tượng
Output:
một tập hợp k các cụm
Thứ tự thực hiện giải thuật:
(1) Khởi tạo k trọng tâm cụm từ tập D đối tượng
(2) Lặp
(3) Đăng ký hoặc đăng ký lại mỗi đối tượng vào cụm có độ tương tự lớn nhất,
dựa trên giá trị trung bình của các đối tượng thuộc cụm;

Tác giả

Phan Minh Hải

Nhà xuất bản

ĐHCN

Năm xuất bản

2014

Người hướng dẫn

Bùi Thu Lâm

Định danh

00050004266

Kiểu

text

Định dạng

text/pdf

Nhà xuất bản

Khoa công nghệ thông tin,

Trường đại học Công nghệ

Các đánh giá

Hiện chưa có đánh giá cho sản phẩm.

Hãy là người đầu tiên đánh giá “Các kỹ thuật phân cụm trong khai phá dữ liệu sử dụng tính toán tiến hóa”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *