ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
TRƯƠNG ĐỨC CƯỜNG
PHÂN CỤM DỮ LIỆU SỬ DỤNG
GIẢI THUẬT DI TRUYỀN VÀ MẠNG NƠ RON
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. Vũ Mạnh Xuân
Thái Nguyên - 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vni
LỜI CẢM ƠN
Em xin bày tỏ lòng biết ơn sâu sắc tới TS. Vũ Mạnh Xuân, thầy đã
hướng dẫn, chỉ dạy tận tình để em hoàn thành luận văn này. Em xin chân
thành cảm ơn các thầy, cô giáo Trường Đại học Công nghệ Thông tin &
Truyền thông - Đại học Thái Nguyên, cùng các thầy, cô giáo Viện Công nghệ
Thông tin - Viện Khoa học và Công nghệ Việt Nam đã truyền thụ kiến thức
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vniii
MỤC LỤC
MỤC LỤC iii
DANH SÁCH HÌNH VẼ v
DANH SÁCH BẢNG BIỂU vi
DANH SÁCH TỪ VIẾT TẮT vii
MỞ ĐẦU 1
CHƢƠNG I: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 3
1.1. Khái niệm và mục đích của phân cụm dữ liệu 3
1.2. Ứng dụng của phân cụm dữ liệu 4
1.3. Một số phương pháp phân cụm dữ liệu 5
1.3.1. Phân cụm phân hoạch 5
1.3.2. Phân cụm phân cấp 7
1.3.3. Phân cụm dựa trên mật độ 9
1.3.4. Phân cụm dựa trên lưới 11
1.3.5. Phân cụm dữ liệu dựa trên mô hình 13
1.3.6. Phân cụm dữ liệu mờ 14
CHƢƠNG II: PHÂN CỤM DỮ LIỆU SỬ DỤNG GIẢI THUẬT DI
TRUYỀN VÀ MẠNG NƠ RON 16
2.1. Giải thuật di truyền 16
2.1.1. Sơ đồ thực hiện giải thuật di truyền 17
2.1.2. Các quá trình chính trong giải thuật di truyền 19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vniv
Hình 1.1. Quy trình phân cụm 3
Hình 1.2. Mô phỏng sự phân cụm dữ liệu 4
Hình 1.3. Các chiến lược phân cụm phân cấp 8
Hình 1.4. Một số hình dạng khám phá bởi phân cụm dựa trên mật độ 10
Hình 1.5. Mô hình cấu trúc dữ liệu lưới 12
Hình 2.1. Lưu đồ giải thuật di truyền 18
Hình 2.2. Bánh xe trọng số 23
Hình 2.3. Lai ghép một điểm 25
Hình 2.4. Lai ghép trong biểu diễn bằng giá trị 26
Hình 2.5. Cấu tạo của nơ ron 31
Hình 2.6. Thu nhận tín hiệu trong nơ ron 31
Hình 2.7. Mạng nơ ron truyền thẳng nhiều lớp 34
Hình 2.8. Mạng hồi quy (Recurrent Neural Network) 34
Hình 2.9. Mô đun ghép cặp Di truyền – Nơ ron trong một hệ thống ứng dụng
38
Hình 2.10. Sơ đồ của hệ thống XROUTE (Kadaba, Nygard và Juell 1991) 38
Hình 3.1. Dữ liệu đầu ra 42
Hình 3.2. Dữ liệu đầu vào sau khi mã hóa 43
Hình 3.3. Quá trình lai ghép 43
Hình 3.4. Tập điểm dữ liệu vào 48
Hình 3.5. Giao diện chương trình 49
Hình 3.6. Kết quả phân cụm với string count = 100 50
Hình 3.7. Kết quả phân cụm với string count = 1 50
Hình 3.8. Kết quả phân cụm bộ dữ liệu giao nhau với stringcount = 1 51
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vnvi
DANH SÁCH BẢNG BIỂU
Nhiễm sắc thể
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
MỞ ĐẦU
Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông
tin và ngành công nghiệp phần cứng đã làm cho khả năng thu thập và lưu trữ
thông tin của các hệ thống thông tin tăng nhanh một cách chóng mặt. Bên
cạnh đó việc tin học hóa một cách ồ ạt và nhanh chóng các hoạt động sản
xuất, kinh doanh cũng như nhiều lĩnh vực hoạt động khác đã tạo cho chúng ta
một hệ thống cơ sở dữ liệu khổng lồ. Hệ thống này đã đem lại những lợi ích
vô cùng to lớn cho con người trong việc lưu trữ, tìm kiếm và thống kê. Tuy
vậy, sự bùng nổ này đã dẫn tới một nhu cầu mới là phát hiện tri thức từ kho
dữ liệu khổng lồ đó. Đây là một vấn đề rất phức tạp, cần phải có những công
cụ và kỹ thuật xử lý linh hoạt như suy nghĩ của con người.
Trong ngành khoa học máy tính, tìm kiếm lời giải tối ưu cho các bài
toán là vấn đề được các nhà khoa học máy tính đặc biệt rất quan tâm. Mục
đích chính của các thuật toán là tìm kiếm thuật giải chất lượng cao và sử
dụng kỹ thuật trí tuệ nhân tạo đặc biệt rất cần thiết khi giải quyết các bài toán
có không gian tìm kiếm lớn.
Giải thuật di truyền (Genetic Algorithm - GA) là một trong những kỹ
thuật tìm kiếm lời giải tối ưu đã đáp ứng được yêu cầu của nhiều bài toán và
ứng dụng. Hiện nay, thuật toán di truyền cùng với mạng nơ ron được ứng
dụng rất rộng rãi trong các lĩnh vực phức tạp. Thuật toán di truyền kết hợp
với mạng nơ ron chứng tỏ được hiệu quả của nó trong các vấn đề khó có thể
giải quyết bằng các phương pháp thông thường hay các phương pháp cổ
điển, nhất là trong các bài toán cần có sự lượng giá, đánh giá sự tối ưu của
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
CHƢƠNG I: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU
Ngày nay, khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền
công nghệ thông tin thế giới nói chung và Việt Nam nói riêng. Khai phá dữ
liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh
và đời sống.
Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu với mục đích
chính là khám phá cấu trúc của mẫu dữ liệu để thành lập các nhóm dữ liệu
từ tập dữ liệu lớn, cho phép con người đi sâu vào phân tích và nghiên cứu
cho từng cụm dữ liệu nhằm khám phá và tìm kiếm các thông tin tiềm ẩn,
hữu ích phục vụ cho việc ra quyết định.
Trong chương 1 sẽ trình bày về khái niệm, ứng dụng, đưa ra nhận xét và
một số phương pháp để phân cụm dữ liệu.
1.1. Khái niệm và mục đích của phân cụm dữ liệu
Phân cụm dữ liệu là quá trình nhóm một tập các đối tượng thực thể hay
trừu tượng thành lớp các đối tượng tương tự. Một cụm là một tập hợp các
đối tượng dữ liệu mà các phần tử của nó tương tự nhau và phi tương tự
với các đối tượng trong các cụm khác. Một cụm các đối tượng dữ liệu có
thể xem như là một nhóm trong nhiều ứng dụng.
Hình 1.1. Quy trình phân cụm
Số các cụm dữ liệu có thể được xác định trước theo kinh nghiệm hoặc có
các lĩnh vực sau:
- Thương mại: phân cụm dữ liệu có thể giúp các thương nhân tìm ra các
nhóm khách hàng quan trọng có các đặc trưng tương đồng nhau và đặc tả họ
từ các mẫu mua bán trong CSDL khách hàng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
- Sinh học: phân cụm dữ liệu được sử dụng để xác định các loại sinh vật,
phân loại các Gen với chức năng tương đồng và thu được các cấu trúc trong
các mẫu.
- Phân tích dữ liệu không gian: do sự đồ sộ của dữ liệu không gian như dữ
liệu thu được từ các hình ảnh chụp từ vệ tinh, các thiết bị y học hoặc hệ thống
thông tin địa lý (GIS),… làm cho người dùng rất khó để kiểm tra các dữ liệu
không gian một cách chi tiết. Phân cụm dữ liệu có thể trợ giúp người dùng tự
động phân tích và xử lý các dữ liệu không gian như nhận dạng và chiết xuất
các đặc tính hoặc các mẫu dữ liệu quan tâm có thể tồn tại trong CSDL không
gian.
- Lập quy hoạch đô thị: nhận dạng các nhóm nhà theo kiểu và vị trí địa
lý,… nhằm cung cấp thông tin cho quy hoạch đô thị.
- Nghiên cứu trái đất: phân cụm để theo dõi các tâm động đất nhằm cung
cấp thông tin cho nhận dạng các vùng nguy hiểm.
- Địa lý: phân lớp các động vật, thực vật và đưa ra đặc trưng của chúng.
- Khai phá Web: phân cụm dữ liệu có thể khám phá các nhóm tài liệu
quan trọng, có nhiều ý nghĩa trong môi trường Web. Các lớp tài liệu này trợ
giúp cho việc khám phá tri thức từ dữ liệu Web, khám phá ra các mẫu truy
cập của khách hàng đặc biệt hay khám phá ra cộng đồng Web,…
1.3. Một số phƣơng pháp phân cụm dữ liệu
1.3.1. Phân cụm phân hoạch
tượng đến tâm nhóm (centroid) là nhỏ nhất. Trọng tâm của một cụm là một
vector, trong đó giá trị của mỗi phần tử của nó là trung bình cộng các thành
phần tương ứng của các đối tượng vector dữ liệu trong cụm đang xét.
Thuật toán K-mean được chứng minh là hội tụ và có độ phức tạp tính
toán là:
)**)**((
flop
TdknO
. Trong đó:
- n là số đối tượng dữ liệu
- k là số cụm dữ liệu
- d là số chiều
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
- τ là số vòng lặp
- T
flop
là thời gian để thực hiện một phép tính cơ sở như phép tính
nhân, chia,…
Như vậy, do K-mean 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-mean là chỉ áp dụng
với dữ liệu có thuộc tính số và khám phá ra các cụm có dạng hình cầu, K-
mean 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.
Hơn nữa, chất lượng PCDL của thuật toán K-mean phụ thuộc nhiều
vào các tham số đầu vào như: số cụm k và k trọng tâm khởi tạo ban đầu.
Trong trường hợp, các trọng tâm khởi tạo ban đầu mà quá lệch so với các
mãn. Cách tiếp cận này sử dụng chiến lược chia để trị trong quá trình phân
cụm.
Sau đây là minh họa chiến lược phân cụm phân cấp Bottom up và Top
down.
Hình 1.3. Các chiến lược phân cụm phân cấp
Trong thực tế áp dụng, có nhiều trường hợp người ta kết hợp cả hai
phương pháp phân cụm phân hoạch và phân cụm phân cấp, nghĩa là kết quả
thu được của phương pháp phân cấp có thể cải tiến thông qua bước phân cụm
phân hoạch. Phân cụm phân hoạch và phân cụm phân cấp là hai phương
pháp PCDL cổ điển, hiện nay đã có nhiều thuật toán cải tiến dựa trên hai
Bước 1
Bước 2
Bước 3
Bước 4
Bottom up
a
b
a b
a b c d e
c
BIRCH chỉ duyệt toàn bộ dữ liệu một lần với một lần quét thêm tùy chọn,
nghĩa là độ phức tạp của nó là O(n).
Nhược điểm của nó là chất lượng của các cụm được khám phá không được
tốt. Nếu BIRCH sử dụng khoảng cách Euclide, nó thực hiện tốt chỉ với các dữ
liệu số. Mặt khác, tham số vào T có ảnh hưởng rất lớn tới kích thước và tính tự
nhiên của cụm. Việc ép các đối tượng dữ liệu làm cho các đối tượng của một
cụm có thể là đối tượng kết thúc của cụm khác, trong khi các đối tượng gần
nhau có thể bị hút bởi các cụm khác nếu chúng được biểu diễn cho thuật toán
theo một thứ tự khác. BIRCH không thích hợp với dữ liệu đa chiều.
1.3.3. Phân cụm dựa trên mật độ
Phương pháp này nhóm các đối tượng theo hàm mật độ xác định. Mật
độ được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu
theo một ngưỡng nào đó.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
Trong cách tiếp cận này, khi một cụm dữ liệu đã xác định thì nó tiếp
tục được phát triển thêm các đối tượng dữ liệu mới, miễn là số các đối tượng
lân cận của các đối tượng này phải lớn hơn một ngưỡng đã được xác định
trước.
Phương pháp phân cụm dựa vào mật độ của các đối tượng để xác định
các cụm dữ liệu và có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ.
Tuy vậy, việc xác định các tham số mật độ của thuật toán là rất khó khăn,
trong khi các tham số này lại có tác động rất lớn đến kết quả PCDL.
Hình dưới minh họa về các cụm dữ liệu với các hình thù khác nhau
dựa trên mật độ được khám phá từ ba CSDL khác nhau:
Hình 1.4. Một số hình dạng khám phá bởi phân cụm dựa trên mật độ
bình của mỗi truy vấn là O(nlogn).
1.3.4. Phân cụm dựa trên lƣới
Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu
nhiều chiều, để giải quyết cho đòi hỏi này, người ta đã sử dụng phương pháp
phân cụm dựa trên lưới. Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để
PCDL, phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không
gian.
Cách tiếp cận dựa trên lưới này không di chuyển các đối tượng trong các
ô mà xây dựng nhiều mức phân cấp của nhóm các đối tượng trong một ô.
Trong ngữ cảnh này, phương pháp này gần giống với phương pháp phân cụm
phân cấp nhưng chỉ có điều chúng không trộn các ô. Do vậy các cụm không
dựa trên độ đo khoảng cách (hay còn gọi là độ đo tương tự đối với các dữ liệu
không gian) mà nó được quyết định bởi một tham số xác định trước.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12 Tầng 1
.
.
.
.
.
.
Mức 1 (mức cao nhất )
có thể chỉ chứa một ô
Tầng i-1
13
Một truy vấn không gian được xác định như là một thông tin khôi
phục lại của dữ liệu không gian và các quan hệ của chúng. STING có khả
năng mở rộng cao, nhưng do sử dụng phương pháp đa phân giải nên nó
phụ thuộc chặt chẽ vào trọng tâm của mức thấp nhất.
Đa phân giải là khả năng phân rã tập dữ liệu thành các mức chi tiết khác
nhau. Khi hòa nhập các cell của cấu trúc lưới để hình thành các cụm, các nút
của mức con không được hòa nhập phù hợp (do chúng chỉ tương ứng với các
cha của nó) và hình thù của các cụm dữ liệu khám phá được có các biên
ngang và dọc, theo biên của các cell. STING sử dụng cấu trúc dữ liệu lưới cho
phép khả năng xử lý song song, STING duyệt toàn bộ dữ liệu một lần nên độ
phức tạp tính toán để tính toán các đại lượng thống kê cho mỗi cell là O(n),
trong đó n là tổng số đối tượng.
Sau khi xây dựng cấu trúc dữ liệu phân cấp, thời gian xử lý cho các
truy vấn là O(g) với g là tổng số cell tại mức thấp nhất (g<<n).
1.3.5. Phân cụm dữ liệu dựa trên mô hình
Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của các tham
số mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng
chiến lược phân cụm phân hoạch hoặc chiến lược phân cụm phân cấp, dựa
trên cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách mà
chúng tinh chỉnh các mô hình này để nhận dạng ra các phân hoạch.
Phương pháp PCDL dựa trên mô hình cố gắng khớp giữa dữ liệu với mô
hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng hỗn hợp
phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình có hai
tiếp cận chính là: Mô hình thống kê và Mạng nơ ron. Một số thuật toán điển
hình như: EM, COBWEB,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
15
phân cụm mờ, độ phụ thuộc của đối tượng dữ liệu x
k
tới cụm thứ i (u
ik
) có
giá trị thuộc khoảng [0,1].
Ý tưởng trên đã được giới thiệu bởi Ruspini (1969) và được Dunn áp
dụng năm 1973 nhằm xây dựng một phương pháp phân cụm mờ dựa trên tối
thiểu hoá hàm tiêu chuẩn. Bezdek (1982) đã tổng quát hoá phương pháp này
và xây dựng thành thuật toán phân cụm mờ C-mean có sử dụng trọng số mũ.
C-mean là thuật toán phân cụm mờ (của K-mean). Thuật toán C-mean
mờ hay còn gọi tắt là thuật toán FCM (Fuzzy C-mean) đã được áp dụng thành
công trong giải quyết một số lớn các bài toán PCDL như trong nhận dạng
mẫu, xử lý ảnh, y học,… Tuy nhiên, nhược điểm lớn nhất của thuật toán FCM
là nhạy cảm với các nhiễu và phần tử ngoại lai, nghĩa là các trung tâm cụm có
thể nằm xa so với trung tâm thực tế của cụm.
Đã có nhiều các phương pháp đề xuất để cải tiến cho nhược điểm trên
của thuật toán FCM bao gồm: Phân cụm dựa trên xác suất (Keller, 1993),
phân cụm nhiễu mờ (Dave, 1991), Phân cụm dựa trên toán tử L
P
Norm
(Kersten, 1999). Thuật toán
- Insensitive Fuzzy c-mean (
Giải thuật di truyền (Genetic Algorithm – GA), do John Holland (1975)
và Goldberg (1989) đề xuất và phát triển. Ý tưởng của giải thuật di truyền là
mô phỏng theo cơ chế của quá trình tiến hóa trong tự nhiên. Từ tập các lời
giải ban đầu, thông qua nhiều bước tiến hóa để hình thành các tập mới với
những lời giải tốt hơn, cuối cùng sẽ tìm được lời giải gần tối ưu nhất.
GA sử dụng các thuật ngữ lấy từ di truyền học:
- Một tập hợp các lời giải được gọi là một Lớp hay Quần thể
(Population).
- Mỗi lời giải được biểu diễn bởi một Nhiễm sắc thể (NST) hay Cá
thể (Chromosome).
- NST được tạo thành từ các Gen
Một quá trình tiến hóa được thực hiện trên một quần thể tương đương
với sự tìm kiếm trên không gian các lời giải có thể của bài toán. Quá trình tìm
kiếm này luôn đòi hỏi sự cân bằng giữa hai mục tiêu: khai thác lời giải tốt
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Copyright: Tài liệu đại học ©