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

NGUYỄN THỊ NHƯ NA

VỀ TÍNH HIỆU QUẢ CỦA CÁC THUẬT TOÁN TỐI ƯU
TIẾN HÓA CHO PHÂN CỤM MỜ VÀ ỨNG DỤNG
TRONG PHÂN TÍCH NHU CẦU KHÁCH HÀNG

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Hà Nội – 2015


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

NGUYỄN THỊ NHƯ NA

VỀ TÍNH HIỆU QUẢ CỦA CÁC THUẬT TOÁN TỐI ƯU
TIẾN HÓA CHO PHÂN CỤM MỜ VÀ ỨNG DỤNG
TRONG PHÂN TÍCH NHU CẦU KHÁCH HÀNG
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60.48.01.04
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Lê Hoàng Sơn

Hà Nội – 2015


văn. Luận văn này được thực hiện dưới sự tài trợ của đề tài NAFOSTED, mã số:
102.05-2014.01.
Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép
nhưng chắc chắn sẽ không tránh khỏi những thiếu sót. Em rất mong được sự góp ý
chân thành của thầy cô và các bạn để em hoàn thiện luận văn của mình.
Xin chân thành cảm ơn!
Hà Nội, ngày 5 tháng 5 năm 2015
Học viên

Nguyễn Thị Như Na
ii


MỤC LỤC
LỜI CAM ĐOAN........................................................................................................................................... i
LỜI CẢM ƠN................................................................................................................................................. ii
MỤC LỤC....................................................................................................................................................... iii
DANH SÁCH HÌNH VẼ......................................................................................................................... vi
DANH SÁCH BẢNG................................................................................................................................ vi
DANH MỤC CÁC KÝ HIỆU VIẾT TẮT.................................................................................... vii
1/. ĐẶT VẤN ĐỀ.......................................................................................................................................... 1
2/. MỤC ĐÍCH CỦA LUẬN VĂN...................................................................................................... 2
3/. BỐ CỤC CỦA LUẬN VĂN............................................................................................................. 3
CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CỤM MỜ................................................................... 5
1.1. Tập mờ....................................................................................................................................................... 5
1.1.1. Lý thuyết mờ............................................................................................................................... 5
1.1.2. Tập mờ........................................................................................................................................... 5
1.2. Giới thiệu về phân cụm mờ............................................................................................................. 8
1.2.1. Khái quát phân cụm............................................................................................................... 8
1.2.2. Độ đo gần gũi.......................................................................................................................... 10

CHƯƠNG 3: SO SÁNH HIỆU NĂNG THUẬT TOÁN TỐI ƯU TIẾN HÓA 62
3.1. Thiết lập môi trường thực nghiệm............................................................................................ 62
iv


3.1.1. Dữ liệu........................................................................................................................................ 62
3.1.2. Cấu hình cài đặt..................................................................................................................... 62
3.1.3. Kết quả thực nghiệm............................................................................................................ 63
3.1.4. So sánh hiệu năng thuật toán.......................................................................................... 65
3.2. Ứng dụng............................................................................................................................................... 66
3.2.1. Bài toán...................................................................................................................................... 66
3.2.2. Dữ liệu........................................................................................................................................ 66
3.2.3. Kết quả chạy thực nghiệm bài toán............................................................................. 68
3.3. Kết luận chương................................................................................................................................. 75
KẾT LUẬN.................................................................................................................................................... 76
TÀI LIỆU THAM KHẢO...................................................................................................................... 78

v


DANH SÁCH HÌNH VẼ

Hình 1.1. Tập mờ và biểu diễn tập mờ
Hình 1.2. Ví dụ một tập mờ
Hình 1.3. Số mờ hình thang.
Hình 1.4. Số mờ hình tam giác.
Hình 1.5. Các dạng hình học khác nhau của cụm trong không gian R2
Hình 2.1. Cá thể cập nhật vị trí
Hình 3.1. Minh họa dữ liệu đầu vào thử nghiệm lưu trên tệp excel
Hình 3. 2. Tóm tắt trường dữ liệu đầu vào

Chiến lược tiến hóa
Thuật toán di truyền
Thuật toán tiến hóa
Tập mờ
Thuật toán tìm kiếm Tabu

viii


MỞ ĐẦU
1/ ĐẶT VẤN ĐỀ
Trong những năm gần đây, công nghệ thông tin đã có những chuyển biến
mạnh mẽ, tác động lớn đến sự phát triển của xã hội. Sự bùng nổ thông tin đã đem
đến lượng dữ liệu khổng lồ. Chúng ta càng có nhu cầu khám phá kho dữ liệu đó
phục vụ cho nhu cầu con người, điều đó đòi hỏi con người phải biết khai thác dữ
liệu và xử lý thông tin đó thành tri thức có ích.
Một trong những kỹ thuật quan trọng trong quá trình khai phá dữ liệu và xử
lý dữ liệu lớn là kỹ thuật phân cụm dữ liệu. Phân cụm đặc biệt hiệu quả khi ta
không biết về thông tin của các cụm, hoặc khi ta quan tâm tới những thuộc tính của
cụm mà chưa biết hoặc biết rất ít về những thông tin đó. Phân cụm được coi như
một công cụ độc lập để xem xét phân bố dữ liệu, làm bước tiền xử lý cho các thuật
toán khác. Việc phân cụm dữ liệu có rất nhiều ứng dụng như trong lập quy hoạch
đô thị, nghiên cứu trái đất, địa lý, khai phá Web v.v.
Ngày nay, cùng với kỹ thuật phân cụm kết hợp với lý thuyết mờ của Zadeh
phương pháp phân cụm mờ đã và đang phát triển và được ứng dụng rộng rãi trong
thực thực tiễn, ví dụ như phân tích nhu cầu khách hàng, phân đoạn ảnh, nhận dạng
mặt người, nhận dạng cử chỉ và điệu bộ, phân tích rủi ro, dự báo nguy cơ phá sản
cho ngân hàng và nhiều bài toán khác. Những vấn đề chính được quan tâm nhiều
trong phân cụm nói chung và phân mờ nói riêng là nâng cao chất lượng phân cụm,
tính toán thông qua một số độ đo chất lượng cụ thể. Những nhược điểm của phân


2


3/ BỐ CỤC CỦA LUẬN VĂN
Luận văn gồm 3 chương, có phần mở đầu, phần kết luận, phần mục lục, phần
tài liệu tham khảo. Các nội dung cơ bản của luận văn được trình bày theo cấu trúc
như sau:
Chương 1: Tổng quan về phân cụm mờ
Trong chương này, luận văn sẽ trình bày tổng quan về tập mờ, bài toán phân
cụm và phân cụm mờ và thuật toán cơ bản giải quyết vấn đề phân cụm trên tập mờ
đó là thuật toán Fuzzy C – Means (FCM). Từ thuật toán này chúng tôi sẽ khảo sát
các thuật toán tối ưu tiến hóa cho bài toán phân cụm mờ.
Chương 2: Các thuật toán tối ưu tiến hóa cho phân cụm mờ
Trong chương này, các khái niệm cơ bản về tối ưu tiến hóa sẽ được nhắc lại ở
đầu chương. Tiếp theo, chúng tôi sẽ trình bày thuật toán Fuzzy J – Means (FJM)
được phát triển từ thuật toán Fuzzy C – Means (FCM) trong việc tìm nghiệm tối ưu
cho bài toán, từ đó có nhận xét về hiệu quả của bài toán phân cụm mờ được áp
dụng thuật toán trên. Tiếp theo, chúng tôi khảo sát thuật toán Variable
Neighbourhood Search (VNS) được phát triển tiếp từ thuật toán Fuzzy J – Means
và phần cuối của chương này trình bày về thuật toán Fuzzy Particle Swarm
Optimization (FPSO) lai của hai phương pháp Fuzzy C – Means và Particle Swarm
Optimization (PSO). Nhận xét chung các thuật toán cũng được nhắc trong chương
này.
Chương 3: So sánh hiệu năng thuật toán tối ưu tiến hoá
Trong chương này, chúng tôi cài đặt và đánh giá hiệu năng các thuật toán:
FCM, FJM, VNS và FPSO theo các tiêu chí về chất lượng phân cụm thông qua giá
trị hàm mục tiêu và thời gian tính toán. Từ đây, hiệu quả của các thuật toán tối ưu
tiến hóa cho phân cụm mờ được khẳng định.
3

mãn điều kiện với
F

x

X,0
x,

F

F

x

x

x

1.

X

5


Khi

F

x = 0 thì x

Như vậy, khái niệm tập mờ là sự tổng quát hóa khái niệm tập rõ bởi hàm thuộc
của nó có thể lấy giá trị bất kỳ trong khoảng [0, 1], tập rõ chỉ là một tập mờ đặc biệt
vì hàm thuộc F x chỉ nhận hai giá trị 0 hoặc 1.
Ví dụ 1.3: X = {X1, X2, X3, X4}

Biểu diễn tập mờ theo đồ thị.

Hàm thuộc không còn mang 2
giá trị tuyệt đối 0 hay 1, mà là giá trị
thuộc đoạn [0,1].

Hình 1.1: Tập mờ và biểu diễn tập mờ
Ví dụ 1.4: Cho tập X gồm 5 người là x1 , x 2 , x 3 , x 4 , x 5 tương ứng có tuổi là
50, 10, 15, 55, 70, xác định tập F là tập hợp những người “Trẻ”?
Ta có thể xây dựng hàm thuộc như sau: µF(50)=0.35, µF(10)=0.95,
µF(15)=0.75, µF(55)=0.30, µF(70)=0.05.
6


Khi đó tập mờ F = {(50, 0.35) (10, 0.95) (15, 0.75) (55, 0.30)(70, 0.05)} và F
được biểu diễn như Hình 1.2 sau:

Hình 1.2: Ví dụ một tập mờ
* Số mờ
Xét tập mờ F trên tập các số thực R. Về nguyên tắc, không có ràng buộc chặt
đối với việc xây dựng các tập mờ để biểu thị ngữ nghĩa của các khái niệm ngôn
ngữ. Tuy nhiên, để đơn giản trong xây dựng các tập mờ và trong tính toán trên các
tập mờ, người ta đưa ra khái niệm tập mờ có dạng đặc biệt, gọi là số mờ để biểu thị
các khái niệm mờ về số như gần 10, khoảng 15, lớn hơn nhiều so với 10,v.v.
Trong điều khiển, với mục đích sử dụng các hàm thuộc sao cho khả năng tích

1.2.1. Khái quát phân cụm
Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các
phương pháp học không giám sát trong học máy, 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 và quan trọng trong tập dữ liệu lớn để từ đó
cung cấp thông tin, tri thức cho việc ra quyết định.
Có rất nhiều định nghĩa khác nhau về kỹ thuật này, nhưng về bản chất ta có thể
hiểu phân cụm là các qui trình tìm cách nhóm các đối tượng đã cho vào các cụm,


8


sao cho các đối tượng trong cùng một cụm tương tự nhau và các đối tượng khác
cụm thì không tương tự nhau [23].
Mục đích của phân cụm là tìm ra bản chất bên trong các nhóm nội tại bên
trong của bộ dữ liệu không có nhãn. Tuy nhiên, không có tiêu chí nào là được xem
là tốt nhất để đánh giá hiệu quả của phân tích phân cụm, điều này phụ thuộc vào
mục đích cuối cùng của phân cụm dữ liệu. Do đó, người sử dụng phải cung cấp tiêu
chuẩn, theo cách như vậy mà kết quả của phân cụm sẽ phù hợp với nhu cầu của
người sử dụng cần.
Định nghĩa 1.1:
Cho X là một tập dữ liệu gồm N
chia tập dữ liệu X , c cụm dữ liệu Z z

vector: x1 , x 2 ,..., x N . Bài toán phân cụm là
1

,z 2 ,..., z c .

Thỏa mãn 3 điều kiện sau:

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), v.v, 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
9


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 cơ sở dữ liệu 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ý,

v.v, 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, v.v.
1.2.2. Độ đo gần gũi
Trong định nghĩa về bài toán phân cụm, chúng tôi đã đưa ra cụm từ “đối tượng
tương tự nhau”. Vậy hai đối tượng như thế nào để gọi là tương tự nhau và làm sao
để đo mức độ tương tự giữa chúng.

nhau.
Một số độ đo không tương tự:
Khoảng cách giữa hai đối tượng x , y như sau
Khoảng cách Minskowski:
n

q 1/q

d (x, y)

xi

yi

i1

với q là số nguyên dương.
Khoảng cách Euclide:
n

d (x, y)

xi
i

yi

2

1

có thể “mã hoá” nhiều nhất thông tin liên quan đến công việc. Mục tiêu chính của
bước này là phải giảm thiểu sự dư thừa thông tin giữa các đặc trưng. Các đặc trưng
cần được tiền xử lý trước khi dùng chúng trong các bước sau.
-

Chọn độ đo gần gũi: Đây là một độ đo chỉ ra mức độ tương tự hay không

tương tự giữa hai véc tơ đặc trưng. Phải đảm bảo rằng tất cả các véc tơ đặc trưng
góp phần như nhau trong việc tính toán độ đo gần gũi và không có đặc trưng nào át
hẳn đặc trưng nào. Điều này được đảm nhận bởi quá trình tiền xử lý.
-

Tiêu chuẩn phân cụm: Điều này phụ thuộc vào sự giải thích của chuyên gia

cho thuật ngữ “dễ nhận thấy” dựa vào loại của các cụm được chuyên gia cho rằng
đang ẩn dấu dưới tập dữ liệu. Chẳng hạn, cụm trong không gian một chiều sẽ có
tiêu chuẩn khác với cụm trong không gian nhiều chiều.
-

Thuật toán phân cụm: Cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm

làm sáng tỏ cấu trúc cụm của tập dữ liệu.
-

Công nhận kết quả: Khi đã có kết quả phân loại thì ta phải kiểm tra tính

đúng đắn của nó. Điều này thường được thực hiện bởi việc dùng các kiểm định
thích hợp.
-


Kỹ thuật phân cụm có thể được áp dụng cho dữ liệu được định lượng (kiểu
số), định lượng (phân loại) hoặc có thể kết hợp cả hai.
Dữ liệu được quan sát bằng quá trình vật lý. Mỗi quan sát chứa n biến độ đo,

x11
X
x

n1


Trong thuật ngữ nhận dạng mẫu, các cột của ma trận được gọi là các mẫu hay
các đối tượng, các dòng gọi là các đặc trưng hay các thuộc tính, và X gọi là mẫu
hoặc ma trận dữ liệu. Ý nghĩa của các cột và các hàng của X phụ thuộc vào ngữ
cảnh. Ví dụ, trong hoạt động sản xuất kinh doanh các cột của X có thể chứa các mẫu
như là: doanh số, lợi nhuận, thanh toán, nợ quá hạn.
1.2.4.2. Các cụm và các mẫu trong phân cụm mờ
Chúng ta đã biết một cụm là một nhóm các đối tượng tương tự nhiều hơn các
đối tượng trong những cụm khác [23]. Thuật ngữ “tương tự” cần được hiểu như
tương tự toán học. Trong không gian metric, tương tự được xác định bằng độ đo
khoảng cách.
Dữ liệu cho thấy thấy các cụm có dạng hình học khác nhau, kích thước và mật
độ khác nhau (xem Hình 1.5).

Hình 1.5. Các dạng hình học khác nhau của cụm trong không gian R2
Trong tập dữ liệu khi cụm (a) có dạng hình cầu, cum (b) đến cụm (d) có thể
được đặc trưng là tuyến tính hoặc phi tuyến. Hiệu quả của hầu hết các thuật toán
phân cụm bị ảnh hưởng bởi hình dạng hình học và phân bố của các cụm, mà còn bị
ảnh hưởng bởi khoảng cách giữa các cụm. Các cụm có thể riêng biệt, liên tục, hoặc
chồng lên nhau.