Luận văn: NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÂN CỤM MỜ VÀ ỨNG DỤNG

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN AN HỒNG SƠN NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP

PHÂN CỤM MỜ VÀ ỨNG DỤNG

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC HƯỚNG DẪN KHOA HỌC: PGS.TS NGÔ QUỐC TẠO

THÁI NGUYÊN - 2008

MỤC LỤC

DANH MỤC CÁC TỪ VIẾT TẮT ........................................................................

DANH MỤC CÁC HÌNH MINH HOẠ ................................................................

Chƣơng 1 - TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KPDL ..................

1.1. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu .................

1.2. Quá trình khám phá tri thức .................................................................

1.3. Quá trình khai phá dữ liệu ....................................................................

1.4. Các phƣơng pháp khai phá dữ liệu .......................................................

1.5. Các lĩnh vực ứng dụng thực tiễn của KPDL ........................................

1.6. Các hƣớng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL ..............

1.7. Các thách thức - khó khăn trong KPTT và KPDL................................

1.8. Kết luận ................................................................................................

Chƣơng 2 - PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG PCDL .

2.1. Khái niệm và mục tiêu của phân cụm dữ liệu ......................................

2.2. Các ứng dụng của phân cụm dữ liệu ....................................................

2.3. Các yêu cầu của phân cụm ...................................................................

2.4. Những kỹ thuật tiếp cận trong phân cụm dữ liệu .................................

2.4.1. Phƣơng pháp phân cụm phân hoạch ..........................................

2.4.2. Phƣơng pháp phân cụm phân cấp ..............................................

2.4.3. Phƣơng pháp phân cụm dựa trên mật độ ...................................

2.4.4. Phƣơng pháp phân cụm dựa trên lƣới .......................................

2.4.5. Phƣơng pháp phân cụm dựa trên mô hình .................................

2.4.6. Phƣơng pháp phân cụm có dữ liệu ràng buộc ...........................

2.5. Một số thuật toán cơ bản trong phân cụm dữ liệu ................................

2.5.1. Các thuật toán phân cụm phân hoạch ........................................

2.5.2. Các thuật toán phân cụm phân cấp ............................................

2.5.3. Các thuật toán phân cụm dựa trên mật độ .................................

2.5.4. Các thuật toán phân cụm dựa trên lƣới ......................................

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

2.5.5. Các thuật toán phân cụm dựa trên mô hình ...............................

2.5.6. Các thuật toán phân cụm có dữ liệu ràng buộc .........................

Chƣơng 3 - KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ .........................................

3.1. Tổng quan về phân cụm mờ .................................................................

3.2. Các thuật toán trong phân cụm mờ ......................................................

3.2.1. Thuật toán FCM(Fuzzy C-means) .............................................

3.2.1.1. Hàm mục tiêu .............................................................

3.2.1.2. Thuật toán FCM .........................................................

3.2.2. Thuật toán FCM(ε- Insensitive Fuzzy C-means) .....................

3.2.2.1. Hàm mục tiêu .............................................................

3.2.2.2. Thuật toán FCM ........................................................

3.2.3. Thuật toán FCM Cải tiến ...........................................................

3.2.3.1. Thuật toán 1: Thuật toán lựa chọn các điểm dữ liệu

làm ứng viên cho việc chọn các trung tâm của các cụm .......

3.2.3.2. Thuật toán 2: Thuật toán lƣợc bớt các ứng viên ........

3.2.3.3. Thuật toán 3: Thuật toán chọn các ứng viên làm cực

tiểu hàm mục tiêu ..................................................................

3.2.3.4. Thuật toán 4: Gán các trung tâm có liên kết “gần

gũi” vào một cụm ..................................................................

3.2.3.5. Tổng kết thuật toán FCM-Cải tiến .............................

Chƣơng 4 - MÔ HÌNH MẠNG NƠRON ĐA KHỚP DÙNG CHO PCM ............

4.1. Tổng quan về mạng Nơron ...................................................................

4.2. Cấu trúc mạng Nơron ...........................................................................

4.2.1. Hàm kích hoạt ...........................................................................

4.2.2. Liên kết mạng ............................................................................

4.2.3. Bài toán huấn luyện mạng .........................................................

4.3. Mạng HOPFIELD ................................................................................

4.3.1. Huấn luyện mạng .......................................................................

4.3.2. Sử dụng mạ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

4.4. Mạng Nơron đa khớp dùng cho phân cụm ............................................

4.4.1. Xây dựng lớp mạng Layer1 cho tối ƣu các trung tâm cụm ........

4.4.2. Xây dựng lớp mạng Layer2 cho tối ƣu các độ thuộc .................

4.5. Sự hội tụ của FBACN ...........................................................................

4.5.1. Chứng minh sự hội tụ của FBACN ............................................

4.5.2. Sự hội tụ FBACN liên tục của Layer1 .......................................

4.6. Giải thuật của FBACN và FBACN với việc học ..................................

Chƣơng 5 - CÀI ĐẶT THỬ NGHIỆM VÀ ỨNG DỤNG .....................................

5.1. Cài đặt thử nghiệm thuật toán FCM ......................................................

5.2. Ứng dụng thuật toán FCM-Cải tiến vào nhận dạng ảnh .......................

KẾT LUẬN ............................................................................................................

TÀI LIỆU THAM KHẢ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

DANH MỤC CÁC TỪ VIẾT TẮT

Công nghệ thông tin CNTT

Cơ sở dữ liệu CSDL

Computational Energy Function CEF

Dữ liệu DL

FBACN Fuzzy Bi-directional Associative Clustering Network

(Mạng Nơron đa khớp phục vụ cho phân cụm mờ)

Fuzzy C-Means FCM

Hàm mục tiêu HMT

Khai phá dữ liệu KPDL

Khám phá tri thức KPTT

Liên kết mạng LKM

Mô hình MH

Nhận dạng ảnh NDA

Neural Network NN

Phân cụm mờ PCM

Phân cụm dữ liệu PCDL

Tài liệu tham khảo TLTK

Thuật toán TT

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

Xử lý ảnh XLA

DANH MỤC CÁC HÌNH MINH HOẠ

Hình 1.1 Quá trình Khám phá tri thức ................................................... 7

Hình 1.2 Quá trình Khai phá dữ liệu ...................................................... 9

Hình 2.1 Mô tả tập dữ liệu vay nợ đƣợc phân thành 3 cụm .................1 14

Hình 2.2 Các chiến lƣợc phân cụm phân cấp .......................................2 20

Hình 2.3 Cấu trúc phân cấp ..................................................................2 21

Hình 2.4 Các cách mà các cụm có thể đƣa ra ....................................... 23

Hình 2.5 Các thiết lập để xác định ranh giới các cụm ban đầu ............. 24

Hình 2.6 Tính toán trọng tâm của các cụm mới .................................... 25

Hình 2.7 Khái quát thuật toán CURE ................................................... 27

Hình 2.8 Các cụm dữ liệu đƣợc khám phá bởi CURE .......................... 27

Hình 2.9 Hình dạng các cụm đƣợc khám phá bởi TT DBSCAN .......... 30

Hình 3.1 Mô phỏng về tập dữ liệu đơn chiều ....................................... 44

Hình 3.2 Hàm thuộc với trọng tâm của cụm A trong k-means ............. 44

Hình 3.3 Hàm thuộc với trọng tâm của cụm A trong FCM .................. 45

Hình 3.4 Các cụm khám phá đƣợc bởi thuật toán FCM ....................... 46

Hình 4.1 Mô hình mạng Nơron ............................................................. 60

Hình 4.2 Mô hình học có giám sát ........................................................ 62

Hình 4.3 Mô hình FBACN .................................................................... 64

Hình 4.4 Mô hình Lớp Layer1 của FBACN ......................................... 65

Hình 4.5 Mô hình Lớp Layer2 của FBACN ......................................... 69

Hình 5.1 Giao diện của thuật toán FCM khi khởi động ........................ 80

Hình 5.2 Giao diện của thuật toán FCM khi làm việc .......................... 81

Hình 5.3 Giao diện của chƣơng trình khi khởi động ............................. 83

Hình 5.4 Giao diện của chƣơng trình khi chọn ảnh để phân cụm .......... 84

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

Hình 5.5 Giao diện của chƣơng trình khi thực hiện phân cụm ............. 85

CHƢƠNG 1

TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC

VÀ KHAI PHÁ DỮ LIỆU

6 7 8 9 10 11 12 12

1.1. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu .................................... 1.2. Quá trình khám phá tri thức .................................................................................... 1.3. Quá trình khai phá dữ liệu ...................................................................................... 1.4. Các phƣơng pháp khai phá dữ liệu ......................................................................... 1.5. Các lĩnh vực ứng dụng thực tiễn của KPDL ........................................................... 1.6. Các hƣớng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL ................................ 1.7. Các thách thức - khó khăn trong KPTT và KPDL .................................................. 1.8. Kết luận ...................................................................................................................

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.

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

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

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 thuật toán 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.2. Quá trình khám phá tri thức

Hình 1.1: Quá trình KPTT

Bao gồm các bƣớc sau:

Làm sạch dữ liệu (Data Cleaning): Loại bỏ dữ liệu nhiễu và dữ liệu

không nhất quán.

Tích hợp dữ liệu (Data Intergation): Dữ liệu của nhiều nguồn 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

đƣợc tổ hợp lại.

Lựa chọn dữ liệu (Data Selection): Lựa chọn những dữ liệu phù hợp

với nhiệm vụ phân tích trích rút từ cơ sở dữ liệu.

Chuyển đổi dữ liệu (Data Transformation): Dữ liệu đƣợc chuyển đổi

hay đƣợc hợp nhất về dạng thích hợp cho việc khai phá.

Khai phá dữ liệu (Data Mining): Đây là một tiến trình cốt yếu trong

đó các phƣơng pháp thông minh đƣợc áp dụng nhằm trích rút ra mẫu dữ liệu.

Đánh giá mẫu (Pattern Evaluation): Dựa trên một độ đo nào đó xác

định lợi ích thực sự, độ quan trọng của các mẫu biểu diễn tri thức.

Biểu diễn tri thức (Knowledge Presentation): Ở giai đoạn này các kỹ

thuật biểu diễn và hiển thị đƣợc sử dụng để đƣa tri thức lấy ra cho ngƣời

dùng.

1.3. Quá trình khai phá dữ liệu

KPDL là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất,

nó là giai đoạn duy nhất tìm ra đƣợc thông tin mới, thông tin tiềm ẩn có trong

CSDL chủ yếu phục vụ cho mô tả và dự đoán.

Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của

những thuộc tính dữ liệu trong kho dữ liệu mà con ngƣời có thể hiểu đƣợc.

Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật

đƣợc phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó

chiết xuất ra các mẫu, dự đoán đƣợc những giá trị chƣa biết hoặc những giá trị

tƣơng lai của các biến quan tâm.

Quá trình KPDL bao gồm các bƣớc chính đƣợc thể hiện nhƣ Hình 1.2

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

Thống kê tóm tắt

Xác định nhiệm vụ

Xác định DL liên quan

Thu thập và tiền xử lý DL

Thuật toán KPD L

Mẫu

DL trực tiếp

Hình 1.2: Quá trình KPDL

 Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết.

 Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp.

 Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và

tiền xử lý chúng sao cho thuật toán KPDL có thể hiểu đƣợc. Đây là một quá

trình rất khó khăn, có thể gặp phải rất nhiều các vƣớng mắc nhƣ: dữ liệu phải

đƣợc sao ra nhiều bản (nếu đƣợc chiết xuất vào các tệp), quản lý tập các dữ

liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay

đổi), v.v..

 Thuật toán khai phá dữ liệu: Lựa chọn thuật toán KPDL và thực

hiện việc PKDL để tìm đƣợc các mẫu có ý nghĩa, các mẫu này đƣợc biểu diễn

dƣới dạng luật kết hợp, cây quyết định... tƣơng ứng với ý nghĩa của nó.

1.4. 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:

 Luật kết hợp (association rules)

 Phân lớp (Classfication)

 Hồi qui (Regression)

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

 Trực quan hóa (Visualiztion)

 Phân cụm (Clustering)

 Tổng hợp (Summarization)

 Mô hình ràng buộc (Dependency modeling)

 Biểu diễn mô hình (Model Evaluation)

 Phân tích sự phát triển và độ lệch (Evolution and deviation

analyst)

 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.5. 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:

- 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

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

- Giáo dục.....

1.6. 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:

- 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

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

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.7. Các thách thức - khó khăn trong KPTT và KPDL

KPTT và KPDL liên quan đến nhiều ngành, nhiều lĩnh vực trong thực

tế, vì vậy các thách thức và khó khăn ngày càng nhiều, càng lớn hơn. Sau đây

là một số các thách thức và khó khăn cần đƣợc quan tâm:

+ Các cơ sở dữ liệu lớn, các tập dữ liệu cần sử lý có kích thƣớc cực lớn,

Trong thực tế, kích thƣớc của các tập dữ liệu thƣờng ở mức tera-byte (hàng

ngàn giga-byte).

+ Mức độ nhiễu cao hoặc dữ liệu bị thiếu

+ Số chiều lớn

+ Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện

không còn phù hợp

+ Quan hệ giữa các trƣờng phức tạp

1.8. Kết luận

KPDL là lĩnh vực đã và đang trở thành một trong những hƣớng nghiên

cứu thu hút đƣợc sự quan tâm của nhiều chuyên gia về CNTT trên thế giới.

Trong những năm gần đây, rất nhiều các phƣơng pháp và thuật toán mới liên

tục đƣợc công bố. Điều này chứng tỏ những ƣu thế, lợi ích và khả năng ứng

dụng thực tế to lớn của KPDL. Chƣơng này đã trình bày một số 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.vn

tổng quan về KPTT, những khái niệm và kiến thức cơ bản nhất về KPDL.

CHƢƠNG 2

PHÂN CỤM DỮ LIỆU VÀ

CÁC THUẬT TOÁN TRONG PHÂN CỤM DỮ LIỆU

13 15 16 18 19 19 20 21 22 22 24 24 26 29 32 35 36

2.1. Khái niệm và mục tiêu của phân cụm dữ liệu ........................................................ 2.2. Các ứng dụng của phân cụm dữ liệu ...................................................................... 2.3. Các yêu cầu của phân cụm ..................................................................................... 2.4. Những kỹ thuật tiếp cận trong phân cụm dữ liệu ................................................... 2.4.1. Phƣơng pháp phân cụm phân hoạch ............................................................. 2.4.2. Phƣơng pháp phân cụm phân cấp ................................................................. 2.4.3. Phƣơng pháp phân cụm dựa trên mật độ ...................................................... 2.4.4. Phƣơng pháp phân cụm dựa trên lƣới ........................................................... 2.4.5. Phƣơng pháp phân cụm dựa trên mô hình .................................................... 2.4.6. Phƣơng pháp phân cụm có dữ liệu ràng buộc ............................................... 2.5. Một số thuật toán cơ bản trong phân cụm dữ liệu ................................................. 2.5.1. Các thuật toán phân cụm phân hoạch ........................................................... 2.5.2. Các thuật toán phân cụm phân cấp ............................................................... 2.5.3. Các thuật toán phân cụm dựa trên mật độ .................................................... 2.5.4. Các thuật toán phân cụm dựa trên lƣới ......................................................... 2.5.5. Các thuật toán phân cụm dựa trên mô hình .................................................. 2.5.6. Các thuật toán phân cụm có dữ liệu ràng buộc .............................................

2.1. Khái niệm và mục tiêu 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 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 là một ví dụ của phƣơng pháp học không có

thầy. Không giống nhƣ phân lớp dữ liệu, 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 bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví

dụ… 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 thuật toán khai phá dữ liệu khác nhƣ là phân loại và mô tả đặ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

điểm, có tác dụng trong việc phát hiện ra các cụm.

Hình 2.1: Mô tả tập dữ liệu vay nợ đƣợc phân thành 3 cụm.

Phân cụm có ý nghĩa rất quan trọng trong hoạt động của con ngƣời.

Ngay từ lúc bé, con ngƣời đã học cách làm thế nào để phân biệt giữa mèo và

chó, giữa động vật và thực vật và liên tục đƣa vào sơ đồ phân loại trong tiềm

thức của mình. Phân cụm đƣợc sử dụng rộng rãi trong nhiều ứng dụng, bao

gồm nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trƣờng....Với

tƣ cách là một chức năng khai phá dữ liệu, phân tích phân cụm có thể đƣợc sử

dụng nhƣ một công cụ độc lập chuẩn để quan sát đặc trƣng của mỗi cụm thu

đƣợc bên trong sự phân bố của dữ liệu và tập trung vào một tập riêng biệt của

các cụm để giúp cho việc phân tích đạt kết quả.

Một vấn đề thƣờng gặp trong phân cụm là hầu hết các dữ liệu cần cho

phân cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác

hoặc thiếu đầy đủ, vì vậy cần phải xây dựng chiến lƣợc cho bƣớc tiền xử lí dữ

liệu nhằm khắc phục hoặc loại bỏ nhiễu trƣớc khi chuyển sang giai đoạn phân

tích cụm dữ liệu. Nhiễu ở đây đƣợc hiểu là các đối tƣợng dữ liệu không chính

xác, không tƣờng minh hoặc là các đối tƣợng dữ liệu khuyết thiếu thông tin

về một số thuộc tính... Một trong các kỹ thuật xử lí nhiễu phổ biến là việ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

thay thế giá trị các thuộc tính của đối tƣợng nhiễu bằng giá trị thuộc tính

tƣơng ứng. Ngoài ra, dò tìm phần tử ngoại lai cũng là một trong những hƣớng

nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác định một

nhóm nhỏ các đối tƣợng dữ liệu khác thƣờng so với các dữ liệu trong CSDL,

tức là các đối tƣợng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu

nhằm tránh sự ảnh hƣởng của chúng tới quá trình và kết quả của phân cụm.

Mục tiêu của phân cụm là xác định đƣợc bản chất nhóm trong tập DL

chƣa có nhãn. Nhƣng để có thể quyết định đƣợc cái vì tạo thành một cụm tốt.

Nó có thể đƣợc chỉ ra rằng không có tiêu chuẩn tuyệt đối “tốt” mà có thể

không phụ thuộc vào kq phân cụm. Vì vậy, nó đòi hỏi ngƣời sử dụng phải

cung cấp tiêu chuẩn này, theo cách mà kết quả phân cụm sẽ đáp ứng yêu cầu.

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

CDL. 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 CDL, với mỗi cách thức biểu diễn khác nhau sẽ có tƣơng ứng

một thuật toán phân cụm phù hợp. 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à phù hợp 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 lĩnh vực KPDL.

2.2. Các ứng dụng của phân cụm dữ liệu

Phân cụm dữ liệu có thể đƣợc ứng dụng trong nhiều lĩnh vực nhƣ:

Thương mại: Tìm kiếm nhóm các khách hàng quan trọng có đặc

trƣng tƣơng đồng và những đặc tả họ từ các bản ghi mua bán trong CSDL

Sinh học: Phân loại các gen với các chức năng tƣơng đồng và thu

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

đƣợc các cấu trúc trong mẫu

Thư viện: Phân loại các cụm sách có nội dung và ý nghĩa tƣơng

đồng nhau để cung cấp cho độc giả

Bảo hiểm: Nhận dạng nhóm tham gia bảo hiểm có chi phí bồi

thƣờng cao, nhận dạng gian lận thƣơng mại

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

WWW: 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 KPTT từ

dữ liệu.

2.3. 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:

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 nhỏ chứa ít hơn 200 đố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 thuật toán 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 thuật

toán đƣợ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

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

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 thuật toán 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ố thuật toán 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 thuật

toán 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 thuật toán 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ố

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

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 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.

Với những yêu cầu đáng lƣu ý này, nghiên cứu của ta về phân tích phân

cụm diễn ra nhƣ sau: Đầu tiên, ta nghiên cứu các kiểu dữ liệu khác và cách

chúng có thể gây ảnh hƣởng tới các phƣơng pháp phân cụm. Thứ hai, ta đƣa

ra một cách phân loại chung trong các phƣơng pháp phân cụm. Sau đó, ta

nghiên cứu chi tiết mỗi phƣơng pháp phân cụm, bao gồm các phƣơng pháp

phân hoạch, phân cấp, dựa trên mật độ,... Ta cũng khảo sát sự phân cụm trong

không gian đa chiều và các biến thể của các phƣơng pháp khác.

2.4. Những kỹ thuật tiếp cận trong phân cụm dữ liệu

Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong

thực tế, nó đều hƣớng tới hai mục tiêu chung đó là chất lƣợng của các cụm

khám phá đƣợc và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuậ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

phân cụm có thể phân loại theo các cách tiếp cận chính sau :

2.4.1. Phương pháp phân cụm phân hoạch

Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k

nhóm cho đến khi xác định số các cụm đƣợc thiết lập. Số các cụm đƣợc thiết

lập là các đặc trƣng đƣợc lựa chọn trƣớc. Phƣơng pháp này là tốt cho việc tìm

các cụm hình cầu trong không gian Euclidean. Ngoài ra, phƣơng pháp này

cũng phụ thuộc vào khoảng cách cơ bản giữa các điểm để lựa chọn các điểm

dữ liệu nào có quan hệ là gần nhau với mỗi điểm khác và các điểm dữ liệu

nào không có quan hệ hoặc có quan hệ là xa nhau so với mỗi điểm khác. Tuy

nhiên, phƣơng pháp này không thể xử lí các cụm có hình dạng kỳ quặc hoặc

các cụm có mật độ các điểm dầy đặc. Các thuật toán phân hoạch dữ liệu có độ

phức tạp rất lớn khi xác định nghiệm tối ƣu toàn cục cho vấn đề PCDL, do nó

phải tìm kiếm tất cả các cách phân hoạch có thể đƣợc. Chính vì vậy, trên thực

tế thƣờng đi tìm giải pháp tối ƣu cục bộ cho vấn đề này bằng cách sử dụng

một hàm tiêu chuẩn để đánh giá chất lƣợng của cụm cũng nhƣ để hƣớng dẫn

cho quá trình tìm kiếm phân hoạch dữ liệu. Nhƣ vậy, ý tƣởng chính của thuật

toán phân cụm phân hoạch tối ƣu cục bộ là sử dụng chiến lƣợc ăn tham

(Greedy) để tìm kiếm nghiệm.

2.4.2. Phương pháp phân cụm phân cấp

Phƣơng pháp này xây dựng một phân cấp trên cơ sở các đối tƣợng dữ

liệu đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc

có dạng hình cây, cây phân cấp này đƣợc xây dựng theo kỹ thuật đệ quy. Có

hai cách tiếp cận phổ biến của kỹ thuật này đó là:

* Hòa nhập nhóm, thƣờng đƣợc gọi là tiếp cận Bottom-Up

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

* Phân chia nhóm, thƣờng đƣợc gọi là tiếp cận Top-Down

Hình 2.2: Các chiến lƣợc phân cụm phân cấp

Thực tế áp dụng, có nhiều trƣờng hợp 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 đã có rất nhiều thuật toán cải tiến dựa trên hai phƣơng pháp này đã đƣợc

áp dụng phổ biến trong KPDL.

2.4.3. Phương pháp phân cụm dựa trên mật độ

Kỹ thuật này nhóm các đối tƣợng dữ liệu dựa trên hàm mật độ xác

định, mật độ là số các đối tƣợng lân cận của một đối tƣợng dữ liệu theo một

nghĩa nào đó. Trong cách tiếp cận này, khi một 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 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 trên mật độ của các đối tƣợng để xác định các cụm dữ liệu có

thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Kỹ thuật này có thể khắc

phục đƣợc các phần tử ngoại lai hoặc giá trị nhiễu rất tốt, tuy nhiên 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ố

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

này lại có tác động rất lớn đến kết quả phân cụm.

2.4.4. Phương pháp phân cụm dựa trên lưới

Kỹ thuật phân cụm dựa trên lƣới thích hợp với dữ liệu nhiều chiều, dựa

trên cấu trúc dữ liệu lƣới để phân cụm, phƣơng pháp này chủ yếu tập trung áp

dụng cho lớp dữ liệu không gian. Mục tiêu của phƣơng pháp này là lƣợng hóa

dữ liệu thành các ô tạo thành cấu trúc dữ liệu lƣới. Sau đó, các thao tác phân

cụm chỉ cần làm việc với các đối tƣợng trong từng ô trên lƣới chứ không phải

các đối tƣợng dữ liệu. 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 ô. 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úng không trộn các ô, đồng thời giải quyết khắc phục yêu

cầu đối với dữ liệu nhiều chiều mà phƣơng pháp phân phân cụm dựa trên mật

độ không giải quyết đƣợc. Ƣu điểm của phƣơng pháp phân cụm dựa trên lƣới

là thời gian xử lí nhanh và độc lập với số đối tƣợng dữ liệu trong tập dữ liệu

ban đầu, thay vào đó là chúng phụ thuộc vào số ô trong mỗi chiều của không

gian lƣới.

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

Hình 2.3: Cấu trúc phân cấp

2.4.5. Phương pháp phân cụm dựa trên mô hình

Phƣơng 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 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 chúng hiệu chỉnh các mô

hình này để nhận dạng ra các phân hoạch. Phƣơng pháp phân cụm dựa trên

mô hình cố gắng khớp giữa các 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 cách tiếp cận chính: mô hình

thống kê và mạng nơron. Phƣơng pháp này gần giống với phƣơng pháp phân

cụm dựa trên mật độ, vì chúng phát triển các cụm riêng biệt nhằm cải tiến các

mô hình đã đƣợc xác định trƣớc đó, nhƣng đôi khi nó không bắt đầu với một

số cụm cố định và không sử dụng cùng một khái niệm mật độ cho các cụm.

2.4.6. Phương pháp phân cụm có dữ liệu ràng buộc

Sự phát triển của PCDL không gian trên CSDL lớn đã cung cấp nhiều

công cụ tiện lợi cho việc phân tích thông tin địa lí, tuy nhiên hầu hết các thuật

toán này cung cấp rất ít cách thức cho ngƣời dùng để xác định các ràng buộc

trong thế giới thực cần phải đƣợc thỏa mãn trong quá trình phân cụm. Để

PCDL không gian hiệu quả hơn, các nghiên cứu bổ sung cần đƣợc thực hiện

để cung cấp cho ngƣời dùng khả năng kết hợp các ràng buộc trong thuật toán

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

phân cụm.

Hình 2.4: Các cách mà các cụm có thể đƣa ra

Hiện nay, các phƣơng pháp phân cụm trên đã và đang đƣợc phát triển

và áp dụng nhiều trong các lĩnh vực khác nhau và đã có một số nhánh nghiên

cứu đƣợc phát triển trên cơ sở của các phƣơng pháp đó nhƣ:

Phân cụm thống kê: Dựa trên các khái niệm phân tích hệ thống, nhánh nghiên

cứu này sử dụng các độ đo tƣơng tự để phân hoạch các đối tƣợng, nhƣng

chúng chỉ áp dụng cho các dữ liệu có thuộc tính số.

Phân cụm khái niệm: Kỹ thuật này đƣợc phát triển áp dụng cho dữ liệu hạng

mục, chúng phân cụm các đối tƣợng theo các khái niệm mà chúng xử lí.

Phân cụm mờ: Sử đụng kỹ thuật mờ để PCDL. Các thuật toán thuộc loại này

chỉ ra lƣợc đồ phân cụm thích hợp với tất cả các hoạt động đời sống hàng

ngày, chúng chỉ xử lí các dữ liệu thực không chắc chắn.

Phân cụm mạng Kohonen: Loại phân cụm này dựa trên khái niệm của cá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

mạng nơron. Mạng Kohonen có tầng nơron vào và các tầng nơron ra. Mỗi

nơron của tầng vào tƣơng ứng với mỗi thuộc tính của bản ghi, mỗi một nơron

vào kết nối với tất cả các nơron của tầng ra. Mỗi liên kết đƣợc gắn liền với

một trọng số nhằm xác định vị trí của nơron ra tƣơng ứng.

2.5. Một số thuật toán cơ bản trong phân cụm dữ liệu

2.5.1. Các thuật toán phân cụm phân hoạch

Thuật toán k-means

Thuật toán này dựa trên độ đo khoảng cách của các đối tƣợng dữ liệu

trong cụm. Trong thực tế, nó đo khoảng cách tới giá trị trung bình của các đối

tƣợng dữ liệu trong cụm. Nó đƣợc xem nhƣ là trung tâm của cụm. Nhƣ vậy,

nó cần khởi tạo một tập trung tâm các trung tâm cụm ban đầu, và thông qua

đó nó lặp lại các bƣớc gồm gán mỗi đối tƣợng tới cụm mà trung tâm gần, và

tính toán tại tung tâm của mỗi cụm trên cơ sở gán mới cho các đối tƣợng. Quá

trình lặp này dừng khi các trung tâm hội tụ.

Hình 2.5: Các thiết lập để xác định ranh giới các cụm ban đầu

Mục đích của thuật toán k-means là sinh k cụm dữ liệu {C1, C2,..., Ck}

từ một tập dữ liệu chứa n đối tƣợng trong không gian d chiều Xi = {xi1, xi2,...,

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

xid}, i = 1  n, sao cho hàm tiêu chuẩn:

đạt giá trị tối thiểu,

trong đó: mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tƣợng.

Hình 2.6: Tính toán trọng tâm của các cụm mới

Thuật toán k-means bao gồm các bƣớc cơ bản sau :

Input: Số cụm k và các trọng tâm cụm

Output: Các cụm C[i] (1  i  k) và hàm tiêu chuẩn E đạt giá trị tối thiểu.

Begin

(a)

Bƣớc 1 : Khởi tạo

Chọn k trọng tâm

ban đầu trong không gian Rd (d là số chiều của

dữ liệu). Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm.

(b)

Bƣớc 2: Tính toán khoảng cách

Đối với mỗi điểm Xi (1  i  n), tính toán khoảng cách của nó tới mỗi

trọng tâm mj (1  j  k). Sau đó tìm trọng tâm gần nhất đối với mỗi điểm.

(c)

Bƣớc 3: Cập nhật lại trọng tâm

Đối với mỗi 1  j  k, cập nhật trọng tâm cụm mj bằng cách xác định

trung bình cộng các vectơ đối tƣợng dữ liệu.

(d)

Điều kiện dừ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

Lặp lại các bƣớc 2 và 3 cho đến khi các trọng tâm của cụm không thay

đổi.

End.

Thuật toán k-means trên đƣợc chứng minh là hội tụ và có độ phức tạp

tính toán là . Trong đó, n là số đối tƣợng dữ liệu, k là số cụm dữ

liệu, d là số chiều, là số vòng lặp, 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-means 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-means 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-means 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-means

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 trọng tâm cụm tự nhiên thì kết quả phân cụm của k-means là rất thấp,

nghĩa là các cụm dữ liệu đƣợc khám phá rất lệch so với các cụm trong thực tế.

Trên thực tế chƣa có một giải pháp tối ƣu nào để chọn các tham số đầu vào,

giải pháp thƣờng đƣợc sử dụng nhất là thử nghiệm với các giá trị đầu vào k

khác nhau rồi sau đó chọn giải pháp tốt nhất.

Ngoài ra thuật toán K-means ra, phân cụm phân hoạch còn bao gồm

một số các thuật toán khac nhƣ: Thuật toán PAM; Thuật toán CLARA; Thuật

toán CLARANS.

2.5.2. Các thuật toán phân cụm phân cấp

Thuật toán CURE

Trong khi hầu hết các thuật toán thực hiện phân cụm với các cụm hình

cầu và kích thƣớc tƣơng tự, nhƣ vậy là không hiệu quả khi xuất hiện các phần

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

tử ngoại lai. Thuật toán CURE khắc phục đƣợc vấn đề này và tốt hơn với các

phần tử ngoại lai. Thuật toán này định nghĩa một số cố định các điểm đại diện

nằm rải rác trong toàn bộ không gian dữ liệu và đƣợc chọn để mô tả các cụm

đƣợc hình thành. Các điểm này đƣợc tạo ra nhờ lựa chọn các đối tƣợng nằm

rải rác cho cụm và sau đó “co lại” hoặc di chuyển chúng về trung tâm cụm

bằng nhân tố co cụm. Quá trình này đƣợc lặp lại và nhƣ vậy trong quá trình

này, có thể đo tỉ lệ gia tăng của cụm. Tại mỗi bƣớc của thuật toán, hai cụm có

cặp các điểm đại diện gần nhau (mỗi điểm trong cặp thuộc về mỗi cụm khác

nhau) đƣợc hòa nhập.

Hình 2.7: Khái quát thuật toán CURE

Nhƣ vậy, có nhiều hơn một điểm đại diện mỗi cụm cho phép CURE

khám phá đƣợc các cụm có hình dạng không phải là hình cầu. Việc co lại các

cụm có tác dụng làm giảm tác động của các phần tử ngoại lai. Nhƣ vậy, thuật

toán này có khả năng xử lí tốt trong trƣờng hợp có các phần tử ngoại lai và

làm cho nó hiệu quả với những hình dạng không phải là hình cầu và kích

thƣớc độ rộng biến đổi. Hơn nữa, nó tỉ lệ tốt với CSDL lớn mà không làm

giảm chất lƣợng phân cụm.

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

Hình 2.8: Các cụm dữ liệu đƣợc khám phá bởi CURE

Để xử lí đƣợc các CSDL 1ớn, CURE sử dụng mẫu ngẫu nhiên và phân

hoạch, một mẫu là đƣợc xác định ngẫu nhiên trƣớc khi đƣợc phân hoạch, và

sau đó tiến hành phân cụm trên mỗi phân hoạch, nhƣ vậy mỗi phân hoạch là

từng phần đã đƣợc phân cụm, các cụm thu đƣợc lại đƣợc phân cụm lần thứ

hai để thu đƣợc các cụm con mong muốn, nhƣng mẫu ngẫu nhiên không nhất

thiết đƣa ra một mô tả tốt cho toàn bộ tập dữ liệu.

Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu.

Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thƣớc bằng

nhau: Ý tƣởng chính ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng

nhau, kích thƣớc của mỗi phân hoạch là n’/p (n’ là kích thƣớc của mẫu).

Phân cụm các điểm của mỗi nhóm: Thực hiện PCDL cho các nhóm

cho đến khi mỗi nhóm đƣợc phân thành n’/pq cụm (với q > 1).

Loại bỏ các phần tử ngoại lai: Trƣớc hết, khi các cụm đƣợc hình

thành cho đến khi số các cụm giảm xuống một phần so với số các cụm

ban đầu. Sau đó, trong trƣờng hợp các phần tử ngoại lai đƣợc lấy mẫu

cùng với quá trình pha khởi tạo mẫu dữ liệu, thuật toán sẽ tự động loại bỏ

các nhóm nhỏ.

Phân cụm các cụm không gian: các đối tƣợng đại diện cho các cụm

di chuyển về hƣớng trung tâm cụm, nghĩa là chúng đƣợc thay thế bởi các

đối tƣợng gần trung tâm hơn.

Đánh dấu dữ liệu với các nhãn tƣơng ứng.

Thuật toán CURE đƣợc thực hiện qua các bƣớc cơ bản sau:

Độ phức tạp tính toán của thuật toán CURE là O(n21og(n)). CURE tà

thuật toán tin cậy trong việc khám phá ra các cụm với hình thù bất kỳ và có

thể áp dụng tốt đối với dữ liệu có phần tử ngoại lai và trên các tập dữ liệu hai

chiều. Tuy nhiên, nó lại rất nhạy cảm với các tham số nhƣ số các đối tƣợ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

đại diện, tỉ lệ co của các phần tử đại điện.

Ngoài thuật toán CURE ra, phân cụm phân cấp còn bao gồm một số

thuật toán khac nhƣ: Thuật toán BIRCH; Thuật toán AGNES; Thuật toán

DIANA; Thuật toán ROCK; Thuật toán CHANMELEON.

2.5.3. Các thuật toán phân cụm dựa trên mật độ

Thuật toán DBSCAN

Thuật toán DBSCAN thích nghi với mật độ dầy để phân cụm và khám

phá ra các cụm có hình dạng bất kỳ trong không gian CSDL có nhiễu.

Trên thực tế DBSCAN tìm kiếm cho các cụm bằng cách kiểm tra các

đối tƣợng mà có số đối tƣợng láng giềng nhỏ hơn một ngƣỡng tối thiểu, tức là

có tối thiểu MinPts đối tƣợng và mỗi đối tƣợng trong cụm tồn tại một đối

tƣợng khác trong cụm giống nhau với khoảng cách nhỏ một ngƣỡng Eps. Tìm

tất cả các đối tƣợng mà các láng giềng của nó thuộc về lớp các đối tƣợng đã

xác định ở trên, một cụm đƣợc xác định bằng một tập tất cả các đối tƣợng liên

thông mật độ các láng giềng của nó. DBSCAN lặp lại tìm kiếm ngay khi các

đối tƣợng liên lạc mật độ từ các đối tƣợng trung tâm, nó có thể bao gồm việc

kết hợp một số cụm có mật độ liên lạc. Quá trình kết thúc khi không tìm đƣợc

điểm mới nào có thể thêm vào bất cứ cụm nào.

DBSCAN có thể tìm ra các cụm với hình thù bất kỳ, trong khi đó tại

cùng một thời điểm ít bị ảnh hƣởng bởi thứ tự của các đối tƣợng dữ liệu nhập

vào. Khi có một đối tƣợng đƣợc chèn vào chỉ tác động đến một láng giềng xác

định. Mặt khác, DBSCAN sử dụng tham số Eps và MinPts trong thuật toán để

kiểm soát mật độ của các cụm. DBSCAN bắt đầu với một điểm tuỳ ý và xây

dựng mật độ láng giềng có thể đƣợc đối với Eps và MinPts. Vì vậy, DBSCAN

yêu cầu ngƣời dùng xác định bán kính Eps của các láng giềng và số các láng

giềng tối thiểu MinPts, các tham số này khó mà xác định đƣợc tối ƣu, thô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

thƣờng nó đƣợc xác định bằng phép chọn ngẫu nhiên hoặc theo kinh nghiệm.

Độ phức tạp của DBSCAN là O(n2), nhƣng nếu áp dụng chỉ số không gian để

giúp xác định các láng giềng của một đối tƣợng dữ liệu thì độ phức của

DBSCAN đã đƣợc cải tiến là O(nlogn). Thuật toán DBSCAN có thể áp dụng

cho các tập dữ liệu không gian lớn đa chiều, khoảng cách Euclide đƣợc sử

dụng để đo sự tƣơng tự giữa các đối tƣợng nhƣng không hiệu quả đối với dữ

liệu đa chiều.

Hình 2.9: Hình dạng các cụm đƣợc khám phá bởi thuật toán DBSCAN

Thuật toán: DBSCAN khởi tạo điểm p tùy ý và lấy tất cả các điểm

liên lạc mật độ từ p tới Eps và MinPts. Nếu p là điểm nhân thì thủ tục trên tạo

ra một cụm theo Eps và MinPts, nếu p là một điểm biên, không có điểm nào

liên lạc mật độ từ p và DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu.

Nếu sử dụng giá trị toàn cục Eps và Minpts, DBSCAN có thể hoà nhập

hai cụm thành một cụm nếu mật độ của hai cụm gần bằng nhau. Giả sử

khoảng cách giữa hai tập dữ liệu S1 và S2 đƣợc định nghĩa là:

dist(S1, S2) = min{dist(p, q) {p S1 và q S2}.

......... Modul chƣơng trình chính ..........

DBSCAN(SetOfPoints, Eps, MinOts)

//SetOfPoints is UNCLASSIFIED

Clusterid:= NextId(NOISE);

FOR i FROM 1 TO SetOfPoints.size DO

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

Thuật toán DBSCAN đƣợc mô tả chi tiết nhƣ sau:

Point := SetOfPoints.get(i);

IF PointClId = UNCLASSIFIED THEN

IF ExpandCluster(SetOfPoints, Point, ClusterId, Eps, MinPts)

THEN

ClusterId.= nextId(ClusterId)

END IF

END FOR

END; //DBSCAN

--------Thủ tục ExpandCluster--------

ExpandClusster(SetOfPoints, Points, C1Id, Eps, MinPts): Boolean;

seeds:= SetOfPoints.regionQuery(Point, Eps)

IF seeds.size < MinPts THEN //no core point

SetOfPoints.changeclId(Point, NOISE),

RETURN False;

ELSE //all points in seeds are density-reachable from Point

SetOfPoints.changeClId(seeds, C1Id);

seeds.delete(Point);

WHILE seeds <> Empty DO

currentP:= seeds.first();

result:= SetOfPoints.regionQuery(CurrentP, Eps);

IF result.size >= MinPts THEN

FOR i FROM 1 to result.size DO

resultpP:= result.get(i);

IF resultp.C1Id IN {UNCLASSIFIED, NOISE} THEN

IF resultp.ClId = UNCLASSIFIED THEN

seeds.append(resultP);

END IF;

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

SetOfPoints.changeC1Id(resultP, C1Id),

END IF; //UNCLASSIFIED or NOISE

END FOR;

END IF; //result.size >= Minpts

seeds.delete(currentP);

END WHILE; //seeds <> Empty

RETURN True;

END IF;

END; //ExpandCluster

Trong đó SetOfPoints hoặc là tập dữ liệu ban đầu hoặc là cụm đƣợc

khám phá từ bƣớc trƣớc, C1Id (ClusterId) là nhãn đánh dấu phần tử dữ liệu

nhiễu có thể thay đổi nếu chúng có thể liên lạc mật độ từ một điểm khác trong

CSDL, điều này chỉ xảy ra đối với các điểm biên của dữ liệu. Hàm

SetOfPoints.get(i) trả về phần tử thứ i của SetOfPoints. Thủ tục

SetOfPoints.regionQuery(Point, Eps) trả về một danh sách các điểm dữ liệu

lân cận với điểm Point trong ngƣỡng Eps từ tập dữ liệu SetOfPoints. Trừ một

số trƣờng hợp ngoại lệ, kết quả của DBSCAN là độc lập với thứ tự duyệt các

đối tƣợng dữ liệu. Eps và MinPts là hai tham số toàn cục đƣợc xác định bằng

thủ công hoặc theo kinh nghiệm. Tham số Eps đƣợc đƣa vào là nhỏ so với

kích thƣớc của không gian dữ liệu, thì độ phức tạp tính toán trung bình của

mỗi truy vấn là O(logn).

Ngoài thuật toán DBSCAN ra, phân cụm dựa trên mật độ còn bao

gồm 2 thuật toán khác nhƣ: Thuật toán OPTICS; Thuật toán DENCLUE.

2.5.4. Các thuật toán phân cụm dựa trên lƣới

Thuật toán STING

STING là kỹ thuật phân cụm đa phân giải dựa trên lƣới, trong đó vù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

không gian dữ liệu đƣợc phân rã thành số hữu hạn các ô chữ nhật, điều này có

nghĩa là các ô lƣới đƣợc hình thành từ các ô lƣới con để thực hiện phân cụm.

Có nhiều mức của các ô chữ nhật tƣơng ứng với các mức khác nhau của phân

giải trong cấu trúc lƣới, và các ô này hình thành cấu trúc phân cấp: mỗi ô ở

mức cao đƣợc phân hoạch thành số các ô nhỏ ở mức thấp hơn tiếp theo trong

cấu trúc phân cấp. Các điểm dữ liệu đƣợc nạp từ CSDL, giá trị của các tham

số thống kê cho các thuộc tính của đối tƣợng dữ liệu trong mỗi ô lƣới đƣợc

tính toán từ dữ liệu và lƣu trữ thông qua các tham số thống kê ở các ô mức

thấp hơn. Các giá trị của các tham số thống kê gồm: số trung bình - mean, số

tối đa - max, số tối thiểu - min, số đếm - count, độ lệch chuẩn - s, ...

Các đối tƣợng dữ liệu lần lƣợt đƣợc chèn vào lƣới và các tham số thống

kê ở trên đƣợc tính trực tiếp thông qua các đối tƣợng dữ liệu này. Các truy

vấn không gian đƣợc thực hiện bằng cách xét các ô thích hợp tại mỗi mức của

phân cấp. 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 hoà nhập các ô của cấu trúc lƣới để hình thành các cụm, nó không xem

xét quan hệ không gian giữa các nút của mức con không đƣợc hoà nhập phù

hợp (do chúng chỉ tƣơng ứng với các cha của nó) và hình dạng của các cụm

dữ liệu khám phá đƣợc, tất cả ranh giới của các cụm có các biên ngang và

dọc, theo biên của các ô và không có đƣờng biên chéo đƣợc phát hiện ra.

Một trong những hạn chế trong khi sử dụng cách tiếp cận đa phân giải

để thực hiện phân tích cụm chất lƣợng của phân cụm STING hoàn toàn phụ

thuộc vào tính chất hộp ở mức thấp của cấu trúc lƣới. Nếu tính chất hộp là

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

mịn, dẫn đến chi phí thời gian xử lý tăng, tính toán trở nên phức tạp và nếu

mức dƣới cùng là quá thô thì nó có thể làm giảm bớt chất lƣợng và độ chính

xác của phân tích cụm.

Cấu trúc dữ liệu lƣới thuận tiện cho quá trình xử lí song song và cập

nhật liên tục, khi duyệt toàn bộ CSDL một lần để tính toán các đại lƣợng

thống kê cho mỗi ô, nên nó rất hiệu quả và do đó độ phức tạp thời gian để tạo

các cụm xấp xỉ O(n), trong đó n là tổng số các đối tƣợng. Sau khi xây dựng

cấu trúc phân cấp, thời gian xử lý cho các truy vấn là O(g), trong đó g là tổng

số ô lƣới ở mức thấp (g << n).

Xác định tầng để bắt đầu:

Với mỗi cái của tầng này, tính toán khoảng tin cậy (hoặc ƣớc lƣợng

khoảng) của xác suất mà ô này liên quan tới truy vấn.

Từ khoảng tin cậy của tính toán trên, gán nhãn cho là có liên quan

hoặc không liên quan.

Nếu lớp này là lớp dƣới cùng, chuyển sang Bƣớc 6; nếu khác thì

chuyển sang Bƣớc 5.

Duyệt xuống dƣới của cấu trúc cây phân cấp một mức. Chuyển sang

Bƣớc 2 cho các ô mà hình thành các ô lên quan của lớp có mức cao hơn.

Nếu đặc tả đƣợc câu truy vấn, chuyển sang Bƣớc 8; nếu không thì

chuyển sang Bƣớc 7.

Truy lục dữ liệu vào trong các ô liên quan và thực hiện xử lí. Trả lại

kết quả phù hợp yêu cầu của truy vấn. Chuyển sang Bƣớc 9.

Tìm thấy các miền có các ô liên quan. Trả lại miền mà phù hợp với

yêu cầu của truy vấn . Chuyển sang Bƣớc 9.

9. Dừng.

Thuật toán STING gồm các bƣớc sau:

Ngoài thuật toán STING ra, phân cụm dựa trên lƣới còn có thêm mộ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

thuật toán khác là: Thuật toán CLIQUE.

2.5.5. Các thuật toán phân cụm dựa trên mô hình

Thuật toán EM

Thuật toán EM đƣợc xem nhƣ là thuật toán dựa trên mô hình hoặc là

mở rộng của thuật toán k-means. Thật vậy, EM gán các đối tƣợng cho các

cụm đã cho theo xác suất phân phối thành phần của đối tƣợng đó. Phân phối

xác suất thƣờng đƣợc sử dụng là phân phối xác suất Gaussian với mục đích là

khám phá lặp các giá trị tốt cho các tham số của nó bằng hàm tiêu chuẩn là

hàm logarit khả năng của đối tƣợng dữ liệu, đây là hàm tốt để mô hình xác

suất cho các đối tƣợng dữ liệu. EM có thể khám phá ra nhiều hình dạng cụm

khác nhau, tuy nhiên do thời gian lặp của thuật toán khá nhiều nhằm xác định

các tham số tốt nên chi phí tính toán của thuật toán khá cao. Đã có một số cải

tiến đƣợc đề xuất cho EM dựa trên các tính chất của dữ liệu: có thể nén, có

thể sao lƣu trong bộ nhớ và có thể hủy bỏ. Trong các cải tiến này, các đối

tƣợng bị hủy bỏ khi biết chắc chắn đƣợc nhãn phân cụm của nó, chúng đƣợc

nén khi không bị loại bỏ và thuộc về một cụm quá lớn so với bộ nhớ và chúng

sẽ đƣợc lƣu lại trong các trƣờng hợp còn lại.

Thuật toán đƣợc chia thành hai bƣớc và quá trình đó đƣợc lặp lại cho

đến khi vấn đề đƣợc giải quyết:

Khởi tạo tham số:

Bước E:

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

Các bƣớc thực hiện của thhuật toán EM

Bước M:

Lặp lại bước 2 và 3 cho đến khi đạt được kết quả

Ngoài thuật toán EM ra, phân cụm dựa trên mô hình còn có thêm một

thuật toán khác là: Thuật toán COBWEB.

2.5.6. Các thuật toán phân cụm có dữ liệu ràng buộc

Thuật toán Phân cụm mờ: FCM, FCM và FCM-Cải tiến (Các thuật

toán này sẽ đƣợc đề cập chi tiết ở chƣơng kế tiếp).

Tóm lại, các kỹ thuật PCDL trình bày ở trên đã đƣợc sử dụng rộng rãi

trong thực tế, thế nhƣng hầu hết chúng chỉ nhằm áp dụng cho tập dữ liệu với

cùng một kiểu thuộc tính. Vì vậy, việc PCDL trên tập dữ liệu có kiểu hỗn hợp

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

là một vấn đề đặt ra trong KPDL ở giai đoạn hiện nay.

CHƢƠNG 3

KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ

3.1. Tổng quan về phân cụm mờ ................................................................................... 3.2. Các thuật toán trong phân cụm mờ ........................................................................ 3.2.1. Thuật toán FCM(Fuzzy C-means) ..................................................................... 3.2.1.1. Hàm mục tiêu .............................................................................................. 3.2.1.2. Thuật toán FCM .......................................................................................... 3.2.2. Thuật toán FCM(ε- Insensitive Fuzzy C-means) ............................................. 3.2.2.1. Hàm mục tiêu .............................................................................................. 3.2.2.2. Thuật toán FCM ........................................................................................ 3.2.3. Thuật toán FCM-Cải tiến ................................................................................... 3.2.3.1. Thuật toán 1: Thuật toán lựa chọn các điểm dữ liệu làm ứng viên cho

việc chọn các trung tâm của các cụm ......................................................... 3.2.3.2. Thuật toán 2: Thuật toán lƣợc bớt các ứng viên ........................................ 3.2.3.3. Thuật toán 3: Thuật toán chọn các ứng viên làm cực tiểu hàm mục tiêu .. 3.2.3.4. Thuật toán 4: Gán các trung tâm có liên kết “gần gũi” vào một cụm ....... 3.2.3.5. Tổng kết thuật toán FCM-Cải tiến ..............................................................

37 38 39 39 42 46 46 48 49 49 51 51 52 56

3.1. Tổng quan về phân cụm mờ

Trong cuộc sống, chúng ta đã gặp rất nhiều ứng dụng của bài toán phân

cụm. Chẳng hạn nhƣ trong ngành bƣu điện, hàng ngày bƣu điện phải phân

loại thƣ theo mã nƣớc, trong mã nƣớc lại phân loại theo mã tỉnh/thành phố,

sau đó khi thƣ về đến bƣu điện tỉnh thì bƣu điện tỉnh lại phải phân loại thƣ

theo quận/huyện để gửi đi, đến bƣu điện quận/huyện lại phân loại thƣ theo

xã/phƣờng để gửi thƣ. Đó chính là một ứng dụng của bài toán phân cụm rõ.

Vậy bài toán phân cụm rõ là gì?

Ta có thể định nghĩa bài toán phân cụm rõ nhƣ sau: Cho tập dữ liệu

mẫu X, ta kiểm tra các điểm dữ liệu xem nó giống với đặc điểm của nhóm

nào nhất thì ta gán điểm dữ liệu đó vào trong nhóm đó. Nhƣng trong thực tế

không phải lúc nào bài toán phân cụm rõ cũng áp dụng đƣợc. Chẳng hạn, ta

có phép phân loại sau: Những ngƣời đi xe máy xịn thì thuộc nhóm ngƣời

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

giàu, những ngƣời đi xe máy thƣờng thuộc nhóm ngƣời bình dân. Vậy ngƣời

nghèo mà đi xe máy xịn thì chúng ta xếp ngƣời đó vào nhóm nào? Vì vậy,

chúng ta cần đƣa vào khái niệm bài toán phân cụm mờ.

Trong các phƣơng pháp phân cụm đã giới thiệu trong chƣơng trƣớc,

mỗi phƣơng pháp phân cụm phân hoạch một tập dữ liệu ban đầu thành các

cụm dữ liệu có tính tự nhiên và mỗi đối tƣợng dữ liệu chỉ thuộc về một cụm

dữ liệu, phƣơng pháp này chỉ phù hợp với việc khám phá ra các cụm có mật

độ cao và rời nhau, với đƣờng biên giữa các cụm đƣợc xác định tốt. Tuy

nhiên, trong thực tế, đƣờng biên giữa các cụm có thể mờ, các cụm có thể

chồng lên nhau, nghĩa là một số các đối tƣợng dữ liệu thuộc về nhiều các cụm

khác nhau, do đó mô hình này không mô tả đƣợc dữ liệu thực. Vì vậy ngƣời

ta đã áp dụng lý thuyết về tập mờ trong PCDL để giải quyết cho trƣờng hợp

này. Cách thức kết hợp này đƣợc gọi là Phân cụm mờ.

Phân cụm mờ là phƣơng pháp phân cụm dữ liệu mà cho phép mỗi điểm

dữ liệu thuộc về hai hoặc nhiều cụm thông qua bậc thành viên. Ruspini (1969)

giới thiệu khái niệm phân hoạch mờ để mô tả cấu trúc cụm của tập dữ liệu và

đề xuất một thuật toán để tính toán tối ƣu phân hoạch mờ. Dunn (1973) mở

rộng phƣơng pháp phân cụm và đã phát triển thuật toán phân cụm mờ. Ý

tƣởng của thuật toán là xây đựng một phƣơng pháp phân cụm mờ dựa trên tối

thiểu hóa hàm mục tiêu. Bezdek (1981) cải tiến và tổng quát hóa hàm mục

tiêu mờ bằng cách đƣa ra trọng số mũ để xây dựng thuật toán phân cụm mờ

và đƣợc chứng minh độ hội tụ của các thuật toán là cực tiểu cục bộ.

3.2. Các thuật toán trong phân cụm mờ

K-means là thuật toán PCDL rõ và C-means là thuật toán phân cụm

mờ tƣơng ứng, hai thuật toán này cùng sử dụng chung một chiến lƣợc phân

cụm dữ liệu. Thuật toán C-means mờ hay còn gọi tắt là thuật toán FCM

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

(Fuzzy C-means) đã đƣợ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(nhận dạng vân tay, ảnh), xử

lý ảnh(phân tách các cụm ảnh màu, cụm màu), y học(phân loại bệnh, phân

loại triệu chứng), … Tuy nhiên, nhƣợc điểm lớn nhất của thuật toán FCM là

tập dữ liệu lớn, tập dữ liệu nhiều chiều, nhạy cảm với các nhiễu và phần tử

ngoại lai trong dữ liệu, nghĩa là các trung tâm cụm có thể nằm xa so với

trung tâm thực 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ử LP Norm (Kerten, 1999) và thuật toán ε- Insensitive Fuzzy C-means

(εFCM) và thuật toán FCM cải tiến.

3.2.1. Thuật toán FCM(Fuzzy C-means)

3.2.1.1. Hàm mục tiêu

Kỹ thuật này phân hoạch một tập n vectơ đối tƣợng dữ liệu X = {x1,…, xn}  Rs thành c các nhóm mờ dựa trên tính toán tối thiểu hóa hàm mục tiêu

để đo chất lƣợng của phân hoạch và tìm trung tâm cụm trong mỗi nhóm, sao

cho chi phí hàm đo độ phi tƣơng tự là nhỏ nhất. Một phân hoạch mờ vectơ điểm dữ liệu X = {x1,…, xn}  Rs là đặc trƣng đầu vào đƣợc biểu diễn bởi ma

trận U = [uik] sao cho điểm dữ liệu đã cho chỉ có thể thuộc về một số nhóm

với bậc đƣợc xác định bởi mức độ thuộc giữa [0, 1]. Nhƣ vậy, ma trận U đƣợc

sử dụng để mô tả cấu trúc cụm của X bằng cách giải thích uik nhƣ bậc thành

viên xk với cụm i.

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

Cho u = (u1, u2, .., uc1) là phân hoạch mờ C

Dunn định nghĩa hàm mục tiêu mờ nhƣ sau:

Bezdek khái quát hóa hàm mục tiêu mờ bằng cách đƣa ra trọng số mũ

m > 1 là bất kỳ số thực nào nhƣ sau:

(1)

trong đó:

X = [x1,…, xn]  Rs là n vectơ mẫu dữ liệu tập con thực s chiều trong

không gian vectơ Rs gồm có n quan sát,

m  [1, +] là trọng số mũ đƣợc gọi là tham số mờ,

vi  Rs là trung tâm cụm thứ i,

d(xk, vi) = dik là khuôn mẫu bất kỳ để đo khoảng cách giữa dữ liệu xk

với trung tâm cụm thứ i, => d2(xk, vi) là khoảng cách Euclidean,

uik  [0, 1] là bậc của phần tử dữ liệu xk thuộc về cụm thứ i, V = [vji] = [v1,…,vc]  Rsxc là ma trận biểu diễn các giá trị đối tƣợng

tâm của cụm,

U = [uik] là ma trận phân hoạch mờ ngẫu nhiên của X trong C phần.

Một trong các nhân tố chính ảnh hƣởng tới quyết định phân cụm hợp lí

các điểm là vấn đề chọn phép đo độ phi tƣơng tự. Thực vậy, tính toán bậc

thành viên uik phụ thuộc vào định nghĩa của phép đo khoảng cách dik mà là tích vô hƣớng trên Rs. Bình phƣơng khoảng cách giữa vectơ mẫu xk và trung

tâm vị trí của cụm thứ i đƣợc định nghĩa nhƣ sau:

trong đó:

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

A là ma trận hữu hạn dƣơng đối xứng (p  p) bất kỳ,

biểu diễn độ lệch của dữ liệu xk với vi, d(xk,vi) là tích vô

hƣớng trên Rs.

Bậc của thành viên thỏa mãn ràng buộc sau:

(2)

Để thuận tiện, coi mảng đối tƣợng dữ liệu {x1,....,xn} là các cột trong ma trận đối tƣợng dữ liệu X = [xjk] = [x1, …, xn]  Rsxc. Ma trận phân hoạch

U là một công cụ tiện lợi để mô tả cấu trúc cụm trong dữ liệu { x1, …, xn };

định nghĩa tập tất cả các ma trận thực phân hoạch mờ không suy thoái cấp cn cho phân hoạch n đối tƣợng thành c cụm dữ liệu trong không gian Rcxn đƣợc

viết gọn nhƣ sau:

(3)

Rcxn là không gian của tất cả các ma trận thực cấp cn.

Thông thƣờng ngƣời ta gọi bài toán phân cụm mờ là bài toán tìm các độ

thuộc uij nhằm tối thiểu hàm mục tiêu ở trên Jm(U,V) với các điều kiện sau:

Định lí 1: Nếu m và c là các tham số cố định, và ik là một tập được

định nghĩa như sau:

(4)

thì hàm mục tiêu Jm(U,V) đạt giá trị tối thiể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

khi và chỉ khi:

; (5)

(6)

ik > 0, 1 i  c) là

Định lí đã đƣợc Bezdek chứng minh (nếu m  1 , d2

đúng đắn.

Một phân hoạch tối ƣu, nghĩa là hàm mục tiêu đạt giá trị tối thiểu, mà

chủ yếu dựa trên đó độ tƣơng tự giữa xk và trung tâm cụm vi, điều này tƣơng

đƣơng với hai điều kiện (5) và (6) phải thỏa mãn. Với hàm mục tiêu và các

ràng buộc để hàm mục tiêu đạt giá trị tối thiểu trên đây.

3.2.1.2. Thuật toán FCM

Thuật toán FCM cung cấp một quá trình lặp qua lại giữa phƣơng trình

(5) và (6) để tối ƣu(xấp xỉ cực tiểu) hàm mục tiêu dựa trên đo đạc độ tƣơng tự

có trọng số giữa xk và trung tâm cụm vi, sau mỗi vòng lặp, thuật toán tính toán

và cập nhật các phần tử ujk trong ma trận phân hoạch U. Phép lặp sẽ dừng khi

, trong đó là chuẩn kết thúc giữa 0 và 1, trong khi k là

các bƣớc lặp. Thủ tục này hội tụ tới cực tiểu cục bộ hay điểm yên ngựa của

Jm(u, V). Thuật toán FCM tính toán ma trận phân hoạch U và kích thƣớc của

các cụm để thu đƣợc các mô hình mờ từ ma trận này. Các bƣớc thực hiện 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

thuật toán FCM nhƣ sau:

THUẬT TOÁN FCM

Input : Số cụm c và tham số mũ m cho hàm mục tiêu J;

Output: c cụm dữ liệu sao cho hàm mục tiêu trong (1) đạt giá trị cực tiểu;

Begin

1. Nhập tham số cụm c (1

Khởi tạo ma trận V=[vij], V(0) Rsxc, j=0;

2. Repeat

(j),..., vc

(j), v2

2.1. j:=j+1; 2.2. Tính ma trận phân hoạch mờ U(j) theo công thức (5); (j)] 2.3. Cập nhật các trung tâm cụm V(j)=[v1 dựa vào công thức (6) và U(j)

3. Until

;

4. Trình diễn các cụm kết quả;

End.

Trong đó, là tiêu chuẩn Frobenious đƣợc định nghĩa nhƣ sau:

và tham số đƣợc cho trƣớc .

Việc chọn các tham số cụm rất ảnh hƣởng đến kết quả phân cụm, tham

số này thƣờng đƣợc chọn theo phép ngẫu nhiên hoặc theo Heuristic.

Đối với m  1+ thì thuật toán C-means trở thành thuật toán rõ.

Đối với m   thì thuật toán FCM trở thành thuật toán phân cụm mờ

với: . Chƣa có quy tắc nào nhằm lựa chọn tham số m đảm bảo cho việc

phân cụm hiệu quả, nhƣng thông thƣờng chọn m = 2.

Để dễ hiểu có thể xét ví dụ sau: Cho một tập các đối tƣợng dữ liệu mộ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

chiều đƣợc biểu thị nhƣ Hình 3.1 sau:

Hình 3.1: Mô phỏng về tập dữ liệu đơn chiều

Bằng quan sát dễ nhận thấy có hai cụm trong tập dữ liệu trên đặt tên

tƣơng ứng là "A" và "B". Với thuật toán k-means thì hàm tính độ phụ thuộc

giữa đối tƣợng dữ liệu và trọng tâm cụm của nó đƣợc thể hiện nhƣ trong đồ

thị Hình 3.2 dƣới đây:

Hình 3.2: Hàm thuộc với trọng tâm của cụm A trong k-means

Dựa vào hình rút ra nhận xét rằng, các đối tƣợng trong cụm A có giá trị

hàm thuộc với trọng tâm của cụm A là bằng 1 và bằng 0 với trọng tâm cụm B.

Điều này ngƣợc lại với các đối tƣợng ở trong cụm B.

Thế nhƣng, đối với thuật toán FCM thì hàm thuộc của các đối tƣợng dữ

liệu với các trung tâm cụm dữ liệu đƣợc minh họa nhƣ trong đồ thị Hình 3.3

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

dƣới đây:

Hình 3.3: Hàm thuộc với trọng tâm của cụm A trong FCM

Dựa vào hình có thể nhận xét rằng, các đối tƣợng dữ liệu có giá trị hàm

thuộc với các trọng tâm của cụm A nằm trong khoảng [0, l], hàm thuộc lúc

này là một đƣờng cong trơn. Điểm có mũi tên chỉ đến có nhiều khả năng

thuộc về lớp B hơn là lớp A do giá trị hàm thuộc của nó vào lớp A là nhỏ

(=0.2). Có thể biểu diễn các giá trị hàm thuộc trên bằng ma trận cho cả hai

trƣờng hợp nhƣ sau:

Số dòng và số cột phụ thuộc vào số các đối tƣợng dữ liệu n và số các

cụm k.

Một số ví dụ mô phỏng về kết quả các cụm khám phá đƣợc của thuậ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

toán phân cụm mờ FCM nhƣ Hình 3.4 dƣới đây:

Hình 3.4: Các cụm khám phá đƣợc bởi thuật toán FCM

Độ phức tạp của thuật toán FCM tƣơng đƣơng với độ phức tạp của

thuật toán k-means trong trƣờng hợp số đối tƣợng của tập dữ liệu cần phân

cụm là rất lớn.

Tóm lại, thuật toán phân cụm mờ FCM là một mở rộng của thuật toán

k-means nhằm để khám phá ra các cụm chồng lên nhau, tuy nhiên, FCM vẫn

chứa đựng các nhƣợc điểm của thuật toán k-means trong việc xử lí đối với các

phần tử ngoại lai và nhiễu trong dữ liệu. Thuật toán FCM đƣợc trình bày

dƣới đây là một mở rộng của thuật toán FCM nhằm khắc phục các nhƣợc

điểm này.

3.2.2. Thuật toán FCM(ε- Insensitive Fuzzy C-means)

3.2.2.1. Hàm mục tiêu

Thuật toán phân cụm FCM sử dụng hàm bậc hai để do độ phi tƣơng tự

giữa dữ liệu và các trung tâm cụm. Suy luận sử dụng độ do này là tính toán

thấp và đơn giản. Tuy nhiên, cách tiếp cận này dễ bị ảnh hƣởng bởi nhiễu và

các phần tử ngoại lai. Để khắc phục nhƣợc điểm trên, một độ đo cải tiến đã

đƣợc đề xuất(Vapnik, 1998) sử dụng tham số  nhƣ sau :

,  là tham số phi nhạy cảm với nhiễu (7)

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

Hàm mục tiêu của thuật toán FCM đƣợc định nghĩa nhƣ sau:

(8)

trong đó: (9)

Ký hiệu:

 là hoặc .

 Lực lƣợng của tập A là card(A).

Định lý 2: Nếu m, c và  là các tham số cố định, với (U,V) (Efc* Rpc),

hàm mục tiêu Jm(U,V) đạt giá trị tối thiểu khi và chỉ khi:

(10)

và: (11)

trong đó:

với giả thiết và , 

tập Ik đƣợc định nghĩa là Ik = {i  1  i  c; xk - vi = 0; k=1, 2, …, N}

(12)

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

Định lí này đã đƣợc các nhà khoa học chứng minh.

3.2.2.2. Thuật toán FCM

Các bƣớc thực hiện của thuật toán FCM nhƣ sau:

THUẬT TOÁN FCM

Input: Số cụm c và các tham số m,  cho hàm mục tiêu J;

Output: Các cụm dữ liệu sao cho hàm mục tiêu trong (2) đạt

giá trị cực tiểu;

Begin

1. Nhập tham số c (1

Khởi tạo ma trận V=[vị], V(0)  Rsxc, thiết lập j = 0;

2. Repeat

(j)]

(j) ,…., vc

(j), v2

2.1. j:=j+1; 2.2. Tính ma trận phân hoạch mờ U(j) theo công thức (10); 2.3. cập nhật các trung tâm V(j) = [v1 dựa vào (12) và U(j) ;

3. Until (

);

4. Trình diễn các cụm kết quả;

End.

Tóm lại, thuật toán FCM là một mở rộng của thuật toán FCM trong

việc thích nghi với nhiễu và phần tử ngoại lai trong dữ liệu. Tuy vậy, hiệu quả

của thuật toán FCM đối với tập dữ liệu lớn, tập dữ liệu nhiều chiều cũng nhƣ

cách xác định tham số  là những vấn đề tiếp tục cần phải nghiên cứu và hoàn

thiện. Thuật toán FCM-Cải tiến đƣợc trình bày dƣới đây là một cải tiến nhằm

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

để khắc phục các nhƣợc điểm này.

3.2.3. Thuật toán FCM-Cải tiến

Do thuật toán FCM và FCM có một số hạn chế nhất định. Nên để giải

bài toán làm min hàm mục tiêu với số cụm không cố định và tránh

đƣợc trƣờng hợp chỉ đạt min địa phƣơng ta tiến hành xây dựng thuật toán

phân cụm mờ dựa trên việc cải tiến thuật toán FCM thông qua việc diễn giải

một số thuật toán nhỏ sau:

3.2.3.1. Thuật toán 1: Thuật toán lựa chọn các điểm dữ liệu làm ứng

viên cho việc chọn các trung tâm của các cụm

Cho tập dữ liệu , và

 Phân chia X thành m tập con (Nếu n bé thì không cần chia nữa):

Giả sử (b, d, m là các số nguyên dƣơng, ).

Khi đó, ta chia , với và tập

cuối cùng . (13)

 Vấn đề chọn lân cận :

Bƣớc này ảnh hƣởng khá lớn tới quá trình tính toán. Chúng ta có thể

dùng khái niệm phƣơng sai mẫu trong thống kê toán học để giải quyết cho

vấn đề chọn lân cận của một điểm dữ liệu.

Chẳng hạn, xét tập , , . Khi đó, kỳ vọng mẫu

, độ lệch tiêu chuẩn là . khi đó ta có , với

là độ lệch tiêu chuẩn của tập với k = 1, 2, …, p.

Ta xét lân cận của mỗi điểm dữ liệu là hình hộp p chiều với bán kính 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

thể định nghĩa theo độ lệch tiêu chuẩn là r.

Điểm nằm trong hình đƣợc gọi là nằm trong lân cận của xi nếu

hộp p chiều bán kính r của xi .

 Tính độ đậm đặc của các điểm dữ liệu.

Độ đậm đặc của , ký hiệu là , là số điểm dữ liệu nằm

trong lân cận của .

, với . (14)

Khi đó, thuật toán 1 đƣợc triển khai theo các bƣớc sau:

THUẬT TOÁN 1

Bƣớc 1: Tính

và độ lệch tiêu chuẩn

, i=1,2,..p.

Tính bán kính

Bƣớc 2: Tính độ đậm đặc của các điểm dữ liệu Di là số điểm dữ

liệu nằm trong hình hộp p chiều bán kính r của

Bƣớc 3: Tìm điểm

sao cho nó có độ đặc lớn nhất.

Bƣớc 4: Tính CC = {xj: xj nằm trong hình hộp p chiều bán kính r

. (* ở đây CC là tập tất cả các điểm dữ liệu nằm

của xi} và

trong hình hộp p chiều bán kính r của điểm dữ liệu xi *)

Bƣớc 5: Nếu

thì dừng. Ngƣợc lại, thì quay lên bƣớc 2.

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

Trong trƣờng hợp mẫu dữ liệu lớn thì chúng ta chia tập dữ liệu ra thành

các tập dữ liệu nhỏ hơn. Sau đó mới áp dụng thuật toán 1 cho từng mẫu dữ

liệu mới thu đƣợc sau khi đã phân chia.

Sau khi chạy xong thuật toán 1, thì ta sẽ có đƣợc một tập các điểm dữ

liệu làm ứng viên cho việc chọn các trung tâm của các cụm. Nếu tập này lớn

thì chúng ta lại áp dụng lại thuật toán 1 một lần nữa. Điều này đƣợc thể hiện

thông qua thuật toán 2.

3.2.3.2. Thuật toán 2: Thuật toán lƣợc bớt các ứng viên

Sau khi chạy xong thuật toán 1. Thì từ tập dữ liệu X ban đầu, chúng ta

đã chọn ra đƣợc nc các điểm dữ liệu làm ứng viên.

Giả sử = {xj: xj là điểm dữ liệu ứng viên, }. Khi nc mà lớn

thì ta sử dụng thuật toán 1 cho tập dữ liệu mới là Cx. Kết quả ta thu đƣợc tập

dữ liệu mới là . Sau khi đã chạy xong thuật toán 2, ta có

đƣợc tập dữ liệu mới. Khi đó, ta chuyển sang thuật toán 3 để tìm các điểm dữ

liệu làm trung tâm của các cụm, đây là những điểm dữ liệu mà làm min hàm

mục tiêu.

3.2.3.3. Thuật toán 3: Thuật toán chọn các ứng viên làm cực tiểu HMT

Sau khi kết thúc thuật toán 1 và thuật toán 2 thì ta thu đƣợc tập các

điểm dữ liệu làm ứng viên cho trung tâm các cụm là .

Trong thuật toán FCM, ta dùng hàm mục tiêu

(15)

Ta thay thế hàm mục tiêu này bằng hàm mục tiêu mới đƣợc xá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

định nhƣ sau: (16)

với (17)

và (18)

Thông thƣờng ta hay chọn m = 2. Do các cụm có thể rất gần nhau nên

để có thể phân biệt đƣợc các cụm này ta dùng JCC có thêm trọng số

trong trƣờng hợp chúng khá gần nhau.

Khi đó, thuật toán 3 đƣợc triển khai theo các bƣớc sau:

THUẬT TOÁN 3

Bƣớc 1: q = 1, gán

Bƣớc 2: gán

Bƣớc 3: Tính độ thuộc

i=1, 2, .., n và j = 1, 2, .., q.

Tính

theo công thức (17)

Bƣớc 4: Nếu

thì gán

và q:=q+1;

Bƣớc 5: Nếu

thì dừng với q:=q-1. Ngƣợc lại thì quay

lên bƣớc 2 với

3.2.3.4. Thuật toán 4:Gán các trung tâm có liên kết “gần gũi” vào 1 cụm

Sau khi kết thúc thuật toán 3, ta có một số hữu hạn các điểm dữ liệ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

đƣợc chọn làm trung tâm của các cụm. Đó là: .

Bây giờ ta kiểm tra xem các cụm có thể kết nối lại đƣợc với nhau hay

không. Điều này đƣợc thực hiện nhờ thuật toán 4. Thuật toán này đƣợc triển

(đường dây này phụ thuộc

khai nhƣ sau:

vào trường hợp cụ thể để ta chọn, chẳng hạn nếu là lông mày, ta sẽ tìm một đường

cong parabol, con mắt ta có thể dùng hình elip…)

Việc 1: Tìm đƣờng dây có thể nối và

Giả sử có những điểm nằm trên đƣờng dây nối và là:

sao cho:

Sau đó, ta tiến hành tính độ đậm đặc của các điểm này:

(19)

(20)

(21)

Nếu các điểm dữ liệu này thỏa mãn với mọi l = 1, 2, …, k đối với tất cả

thì ta xác định hai cụm này có thể kết nối đƣợc.

Việc 2: Ta nối 2 trung tâm và dùng luật bắc cầu để nối tiếp chúng

và

vào một cụm.

là kết nối đƣợc) và (

là kết nối đƣợc)

Chẳng hạn, nếu (

thì , và là kết nối đƣợc và các trung tâm này đƣợc gán vào cùng

một cụm.

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

Khi đó, thuật toán 4 đƣợc thể hiện chi tiết qua các bƣớc sau:

THUẬT TOÁN 4

Việc thứ nhất:

Bƣớc 1: gán

Bƣớc 2: Ta tạo ra index1 và index2 đều là mảng một chiều cỡ h.

Khởi tạo tất cả các phần tử của mảng này với giá trị 0.

Bƣớc 3: Đặt i:=1; j:=i+1;

Bƣớc 4: Tìm các điểm nằm trên đƣờng dây nối

và

(thường đường dây này dựa vào đặc điểm của đường cong cần nhận dạng,

chẳng hạn lông mày thì ta dùng một đường cong parabol) là

sao cho:

Bƣớc 5: Tính độ đậm đặc của các điểm dữ liệu ở bƣớc 4:

Bƣớc 6:

)THEN

(

If (index1[i]=0) and (index2[j]=0) then

Begin

;

Index1[i]:=j;

Index2[j]:=i;

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

End

Else if (

then

Begin

;

End

Else if ((

then

Begin

;

End

Else if (

then

Begin

temp:=

;

End

Else (* của IF đầu tiên *)

begin

và

End;

Bƣớc 7: IF

THEN j:=j+1 và quay trở lại bƣớc 4

ELSE if

then quay trở lại bƣớc 4

ELSE i:=i+1,j:=j+1 và quay trở lại bƣớc 4

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

Việc thứ hai:

Bƣớc 1: i:=1;FC:= ;

Bƣớc 2: IF

then

Begin

h:=h-1; xóa

;

FC:=FC ;

End;

Bƣớc 3: i:=i+1;

Bƣớc 4: IF i

THEN quay lại bƣớc 2

ELSE dừng lại .

3.2.3.5. Tổng kết thuật toán FCM-Cải tiến

Từ chi tiết của 4 thuật toán nhỏ trên, ta có thể tổng hợp thuật toán

FCM-Cải tiến một cách tổng quát thông qua các bƣớc cụ thể nhƣ sau:

THUẬT TOÁN FCM-CẢI TIẾN

Cho tập dữ liệu

và

Thuật toán FCM-Cải tiến đƣợc thực hiện thông qua các bƣớc sau:

Bƣớc 1: Nếu n là lớn thì chạy thuật toán 1 để có đƣợc tất cả các

điểm có khả năng làm trung tâm cụm, ngƣợc lại thì chạy bƣớc 3.

Bƣớc 2: Nếu sau khi chạy thuật toán 1 mà số điểm làm ứng viên

lớn thì ta chạy thuật toán 2 để rút gọn bớt số các điểm ứng viên làm các

trung tâm của các cụm.

Bƣớc 3: Chạy thuật toán 3 để tìm các điểm làm trung tâm cụm.

Bƣớc 4: Chạy thuật toán 4 để nối các trung tâm cụm có liên hệ

“gần gũi” vào một cụm.

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

Sau khi bƣớc 4 kết thúc, ta sẽ có tập các trung tâm của các cụm.

Bƣớc 5: (có thể nhảy tới bƣớc 6)

Chạy thuật toán FCM với tập các trung tâm của các cụm, sau đó

dừng lại.

Bƣớc 6: Tính các độ thuộc của các điểm dữ liệu còn lại:

Gọi

là độ thuộc của xi vào

Ta có:

Tóm lại, phân cụm mờ là một sự mở rộng của PCDL bằng cách thêm

vào yếu tố quan hệ giữa các phần tử và các cụm dữ liệu thông qua các trọng

số trong ma trận U. Bằng cách này, có thể khám phá ra các cụm dữ liệu phức

tạp theo cách mềm dẻo từ một tập dữ liệu đã cho. Thuật toán phân cụm mờ là

một cách thức mở rộng cho các thuật toán phân cụm rõ nhằm khám phá ra các

cụm dữ liệu chồng lên nhau trên các tập dữ liệu có kích thƣớc lớn, nhiề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

chiều và nhiều nhiễu...

CHƢƠNG 4

MÔ HÌNH MẠNG NƠRON ĐA KHỚP

DÙNG CHO PHÂN CỤM MỜ

4.5.

4.1. Tổng quan về mạng Nơron .................................................................................... 4.2. Cấu trúc mạng Nơron ............................................................................................. 4.2.1. Hàm kích hoạt ................................................................................................. 4.2.2. Liên kết mạng .................................................................................................. 4.2.3. Bài toán huấn luyện mạng ............................................................................... 4.3. Mạng HOPFIELD .................................................................................................. 4.3.1. Huấn luyện mạng ............................................................................................ 4.3.2. Sử dụng mạng .................................................................................................. 4.4. Mạng Nơron đa khớp dùng cho phân cụm ............................................................. 4.4.1. Xây dựng lớp mạng Layer1 cho tối ƣu các trung tâm cụm ............................. 4.4.2. Xây dựng lớp mạng Layer2 cho tối ƣu các độ thuộc ...................................... Sự hội tụ của FBACN ............................................................................................ 4.5.1. Chứng minh sự hội tụ của FBACN ................................................................. 4.5.2. Sự hội tụ FBACN liên tục của Layer1 ............................................................ 4.5.3. Giải thuật của FBACN và FBACN với việc học ............................................

58 61 61 61 61 62 62 63 63 65 68 72 72 74 75

Thuật toán FCM-Cải tiến đã khắc phục đƣợc một số hạn chế của thuật

toán FCM và εFCM. Tuy nhiên nó lại có nhƣợc điểm là mỗi khi có yêu cầu

phân cụm thì thuật toán sẽ chạy từ đầu, các kết quả của các mẫu trƣớc là

không sử dụng đƣợc cho lần sau nên thời gian chạy khá lớn nếu nhƣ kích

thƣớc mẫu lớn. Vì vậy, trong chƣơng này, chúng ta nghiên cứu một mô hình

mạng Nơron đa khớp dùng cho bài toán phân cụm mờ (a fuzzy bi-directional

associative clustering network –FBACN). Mạng Nơron này chủ yếu dựa vào

tài liệu của hai tác giả Chih-Hsiu Wei, Chin - Shyurng Fahn.

4.1. Tổng quan về mạng Nơron

Trƣớc hết chúng ta ai cũng biết rằng tri thức của loài ngƣời cho đến nay

hết sức phong phú, sâu rộng và đa dạng. Nó bao gồm những hiểu biết 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

chúng ta từ thế giới vi mô nhƣ nguyên tử, điện tử, hạt nhân, các hạt cơ bản, ...

đến những hiểu biết vĩ mô về trái đất, về hệ mặt trời, hệ thiên hà, ... . hiểu biết

về thế giới tự nhiên và xã hội, về các nghành khoa học, kỹ thuật khác nhau

nhƣ: toán, lý, hóa, công nghệ thông tin và cả những hiểu biết về bản thân con

ngƣời. Thế nhƣng có một điều mà có vẻ nhƣ là một nghịch lý đó là chúng ta

biết "rất ít" về chính bộ não của chúng ta.

Hơn nữa do nhu cầu ngày càng cao trong việc giải quyết các vấn đề phức tạp

và do bản chất của con ngƣời là không muốn bằng lòng với hiện tại mà luôn

muốn vƣơn tới những gì cao hơn, hoàn thiện hơn. Có lẽ chính vì những điều

trên mà thuật ngữ "mạng Nơron" hoặc "mạng Nơron nhân tạo" đã ra đời. Các

thuật ngữ đó nói đến một nghành kỹ thuật mới mà nó đòi hỏi kiến thức từ

nhiều nghành khoa học khác nhau nhƣ toán học, vật lý học, hóa học, sinh vật

học, tâm lý học, thần kinh học, ... và tất cả chỉ nhằm làm sao tạo ra những

chiếc máy tính hoạt động giống nhƣ " bộ não " của chính chúng ta.

Mạng Nơron nhân tạo hay thƣờng đƣợc gọi ngắn gọn là mạng Nơron là

một mô hình toán học hay mô hình tính toán đƣợc xây dựng dựa trên các

mạng Nơron sinh học. Nó gồm có một nhóm các Nơron nhân tạo(nút) nối với

nhau, và xử lý thông tin bằng cách truyền theo các kết nối và tính giá trị mới

tại các nút. Trong nhiều trƣờng hợp, mạng Nơron nhân tạo là một hệ thống

thích ứng, tự thay đổi cấu trúc của mình dựa trên các thông tin bên ngoài hay

bên trong chảy qua mạng trong quá trình học.

Trong thực tế sử dụng, nhiều mạng Nơron là các công cụ mô hình hóa

dữ liệu thống kê phi tuyến. Chúng có thể đƣợc dùng để mô hình hóa các mối

quan hệ phức tạp giữa dữ liệu vào và kết quả hoặc để tìm kiếm các dạng mẫ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

trong dữ liệu.

Hình 4.1: Mô hình mạng Nơron

Mạng Nơron nhân tạo (Artificial Neural Network) là một mô hình toán

học bao gồm các nút xử lý thông tin cơ sở (gọi là đơn vị xử lý hoặc Nơron) có

mối liên hệ tƣơng hỗ cao, tiến hành xử lý thông tin song song và phân tán có

năng lực tính toán mạnh (ví dụ hiện nay nó có thể học, nhớ và suy diễn từ mẫu

dữ liệu...). Mỗi liên kết giữa hai Nơron kèm theo một trọng số nào đó, đặc

trƣng cho đặc tính kích hoạt/ức chế giữa các Nơron. Có thể xem trọng số là

phƣơng tiện để lƣu giữ thông tin dài hạn trong mạng Nơron và nhiệm vụ của

quá trình huấn luyện (hay còn gọi là quá trình học) mạng là cập nhật các trọng

số khi có thêm thông tin về các mẫu học, hay nói cách khác, các trọng số

đƣợc điều chỉnh sao cho dáng điệu vào ra của nó mô phỏng hoàn toàn phù

hợp với môi trƣờng đang xem xét. Vì vậy, cấu trúc của mạng Nơron chủ yếu

đƣợc đặc trƣng bởi loại của các Nơron và mối liên hệ xử lý thông tin giữa

chúng và do đó, mạng Nơron có rất nhiều ứng dụng trong nhiều lĩnh vực nhƣ

nhận dạng, phân lớp ảnh, phân tích - nén dữ liệu, các bài toán tối ƣu, dự bá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

chuẩn đoán,… Và xu thế hiện đại đó là sự kết hợp mạng Nơron với logic mờ.

4.2. Cấu trúc mạng Nơron

4.2.1. Hàm kích hoạt

Hàm kích hoạt của từng Nơron trong mạng Nơron đóng vai trò quan

trọng trong sự liên kết giữa các Nơron. Hàm này đặc trƣng cho mức độ liên

kết giữa các Nơron.

Trong lý thuyết mạng Nơron, phép tổng hợp các tín hiệu đầu vào

thƣờng đƣợc kí hiệu dƣới dạng: với là các tín hiệu

vào. là trọng số, n là số tín hiệu đầu vào. Đầu ra của Nơron j

thƣờng đƣợc kí hiệu là outj hoặc fj, đƣợc gọi là hàm kích hoạt.

, với là ngƣỡng kích hoạt Nơron, t là thời gian, f

là hàm kích hoạt.

4.2.2. Liên kết mạng

Sự liên kết trong mạng Nơron tuỳ thuộc vào nguyên lý tƣơng tác giữa

đầu ra của từng Nơron riêng biệt với các Nơron khác và tạo ra cấu trúc mạng

Nơron. Về nguyên tắc sẽ có rất nhiều kiểu liên kết giữa các Nơron nhƣng

trong thực tế ta thƣờng gặp các dạng nhƣ: Mạng truyền thẳng và mạng hồi

quy....

4.2.3. Bài toán huấn luyện mạng

Bài toán huấn luyện mạng là quá trình giải bài toán tối ƣu hóa tham số

của mạng, chủ yếu là các trọng số liên kết mạng và cấu trúc các dạng liên kết

của các Nơron, giữa các lớp dựa trên thông tin có trong hệ thống.

Thƣờng thì quá trình huấn luyện mạng nơtron(hay còn gọi là thuật học)

đƣợc thực hiện qua phép so sánh đầu ra của mạng với tín hiệu chỉ đạ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

Mô hình học có giám sát đƣợc mô phỏng nhƣ Hình 4.2 dƣới đây:

Hình 4.2: Mô hình học có giám sát

Sai số e = y-d là cơ sở để huấn luyện mạng.

Tiếp theo chúng ta tìm hiểu một mô hình mạng Nơron đƣợc áp dụng rất

nhiều là mạng Hopfield.

4.3. Mạng HOPFIELD

Năm 1982 nhà vật lý ngƣời Mỹ J.J Hopfield đã đề xuất ra mô hình

mạng Nơron (Neural Network - NN) cho phép tạo ánh xạ dữ liệu từ tín hiệu

vào sang tín hiệu ra theo kiểu tự kết hợp, tức là nếu tín hiệu vào là X thuộc

miền giá trị D nào đó thì kết quả Y cũng phải thuộc miền D đó. Nhờ vậy, mà

một véctơ tín hiệu vào X bị thiếu thông tin hoặc bị biến dạng có thể đƣợc

phục hồi về dạng nguyên bản của mình.

Trong ứng dụng, mạng Hopfield đã mô phỏng đƣợc khả năng tự kết

hợp của bộ não con ngƣời. Ngoài ra, với một số cải biên mạng Hopfield còn

đƣợc dùng để giải quyết các bài toán tối ƣu, bài toán xử lý dữ liệu trong điều

khiển tự động...

4.3.1. Huấn luyện mạng

Mạng Hopfield học dựa trên nguyên tắc học có giám sát. Giả sử có p

mẫu học tƣơng ứng với các véctơ tín hiệu vào Xs, với s = 1, 2, .., p. Mạng

Hopfield sẽ xác định ma trận trọng số W sao cho:

Xs = Tinh(Xs,W) với mọi s =1, 2, ..p.

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

Với ma trận trọng số W đƣợc xác định nhƣ sau:

với Xs=(xs1,..,xsm)

4.3.2. Sử dụng mạng

Giả sử ta đƣa vào mạng tín hiệu vào là véctơ X.

Sử dụng mạng để tính đầu ra tƣơng ứng với tín hiệu vào X là quá trình

lặp gồm các bƣớc:

1. Ban đầu, đặt X(0)=X. Gọi Y(1) là véctơ tín hiệu ra tƣơng ứng với một

lần cho X(0) lan truyền trong mạng.

Y(1)= out(1)= Tính (HF, X(0)).

2. Nếu thì tiếp tục lặp với bƣớc t = t+1 và X(t+1)=Y(1). Ngƣợc

lại thì dừng.

Tiếp theo chúng ta nghiên cứu một mô hình mạng Nơron dùng cho

phân cụm mờ, đó là mạng Nơron đa khớp.

4.4. Mạng Nơron đa khớp dùng cho phân cụm

hồi quy) đƣợc sử dụng nhiều trong các quá trình xử lý thông tin.

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

Một vài năm trƣớc, các hệ thống Nơron động(đôi khi gọi là mạng Nơron

Hình 4.3: Mô hình FBACN

Cấu trúc của mạng Nơron đa khớp-FBACN đƣợc đƣa ra nhƣ hình 4.3.

Lớp hồi quy Layer1 đƣợc thực hiện bởi một mạng Hopfield để tối ƣu hoá các

trung tâm cụm. Trong khi đó lớp hồi quy Layer2 đƣợc thực hiện bởi một

mạng Nơron đa khớp nối để tối ƣu các độ thuộc. Kết hợp Layer1 và Layer2

tạo thành lớp hồi quy 3, lớp này làm nên cấu trúc động của mạng.

Hoạt động của FBACN đƣợc mô tả nhƣ sau: Thứ 1 là khởi tạo ngẫu

nhiên các trung tâm cụm và độ thuộc thành viên của Layer1 và Layer2 tƣơng

ứng. Thứ 2, khởi tạo các độ thuộc thành viên trong Layer2 sẽ đƣợc truyền

sang Layer1. Thứ 3, dựa trên việc nhận đƣợc các độ thuộc thành viên, Layer1

thực hiện quá trình hồi quy để thu đƣợc các trung tâm cụm tối ƣu mới. Thứ 4,

các trung tâm cụm mới của Layer1 truyền sang Layer2. Thứ 5, dựa trên việc

nhận đƣợc các trung tâm cụm mới, thực hiện quá trình hồi quy để thu đƣợc độ

thuộc thành viên tối ƣu mới. Việc hoàn tất quá trình trên từ bƣớc 2 đến bƣớc 5

đƣợc gọi là quá trình lặp. Quá trình lặp diễn ra cho tới khi nào đạt tới một tiê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

chuẩn tới hạn.

4.4.1. Xây dựng lớp mạng Layer1 cho tối ƣu các trung tâm cụm

Lớp Layer1 của FBACN có thể sử dụng mạng Hopfield hoặc mạng

Nơron đa khớp tuỳ thuộc vào các ràng buộc của FC-partition (FC- fuzzy c).

Nếu ràng buộc làm cho hàm mục tiêu có dạng bậc cao, hoặc dạng logarithm,

hoặc dạng sin, v.v.. thì ta sử dụng mạng Nơron đa khớp thay vì dùng mạng

Hopfield đơn giản.

Hình 4.4: Mô hình Lớp Layer1 của FBACN

Gọi là trọng số kết nối hoạt động của Nơron j với Nơron vào i. Tất cả

các đầu vào đến Nơron thứ j đƣợc kí hiệu là ij. Khi đó, tổng hợp các tín hiệu

đầu vào đối với Nơron j là: (1). Với vi là đầu ra của Nơron

i, f là hàm đơn điệu tăng và liên tục.

Ta có hàm kích hoạt (2). ở đây, ngƣỡng

r > 0 làm tăng tính thích nghi và khả năng tính toán của mạng Nơron.

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

Giả sử g là chỉ số đệ quy và khi đó

(3)

Khi đó, ta có thể diễn tả mạng Nơron thông qua ma trận NET sau:

NET = WV + I (4)

với

, , và

Để đánh giá tính ổn định của hệ thống trong hình 4.4, chúng ta dùng

hàm tính toán năng lƣợng CEF(computational energy function-CEF).

Ta có CEF(E) là: (5)

Hay cụ thể hơn là: (6)

Trong công thức (6) thì E là dạng toàn phƣơng. Vì vậy, trong mạng Nơron

động này ta có thể dùng hàm mục tiêu dạng toàn phƣơng để tối ƣu hóa các

tham số.

Tiếp theo, ta sẽ lý giải sự phù hợp giữa hàm mục tiêu của FC-partion và

hàm tính toán năng lƣợng của FBACN.

Ta có hàm mục tiêu của FC-partion là:

(7)

Trong Layer1 của FBACN, các tham số tối ƣu là các trung tâm cụm vi.

Các độ thuộc mới ui,k đƣợc thực hiện từ lớp 2 tới Layer1 sẽ kích hoạt hồi quy

trong Layer1 để tối ƣu vi. Ngoài ra, ui,k tạm thời coi là các hằng số trong khi

hồi quy trong Layer1. Từ định nghĩa của hàm mục tiêu, các véctơ trung tâm

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

của các cụm là véctơ p chiều. Vì vậy, ta phải khai triển

(7) để khử biểu thức véctơ trƣớc khi nó đƣợc đem so sánh với hàm tính toán

năng lƣợng thăng giá trị. Thăng giá trị đƣợc khai triển trong công thức (7) với

lần khử đầu tiên là:

(8)

Quan sát (6) và (8) ta thấy sự khác nhau chính giữa hai công thức này

là cách ký hiệu khác nhau. Trong mạng Nơron, thì các hoạt động ra của các

Nơron đƣợc ký hiệu một cách duy nhất bằng một ký hiệu dƣới dòng. Chẳng

. Tuy nhiên, sau khi khai triển hàm mục tiêu hạn, hoạt động ra vi với

. của FC-pariton, có 2 từ viết dƣới dòng trong tham số vi,l, với

Để thống nhất trong cách thể hiện, ta ký hiệu lại nhƣ sau:

(9)

Khi đó, ta viết lại biểu thức (8) nhƣ sau:

(10)

Số Nơron s trong Layer1 ở (6) là .

Ta có ,với , (11)

và các phần tử của ma trận W đƣợc xác định bởi:

, (12)

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

với ký hiệu | x | là cách lấy số nguyên cao hơn và gần nhất so với x.

Quá trính tối ƣu của Layer1:

Mục tiêu của mạng hồi quy là làm cho hàm mục tiêu xấp xỉ tới giá trị nhỏ nhất. Do W là ma trận đối xứng nên WT=W, ta lấy gradient của véctơ

năng lƣợng trong (5) ta đƣợc:

(13)

và (14)

Tiếp theo, chúng ta xây dựng hàm kích hoạt (liên tục hoặc rời rạc) f

đƣợc sử dụng ở trong Layer1 của FBACN theo công thức sau:

(15)

với thì là giá trị dƣơng nhỏ nhất để điều chỉnh vj. Ta thấy khi

>0, .

Trong kiểu kiến trúc này, thì sự cập nhật hệ số với giá trị không hạn

chế. Theo phƣơng pháp mà ta đã thiết kế thì cách lựa chọn giá trị của nó là

phù hợp với tiến triển của Layer1.

4.4.2. Xây dựng lớp mạng Layer2 cho tối ƣu các độ thuộc

Lớp mạng Layer2 của FBACN có chức năng là tối ƣu hóa lớp các độ

thuộc. Ta có thể coi các vi là các hằng số tạm thời trong khi lớp Layer2 hồi

quy. Ta có tập . Khi đó, công thức:

đƣợc viết lại là .

Khi đó, bài toán tối ƣu trong lớp Layer2 của FBACN là: làm min

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

với ràng buộc .

Theo công thức Lagrange thì ta có thể phát biểu lại bài toán nhƣ sau:

(16)

với là tham số Lagrange (thƣờng ).

Ta ký hiệu lại và (17)

Khi đó, ta có thể biểu diễn lại hàm mục tiêu là:

(18)

Trong công thức (18) thì số hạng có bậc cao nhất là (thông thường

ta chọn m=2) với k=1, 2, ..,n và i = 1, 2, ..., c. Nhƣng mạng Hopfield chỉ phù

hợp với bài toán tối ƣu bậc hai. Vì vậy, ta phát triển mạng Nơron đa khớp cho

các bài toán tối ƣu chung. Tức mạng Nơron đa khớp có thể giải quyết đƣợc

với bất kỳ hàm mục tiêu bậc cao có ràng buộc nào.

Mô hình mạng Nơron đa khớp đơn giản đƣợc sử dụng cho Layer2 nhƣ sau:

Hình 4.5: Mô hình Lớp Layer2 của FBACN

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

Tính động của mạng Nơron đa khớp trong hình 4.5 là:

, với j=1, 2, ..., s. (19)

Ta có ma trận đầu vào mạng: (20)

Với và

, m > 1 và U(1) = U (21)

. Khi đó, hàm tính toán năng Ta ký hiệu chuyển vị của U(m-1) là:

lƣợng của mạng Nơron sẽ đƣợc tính bởi công thức:

(22)

Với số lƣợng Nơron s trong lớp Layer2 là . Ta có thể tính toán các phần

tử của ma trận W, Z và I nhƣ sau: tức là các phần tử

của W đƣợc tính theo công thức sau:

, (23)

Z là ma trận cỡ và đƣợc xác định nhƣ sau:

với i,j = 1, 2, ..., . (24)

otherwise

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

Và ma trận I là ma trận một chiều cỡ và đƣợc xác định nhƣ sau:

B.W.A), vì vậy hàm tính toán năng lƣợng ở (22) đƣợc biểu diễn là:

Do ma trận trọng số W là đối xứng (W được gọi là đối xứng nếu A. W.B =

(25)

U có thể điều chỉnh hai ma trận trọng số W và Z. Khi đó, ma trận

NET của mạng Nơron đa khớp đƣợc xác định nhƣ sau:

Gọi h là hàm số xác định bởi: (26). Khi đó, h đƣợc gọi là hàm để

tính Và tính động của lớp Layer2 đƣợc thể hiện ở công thức:

(27)

Với là tổng đầu vào của Nơron thứ j và đƣợc tính bởi công thức:

(28)

Theo công thức (25), ta có gradient năng lƣợng :

với s = (29)

Từ (28) và (29) ta có (30)

Quá trình tối ƣu của Layer2

Khi hàm mục tiêu (18) đƣợc cân bằng với hàm tính toán năng lƣợng

(25) và gradient tính toán năng lƣợng đƣợc liên kết với giá trị net vào, kế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

quả tối ƣu dần đạt đƣợc khi mạng tiến triển. Từ khái niệm năng lƣợng, hàm

rời rạc f là hàm kích hoạt của mạng Nơron đa khớp đƣợc xây dựng giống

nhƣ của lớp thứ nhất:

Vectơ năng lƣợng gradient đƣợc tính toán liên quan đến uj:

Hàm kích hoạt rời rạc đƣợc đƣa ra :

(31)

Với vectơ năng lƣợng gradient luôn âm và công thức (31), đảm bảo

mạng Layer2 sẽ tối ƣu trong quá trình tiến hoá.

4.5. Sự hội tụ của FBACN

4.5.1. Chứng minh sự hội tụ của FBACN

Một yếu tố quan trọng cho mạng hồi quy đó là khả năng ổn định của

mạng. Trƣớc khi đƣa ra tính ổn định của mạng FBACN, chúng ta sẽ bắt đầu

với một vài định nghĩa về không gian Metric và định lý đƣa ra bởi Steck và

sau đó là một định lý hội tụ phổ quát.

Định nghĩa 1: Trong không gian Metric cho tập X và hàm d:

thỏa mãn các điều kiện:

Định nghĩa 2: Cho X là không gian Metric với khoảng cách d và

. Điểm x đƣợc gọi là điểm cố định của nếu .

Định nghĩa 3: Ánh xạ là co nếu tồn tại c*, với sao cho:

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

, (32)

Nếu thỏa mãn (32) thì chỉ có 1 điểm cố định. Thật vậy, giả sử có 2

điểm cố định x và y. Khi đó theo (32) ta có: . Vì vậy,

d(x,y)=0, nên x = y.

Vậy ta có thể khái quát điều trên thông qua định lý sau:

Định lý về ánh xạ co(ánh xạ thu gọn-AXC): Ánh xạ co của không gian

Metric đầy đủ có duy nhất một điểm cố định.

Định lý 1: Cho mạng Nơron nhân tạo hồi quy kết nối đầy đủ gồm các

Nơron s với kích hoạt động (33), với f là một

hàm có giới hạn, liên tục và có giá trị thực, hàm có đạo hàm có giới hạn và

nếu thỏa mãn: , (34) thì mạng hội tụ đến một

điểm cố định duy nhất đối với bất kỳ một giá trị khởi tạo nào của mạng.

Bổ đề: với mỗi hàm f thỏa mãn điều kiện giả thuyết, thì với bất kỳ

ta có (35)

Dựa vào các định nghĩa, định lý và bổ đề ở trên, một định lý hội tụ phổ

biến cho mạng Nơron đa khớp nối đƣợc đƣa ra nhƣ sau:

Định lý 2(đối với mạng Nơron đa khớp nối): Ứng với mỗi mạng Nơron đa

khớp nối gồm s Nơron có hai trọng số và với tính động kích hoạt sau:

(36)

ở đây f là hàm có giới hạn, liên tục và có giá trị thực. Nếu f thỏa mãn điều

kiện: , (với i, j = 1, 2, ..., s) (37) thì mạng hội tụ

đến một giá trị cố định duy nhất đối với với mọi giá trị khởi đầu của mạng.

Chứng minh: Theo định lý về ánh xạ co, để chứng minh FBACN là hội

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

tụ đến một điểm duy nhất thì chúng ta phải chỉ ra tồn tại một hằng số

c* sao cho với mọi giá trị và

thì

(38)

Ta định nghĩa hàm số:

(39)

Với không gian là đầy đủ với Metric đã lựa chọn, thì ta có:

, (40)

Ta có : =

(41)

= (42)

với . Theo (37) thì (43)

Theo (42) và (43) thì ánh xạ là ánh xạ co. Do đó, theo điều kiện của

(37) thì mạng Nơron đang xét là hội tụ về một điểm duy nhất.

4.5.2. Sự hội tụ FBACN liên tục của Layer1

Hàm kích hoạt của Layer1 đƣợc xây dựng nhƣ sau:

(44)

Với và là các số thực dƣơng. Ta cần tìm giá trị max của đạo hàm

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

cấp 1 của (44). Ta biết rằng đạo hàm cấp 1 của hàm f là cực đại tại x nếu đạo

hàm cấp 2 của hàm f tại x là bằng 0. Giả sử thì ta có netj=0. Vì

vậy, giá trị max của là đạt cực đại địa phƣơng tại netj = 0 và giá trị đó là

(45)

Mặt khác nên ta có (46)

Ta có (47) với s là số lƣợng Nơron có trong mạng

và trong lớp Layer1. Vì thế ta chọn , và vì vậy ta có thể

tìm đƣợc một hằng số sao cho (48) Điều

này thỏa mãn điều kiện của định lý 1 nên ta có mạng là hội tụ đến một điểm.

Kết luận: Quá trình tính toán và chứng minh, ta có đƣợc kết quả sau:

 Với Layer1, mạng thoả mãn giả thuyết của định lý 1, nên mạng hội tụ

 Với Layer2, mạng thoả mãn giả thuyết của định lý 2, nên mạng hội tụ

4.6. Giải thuật của FBACN và FBACN với việc học

Giải thuật của FBACN đƣợc thực hiện qua các bƣớc sau:

GIẢI THUẬT CỦA FBACN

1) Thiết lập các giá trị c, m, λ, ε và các hệ số iδv, iδu trong lớp Layer1

và Layer2 tƣơng ứng.

2) Đặt hệ số ổn định

và

cho Layer1 và Layer2 tƣơng ứng.

3) Khởi tạo ngẫu nhiên các trung tâm cụm

i=1, 2, ..., c và

l = 1, 2.., n trong Layer1 và lớp thành viên

với k=1, 2,

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

...,n và i = 1, 2, ...,c trong Layer2.

4) Cập nhật các hệ số

và

và giá trị mạng ban đầu

với j =1, 2, ..., s

(s=c.p trong Layer1 và s=n.c trong Layer2).

5) Thiết lập chỉ số hồi quy g =1 cho Layer1.

6) Trong Layer1, tính ma trận trọng số W theo công thức (12), ma trận

tín hiệu vào bên ngoài I theo công thức (11), và giá trị mạng NET

theo công thức (4).

7) For j = 1 to s do

then

;

8) For j = 1 to s do

then

else

9) if

then goto 10)

else {g:= g+1; goto 6)}.

10) Đặt chỉ số hồi quy g=1 cho Layer2.

11) Trong Layer2, tính ma trận trọng số W theo công thức (23), ma

trận trọng số Z theo công thức (24) và

và ma trận

12) For j = 1 to s do

then

;

13) For j = 1 to s do

then

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

else

14) if

then goto 15)

else {g:= g+1; goto 11)}.

15) if

then Stop else goto 4

Đối với FBACN với việc học thì thuật toán tƣơng tự nhƣ của FBACN,

nhƣng từ bƣớc 10 đến bƣớc thứ 14 thì đƣợc thay bằng 10’ đến 17’. Trƣớc hết

ta định nghĩa một số tham số: p0 là hằng số tỉ lệ xác suất nằm trong [0,1], sử

lặp đang xử lý cần giữ thăng bằng ấm tại nhiệt độ T). Tstart là nhiệt độ xung

dụng để tính xác suất. EquiCycle là chu kỳ thăng bằng ấm(có nghĩa là khi vòng

quanh, Tstop là nhiệt độ dừng(tức dừng việc học) và Tstep là tổng nhiệt độ thấp

hơn trong mỗi vòng lặp.

Giải thuật của FBACN với việc học đƣợc thực hiện nhƣ sau:

GIẢI THUẬT CỦA FBACN VỚI VIỆC HỌC

1’ -> 9’ = 1 -> 9 của FBACN

10’) Đặt T = Tstart.

11’) Đặt chỉ số hồi quy g = 1 cho Layer2.

12’) Trong Layer2, tính giá trị của ma trận trọng số W theo công thức

(23), ma trận trọng số Z theo công thức (24) và ma trận tín hiệu

vào từ bên ngoài I và ma trận giá trị mạng NET.

13’) if

then

{ For j =1 to s do

{ Tính xác xuấ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

}}

esle {

For j =1 to s do {

}};

14’) for j = 1 to s do

then

15’) for j =1 to s do {

then { if Rand([0,1])

then

else

}

else { if

then

else

}}

16’) if

then goto 17’)

else {g:= g+1; goto 12’)}.

17’) if T>Tstop then {T:=T-Tstep; goto 11’)} else goto 18’).

18’) if

then Stop else goto 4)

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

CHƢƠNG 5

CÀI ĐẶT THỬ NGHIỆM VÀ ỨNG DỤNG

5.1. Cài đặt thử nghiệm thuật toán FCM ........................................................................ 5.2. Ứng dụng thuật toán FCM-Cải tiến vào nhận dạng ảnh ..........................................

79 82

Chƣơng này trình bày kết quả xây dựng chƣơng trình thử nghiệm của

thuật toán FCM và ứng dụng thuật toán FCM-Cải tiến vào quá trình nhận

dạng ảnh.

5.1. Cài đặt thử nghiệm thuật toán FCM

FCM là một thuật toán đƣợc áp dụng khá nhiều trong phân cụm dữ liệu

vì hiệu năng và tính hiện thực của nó khá tốt. Thuật toán FCM đƣợc bắt đầu

bằng cách chọn C cụm và chọn ngẫu nhiên c điểm làm trung tâm cụm hoặc

chọn phân hoạch ngẫu nhiên C cụm và tính trọng tâm của từng cụm này. Nếu

số lƣợng dữ liệu nhỏ hơn số cụm thì ta gán mỗi dữ liệu là một trọng tâm của

cụm, mỗi trọng tâm sẽ có 1 số cụm. Nếu số lƣợng dữ liệu lớn hơn số cụm, với

mỗi dữ liệu, ta tính toán độ tƣơng tự có trọng số giữa điểm đó và trọng tâm

cụm và lấy khoảng cách tối thiểu. Dữ liệu này thuộc về cụm có khoảng cách

tối thiểu tới dữ liệu đó. Khi chúng ta không chắc chắn về vị trí của trọng tâm,

ta cần điều chỉnh vị trí trọng tâm dựa vào dữ liệu đã cập nhật hiện tại. Sau đó,

ta gán tất cả dữ liệu tới trọng tâm mới này. Quá trình này đƣợc lặp lại cho tới

khi không còn dữ liệu di chuyển sang cụm khác. Về mặt toán học, vòng lặp

này có thể chứng minh là hội tụ cực tiểu cục bộ.

Quá trình cài đặt của thuật toán đƣợc mô phỏng thông qua giao diện

của chƣơng trình nhƣ Hình 5.1 và Hình 5.2 dƣới đây:

 Ngôn ngữ sử dụng là Visual C++ 6.0

 Tham số ban đầu: Số cụm = 3, tham số mũ m = 2

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

 Dữ liệu đầu vào là các điểm màu khác nhau

Hình 5.1: Giao diện của chƣơng trình khi khởi động

Khi ngƣời sử dụng nhập số cụm vào khung “Nhập số cụm”, kích chuột

vào khung chƣơng trình để tạo ra các điểm của cụm, vị trí của các điểm đƣợc

thể hiện ở khung “Toạ độ xy”. Chƣơng trình sẽ tự động tạo ra các cụm dữ

liệu bằng cách tối giản tổng bình phƣơng các khoảng cách giữa dữ liệu và

trọng tâm cụm tƣơng ứng khi ta kích chuột vào khung chƣơng trình để tạo ra

mỗi điểm. Mỗi điểm và tọa độ của nó biểu thị cho một đối tƣợng với mô tả

hai thuộc tính của đối tƣợng đó là màu sắc của điểm và số nhãn biểu thị cho

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

cụm.

Dƣới đây là hình ảnh thu đƣợc khi chạy chƣơng trình với số cụm nhập vào là

8 cụm..

Hình 5.2: Giao diện của chƣơng trình khi làm việc

Chƣơng trình tự động phân thành 8 cụm thông qua số màu hiện trong

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

từng cụm và tâm của mỗi cụm.

5.2. Ứng dụng thuật toán FCM-Cải tiến vào nhận dạng ảnh

Bài toán nhận dạng chính là quá trình phân loại các đối tƣợng đƣợc

biểu diễn theo một mô hình nào đó và gán cho chúng vào một lớp dựa theo

các quy luật và các mẫu chuẩn. Nhận dạng có rất nhiều ứng dụng, đƣợc áp

dụng vào rất nhiều lĩnh vực, chẳng hạn nhƣ nhận dạng vân tay, nhận dạng chữ

viết, nhận dạng ảnh… Và phân cụm màu là một bƣớc rất quan trọng trong quá

trình nhận dạng ảnh.

Do số lƣợng điểm ảnh là rất lớn, thƣờng trên 80.000 điểm ảnh và số

lƣợng màu của mẫu dữ liệu ảnh là phụ thuộc vào độ sắc nét của ảnh. Nếu ảnh

có chất lƣợng càng tốt thì số lƣợng màu càng lớn, nhƣng dù ảnh có chất lƣợng

nhƣ thế nào đi nữa thì số lƣợng màu vẫn lớn. Mặt khác, trong nhận dạng ảnh,

chúng ta chỉ quan tâm tới một số yếu tố nhất định, chẳng hạn nhƣ mắt, lông

mày, miệng và da,... nên số lƣợng màu mà ta quan tâm cũng không lớn lắm,

vì vậy áp dụng thuật toán FCM-Cải tiến vào việc phân cụm màu trong nhận

dạng ảnh là một ứng dụng rất cần thiết trong bài toán này.

Quá trình ứng dụng của thuật toán FCM-Cải tiến đƣợc mô phỏng thông

qua giao diện của chƣơng trình với Hình 5.3, Hình 5.4 và Hình 5.5 dƣới đây:

 Ngôn ngữ sử dụng là Visual C++ 6.0

 Tham số ban đầu: Khai báo mảng lƣu trữ số lƣợng màu của ảnh, mảng

lƣu trữ số trung tâm của cụm, số lƣợng cụm, tham số mũ.

 Dữ liệu đầu vào là một File ảnh màu(Bitmap)

 Dữ liệu đầu ra là một ảnh màu đã đƣợc nhận dạng với số cụm mà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

đƣợc thuật toán FCM-Cải tiến thực hiện phân cụm.

Hình 5.3: Giao diện của chƣơng trình khi khởi động

Khi chƣơng trình khởi động xong, ta chọn một ảnh nguồn để thực hiện

bằng cách ấn vào nút “Mở File Ảnh” và chọn một ảnh cần thực hiện nhƣ Hình

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.4 dƣới đây:

Hình 5.4: Giao diện của chƣơng trình khi chọn ảnh để phân cụm

Sau khi chọn xong, ta ấn vào nút “Thực hiện phân cụm”. Chƣơng trình sẽ

thực hiện quá trình nhận dạng và phân cụm màu theo thuật toán FCM-Cải tiến

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

và hiển thị kết quả ở khung “Ảnh Đích” nhƣ Hình 5.5 dƣới đây.

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

Hình 5.5: Giao diện của chƣơng trình khi thực hiện phân cụm

KẾT LUẬN

Trong quá trình tìm hiểu và hoàn thành luận văn tốt nghiệp với đề tài

“Nghiên cứu một số phương pháp phân cụm mờ và ứng dụng”, dù đã đạt

đƣợc những kiến thức nhất định, nhƣng em nhận thấy phân cụm dữ liệu trong

KPDL nói chung và phân cụm dữ liệu mờ nói riêng là một lĩnh vực nghiên

cứu rộng lớn, nhiều triển vọng. Đề tài đã cố gắng tập trung tìm hiểu, nghiên

cứu và trình bày đƣợc một số kỹ thuật và thuật toán phân cụm dữ liệu phổ

biến, một số kỹ thuật phân cụm mờ và mô hình mạng nơron đa khớp dùng cho

phân cụm mờ trong KPDL hiện nay, trình bày một số cải tiến của thuật toán

phân cụm mờ(FCM-Cải tiến) dựa trên các phƣơng pháp đã có, cài đặt thử

nghiệm thuật toán phân cụm mờ(FCM) với ứng dụng phân cụm các điểm màu

và thực hiện cài đặt ứng dụng của thuật toán FCM-Cải tiến đối với việc phân

cụm màu trong bài toán nhận dạng ảnh màu.

Tuy nhiên, do những hạn chế về tài liệu và thời gian nên em mới chỉ

tìm hiểu đƣợc một số kỹ thuật điển hình trong phân cụm và đặc biệt là phân

cụm mờ, cài đặt và thử nghiệm một số thuật toán ứng dụng .... nhƣng còn

một số kỹ thuật khác vẫn chƣa đƣợc tìm hiểu và khai thác, cài đặt thử nghiệm

chƣa áp dụng đƣợc cho bài toán phân cụm tổng quát....

Trong thời gian tới em sẽ tiếp tục nghiện cứu thêm một số kỹ thuật

phân cụm và đặc biệt là các thuật toán phân cụm mờ kết hợp song song ứng

dụng vào một số bài toán thực tế ở Việt Nam hiện nay và hy vọng sẽ dần đƣa

những kiến thức đã có từ đề tài này sớm trở thành thực tế, phục vụ cho cuộc

sống con ngƣời chúng ta.

Học viên thực hiện

An Hồng Sơn

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

TÀI LIỆU THAM KHẢO

Tài liệu Tiếng Việt:

1. Phan Đình Diệu (1999), “Lô Gích trong Các Hệ Tri Thức”, NXB

Đại học Quốc gia Hà Nội, Hà Nội.

2. Nguyễn Trọng Thuần, “Điều khiển Logic và ứng dụng”, Nhà xuất

bản Khoa học và Kỹ thuật, 2004.

3. Bùi Công Cƣờng và Nguyễn Doãn Phƣớc, “Hệ mờ, mạng nơron và

ứng dụng ”, NXB Khoa học và kỹ thuật, 2006.

4. Vũ Thanh Nguyên, “Ứng dụng logic mờ, mạng nơron mờ, hệ các

luật mờ phân tích dự báo các mặt hàng chiến lược”, Hội thảo khoa

học Hệ mờ, mạng nơron và ứng dụng, lần 1, Hà nội 8-9/11/2006.

5. Ngô Quốc Tạo, “Giáo trình Xử Lý Ảnh”, Lớp CHCLC-ĐH Công

Nghệ-ĐHQG Hà Nội 2001-2002.

6. Ngô Quốc Tạo, “Bài giảng môn Data Mining”, Lớp CHK5-ĐH Thái

Nguyên 2006-2008.

7. Ngô Quốc Tạo, “Bài giảng môn Xử Lý Ảnh”, Lớp CHK5-ĐH Thái

Nguyên 2006-2008.

Tài liệu Tiếng Anh:

8. Daniel T. Larose, “Discovering Knowledge in Data: An

Introduction toData Mining”, ISBN 0-471-66657-2 CopyrightC

2005 John Wiley & Sons, Inc.

9. A. Arning, R. Agrawal, and P. Raghavan. Alinear method for

deviation detection in larger databases, “In Proc. 1996 Int. Conf.

Data Mining and Knowledge Discovery (KDD-96)”, Portland,

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

Oregon, August 1996.

10. P.S. Bradley, U. Fayyad, C. Reina, Scaling Clustering Algorithms

to Large Databases, “In Proc of 4th International conference on

Knowledge Discovery and Dala Mining (Kdd-98)”, New York. 1998.

11. D. Fisher, “Knowledge acquisition via incremental conceptual

clustering, In Machine Learning”, 2 pp. 139-/72, 1987.

12. D. Gibson, J. Kleinberg, P. Raghavan, “Clustering Categorical

Data: An Approach Based on Dynamical Systems”, VLDB Journal 8

(3-4) pp. 222-236, 2000.

13. J. Han, M. Kamber, “Data Mining Concepts and Techniques”,

Morgan Kaufmann Publishers, 2001.

14. A.K. Jain, R.C. Dubes, “Algorithms for clustering data”, Ptentice

Hall, Englewood Cliffs, NJ, 1988.

15. R.A. Jarvis, E.A. Patrick, “Clustering using a similarity measure

based on shared near neighbors”, IEEE Transactions on Computers

C22, pp. 1025-1034, 1973.

16. M. Manago, Y. Kodratoff, “Inđuction of Decision Trees from

Complex Structuted Data, In Knowledge Discovery in Databases”,

AAAI/Th MIT press, pp. 289-306, 1991.

17. J.C.Bezdek, “Pattern Recognition with fuzzy Objective Function

Algorithms”, New York, Plenum, 1981.

18. W.Pedrycz, “Algorithms of fuzzy clustering with partial

supervision”, Pattern Recognition, vol. 23, pp.121-146, 1990.

19. M.P.Windham, “Cluster validity for fuzzy clustering algorithms”,

“Fuzzy Sets and System”, vol. 3, pp. 177-183, 1981.

20. W.Pedrycz, “Algorithms of fuzzy clustering with partial

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

supervision”, Pattern Recognition, vol. 23, pp.121-146, 1990.

21. G.Bueno, R.Gonzalez, J.Gonzalez, and M.Garcia-Rojo, “Fuzzy

colour C-means clustering for pattern segmentation in histological

images”, The 3rd European Medical and Biological Engineering

Conference, 2005.

22. Chih-Hsiu Wei, Chin - Shyurng Fahn, “The multisynapse neural

network and its application to fuzzy clustering”.

23. J.H.Wang and C.Y.Peng, “Optimal clustering using neural

network”, in Proc. IEEE Int. Conf. Syst., Man, Cybern., vol.2, 1998,

pp.1625-1630.

24. Y.Guo, X.Yin, and W.Gong, “ART2 neural network clustering for

hierarchical simulation”, in Proc. SPIE Int. Soc.Opt.Eng., vol.

2.1998, pp.35-48.

25. M.F.Augusteijn and U.J.Steck, “Supervised adaptive clustering: A

hybrid neural network clustering algorithm”, neural

Comput.Applicat., vol.7,no. 1, pp.78-89, 1998.

26. E. C. Tsao, J. C. Bezdek, and N. R. Pal, “Fuzzy Kohonen

clustering network”, Patterm recognition, vol.27, no.5, pp.757-764,

1994.

27. J. Lin, K. Cheng, and C.Mao, “A fuzzy Hopfield neural

network for medical image segmentation”, IEEE Trans. Nuclear

Sci., vol.43, 1996.

28. Hathaway R.J and Bezdek J.CNTT (2000), “Generalized

fuzzy c-means clustering Strategies using LP Norm Distances”,

IEEE Trans.Fuzzy Syst, No 5, pp.576-582.

29. J.E.Steck and S.N.Balakrishnan, “Use of Hopfield newral networks

in optimal guidance”, IEEE Trans. Aerosp.Electron. Syst., vol.30,

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

no.1, pp 287-293, Jan.1994.