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


Cuối cùng em xin chân thành cảm ơn tới gia đình, bạn bè, đồng nghiệp đã luôn
bên em cổ vũ, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện luận
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

Cài đặt chương trình........................................................................................... 58
2.5. Kết luận chương ................................................................................................ 61
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 R 2
Hình 2.1. Cá thể cập nhật vị trí


Fuzzy C – Means

Phân cụm mờ J - Means

FJM

Fuzzy J – Means

Tìm kiếm lân cận biến đổi

VNS

Variable

neighbourhood

search
Tối ưu bầy đàn

PSO
vii

Particle Swarm Optimization


Tối ưu bầy đàn mờ

FPSO



Tập mờ

FS

Fuzzy Set

Thuật toán tìm kiếm Tabu

TS

Tabu search

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.

cầu của nhóm khách hàng và mức độ hài lòng về sản phẩm và dịch vụ của doanh
nghiệp.
Cụ thể với một cơ sở dữ liệu mẫu về thống kê doanh doanh số bán hàng của
một công ty kinh doanh thiết bị y tế cho khoảng 500 bệnh viện [26] được sử dụng
làm dữ liệu đầu vào cho các thuật toán trên. Qua đây, tính hiệu quả của các thuật
toán tối ưu tiến hóa cho bài toán phân cụm mờ theo các tiêu chí về chất lượng và
thời gian tính toán được làm rõ đồng thời phác họa chi tiết về các chức năng chính
của bài toán phân tích nhu cầu khách hàng.

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

cả về lý thuyết và ứng dụng trong các bài toán điều khiển mờ, khai phá dữ liệu mờ,
cơ sở dữ liệu mờ, các hệ hỗ trợ quyết định
Tập mờ FS được định nghĩa như sau:
1.1.2. Tập mờ
Định nghĩa 1.2 [25]: Cho tập nền X và x là phần tử của tập X . Một tập mờ
F trên tập X được định nghĩa bởi một hàm thành viên hay còn gọi là hàm thuộc

 F  x  (degree of membership), đo “mức độ” mà phần tử x thuộc về tập F thỏa

mãn điều kiện với  x  X , 0   F  x  1.
F

 x, 

F

 x x  X 
5


Khi  F  x  = 0 thì x  F hoàn toàn. Khi  F  x  = 1 thì  x  F hoàn toàn.
Tập mờ F rỗng nếu và chỉ nếu  F  x  = 0 với  x  X
Tập mờ F toàn phần nếu và chỉ nếu  F  x  = 1 với  x  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}

Hàm thuộc không còn mang 2



0,
x  ac

 x  a  c / c, a  c  x  a

 
F  x   
1,
a xb
 b  d  x  / d , b  x  b  d

0,
d d  x


Hình 1.3. Số mờ hình thang.
Số mờ hình tam giác
Số mờ hình tam giác là trường hợp đặc biệt của số mờ hình thang. Hàm
thành viên có dạng sau:
xa
b  a , a  x  b

c  x
F  x   
, b xc
cb
otherwise
 0,





X   i 1 zi



zi  z j   với i  j ; i, j  1, 2,..., c

c

Phân cụm được đóng vai trò quan trọng trong các nghành khoa học:
- Thương mại: Phân cụm dữ liệu giúp các nhà cung cấp biết được nhóm khác
hàng quan trọng có các đặc trưng tương đồng nhau và đặc tả họ từ các mẫu trong
cơ sở dữ liệu khách hàng.
- 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), 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

Khoảng cách giữa hai đối tượng x , y như sau
 Khoảng cách Minskowski:
1/ q

 n
q
d ( x, y )    xi  yi 
 i 1


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

d ( x, y ) 

 x  y 
i

2

i

i 1

Đây là trường hợp đặc biệt của khoảng cách Minkowski với q  2
N

 Khoảng cách Manhattan:   x, y    i 1 xi  yi .
 Khoảng cách cực đại:   x, y   max i 1.. N xi  yi

Phân cụm có ràng buộc
11


1.2.3. Các bước phân cụm
- Chọn lựa đặc trưng: Các đặc trưng phải được chọn lựa một cách hợp lý để
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.
- Giải thích kết quả: Trong rất nhiều trường hợp, chuyên gia trong lĩnh vực
ứng dụng phải kết hợp kết quả phân loại với những bằng chứng thực nghiệm và
phân tích để đưa ra được kết quả đúng đắn.
Tóm lại, phân cụm dữ liệu là một vấn đề đòi hỏi chúng ta phải giải quyết
những công việc sau đây:
- Biểu diễn dữ liệu.
- Xây dựng hàm tính độ tương tự.
- Xây dựng các tiêu chuẩn phân cụm.

X  
 xn1





x1N 
 
xnN 

13


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


0  u  1
kj

 c
 ukj  1
 j 1
N

0   ukj  N
k 1


j  1, 2,.., c
k  1, 2,.., N

1.3. Thuật toán Fuzzy C – Means (FCM)
Phân cụm dữ liệu đóng vai trò quan trọng trong giải quyết bài toán nhân biết
mẫu và xác định mô hình mờ. Thuật toán FCM phù hợp hơn với dữ liệu lớn hoặc
nhỏ phân bố quanh tâm cụm.

15