Các thuật toán phân tích phân cụm và ứng dụng: Luận văn Thạc sĩ Khoa học

Mục lục

Lời nói đầu iii

1 Khái quát chung về dạng và nhận dạng

1 1 1 2 2 5 6 7 7

1.1 Khái niệm về dạng và nhận dạng . . . . . . . . . . . . . . 1.1.1 Khái niệm về dạng, lớp dạng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Khái niệm nhận dạng: 1.2 Không gian mẫu và cách tiếp cận nhận dạng . . . . . . . . . . . . . . . . . . . . . . 1.3 Một số ứng dụng của nhận dạng: 1.3.1 Nhận dạng giọng nói . . . . . . . . . . . . . . . . . 1.3.2 Nhận dạng chữ viết tay . . . . . . . . . . . . . . . 1.3.3 Dự báo thời tiết . . . . . . . . . . . . . . . . . . . . 1.3.4 Phân tích điện tâm đồ để chẩn đoán hoạt động của tim . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.5 Phân tích y học bằng chụp tia X-quang . . . . . . . 1.3.6 Làm rõ các bức ảnh chụp từ vệ tinh và khoảng không

8 8 8 9 1.4 Học có hướng dẫn và không có hướng dẫn . . . . . . . . .

2 Phân tích phân cụm và các thuật toán phân cụm

11 11 2.1 Phân tích phân cụm . . . . . . . . . . . . . . . . . . . . . 11 2.1.1 Khái niệm phân cụm . . . . . . . . . . . . . . . . . 13 2.1.2 Ứng dụng của phân cụm . . . . . . . . . . . . . . . 13 2.1.3 Các yêu cầu của phân tích phân cụm . . . . . . . . 2.2 Các độ đo thường được sử dụng trong phân tích phân cụm 15 2.2.1 Độ đo sự gần gũi . . . . . . . . . . . . . . . . . . . 15 2.2.2 Khoảng cách giữa hai cụm (interset) và khoảng cách nội cụm (intraset) . . . . . . . . . . . . . . . . . . . 2.3 Phân cụm trong trường hợp số lớp chưa biết . . . . . . . . 2.3.1 Thuật toán sử dụng phương pháp trực quan . . . . . . . . . . . . . . 2.3.2 Thuật toán Batchelor và Wilkins 17 19 19 21

2.5 Thuật toán K*-means

2.4 Phân cụm trong trường hợp đã biết số lớp . . . . . . . . . 2.4.1 Thuật toán ISODATA . . . . . . . . . . . . . . . . 2.4.2 Thuật toán ISODATA hiệu chỉnh . . . . . . . . . . 2.4.3 Thuật toán K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Độ đo cho phân cụm dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Thuật toán K*-means 2.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . 25 25 34 36 40 41 45 48

3 Chương trình ứng dụng thuật toán ISODATA

3.1 Nêu lại ví dụ: . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Các trường hợp tính toán . . . . . . . . . . . . . . . . . . 52 52 52

Kết luận 59

Tài liệu tham khảo 60

Lời nói đầu

Cuộc sống ngày càng hiện đại, khoa học công nghệ ngày càng phát triển và đạt được nhiều thành tựu to lớn, phục vụ thiết thực cho cuộc sống của con người. Trong những thành tựu đó không thể không nhắc tới công nghệ nhận dạng. Công nghệ nhận dạng sử dụng khả năng tính toán của máy tính để xử lý một khối lượng dữ liệu lớn thành các thông tin cần thiết dựa vào quá trình nhận dạng của con người. Nhờ công nghệ nhận dạng bạn có thể điều khiển các đồ vật trong nhà mình không cần bằng tay mà bằng giọng nói, hay bạn không phải tra thìa khóa vào ổ để mở cửa mà chỉ cần đặt tay vào máy nhận dạng là cửa tự động mở, v.v. Còn vô số các ứng dụng mà bạn không thể ngờ tới trong tương lai không xa. Công nghệ cuộc sống, điều đó thật thú vị phải không? Đó là lí do vì sao chúng tôi chọn đề tài "Các thuật toán phân tích phân cụm và ứng dụng". Không đi sâu vào nghiên cứu từng ứng dụng cụ thể của nhận dạng ở trên mà luận văn này tập trung vào ba chương chính:

Chương 1: Nêu khái quát chung về nhận dạng, bao gồm khái niệm về dạng, lớp dạng và khái niệm nhận dạng, cùng với những ứng dụng của nhận dạng. Qua đó cung cấp cho chúng ta một cách nhìn tổng quan về nhận dạng.

Chương 2: Đây là nội dung chính của bản luận văn. Chương này gồm

ba phần:

• Phần đầu là mục "phân tích phân cụm" bao gồm khái niệm phân cụm,

ứng dụng của phân cụm, và một số yêu cầu trong phân cụm.

• Giới thiệu một số độ đo thường được sử dụng trong phân tích phân

cụm.

• Trình bày một số các thuật toán phân cụm dữ liệu trong 2 trường hợp: chưa biết trước số lớp và đã biết trước số lớp. Phần này tập trung chính vào trình bày 2 thuật toán quan trọng trong phân tích phân cụm, đó là thuật toán ISODATA và thuật toán K-means, phân tích ưu nhược

iii

điểm của chúng và giới thiệu thuật toán cải biên K*-means nhằm khắc phục các nhược điểm đó.

Chương 3: Xây dựng chương trình ứng dụng minh họa cho thuật toán ISODATA, trong đó có ứng dụng thuật toán ISODATA để phân cụm dữ liệu với số liệu đầu vào cho trước, đồng thời trình bày thuật toán sinh số liệu phân phối chuẩn hai chiều qua mô phỏng và từ đó áp dụng thuật toán ISODATA để phân cụm dữ liệu vừa sinh.

Qua đây, chúng tôi xin được gửi lời cảm ơn sâu sắc đến người thầy, người hướng dẫn khoa học của mình, TS. Nguyễn Hữu Tiến, người đã đưa ra đề tài và tận tình hướng dẫn trong suốt quá trình nghiên cứu của chúng tôi. Đồng thời xin gửi lời cảm ơn sâu sắc đến các thầy cô trong khoa Toán - Cơ - Tin học trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, đã dạy bảo và tạo mọi điều kiện cho chúng tôi về tài liệu và thủ tục hành chính để hoàn thành bản luận văn này. Cuối cùng xin gửi lời cảm ơn chân thành đến gia đình, bạn bè đã động viên giúp đỡ trong quá trình thực hiện luận văn.

Do thời gian và trình độ còn hạn chế, chắc chắn bản luận văn không thể tránh khỏi những thiếu sót, chúng tôi rất mong nhận được sự chỉ bảo tận tình của các thầy cô và bạn bè đồng nghiệp, xin chân thành cảm ơn!

Hà Nội, ngày 20 tháng 11 năm 2010

Học viên

Lê Đăng Điển

Chương 1

Khái quát chung về dạng

và nhận dạng

1.1 Khái niệm về dạng và nhận dạng

1.1.1 Khái niệm về dạng, lớp dạng

Khái niệm về dạng: Chúng ta nói về dạng thường là đề cập đến những đối tượng hoặc những cá thể mà ta có thể quan sát được. Nhưng thực tế ta có thể hiểu dạng theo nghĩa rộng hơn, dạng không chỉ là một đối tượng cụ thể mà còn có thể là một hệ thống dữ liệu.

Có rất nhiều ví dụ về dạng như khi ta nghiên cứu tình hình kinh tế của một quốc gia thì ta đề cập đến dạng của nền kinh tế quốc gia đó, ta nhận thấy rằng trong suốt quá trình khủng hoảng tài chính thế giới năm 1997-1999 có nhiều quốc gia bị ảnh hưởng nặng nề nhưng một số khác thì không, lí do là dạng nền kinh tế của họ là khác nhau.

Khái niệm về lớp dạng: Dạng có thể được xác định định lượng hay được mô tả cấu trúc của đối tượng mà chúng ta quan tâm. Theo đó một lớp dạng có thể được hiểu là một tập hợp các dạng có một số thuộc tính chung.

Thông thường, dạng được mô tả như một điểm trong không gian đa chiều thích hợp nào đó gọi là không gian dạng (mỗi chiều tương ứng với một đặc trưng nào đó của dạng).

Chương 1. Khái quát chung về dạng và nhận dạng

1.1.2 Khái niệm nhận dạng:

Nhận dạng là quá trình phân loại các dữ liệu đo được hay nhận thấy được thành một thành phần của một trong số những lớp hay cụm khác nhau. Thực tế ta có thể xây dựng cấu trúc phân biệt các lớp dạng khác nhau. Ví dụ như, không khó để phân biệt giới tính nam-nữ, phân biệt người ở khu vực này khu vực kia trên thế giới... Mục đích chung của các nghiên cứu nhận dạng là tìm ra cơ chế hoạt động của quá trình nhận dạng, mô phỏng tính năng và xử lý các thủ tục nhận dạng bằng công nghệ hiện đại nhằm phục vụ cho các nhu cầu thiết thực hằng ngày của con người. Nhận dạng là một nhánh của trí tuệ nhân tạo mang tính liên ngành, rất nhiều nhà khoa học đã áp dụng công nghệ nhận dạng để giải quyết những vấn đề trong lĩnh vực nghiên cứu của họ như khảo cổ học, thiên văn học, mật mã, địa lí, địa chất,...

Thông thường công nghệ nhận dạng được áp dụng khi:

• Các phương pháp phân tích truyền thống thất bại.

• Việc áp dụng phương pháp mô hình hóa không phù hợp.

• Các xử lý dựa theo mô phỏng trở nên kém hiệu quả.

Chúng ta thường phân biệt hai loại bài toán nhận dạng cơ bản sau:

1. Nhận dạng các đối tượng cụ thể: là nhận dạng giữa các dạng vật thể mang tính chất không gian và thời gian. Ví dụ, không gian là quang cảnh, tranh ảnh, biểu tượng, các kí tự (chữ Latinh, chữ Ả rập, chữ Trung Hoa), các bản đồ thời tiết, điện tâm đồ (ECG), điện não đồ (EEG), hình ảnh chụp X-quang,...

2. Nhận dạng đối tượng trừu tượng: là nhận dạng khái niệm. Ví dụ, khi nghe một bản nhạc ta có thể nhận biết được bài đó có giai điệu đàn guitar hay piano ...

1.2 Không gian mẫu và cách tiếp cận nhận

dạng

Chúng ta cần lựa chọn, đo đạc hay quan sát để thu thập một tập dữ liệu về một hiện tượng nào đó. Nếu hiện tượng cần phân tích bao gồm

Chương 1. Khái quát chung về dạng và nhận dạng

các đối tượng vật lý hoặc hình ảnh, thì thiết bị thu thập dữ liệu có thể là camera, máy quét đa phổ, hay một thiết bị khác. Đối với những vấn đề khác như bài toán kinh tế, có thể cần đến một loại hệ thu thập dữ liệu đặc thù để thu được một tập dữ liệu phù hợp.

Trong quá trình tiền xử lý dữ liệu chúng ta thường sử dụng một phép biến đổi (hay một hàm) nào đó để chuyển đổi dạng quan sát được thành một dạng điện tử hoặc chuyển đổi một tập hợp dữ liệu rời rạc thành dạng toán học sao cho dữ liệu này phù hợp hơn với việc phân tích của máy tính. Kết quả của quá trình chuyển đổi này sẽ cho một véc tơ dạng, và véc tơ này được xem như một điểm trong không gian dạng mẫu.

Chẳng hạn nếu ta quét một ảnh bằng một máy quét đa phổ 12 kênh, ta sẽ thu được một điểm ảnh đơn lẻ với 12 giá trị, mỗi giá trị tương ứng với một phản ứng phổ riêng biệt. Còn nếu ảnh được xử lý như một ảnh màu, thì quá trình tiền xử lý sẽ cho một điểm ảnh với 3 giá trị thành phần màu chính, lần lượt tương ứng là: đỏ, xanh lá cây, xanh da trời.

Mỗi giá trị thành phần dải phổ có thể được xem như một biến ngẫu nhiên trong không gian n chiều của một không gian dạng mẫu trong đó mỗi thành phần dải phổ được cho tương ứng với một chiều. Mỗi dạng khi đó xuất hiện như một điểm trong không gian dạng mẫu Rn nó là một véc tơ gồm n thành phần kí hiệu là xi và có biểu diễn như sau:

  xi1

xi =

              xi2 ... xin

trong đó chỉ số n mô tả số chiều. Nếu n < 3, không gian dạng mẫu sẽ có biểu diễn bằng hình học. Một tập S bao gồm N véc tơ dạng mẫu có thể được mô tả bởi một ma trận kích thước N × n sau:

    x11 x12 · · · x1n

x21 x22 = S =

i = (xi1, xi2, · · · , xin), i = 1, · · · , N , biểu diễn véc tơ dạng mẫu

                            · · · x2n ... · · · xN n xN 1 xN 2 xT 1 xT 2 ... xT N

trong đó xT thứ i.

Chương 1. Khái quát chung về dạng và nhận dạng

Mục đích của việc trích chọn đặc trưng là quá trình làm giảm số chiều. Nó chuyển đổi dữ liệu gốc thành một dạng phù hợp gọi là véc tơ dạng mẫu và sẽ được sử dụng như đầu vào cho quá trình xử lý đưa ra quyết định phân loại. Như vậy kết quả của quá trình trích chọn đặc trưng sẽ cho các véc tơ đặc trưng:

xT i = (xi1, xi2, · · · , xir), i = 1, · · · , N ; với r < n

Một véc tơ dạng mẫu được đặt trong không gian dạng mẫu như một điểm, và các véc tơ dạng mẫu tập trung gần nhau trong không gian dạng mẫu sẽ tạo thành một lớp hay một cụm riêng biệt.

Như vậy dữ liệu đầu vào cho quá trình xử lý để đưa ra quyết định phân loại là một tập hợp các véc tơ dạng mẫu. Dữ liệu đầu ra của quá trình xử lý sẽ đưa ra quyết định phân loại.

Cả quá trình tiền xử lý và xử lý đưa ra quyết định thường được chọn lựa bởi người sử dụng. Hàm quyết định được sử dụng có thể là tuyến tính, tuyến tính từng khúc, phi tuyến, hay một số loại hàm khác. Trọng số được dùng trong quá trình xử lý đưa ra quyết định sẽ là các giá trị tính toán dựa trên việc hoàn thiện các thông tin tiên nghiệm có trong tập các véc tơ dạng mẫu. Tập dữ liệu này sẽ được gọi là tập luyện, còn quá trình xử lý trên được gọi là quá trình luyện. Trong suốt quá trình luyện, các trọng số sẽ được hiệu chỉnh tùy theo việc phân loại các véc tơ dạng mẫu của tập luyện được thực hiện là đúng hay sai. Quá trình luyện này sẽ được coi là hoàn thành khi các thông tin thu được cho phép hình thành một qui tắc phân loại có khả năng phân loại đúng tất cả các véc tơ dạng mẫu của tập luyện. Sau đó qui tắc phân loại được hình thành sẽ được sử dụng vào việc phân loại các dạng vào các lớp hay các cụm tương ứng của không gian dạng mẫu. Ta lưu ý là không nên tách rời hai công đoạn học và phân loại của một thủ tục nhận dạng với nhau. Thông thường việc kết hợp một cách hợp lý hai công đoạn nói trên sẽ tạo ra một thủ tục nhận dạng hiệu quả hơn.

Một tập luyện S sẽ được gọi là tập luyện có hướng dẫn nếu các véc tơ

dạng mẫu của nó được cho như sau:

 

; l = 1, · · · , K; i = 1, · · · , Nl; k = 1, · · · , n xl i =

                    xl i1 ... xl ik ... xl in

Chương 1. Khái quát chung về dạng và nhận dạng

trong đó l là chỉ số của lớp dạng, i là chỉ số véc tơ dạng mẫu thứ i của lớp thứ l: ωl; k là thành phần thứ k của vectơ dạng mẫu n chiều. K, Nl, n tương ứng là số lớp dạng, số véc tơ dạng mẫu của lớp thứ l, và số chiều của vectơ dạng mẫu.

Các véc tơ dạng mẫu thuộc cùng một lớp dạng do có cùng một số thuộc tính chung sẽ tạo thành một cụm trong một miền nhất định của không gian dạng mẫu.

Trong trường hợp không gian dạng mẫu là hai chiều thì bài toán phân loại thực chất là tìm một mặt phân biệt trong không gian dạng mẫu sao cho nó có khả năng phân loại đúng tất cả các véc tơ dạng mẫu của tập luyện. Sau đó ta mong muốn có thể sử dụng mặt phân biệt này để phân loại các véc tơ dạng mẫu bất kỳ nếu xét theo một độ đo sự gần gũi nào đó chúng là giống nhau với các véc tơ dạng mẫu của tập luyện đã cho trước. Như vậy quá trình nhận dạng thực chất sẽ là quá trình phân chia không gian dạng mẫu thành một số hữu hạn các miền rời nhau còn được gọi là các miền quyết định và việc phân loại sẽ phụ thuộc vào véc tơ dạng mẫu được xét rơi vào miền quyết định nào của không gian dạng mẫu. Cách tiếp cận này nói chung cũng giống như cách tiếp cận của lý thuyết quyết định. Điều cơ bản của cách tiếp cận này là cần có một biểu diễn đầy đủ tập dữ liệu dưới dạng các véc tơ dạng mẫu. Khi đó một thủ tục nhận dạng thường được xây dựng theo một trong hai phương pháp là phương pháp phân tích cấu trúc cú pháp và phương pháp tiếp cận theo lý thuyết quyết định.

Ta lưu ý rằng có một số bài toán cách tiếp cận cú pháp hoặc cấu trúc là phù hợp, trong khi một số bài toán cách tiếp cận lý thuyết quyết định lại phù hợp hơn. Việc chọn lựa cách tiếp cận nào phụ thuộc vào tập các dữ liệu có trong bài toán. Nhiều bài toán có thông tin cấu trúc phong phú có thể sử dụng phương pháp cấu trúc nhằm thu được một thủ tục nhận dạng hiệu quả. Nhưng trong các bài toán mà các thông tin cú pháp hay cấu trúc không đóng vai trò quan trọng thì nên sử dụng cách tiếp cận lý thuyết quyết định. Tuy nhiên, có nhiều ứng dụng cần kết hợp cả hai phương pháp nêu trên. Một sự kết hợp hợp lí của hai cách tiếp cận này có thể cho kết quả rất hiệu quả đối với một bài toán nhận dạng cụ thể.

1.3 Một số ứng dụng của nhận dạng:

Công nghệ nhận dạng mẫu có thể được áp dụng cho nhiều loại bài toán thực tế khác nhau, trong đó ta có thể nêu một số ứng dụng như sau:

Chương 1. Khái quát chung về dạng và nhận dạng

1.3.1 Nhận dạng giọng nói

Nhận dạng giọng nói có rất nhiều ứng dụng. Ví dụ như, trong công tác điều tra tội phạm, việc nhận dạng được chính xác giọng nói của các đối tượng để phân tích xem họ có phải đối tượng nghi vấn không hay không. Chúng ta có thể mô tả cơ chế hoạt động của một hệ thống nhận dạng

giọng nói theo sơ đồ sau:

Hình 1.1: Cơ chế của hệ thống nhận dạng giọng nói

Các tín hiệu biến đổi từ các ngôn từ, đầu tiên được lọc và lấy mẫu

Chương 1. Khái quát chung về dạng và nhận dạng

1.3.2 Nhận dạng chữ viết tay

thông qua các bộ lọc thông âm điệu với tần số trung tâm từ 200Hz đến 7500Hz. Một vài tham số riêng, chẳng hạn như những đỉnh cục bộ phổ, năng lượng giọng nói, và những biểu diễn toàn bộ mẫu của phổ, được chiết xuất cho sự phân mảnh và nhận dạng âm vị. Lỗi xuất hiện trong quá trình phân mảnh và nhận dạng âm vị được sửa bằng cách cho trước các quy tắc sửa lỗi âm vị, sau đó các tính toán tương đương được thực hiện và các tương thích nhất được chọn cho giải pháp.

Đây là một trong những ứng dụng chính của việc phân loại. Bài toán này đã được nghiên cứu trong một thời gian dài. Tuy nhiên, có nhiều cách khác nhau để viết một kí tự nên tỉ lệ nhận dạng đúng chữ viết tay còn thấp và vì thế các phương pháp nhận dạng chữ viết tay còn chưa được đưa vào ứng dụng thực tế.

Nhiều cách tiếp cận đã được đề xuất trong việc nhận dạng chữ viết tay. Cho đến bây giờ, đã có khoảng 121 kí tự khác nhau, bao gồm 52 chữ in hoa và chữ thường, 10 chữ số và những biểu tượng khác đã được cho là có thể nhận biết được.

1.3.3 Dự báo thời tiết

Máy nhận dạng còn có khả năng nhận dạng các kí tự phức tạp hơn như chữ Trung Hoa, hay các biểu tượng khác vẫn là đề tài đang được nghiên cứu.

Trong việc dự báo thời tiết, bản đồ áp suất khí quyển trên một khu vực nào đó là dữ liệu quan trọng cho việc nghiên cứu. Từ những kinh nghiệm trước đó và hiểu biết chuyên môn, những mẫu khác nhau có thể được định rõ trên các bộ bản đồ dữ liệu. Khi đó bài toán dự báo thời tiết trở thành phân loại các mẫu áp suất khí quyển đang tồn tại và liên kết chúng với các điều kiện thời tiết khác nhau. Việc phân loại tự động và bán tự động bằng máy tính đã trở nên rất cần thiết khi mà số lượng bản đồ tăng lên. Hai phương pháp thường dùng để phân loại biểu đồ đường đẳng áp là phương pháp phân tích tương quan và phương pháp phân tích thành phần chính (Kahunen-Loeve). Cả hai phương pháp này sẽ tìm ra những đặc trưng tổng thể. Ứng dụng của phương pháp cú pháp cho bài toán dự báo thời tiết, chẳng hạn như sử dụng chuỗi hoặc cây biểu diễn cho biểu đồ đường đẳng áp, cũng đang được nghiên cứu.

Chương 1. Khái quát chung về dạng và nhận dạng

1.3.4 Phân tích điện tâm đồ để chẩn đoán hoạt động

của tim

1.3.5 Phân tích y học bằng chụp tia X-quang

Điện tâm đồ (ECG) ghi chép lại hoạt động của tim thông qua máy đo nhịp tim. Thông tin về tim và những dẫn giải về thể chất của người bệnh có thể dễ dàng được ghi lại dưới dạng sóng trong định dạng "file" được chuyển đến. Các thông số được ghi lại qua máy điện tâm đồ rất hữu ích cho việc chẩn đoán các hoạt động của tim bệnh nhân từ đó bác sĩ có những biện pháp điều trị hợp lí.

1.3.6 Làm rõ các bức ảnh chụp từ vệ tinh và khoảng

không

Việc phát hiện, chẩn đoán sớm và chính xác bệnh có thể cứu chữa kịp thời cho bệnh nhân. Ví dụ về bệnh ho dị ứng do hít phải nhiều bụi của công nhân mỏ than đá, nguyên nhân do liên tục hít phải khí bụi bẩn và độc hại. Triệu chứng chính là sự giảm động mạch phổi. Chẩn đoán dựa trên việc phân biệt chính xác các vết mờ đục rất nhỏ của các mẫu khác nhau với các động mạch phổi thông thường. Các vết mờ đục này xuất hiện đây đó, đôi khi nằm trong kẽ xương sườn. Những vết này xuất hiện trong khoảng không của xương sườn, và bị che phủ bởi bóng của xương và các động mạch phổi chính, khiến cho rất khó để nhận ra. Kỹ thuật nhận dạng sẽ là hữu ích khi được áp dụng cho việc giải quyết dạng bài toán này.

Các bức ảnh chụp từ vệ tinh và khoảng không được sử dụng cho cả mục đích quân sự lẫn dân sự. Trong số các ứng dụng dân sự, việc phát hiện từ xa tài nguyên trái đất là một chủ đề quan trọng để nghiên cứu. Đặc biệt, trong thời đại hiện nay việc phát hiện từ xa có ứng dụng to lớn trong các ngành nông, lâm nghiệp, địa chất địa lý... Dữ liệu nhận được từ vệ tinh hoặc băng từ thu được dưới dạng ảnh. Do giới hạn năng lực của mắt người khó có thể thấy rõ giá trị các tín hiệu trên một bức ảnh và không thể phân tích nhiều bức ảnh cùng một lúc bằng mắt thường. Vì vậy, xử lý dữ liệu máy tính và phân loại dữ liệu sẽ ngày càng đóng vai trò quan trọng trong tương lai...

Chương 1. Khái quát chung về dạng và nhận dạng

1.4 Học có hướng dẫn và không có hướng

dẫn

Ta đã thấy ở trên một thủ tục nhận dạng sẽ bao gồm hai công đoạn là học và phân loại, trong đó công đoạn học (hay còn gọi là luyện) là quá trình hình thành tri thức phân loại dựa trên các thông tin đã cho trước ở tập luyện còn công đoạn phân loại là quá trình đưa ra quyết định phân loại một dạng có véc tơ dạng mẫu bất kỳ vào một trong các lớp hay các cụm đã được xác định. Tùy theo cấu trúc của tập luyện cho trước ta phân biệt hai quá trình học sau:

Quá trình học có hướng dẫn là quá trình hình thành tri thức phân loại thông qua việc xử lý một tập luyện bao gồm các véc tơ dạng mẫu cùng với chỉ số lớp tương ứng của nó đều đã cho trước. Khi đó, thủ tục nhận dạng được xây dựng sẽ lần lượt xử lý các véc tơ dạng mẫu của tập luyện và mỗi khi tri thức phân loại đã hình thành được sử dụng để phân loại cho véc tơ dạng mẫu mới được xét của tập luyện cho kết quả không đúng với chỉ số lớp cho trước của nó thì thủ tục phân loại sẽ thực hiện một hiệu chỉnh các tham số của nó và quá trình học này sẽ chỉ kết thúc khi: với tham số đã hiệu chỉnh, thủ tục phân loại đã thực hiện phân loại đúng toàn bộ tập luyện cho trước. Tập luyện bao gồm các véc tơ dạng mẫu cùng với chỉ số lớp tương ứng của nó đều đã cho trước như xét trên sẽ được gọi là một tập luyện có hướng dẫn. Rõ ràng là nếu tập luyện có hướng dẫn có kích thước đủ lớn và có tính đại diện cho lớp dạng của không gian dạng thì có cơ sở để tin là thủ tục phân loại đã học được các tri thức phân loại cần thiết và sẽ có khả năng thực hiện phân loại chính xác không chỉ với các véc tơ dạng mẫu của tập luyện mà đối với cả một véc tơ dạng mới bất kỳ.

Quá trình học không có hướng dẫn là quá trình hình thành tri thức phân loại cho một thủ tục nhận dạng nhờ kết quả xử lý một tập luyện chỉ bao gồm các véc tơ dạng mẫu mà không cho trước các chỉ số lớp tương ứng của chúng. Tập luyện này được gọi là tập luyện không có hướng dẫn và quá trình học trong trường hợp này thực chất là quá trình xử lý tập luyện nhằm hình thành trong tập luyện một cấu trúc cụm các véc tơ dạng mẫu theo nguyên tắc: các véc tơ dạng mẫu ở cùng một cụm sẽ là tương tự nhau (hay là "gần nhau") còn các véc tơ dạng mẫu ở các cụm khác nhau sẽ không tương tự nhau (hay là "không gần nhau") khi ta xét theo một độ đo gần gũi nào đó được chọn trước. Vấn đề chính trong quá trình này là việc xác định một độ đo gẫn gũi giữa các véc tơ dạng mẫu của tập luyện nhằm chọn ra tiêu chuẩn phân loại tốt nhất, đồng thời dựa vào tiêu chuẩn đánh giá về độ đo gần gũi này để xây

Chương 1. Khái quát chung về dạng và nhận dạng

dựng các thuật toán nhằm phân cụm các véc tơ dạng mẫu của tập luyện. Trong đề tài này, chúng tôi nghiên cứu về Các thuật toán phân tích phân cụm và ứng dụng, nghĩa là tìm hiểu một số các bài toán phân loại trong trường hợp học không có hướng dẫn (còn gọi là phân cụm). Dựa trên cơ sở nghiên cứu các độ đo gần gũi chúng tôi sẽ phân tích một số thuật toán phân cụm khác nhau trong trường hợp số lớp chưa biết và số lớp đã biết. Đồng thời, dựa trên một số yêu cầu thực tiễn trong phân cụm dữ liệu như tính mở rộng (tức là thuật toán có thể áp dụng với tập dữ liệu lớn), tính thích nghi (thích nghi với tập dữ liệu có hình dạng bất kì),v.v. chúng tôi sẽ giới thiệu một thuật toán cải biên K*-means có khả năng phân cụm rất linh động và hiệu quả.

Chương 2

Phân tích phân cụm và

các thuật toán phân cụm

2.1 Phân tích phân cụm

2.1.1 Khái niệm phân cụm

Phân cụm là phương pháp phân loại một tập dữ liệu (hay còn gọi là tập luyện) trong đó quá trình tạo ra các cụm không sử dụng bất kỳ kiến thức tiên nghiệm nào về chỉ số lớp của các cá thể thuộc tập luyện. Khi cho một tập luyện S gồm N phần tử:

S = {xi|xi ∈ Rn, i = 1, · · · , N }

Thì quá trình phân cụm có thể được phát biểu như sau: Tìm các miền con: S1, S2 · · · , SK của tập luyện S sao cho mỗi xi, i=1,...,N sẽ chỉ thuộc vào duy nhất một miền con xác định trên, nghĩa là:

S1 ∪ S2 ∪ · · · ∪ SK = S

Si ∩ Sj = ∅ với ∀i (cid:54)= j

Khi đó ta nói tập luyện có N phần tử trên đã được phân thành K cụm khác nhau. Đồng thời, các véc tơ thuộc cùng một cụm Si thì "gần nhau" hơn, còn các véc tơ thuộc các cụm khác nhau thì không "gần nhau", trong đó tiêu chuẩn độ đo sự gần gũi giữa các véc tơ của các cụm sẽ được lựa

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

chọn thích hợp với kiểu dáng hình thành của tập luyện cũng như với các thành phần được xác định (hay còn gọi là các biến) của các véc tơ dạng mẫu trong tập luyện.

Không giống như phân lớp, phân cụm không đòi hỏi phải cho trước các chỉ số lớp của các véc tơ dạng mẫu của tập luyện, cũng vì đặc điểm này nên phân cụm còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán phân loại.

Phân cụm có ý nghĩa rất quan trọng trong hoạt động của con người. Ngay từ nhỏ, con người đã học cách làm thế nào để phân biệt được 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 ứng dụng rộng rãi trong nhiều lĩnh vực, 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, địa lí, địa chất, y học,... Phân cụm có thể được sử dụng như một công cụ độc lập giúp hình thành các đặc trưng của mỗi cụm trong sự phân bố của tập luyện và từ đó 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 nhiễu do quá trình thu thập thiếu chính xác hoặc không đầ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 dữ liệu không chính xác, không tường minh, hoặc thiếu thông tin về một số thuộc tính... Một trong những kỹ thuật xử lí nhiễu phổ biến là việc thay thế giá trị các thuộc tính của dữ liệu bị nhiễu bằng giá trị thuộc tính tương ứng. Ngoài ra, dò tìm ra 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 chính của nó là xác định một nhóm nhỏ các dữ liệu không tuân theo các mô hình của tập dữ liệu đang được xét nhằm tránh sự ảnh hưởng của chúng tới kết quả phân cụm.

Mục tiêu của phân cụm là xác định được bản chất của cấu trúc cụm trong tập luyện không có hướng dẫn. Để thực hiện được việc này cần phân tích bài toán thực tế nhằm tìm ra các tiêu chuẩn cho việc tạo thành các cụm tốt theo một ý nghĩa nào đó.

Theo các nghiên cứu gần đây, 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ả tập dữ liệu. Hơn nữa, mỗi phương pháp phân cụm cần có cách thức biểu diễn cấu trúc khác nhau, và với mỗi cách thức biểu diễn khác nhau sẽ tương ứng với một thuật toán phân cụm phù hợp. Vì vậy, phân cụm 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 tập dữ liệu khác nhau nhất là đối với các tập dữ liệu dạng hỗn hợp.

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.1.2 Ứng dụng của phân cụm

Phân cụm có nhiều ứ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ừ những bản ghi mua bán trong các mẫu dữ liệu

• Sinh học: Phân loại các gen với các chức năng tương đồng và thu đượ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 các nhóm đối tượng tham gia bảo hiểm có chi

phi bồi thường cao, hoặc ưu tiên đặc biệt.

• 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

2.1.3 Các yêu cầu của phân tích phân cụm

cung cấp thông tin cho nhận dạng vùng nguy hiểm...

Trong lý thuyết nhận dạng, các nghiên cứu về phân cụm hiện nay vẫn là một thách thức vì những ứng dụng tiềm năng của phân cụm như đã nêu trên, bản thân nó lại đặt ra những vấn đề cần được giải quyết. Sau đây là những yêu cầu cơ bản của phân tích phân cụm:

• 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 phần tử, tuy nhiên, việc triển khai thuật toán này với một tập dữ liệu lớn có thể chứa đến hàng triệu phần tử sẽ là một bài toán mới. Sở dĩ như vậy vì thuật toán phân cụm có thể sẽ không cho kết quả mong đợi như đã thu được khi xét trên một tập dữ liệu có kích thước nhỏ nói trên. Rõ ràng bài toán đặt ra là làm thế 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 tập mẫu dữ liệu 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 với tập mẫu 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

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

dữ liệu khác nhau, như kiểu nhị phân, kiểu tường minh (định danh- không thứ tự), hay dạng hỗn hợp nhiều kiểu dữ liệu.

• 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 Euclide và khoảng cách Mahalanobis. 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à việc làm quan trọng.

• Tối thiểu hóa 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ó số lượng phần tử 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 phân cụm.

• Khả năng thích nghi với các dữ liệu nhiễu: Hầu hết những tập dữ liệu đều chứa đựng những phần tử ngoại lai, dữ liệu lỗi, chưa biết thuộc tính hoặc 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ự đầu vào của các tập dữ liệu: Một số thuật toán phân cụm nhạy cảm với thứ tự đầu vào của dữ liệu, ví dụ như với cùng một tập dữ liệu, khi được đưa vào với các thứ tự khác nhau thì có thể sinh ra các cụm khác nhau. Do đó, việc quan trọng là phát triển một thuật toán ít nhạy cảm với thứ tự đầu vào của các mẫu dữ liệu.

• Số chiều lớn: Một tập dữ liệu có thể chứa các véc tơ dạng mẫu với số chiều hoặc các thuộc tính lớn. Nhiều thuật toán phân cụm áp dụng tốt cho các mẫu dạng có số chiều thấp, bao gồm chỉ hai đến ba chiều. Người ta đánh giá việc phân cụm là có chất lượng nếu nó áp dụng được cho các mẫu dạng từ ba chiều trở lên. Đây là một 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 khi xét những không gian với số chiều lớn nhưng có thể rất thưa.

• Phân cụm ràng buộc: Nhiều ứng dụng thực tế có thể 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à

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

đi tìm những nhóm tập 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 thường 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à, một phân cụm được đề xuất sẽ cần được giải thích rõ ràng ý nghĩa và ứng dụng của nó.

2.2 Các độ đo thường được sử dụng trong

phân tích phân cụm

2.2.1 Độ đo sự gần gũi

Từ định nghĩa sự phân cụm, một cụm sẽ bao gồm các véc tơ dạng mẫu xi của tập luyện sao cho các véc tơ dạng mẫu thuộc cùng một cụm sẽ giống nhau càng nhiều càng tốt. Vì vậy, chúng ta cần một độ đo sự gần gũi đánh giá mức độ tương tự hoặc không tương tự giữa các mẫu này. Chẳng hạn nếu kí hiệu ζ là độ đo không tương tự giữa hai véc tơ dạng mẫu xi và xj, thì độ đo này có tính chất:

ζ(xi, xi) = 0

ζ(xi, xj) (cid:54)= 0 ∀xi (cid:54)= xj

Các độ đo sự gần gũi thường được đưa ra dưới dạng số để chỉ mức độ gần gũi giữa các mẫu trong một cụm, hoặc giữa một mẫu và một cụm các mẫu, hoặc giữa hai cụm mẫu.

1. Độ đo không tương tự:

• Độ đo khoảng cách Euclide:

n (cid:88)

Khoảng cách Euclide là độ đo không tương tự đơn giản nhất và thường sử dụng nhiều nhất, nó được kí hiệu là d(xi, xj) và xác định như sau:

k=1

d2(xi, xj) = (xi − xj)T (xi − xj) = (xik − xjk)2

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

trong đó: xi, xj ∈ Rn.

k=1 trong đó xi = (xi1, · · · , xin)T và xik, xjk là thành phần thứ k của xi,xj, và αk là trọng số tương ứng với thành phần thứ k của các véctơ đó. Đặc biệt, cho zl = (zl1, · · · , zln)T là trung bình của cụm thứ l. Cho αk = 1 σ2 lk trong đó σl = (σl1, ...., σln), và σ2 lk là phương sai của biến thành phần thứ k tương ứng với cụm thứ l. Khi đó khoảng cách Euclide từ xi tới cụm thứ l là dl(xi, zl), xác định như sau:

n (cid:88)

Khoảng cách này sẽ trở thành độ đo không tương tự nếu các biến thành phần của véc tơ xi, xj là có cùng thứ nguyên, nếu không ta cần sử dụng các hiệu chỉnh là các trọng số tương ứng. Khi đó, ta có một độ đo không tương tự có trọng số được xác định như sau: n (cid:88) αk(xik − xjk)2 d2(xi, xj) =

k=1

. d2 l (xi, zl) = (xik − zlk)2 σ2 lk

• Khoảng cách Mahalanobis

Bình phương khoảng cách Mahalanobis từ xi tới xj cho bởi

công thức:

r2(xi, xj) = (xi − xj)T C −1(xi − xj) trong đó C −1 là ma trận nghịch đảo của ma trận hiệp phương sai C. Khoảng cách Mahalanobis được sử dụng khi các biến (hay các thành phần) của véc tơ dạng mẫu không có cùng thứ nguyên.

2. Độ đo tương tự Tanimoto:

Tanimoto đưa ra một tỉ số được biết như là độ đo Tanimoto:

i xj

i xj biểu thị số các thuộc tính chung giữa xi và xj. Còn xT

dT (xi, xj) = xT i xj j xj − xT i xi + xT xT

trong đó xT i xi biểu diễn số các thuộc tính có bởi xi, và xT j xj biểu diễn số thuộc tính có bởi xj. Mẫu số biểu diễn số thuộc tính cái mà có ở trong xi hoặc xj nhưng không có ở trong cả hai. Vậy độ đo Tanimoto biểu diễn tỉ số giữa số thuộc tính thuộc vào cả hai véc tơ xi và xj với số thuộc tính chỉ có ở xi hoặc xj nhưng không có ở cả hai véc tơ dạng mẫu xi và xj.

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.2.2 Khoảng cách giữa hai cụm (interset) và khoảng

cách nội cụm (intraset)

Bình phương khoảng cách giữa hai cụm riêng biệt: ω1 và ω2 sẽ được ký

hiệu như sau:

12 = D2([x1

i ], [x2

j])

D2 (2.1) i = 1, · · · , N1; j = 1, · · · , N2

N1(cid:88)

N2(cid:88)

N1(cid:88)

N2(cid:88)

n (cid:88)

và được định nghĩa:

12 =

ik − x2

jk)2.

i , x2

j) =

i=1

j=1

i=1

j=1

k=1

i ] [x2

D2 (x1 (2.2) D2(x1 1 N1N2 1 N1N2

Như vậy, bình phương khoảng cách này là trung bình của bình phương các khoảng cách giữa các điểm thuộc các cụm riêng biệt, với chỉ số trên 1 và 2 trong [x1 j] ký hiệu cho các véctơ dạng mẫu thuộc cụm thứ nhất: ω1 và cụm thứ hai: ω2 và N1, N2 tương ứng là số véctơ dạng mẫu của cụm ω1 và ω2

Khoảng cách nội cụm của cụm thứ s (Ss) gồm N véc tơ dạng mẫu sẽ

n (cid:88)

được xây dựng tương tự như sau: Nếu xi, xj ∈ Ss thì khoảng cách giữa chúng là D(xi, xj) và được xác định như sau:

k=1

(2.3) D2(xi, xj) = (xik − xjk)2.

N (cid:88)

n (cid:88)

Ký hiệu D2(xi, [xj]) là trung bình bình phương khoảng cách từ một véc tơ dạng mẫu xi ∈ Ss tới N − 1 véc tơ dạng mẫu còn lại của cụm Ss và được xác định như sau:

j=1

k=1

(2.4) D2(xi, [xj]) = (xik − xjk)2. 1 N − 1

Khi đó, khoảng cách nội cụm của cụm Ss ký hiệu là Dss và bình phương của nó được định nghĩa là trung bình của các D2(xi, [xj]) đã xét ở trên, hay:

N (cid:88)

n (cid:88)

ss = D2([xi], [xj]) =

i=1

j=1

k=1

(cid:104) (2.5) D2 (xik − xjk)2(cid:105) 1 N 1 N − 1

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

n (cid:88)

N (cid:88)

Hay:

ss =

j=1

i=1

k=1

D2 (2.6) (xik − xjk)2(cid:105) . N N − 1 (cid:104) 1 N 2

Khai triển vế phải của biểu thức này ta được:

ss = D2([xi], [xj])

N (cid:88)

n (cid:88)

N (cid:88)

j=1

i=1

j=1

i=1

j=1

k=1

= (xik)2 − 2 xik xjk + (xjk)2(cid:105) N N − 1 (cid:104) 1 N 1 N 1 N 1 N 1 N 1 N

N (cid:88)

n (cid:88)

N (cid:88)

j=1

i=1

k=1

(cid:105) = . (2.7) (xik)2 − 2xik xjk + (xjk)2 N N − 1 (cid:104) 1 N 1 N

Do chúng ta đang làm việc trên tập các véc tơ dạng mẫu của cùng một cụm nên rõ ràng có:

(2.8) (xik)2 = (xjk)2

n (cid:88)

Vì vậy ta có :

2 [(xik)2 − (xik)

ss = D2([xi], [xj]) =

k=1

]. (2.9) D2 2N N − 1

N (cid:88)

Chú ý rằng, bằng thực nghiệm, phương sai của biến thành phần thứ k trong tập của N véc tơ dạng được tính bởi:

i=1 N (cid:88)

N (cid:88)

(xik − xik)2 σ2 k = 1 N

2 (xik)

i=1

= (xik)2 − xikxik + 1 N 2 N 1 N

2 = (xik)2 − (xik)

. (2.10)

n (cid:88)

Sau khi thực hiện quá trình rút gọn trên thì ta thu được công thức tính khoảng cách nội cụm Dss xác định như sau:

ss = D2([xi], [xj]) =

k=1

(2.11) D2 σ2 k. 2N N − 1

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.3 Phân cụm trong trường hợp số lớp chưa

biết

2.3.1 Thuật toán sử dụng phương pháp trực quan

Trong trường hợp chưa biết số lớp, từ các véc tơ dạng mẫu đã cho trong tập luyện, ta có thể sử dụng các phương pháp phi thống kê để xây dựng thuật toán phân cụm.

Điểm thiết yếu của thuật toán này là xác định các cụm bằng cách sử

dụng độ đo khoảng cách: Cụm đầu tiên có thể được chọn bất kỳ, giả sử nó có tâm cụm là z1. Khi cụm đầu tiên được chọn, phân loại các véc tơ dạng mẫu vào cụm này nếu khoảng cách từ véc tơ dạng mẫu đó tới tâm cụm z1 là nhỏ hơn một ngưỡng τ đã cho trước. Nếu không thì tạo ra một cụm mới. Mỗi khi có các véc tơ dạng mẫu rơi vào trong một cụm thì giá trị tâm cụm và phương sai của cụm này sẽ được tính lại. Lặp lại quá trình trên cho đến khi tất cả các véc tơ dạng mẫu đã được phân hết vào các cụm.

Thuật toán phân cụm sử dụng phương pháp trực quan:

Dựa trên cơ sở lí thuyết đã trình bày ở trên, chúng ta có thuật toán phân cụm trực quan sẽ được tiến hành theo các bước sau:

• Bước 1: Chọn một véc tơ dạng mẫu đầu tiên làm phần tử đại diện z1 của cụm xuất phát, hay z1 = x1 còn được gọi là tâm cụm đầu tiên.

• Bước 2: Chọn một véc tơ dạng mẫu tiếp theo xi và tính toán khoảng cách của nó tới tất cả các cụm hiện thời (đầu tiên thì chỉ có một cụm), khi đó có các trường hợp sau: a. xi thuộc cụm thứ w là ωw có tâm cụm zw nếu:

0 ≤ θ ≤ 1 (2.12) d(xi, zw) ≤ θτ

trong đó τ là tham số xác định độ thuộc của véc tơ dạng vào cụm thứ i và giá trị của τ được thiết lập từ đầu bởi người thiết kế thủ tục phân cụm b. xi không thuộc cụm ωw nếu:

(2.13) d(xi, zw) > τ

c. Không quyết định xi có thuộc cụm thứ w hay không nếu xi rơi vào

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

vùng trung gian, tức là:

θτ < d(xi, zw) ≤ τ

• Bước 3: Xét các trường hợp sau:

a. Mỗi lần có một giá trị mới xi được phân vào cụm ωw, thuật toán sẽ tính toán lại tâm zw(n + 1) và phương sai Cw(n + 1) của cụm ωw sau hiệu chỉnh này theo các công thức sau:

(2.14) [nzw(n) + xi] zw(n + 1) =

(2.15) Cw(n + 1) = [nCw(n) + (xi − zw(n + 1))2] 1 n + 1 1 n + 1

trong đó n là số véc tơ dạng mẫu đã được phân vào cụm ωw và xi là véc tơ dạng mẫu mới thứ n + 1 của nó, zw(n), Cw(n), tương ứng là tâm cụm và phương sai của cụm có n véctơ dạng mẫu. b. Tạo ra một cụm mới zl nếu:

∀w (2.16) d(xi, zw) > τ

• Bước 4: Lặp lại bước 2 và bước 3 cho đến khi tất cả các véc tơ dạng mẫu của tập luyện được phân vào các cụm. Trong quá trình thực hiện bước 4, có thể xảy ra các kết quả phân cụm ở bước lặp trước bị thay đổi hay một số véc tơ dạng mẫu sẽ được sắp xếp lại theo một trật tự khác.

• Bước 5: Quá trình luyện được coi như hoàn thành nếu tất cả các véc tơ dạng mẫu xi không còn bị thay đổi về sự liên thuộc cụm trong quá trình phân cụm theo cách trên.

Thuật toán này là đơn giản và hiệu quả, nó có những tính ưu

việt sau:

• Thuật toán này đòi hỏi nhu cầu tính toán tối thiểu.

• Các véc tơ dạng mẫu được xử lí liên tiếp và không có nhu cầu bộ nhớ

lớn.

• Thuật toán cho phép xác định số cụm dạng mà không cần thông tin

gì đặc biệt về số cụm.

Mặt khác nó cũng có vài hạn chế khi dùng thuật toán như sau:

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

• Thuật toán này đòi hỏi các véc tơ dạng nếu thuộc cùng một cụm phải có liên kết chặt chẽ với nhau và giữa các cụm vẫn có sự tách biệt khá rõ ràng thì thuật toán mới cho một phân cụm như mong đợi.

• Kết quả phân cụm theo thuật toán sẽ phụ thuộc vào thứ tự xử lí các véc tơ dạng mẫu của tập luyện cũng như vào việc chọn véc tơ dạng mẫu làm tâm cụm đầu tiên.

• Cuối cùng, kết quả phân cụm còn phụ thuộc nhiều vào các giá trị

2.3.2 Thuật toán Batchelor và Wilkins

ngưỡng τ và θ được chọn trong thuật toán.

Batchelor và Wilkins đã đề xuất một phương pháp trực quan khác cho việc phân cụm một tập dữ liệu và phương pháp này còn được gọi là thuật toán cực đại khoảng cách, thuật toán này có thể mô tả ngắn gọn theo các bước sau:

• Bước 1: Chọn x1 làm tâm cụm đầu tiên z1 hay z1 = x1.

• Bước 2: Xác định véc tơ dạng mẫu xa nhất so với x1 và chọn véc tơ

dạng mẫu này làm tâm của cụm thứ hai z2.

• Bước 3: Tính khoảng cách từ các véc tơ dạng mẫu còn lại của tập luyện

đến các tâm cụm vừa hình thành là z1 và z2.

• Bước 4: Tìm min(d(xi, z1), d(xi, z2)), với xi là các véc tơ dạng mẫu của

tập luyện. Lưu lại các giá trị này.

• Bước 5: Tìm max [min(d(xi, z1), d(xi, z2))].

• Bước 6: Nếu khoảng cách max này lớn hơn một phần xác định của khoảng cách giữa tâm của hai cụm: d(z1, z2) thì véc tơ dạng mẫu có giá trị khoảng cách tương ứng vừa đạt giá trị cực đại này được chọn làm tâm của cụm mới, z3. Trường hợp ngược lại thì sẽ dừng thuật toán.

• Bước 7: Lặp lại các Bước 3, Bước 4, Bước 5 và Bước 6, sau khi đã xác định được ba tâm cụm, xác định xem có cần tìm thêm tâm cụm mới nữa không, nếu không thì sẽ dừng và kết thúc thuật toán. Nếu cần tâm cụm mới thì quy về Bước 3, Bước 4, Bước 5 và Bước 6 cho đến khi dừng hẳn thuật toán. Nếu khoảng cách này lớn hơn một phần xác định của khoảng cách giữa các tâm cụm thì mẫu đó sẽ tương ứng với một cụm mới. Nếu không, dừng thuật toán.

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

• Bước 8: Phân cụm các véc tơ dạng mẫu mới về cụm có tâm là zi gần

nó nhất.

Ví dụ áp dụng thuật toán Batchelor và Wilkins:

Cho 10 véc tơ dạng mẫu hai chiều như sau:

(0, 0)T (2, 8)T (1, 2)T (1, 1)T (5, 3)T

(3, 9)T (6, 2)T (6, 3)T (6, 4)T (7, 3)T

Tiến hành tuần tự các bước của thuật toán Bachelor và Wilkins vào bộ

số liệu trên ta có:

• Bước 1: Chọn z1 = x1 = (0, 0)T

• Bước 2: Ta có:

|x6 − z1| > |x2 > z1| > |x10 − z1| > |x9 − z1| > |x8 − z1| > |x7 − z1| >

> |x5 − z1| > |x3 − z1| > |x4 − z1|

Chọn z2 = x6

• Bước 3: So sánh các cặp khoảng cách và có:

| x4 − z1| < |x4 − z2 |

| x3 − z1| < |x3 − z2 |

| x5 − z1| < |x5 − z2 |

| x8 − z2| < |x8 − z1 |

| x7 − z1| < |x7 − z2 |

| x9 − z2| < |x9 − z1 |

|x10 − z2| < |x10 − z1|

[min(d(xi, z1), d(xi, z2))] = d(x8, z2) = d(x8, x6) • Bước 4-5: Tìm max i(cid:54)=1,6

• Bước 6: Kiểm tra điều kiện:

|x8 − z2| > |z2 − z1| 1 2

Chọn z3 = x8

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

• Bước 7: So sánh các khoảng cách d(xi, zk), với k = 1, 2, 3 để tìm

d(xi, zk) và có: min k=1,2,3

| x4 − z1| < |x4 − z3| < |x4 − z2 |

| x3 − z1| < |x3 − z3| < |x3 − z2 |

| x5 − z3| < |x5 − z1| < |x5 − z2 |

| x7 − z3| < |x7 − z1| < |x7 − z2 |

| x9 − z3| < |x9 − z2| < |x9 − z1 |

|x10 − z3| < |x10 − z2| < |x10 − z1|

| x2 − z2| < |x2 − z3| < |x2 − z1|

• Bước 8-9: Lưu lại khoảng cách nhỏ nhất ở bên trái của các bất đẳng thức trên. Chọn giá trị lớn nhất trong những giá trị vừa lưu, và đó là |x3 − z1|

• Bước 10: Kiểm tra điều kiện:

. |x3 − z1| < 1 2 [|z2 − z1| + |z3 − z2|] 2

Vậy điều kiện cho việc thành lập một cụm mới là không thỏa mãn, thuật toán kết thúc.

Kết quả: Với thuật toán trên và ký hiệu Si là tập hợp các phần tử của cụm thứ i. Ta có: S1 = {z1, x4, x3} với z1 = x1

S2 = {z2, x2} với z2 = x6

S3 = {z3, x5, x7, x9, x10} với z3 = x8

Ta có hình vẽ minh họa ví dụ trên:

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Hình 2.1: : Ví dụ minh họa cho thuật toán Batchelor và Wilkins

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.4 Phân cụm trong trường hợp đã biết số

lớp

2.4.1 Thuật toán ISODATA

ISODATA( Iterative Self Organizing Data Analysis Techniques A) là một từ viết tắt cho các kĩ thuật lặp phân tích dữ liệu tự tổ chức. Trong thuật toán này, ta qui ước sử dụng các tham số đầu vào như sau:

M = số cụm mong muốn

η = số lượng véc tơ dạng mẫu tối thiểu có trong một cụm

σs = giá trị cực đại cho phép của độ lệch chuẩn

δ = khoảng cách tối thiểu có thể chấp nhận được giữa các tâm cụm

L = số lượng lớn nhất các cặp tâm cụm được phép gộp lại với nhau.

I = số bước lặp cho phép. Các giá trị này là giá trị đầu vào của thuật toán ISODATA được xác định trước.

Các bước của thuật toán ISODATA:

• Bước 1: Chọn một vài tâm cụm khởi tạo.

• Bước 2: Phân loại véc dạng mẫu vào cụm có véc tơ tâm cụm đã được

chọn trên sao cho đây là véc tơ tâm cụm gần nó nhất.

• Bước 3: Tính toán lại các véc tơ tâm cụm sau khi đã hoàn thành Bước

2 đối với toàn bộ tập luyện.

• Bước 4: Kiểm tra nếu bất kì cụm nào không đủ số véc tơ dạng mẫu

tối thiểu như đã chọn trước thì loại cụm đó.

• Bước 5: Tính toán độ lệch chuẩn cho mỗi miền cụm và kiểm tra xem

nó có lớn hơn giá trị cho phép đã chọn trước không. Nếu có và nếu kiểm tra thấy giá trị trung bình khoảng cách của các véc tơ dạng mẫu trong miền cụm Si tới tâm cụm tương ứng là lớn hơn trung bình chung khoảng cách của các véc tơ mẫu dạng tới tâm cụm tương ứng, đồng thời số véc tơ dạng mẫu trong cụm Si lớn hơn hai lần số véc tơ dạng mẫu tối thiểu cần có trong một cụm thì tách cụm Si này làm hai cụm mới.

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

• Bước 6: Tính các khoảng cách giữa tất cả các cặp tâm cụm. Nếu có một vài cặp cụm có khoảng cách giữa hai tâm cụm nhỏ hơn khoảng cách tối thiểu cho phép đã được chỉ định trước thì lưu lại, và trong số các cặp cụm này, cặp nào có khoảng cách giữa hai tâm cụm nhỏ nhất thì sẽ được kết hợp thành một cụm.

Ta ký hiệu : x = các véc tơ dạng mẫu. Si = miền cụm thứ i zi = tâm cụm thứ i Ni = số véc tơ dạng mẫu trong Si Nc = số tâm cụm được chỉ định trước một cách tùy ý N = tổng số véc tơ dạng mẫu của tập luyện Di = trung bình khoảng cách của các véc tơ dạng mẫu tới tâm cụm trong miền cụm Si D = trung bình chung khoảng cách các véc tơ dạng mẫu tới các tâm cụm hiện thời tương ứng zil, zjl = các tâm cụm được gộp Nil, Njl = số các véc tơ dạng mẫu trong các cụm có tâm tương ứng zil, zjl

Toàn bộ quá trình này có thể được mô tả bằng một sơ đồ khối như hình vẽ sau:

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Hình 2.2: Sơ đồ thuật toán ISODATA

Ví dụ áp dụng thuật toán ISODATA để xét bài toán về 20 véc tơ dạng mẫu 2 chiều trong mục trước:

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10

(0, 0)T (1, 0)T (0, 1)T (1, 1)T (2, 1)T (1, 2)T (2, 2)T (2, 3)T (6, 6)T (7, 6)T

x11 x12 x13 x14 x15 x16 x17 x18 x19 x20

(8, 6)T (6, 7)T (7, 7)T (8, 7)T (9, 7)T (7, 8)T (8, 8)T (9, 8)T (10, 8)T (11, 8)T

Ta giả thiết là thuật toán ISODATA được áp dụng để xử lý tập luyện trên với tham số đầu vào được cho trước như sau:

M = 2 δ = 4

η = 1 L = 0

σs = 1.5 I = 4

Trong trường hợp này, N = 20 và n = 2. Để bắt đầu ta chọn Nc = 1 với tâm cụm đầu tiên là z1 = (0, 0)T . Khi đó chỉ có một tâm cụm, nên cả tập

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

luyện S sẽ có một cụm là:

S1 = {x1, x2, · · · , x20}

x∈S1

(cid:80) x = (5.25, 4.8)T

(cid:48)

Vì N1 = 20 > η = 1 nên không có tập con nào bị loại. Tính tâm cụm này và có: z(cid:48) 1 = 1 20 Tinh D1:

1| = 4.42

x∈S1

(cid:88) |x − z D1 = 1 N1

Tính D .Trong trường hợp này, vì chỉ có một cụm nên:

D = D1 = 4.42

Do Nc = 1 ≤ M/2 = 1, ta tính véc tơ độ lệch tiêu chuẩn của cụm khởi tạo, ta có:

σ1 = (σ11, σ12)T

1 2

(cid:48)

Trong đó:  

11)2

xj∈S1

1 2

(cid:88) = 3.59 σ11 = (xj1 − z   1 N1

(cid:48)

 

12)2

xj∈S1

(cid:88) = 3.02 σ12 = (xj2 − z   1 N1

Vậy có:

1 và z(cid:48)−

1, và vì σ1max = σ11, nên ta tách 1 dọc theo thành phần đầu tiên của

σ1 = (3.59, 3.02)T nên ta có σ1max = 3.59

1 với việc chọn γ = 0.6, γσ1max = 2.15 ta có:

(cid:48)+ 1 = ((5.25 + 2.15), 4.8)T = (7.40, 4.8)T z (cid:48)− 1 = ((5.25 − 2.15), 4.8)T = (3.10, 4.8)T z Nc = 2. Với hai tâm cụm mới nhận được và sử dụng tiêu chuẩn khoảng cách cực tiểu ta sẽ thu được phân cụm cho tập luyện trên vào hai miền cụm mới có tâm tương ứng là z(cid:48)+

1 , cụ thể là:

1 và z(cid:48)−

Vì σ1max > σs và Nc ≤ M/2, nên tách z(cid:48) 1 thành hai tâm cụm mới z(cid:48)+ z(cid:48) véc tơ tâm cụm z(cid:48)

S1 = {x1, x2, x3, · · · , x8}

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

S2 = {x9, x10, x11, · · · , x20}

N1 = 8, N2 = 12.

Vì cả hai giá trị N1, N2 đều lớn hơn η, nên không có tập con nào bị loại. Sau đó, theo thuật toán ta tính lại tâm cụm mới, và thu được:

x∈S1

(cid:88) x = (1.125, 1.25)T z1 = 1 N1

x∈S2

(cid:88) x = (8.00, 7.17)T z2 = 1 N2

Tính trung bình các khoảng cách từ các miền cụm S1 và S2 đến các tâm cụm mới, ta có :

x∈S1

(cid:88) D1 = |x − z1| = 1.14 1 N1

x∈S2

(cid:88) |x − z2| = 1.49. D2 = 1 N2

N (cid:88)

Vì vậy, trung bình chung của các khoảng cách xét trên sẽ là:

j=1

D = NjDj = 1.35. 1 N

Tính khoảng cách giữa hai tâm cụm z1 và z2 là:

D12 = |z1 − z2| = 9.07.

Vì L = 0 nên không cần xét việc gộp các tâm cụm lại. Do yêu cầu số các cụm đã thỏa mãn và khoảng cách giữa các tâm cụm là tương đối lớn so với khoảng cách tối thiểu đã định trước, không cần thiết phải thay đổi tham số. Tính lại các độ lệch tiêu chuẩn của các biến trong véc tơ dạng mẫu ta thu

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

được:

1 2

Với cụm thứ nhất ta có .

σ1 = (σ11, σ12)T  

xj∈S1

1 2

(cid:88) Trong đó = 0.78 . σ11 = (xj1 − z11)2   1 N1

 

xj∈S1

(cid:88) = 0.96 Và . σ12 = (xj2 − z12)2   1 N1

Vậy σ1 = (0.78, 0.96)T .

1 2

Với cụm thứ hai ta có

 σ2 = (σ21, σ22)T . 

xj∈S2

1 2

(cid:88) = 1.47 . Trong đó σ21 = (xj1 − z21)2   1 N2

 

xj∈S2

(cid:88) Và = 0.8 . σ22 = (xj2 − z22)2   1 N2

Vậy . σ2 = (1.47, 0.8)T

Ta có . σ1max = 0.96 < σs

Và . σ2max = 1.47 < σs

Nc ≥ M/2, vì vậy, không cần thực hiên quá trình tách cụm nữa. Kết quả

Áp dụng thuật toán ISODATA cho ví dụ xét trên, ta thu được hai cụm:

S1 = {x1, x2, x3, · · · , x8}

S2 = {x9, x10, x11, · · · , x20}

Với hai tâm cụm tương ứng:

z1 = (1.125, 1.25)T

z2 = (8.00, 7.17)T

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.4.2 Thuật toán ISODATA hiệu chỉnh

Chú ý Nếu σs được chọn trước có giá trị nhỏ và M chọn trước có giá trị lớn hơn, ví dụ M = 3 thì S2 có thể được tách thành 2 cụm mới nữa theo cách làm tương tự như đã xét trên.

Như có thể thấy ở mục trên, trong việc sử dụng thuật toán ISODATA, một số tham số cho quá trình xử lí phải được chỉ định trước, như là số lượng cụm mong muốn, giá trị cực tiểu của độ lệch chuẩn và khoảng cách cực tiểu cho phép đối với các cụm. Để chỉ định được các giá trị này, cần có các nghiên cứu cơ bản về tập luyện trước khi thực hiện thuật toán này. Có thể thấy, hiệu quả của thuật toán sẽ phụ thuộc nhiều vào người sử dụng thuật toán cài đặt tham số này. Mà việc cài đặt hợp lí chỉ có thể thực hiện nhờ một phương pháp vừa thử nghiệm vừa kiểm tra và rút kinh nghiệm. Davies và Bouldin đã đề xuất cách chọn các tham số phân cụm tối thiểu sao cho với các tham số này có thể thu được một phân hoạch tự nhiên của các tập dữ liệu. Họ đưa ra tham số sau:

(2.17) Rij = Dii + Djj Dij

Trong đó Dii và Djj được định nghĩa như là độ phân tán của cụm thứ i và j. Còn Dij là khoảng cách giữa cụm thứ i và cụm thứ j Rõ ràng từ định nghĩa, nếu x1, · · · , xN ∈ S, thì:

(2.18) Dii(x1, · · · , xN ) ≥ 0

(2.19) Dii(x1, · · · , xN ) = 0 khi và chỉ khi xi = xj, ∀xi, xj ∈ S

Các tính chất của tham số R gồm:

(1) Rij(Dii, Djj, Dij) ≥ 0

(2) Rij(Dii, Djj, Dij) = Rji(Dii, Djj, Dji)

(3) Rij(Dii, Djj, Dij) = 0 khi và chi khi Dii = Djj = 0

(4) Nếu Djj = Dkk, Dij < Dik thì Rij(Dii, Djj, Dij) > Rik(Dii, Dkk, Dik)

(5) Nếu Dij = Dik, Djj ≥ Dkk thì Rij(Dii, Djj, Dij) > Rik(Dii, Dkk, Dik)

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Nhận xét + Tính chất đầu tiên và thứ hai chỉ ra rằng hàm R là không âm và có tính đối xứng. + Tính chất thứ ba chỉ ra rằng sự giống nhau giữa các cụm bằng không khi và chỉ khi các sự phân tán của chúng bằng không. + Tính chất thứ tư và thứ năm chỉ ra rằng: nếu khoảng cách giữa các tâm cụm là không đổi trong khi sự phân tán tăng thì hàm tương tự giữa các cụm là tăng. Ngược lại, sự phân tán không đổi trong khi khoảng cách giữa các tâm cụm tăng thì hàm tương tự giữa các cụm là giảm Để bắt đầu, số cụm xuất pháp có thể được chọn là một số lớn, nó có thể được chọn bằng số phần tử của tập luyện. Theo thuật toán ISODATA đưa ra ở mục trên, chúng ta có thể thu được miền cụm cũng như số các véc tơ dạng mẫu được phân bổ tới mỗi cụm đã chỉ định. Dii và Djj có thể được tính theo công thức sau:

Ni(cid:88)

(cid:35) 1 (cid:34)

j=1

|xj − zi| Dii = 1 Ni

k=1

(cid:34) n (cid:35) 1 (cid:88) Dij = |zik − zjk|2

Ở đó zik là thành phần thứ k của cụm i. Rij được tính theo công thức sau:

Rij = Dii + Djj Dij

Cho Nc là số cụm được chọn. Cho một giá trị cụ thể của i, với j = 1, · · · , Nc, j (cid:54)= i. Kí hiệu Ri là giá trị lớn nhất trong số các Rij, nghĩa là:

Ri = Rij max j=1,2,..Nc; j(cid:54)=i

Nc(cid:88)

Và R là giá trị trung bình chung các độ tương tự của mỗi cụm, thì R được tính theo công thức sau:

i=1

(2.20) R = Ri 1 Nc

Các giá trị khác nhau của Nc sẽ cho các kết quả là các giá trị khác nhau của R. Số cụm Nc tương ứng với giá trị nhỏ nhất của R xem như là thích hợp nhất cho việc lựa chọn số cụm chỉ định. Tuy nhiên, không dễ dàng có

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.4.3 Thuật toán K-means

được cách để tìm ra được số lượng thích hợp nhất bằng phương pháp giải tích. Ngoài ra, chúng ta có thể vẽ đồ thị biểu diễn sự liên hệ giữa R và Nc được chọn để tìm ra số cụm Nc nên chọn sao cho tương ứng với giá trị này sẽ thu được giá trị R là nhỏ nhất có thể.

Thuật toán K-means được J.MacQueen trình bày vào năm 1967 sau đó được J.A. Hartigan và M.A.Wong phát triển vào khoảng năm 1975. Ý tưởng của thuật toán này là là phân bổ một tập các véc tơ dạng mẫu S = {xi| xi ∈ Rn, i = 1, · · · , N } vào K cụm dạng {S1, · · · , SK} theo nguyên tắc: véc tơ dạng mẫu đầu vào xi sẽ được xếp vào cụm thứ l nếu khoảng cách từ nó tới tâm của cụm Sl là nhỏ nhất, sau khi phân bổ các véc tơ dạng mẫu vào các cụm tương ứng ta cập nhật lại tâm mỗi cụm. Lặp lại các bước trên đến khi các tâm cụm hội tụ thì dừng. Theo nghĩa trên, thuật toán K-means bao gồm các bước sau:

đầu {zl}K • Bước 1: Xác định trước số cụm K, và khởi tạo các điểm hạt giống ban l=1 (mỗi điểm hạt giống này xem như tâm mỗi cụm ban đầu)

• Bước 2: Tính toán khoảng cách: Đối với mỗi véc tơ dạng xi, (1 ≤ i ≤ N ), tính toán khoảng cách của nó tới mỗi tâm zl (1 ≤ l ≤ K). Sau đó tìm tâm cụm gần nhất với mỗi điểm, tức là với mỗi i = 1, · · · , N ta tìm được:

(2.21) d(xi, zl) = d(xi, zw) min 1≤l≤K

thì phân bổ véc tơ dạng mẫu xi vào cụm có điểm hạt giống zw là: Sw.

• Bước 3: Cập nhật lại điểm hạt giống theo công thức sau:

x∈Sl(k)

(cid:88) x , l = 1, · · · , K (2.22) zl(k + 1) = 1 Nl(k)

trong đó, Sl(k), Nl(k), zl(k) là cụm thứ l, số véc tơ dạng mẫu, và điểm hạt giống tương ứng của nó ở lần lặp thứ k.

Bước 2 và bước 3 được thực hiện lặp lại cho đến khi tất cả các điểm

hạt giống hội tụ.

Quá trình phân cụm bằng thuật toán K-means có thể minh họa bằng việc

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

xử lí một tập luyện hai chiều gồm 20 véc tơ dạng mẫu sau:

(0, 0)T (1, 0)T (0, 1)T (1, 1)T (2, 1)T (1, 2)T (2, 2)T (2, 3)T (6, 6)T (7, 6)T

(8, 6)T (6, 7)T (7, 7)T (8, 7)T (9, 7)T (7, 8)T (8, 8)T (9, 8)T (10, 8)T (11, 8)T

Ta thực hiện các thuật toán với giả thiết cho trước số cụm K = 2 với tập luyện như trên theo các bước sau:

• Bước 1: Chọn 2 véc tơ dạng mẫu bất kì làm tâm của hai cụm khởi tạo

đầu tiên.

z1(1) = x1 = (0, 0)T

(2.23) z2(1) = x2 = (1, 0)T

Số bên trong dấu ngoặc là chỉ số thứ tự bước lặp.

• Bước 2: Phân loại các véc tơ dạng mẫu x vào các miền cụm dựa theo nguyên tắc cực tiểu khoảng cách, và do giả thiết trên có số cụm cho trước K = 2 nên chẳng hạn ta có:

l (cid:54)= 1 x1 ∈ S1(1) khi |x1 − z1(1)| ≤ |x1 − zl(1)| ∀ l = 1, · · · , K;

l (cid:54)= 2 x4 ∈ S2(1) khi |x4 − z2(1)| ≤ |x4 − zl(1)| ∀ l = 1, · · · , K;

(2.24)

ở đây, chỉ số k trong Sl(k) là chỉ số của bước lặp thứ k. Vì vậy, với việc khảo sát tương tự trên các véc tơ của tập luyện S như đối với hai véc tơ x1 và x4 ở trên ta thu được kết quả phân cụm sau bước lặp đầu tiên là:

S1(1) = {x1, x3}

S2(1) = {x2, x4, · · · , x20}.

• Bước 3: Cập nhật lại tâm của các cụm mới theo công thức (2.22):

x∈Sl(k)

(cid:88) x , l = 1, · · · , K zl(k + 1) = 1 Nl(k)

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Cụ thể với số liệu trên, ta có:

x∈S1(1)

  0.0 (cid:88) x = z1(2) = (x1 + x3) =   1 2 1 N1(1) 0.5

x∈S2(1)

  5.83 (cid:88) x = z2(2) = (x2 + x4 + ... + x20) =  .  1 18 1 N2(1) 5.28

Chú ý rằng, các tâm cụm đã được thiết lập là giá trị trung bình của tất cả các véc tơ dạng mẫu nằm trong miền cụm tương ứng sẽ làm giảm thiểu tổng các khoảng cách bình phương từ tất cả các điểm trong Sl(k) tới các tâm cụm mới. Trong trường hợp này, K = 2; N1(1) = 2 và N2(1) = 18 tương ứng là số véc tơ dạng mẫu trong các cụm S1(1) và S2(1)

• Bước 4: Do zl(2) (cid:54)= zl(1), l = 1, 2, nên thuật toán phân cụm chưa dừng, vì vậy chúng ta quay lại Bước 2 và lặp lại các thao tác như trên. Ngược lại, nếu ta thu được zl(2) = zl(1) thì thuật toán dừng.

• Bước 5: Với các tâm cụm mới, chúng ta có:

j = 1, · · · , 8 với |xj − z1(2)| < |xj − z2(2)|

j = 9, · · · , 20. (2.25) với |xj − z2(2)| < |xj − z1(2)|

Vậy ta thu được kết quả phân cụm sau bước lặp thứ 2 là:

S1(2) = {x1, x2, · · · , x8}

S2(2) = {x9, x10, · · · , x20}.

• Bước 6: Cập nhật các tâm cụm:

x∈S1(2)

  1.13 (cid:88) x = z1(3) = (x1 + x2 + · · · + x8) =   1 8 1 N1 1.25

x∈S2(2)

  8.00 (cid:88) x = (x9 + x10 + · · · + x20) = z2(3) =   . 1 12 1 N2 7.17

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

• Bước 7: Quay lại Bước 2, do zl(3) (cid:54)= zl(2), với l = 1, 2.

• Bước 8: Kết quả miền cụm thu được cũng giống với kết quả trước đó,

nghĩa là:

S1(3) = S1(2), S2(3) = S2(2)

• Bước 9: Do zl(4) = zl(3), l = 1, 2 nên thuật toán hội tụ. Kết quả các

tâm cụm cuối cùng chúng ta thu được là:

    8.00 1.13 (2.26) z1 =    , z2 =  7.17 1.25

Nhận xét:

Từ các bước tính toán trên, ta có thể thấy rằng các tâm cụm được cập

nhật liên tục.

Hiệu quả của thuật toán này phụ thuộc vào số lượng các tâm cụm ban đầu được chọn và phụ thuộc vào thứ tự các véc tơ dạng mẫu được xử lý trong thuật toán. Nó cũng phụ thuộc vào dạng biểu diễn hình học của tập dữ liệu được phân tích.

Thuật toán K-means trên đã được chứng minh là hội tụ và có độ phức tạp tính không cao vì vậy việc phân tích phân cụm là khá đơn giản nên có thể áp dụng đối với tập dữ liệu lớn.

Mặc dù thuật toán K-means áp dụng rộng rãi trong xử lý ảnh, nhận

dạng, v.v , nhưng nó có ba nhược điểm chính:

• Chỉ thực hiện phân cụm được các cụm dữ liệu có dạng hình cầu vì

thuật toán dựa vào độ đo khoảng cách Euclide.

• Nếu một số điểm hạt giống được khởi tạo khá xa so với các điểm hạt giống khác trong tập dữ liệu đầu vào thì các điểm này không có bất kỳ cơ hội nào được xét đến trong toàn bộ quá trình thực hiện thuật toán và vì vậy chúng được gọi là các điểm chết.

• Thuật toán K-means cần được xác định trước số nhóm K. Khi K được chọn "tốt" thì thuật toán K-means có thể tìm kiếm được chính xác tâm cụm như đã chỉ ra ở hình (2.3b). Nếu không nó sẽ dẫn đến một kết quả phân cụm không đúng như mô tả trong hình (2.3a) và (2.3c), nơi một số zl không ở đúng vị trí tâm cụm tương ứng, thay vào đó chúng ở một trong những điểm biên giữa các cụm khác nhau hoặc ở tại các điểm lệch so với tâm cụm.

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Hình 2.3: Kết quả thuật toán K-means khi chọn: a) K=1 ;b) K=2; c) K=3

2.5 Thuật toán K*-means

Trong mục này, chúng ta sẽ giới thiệu một mở rộng của thuật toán K-means bằng cách sử dụng thêm thông tin về các ma trận hiệp phương sai của các cụm được hình thành trong quá trình phân cụm, do đó thuật toán này có thể làm việc trên cả các tập dữ liệu hình elip cũng như hình cầu.

Thuật toán phân cụm cải biên này có tên là K*-means ( STep-wise Automatic Rival-penalised K-means hay STAR K-means). Đây là thuật toán tổng quát của K-means, nhưng đã khắc phục được ba nhược điểm nêu trên của thuật toán K-means. Thuật toán K*-means bao gồm hai bước riêng biệt, bước thứ nhất là một thủ tục tiền xử lý cho phép gán mỗi cụm ít nhất một điểm hạt giống, bước thứ hai là điều chỉnh các điểm hạt giống mỗi khi một dữ liệu đầu vào xi được xếp vào cụm có điểm hạt giống này đại diện và đồng thời phạt các điểm hạt giống còn lại thông qua việc điều chỉnh các trọng số của các cụm tương ứng của chúng.

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.5.1 Độ đo cho phân cụm dữ liệu

Giả sử tập dữ liệu đầu vào S = {xi| xi ∈ Rn, i = 1, · · · , N } gồm các

K ∗ (cid:88)

véc tơ dạng có cùng chung mật độ trộn chuẩn n chiều sau:

l G(x|z∗ α∗ l ,

l=1

) (2.27) p∗(x; Θ∗) = (cid:88)∗ l

K ∗ (cid:88)

với:

l = 1, và α∗ α∗

l ≥ 0 khi 1 ≤ l ≤ K ∗

l=1

l , z∗

l , (cid:80)∗

(2.28)

trong đó, K ∗ là số các cụm thực sự của tập dữ liệu. l )|1 ≤ l ≤ K ∗} là tập các tham số thực sự, và G(x|z, (cid:80)) Θ∗ = {(α∗ là mật độ chuẩn n chiều có véctơ trung bình z (cũng được gọi là những điểm hạt giống) và hiệp phương sai (cid:80). Trong biểu thức (2.27) thì cả K ∗ và Θ∗ đều chưa biết và cần được ước lượng. Do đó ta có mô hình ước lượng cho bộ các tham số trên được xác định theo hàm mật độ sau:

K (cid:88)

l=1

(cid:88) ) (2.29) p(x; Θ) = αlG(x|zl,

K (cid:88)

với

l=1

(2.30) αl = 1, và αl ≥ 0 khi 1 ≤ l ≤ K

trong đó, K là một ước lượng của K ∗, Θ = {(αl, zl, (cid:80) l)|1 ≤ l ≤ K} là một ước lượng của Θ∗. Chúng ta đo khoảng cách giữa các mật độ p∗(x; Θ∗) và p(x; Θ) bằng hàm phân kỳ Kullback-Leibler ( Kullback-Leibler divergence function ) sau:

(cid:90) Q(x; Θ) = p∗(x; Θ∗)ln dx (2.31) p∗(x; Θ∗) p(x; Θ)

K (cid:88)

(cid:90) = p(l|x)p∗(x; Θ∗)ln dx p∗(x; Θ∗) p(x; Θ)

l=1 K (cid:88)

l=1

(cid:90) dx. (2.32) = p(l|x)p∗(x; Θ∗)ln p(l|x)p∗(x; Θ∗) αlG(x|zl, (cid:80) l)

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Trong đó:

p(l|x) = , 1 ≤ l ≤ K. (2.33) αlG(x|zl, (cid:80) l) p(x; Θ)

Ở đây, p(l|x) là hàm xác suất hậu nghiệm của cụm dạng thứ l khi giả thiết quan sát được một véc tơ đầu vào x. Có thể thấy rằng, bài toán cực tiểu biểu thức (2.32) tương đương với bài toán cực đại hàm hợp lý (Maximum Likelihood-ML) của Θ, tức là cực tiểu biểu thức (2.33), trong khi thực tế (cid:82) p∗(x; Θ∗)lnp∗(x; Θ∗)dx là một hằng số không liên quan tới Θ. Cần lưu ý rằng, biểu thức (2.27) và (2.29) là hai mô hình có thể nhận dạng được nghĩa là p∗(x; Θ∗) = p(x; Θ) nếu và chỉ nếu Θ∗ = Θ. Vì vậy, khi cho K ≥ K ∗, thì Q(x; Θ) sẽ đạt giá trị nhỏ nhất khi Θ = Θ∗, tức là: p∗(x; Θ∗) = p(x; Θ). Do đó biểu thức (2.32) là độ đo thích hợp cho phân cụm dữ liệu theo ý nghĩa của hàm mục tiêu p(l|x).

Ở đây, chúng ta ưu tiên thực hiện phân cụm dựa trên nguyên tắc người thắng cuộc sẽ được tất cả ("winner-take-all"). Có nghĩa là, chúng ta xếp một véc tơ đầu vào x vào cụm thứ l nếu I(l|x) = 1, trong đó

p(r|x)   1 nếu l = w = arg max 1≤r≤K . (2.34) I(l|x) =

0 nếu ngược lại 

Điều đó đúng theo nguyên lý phân loại Bayes:

p(r|x). x ∈ Sw nếu p(w|x) = max 1≤r≤K

P (r)p(x|r) và do các biểu thức của p(r|x) có cùng p(x)

1 αlp(x|r) nên bài toán max 1≤r≤K

p(r|x) Nhưng do p(r|x) = chung một mẫu số là p(x) = (cid:80)K

P (r)p(x|r) tương đương với bài toán max 1≤r≤K

r) và có hàm mật

ln(P (r)p(x|r)) tương đương bài toán max 1≤r≤K

Mặt khác do giả thiết nếu véc tơ x ∈ Sr thì x ∼ N(zr, (cid:80) độ sau:

r | 1

(cid:104) p(x|r) = exp − . (x − zr)T (cid:88)−1 (cid:105) (x − zr) 1 2 1 2 | (cid:80) (2π) n

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Vì vậy với ký hiệu lnP (r) = ln(αr) ta sẽ có biểu diễn sau:

ln(P (r)p(x|r)) = max 1≤r≤K

r | −

n 1 1 ln(2π) − ln| (cid:80) . (cid:104) ln(αr) − (x − zr)T (cid:80)−1 (cid:105) r (x − zr) max 1≤r≤K 2 2 2

n Nhưng do p(r|x) trở thành bài

r (x − zr) + ln(| (cid:80)

2 (cid:104) . toán min 1≤r≤K

ln(2π) là hằng số, nên bài toán max 1≤r≤K (cid:105) (x − zr)T (cid:80)−1 r |) − 2ln(αr) Khi đó hàm mục tiêu (2.34) sẽ có dạng tương đương sau:

ρr   1 nếu l = w = arg min 1≤r≤K . (2.35) I(l|x) =

0 nếu ngược lại 

r | = | (cid:80)−1

r | = −ln| (cid:80)−1

|−1 nên ta có ln| (cid:80) | vì

Trong đó, với lưu ý là | (cid:80) vậy ta có thể đặt:

. (2.36) (cid:105) |) − 2ln(αr) (x − zr) − ln(| ρr = (cid:104) (x − zr)T (cid:88)−1 (cid:88)−1 r

Vì vậy, bài toán cực tiểu biểu thức (2.32) sẽ tương đương với bài toán cực tiểu biểu thức sau:

K (cid:88)

l=1

(cid:90) dx. (2.37) R(x; Θ) = I(l|x)p∗(x; Θ∗) × ln I(l|x)p∗(x; Θ∗) αlG(x|zl, (cid:80) l)

N (cid:88)

K (cid:88)

Khi đó, nếu N đủ lớn, dựa vào luật số lớn ta có thể đơn giản hóa biểu thức trên như sau:

i=1

l=1

(cid:88) (2.38) )]. I(l|xi) × ln[αlG(xi|zl, R(x1, · · · , xN ; Θ) = H − 1 N

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

i=1 lnp∗(xi; Θ∗) là một hằng số không liên quan tới Θ.

N × (cid:80)N Ở đây, H = 1 Thật vậy, từ biểu thức (2.37) ta có:

K (cid:88)

(cid:90) R(x; Θ) = I(l|x)p∗(x; Θ∗) × ln dx I(l|x)p∗(x; Θ∗) αlG(x|zl, (cid:80) l)

l=1 K (cid:88)

(cid:90) = I(l|x)p∗(x; Θ∗)ln[I(l|x)p∗(x; Θ∗)]dx

l=1 K (cid:88)

l=1

(cid:90) (cid:88) − )]dx. I(l|x)p∗(x; Θ∗)ln[αlG(x|zl,

Trong đó số hạng đầu có: I(l|x) = 1 tại l = w và I(l|x) = 0 với ∀l (cid:54)= w và l = 1, · · · , K.

Vì vậy số hạng này theo luật số lớn sẽ có dạng sau:

N (cid:88)

i=1

(cid:90) p∗(x; Θ∗)ln(p∗(x; Θ∗))dx = E(ln(p∗(x; Θ∗))) ≈ ln(p∗(xi; Θ∗)) 1 N

Còn số hạng thứ hai (không kể dấu) cũng theo luật số lớn sẽ có dạng tương ứng như sau:

K (cid:88)

l=1 (cid:90)

(cid:90) (cid:88) )]dx I(l|x)p∗(x; Θ∗)ln[αlG(x|zl,

K (cid:88)

l=1

K (cid:88)

(cid:88) )]dx = p∗(x; Θ∗) I(l|x)ln[αlG(x|zl,

l=1 N (cid:88)

K (cid:88)

(cid:88) =E(cid:2) )](cid:3) I(l|x)ln[αlG(x|zl,

i=1

l=1

(cid:88) ≈ )]. I(l|x)ln[αlG(xi|zl, 1 N

Vì vậy ta thu được công thức xấp xỉ cho hàm R(x; Θ) bởi R(x1, · · · , xN ; Θ) đã được cho ở công thức (2.38).

Trước khi kết thúc mục này, có hai điểm cần lưu ý:

Thứ nhất là: Biểu thức (2.38) có thể suy biến thành hàm sai số trung bình bình phương (mean square error -MSE ) nếu như tất cả αl nhận giá trị bằng 1/K và các ma trận hiệp phương sai (cid:80) l là giống nhau. Trong

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.5.2 Thuật toán K*-means

trường hợp đó, phân cụm dựa trên biểu thức (2.35) thực sự là thuật toán K-means thông thường. Thứ hai là: Thành phần ln(αr) với r (cid:54)= w trong biểu thức (2.36) sẽ tự động bị giảm xuống để thỏa mãn biểu thức (2.30) về tổng các ràng buộc của các trọng số αl. Nghĩa là khi trọng số αw được điều chỉnh tăng (do véc tơ xi được xếp vào cụm thứ w) thì để thỏa mãn điều kiện (2.30) các trọng số αl, l (cid:54)= w, l = 1, · · · , K còn lại sẽ phải được điều chỉnh giảm tương ứng.

Từ những kết quả ở mục trên, chúng ta biết rằng việc phân cụm dữ liệu dựa theo điều kiện trong (2.35) có thể tự động "phạt" các điểm hạt giống phụ mà không cần thêm bất cứ sự hiệu chỉnh nào khác. Vì vậy, thuật toán K*-means được chia thành hai bước riêng biệt. Bước thứ nhất sẽ gán cho mỗi cụm ít nhất một điểm hạt giống và bước thứ hai có nhiệm vụ thiết lập tập các tham số Θ thông qua cực tiểu biểu thức (2.38) trong khi quá trình phân cụm các dữ liệu được thực hiện thông qua biểu thức (2.35).

Các bước của thuật toán K*-means được mô tả như sau:

Bước 1: Chúng ta giả sử số cụm khởi tạo là K với K ≥ K ∗, ký hiệu K điểm hạt giống là z1, z2, · · · , zK và giả sử là các điểm này được chọn ngẫu nhiên từ tập luyện S đã cho.

Bước 1.1: Nhặt ngẫu nhiên một điểm dữ liệu từ tập luyện, và với

l = 1, · · · , K, đặt:

1 nếu l = w = argminrλr||xi − zr||   . (2.39) ul =

0 nếu ngược lại 

r=1 nr, với nr là tần số xuất hiện ur = 1; r = 1, · · · , K

Ở đây, λr = nr/ (cid:80)K

Bước 1.2: Cập nhật lại các điểm hạt giống zw bởi công thức sau:

w = zold znew

w + η(xi − zold

w ).

(2.40)

Tiến hành lặp lại các bước 1.1 và 1.2 cho đến khi dãy K giá trị thu được về các ul; l = 1, · · · , K ở bước lặp sau là không thay đổi với tất cả các xi ∈ S. Sau đó chuyển sang bước 2. Ở các bước trên, chúng ta không sử

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

dụng đến các thông tin về các ma trận hiệp phương sai khi xét các biểu thức (2.39) và (2.40) vì các bước này đơn thuần ta chỉ nhằm mục đích định vị các miền cụm với các điểm hạt giống tương ứng. Do đó, để đơn giản tính toán chúng ta đã bỏ qua thông tin về các hiệp phương sai.

r là ma trận hiệp phương sai của các điểm dữ liệu với ur = 1 ( hay của véc tơ dạng thuộc cụm Sr). Dưới dây, chúng ta sẽ ước lượng αr, zr và (cid:80) r nhằm cực tiểu hóa biểu thức (2.38) ( hay tương đương nhằm cực tiểu hóa biểu thức (2.32))

Bước 2: Khởi tạo các αr = 1/K với r = 1, · · · , K và cho (cid:80)

Bước 2.1: Cho một điểm dữ liệu xi, tính I(l|xi) bằng công thức (2.35). Bước 2.2: Cập nhật lại các điểm hạt giống zw mỗi khi có một véc tơ

w = zold znew

w − η

dạng xi được xếp vào miền cụm Sw theo công thức sau:

(cid:12) (cid:12) (cid:12)zold

w ).

w + η

w trong biểu thức

(2.41) = zold (xi − zold ∂R ∂zw (cid:88)−1 w

Hoặc đơn giản bằng biểu thức (2.40) với việc bỏ đi (cid:80)−1 (2.41). Như vậy, chúng ta đã cập nhật lại zw theo hướng giảm gradient.

w. Việc này thực hiện được bằng việc làm cực tiểu biểu thức (2.38) với các ràng buộc về αr được xác định ở biểu thức (2.30). Ta có nhận xét là bộ trọng số αl có thể chọn để thỏa mãn điều kiện (2.30) theo cách sau:

Ngoài ra, ta còn phải cập nhật các tham số αr và (cid:80)

, 1 ≤ r ≤ K. (2.42) αr = (cid:80)K exp(βr) r=1 exp(βr)

w = βold βnew

w − η

Ở đây, các ràng buộc về αr tự động được thỏa mãn, nhưng các biến mới là βr lại có thể chọn được tùy ý. Do đó, thay vì cập nhật αr ta có thể cập nhật ước lượng cho βnew bởi công thức sau:

∂R ∂βw

w ).

= βold (2.43) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)βold w + η(1 − αold

Còn các giá trị βr khác không thay đổi. Theo cách này ta thấy chỉ có αw được điều chỉnh tăng trong khi các αr khác sẽ bị giảm tương ứng. Ở đây, cần chú ý rằng, mặc dù các αr là dần dần hội tụ nhưng biểu thức (2.43) luôn tính toán các giá trị β theo chiều tăng lên mà không có cận trên, khi

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

thực tế αw luôn nhỏ hơn 1. Để tránh xảy ra trường hợp không mong muốn này, một phương pháp khả thi là trừ đi một hằng số dương cβ từ tất cả các giá trị βr khi giá trị lớn nhất của các βr đạt đến giá trị ngưỡng dương đã xác định trước.

w sẽ được thực hiện theo công thức sau:

Còn việc cập nhật (cid:80)

(2.44) = (1 − ηs) +ηsUiU T i (cid:88)new w (cid:88)old w

l nên để giảm nhẹ tính toán, thay vì ước lượng cho (cid:80)

Ở đó Ui = xi − zold w , và ηs là một hệ số tỷ lệ khá bé được chọn trước. Nói chung, việc ước lượng ma trận hiệp phương sai là nhạy cảm hơn so với việc ước lượng các tham số khác.

Từ nhận xét là các công thức ước lượng (2.36) và (2.41) chỉ sử dụng w ta w theo công thức truy giá trị của (cid:80)−1 có thể thực hiện ước lượng trực tiếp cho ma trận (cid:80)−1 hồi sau:

(cid:35) (cid:34)

. (2.45) I − = (cid:88)−1(new) w (cid:80)−1(old) w 1 − ηs Ui ηsUiU T i 1 − ηs + ηsU T i (cid:80)−1(old) w (cid:80)−1(old) w

Trong đó I là một ma trận đơn vị cùng cấp với (cid:80)−1 w .

Bước 2.1 và 2.2 tiến hành lặp lại cho đến khi dãy K giá trị thu được về I(l|xi) với l = 1, · · · , K ở bước lặp sau không thay đổi với tất cả các giá trị xi ∈ S thì thuật toán kết thúc.

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.6 Kết quả thực nghiệm

Chúng ta giới thiệu 2 ví dụ để minh họa cho hiệu quả của thuật toán K*-means đã được xét trong tài liệu ([3]). Ở thí dụ thứ nhất, với việc sử dụng 1000 véc tơ dạng mẫu được mô phỏng từ hàm mật độ trộn chuẩn xác định bởi ba phân phối chuẩn như sau:

   (cid:35) (cid:34) 0.1 0.05 p(x) = 0.3G x   

  0.05 0.2   1  , 1  (cid:35) (cid:34) 0.1 0 1 + 0.4G   ,   0 0.1 5

    (cid:35) (cid:34) 0.1 −0.05 5 (2.46) + 0.3G   ,   −0.05 0.1 5 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) x (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) x (cid:12) (cid:12)

Như đã chỉ ra ở hình(2.4a) thì tập luyện này có K ∗ = 3 cụm riêng biệt. Để chạy thuật toán K*-means tác giả đã xuất phát với K=6 điểm hạt giống được chọn ngẫu nhiên từ tập luyện gồm 1000 véc tơ dạng mẫu trên và chọn các hệ số hiệu chỉnh là η = 0.001 và ηs = 0.0001. Sau bước 1 của thuật toán K*-means, mỗi cụm được phân ít nhất một điểm hạt giống như đã chỉ ra trong hình(2.4b). Sau đó, chúng ta thực hiện bước 2 của thuật toán, kết quả thu được có α1, α5, α6 lần lượt hội tụ đến 0.2958, 0.3987, 0.3055 trong khi các giá trị α2, α3, α4 hội tụ về 0. Do đó, như đã chỉ ra ở hình(2.4c) 3 cụm được nhận biết rất tốt với:

    0.0968 0.0469 1.0087 (cid:88) = z1 =    ,  0.0469 0.1980 0.9738

    0.9757 0.0919 0.0016 (cid:88) = z5 =   ,   4.9761 0.0016 0.0908

    5.0163 0.1104 −0.0576 (cid:88) = (2.47) z6 =   ,   5.0063 −0.0576 0.1105

Trong khi những điểm hạt giống phụ z2, z3, và z4 bị đẩy về phía biên của những cụm tương ứng của chúng. Ta có hình vẽ mô tả kết quả của thuật toán trong ví dụ thứ nhất theo các bước như sau:

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Hình 2.4: Ví dụ thứ nhất với tập luyện gồm 1000 véc tơ dạng mẫu

Trong ví dụ thứ 2, tác giả sử dụng 2000 véc tơ dạng mẫu và cũng được mô phỏng từ hàm mật độ trộn chuẩn p(x) xác định bởi ba hàm phân phối

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

chuẩn như sau:

    (cid:35) (cid:34) 0.15 0.05 1 p(x) = 0.3G   ,  

 0.05 0.25   1  (cid:35) (cid:34) 0.15 0 1 + 0.4G    ,  0 0.15 2.5

    (cid:35) (cid:34) 0.15 −0.1 2.5 (2.48) + 0.3G    ,  −0.1 0.15 2.5 (cid:12) (cid:12) (cid:12) x (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) x (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) x (cid:12) (cid:12)

Tuy nhiên tập dữ liệu thu được có sự chồng xếp các cụm dạng như được mô tả trong hình ( 2.5a). Tương tự, đầu tiên tác giả thực hiện bước 1 của phương pháp K*-means, là 6 điểm hạt giống được phân bổ vào 3 cụm như hình vẽ (2.5b). Sau đó tác giả thực hiện bước 2, kết quả thu được α2 = 0.3879, α3 = 0.2925, và α6 = 0.3196 trong khi α1, α4, α5 hội tụ về 0 như hình vẽ (2.5c). Do đó, ta có kết quả như sau:

    0.9491 0.1252 0.0040 (cid:88) = z2 =   ,   2.4657 0.0040 0.1153

    0.1481 0.0494 1.0223 (cid:88) = z3 =    ,  0.0494 0.2189 0.9576

    0.1759 −0.1252 2.5041 (cid:88) (2.49) = z6 =     , −0.1252 0.1789 2.5161

Kết quả cho thấy việc áp dụng thuật toán K*-means không chỉ cho phép nhận dạng các cụm có cấu trúc cụm phân biệt hoàn toàn với nhau (như ở ví dụ 1) mà kể cả khi các cụm dạng có cấu trúc chồng xếp lên nhau (như ở ví dụ 2), chúng ta vẫn có thể đạt đến một phân cụm hợp lý cho tập dữ liệu đó. Ta có hình vẽ mô tả kết quả của thuật toán trong ví dụ thứ hai theo các bước như sau:

Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Hình 2.5: Ví dụ thứ hai với tập luyện gồm 2000 véc tơ dạng mẫu

Chương 3

Chương trình ứng dụng

thuật toán ISODATA

3.1 Nêu lại ví dụ:

Cho một tập dữ liệu gồm 20 véc tơ dạng mẫu:

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10

(0, 0)T (1, 0)T (0, 1)T (1, 1)T (2, 1)T (1, 2)T (2, 2)T (2, 3)T (6, 6)T (7, 6)T

x11 x12 x13 x14 x15 x16 x17 x18 x19 x20

(8, 6)T (6, 7)T (7, 7)T (8, 7)T (9, 7)T (7, 8)T (8, 8)T (9, 8)T (10, 8)T (11, 8)T

Dựa vào thuật toán ISODATA hãy thực hiện phân cụm đối với bộ dữ liệu trên.

3.2 Các trường hợp tính toán

(cid:70) Trường hợp 1: Các giá trị đầu vào: M = 2, δ = 4, η = 1, L = 0, σs = 1.5, I = 4, γ = 0.6 :. Ta có bảng:

Tóm tắt lại các bước tính toán: Bước lặp 1:

Chương 3. Chương trình ứng dụng thuật toán ISODATA

• Chọn: z1 = x1 = (0, 0)T

• Tính toán lại tâm cụm, ta được: z1 = (5.25, 4.8)T

• Độ lệch tiêu chuẩn σ1 = (3.59, 3.027)T nên σ1max = 3.59

Ta có σ1max > σs nên tách z1 theo thành phần thứ nhất với giá trị γ = 0.6 ta thu được hai tâm mới: z1 = (7.404, 4.8)T , z2 = (3.096, 4.8)T .

Bước lặp 2:

• Với hai tâm cụm: z1 = (7.404, 4.8)T , z2 = (3.096, 4.8)T , ta phân bố các véc tơ dạng mẫu vào các miền cụm dựa theo nguyên lý cực tiểu khoảng cách, tức là véc tơ dạng mẫu gần tâm cụm nào nhất thì được phân vào cụm tương ứng có tâm cụm đó. Do đó ta thu được hai miền cụm mới: S1 = {x9, x10, · · · , x20} và S2 = {x1, x2, · · · , x8}

• Tính lại các tâm cụm, ta được: z1 = (8, 7.17)T và z2 = (1.125, 1.25)T :

Độ lệch chuẩn của cụm 1: σ1 = (1.472, 0.799) nên σ1max = 1.472 Độ lệch chuẩn của cụm 2: σ2 = (0.78, 0.97) nên σ2max = 0.97 Do σs = 1.5 nên σ1max < σs và σ2max < σs: giữ nguyên các tâm cụm.

Kết quả: Ta thu được hai cụm có tâm cụm là: z1 = (8, 7.17)T và z2 = (1.125, 1.25)T với các miền cụm tương ứng là:

S1 = {x9, x10, · · · , x20} và S2 = {x1, x2, · · · , x8}

Ta có bảng hiển thị kết quả thuật toán:

(cid:70) Trường hợp 2:

Chương 3. Chương trình ứng dụng thuật toán ISODATA

Hình 3.1: Trường hợp 1: Kết quả thuật toán với thông số đầu vào ban đầu

Nếu giữ nguyên một số giá trị đầu vào ở trường hợp 1, nhưng thay đổi giá trị M = 4 và giá trị σs = 0.9. Ta có bảng sau:

• Do σ1 = (1.472, 0.799) và σ2 = (0.78, 0.97)T có σ1max > σs và σ2max > σs nên áp dụng thuật toán ta tiếp tục chia 2 cụm trên thành 4 cụm với các tâm cụm mới:

z1 = (8.883, 7.167)T , z2 = (7.117, 7.167)T z3 = (1.125, 1.831)T , z4 = (1.125, 0.669)T

Chương 3. Chương trình ứng dụng thuật toán ISODATA

• Với bốn tâm cụm mới trên, ta thực hiện phân bố lại các véc tơ dạng mẫu vào các miền cụm tương ứng với bốn tâm cụm trên, ta được bốn miền cụm như sau:

S1 = {x15, x18, x19, x20}, S2 = {x9, x10, x11, x12, x13, x14, x16, x17}

S3 = {x6, x7, x8}, S4 = {x1, x2, x3, x4, x5}

• Cập nhật lại các tâm cụm ta thu được bốn tâm cụm tương ứng:

z1 = (9.75, 7.75)T , z2 = (7.125, 6.875)T

z3 = (1.67, 2.33)T , z4 = (0.8, 0.6)T

Ta có bảng hiển thị kết quả thuật toán:

Hình 3.2: Trường hợp 2: Kết quả thuật toán khi thay M = 4 và σs = 0.9

(cid:70) Trường hợp 3:

Nếu thay đổi giá trị của L (ví dụ L=1, tức là số cặp cụm tối đa có thể được gộp là 1). Ta có bảng:

• Khi đó, khoảng cách giữa các tâm cụm sẽ là:

D12 = 2.77, D13 = 9.73, D14 = 11.46, D23 = 7.10, D24 = 8.91, D34 = 1.94

Chương 3. Chương trình ứng dụng thuật toán ISODATA

Ta thấy các giá trị của D12 < σ và D34 < σ. Do L=1 nên ta chọn ra giá trị nhỏ nhất giữa D12 và D34 là D34, do vậy ta gộp cụm thứ 3 và cụm thứ 4 thành một cụm.

• Ba miền cụm mới là:

S1 = {x15, x18, x19, x20} và S2 = {x9, x10, x11, x12, x13, x14, x16, x17} và S3 = {x1, x2, x3, x4, x5, x6, x7, x8}

• Tương ứng là ba tâm cụm mới:

z1 = (9.75, 7.75)T , z2 = (7.125, 6.875)T , z3 = (1.125, 1.25)T

Ta có bảng hiển thị kết quả của thuật toán:

Hình 3.3: Trường hợp 3: Kết quả thuật toán khi thay L=1

Chương 3. Chương trình ứng dụng thuật toán ISODATA

(cid:70) Trường hợp 4: Các giá trị đầu vào như ở trên, ta chỉ thay đổi δ sao cho δ < 1.94, chẳng hạn chọn δ = 1.5.Ta có bảng số liệu đầu vào

Do δ < Dij ∀i (cid:54)= j, i, j = 1, 2, 3, 4 nên không có cụm nào bị gộp, vậy ta vẫn có bốn cụm như trường hợp 2:

S1 = {x15, x18, x19, x20}, S2 = {x9, x10, x11, x12, x13, x14, x16, x17}

S3 = {x6, x7, x8}, S4 = {x1, x2, x3, x4, x5}

Với các tâm cụm tương úng:

z1 = (9.75, 7.75)T , z2 = (7.125, 6.875)T

z3 = (1.67, 2.33)T , z4 = (0.8, 0.6)T

Ta có bảng hiển thị kết quả thuật toán sau:

Chương 3. Chương trình ứng dụng thuật toán ISODATA

Hình 3.4: Trường hợp 4: Kết quả thuật toán khi thay δ = 1.5

Kết luận

Qua luận văn này, chúng tôi đã đề cập đến 3 nội dung chính sau: Khái quát chung về nhận dạng, tìm hiểu một số thuật toán phân tích phân cụm và chương trình minh họa thuật toán ISODATA.

Qua việc xây dựng và chạy thử chương trình ISODATA với các bộ số liệu khác nhau, chúng tôi nhận thấy rằng: bên cạnh việc phân cụm một cách linh động và khá hiệu quả, thì kết quả của thuật toán ISODATA lại phụ thuộc rất nhiều vào các giá trị đầu vào được chỉ định trước như: số cụm mong muốn, giá trị cực tiểu cho phép của độ lệch chuẩn hay khoảng cách tối thiểu giữa hai tâm cụm có thể chấp nhận. Số cụm thu được có thể sẽ tăng lên nếu giảm giá trị cực tiểu cho phép của độ lệch chuẩn để có thể thỏa mãn điều kiện tách cụm. Hoặc số cụm thu được có thể được sẽ giảm đi nếu tăng số cặp cụm tối đa có thể được gộp hoặc tăng giá trị của khoảng cách tối thiểu giữa hai tâm cụm có thể chấp nhận được để thỏa mãn điều kiện gộp cụm. Để chỉ định các giá trị này, cần đến một nghiên cứu cơ bản trước khi thực hiện thuật toán.Vì vậy, việc cài đặt hợp lý chỉ có thể thực hiện được nhờ một phương pháp vừa chạy vừa thử nghiệm lỗi. Đồng thời, việc giới thiệu thuật toán K*-means và các kết quả thực nghiệm của nó đã chứng tỏ được đó là một thuật toán rất linh động hiệu quả, nhưng việc lập trình để minh họa kết quả cho thuật toán đó là một bài toán tương đối phức tạp đòi hỏi kiến thức khá sâu rộng về lĩnh vực toán và tin học.

Do thời gian và trình độ còn hạn chế nên luận văn mới chỉ dừng lại ở mức tìm hiểu một số thuật toán phân cụm và xây dựng chương trình minh họa một thuật toán với các số liệu khác nhau. Trong thời gian tới, nếu điều kiện cho phép, chúng tôi sẽ nghiên cứu, tìm hiểu và cải thiện các thuật toán để có thể đưa ra một kết quả có tính ứng dụng thực tiễn hơn. Trong quá trình thực hiện luận văn chắc chắn không tránh khỏi sai sót. Chúng tôi rất mong muốn nhận được những ý kiến đóng góp của các thầy cô và bạn bè để hoàn thiện luận văn tốt hơn. Xin chân thành cảm ơn.