Luận văn Thạc sĩ Công nghệ thông tin: Tập thô và bài toán phân cụm dữ liệu

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

VŨ THỊ BÍCH THẢO TẬP THÔ VÀ BÀI TOÁN PHÂN CỤM DỮ LIỆU LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - 2014

1

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

VŨ THỊ BÍCH THẢO TẬP THÔ VÀ BÀI TOÁN PHÂN CỤM DỮ LIỆU

Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HƯỚNG DẪN KHOA HỌC: PGS.TS HOÀNG XUÂN HUẤN Hà Nội - 2014

2

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Kết quả trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kì công trình nào khác.

Tác giả

3

Vũ Thị Bích Thảo

LỜI CẢM ƠN

Tôi xin gửi lời cảm ơn với lòng kính trọng và biết ơn sâu sắc tới PGS.TS Hoàng Xuân Huấn. Thầy đã hƣớng dẫn, chỉ bảo tận tình, cung cấp cho tôi những kiến thức bổ ích đồng thời tạo động lực giúp tôi hoàn thành luận văn đúng thời hạn. Thầy luôn theo sát, hỗ trợ nhiệt tình, giải đáp những vƣớng mắc trong quá trình tôi thực hiện luận văn. Tôi xin chân thành cảm ơn các Thầy, Cô trong khoa Công nghệ thông tin, trƣờng Đại học Công nghệ, đã tạo điều kiện cũng nhƣ môi trƣờng học tập tốt trong suốt quá trình tôi theo học ở đây.

Tôi cũng xin gửi lời cảm ơn tới BGH trƣờng CĐCN Thực Phẩm, lãnh đạo Khoa CNTT cùng toàn thể cán bộ, giáo viên trong khoa đã hỗ trợ, tạo điều kiện tốt nhất để tôi có thể hoàn thành chƣơng trình học.

Cuối cùng tôi xin cảm ơn gia đình hai bên nội, ngoại đã ủng hộ giúp đỡ

4

tôi rất nhiều về mặt tinh thần trong tất cả những công việc mà tôi đã thực hiện.

MỤC LỤC

LỜI CAM ĐOAN ............................................................................................................ 3

LỜI CẢM ƠN .................................................................................................................. 4

MỤC LỤC ....................................................................................................................... 5

DANH MỤC KÝ HIỆU VIẾT TẮT ............................................................................... 7

DANH MỤC CÁC HÌNH VẼ ..................................................................................... 8

MỞ ĐẦU ......................................................................................................................... 9

CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU ........................................... 12

1.1. Độ tƣơng đồng .................................................................................................... 13

1.2. Các phƣơng pháp và các thuật toán phân cụm dữ liệu ....................................... 15

1.2.1 Phƣơng pháp dựa vào hàm mục tiêu ................................................................ 16

1.2.2. Các phƣơng pháp phân cụm phân cấp ............................................................ 20

1.2.3. Các phƣơng pháp dựa vào mật độ ................................................................... 25

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

CHƢƠNG 2: LÝ THUYẾT TẬP THÔ......................................................................... 34

2.1 Hệ thông tin và hệ quyết định .............................................................................. 34

2.2 Tính không phân biệt đƣợc (Indiscernibility) ...................................................... 36

2.3 Xấp xỉ tập hợp ...................................................................................................... 38

CHƢƠNG 3: TẬP THÔ VÀ BÀI TOÁN PHÂN CỤM ............................................... 43

3.1. Phân cụm thô (Rough C-means) ......................................................................... 44

3.2. Phân cụm mờ ....................................................................................................... 47

3.3. Phân cụm thô-mờ (Rough-Fuzzy C-means) ....................................................... 50

5

3.4. Phân cụm bóng .................................................................................................... 52

CHƢƠNG 4. ỨNG DỤNG RCM TRONG PHÂN CỤM ẢNH ................................... 58

4.1 Phân vùng ảnh: ..................................................................................................... 58

4.2 Ảnh và những khái niệm liên quan ...................................................................... 59

4.2.1 Điểm ảnh (Picture Element) ............................................................................. 59

4.2.2 Độ phân giải của ảnh ........................................................................................ 60

4.2.3 Mức xám của ảnh ............................................................................................. 60

4.2 Phân cụm ảnh sử dụng phân cụm thô và phân cụm mờ ....................................... 61

4.3 Thử nghiệm phân cụm ảnh sử dụng phân cụm thô và phân cụm mờ .................. 61

4.4 So sánh và đánh giá: ............................................................................................ 65

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

Tài liệu tham khảo ......................................................................................................... 69

6

DANH MỤC KÝ HIỆU VIẾT TẮT

STT Từ viết tắt Từ hoặc cụm từ

FCM 1 Fuzzy C-Means (Thuật toán phân cụm mờ)

RCM 2 Rough C-Means (Thuật toán phân cụm thô)

RFCM 3 Rough Fuzzy C-Means (Thuật toán phân cụm thô- mờ)

SCM 4 Shadowed C-Means (Thuật toán phân cụm bóng)

RGB Red Green Blue 5

BIRCH 6 Balanced Iterative Reducing and Clustering using Hierarchies

CURE Clustering Using Representatives 7

OPTICS 8 Ordering Point To Identify the Clustering Structure

STING A STatistical INformation Grid approach 9

7

10 CF Clustering Feature

DANH MỤC CÁC HÌNH VẼ

Hình 1.1 Ví dụ về phân cụm .......................................................................................... 12

Hình 1.2 Biểu đồ hình sao thể hiện 3 cụm trong ma trận bộ phận U ............................ 17

Hình 1.3 Biểu đồ biểu diễn các mẫu trong phân cụm phân cấp .................................... 21

Hình 1.4 Ba cách tính khoảng cách giữa hai cụm ......................................................... 22

Hình 1.5 Trộn 2 cụm theo thuật toán CURE ................................................................. 25

Hình 1.6 Hai cụm đƣợc tìm bởi thuật toán DBSCAN ................................................... 27

Hình 1.7 Thứ tự cụm theo OPTICS ............................................................................... 29

Hình 1.8 Ba tầng liên tiếp nhau của cấu trúc STING .................................................... 30

Hình 1.9 CLIQUE xác định các vùng tiềm năng dựa trên các đơn vị dày đặc ............. 33

Hình 2.1: Hình minh họa khái niệm tập thô .................................................................. 34

Hình 3.1 Ba vùng của một cụm ..................................................................................... 45

Hình 3.2: Hình minh họa cụm mờ ................................................................................. 47

Hình 3.3. Các tập bóng đƣợc tạo bởi tập mờ thông qua một ngƣỡng ........................... 54

Hình 3.4. Các tập bóng đƣợc tạo ra bởi hàm thành viên mờ f(x) .................................. 56

Hình 4.1 Minh họa ảnh đã phân vùng ........................................................................... 58

Hình 4.2: Chuyển hình ảnh từ hệ màu RGB sang ảnh xám .......................................... 62

Hình 4.3 Hình ảnh chụp cắt lớp sọ ngƣời ...................................................................... 63

Hình 4.4 Kết quả sau khi sử dụng phân cụm mờ .......................................................... 64

Hình 4.5 Kết quả sau khi sử dụng phân cụm thô........... Error! Bookmark not defined.

Hình 4.7 Kết quả sau khi sử dụng phân cụm mờ .......................................................... 65

Hình 4.8 Kết quả sau khi sử dụng phân cụm thô........... Error! Bookmark not defined.

8

MỞ ĐẦU

Phân cụm dữ liệu là một kỹ thuật quan trọng trong công nghệ tri thức, nó đƣợc ứng dụng rộng rãi và đa dạng trong các ngành khoa học nhƣ sinh học, tâm lý học, y học, ngành marketing, thị giác máy tính, và điều kiển học v.v. Phân cụm dữ liệu tổ chức dữ liệu bằng cách nhóm các đối tƣợng có độ tƣơng đồng cao vào một cụm, các đối tƣợng thuộc các cụm khác nhau có độ tƣơng đồng thấp hơn so với các đối tƣợng trong cùng một cụm. Tùy theo đặc điểm cấu trúc của tập dữ liệu và mục đích sử dụng, có các phƣơng pháp giải quyết khác nhau nhƣ: Phân cụm dựa vào hàm mục tiêu, phân cụm phân cấp, phân cụm dựa vào mật độ và phân cụm dựa vào lƣới.

Thông thƣờng, thông tin về thế giới xung quanh là không chính xác, không đầy đủ, không chắc chắn hoặc chồng chéo. Đó cũng là vấn đề gặp phải khi phân cụm dữ liệu. Phân cụm đƣợc chia làm hai loại phân cụm là phân cụm cứng và phân cụm mềm. Trong phân cụm cứng đối tƣợng đƣợc phân thành các cụm khác nhau, mỗi đối tƣợng thuộc về chính xác một cụm, ngƣợc lại ở phân cụm mềm các đối tƣợng có thể thuộc về nhiều hơn một cụm và mỗi đối tƣợng có độ thuộc với cụm. Cụ thể trong luận văn, tôi sẽ nghiên cứu các thuật toán phân cụm trong cả hai loại phân cụm này: Phân cụm thô (phân cụm cứng) và phân cụm mờ (phân cụm mềm). Ngoài ra tôi cũng nghiên cứu thêm về 2 thuật toán kết hợp từ hai loại phân cụm trên là phân cụm thô mờ và phân cụm bóng.

9

Năm 1965, giáo sƣ Lotfi A. Zadeh (Đại học California ở Berkeley) đề xuất lý thuyết tập mờ (fuzzy set), là phần mở rộng của lý thuyết tập hợp truyền thống. Ý tƣởng chính của lý thuyết tập mờ là các phần tử của tập có độ thuộc trong khoảng [0,1] thay vì giá trị nhị phân. Nó là công cụ mô hình hóa sự không chắc chắn, không rõ ràng trong hệ thống phức tạp. Trong phân cụm mờ, thuật toán thƣờng đƣợc sử dụng nhất là Fuzzy C-Means (FCM) đƣợc đề xuất vào năm 1973 bởi J.C Dunn và đƣợc cải tiến lại bởi Bezděk vào năm 1981. FCM thƣờng đƣợc sử dụng để xử lý trƣờng hợp các cụm chồng chéo nhau, tức là một số đối tƣợng có thể thuộc về nhiều hơn một cụm. Trong đó, mỗi một đối tƣợng có độ thuộc khác nhau đối với các cụm, chứ không hoàn toàn chỉ thuộc về một cụm đƣợc biểu diễn qua ma trận phân hoạch. FCM sử dụng giá trị trung bình (mean) độ thuộc của các đối tƣợng trong ma trận phân hoạch làm tâm cụm. Các bƣớc

trong thuật toán là quá trình thực hiện cập nhật các đối tƣợng của cụm và ma trận phân hoạch. Thuật toán chi tiết sẽ đƣợc trình bày cụ thể trong luận văn.

Đến năm 1982, Zdzislaw Pawlak đề xuất ra lý thuyết tập thô với mục đích là để phân loại thông tin và tri thức không chính xác hoặc không đầy đủ. Khái niệm cơ bản của lý thuyết tập thô là xấp xỉ trên và xấp xỉ dƣới của một tập dữ liệu. Xấp xỉ dƣới bao gồm những đối tƣợng chắc chắn thuộc về cụm, trong khi xấp xỉ trên bao gồm những đối tƣợng có thể đƣợc phân lớp là thành viên không chắc chắn của cụm. Mỗi tập đƣợc xác định thông qua xấp xỉ trên và xấp xỉ dƣới đƣợc gọi là tập thô. Trong khuôn khổ luận văn, tôi tìm hiểu và trình bày cụ thể thuật toán Rough C-Means (RCM). Thuật toán RCM đƣợc Lingras và West đề xuất năm 2004 [4]. Trong đó, mỗi cụm có vùng xấp xỉ trên và vùng xấp xỉ dƣới của riêng mình. Việc xác định cụm phụ thuộc vào hai vùng xấp xỉ, không phải tất cả các đối tƣợng nhƣ trong FCM. Cụ thể, nếu nhƣ FCM xác định cụm dựa vào độ thuộc của đối tƣợng vào cụm thì RCM lựa chọn cụm bằng cách so sánh khoảng cách từ đối tƣợng tới tâm cụm so với một ngƣỡng mà ngƣời dùng tự chọn. Tất cả các đối tƣợng đƣợc chia vào ba vùng, cụ thể là, vùng lõi (Core level), vùng biên (Boundary level) và vùng loại trừ (Exclusion level). Các đối tƣợng nằm ở vùng lõi chắc chắn thuộc về cụm. Các đối tƣợng ở vùng biên có thể thuộc về cụm. Các đối tƣợng khác thuộc phạm vi vùng loại trừ không thuộc cụm.

Ngoài ra, trong luận văn tôi trình bày chi tiết hai thuật toán nữa là phân cụm thô-mờ, phân cụm bóng tƣơng ứng là Rough Fuzzy C-Means (RFCM) và Shadowed C –Means (SCM). RFCM là thuật toán kết hợp từ FCM và RCM, trong đó cách xác định cụm của RFCM giống nhƣ RCM là dựa vào hai vùng xấp xỉ trên và xấp xỉ dƣới. Tuy nhiên cách xác định các vùng xấp xỉ này không dựa vào khoảng cách từ các đối tƣợng tới tâm mà dựa vào độ thuộc của phần tử đối với cụm giống nhƣ FCM. Thuật toán này giúp cho việc phân cụm mạnh hơn so với hai thuật toán phân cụm trƣớc.

10

Đối với SCM, các đối tƣợng cũng đƣợc chia vào ba vùng tƣơng tự nhƣ trong RCM nhƣng tên gọi và cách xác định mỗi vùng là khác nhau. Ba vùng lõi, vùng biên và vùng loại trừ trong lý thuyết tập thô tƣơng ứng với ba giá trị logic 0,1, và [0,1] trong tập bóng, cụ thể, lõi (Core), loại trừ (Exclusion), bóng

(shadow). Ngoài ra, SCM tạo ra sự khác biệt với FCM là nó tăng độ thuộc của một số phần tử tới 1 và giảm độ thuộc của một số phần tử khác về 0 để làm tăng sự tƣơng phản của các phần tử nhằm làm giảm sự chồng chéo không chắc chắn nhƣ ở trong FCM. Theo khía cạnh này, tập bóng có thể đƣợc coi là cầu nối giữa tập mờ và thô.

Hiện nay phân cụm ảnh là một vấn đề đang nhận đƣợc nhiều sự quan tâm từ các nhà nghiên cứu. Mục đích là để đơn giản hóa hoặc làm nổi bật một số đối tƣợng nhằm dễ dàng hơn trong việc phân tích hình ảnh. Để phân cụm ảnh, phải chuyển các điểm màu của ảnh sang hệ màu xám với giá trị từ 0 đến 255 sau đó áp dụng thuật toán phân cụm. Trƣớc đây, FCM đƣợc sử dụng nhiều trong phân cụm ảnh và nó đƣợc ứng dụng trong nhiều lĩnh vực khác nhau nhƣ phân tích hình ảnh y tế, phát hiện các đối tƣợng,… Trong cuốn luận văn này, tôi đã nghiên cứu và áp dụng RCM cho phân cụm ảnh, từ đó so sánh sự khác biệt so với phân cụm ảnh sử dụng FCM.

Luận văn của tôi đƣợc chia làm 4 chƣơng với nội dung nhƣ sau:

Chƣơng 1: Tổng quan về phân cụm dữ liệu. Giới thiệu về phân cụm dữ liệu và các phƣơng pháp phân cụm với mỗi phƣơng pháp trình bày một thuật toán tƣơng ứng.

Chƣơng 2: Lý thuyết tập thô. Trình bày tổng quan về lý thuyết tập thô bao

gồm hệ thông tin, hệ quyết định, tính không phân biệt đƣợc và xấp xỉ tập hợp.

Chƣơng 3: Tập thô và bài toán phân cụm. Giới thiệu các thuật toán phân cụm: Phân cụm thô, phân cụm mờ, phân cụm thô-mờ, phân cụm bóng, các bƣớc phân cụm và công thức chi tiết của từng thuật toán.

11

Chƣơng 4: Ứng dụng RCM trong phân cụm ảnh. Xây dựng phân cụm ảnh bằng RCM, đƣa ra kết quả phân cụm, đánh giá và so sánh với phân cụm ảnh bằng FCM.

CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU

Bài toán phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu thuộc lĩnh vực học không giám sát, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn đƣợc quan tâm trong tập dữ liệu lớn, từ đó cung cấp các thông tin hữu ích hỗ trợ cho việc ra quyết định. Các thuật toán phân cụm hƣớng tới việc tìm kiếm cấu trúc trong dữ liệu. Phƣơng pháp này còn đƣợc gọi là “học không thầy” hay “học không có giám sát” (Unsupervised Learning) trong lĩnh vực nhận dạng mẫu (Pattern Recognition) nói riêng và trong trí tuệ nhân tạo nói chung.

Một cụm bao gồm một tập các đối tƣợng có độ tƣơng đồng cao. Định nghĩa về cụm đƣợc phát biểu một cách không hình thức nhƣ sau: Một cụm là một tập các thực thể (các đối tƣợng) tƣơng tự nhau, và các thực thể ở các cụm khác nhau thì không giống nhau.

Hình 1.1 Ví dụ về phân cụm

12

Tùy vào từng ứng dụng, đặc tính của dữ liệu và từng phƣơng pháp phân cụm cụ thể, chúng ta có thể xem xét các dữ liệu nhƣ là các điểm trong không gian thỏa mãn điều kiện độ tƣơng đồng giữa hai điểm bất kỳ trong một cụm lớn hơn độ tƣơng đồng giữa một điểm bất kỳ trong cụm đó với một điểm bất kỳ không thuộc cụm hoặc các cụm có thể đƣợc mô tả nhƣ là các vùng chứa các đối

tƣợng có mật độ cao trong không gian nhiều chiều, đƣợc tách với các vùng chứa các đối tƣợng có mật độ thấp hơn.

Chúng ta có thể dễ dàng phát biểu không hình thức về một cụm, nhƣng lại rất khó để có thể đƣa ra một định nghĩa hình thức về cụm. Bởi vì thực tế thì các đối tƣợng đƣợc nhóm vào trong các cụm theo các mục đích khác nhau trong từng ứng dụng. Dữ liệu có thể cho thấy các cụm theo hình dạng và theo các kích thƣớc cụm.

Các vấn đề liên quan tới bài toán phân cụm dữ liệu là vấn đề biểu diễn dữ liệu trong máy tính, xác định phƣơng pháp, từ đó đƣa ra thuật toán cụ thể để áp dụng, đồng thời xác định độ tƣơng đồng giữa các đối tƣợng. Đối với các thuật toán trong phƣơng pháp dựa vào phân hoạch thì chúng ta còn phải xây dựng hàm đánh giá phù hợp để thuật toán cho ra kết quả phân cụm tốt.

1.1. Độ tương đồng

Độ tƣơng đồng giữa các đối tƣợng mô tả tính chất giống hoặc khác nhau giữa chúng theo một ý nghĩa nào đó. Có rất nhiều hàm đƣợc dùng để biểu diễn độ tƣơng đồng giữa các đối tƣợng. Tuy nhiên, trong khuôn khổ của luận văn chỉ trình bày một số các hàm đo tƣơng đồng phổ biến gọi là các hàm khoảng cách. Khoảng cách giữa hai mẫu thứ i và mẫu thứ k ký hiệu là d(i,k) phải thỏa mãn các tính chất sau:

1. d(i,i)=0 với mọi i.

2. d(i,k)=d(k,i) với mọi cặp (i,k).

3. d(i,k)>=0 với mọi cặp (i,k).

13

Hàm đánh giá độ tƣơng đồng có thể đƣợc xác định theo một số cách. Giả sử rằng chúng ta có một ma trận mẫu [xij] với xij là giá trị của đặc trƣng thứ j của mẫu i. Tất cả các đặc trƣng là liên tục và đƣợc ƣớc lƣợng theo tỷ lệ xích. Hàm khoảng cách phổ biến là khoảng cách Minkowski (1) dùng để ƣớc lƣợng độ tƣơng đồng. Mẫu thứ i tƣơng ứng với dòng thứ i của ma trận mẫu đƣợc ký hiệu là một vector cột xi.

Với d là số đặc trƣng, n là số lƣợng mẫu, T ký hiệu là vector chuyển vị.

Khoảng cách Minkowski đƣợc định nghĩa nhƣ sau:

với r>=1 (1.1)

Các hàm khoảng cách Minkowski thỏa mãn tính chất các tính chất sau:

4. d(i,k)=0 nếu và chỉ nếu xi=xk

5. d(i,k) với mọi (i,m,k)

Có ba khoảng cách phổ biến sử dụng khoảng cách Minkowsky đƣợc định

nghĩa nhƣ sau:

Khoảng cách Euclide (r=2):

(1.2)

Khoảng cách Manhattan (r=1)

(1.3)

Khoảng cách Max (r ):

(1.4)

Khoảng cách Euclide là chuẩn đƣợc dùng phổ biến nhất trong các chuẩn theo khoảng cách Minkowski. Các khái niệm hình học quen thuộc về tính bất biến của phép tịnh tiến và phép quay của không gian mẫu là phù hợp với chuẩn Euclide. Các ứng dụng cụ thể tác động lớn đến việc chọn ra hàm khoảng cách nào đƣợc sử dụng.

14

Ngoài các hàm khoảng cách đƣợc sử dụng để đánh giá độ tƣơng đồng của các đối tƣợng nêu trên còn có rất nhiều cách đánh giá độ tƣơng đồng khác, tùy thuộc vào tính chất của tập dữ liệu.

Để biểu diễn độ tƣơng đồng của tất cả các đối tƣợng trong tập dữ liệu, ngƣời ta thƣờng sử dụng ma trận để lƣu lại giá trị tƣơng đồng giữa các cặp đối tƣợng. Ma trận này đƣợc gọi là ma trận tƣơng đồng. Có thể đƣa ra khái niệm về ma trận tƣơng đồng nhƣ sau:

Ma trận tƣơng đồng [d(i,j)] lƣu giá trị tƣơng đồng trong một ma trận, mỗi dòng và mỗi cột của ma trận biểu diễn một mẫu. Trong đó d(i,j) là độ tƣơng tự giữa mẫu thứ i và mẫu thứ j. Chúng ta bỏ qua các giá trị nằm trên đƣờng chéo chính của ma trận tƣơng đồng khi giả sử rằng tất cả các mẫu có cùng mức độ tƣơng đồng với chính nó. Giả sử rằng ma trận tƣơng đồng là ma trận có tính đối xứng, tất cả các cặp đối tƣợng có cùng một giá trị tƣơng đồng, không phụ thuộc vào thứ tự sắp xếp.

Một ma trận tƣơng đồng có thể là đƣợc gọi là ma trận độ tƣơng tự hoặc

cũng có thể gọi là ma trận bất tƣơng đồng.

Các giá trị tƣơng đồng cũng có thể là nhận giá trị nhị phân, rời rạc hoặc nhận giá trị liên tục. Ví dụ, giả sử rằng một tập đối tƣợng đƣợc phân hoạch vào các tập con. Giá trị nhị phân đo độ tƣơng đồng nhận giá trị 0 với các cặp đối tƣợng ở hai tập con khác nhau và nhận giá trị bằng 1 với các cặp ở cùng một tập con. Nếu giá trị tƣơng đồng là một số nguyên từ 1 tới n(n-1)/2 với n là số lƣợng các đối tƣợng đƣợc xem là ma trận tƣơng đồng nhận giá trị rời rạc. Nếu ma trận tƣơng đồng mà các phần tử nhận giá trị là khoảng cách Euclide giữa các mẫu trong không gian mẫu thì đƣợc xem là ma trận tƣơng đồng nhận giá trị liên tục.

Các thuật toán phân cụm nhóm các đối tƣợng, hay các dữ liệu thành phần dựa trên độ tƣơng đồng giữa các cặp đối tƣợng. Các đối tƣợng đƣợc gọi là các điểm, các trƣờng hợp, các thành phần trong các ứng dụng khác nhau.

1.2. Các phương pháp và các thuật toán phân cụm dữ liệu

15

Phân cụm dữ liệu biểu diễn mối quan hệ giữa các đối tƣợng trong ma trận tƣơng đồng. Nếu các đối tƣợng đƣợc đặc tả nhƣ là các mẫu hoặc các điểm trong không gian metric, thì độ tƣơng đồng có thể là khoảng cách giữa các cặp đối tƣợng, nhƣ là khoảng cách Euclide. Ma trận mẫu và ma trận tƣơng đồng là những dữ liệu vào cho các thuật toán phân cụm. Đã có rất nhiều thuật toán phân

cụm đƣợc xây dựng nhằm áp dụng vào các mục đích cụ thể. Các thuật toán này có thể đƣợc phân vào một trong 4 phƣơng pháp sau đây:

1. Phƣơng pháp phân cụm dựa vào hàm mục tiêu (Object Function-

Based Clustering).

2. Phƣơng pháp phân cụm phân cấp (Hierarchical Clustering).

3. Phƣơng pháp phân cụm dựa trên mật độ (Density-Based

Clustering).

4. Phƣơng pháp phân cụm dựa trên lƣới (Grid-Based Clustering).

1.2.1 Phương pháp dựa vào hàm mục tiêu

Loại phân cụm này liên quan tới phân chia các tập dữ liệu dựa trên một vài chỉ số đƣợc biết đến là hàm mục tiêu. Về mặt bản chất, phân chia N mẫu vào c cụm. Đầu tiên, số lƣợng phân chia đƣợc tính theo công thức

Con số này tăng lên rất nhanh nên không thể liệt kê số lƣợng phân chia này. Tối thiểu hàm mục tiêu có thể coi nhƣ phƣơng pháp tối ƣu hóa. Thách thức thiết kế chính chấp nhận tính toán một hàm mục tiêu có khả năng phản ảnh bản chất của vấn đề nên tối thiểu bộc lộ cấu trúc có nhiều nghĩa trong bộ dữ liệu. Tối thiểu sự khác biệt tiêu chuẩn là một trong những lựa chọn chung nhất. Có N mẫu trong Rn, chúng ta tính tổng khoảng cách giữa các mẫu và tập các nguyên mẫu v1, v2,…,vc

Với

16

là khoảng cách giữa xk và vi. Thành phần quan trọng của tổng trên là ma trận bộ phận U=[uik], i=1,2,…,c,k=1,2,...,N là đóng vai trò phân chia các mẫu vào các cụm. Các giá trị trong U là nhị phân. Mẫu k thuộc về cụm i khi uik=1. Ngƣợc lại k không thuộc về cụm i khi uik=0. Ma trận bộ phận thỏa mãn các điều kiện sau:

Mỗi cụm đều có giá trị, vì thế nó không chứa tất cả các mẫu và nó không

, i=1,2,…,c

rỗng:

, k=1,2,…,N

Mỗi mẫu thuộc về một cụm riêng:

Ma trận bộ phận kí hiệu là U (U là ma trận nhị phân). Ma trận bộ phận thể hiện trực quan cấu trúc của các cụm. Ví dụ, cho ma trận N=8 mẫu chia vào 3 cụm nhƣ sau:

Mỗi hàng thể hiện 1 cụm riêng biệt. Nhƣ vậy chúng ta có sự sắp xếp: Cụm đầu tiên chứa các mẫu {1,4,6,8}, cụm thứ hai chứa các mẫu {2,3} và cụm thứ ba chứa các mẫu còn lại {5,7}.

Biểu diễn ma trận bộ phận bằng đồ thị hình sao (hay gọi là đồ thị radar)

Hình 1.2 Biểu đồ hình sao thể hiện 3 cụm trong ma trận bộ phận U

17

Một vài thuật toán đã đƣợc sử dụng để đạt đƣợc tối ƣu hóa. Thuật toán phổ biến nhất là C-Means (Duda và cộng sự, 2001; Webb, 2002), là cách thiết lập dữ liệu phân cụm tốt.

Phần này sẽ giới thiệu các thuật toán phân cụm dựa vào phân hoạch sau: Thuật toán K-Means (MacQueen, 1967), Thuật toán EM (Expectation Maximazation) (Dempster et al.,1977; Yu et al.,1998; Braley et al 1998), thuật toán K-Medoids. Ba thuật toán này có các cách biểu diễn các cụm khác nhau. Thuật toán K-Means sử dụng tâm (điểm trung bình) của các đối tƣợng trong một cụm làm tâm của cụm đó trong khi thuật toán K-Medoids sử dụng đối tƣợng gần điểm trung bình nhất làm tâm. Không giống nhƣ thuật toán K-Means và K- Medoid, thuật toán EM sử dụng điểm trung bình và ma trận hệ số kích thƣớc d*d biểu diễn mỗi cụm. Thay thế cho việc kết gán mỗi đối tƣợng tới một tâm duy nhất, thuật toán EM kết gán mỗi đối tƣợng tới một cụm theo một xác xuất đƣợc tính toán từ phân bố của mỗi cụm.

Mặc dù các thuật toán phân cụm khác nhau tạo ra kết quả phân cụm là khác nhau, tuy nhiên ba thuật toán phân hoạch đều có một tiếp cận chung khi tính toán các lời giải của chúng. Thật vậy, quan sát ba thuật toán tìm kiếm K tâm và các phân bố để làm tối ƣu hàm mục tiêu. Một khi đã xác định đƣợc K tâm hay các phân bố tối ƣu, các đối tƣợng trong K cụm đƣợc xác định. Tuy nhiên, để tìm kiếm K tâm hay các phân bố tối ƣu là một bài toán NP-Hard (Garey và Johnson,1979). Do đó, một cách để tìm ra các tâm tối ƣu cục bộ phải dùng phƣơng pháp cập nhật tâm nhiều lần cho đến khi hàm mục tiêu đạt giá trị cực tiểu. Ba thuật toán này có các hàm mục tiêu khác nhau và các cách thực hiện khác nhau đƣợc thể hiện ở bƣớc 3 và 4 của thuật toán A. Một trở ngại của các thuật toán dựa vào hàm mục tiêu là yêu cầu phải biết trƣớc tham số K và chúng không có khả năng để tìm kiếm các cụm theo hình dạng bất kỳ. Chúng ta sẽ xem xét các thuật toán một cách chi tiết hơn.

Thuật toán A :

Input: Số lƣợng cụm K, và một cơ sở dữ liệu chứa N đối tƣợng.

Output: Một tập gồm K cụm thỏa mãn điều kiện cực tiểu hóa hàm mục tiêu

E.

Phƣơng pháp:

1) Khởi tạo chọn ngẫu nhiên K tâm cho lời giải ban đầu.

18

2) Repeat

3) Phân hoạch các đối tƣợng trong cơ sở dữ liệu theo lời giải hiện tại.

4) Cập nhật các tâm theo các đối tƣợng đã đƣợc phân hoạch ở bƣớc 3

5) Until (E không thay đổi);

Thuật toán K-Means

Thuật toán K-Means (MacQueue, 1967) sử dụng giá trị trung bình của các đối tƣợng trong một cụm là tâm cụm. Hàm mục tiêu đƣợc sử dụng trong thuật toán là hàm sai số bình phƣơng đƣợc định nghĩa nhƣ sau:

(4)

Với x là một điểm trong không gian biểu diễn các đối tƣợng, và mi là giá

trị trung bình của cụm Ci.

Thuật toán K-Means cơ bản dựa theo cấu trúc của thuật toán A. Trong bƣớc 3 của thuật toán, K-Means gán mỗi đối tƣợng vào trong tâm gần nhất của nó tạo ra tập các cụm mới. Trong bƣớc 4, tất cả các tâm của cụm mới đƣợc tính toán bằng giá trị trung bình của các đối tƣợng trong mỗi cụm. Quá trình này lặp đi lặp lại cho tới khi hàm mục tiêu E không thay đổi.

Thuật toán K-Means là tƣơng đối mềm dẻo và hiệu quả trong việc xử lý các tập dữ liệu lớn bởi vì độ phức tạp tính toán của thuật toán là O(NKt), với N là tổng số các đối tƣợng, K là số lƣợng cụm, và t là số vòng lặp. Thông thƣờng thì K<

Nhƣợc điểm của thuật toán K-Means là sẽ phân cụm tồi khi dữ liệu chứa nhiễu và các phần tử ngoại lại, chỉ cần một số lƣợng nhỏ dữ liệu nhiễu nhƣ thế cũng đã ảnh hƣởng tới giá trị trung bình.

Thuật toán phân cụm K-Medoids

19

Không giống nhƣ thuật toán K-Means và thuật toán EM, thuật toán K- Medoids sử dụng đối tƣợng trong một cụm là tâm cụm đó để thay thế cho việc lấy giá trị trung bình của các đối tƣợng trong một cụm. Điều này làm cho thuật toán K-Medoids tránh đƣợc nhiễu và phần tử ngoại lai. Tuy nhiên, độ phức tạp của thuật toán này cao hơn độ phức tạp của thuật toán K-Means.

Để thực hiện bƣớc 4 trong thuật toán A, thuật toán K-Medoids trƣớc đây nhƣ PAM (Partitioning Around Medoids) (Kaufman & Rousseeuw, 1990) lặp tất cả K tâm và cố gắng thay thế mỗi tâm bởi N-K đối tƣợng còn lại. Với mỗi sự thay thế này, nếu hàm sai số bình phƣơng E giảm, thì sự thay thế đƣợc giữ lại, và vòng lặp tiếp theo của thuật toán A đƣợc thực hiện. Tuy nhiên, nếu không có sự thay thế nào đƣợc tìm thấy sau khi đã thực hiện xong K tâm, tức là không làm giảm hàm E thì thuật toán sẽ kết thúc với nghiệm tối ƣu cục bộ.

Do độ phức tạp lớn nên thuật toán phân hoạch nhƣ PAM chỉ thực hiện hiệu quả đối với các tập dữ liệu nhỏ, không phù hợp với các tập dữ liệu lớn. Để thực hiện với các tập dữ liệu lớn, phƣơng pháp phân cụm dựa trên mẫu (Sampling – based method) là CLARA (Clustering LARge Applications) đã đƣợc phát triển bởi Kaufman & Rousseeuw. Thuật toán chọn một phần của dữ liệu thực làm mẫu thay cho việc xem toàn bộ tập dữ liệu. Các tâm đƣợc chọn từ các mẫu sử dụng thuật toán PAM và độ bất tƣơng đồng trung bình đƣợc tính cho toàn bộ tập dữ liệu. Nếu có một tập các tâm mới có độ bất tƣơng đồng thấp hơn lời giải tốt nhất trƣớc đó, thì lời giải tốt nhất đƣợc thay thế bởi tập tâm mới này, chi tiết thuật toán xem ở.

1.2.2. Các phương pháp phân cụm phân cấp

Phƣơng pháp phân cụm này tạo ra đồ thị dữ liệu. Cấu trúc của các đồ thị

đƣợc thực hiện theo hai cách: bottom-up và top-down.

Trong mô hình bottom-up, chúng ta xét từng mẫu nhƣ là cụm đơn lẻ và

sau đó lần lƣợt kết hợp các cụm gần nhất. Qua từng lƣợt của thuật toán, chúng ta

kết hợp hai cụm gần nhất. Quá trình đƣợc lặp lại cho đến khi chúng ta lấy đƣợc

tập dữ liệu riêng biệt hoặc xác định chắc chắn giá trị ngƣỡng.

Phƣơng pháp top-down, làm việc theo cách ngƣợc lại mô hình bottom-up:

chúng ta bắt đầu bằng việc xét toàn bộ các tập nhƣ là cụm đơn và phân chia

chúng vào các cụm nhỏ hơn. Xét về bản chất, những phƣơng thức này thƣờng

không có khả năng tính toán, và có thể có ngoại lệ với các mẫu có giá trị nhị

20

phân.

Kết quả của phân cụm phân cấp thƣờng đƣợc biểu diễn theo dạng biểu đồ

hình cây. Tỉ lệ khoảng cách đƣợc biểu diễn ở phía bên phải của đồ thị giúp

chúng ta xác định khoảng cách giữa các cụm. Chúng đƣa đến một tiêu chuẩn

đơn giản: đƣa ra giá trị ngƣỡng khoảng cách chắc chắn, chúng ta dừng việc kết

hợp các cụm khi khoảng cách giữa chúng vƣợt quá ngƣỡng này, có nghĩa là kết

hợp 2 cấu trúc riêng biệt dƣờng nhƣ không khả thi.

Hình 1.3 Biểu đồ biểu diễn các mẫu trong phân cụm phân cấp

Một vấn đề quan trọng là làm thế nào để đo khoảng cách giữa hai cụm. Ở

đây, mỗi cụm có thể chứa nhiều mẫu, tính toán khoảng cách không phải là hiển

nhiên hay duy nhất. Coi 2 cụm, A và B minh họa trong hình 1.4, khoảng cách

giữa 2 cụm đƣợc kí hiệu d(A,B) và số lƣợng mẫu của A và B tƣơng ứng kí hiệu

là n1 và n2. Nhìn bằng mắt, chúng ta có thể dễ dàng hình dung ra ba cách tính

21

toán khoảng cách giữa hai cụm

Hình 1.4 Ba cách tính khoảng cách giữa hai cụm

(a) Liên kết đơn, (b) liên kết đầy đủ, (c) liên kết trung bình cụm

Phƣơng thức liên kết đơn. Khoảng cách d(A,B) đƣợc tính dựa trên khoảng

cách nhỏ nhất giữa các mẫu của A và B. Nó đƣợc tính theo công thức sau:

Phƣơng thức liên kết đầy đủ. Phƣơng thức này tính toán dựa trên khoảng

cách của hai mẫu xa nhất của hai cụm

Phƣơng thức liên kết trung bình cụm. Khoảng cách đƣợc xác định dựa

vào các giá trị của hàm khoảng cách, phƣơng thức này xét giá trị trung bình của những khoảng cách đã đƣợc tính toán giữa tất cả các cặp mẫu của các cụm

Các thuật toán phân cụm trƣớc đây theo phƣơng pháp phân cấp nhƣ AGNES và DIANA (Kaufman & Rousseeuw, 1990) thƣờng phải sử dụng các hàm đánh giá đơn giản để tách hoặc trộn các cụm. Thực tế thì các bƣớc trộn hoặc tách là không thuận nghịch, do đó các phƣơng pháp đƣa ra thƣờng cho kết quả phân cụm sai.

22

Để nâng cao hiệu quả của thuật toán theo phân cấp, các phƣơng pháp gần đây cố gắng theo một trong hai tiếp cận sau đây. Tiếp cận đầu tiên đƣợc trình bày bởi các thuật toán nhƣ CURE (Guha et al., 1998) và CHAMELEON

(Karypis et al., 1999) sử dụng các quy tắc phức tạp hơn khi tách hoặc trộn các cụm. Mặc dù việc tách hoặc trộn các cụm vẫn không thuận nghịch trong tiếp cận này, nhƣng các lỗi tạo ra là rất ít bởi vì đây là một phƣơng pháp tốt hơn đƣợc sử dụng để trộn và tách. Tiếp cận thứ hai đƣợc biểu diễn bởi các thuật toán nhƣ BIRCH (Zhang et all., 1996) là để xác định kết quả ban đầu bằng cách sử dụng thuật toán “vun đống” và sau đó sử dụng lặp tìm vị trí tâm để làm mịn kết quả.

Thuật toán BIRCH: Balanced Iterative Reducing and Clustering using

Hierarchies

BIRCH là một phƣơng pháp phân cụm phân cấp theo “Bottom - Up”. Tƣ tƣởng chính của BIRCH là nén các đối tƣợng dữ liệu vào trong các cụm con và sau đó thực hiện phân cụm với các cụm con này. Để trộn các cụm con, số lƣợng các cụm phải bé hơn hoặc bằng số lƣợng đối tƣợng dữ liệu và do đó cho phép quá trình phân cụm thực hiện trong bộ nhớ trong. Các kết quả trong thuật toán chỉ cần quét qua cơ sở dữ liệu một lần.

Trong thuật toán BIRCH, mỗi một cụm con đƣợc biểu diễn bởi đặc trƣng của cụm đó là bộ ba mô tả tóm tắt thông tin về nhóm các đối tƣợng trong cụm đó. Cho N đối tƣợng {Xi} trong không gian d chiều. Một cụm của một cụm con đƣợc định nghĩa là:

Trong đó, N là số lƣợng các đối tƣợng trong một cụm, là tổng

của N điểm và là tổng bình phƣơng của N điểm dữ liệu.

23

Các CF này đƣợc lƣu trong cây đặc trƣng cụm (Clustering feature tree: CF tree), đƣợc sử dụng để mô tả tóm tắt cụm. Cây CF đƣợc gọi là cây cân bằng theo độ cao nếu cây đó chứa các CF cho thuật toán phân cụm theo phân cấp. Các đỉnh không phải là lá lƣu các tổng các CF của các đỉnh còn lại và do đó, mô tả tóm tắt thông tin phân cụm về các đỉnh con của chúng. Một cây CF có hai tham số: Nhân tố nhánh B, và ngƣỡng T. Nhân tố nhánh là số lƣợng cực đại các đỉnh con mà một đỉnh trong có thể có. Tham số ngƣỡng là đƣờng kính tối đa của các

cụm con đƣợc lƣu trữ tại mỗi đỉnh lá của cây. Hai tham số này ảnh hƣởng đển cỡ của cây kết quả.

Cây CF đƣợc xây dựng một cách tự động theo cách các đối tƣợng đƣợc chèn vào. Một đối tƣợng đƣợc chèn vào một lá gần nhất (Cụm con). Nếu đƣờng kính của một cụm con đƣợc lƣu trữ trong đỉnh lá sau khi chèn lớn hơn giá trị ngƣỡng thì sau đó đỉnh lá này và có thể có các đỉnh khác sẽ đƣợc tách. Sau khi chèn một đối tƣợng mới, thông tin đƣợc truyền về gốc của cây. Cỡ của cây có thể bị thay đổi bằng cách thay đổi giá trị ngƣỡng. Nếu giá trị ngƣỡng tạo ra cây CF không lƣu đƣợc trong bộ nhớ trong thì giá trị ngƣỡng đƣợc tăng lên và cây CF đƣợc xây dựng lại mà không cần thiết đọc lại tất cả các đối tƣợng trong cơ sở dữ liệu. Sau khi cây CF đƣợc xây dựng, một thuật toán phân cụm bất kỳ, nhƣ các thuật toán phân cụm theo phân hoạch đƣợc sử dụng để thực hiện quá trình phân cụm trong bộ nhớ trong. Để cải tiến chất lƣợng phân cụm hơn nữa, một hoặc nhiều lần quét cơ sở dữ liệu có thể đƣợc thực hiện. Độ phức tạp thuật toán là O(N), với N là số lƣợng đối tƣợng đƣợc phân cụm.

Các kết quả thực hiện cho thấy thuật toán có tính mềm dẻo đối với số lƣợng các đối tƣợng, và chất lƣợng phân cụm là tốt. Tuy nhiên, khi một đỉnh trong cây CF chỉ thỏa mãn về giới hạn số lƣợng các đối tƣợng theo kích thƣớc của nó, một đỉnh không phải luôn luôn tƣơng ứng với một cụm thực mang tính tự nhiên nhƣ ngƣời sử dụng mong muốn. Hơn nữa, nếu các cụm không phải có hình dạng là hình cầu, BIRCH không thực hiện tốt bởi vì nó sử dụng khái niệm bán kính hoặc đƣờng kính để điều khiển giới hạn của một cụm.

Thuật toán CURE: Clustering Using Representatives

Không giống các phƣơng pháp vun đống truyền thống nhƣ AGNES, CURE là một phƣơng pháp vun đống sử dụng quy tắc phức tạp để trộn các cụm.

24

Có hai ý tƣởng chính mà CURE sử dụng để đạt đƣợc các cụm có chất lƣợng cao. Đầu tiên, thay cho việc sử dụng các tâm hoặc các đối tƣợng để biểu diễn tâm một cụm, số lƣợng các đối tƣợng xác định đƣợc lựa chọn để biểu diễn mỗi cụm. Thứ hai, các đối tƣợng đƣợc lựa chọn để biểu diễn cụm đƣợc co tới các tâm của cụm bằng nhân tố co nằm trong đoạn [0,1].

Các điểm đại diện gần nhau nhất

Trộn

Tại mỗi bƣớc của thuật toán, hai cụm có các cặp biểu diễn các cụm gần nhau nhất đƣợc trộn vào với nhau. Tiếp cận này cho phép CURE điều chỉnh tốt hình dạng của các cụm không phải là hình cầu. Các cụm co trợ giúp loại bỏ ảnh hƣởng của các phần tử ngoại lai. Do đó, CURE là một thuật toán mạnh tránh đƣợc các phần tử ngoại lai và nhận ra các cụm không phải là hình cầu và có cỡ tùy ý. Nó mềm dẻo đối với các cơ sở dữ liệu lớn mà không ảnh hƣởng với chất lƣợng cụm. Hình 1.5 biểu diễn quá trình trộn hai cum con với nhau theo CURE và việc co các điểm dữ liệu tới tâm cụm đƣợc tạo ra. Các điểm đen ở trong hình là các điểm đƣợc chọn để biểu diễn mỗi cụm con.

Hình 1.5 Trộn 2 cụm theo thuật toán CURE

1.2.3. Các phương pháp dựa vào mật độ

Hầu hết các phƣơng pháp phân cụm dựa trên hàm mục tiêu truyền thống phân cụm đều dựa trên khoảng cách giữa các đối tƣợng. Các phƣơng pháp này chủ yếu tìm ra các cụm có dạng hình cầu và rất khó để tìm ra các cụm có hình dạng ngẫu nhiên. Phƣơng pháp phân cụm dựa vào mật độ xem các cụm nhƣ là các vùng có mật độ các đổi tƣợng lớn trong không gian dữ liệu. Các phƣơng pháp dựa vào mật độ có thể sử dụng để loại bỏ nhiễu, và phát hiện ra các cụm có hình dạng ngẫu nhiên.

25

Thuật toán dựa vào mật độ đầu tiên là thuật toán DBSCAN (Ester và cộng sự, 1996), thuật toán này xem xét mật độ theo lân cận của mỗi đối tƣợng, nếu số lƣợng các đối tƣợng trong khoảng cách của một đối tƣợng lớn hơn MinPts thì đối tƣợng đó đƣợc xem là nằm trong một cụm. Bởi vì các cụm tìm đƣợc phụ

và MinPts, nên thuật toán DBSCAN dựa trên khả năng của

thuộc vào tham số ngƣời sử dụng để lựa chọn tập tham số tốt.

Để tránh đƣợc vấn đề này, năm 1999 Ankerst đề xuất phƣơng pháp sắp xếp các cụm đƣợc gọi là OPTICS. OPTICS tính toán việc sắp xếp các cụm có tham số để phân cụm tự động.

DBSCAN: phương pháp phân cụm dựa trên mật độ của các vùng được

liên kết với mật độ đủ lớn

DBSCAN là một thuật toán phân cụm dựa vào mật độ. Thuật toán nhóm các vùng có mật độ đủ cao vào trong các cụm, và tìm kiếm các cụm với hình dạng tự nhiên trong các tập dữ liệu không gian. Thuật toán yêu cầu 2 tham số đầu vào là của một và Minpts. Các đối tƣợng nằm trong hình cầu bán kính -lận cận của đối tƣợng đó và và đối tƣợng có ít nhất là đối tƣợng đƣợc gọi là Minpts đối tƣợng khác là -lân cận thì đƣợc gọi là đối tƣợng lõi (Core Object). Phân cụm dữ liệu theo thuật toán DBSCAN áp dụng các luật sau đây:

- Một đối tƣợng có thể nằm trong một cụm nếu và chỉ nếu nó nằm trong

-lân cận của một đối tƣợng lõi thuộc cụm đó.

- Một đối tƣợng lõi o nằm thuộc -lân cận của một đối tƣợng lõi p khác

thì o bắt buộc phải nằm cùng một cụm với p.

- Một đối tƣợng không lõi q nằm trong

-lân cận của các đối tƣợng p1,…, pi, i>0, thì q phải nằm cùng một cụm chứa ít nhất một đói tƣợng lõi thuộc p1,…, pi.

- Một đối tƣợng không lõi r không nằm thuộc -lân cận của một đối

tƣợng lõi bất kỳ thì đƣợc xem là nhiễu.

Ví dụ: Xem xét hình 1.6 dƣới đây với

26

là bán kính của hình tròn và Minpts =3. Chúng ta biểu diễn các đối tƣợng lõi là các điểm hình tròn, còn các đối tƣợng không lõi là các điểm có dạng hình tròn. Trong hình 1.6 biểu diễn hai cụm, C1 và C2 đƣợc tìm kiếm bởi thuật toán DBSCAN. Các đối tƣợng dữ liệu - lân cận của ít nhất một đối tƣợng lõi nằm nằm trong C1 hoặc C2 đều thuộc trong C1 hoặc C2 và không có hai đối tƣợng lõi nào thỏa mãn thuộc -lân cận của nhau và do đó chúng có thể năm ở các cụm khác nhau. Đối tƣợng không lõi

-lân cận của T và R, với T là đối tƣợng lõi thuộc C1 và R là đối M nằm trong tƣợng lõi thuộc C2. Điều này dẫn tới có thể phân M vào C1 hoặc C2 khi nó là biên của hai cụm. Cuối cùng, đối tƣợng S có thể đƣợc xem là nhiễu bởi vì nó là một đối tƣợng không lõi và không thuộc -lân cận của các đối tƣợng lõi.

Hình 1.6 Hai cụm đƣợc tìm bởi thuật toán DBSCAN

Để tìm kiếm các cụm , DBSCAN kiểm tra

- lân cận của mỗi đối tƣợng -lân cận của một điểm p chứa nhiều hơn MinPts, một trong cơ sở dữ liệu. Nếu -lân cận của p cụm mới với p là đối tƣợng lõi đƣợc tạo ra. Các đối tƣợng trong đƣợc phân vào cụm mới này. Các đối tƣợng lõi trong lân cận này sẽ đƣợc xử lý tƣợng tự nhƣ p và điều này làm cho kích thƣớc của cụm tăng lên. Khi không còn đối tƣợng lõi để xử lý, các đối tƣợng lõi khác trong cơ sở dữ liệu sẽ đƣợc tìm kiếm và tạo nên một cụm mới khác. Chú ý rằng trong quá trình làm tăng kích thƣớc của cụm theo thuật toán DBSCAN, một đối tƣợng lõi đã nằm trong một cụm khác có thể tiếp tục bị phân cụm và kết quả là làm trộn hai cụm với nhau. Quá trình kết thúc khi không có điểm nào đƣợc phân vào các cụm.

OPTICS: Ordering Point To Identify the Clustering Structure

Mặc dù thuật toán DBSCAN có thể tìm kiếm các cụm với hình dạng tự

nhiên trong tập dữ liệu chứa nhiễu, nó cũng bị ảnh hƣởng rất lớn bởi hai tham số

là và MinPts. Để tìm kiếm các cụm đƣợc xem là chấp nhận đƣợc, ngƣời sử

27

dụng có thể chạy thuật toán này nhiều lần trong các tập giá trị khác nhau của hai

tham số. Nếu không có một hƣớng dẫn nào để lựa chọn hai tham số này thì tổng

thời gian thực hiện có thể là rất lớn và dẫn đến không khả thi.

Để khắc phục khó khăn này, phƣơng pháp xếp loại một cụm đƣợc gọi là

OPTICS (Ordering Point To Identify the Clustering Structure) đã đƣợc đề xuất.

Cũng giống nhƣ thuật toán DBSCAN, thuật toán OPTICS yếu cầu hai tham số

đầu vào là và MinPts. Tuy nhiên, thay cho việc tạo ra kết quả phân cụm của

một cặp giá trị của hai tham số này, thuật toán OPTICS một dãy các điểm dữ

liệu có thứ tự là kết quả của việc phân cụm với giá trị thấp hơn và với cùng

một giá trị của MinPts có thể dễ dàng xác định và tính toán.

Bằng cách kiểm tra thuật toán DBSCAN, có thể dễ dàng thấy rằng mới

một hằng số MinPts, giảm tới giá trị mới ’ sẽ tạo ra hai tác động:

Một đối tƣợng lõi có thể trở thành không lõi bởi vì nó không có ít nhất

MinPts đối tƣợng trong ’- lân cận của nó.

Một đối tƣợng không lõi ban đầu trong -lân cận của một số đối tƣợng lõi

có thể trở thành nhiễu bởi vì chúng không nằm trong ’- lân cận của các đối

tƣợng lõi hoặc bởi vì các đối tƣợng lõi này đã trở thành các đối tƣợng không

phải là lõi.

Do đó có thể thấy rằng, hai tác động này sẽ tạo ra kết quả tập các cụm mà

các tập này nằm hoàn toàn trong các tập các cụm đƣợc tìm thấy với giá trị cao

hơn. Do đó, để tạo ra một tập các cụm đƣợc sắp xếp, chỉ cần lƣu các giá trị

ngƣỡng cho mỗi đối tƣợng dữ liệu thỏa mãn tự động của một giá trị nào đó.

Các giá trị cần đƣợc lƣu là khoảng cách lõi và khoảng đạt đƣợc:

Khoảng cách lõi của một đối tƣợng p ký hiệu là core(p) là khoảng cách

nhỏ nhất thỏa mãn core(p)-lân cận chứa đúng MinPts đối tƣợng. Nếu p không là

28

đối tƣợng lõi với ban đầu thì khoảng cách lõi của p không xác định.

Khoảng cách đạt đƣợc của đối tƣợng p đối với đối tƣợng o, ký hiệu là

reach(o,p) là khoảng cách nhỏ nhất thỏa mãn p nằm trong reach(o,p)-lân cận của

o và o còn là đối tƣợng lõi đối với reach(o,p). Nếu o không là đối tƣợng lõi với

, thì reach(o,p) không xác định.

Thuật toán OPTICS tạo ra một thứ tự các đối tƣợng trong cơ sở dữ liệu,

ngoài ra còn lƣu khoảng cách lõi và khoảng cách đạt đƣợc phù hợp cho mỗi đối

tƣợng. Những thông tin này đủ để tìm kiếm tất cả các cụm với ’ bất kỳ nhỏ

hơn đƣợc sử dụng để xếp loại.

Xếp phân cụm cho một tập dữ liệu có thể đƣợc biểu diễn bởi đồ họa, điều

này trở giúp cho chúng ta có thể hiểu hơn về cụm. Ví dụ, trong hình 1.6 là biểu

đồ cho tập dữ liệu 2 chiều, biểu đồ biểu diễn tổng quan về dữ liệu và các cụm

của chúng. Đã có mốt số phƣơng pháp đƣợc phát triển để hiển thị các cấu trúc

cụm trong không gian nhiều chiều.

Hình 1.7 Thứ tự cụm theo OPTICS

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

29

Các phƣơng pháp phân cụm dựa vào mật độ nhƣ DBSCAN, OPTICS có thể sẽ thất bại trong không gian dữ liệu với số chiều cao và phải thiết lập các

tham số và MinPts. Để nâng cao hiệu quả của phân cụm, tiếp cận phân cụm dựa trên lƣới sử dụng cấu trúc dữ liệu dạng lƣới. Tiếp cận này phân chia không gian dữ liệu vào một số lƣợng hữu hạn các ô tạo nên dạng hình lƣới. Tiện lợi chính của tiếp cận này là thời gian xử lý nhanh và nó không phụ thuộc vào số lƣợng các đối tƣợng dữ liệu, chỉ phụ thuộc vào số lƣợng các ô ở mỗi chiều trong không gian lƣợng hóa.

Một số thuật toán cơ bản của tiếp cận dựa trên lƣới là thuật toán STING, thuật toán này tìm kiếm theo thống kê các thông tin nằm trong các ô. Thuật toán WaveCluster phân cụm dữ liệu sử dụng phƣơng pháp biến đổi sóng và thuật toán CLIQUE trình bày cách tiếp cận dựa vào mật độ và dựa vào lƣới để phân cụm dữ liệu nằm trong không gian với số chiều lớn.

STING: A STatistical INformation Grid approach

STING là một cấu trúc dữ liệu đa mức dựa trên lƣới, trong không gian dữ

liệu đƣợc chia thành các ô hình chữ nhật. Có các ô tƣơng ứng với các mức khác

nhau để giải quyết bài toán, cách phân chia ô nhƣ vậy tạo ra một cấu trúc phân

cấp: mỗi ô ở mức cao đƣợc phân chia thành một số ô ở mức thấp hơn tiếp theo.

Thông tin thống kê liên quan tới thuộc tính của mỗi ô nhƣ mean, maximum,

minimum đƣợc tính toán trƣớc và lƣu trữ. Những thông tin thông kê này sẽ trợ

giúp cho quá trình truy vấn nhƣ sau:

Hình 1.8 Ba tầng liên tiếp nhau của cấu trúc STING

Trong hình 1.8 trình bày 3 tầng liên tiếp nhau của cấu trúc STING, mỗi ô

30

ở tầng trên đƣợc phân chia thành bốn ô ở tầng tiếp theo. Các tham số thống kê ở

mức cao có thể đƣợc dễ dàng tính toán bởi các tham số từ các ô ở mức thấp hơn.

Các tham số này bao gồm: số lƣợng đối tƣợng trong ô: count; giá trị trung bình:

mean; độ lệch chuẩn: s; giá trị nhỏ nhất của thuộc tính của các đối tƣợng trong

ô: min; giá trị lớn nhất của thuộc tính của các đối tƣợng trong ô: max và kiểu

phân bố trong các ô. Dữ liệu đƣợc đƣa vào trong cấu trúc lƣới bắt đầu từ mức

thấp nhất. Các tham số count, m, s, min, max ở mức này đƣợc tính toán trực tiếp

từ dữ liệu. Giá trị của phân bố có thể đƣợc đặt bởi ngƣời sử dụng. Kiểu phân bố

ở ô mức cao đƣợc tính toán dựa trên các kiểu phân bố ở các ô tƣơng ứng ở mức

thấp kề nó theo một ngƣỡng cho trƣớc. Nếu các phân bố ở mức thấp giống nhau

và bị lỗi khi kiểm tra bởi ngƣỡng, kiểu phân bố ở ô mức cao sẽ là không xác

định (đƣợc đặt là none).

Để thực hiện phân cụm trên cấu trúc lƣới, ngƣời sử dụng cung cấp mật độ

ở các ô nhƣ là tham số đầu vào. Sử dụng tham số này, áp dụng tiếp cận Top-

down, phƣơng pháp dựa trên lƣới tìm các vùng có mật độ chấp nhận đƣợc bằng

việc thực hiện các thao tác sau:

Một tầng với cấu trúc phân cấp đƣợc xác định để thực hiện tiến trình trả

lời truy vấn. Tầng này bao gồm một số lƣợng nhỏ các ô. Với mỗi ô trong tầng,

tính khoảng chắc chắn mà các ô trong đó sẽ trở thành một cụm. Các ô không

chắc chắn sẽ bị loại bỏ.

Các ô thỏa mãn truy vấn đƣợc tinh chỉnh lại bằng cách lặp lại thủ tục tại

mức tiếp theo của cấu trúc.

Tiến trình này đƣợc lặp lại cho đến khi mức cuối cùng đƣợc tìm thấy. Tại

đó, nếu truy vấn xác định đƣợc kết quả, các vùng chứa các ô thích hợp thỏa mãn

truy vấn đƣợc trả về. Trƣờng hợp khác, dữ liệu rơi vào các ô thích hợp đƣợc

khôi phục lại, và tiến trình tiếp theo đƣợc thực hiện cho đến khi chúng gặp các

31

yêu cầu của truy vấn.

CLIQUE : Phân cụm với dữ liệu đa chiều

Thuật toán CLIQUE tích hợp cả hai phƣơng pháp phân cụm dựa trên mật

độ và trên lƣới. CLIQUE tìm kiếm các cụm trong không gian con của dữ liệu.

Nó đƣợc sử dụng rộng rãi để phân cụm dữ liệu đa chiều phân bố thƣa thớt và

khó nhận ra các cụm trong không gian nhiều chiều này.

Trong thuật toán CLIQUE, không gian dữ liệu đƣợc chia thành các khối

chữ nhật không chồng nhau lên bằng phân đoạn dọc theo mỗi chiều. Một khối là

dày đặc nếu nó có số lƣợng các điểm dữ liệu bao gồm nó vƣợt quá thông số vào

của mô hình. Một cụm đƣợc định nghĩa là một tập lớn nhất của các khối dày đặc

liên kết với nhau.

CLIQUE thực hiện phân cụm dữ liệu nhiều chiều bằng di chuyển từ

không gian ít chiều tới không gian nhiều chiều hơn. Khi tìm các khối có mật độ

dày đặc tại vùng k-chiều, CLIQUE sử dụng thông tin phân cụm đạt đƣợc từ

vùng (k-1)-chiều để làm giảm quá trình tìm kiếm không cần thiết. Điều này

đƣợc thực hiện bằng cách quan sát thông tin tiên nghiệm đƣợc sử dụng trong

khám phá luật kết hợp (Argawal & Srikant, 1994). Việc sử dụng thông tin biết

trƣớc này nhằm làm giảm quá trình tìm kiếm trong không gian tìm kiếm. Áp

dụng tính chất này vào thuật toán QLIQUE có thể phát biểu nhƣ sau:

Nếu một khối k-chiều là dày đặc thì đó là các ánh xạ của chúng trong

không gian (k-1)-chiều. Điều đó có nghĩa: một khối đƣợc xem là mật độ dày đặc

trong k-chiều, nếu chúng ta kiểm tra các khối ánh xạ của nó trong không gian

(k-1) chiều hình thành các khối và tìm xem nếu có bất kỳ một khối nào thƣa thì

32

chúng ta biết rằng khối trong không gian k-chiều sẽ không dày đặc.

Hình 1.9 CLIQUE xác định các vùng tiềm năng dựa trên các đơn vị dày đặc

Thuật toán CLIQUE đƣợc minh họa trong hình 1.9. Thông thƣờng, kết

quả vùng tìm kiếm là nhỏ hơn so với vùng ban đầu. Các khối dày đặc đại diện

để xác định các cụm.

Điều kiện tìm ra các cụm, thuật toán CLIQUE mô tả thông tin tối thiểu về

các cụm nhƣ sau:

Với mỗi cụm, nó xác định vùng lớn nhất phủ các khối liên kết dày đặc.

Sau đó nó xác định một phủ tối thiểu cho mỗi cụm.

CLIQUE tự động tìm các không gian con của không gian có số chiều cao

nhất thỏa mãn các cụm mật độ cao tồn tại trong các không gian con. Nó sẽ

không nhạy cảm với thứ tự của các điểm dữ liệu và phân bố dữ liệu. Thuật toán

phân chia tuyến tính với cỡ của dữ liệu vào và có thang chia tốt theo số chiều

khi số lƣợng dữ liệu tăng. Tuy nhiên, tính chính xác của các cụm kết quả có thể

33

giảm tại tính đơn giản hóa của phƣơng pháp.

CHƢƠNG 2: LÝ THUYẾT TẬP THÔ

Tập thô đƣợc Zdzislaw Pawlak (một nhà toán học và khoa học máy tính ngƣời Ba Lan) đề xuất năm 1982, với ý tƣởng coi nó là công cụ toán học để đối phó với các khái niệm mơ hồ, nó đƣợc phát triển từ giả định là để định nghĩa một tập hợp ta cần phải biết một số thông tin (hay tri thức) về các phần tử của tập, không giống nhƣ định nghĩa tập hợp trƣớc đây (Georg Cantor, ngƣời đƣợc coi là ông tổ của lý thuyết tập hợp đã đƣa ra là để định nghĩa tập hợp, cách duy nhất là dựa trên các phần tử của tập đó và không cần thông tin về các phần tử của tập hợp). Đối với một số phần tử, thông tin của chúng có thể tƣơng tự nhau, do đó các phần tử này không thể phân biệt đƣợc một cách rõ ràng. Quan hệ không phân biệt đƣợc là điểm khởi đầu của lý thuyết tập thô. Quan hệ này chỉ ra sự mập mờ và không chắc chắn, có quan hệ chặt chẽ với tính không phân biệt đƣợc.

Hình 2.1: Hình minh họa khái niệm tập thô

2.1 Hệ thông tin và hệ quyết định

34

Một tập dữ liệu về các loại đối tƣợng đƣợc biểu diễn dƣới dạng một bảng, trong đó mỗi dòng biểu diễn một đối tƣợng (có thể là một sự vật, một ngƣời, một tình huống,…). Mỗi cột biểu diễn một thuộc tính (một biến, một quan sát,

một đặc tính,…) của đối tƣợng, thuộc tính này có thể đo đƣợc cho mỗi đối tƣợng, thuộc tính cũng có thể do chuyên gia hoặc ngƣời sử dụng cung cấp. Bảng này đƣợc gọi là hệ thông tin.

Định nghĩa Hệ thông tin:

Hệ thông tin là một cặp I=(U,A), trong đó U là một tập hữu hạn không rỗng các đối tƣợng đƣợc gọi là tập vũ trụ và A là một tập hữu hạn không rỗng

các thuộc tính mà a:UVa với aA, các thuộc tính này đƣợc gọi là các thuộc tính điều kiện. Tập Va đƣợc gọi là tập giá trị của a.

Ví dụ:

Tiếng Anh Tiếng Pháp Tin học

t1 Trình độ A Trình độ B Trình độ A

t2 Trình độ B Trình độ A Trình độ C

t3 Trình độ A Trình độ B Trình độ A

t4 Trình độ B Trình độ C Trình độ C

t5 Trình độ C Trình độ A Trình độ C

t6 Trình độ A Trình độ B Trình độ A

Bảng 2.1 Ví dụ hệ thông tin

Trong ví dụ trên, ta thấy các thuộc tính điều kiện của các đối tƣợng {t1,t3,t6} có cùng giá trị, những đối tƣợng này không phân biệt đƣợc với nhau dựa trên giá trị của các thuộc tính cho trƣớc đó.

35

Trong nhiều ứng dụng các đối tƣợng đã đƣợc phân lớp trƣớc. Tri thức về lớp của các đối tƣợng này đƣợc biểu diễn bằng một thuộc tính khác đƣợc gọi là thuộc tính quyết định. Hệ thông tin loại này đƣợc gọi là hệ quyết định

Định nghĩa Hệ quyết định

Một hệ quyết định là một hệ thông tin đƣợc biểu diễn dƣới dạng

I=(U,A{d}), trong đó A là tập thuộc tính điều kiện, dA là thuộc tính quyết

định.

Các phần tử của A đƣợc gọi là các thuộc tính điều kiện hoặc có thể gọi tắt là các điều kiện. Miền giá trị của thuộc tính quyết định có thể chứa nhiều giá trị khác nhau nhƣng trong hầu hết bài toán thực tế, miền này thƣờng chỉ có hai giá trị

Ví dụ:

Tiếng Anh Tiếng Pháp Tin học Tuyển dụng

t1 Trình độ A Trình độ B Trình độ A Không

t2 Trình độ B Trình độ A Trình độ C Có

t3 Trình độ A Trình độ B Trình độ A Có

t4 Trình độ B Trình độ C Trình độ C Có

t5 Trình độ C Trình độ A Trình độ C Không

t6 Trình độ A Trình độ B Trình độ A Không

Bảng 2.2 Ví dụ về hệ quyết định

Trong bảng trên, các thuộc tính điều kiện của các đối tƣợng {t1,t3} có cùng giá trị nhƣng giá trị của thuộc tính quyết định “Tuyển dụng” lại khác nhau.

2.2 Tính không phân biệt được (Indiscernibility)

36

Một hệ quyết định biểu diễn toàn bộ tri thức của mô hình, hệ này không nhất thiết phải có kích thƣớc lớn vì các dữ liệu trong đó có thể dƣ thừa nhƣ: các đối tƣợng giống nhau hoặc không phân biệt đƣợc có thể xuất hiện nhiều lần, hoặc một số thuộc tính có thể không cần thiết. Để thể hiện tính không phân biệt đƣợc cho các đối tƣợng, ta tìm hiểu một số khái niệm liên quan

Định nghĩa Quan hệ tương đương:

Quan hệ tƣơng đƣơng là một quan hệ hai ngôi RXY có tính phản xạ,

tính đối xứng và tính bắc cầu.

Định nghĩa lớp tương đương

Lớp tƣơng đƣơng của một phần tử xX là tập tất cả các đối tƣợng yX

mà xy

Định nghĩa Quan hệ không phân biệt được

Gọi I=(U,A) là một hệ thống thông tin, với mỗi tập con các thuộc tính

BA, tồn tại một quan hệ tƣơng đƣơng INDA(B):

Trong đó a(x) là giá trị trên thuộc tính a của đối tƣợng x.

INDA(B) đƣợc gọi là quan hệ B_không phân biệt được

Nếu (x,x’) INDA(B), khi đó đối tƣợng x và x’ là không phân biệt với nhau thông qua các thuộc tính trong B. Các lớp tƣơng đƣơng của quan hệ B- _không phân biệt được ký hiệu là [x]B. Trong thực thế, ngƣời ta có thể không viết ký hiệu tập A trong quan hệ tƣơng đƣơng nếu chỉ xét trên một hệ thống thông tin.

Ví dụ: Từ bảng 1.1, ta có thể có các lớp tƣơng đƣơng của quan hệ không

phân biệt đƣợc nhƣ sau:

IND({Tiếng Anh})={{t1,t3,t6},{t2,t4},{t5}}

IND({Tiếng Anh, Tiếng Pháp})={{t1,t3,t6},{t2},{t4},{t5}}

IND({Tiếng Anh, Tin học})={{t1,t3,t6},{t2,t4},{t5}}

IND({Tiếng Pháp, Tin học})={{t1,t3,t6},{t2,t5},{t4}}

37

IND({Tiếng Anh, Tiếng Pháp, Tin học})={{t1,t3,t6},{t2},{t4}, {t5}}

2.3 Xấp xỉ tập hợp

Một trong những khái niệm cơ bản và rất quan trọng trong lý thuyết tập thô là xấp xỉ tập hợp. Trong lý thuyết tập thô, ngƣời ta có thể thay thế một tập hợp bằng các xấp xỉ của tập hợp đó dựa trên một số thông tin cho trƣớc với quan hệ không phân biệt.

Định nghĩa Xấp xỉ trên và xấp xỉ dƣới của tập hợp

trong đó: Gọi I=(U,A) là một hệ thống thông tin, với BA và XU. Ta có xấp xỉ U bằng cách sử dụng những thông tin có trong B bằng việc xây dựng các xấp xỉ B- dƣới và B-trên của U, đƣợc ký hiệu là

Các đối tƣợng trong có thể đƣợc phân lớp một cách chắc chắn là thành

chỉ có thể

viên thuộc U dựa trên tri thức B, trong khi đó các đối tƣợng trong đƣợc phân lớp là thành viên không chắc chắn thuộc U dựa trên tri thức B.

Tập đƣợc gọi là vùng B-biên của U chứa những đối

tƣợng không thể đƣợc phân lớp chính xác vào U dựa trên tri thức B.

Tập đƣợc gọi là vùng ngoài B-ngoài của U chứa những đối tƣợng

đƣợc phân lớp một cách chính xác là không thuộc vào U dựa trên tri thức B.

Trong trƣờng hợp , U đƣợc gọi là tập rõ, ngƣợc lại U đƣợc

gọi là tập thô.

Ví dụ: U={u:uX và Tuyển dụng = “Có”}={t2,t3,t4}

U là tập các đối tƣợng đƣợc phân lớp với thuộc tính quyết định Tuyển dụng = có. Nếu ta chỉ sử dụng thuộc tính trình độ Tiếng Anh để tìm những đối tƣợng xấp xỉ của U thì:

B={Tiếng Anh}

Khi đó:

BU={t2,t4}

38

BU={t1,t2,t3,t4,t6}

Một số tính chất của các xấp xỉ tập hợp

1.

2. ,

3.

4.

5. Nếu

6.

7.

8.

9.

10.

11.

Dựa vào ý nghĩa của các xấp xỉ trên và xấp xỉ dƣới, ngƣời ta định nghĩa

bốn lớp cơ bản của các tập thô, hay bốn loại mơ hồ (vagueness):

a, X đƣợc gọi là B - định nghĩa được một cách thô (roughly B -definable)

nếu và chỉ nếu và

b, U đƣợc gọi là B - không định nghĩa được một cách nội vi (internally B

undefinable) nếu và chỉ nếu và

c, U đƣợc gọi là B -không định nghĩa được một cách ngoại vi (externally

B undefinable) nếu và chỉ nếu và

d, U đƣợc gọi là B -không định nghĩa được một cách hoàn toàn (totally B

undefinable) nếu và chỉ nếu và

39

Có thể diễn tả lại các khái niệm trên nhƣ sau:

 U là B -định nghĩa được một cách thô nghĩa là: Nhờ sử dụng tập thuộc tính B ta có thể chỉ ra một số đối tƣợng của X thuộc về tập U và một số đối tƣợng của X thuộc về X -U.

 U là B -không định nghĩa được một cách nội vi nghĩa là: sử dụng tập thuộc tính B ta có thể chỉ ra một số đối tƣợng của X thuộc về X - U, nhƣng lại không thể chỉ ra đƣợc các đối tƣợng thuộc về U.

 U là B - không định nghĩa được một cách ngoại vi nghĩa là : sử dụng tập thuộc tính B ta có thể chỉ ra một số đối tƣợng của X thuộc về U, nhƣng không chỉ ra đƣợc các đối tƣợng thuộc về X-U

 U là B - không định nghĩa được một cách hoàn toàn nghĩa là: sử dụng tập thuộc tính B ta không thể chỉ ra bất kỳ đối tƣợng nào của X thuộc về U hay thuộc về X -U

Một tập thô có thể đƣợc định lƣợng bởi công thức:

đƣợc gọi là độ chính xác của xấp xỉ, trong đó |U | chỉ số phần tử của tập .

Rõ ràng . Nếu thì U là rõ (chính xác) đối với tập thuộc

tính B. Ngƣợc lại, nếu thì U là thô (mơ hồ) đối với tập thuộc tính B.

Dƣới đây là các thuật toán xác định các xấp xỉ trên và xấp xỉ dƣới của một

40

tập đối tƣợng theo một tập thuộc tính cho trƣớc.

Thuật toán xác định xấp xỉ dƣới

Input:

 Tập các đối tƣợng U

 Tập các thuộc tính B

Output:

 Tập các đối tƣợng U

Thuật toán :

Bước 1:

Khởi tạo BU = 

Xác định tập các phân hoạch P tạo bởi B.

Bước 2:

Thực hiện bƣớc 3.

Thực hiện bƣớc 4

U1 = U If (U1≠){ } else{ }

Bước 3:

Xét x  U1 Tìm phân hoạch Pi  P sao cho: x Pi If (Pi  U){ BU = BU  Pi

} U1 = U1 - Pi. Quay lại bƣớc 2.

41

Bước 4: Kết thúc

Thuật toán xác định xấp xỉ trên

Input :

 Tập các đối tƣợng U

 Tập các thuộc tính B

Output:

- Tập các đối tƣợng U

Thuật toán:

Bước 1:

Khởi tạo =

Xác định tập các phân hoạch P tạo bởi B.

Bước 2:

Thực hiện bƣớc 3.

Thực hiện bƣớc 4

U1 = U If (U1 ){ Else { }

Bước 3:

Xét x  U1. Tìm phân hoạch Pi  P sao cho: x  Pi.

For (p  Pi U1){ U1 = U1 - {p}

} Quay lại bƣớc 2.

42

Bước 4: Kết thúc.

CHƢƠNG 3: TẬP THÔ VÀ BÀI TOÁN PHÂN CỤM

Trong chƣơng này, tôi tập trung vào việc nghiên cứu thêm tập mờ, tập

bóng và các bài toán phân cụm: phân cụm thô, phân cụm mờ, phân cụm bóng.

Trong phân cụm dữ liệu, dữ liệu thực thƣờng phân tán, có cấu trúc không rõ ràng và có sự không chắc chắn và chồng chéo giữa các thành phần của cấu trúc (cụm). Trong các thuật toán phân cụm, thuật toán nổi bật và cổ điển là thuật toán K –Means. K-Means là thuật toán nằm trong phƣơng pháp phân cụm phân hoạch. Mặc dù K-Means có hiệu quả, nhƣng tính hiệu quả của nó sẽ giảm khi phân chia với các cụm chồng chéo. Phân cụm mờ, đặc biệt là Fuzzy C-Means (FCM)- phần mở rộng của K -Means, thƣờng đƣợc sử dụng để khám phá cấu trúc của một tập dữ liệu và thông tin để xây dựng hạt nhân. Nó sử dụng một ma trận bộ phận để lƣu trữ điểm thành viên của từng đối tƣợng thuộc mỗi cụm, do đó trƣờng hợp chồng chéo có thể đƣợc mô tả một cách hiệu quả. Thách thức chủ yếu của FCM là các phần tử ngoại lai hay nhiễu.

Gần đây, xét về lý thuyết tập thô, Lingras và West [4] đã giới thiệu phân cụm Rough C -Means (RCM), trong đó mô tả mỗi cụm không chỉ bởi một mẫu, mà còn có một cặp cận trên và dƣới. Các tham số đƣợc sử dụng để đo độ quan trọng của các cận dƣới và vùng biên khi tính cụm mới. RCM có thể đối phó với sự không chắc chắn và không rõ ràng phát sinh trong vùng biên của mỗi cụm (hay nói cách khác là nhiễu và các phần tử ngoại lai).

43

Hai mô hình quan trọng của tính toán hạt nhân (Granular Computing), tập thô và tập mờ đã đƣợc phát triển riêng biệt đáng kể. Liên quan đến điểm thành viên, Mitra [5] đã đƣa ra một phƣơng pháp phân cụm Rough-Fuzzy C-Means (RFCM), đƣợc tích hợp những ƣu điểm của các công nghệ của tập mờ và tập thô. Cận trên và dƣới đƣợc xác định theo điểm thành viên trong ma trận bộ phận chứ không phải là khoảng cách tuyệt đối giữa từng đối tƣợng với các lân cận của nó. Maji [6] tiếp tục chỉ ra rằng các đối tƣợng ở cận dƣới của một cụm nên có tầm quan trọng với cụm đó và các mẫu trong cụm, trọng số của chúng cũng phải độc lập với các mẫu khác khi lặp đi lặp lại các bƣớc tính toán các mẫu mới. Sau

khi đƣa ra khái niệm này, Maji đã sửa đổi các tính toán cho mẫu mới theo phƣơng pháp phân cụm RFCM.

Tập bóng theo khái niệm của Pedrycz [7], đƣợc coi là cầu nối về khái niệm và thuật toán giữa tập thô và tập mờ. Nó là một mô hình mới đang nổi lên của Granular Computing đƣợc sử dụng thành công trong học không giám sát. Năm 2010, Mitra và Perdrycz đã tạo ra thuật toán phân cụm Shadowed C-Means (SCM). Không giống nhƣ FCM, giá trị của các đối tƣợng ở mức core (lõi) của một cụm đƣợc tăng trong SCM. Các giá trị của các đối tƣợng ở mức exclusion (loại trừ) ở một cụm sẽ đƣợc giảm bằng cách tăng hệ số mờ lên mũ 2.

3.1. Phân cụm thô (Rough C-means)

Thuật toán c-means thông thƣờng bắt đầu bằng cách phân vùng N đối tƣợng xk vào C tập con khác rỗng. Trong mỗi phân vùng, các tâm của các cụm đƣợc tính nhƣ sau

(3.1)

Với là số đối tƣợng trong cụm Ui. Quá trình này đƣợc lặp đi lặp lại

cho đến khi hội tụ, có nghĩa là, các đối tƣợng đã thuộc về 1 cụm nào đó.

Phần này sẽ xét giải thuật Rough C-means (RCM), một thuật toán phân cụm phân hoạch của Lingras. Mỗi một tập thô trong RCM đƣợc đặc trƣng bởi

xấp xỉ trên và dƣới là và tƣơng ứng và chúng phải thỏa mãn đƣợc

các tính chất cơ bản sau:

Tính chất 1. Một đối tƣợng có thể thuộc về cận dƣới của nhiều nhất một

cụm.

Tính chất 2. Một đối tƣợng thuộc về cận dƣới của cụm cũng thuộc về cận

trên của cụm đó

Tính chất 3. Một đối tƣợng mà không thuộc về bất cứ cận dƣới nào sẽ

44

thuộc về nhiều hơn một cận trên.

Hình 3.1 Ba vùng của một cụm

Vì phải thỏa mãn 3 tính chất này nên RCM không cho phép có sự chồng

chéo giữa các cụm.

Thuật toán 1. Khái quát hoá tập thô dựa trên thuật toán C-means

Bƣớc 1: Khởi tạo. Gán mẫu ban đầu cho các cụm C;

Bƣớc 2: Xác định các cận dƣới và vùng biên của mỗi cụm;

Bƣớc 3: Cập nhật các mẫu cho các cụm C;

Bƣớc 4: Lặp lại bƣớc 2 và 3 cho đến khi đã đạt tới hội tụ.

Mỗi cụm có cận trên và cận dƣới của riêng mình. Tính toán các mẫu mới sẽ chỉ phụ thuộc lên các đối tƣợng trong hai vùng xấp xỉ, không phải tất cả các đối tƣợng nhƣ trong K -Means, FCM hoặc SCM. Do đó việc sử dụng ít thông tin có thể đƣợc lọc ra và số lƣợng tính toán có thể đƣợc giảm. Trong một cụm cố định, tất cả các đối tƣợng đƣợc chia vào ba vùng, cụ thể là, vùng lõi (Core level), vùng biên (Boundary level) và vùng loại trừ (Exclusion level), nhƣ thể hiện trong hình 3.1.

45

Các đối tƣợng nằm ở vùng lõi chắc chắn thuộc về cụm. Các đối tƣợng ở vùng biên có thể thuộc về cụm. Các đối tƣợng khác thuộc phạm vi vùng loại trừ không thuộc cụm. Sự đóng góp của các đối tƣợng nằm ở các mức khác nhau tới các cụm là khác biệt. Nói chung, các đối tƣợng vùng lõi có mức quan trọng cao nhất trong khi các đối tƣợng ở trong vùng loại trừ gần nhƣ bị bỏ qua. Giả sử đối tƣợng N đƣợc nhóm lại thành C cụm U1, U2, …, UC. Các mẫu tƣơng ứng v1, v2,..., vC, viRn, đƣợc cập nhật theo cách sau.

(3.2)

Với

(3.3)

(3.4)

và kí hiệu cho vùng biên của cụm Ui, với

kí hiệu các cận trên và dƣới của cụm Ui liên quan tƣơng ứng đến tập đặc

điểm R. A1, B1 có thể đƣợc coi là giá trị tƣơng ứng với cận dƣới và vùng biên.

và là trọng số của chúng. Khi cập nhật một mẫu,

wl có giá trị cao hơn thì các cận dƣới quan trọng hơn.

Để xác định các cận dƣới và vùng biên của mỗi cụm, Lingras [4] sử dụng

các quy tắc sau đây:

Nếu , thì và . Trong trƣờng hợp này, xk

không thể thuộc về các cận dƣới của cụm bất kỳ nào. Nếu không, . Ở

đây thể hiện khoảng cách giữa đối tƣợng và mẫu vi(i=1,2,…C).

và là hai khoảng cách tối thiểu của uk trên tất cả các cụm.

Khoảng cách Euclide đƣợc sử dụng, với công thức nhƣ sau:

(3.5)

46

Với j là độ lệch chuẩn của các thuộc tính j. So với khoảng cách Euclide chuẩn, phiên bản trọng số của nó giúp loại bỏ sự ảnh hƣởng của các tính năng riêng lẻ trên các vùng khác biệt đáng kể.

Ngƣỡng  rất quan trọng cho việc xác định các vùng xấp xỉ của mỗi cụm.

Nếu ngƣỡng  có giá trị nhỏ hơn, sẽ có nhiều đối tƣợng thuộc về các cận dƣới.

Ngƣợc lại, nếu ngƣỡng  có giá trị cao hơn, sẽ có nhiều đối tƣợng thuộc về vùng

biên hơn. Việc lựa chọn giá trị của ngƣỡng không đúng cách sẽ dẫn đến các vùng xấp xỉ không chính xác, dẫn đến làm sai lệch thông tin hình thành mẫu. Thêm vào đó, vì không có phần tử nào, các phân vùng chồng chéo có thể không đƣợc xử lý hiệu quả bởi RCM.

3.2. Phân cụm mờ

Với cách tiếp cận truyền thống tạo ra các phân hoạch (các cụm), trong quá trình phân hoạch mỗi một mẫu (đối tƣợng) đƣợc kết gán vào trong một cụm xác định. Do đó, các cụm trong phân cụm phân hoạch không có tính kết nối. Thuật toán phân cụm mờ (Fuzzy Clustering) mở rộng khái niệm này để kết hợp các mẫu với tất cả các cụm bằng cách sử dụng hàm liên thuộc [Zadeh 1965].

Hình 3.2: Hình minh họa cụm mờ

47

Trong phân cụm mờ, mỗi một cụm là một tập mờ cho tất cả các mẫu (các đối tƣợng). Hình 3.2 minh họa ý tƣởng này. Các hình chữ nhật bao quanh 2 cụm dữ liệu H1= {1,2,3,4,5} và H2={6,7,8,9}. Thuật toán phân cụm mờ có thể tạo ra hai cụm mờ F1 và F2 đƣợc biểu diễn bởi các hình elip nhƣ trên hình 3.2. Các mẫu có các giá trị liên thuộc nằm trong đoạn [0,1] cho mỗi cụm. Ví dụ cụm mờ F1 có thể đƣợc xem nhƣ là {(1 , 0.9), (2 , 0.8), (3 , 0.7), (4 , 0.6), (5, 0.55),(6 , 0.2), (7 , 0.2), (8 , 0.0), (9 , 0.0)} và F2 có thể xem là {(1 , 0.0), (2 , 0.0), (3 , 0.0), (4 , 0.1) , ( 5 , 0.15) , (6 , 0.4), (7 , 0.35), (8 , 1.0), (9 , 0.9)}. Các cặp có thứ

tự trong mỗi cụm biểu diễn mẫu thứ i và giá trị liên thuộc của nó vào cụm

thứ uj. Giá trị liên thuộc càng cao cho biết độ tin cậy để kết gán đối tƣợng đó tới cụm càng lớn. Phân cụm phân hoạch có thể thực hiện từ phân hoạch mờ thông qua ngƣỡng cho trƣớc của hàm liên thuộc.

Lý thuyết tập mờ đƣợc ứng dụng vào phân cụm đầu tiên bởi Ruspini [1996]. Thuật toán phân cụm mờ phổ biến nhất là thuật toán phân cụm Fuzzy C- Means (FCM). Mặc dù nó tốt hơn thuật toán phân cụm K-Means là tránh đƣợc tối ƣu cục bộ, nhƣng thuật toán phân cụm mờ K-Means vẫn hội tụ tới tối ƣu cục bộ của hàm đánh giá. Do đó, việc thiết kế hàm đánh giá là vấn đề quan trọng trong phân cụm mờ; những lựa chọn khác thƣờng dựa trên việc phân tích tính tƣơng đồng của các đối tƣợng và tâm của các cụm. Thuật toán FCM đƣợc Dunn đề xuất (1974) và đƣợc phát triển bởi Bezdek (1981) dựa vào hàm mục tiêu.

(3.6)

Với m>1 là hệ số mờ, uik[0,1] là thành viên của Mô hình thứ k với tâm

là khoảng cách Euclide cụm vi, và

(3.7)

Và

(3.8)

48

i, với , tùy thuộc vào ,k, và

Việc đƣa ra đối tƣợng và tính toán tâm đƣợc lặp đi lặp lại cho đến khi

, tại lần lặp t.

Nói tóm lại, thuật toán FCM là quá trình cập nhật các mẫu và ma trận phân hoạch. Các giá trị của các tham số đƣợc cho trong từng trƣờng hợp cụ thể. Chúng bao gồm: Số lƣợng cụm (K), độ tƣơng đồng hay hàm khoảng cách, hệ số mờ và ngƣỡng kết thúc quá trình cập nhật .

Tƣ tƣởng của thuật toán đƣợc mô phỏng nhƣ sau:

Khởi tạo: lựa chọn các giá trị của các tham số K,m, và . Chọn hàm

khoảng cách. Khởi tạo ngẫu nhiên ma trận phân hoạch (ma trận liên thuộc).

Repeat// vòng lặp chính

Tính toán tâm của các cụm.

Tính toán ma trận phân hoạch.

Until điều kiện dừng là các phần tử trong ma trận phân hoạch thỏa

mãn ràng buộc với

Đã có rất nhiều thuật toán cải tiến từ thuật toán FCM nhằm cải tiến chất lƣợng phân cụm cho các tập dữ liệu chứa nhiễu và có hình dạng các cụm bất kỳ. Các thuật toán này chủ yếu thay đổi độ tƣơng đồng và hàm mục tiêu. Dƣới đây là một số thuật toán cải tiến từ thuật toán FCM:

Thuật toán FCM đƣợc cộng thêm biểu thức Entropy vào hàm đánh giá với mục đích làm giảm tốc độ hội tụ và cải tiến chất lƣợng phân cụm. Hàm mục tiêu đƣợc viết lại nhƣ sau:

+ (3.9)

Bài toán phân cụm trở thành bài toán làm tối thiểu hàm mục tiêu E với

ràng buộc với t=1,2,…K. Áp dụng phƣơng pháp Lagrange ta tính

49

đƣợc:

(3.10)

(3.11)

Với . Bài toán tối thiểu hàm mục tiêu E trở thành bài toán

tìm x = [xij] và r = [r1, ..., rk]. Đầu tiên, chúng ta khởi tạo ngẫu nhiên x và tính toán r, và sau đó cập nhật x. Lặp đi lặp lại việc cập nhật này cho tới khi x hội tụ. Hàm mục tiêu sẽ giảm tuyến tính theo các vòng lặp này và dừng lại ở nghiệm tối ƣu cục bộ.

Thuật toán FCM truyền thống đƣợc cải tiến bằng cách thay đổi khoảng tƣợng bằng hàm tƣơng đồng giữa các đối cách Euclidian hay độ

nhằm mục đích tránh nhiễu trong quá trình phân cụm. Dễ

dàng chứng minh đƣợc rằng f(di,rj) thành lập đƣợc một không gian metric. Nếu một đối tƣợng di là nhiễu nằm trong một cụm thì đối tƣợng này không ảnh hƣởng tới quá trình cập nhật lại tâm cụm.

Ngoài ra, thuật toán FCM còn đƣợc cải tiến bằng cách sử dụng phƣơng pháp Kernel Method. Kernel Method là phƣơng pháp chuyển đổi không gian dữ liệu sang không gian khác, số chiều của không gian đƣợc biến đổi có thể lớn hơn hoặc bé hơn không gian dữ liệu ban đầu. Việc biểu diễn dữ liệu ở không gian biến đổi cho phép cho chúng ta phân cụm tốt hơn, đồng thời tránh đƣợc nhiễu so với việc phân cụm trong không gian dữ liệu ban đầu.

3.3. Phân cụm thô-mờ (Rough-Fuzzy C-means)

50

Theo sự sát nhập của các phƣơng pháp phân cụm thô và mờ, Mitra [5] đƣa ra thuật toán phân cụm thô- mờ (Rough-Fuzzy C-Means viết tắt là RFCM), trong đó mức phần tử uik sẽ thay thế khoảng cách tuyệt đối d(xk,vi) khi xác định

các vùng xấp xỉ cho từng cụm. Việc điều chỉnh này sẽ tăng cƣờng sự vững mạnh của các phân cụm trong các tình huống chồng chéo. Trong trƣờng hợp này, việc tính toán mẫu đƣợc điều chỉnh bởi các biểu thức sau:

(3.12)

Với

(3.13)

(3.14)

A2 và B2 có thể đƣợc coi là các cận dƣới mờ và vùng biên mờ tƣơng ứng.

Trọng số wb, wl có giá trị nhƣ trong RCM với wb=1-wl và 0.5

, và Nếu upk-uqk, thì . Trong trƣờng hợp này, xk

không thể thuộc về các cận dƣới của bất kỳ cụm nào. Nếu không, . uik

biểu diễn mức phần tử của đối tƣợng xk vào cụm với mẫu vi= (i= 1,2,...,C) và đã đƣợc tính toán tƣơng tự nhƣ trong FCM. upk và uqk đại diện cho cực đại và cực đại thứ 2 của xk trên tất cả các cụm tƣơng ứng.

51

Giả định hệ số mờ m có giá trị lớn hơn 1. Giá trị của nó phản ánh hình dạng của cụm mờ. Khi giá trị gần 1, nó có tính chất lôgic của cụm. Ngƣợc lại, nó sẽ cho kết quả hàm phần tử tăng đột biến giống nhƣ khi tăng giá trị (chẳng hạn nhƣ ba hoặc nhiều hơn). Chúng ta có thể kiểm soát hình dạng của cụm bằng cách lựa chọn giá trị khác nhau của m. Yu cung cấp một cơ sở lý luận cho việc lựa chọn hệ số mờ và chỉ ra rằng giá trị thích hợp của nó sẽ phụ thuộc vào các tập dữ liệu của nó. Một cơ chế mã hóa và giải mã mờ cũng đã đƣợc xây dựng

cho việc lựa chọn các giá trị tối ƣu thực nghiệm. Chủ yếu, các ứng dụng liên quan đến FCM thƣờng đặt giá trị này bằng 2.

Maji chỉ ra rằng trọng số của các đối tƣợng hình thành cận dƣới của một cụm nên độc lập với mẫu khác và chúng cần phải có sự đóng góp cùng với cụm này. Tuy nhiên, các đối tƣợng trong vùng biên nên thể hiện ảnh hƣởng khác nhau trên mẫu này. Mô hình Mitra đƣợc sửa đổi với các mẫu đƣợc tính tùy thuộc vào trọng số trung bình của các giới hạn cận dƣới và vùng biên mờ. Cụ thể hơn, chúng ta có

(3.15)

3.4. Phân cụm bóng

Tập bóng, nhƣ Pedrycz giới thiệu, là một trong số nhiều đóng góp quan trọng vào lĩnh vực Granular Computing. Nó có thể đƣợc coi là cấu trúc mới và độc lập, nhƣng nó thƣờng đƣợc tạo ra bởi các tập mờ tƣơng ứng. Nó đơn giản hơn và thực tế hơn tập mờ và có thể đƣợc tìm kiếm nhƣ là một biểu tƣợng đại diện của tập mờ số.

Mô hình không chắc chắn thông thƣờng nhƣ tập mờ có xu hƣớng nắm bắt sự mơ hồ thông qua các giá trị thành viên. Điều này đặt ra một vấn đề chính xác quá mức trong việc mô tả hiện tƣợng không chính xác. Khái niệm về tập bóng giải quyết vấn đề lựa chọn mức tối ƣu của cách giải quyết độ chính xác.

Độ chính xác quá mức của các tập mờ là khái niệm thiếu sót liên quan đến giá trị con số chính xác của thành viên đƣợc sử dụng để mô tả khái niệm mơ hồ. Chúng ta có thể gán giá trị thành viên lớp bằng 1 hoặc 0 một cách dễ dàng trong khi gán giá trị thành viên là 0.5 lại có sự không chắc chắn. Dựa trên ý tƣởng chính này, Pedrycz phát triển khái niệm của tập shadowed để cải thiện khả năng quan sát và diễn giải của hiện tƣợng mơ hồ.

52

Ba mức là yếu tố định lƣợng của tập {0,1, [0,1]} đƣợc sử dụng để đơn giản hóa các tập mờ có liên quan trong lý thuyết tập bóng. Rõ ràng, đó không chỉ đơn giản hoá việc giải thích mà còn tránh một số tính toán số lớp phần tử so

với tập mờ. Khái niệm, tập bóng giống với tập thô mặc dù cơ sở toán học của chúng rất khác nhau. Các khái niệm về vùng phủ định, cận dƣới và vùng biên trong lý thuyết tập thô tƣơng ứng với ba giá trị logic 0,1, và [0,1] trong tập che, cụ thể tƣơng ứng với, loại trừ, bao gồm và không chắc chắn. Trong ý nghĩa này, tập bóng có thể đƣợc coi là cầu nối giữa tập mờ và thô.

Việc xây dựng các tập bóng dựa trên cân bằng sự không chắc chắn vốn đã liên quan đến tập mờ, nói cách khác, sự không chắc chắn tái lập. Nhƣ việc nâng cao giá trị phần tử (đủ cao) của một số vùng của không gian đến 1 và đồng thời, làm giảm giá trị phần tử (đủ thấp) của một số vùng của không gian đến 0, chúng ta có thể loại bỏ sự không chắc chắn trong các vùng này. Để cân bằng không chắc chắn hoàn toàn, nó cần phải bù đắp những thay đổi này bằng cách cho phép cho sự xuất hiện của các vùng không chắc chắn, điều đó xảy ra ở trong tập bóng.

Xét một tập J mờ nhƣ mô tả trong hình 3.3. Tập bóng điều chỉnh các giá trị thành viên (MVs) trên giới hạn của ba giá trị logic bằng cách nâng cao và làm giảm một số MV và cân bằng sự không chắc chắn. Nâng cao, giảm và cân bằng sự không chắc chắn là điều khá cơ bản. Tập bóng tạo ra sự khác biệt với các khái niệm của tập mờ bằng cách tăng một vài trong số các MV tới 1 và giảm một vài MV khác tới 0. Nhƣ vậy làm tăng sự tƣơng phản, do đó làm giảm số lƣợng tính toán so với tập mờ. Để duy trì mức độ tổng thể của sự mơ hồ, một số vùng khác đƣợc xác định là vùng không chắc chắn. Một tập bóng là một ánh xạ đƣợc xác định nhƣ sau:

Ở đây các đối tƣợng có giá trị thành viên bằng một là lõi (core), trong khi

các đối tƣợng thuộc vùng bóng của ánh xạ, phần còn lại tạo thành

53

vùng loại trừ. Các vùng đƣợc phân định rõ ràng trong hình 3.3. Ban đầu, tập shadowed đã đƣợc giới thiệu để mô tả tập mờ.

Hình 3.3. Các tập bóng đƣợc tạo bởi tập mờ thông qua một ngƣỡng

Câu hỏi hấp dẫn nhất liên quan đến việc tính toán ngƣỡng. Pedrycz đề xuất một tối ƣu hóa dựa trên sự cân bằng của sự mơ hồ. Giảm một số MV về không và tăng một số tới 1 phải đƣợc bù đắp bằng sự do dự đáng kể các vùng khác, hoặc tăng sự không chắc chắn trong MV trong khoảng đơn vị [0,1] trên phạm vi cụ thể của J. Ngƣỡng cụ thể đƣợc lựa chọn cho quá trình định lƣợng và đƣợc thể hiện trong giới hạn của mối quan hệ

Cho một hàm phần tử m liên tục , giảm sự không

chắc chắn và che có thể đƣợc đƣợc thể hiện nhƣ hình 3.3 và đƣợc xác định nhƣ sau:

Giảm phần tử:

(3.16)

Tăng phần tử:

(3.17)

Hình thành shadows:

54

(3.18)

Ngƣỡng riêng biệt  trong tập bóng có thể đƣợc tối ƣu hóa bằng cách thực

hiện các nguyên tắc cân đối không chắc chắn. Nó chuyển thành cực tiểu hàm mục tiêu theo công thức sau.

(3.19)

Ngƣỡng tối ƣu  thỏa mãn yêu cầu với [0,0.5).

Phiên bản riêng biệt của quá trình tối ƣu hóa có thể đƣợc thể hiện một cách

tƣơng tự. Giả sử u1, u2,…, uN là những giá trị phần tử rời rạc, uk[0,1] (k=1,2,…,N). umax và umin biểu diễn giá trị lớn nhất và nhỏ nhất, tƣơng ứng. Hàm mục tiêu đƣợc sửa đổi nhƣ

(3.20)

Với có nghĩa là giảm phần tử.

có nghĩa là tăng phần tử. thể hiện

cho shadows, .

Phạm vi của các giá trị khả thi của một ngƣỡng  đƣợc đề xuất trong

.

55

Ba giá trị logic gây ra bởi tập bóng tƣơng ứng với khái niệm của ba vùng xấp xỉ trong lý thuyết tập thô. Mặc dù nền tảng của hai phƣơng pháp này là khác nhau, chúng chia sẻ một số triết lý phổ biến khi đối phó với những vấn đề không chắc chắn. Những giá trị chính của tập bóngliên quan đến các cơ chế tối ƣu hóa cho việc lựa chọn ngƣỡng riêng biệt và có sự giảm bớt số lƣợng phép tính đơn giản.

Hình 3.4. Các tập bóng đƣợc tạo ra bởi hàm thành viên mờ f(x)

Dựa trên khái niệm của tập shadowed, chúng tôi phát triển ở đây thuật toán shadowed c -means hoặc phân cụm SCM. Xác định các MV dựa vào vùng lõi, bóng và loại trừ cho phép giảm độ phức tạp tính toán [13]. Chúng tôi tin rằng các đối tƣợng tƣơng ứng với vùng core không nên có bất kỳ trọng số mờ nào trong giới hạn của các MV của nó. Nói cách khác, không giống nhƣ việc tính toán MV nhƣ trong FCM, ở đây MV phải đƣợc thống nhất cho các đối tƣợng lõi trong khi tính toán tâm. Các đối tƣợng tƣơng ứng với vùng bóng nằm trong vùng không chắc chắn, chúng đƣợc xem xét giống nhƣ trong FCM. Tuy nhiên, các thành viên của vùng loại trừ đƣợc kết hợp một cách hơi khác nhau.

Tâm của lớp thứ i đƣợc đánh giá là

(3.21)

(3.22) Với

56

(3.23)

(3.24)

Và là ngƣỡng tƣơng ứng. Cách tính toán này giảm đƣợc ảnh hƣởng

của nhiễu và các phần tử ngoại lai.

Các bƣớc chính của thuật toán đƣợc nêu dƣới đây.

1. Khởi tạo tâm, vi, i=1,…,c. Chọn các giá trị mờ, m và tmax. Thiết lập

biến đếm lặp t=1.

2. Lặp các bƣớc 3-5 bằng cách tăng t cho đến khi không có nhiệm vụ

mới và t

3. Tính uik với c cụm và N đối tƣợng.

4. Tính toán ngƣỡng của lớp thứ i trong phƣơng trình.

5. Cập nhật tâm vi.

57

Giá trị nằm trong khoảng

CHƢƠNG 4. ỨNG DỤNG RCM TRONG PHÂN CỤM ẢNH

4.1 Phân vùng ảnh:

Phân vùng ảnh là một bƣớc trong xử lý ảnh. Phân vùng ảnh là tách một ảnh đầu vào thành các vùng thành phần để biểu diễn phân tích, nhận dạng ảnh. Ví dụ: để nhận dạng chữ (hoặc mã vạch) trên phong bì thƣ cho mục đích phân loại bƣu phẩm, cần chia các câu, chữ về địa chỉ hoặc tên ngƣời thành các từ, các chữ, các số (hoặc các vạch) riêng biệt để nhận dạng. Đây là phần phức tạp khó khăn nhất trong xử lý ảnh và cũng dễ gây lỗi, làm mất độ chính xác của ảnh. Kết quả nhận dạng ảnh phụ thuộc rất nhiều vào công đoạn này.

Phân vùng ảnh là bƣớc then chốt trong xử lý ảnh. Giai đoạn này nhằm phân tích ảnh thành những thành phần có cùng tính chất nào đó dựa theo biên hay các vùng liên thông. Tiêu chuẩn để xác định các vùng liên thông có thể là cùng mức xám, cùng màu hay cùng độ nhám...

Hình 4.1 Minh họa ảnh đã phân vùng

58

Trƣớc hết cần làm rõ khái niệm "vùng ảnh" (Segment) và đặc điểm vật lý của vùng. Vùng ảnh là một chi tiết, một thực thể trông toàn cảnh. Nó là một tập hợp các điểm có cùng hoặc gần cùng một tính chất nào đó : mức xám, mức màu, độ nhám… Vùng ảnh là một trong hai thuộc tính của ảnh. Nói đến vùng ảnh là nói đến tính chất bề mặt. Đƣờng bao quanh một vùng ảnh (Boundary) là biên ảnh. Các điểm trong một vùng ảnh có độ biến thiên giá trị mức xám tƣơng đối đồng đều hay tính kết cấu tƣơng đồng.

Phân vùng ảnh đƣợc sử dụng trong nhiều lĩnh vực nhƣ: Truy hồi hình ảnh dựa trên nội dung, phân tích hình ảnh y tế, phát hiện đối tƣợng, nhận dạng mẫu, hệ thống điều khiển giao thông,…

Một số phƣơng pháp phổ biến của phân vùng ảnh:

- Phƣơng pháp phân cụm

- Phƣơng pháp dựa trên nén

- Phƣơng pháp dựa trên biểu đồ

- Phƣơng pháp phát hiện cạnh

- Phƣơng pháp dựa trên phƣơng trình vi phân từng phần

- Phƣơng pháp phân vùng đồ thị

4.2 Ảnh và những khái niệm liên quan

4.2.1 Điểm ảnh (Picture Element)

Gốc của ảnh (ảnh tự nhiên) là ảnh liên tục về không gian và độ sáng. Để xử lý bằng máy tính (số), ảnh cần phải đƣợc số hoá. Số hoá ảnh là sự biến đổi gần đúng một ảnh liên tục thành một tập điểm phù hợp với ảnh thật về vị trí (không gian) và độ sáng (mức xám). Khoảng cách giữa các điểm ảnh đó đƣợc thiết lập sao cho mắt ngƣời không phân biệt đƣợc ranh giới giữa chúng. Mỗi một điểm nhƣ vậy gọi là điểm ảnh (PEL: Picture Element) hay gọi tắt là Pixel. Trong khuôn khổ ảnh hai chiều, mỗi pixel ứng với cặp tọa độ (x, y).

Định nghĩa:

59

Điểm ảnh (Pixel) là một phần tử của ảnh số tại toạ độ (x, y) với độ xám hoặc màu nhất định. Kích thƣớc và khoảng cách giữa các điểm ảnh đó đƣợc chọn thích hợp sao cho mắt ngƣời cảm nhận sự liên tục về không gian và mức xám (hoặc màu) của ảnh số gần nhƣ ảnh thật. Mỗi phần tử trong ma trận đƣợc gọi là một phần tử ảnh.

4.2.2 Độ phân giải của ảnh

Định nghĩa:

Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh đƣợc ấn định trên một ảnh số đƣợc hiển thị. Theo định nghĩa, khoảng cách giữa các điểm ảnh phải đƣợc chọn sao cho mắt ngƣời vẫn thấy đƣợc sự liên tục của ảnh. Việc lựa chọn khoảng cách thích hợp tạo nên một mật độ phân bổ, đó chính là độ phân giải và đƣợc phân bố theo trục x và y trong không gian hai chiều.

4.2.3 Mức xám của ảnh

Một điểm ảnh (pixel) có hai đặc trƣng cơ bản là vị trí (x, y) của điểm ảnh và độ xám của nó. Dƣới đây chúng ta xem xét một số khái niệm và thuật ngữ thƣờng dùng trong xử lý ảnh.

a) Định nghĩa: Mức xám của điểm ảnh là cƣờng độ sáng của nó đƣợc gán

bằng giá trị số tại điểm đó.

b) Các thang giá trị mức xám thông thƣờng: 16, 32, 64, 128, 256 (Mức 256 là mức phổ dụng. Lý do: từ kỹ thuật máy tính dùng 1 byte (8 bit) để biểu diễn mức xám: Mức xám dùng 1 byte biểu diễn: 28 =256 mức, tức là từ 0 đến 255).

c) Ảnh đen trắng: là ảnh có hai màu đen, trắng (không chứa màu khác) với

mức xám ở các điểm ảnh có thể khác nhau.

d) Ảnh nhị phân: ảnh chỉ có 2 mức đen trắng phân biệt tức dùng 1 bit mô tả 21 mức khác nhau. Nói cách khác: mỗi điểm ảnh của ảnh nhị phân chỉ có thể là 0 hoặc 1.

60

e) Ảnh màu: trong khuôn khổ lý thuyết ba màu (Red, Blue, Green) để tạo nên thế giới màu, ngƣời ta thƣờng dùng 3 byte để mô tả mức màu, khi đó các giá trị màu: 28*3=224≈ 16,7 triệu màu.

4.2 Phân cụm ảnh sử dụng phân cụm thô và phân cụm mờ

Mục tiêu của phân cụm là phân chia tập các đối tƣợng vào trong các cụm có độ tƣơng đồng cao. Trong phân cụm ảnh, các đối tƣợng là các điểm ảnh (pixel). Thành phần của chúng bao gồm:

- Giá trị cƣờng độ

- Giá trị RGB và đặc tính màu sắc

- Độ đo kết cấu

Năm 1998 Tolias và Panas đề xuất ra phân vùng ảnh sử dụng phân cụm mờ (FCM). Từ đó cho đền nay việc phân vùng ảnh sử dụng FCM này vẫn đang đƣợc sử dụng rộng rãi và đã có rất nhiều cải tiến liên quan đến nó.

Việc phân vùng ảnh sử dụng phân cụm thô hay phân cụm mờ thực hiện các

bƣớc sau đây:

 Bƣớc 1: Đọc hình ảnh

 Bƣớc 2: Chuyển đổi hình ảnh từ hệ RGB sang hệ xám

 Bƣớc 3: Phân cụm các điểm ảnh bởi độ xám của mỗi điểm ảnh sau

khi đã chuyển thành hệ xám bằng thuật toán phân cụm

 Bƣớc 4: Gán nhãn cho từng điểm ảnh trong hình từ kết quả sau khi

phân cụm

4.3 Thử nghiệm phân cụm ảnh sử dụng phân cụm thô và phân cụm mờ

Tôi tiến hành cài đặt thuật toán phân cụm ảnh sử dụng phân cụm thô và phân cụm mờ trên môi trƣờng lập trình Matlab, với cấu hình của máy tính bình thƣờng: Ram 1GB, tốc độ xử lý của CPU là 1.8 GHz. Chƣơng trình phân cụm ảnh với ảnh bất kì.

61

Bƣớc đầu tiên tôi tải hình ảnh cần phân cụm vào chƣơng trình. Sau đó, với hình ảnh đã đƣợc nạp, tôi tiến hành bƣớc tiền xử lý ảnh để phân cụm là chuyển hình ảnh đó sang ảnh xám với các bƣớc thực hiện trong hàm nhƣ sau:

- Hình ảnh đã đƣợc nạp để xử lý thực chất là 1 ma trận xy, trong đó

mỗi điểm ảnh có tọa độ x[i]y[i] và chứa giá trị cƣờng độ của nó.

- Khi tiến hành chuyển hình ảnh màu về ảnh xám ta phải chuyển đổi

ma trận xy về ma trận cƣờng độ I (ma trận cƣờng độ I chứa các

giá trị trong khoảng [0,1], với 0 tƣơng ứng với màu đen, 1 tƣơng ứng với màu trắng) bằng cách chuyển giá trị của các điểm ảnh về 0 hay 1. So sánh giá trị của từng điểm ảnh, điểm ảnh nào có giá trị nhỏ hơn 0 sẽ đƣợc gán bằng 0, ngƣợc lại, điểm ảnh nào có giá trị nhỏ hơn 1 sẽ đƣợc gán bằng 1

Ví dụ về một ảnh màu đƣợc chuyển sang ảnh xám thực hiện từ thực

nghiệm:

(a) (b)

Hình 4.2: Chuyển hình ảnh từ hệ màu RGB sang ảnh xám

(a) Ảnh gốc ban đầu ở hệ màu RGB

(b) Ảnh sau khi đã đƣợc chuyển sang ảnh xám

Từ ảnh thu đƣợc sau khi đã chuyển thành ảnh xám tôi tiến hành thực hiện

phân cụm bằng thuật toán phân cụm nhƣ sau:

- Đối với phân cụm mờ Fuzzy C-means:

62

+ Khởi tạo số cụm, và hệ số mờ m.

+ Xác định các điểm ảnh cho từng cụm.

+ Gán giá trị khác nhau cho các cụm.

- Đối với phân cụm mờ Rough C-means:

+ Gán ngẫu nhiên các điểm ảnh cho các cụm với số cụm cho trƣớc.

+ Xác định xấp xỉ dƣới và vùng biên của mỗi cụm

+ Tính toán lại điểm ảnh của các cụm

+ Gán giá trị khác nhau cho các cụm

 Phân cụm ảnh với ảnh ban đầu là ảnh xám

Hình 4.3 Hình ảnh chụp cắt lớp sọ ngƣời

63

Tôi tiến hành mô phỏng phân cụm ảnh bằng hình ảnh nhƣ hình 4.3. Đối với hình ảnh này tôi lựa chọn số cụm là 7, và hệ số mờ cho phân cụm mờ m=2, xấp xỉ dƣới cho phân cụm thô là 0.95. Kết quả sau khi phân cụm bằng phân cụm thô và phân cụm mờ của hình chụp cắt lớp trên đƣợc thể hiện nhƣ trong hình 4.4 và 4.5.

Hình 4.4 Phân vùng ảnh chụp cắt lớp sử dụng phân cụm

(a) Phân vùng ảnh sử dụng phân cụm mờ (b) Phân vùng ảnh sử dụng phân cụm thô

 Phân cụm ảnh với ảnh ban đầu là ảnh màu

Hình 4.6: Hình ảnh tế bào đƣợc nhuộm màu H&E

64

Ở đây tôi phân cụm ảnh màu bằng hình ảnh nhƣ hình 4.3. Đối với hình ảnh này tôi lựa chọn số cụm là 3, và hệ số mờ và xấp xỉ dƣới cho phân cụm thô vẫn lựa chọn nhƣ trƣờng hợp trên là 2 và 0.95. Kết quả sau khi phân cụm bằng phân

cụm thô và phân cụm mờ của hình tế bào nhuộm màu H&E đƣợc thể hiện nhƣ trong hình 4.7 và 4.8.

Hình 4.7 Phân vùng ảnh màu sử dụng phân cụm

(a) Phân vùng ảnh sử dụng phân cụm mờ (b) Phân vùng ảnh sử dụng phân cụm thô

4.4 So sánh và đánh giá:

Để đánh giá kết quả phân cụm với thực nghiệm trên tôi thực hiện tính 3 chỉ số đánh giá với từng phƣơng pháp phân cụm mờ và phân cụm thô. Ba chỉ số tôi sử dụng ở đây là: Davies-Bouldin, Xie-Beni, và Silhouette. Chỉ số ở phƣơng pháp nào có giá trị nhỏ hơn thì kết quả phân cụm của phƣơng pháp đó tốt hơn.

- Chỉ số Davies-Bouldin là hàm tỉ lệ tổng khoảng cách trong cụm và

giữa các cụm.

Với k≥1, l≥c. Trong công thức trên, khoảng cách trong cụm dw(Uk) đƣợc tối hiểu và khoảng cách giữa các cụm db(Uk,Ul) đƣợc cực đại. Khoảng cách có thể đƣợc tính bằng công thức tính khoảng cách truyền thống Euclide

65

- Chỉ số Xie-Beni thể hiện giá trị mờ dựa trên hàm trong đó xác định các phân vùng mờ. Hàm này phụ thuộc vào bộ dữ liệu, độ đo khoảng

cách, khoảng cách giữa các tâm cụm và phân vùng mờ, không phân biệt có sử dụng thuật toán mờ hay không.

- Chỉ số Silhouette là một cách khác để ƣớc tính số lƣợng các cụm phân tán. Chỉ số Silhouette tính với từng điểm với độ rộng phụ thuộc vào độ thuộc của nó trong cụm bất kỳ.

Với N là tổng số các điểm, ai là khoảng cách trung bình giữa xi mẫu và tất cả các điểm trong các cụm đó, và bi là khoảng cách không tƣơng đồng giữa xi và các mẫu trong các cụm khác.

Dƣới đây là kết quả chỉ số của hai phƣơng pháp phân cụm thô và phân cụm mờ với các trƣờng hợp lựa chọn số cụm . Bảng 4.1 là kết quả của trƣờng hợp phân cụm với ảnh xám, bảng 4.2 là kết quả của trƣờng hợp phân cụm thứ hai với ảnh màu.

Chỉ số

C (Số cụm)

FCM

RCM

5

0.0696

Davies Bouldin

0.0659

6

0.0744

0.0703

7

0.0799

0.0764

5

0.2503

Xie Beni

0.2378

6

0.1893

0.1795

7

0.2049

0.1913

5

-0.8507

Silhouette

-0.8523

6

-0.8410

-0.8467

7

-0.8851

-0.8932

66

Bảng 4.1 Bảng giá trị các chỉ số trong trƣờng hợp phân cụm là ảnh xám

Chỉ số

C (Số cụm)

FCM

RCM

2

0.6829

Davies Bouldin

0.4246

3

0.3878

0.3418

2

0.5810

Xie Beni

0.5340

3

0.1230

0.1204

2

-0.7139

Silhouette

-0.7239

3

-0.3666

-0.3897

Bảng 4.2 Bảng giá trị các chỉ số trong trƣờng hợp phân cụm là ảnh màu

67

Ở bảng 4.1 trên tôi lựa chọn đƣa ra kết quả tốt nhất từ 3 lựa chọn số cụm tốt nhất là 5,6,7 còn bảng 4.2 tôi đƣa ra kết quả phân cụm từ 2 lựa chọn số cụm là 2,3. Nhìn vào kết quả các chỉ số ở cả 2 bảng 4.1 và 4.2, tuy chỉ số Xie Beni ở bảng 4.2 và 2 trƣờng hợp của chỉ số Xie Beni với số cụm 6 và 7 ở bảng 4.1 có kết quả tốt hơn ở thuật toán FCM nhƣng dựa trên tất cả kết quả của cả 3 chỉ số thì thuật toán RCM lại cho nhiều kết quả tốt tốt hơn. Do vậy, kết quả phân cụm ảnh sử dụng phân cụm thô là tốt hơn.

KẾT LUẬN

Chƣơng 1 của luận văn tôi đã trình bày tổng quan về phân cụm dữ liệu bao gồm độ tƣơng đồng, từ giá trị của độ tƣơng đồng giữa các đối tƣợng để phân chúng vào cùng một nhóm hay khác nhóm, và các phƣơng pháp phân cụm bao gồm: Phân cụm dựa vào hàm mục tiêu, phân cụm phân cấp, phân cụm dựa vào mật độ và phân cụm dựa vào lƣới và các thuật toán của chúng.

Chƣơng 2 tôi trình bày về lý thuyết tập thô với các định nghĩa về hệ thông tin, hệ quyết định, xấp xỉ tập hợp. Với khái niệm cơ bản của tập thô là vùng xấp xỉ trên và vùng xấp xỉ dƣới của tập dữ liệu. Với vùng xấp xỉ dƣới chứa những đối tƣợng chắc chắn thuộc về cụm và vùng xấp xỉ trên chứa những đối tƣợng có thể thuộc cụm.

Tiếp đó trong chƣơng 3 tôi trình bày các thuật toán phân cụm: phân cụm thô, phân cụm mờ, phân cụm thô-mờ, phân cụm bóng. Trong khi phân cụm mờ có ƣu điểm giải quyết đƣợc trƣờng hợp các cụm chồng chéo nhau thì phân cụm thô lại giải quyết tốt trƣờng hợp có các phần tử ngoại lai, hay các đối tƣợng chứa thông tin không chắc chắn. Phân cụm thô-mờ kết hợp từ hai thuật toán phân cụm thô và mờ, lấy ƣu điểm của cả hai phƣơng pháp này để đƣa vào thuật toán phân cụm của mình. Phân cụm bóng lấy tƣ tƣởng từ các vùng xấp xỉ của phân cụm thô và phát triển từ phân cụm thô-mờ, nó làm giảm sự chồng chéo trong các cụm nhƣ ở trong phân cụm mờ.

68

Chƣơng cuối cùng xây dựng phân vùng ảnh sử dụng phân cụm thô, so sánh với phân vùng ảnh sử dụng phân cụm mờ đã đƣợc xây dựng trƣớc đây. Kết quả cho thấy phân cụm thô có kết quả phân cụm tốt hơn. Trong thời gian tới, tôi sẽ tiếp tục nghiên cứu và ứng dụng phân cụm thô-mờ, phân cụm bóng vào lĩnh vực cụ thể.

Tài liệu tham khảo [1] Anil K. Jain,Richard C. Dubes, Algorithms for Clustering Data, 1988

[2]

J.C. Bezdek, Pattern Recognition With Fuzzy Objective Function Algorithms, Kluwer Academic Publishers, Norwell, MA, USA, 1981

[3]

Z.Pawlak, Rough sets, International Journal of Information and Computer Science 11 (1982)

[4]

P.Lingras, C.West, Interval set clustering of web users with rough k- means, Journal of Intelligent Information System 23 (2004)

[5]

S.Mitra, H.Banka, W.Pedrycz, Rough-fuzzy collaborative clustering, IEEE Transaction on System, Man, and Cybernetics (Part B) (2006)

[6]

P.Maji, S.K.Pal, Rough set based generalized fuzzy c-means algorithm and quantitative indices, IEEE Transaction on Systems, Man, and Cybernetics (2007)

[7] W.Pedrycz, Shadowed sets: representing and processing fuzzy sets IEEE Transactions on Systems, Man, and Cybernetics (Part B) (1998)

[8]

S.Mitra, W.Pedrycz, B.Barman, Shadowed c-means: intergrating fuzzy and rough clustering, Pattern Recognition 43 (2010)

[9]

Z.Pawlak, Rough Sets, Theoretical Aspects of Reasoning about Data, Kluwer Academic, Dordrech, 1991

[10] W.Predycz, Shadowed sets: representing and processing fuzzy sets, IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics 28 (1998)

[11] P.Maji, S.K.Pal, Rough-Fuzzy C-Means Algorithm, Fundamental

Informaticae 80, (2007) 475-496

[12]

Juraj Horvath, Image Segmentation Using Fuzzy C-Means, IEEE International Conference on Computational Cybernetics ICCC, 2004

69

[13] Yang, Huang, Imgage segmentation by Fuzzy C-Means clustering algorithms, Computing and Informatics, Vol. 26, 2007, 17–31

70