intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:64

Thêm vào BST
Báo xấu
107
lượt xem 19
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn có kết cấu gồm 3 chương. 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. Chương 2 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. 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. 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 Khái niệm về dạng và nhận dạng . . . . . . . . . . . . . . 1 1.1.1 Khái niệm về dạng, lớp dạng . . . . . . . . . . . . . 1 1.1.2 Khái niệm nhận dạng: . . . . . . . . . . . . . . . . 2 1.2 Không gian mẫu và cách tiếp cận nhận dạng . . . . . . . . 2 1.3 Một số ứng dụng của nhận dạng: . . . . . . . . . . . . . . 5 1.3.1 Nhận dạng giọng nói . . . . . . . . . . . . . . . . . 6 1.3.2 Nhận dạng chữ viết tay . . . . . . . . . . . . . . . 7 1.3.3 Dự báo thời tiết . . . . . . . . . . . . . . . . . . . . 7 1.3.4 Phân tích điện tâm đồ để chẩn đoán hoạt động của tim . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.5 Phân tích y học bằng chụp tia X-quang . . . . . . . 8 1.3.6 Làm rõ các bức ảnh chụp từ vệ tinh và khoảng không 8 1.4 Học có hướng dẫn và không có hướng dẫn . . . . . . . . . 9 2 Phân tích phân cụm và các thuật toán phân cụm 11 2.1 Phân tích phân cụm . . . . . . . . . . . . . . . . . . . . . 11 2.1.1 Khái niệm phân cụm . . . . . . . . . . . . . . . . . 11 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 . . . . . . . . 13 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) . . . . . . . . . . . . . . . . . . . 17 2.3 Phân cụm trong trường hợp số lớp chưa biết . . . . . . . . 19 2.3.1 Thuật toán sử dụng phương pháp trực quan . . . . 19 2.3.2 Thuật toán Batchelor và Wilkins . . . . . . . . . . 21 i
  2. 2.4 Phân cụm trong trường hợp đã biết số lớp . . . . . . . . . 25 2.4.1 Thuật toán ISODATA . . . . . . . . . . . . . . . . 25 2.4.2 Thuật toán ISODATA hiệu chỉnh . . . . . . . . . . 34 2.4.3 Thuật toán K-means . . . . . . . . . . . . . . . . . 36 2.5 Thuật toán K*-means . . . . . . . . . . . . . . . . . . . . 40 2.5.1 Độ đo cho phân cụm dữ liệu . . . . . . . . . . . . . 41 2.5.2 Thuật toán K*-means . . . . . . . . . . . . . . . . 45 2.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . 48 3 Chương trình ứng dụng thuật toán ISODATA 52 3.1 Nêu lại ví dụ: . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2 Các trường hợp tính toán . . . . . . . . . . . . . . . . . . 52 Kết luận 59 Tài liệu tham khảo 60 ii
  3. 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
  4. đ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 iv
  5. 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). 1
  6. 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 2
  7. 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:   x  i1     xi2  xi =   ..    .    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:     T x x x12 · · · x1n  1   11   T   x2   x21 x22 · · · x2n   S=  ..  =    ..   .   .       T xN xN 1 xN 2 · · · xN n trong đó xTi = (xi1 , xi2 , · · · , xin ), i = 1, · · · , N , biểu diễn véc tơ dạng mẫu thứ i. 3
  8. 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: xTi = (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  xi1   ..   .    l xi =  xik  ; l = 1, · · · , K; i = 1, · · · , Nl ; k = 1, · · · , n  l     ..   .    l xin 4
  9. 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: 5
  10. 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 6
  11. Chương 1. Khái quát chung về dạng và nhận dạng 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. 1.3.2 Nhận dạng chữ viết tay Đâ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. 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. 1.3.3 Dự báo thời tiết 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. 7
  12. 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 Đ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.5 Phân tích y học bằng chụp tia X-quang 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. 1.3.6 Làm rõ các bức ảnh chụp từ vệ tinh và khoảng không 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... 8
  13. 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 9
  14. 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ả. 10
  15. 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 6= 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 11
  16. 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. 12
  17. 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 cung cấp thông tin cho nhận dạng vùng nguy hiểm... 2.1.3 Các yêu cầu của phân tích phân cụ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 13
  18. 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à 14
  19. 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 ) 6= 0 ∀xi 6= 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: 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: n X 2 T d (xi , xj ) = (xi − xj ) (xi − xj ) = (xik − xjk )2 k=1 15
  20. 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 . 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 X 2 d (xi , xj ) = αk (xik − xjk )2 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 = σ12 lk 2 trong đó σl = (σl1 , ...., σln ), và σ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 X (xik − zlk )2 d2l (xi , zl ) = 2 . σlk k=1 • 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: xTi xj dT (xi , xj ) = T xi xi + xTj xj − xTi xj trong đó xTi xj biểu thị số các thuộc tính chung giữa xi và xj . Còn xTi xi biểu diễn số các thuộc tính có bởi xi , và xTj 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 . 16
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

TL.01: Bộ Tiểu Luận Triết Học
207 tài liệu
1468 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
3=>0