Tài liệu Phân cụm đồ thị dữ liệu và ứng dụng

ĐẠI HỌC THÁI NGUYÊN  TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG TRẦN HÀ PHƯƠNG PHÂN CỤM ĐỒ THỊ DỮ LIỆU VÀ ỨNG DỤNG         LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN  TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG TRẦN HÀ PHƯƠNG PHÂN CỤM ĐỒ THỊ DỮ LIỆU VÀ ỨNG DỤNG     Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: PGS. TS. ĐOÀN VĂN BAN THÁI NGUYÊN - 2016   i LỜI CAM ĐOAN Tên tôi là: Trần Hà Phương  Sinh ngày:   Học  viên  lớp  cao  học  CHK13  -  Trường  Đại  học  Công  nghệ  thông  tin  và  Truyền thông - Đại học Thái Nguyên.  Hiện đang công tác tại:     Xin cam đoan: Đề tài “Phân cụm đồ thị dữ liệu và ứng dụng” do Thầy giáo  PGS.TS Đoàn Văn Ban hướng dẫn là công trình nghiên cứu của riêng tôi. Tất cả tài  liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng.  Tác  giả  xin  cam  đoan  tất  cả  những  nội  dung  trong  luận  văn  đúng  như  nội  dung  trong  đề  cương  và  yêu  cầu  của  thầy  giáo  hướng  dẫn.  Nếu  sai  tôi  hoàn  toàn  chịu trách nhiệm trước hội đồng khoa học và trước pháp luật.  Thái Nguyên, ngày 14 tháng 4 năm 2016 Tác giả luận văn Trần Hà Phương               ii LỜI CẢM ƠN   Sau một  thời gian  nghiên  cứu  và làm việc nghiêm  túc,  được  sự  động  viên,  giúp đỡ và hướng dẫn tận tình của Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban,  luận văn với đề tài “Phân cụm đồ thị dữ liệu và ứng dụng”đã hoàn thành.  Tôi xin bày tỏ lòng biết ơn sâu sắc đến:  Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban đã tận tình chỉ dẫn, giúp đỡ  tôi hoàn thành luận văn này.  Khoa sau Đại học Trường Đại học công nghệ thông tin và truyền thông đã  giúp đỡ tôi trong quá trình học tập cũng như thực hiện luận văn.  Tôi  xin  chân  thành  cảm  ơn  bạn  bè,  đồng  nghiệp  và  gia  đình  đã  động  viên,  khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện và hoàn  thành luận văn này.  Thái Nguyên, ngày 16 tháng 6 năm 2016 Tác giả luận văn Trần Hà Phương         iii MỤC LỤC   LỜI CAM ĐOAN ................................................................................................... i  LỜI CẢM ƠN ........................................................................................................ii  MỤC LỤC ............................................................................................................ iii  DANH MỤC CÁC TỪ VIẾT TẮT ....................................................................... v  DANH MỤC BẢNG ............................................................................................. vi  DANH MỤC CÁC HÌNH ẢNH .......................................................................... vii MỞ ĐẦU ................................................................................................................ 1  1. Tính khoa học và cấp thiết của đề tài ................................................................... 1  2. Mục tiêu, đối tượng và phạm vi nghiên cứu của đề tài ......................................... 2  3. Phương pháp luận nghiên cứu .............................................................................. 2  4. Nội dung và bố cục của luận văn ......................................................................... 2  CHƯƠNG 1TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU ...................................... 4  1.1  Khái niệm, mục tiêu và các bước cơ bản của phân cụm dữ liệu ..................... 4  1.1.1  Phân cụm dữ liệu là gì? ........................................................................... 4  1.1.2  Các mục tiêu của phân cụm dữ liệu ........................................................ 5  1.1.3  Các bước cơ bản để phân cụm ................................................................ 7  1.2  Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu ............................. 8  1.2.1  Phân loại các kiểu dữ liệu ....................................................................... 8  1.2.2  Độ đo tương tự và phi tương tự ............................................................... 9  1.3  Những kỹ thuật tiếp cận trong phân cụm dữ liệu ......................................... 11  1.3.1  Phương pháp phân cụm phân hoạch ...................................................... 12  1.3.2  Phương pháp phân cụm phân cấp .......................................................... 12  1.3.3  Phương pháp phân cụm dựa trên mật độ ............................................... 13  1.3.4  Phương pháp phân cụm dựa trên lưới ................................................... 14  1.3.5  Phương pháp phân cụm dựa trên mô hình ............................................. 15  1.3.6  Phương pháp phân cụm dữ liệu có liên kết ............................................ 15  1.4  Các ứng dụng của phân cụm dữ liệu ............................................................ 16  1.5  Các yêu cầu và những vấn đề còn tồn tại trong phân cụm dữ liệu ................ 18  1.5.1  Các yêu cầu của phân cụm dữ liệu ........................................................ 18  1.5.2  Những vấn đề còn tồn tại trong phân cụm dữ liệu ................................. 20  1.6  Tổng kết chương ......................................................................................... 20      iv CHƯƠNG 2 THUẬT TOÁN PHÂN CỤM ĐỒ THỊ DỮ LIỆU ....................... 22  2.1  Tổng quan về lý thuyết đồ thị ...................................................................... 22  2.1.1  Giới thiệu chung ................................................................................... 22  2.1.2  Biểu diễn đồ thị trên máy tính ............................................................... 23  2.2  Mô hình đồ thị dữ liệu ................................................................................. 27  2.3  Độ đo trong phân cụm đồ thị dữ liệu ........................................................... 28  2.3.1  Độ đo cho phân cụm dữ liệu nói chung ................................................. 28  2.3.2  Độ đo cho phân cụm đồ thị ................................................................... 30  2.4  Một số thuật toán phân cụm dữ liệu dựa trên đồ thị ..................................... 31  2.4.1  Thuật toán CHAMELEON ................................................................... 31  2.4.2  Thuật toán phân cụm quang phổ ........................................................... 33  2.4.3  Thuật toán phân cụm phân cấp.............................................................. 35  2.5  Kết luận chương .......................................................................................... 46  CHƯƠNG 3. ỨNG DỤNG THUẬT TOÁN ĐỒ THỊ QUANG PHỔ TRONG VIỆC PHÂN LOẠI KẾT QUẢ HỌC TẬP CỦA HỌC SINH ........................... 47  3.1  Đặt vấn đề ................................................................................................... 47  3.2  Xây dựng chương trình ứng dụng ................................................................ 49  3.2.1  Mục đích chương trình ......................................................................... 49  3.2.2  Cơ sở dữ liệu ........................................................................................ 49  3.2.3  Các bước thực hiện ............................................................................... 49  3.2.4  Môi trường cài đặt ................................................................................ 50  3.2.5  Cài đặt .................................................................................................. 50  3.3  Các chức năng chính của chương trình ........................................................ 51  3.3.1  Chương trình chính ............................................................................... 51  3.3.2  Biểu diễn dữ liệu theo đồ thị ................................................................. 52  3.3.3  Phân cụm dữ liệu đồ thị quang phổ ....................................................... 52  3.4  Đánh giá hiệu quả của thuật toán phân cụm dữ liệu đồ thị quang phổ.......... 54  3.5  Kết luận chương .......................................................................................... 58  KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN........................................................... 59  TÀI LIỆU THAM KHẢO ................................................................................... 61      v DANH MỤC CÁC TỪ VIẾT TẮT   Từ hoặc cụm từ  Từ tiếng Anh  Từ tiếng Việt  Binding  data  Clustering  Phương pháp phân cụm dữ liệu  BDCM CA Methods có liên kết Continuous Attribute Thuộc tính liên tục Cơ sở dữ liệu CSDL Discrette Attribute Thuộc tính rời rạc DBM Density-Based Methods  Phương pháp dựa trên mật độ  GBM Grid-Based Methods  Phương pháp dựa trên lưới  HM Hierarchical Methods  Phương pháp phân cấp  DA Model-Based  MBCM Methods  phân cụm  MC Markov Clustering Phân cụm theo mô hình Markov MST Minimum Spanning Tree  Cây khung nhỏ nhất  Partitioning Methods  Phương pháp phân họach  Random Walk Algorithm  Thuật toán bước đi ngẫu nhiên  Star Clustering  Phân cụm hình sao  PM RWA SC SCA Spectral Clustering Algorithm  Thuật toán phân cụm quang phổ  SOM  Self-Organizing Map        Clustering  Phương pháp dựa trên mô hình  Mạng tự tổ chức        vi DANH MỤC BẢNG   Bảng 3.1. Các module chính của chương trình ....................................................... 51          vii DANH MỤC CÁC HÌNH ẢNH   Hình 1.1. Ví dụ về phân cụm dữ liệu [7] .................................................................. 5  Hình 1.2. Ví dụ phân cụm các đối tượng dựa trên khoảng cách [7] .......................... 5  Hình 1.3. Ví dụ phân cụm các đối tượng dựa trên kích cỡ [7] .................................. 6  Hình 1.4. Các bước trong quá trình phân cụm .......................................................... 8  Hình 1.5. Các chiến lược phân cụm phân cấp [11] ................................................. 13  Hình 1.6. Cấu trúc phân cụm dữ liệu dựa trên lưới ................................................ 15  Hình 2.1. Ví dụ về mô hình đồ thị .......................................................................... 22  Hình 2.2. Phân loại đồ thị ...................................................................................... 23  Hình 2.3. Ma trận kề vô hướng (trên) và có hướng (dưới) ...................................... 25  Hình 2.4. Ma trận trọng số vô hướng (trên) và có hướng (dưới) ............................. 26  Hình 2.5. Ma trận liên thuộc vô hướng (trên) và có hướng (dưới) .......................... 27  Hình 2.6. Minh họa thuật toán CHAMELEON ...................................................... 32  Hình 2.7. Nguyên lý chung của AntTree ................................................................ 36  Hình 2.8. Kiến trúc khác nhau giữa SOM và SOMTree ......................................... 41  Hình 2.9. Phân việc từ cây  treec cho treec ............................................................ 44  old Hình 2.10. Tách subtreex khỏi cây  treec và đưa vào list ........................................ 45  old Hình 2.11. Tái liên kết subtreex vào treec .............................................................. 45  Hình 3.1. Màn hình chính của chương trình ........................................................... 51  Hình 3.2. Biểu diễn dữ liệu theo đồ thị .................................................................. 52  Hình 3.3. Phân cụm dữ liệu đồ thị quang phổ với dữ liệu vào là dữ liệu kiểm tra ... 53  Hình 3.4. Phân cụm dữ liệu đồ thị quang phổ với dữ liệu vào là điểm học sinh ..... 54  Hình 3.5. Kết quả phân cụm dữ liệu dạng ba cụm Gaussian với 1000 mẫu dữ liệu 55  Hình 3.6. Kết  quả  phân  cụm  dữ  liệu  dạng  ba  cụm Gaussian với  độ lớn  lần  lượt là  100, 1000, 3000 mẫu dữ liệu ................................................................................. 55  Hình 3.7. Kết quả phân cụm dữ liệu dạng hai nửa vầng trăng với kích thước dữ liệu  là ba cụm Gaussian với độ lớn lần lượt là 7500 mẫu dữ liệu .................................. 56  Hình 3.8. Kết quả phân cụm dữ liệu dạng hai nửa vầng trăng với hai thuật toán K  mean (trái) và đồ thị quang phổ (phải) ................................................................... 56  Hình 3.9. Kết quả phân cụm dữ liệu điểm học sinh với số cụm khác nhau ............. 57      1 MỞ ĐẦU   1. Tính khoa học và cấp thiết của đề tài Phân  cụm  là  một  trong  những  vấn  đề  cơ  bản  phổ  biến  trong  các  lĩnh  vực  nhận  dạng  mẫu,  học  máy  và  khai  thác  dữ  liệu.  Hiện  tại,  trên  thực  tế  có  rất  nhiều  thuật toán phân cụm được công bố. Tuy nhiên, do không tồn tại một thuật toán phân  cụm  duy  nhất  cho  tất  cả  các  loại bộ dữ liệu,  những  thuật  toán  phân  cụm  mới  vẫn  liên tục được đề xuất. Kết quả là, người dùng phải chọn thuật toán thích hợp nhất từ  nhiều ứng viên để đạt được kết quả chính xác.   Trong thực tế, việc lựa chọn thuật toán phân cụm dữ liệu phù hợp là rất khó  khăn do người sử dụng thường không có một kiến thức tiên nghiệm về sự đa dạng  và phức tạp của dữ liệu. Để phần nào giảm bớt nhược điểm trên, các thuật toán phân  cụm dựa trên đồ thị được đề xuất do ưu điểm ở khả năng xử lý các bộ dữ liệu đa  dạng và có cấu trúc. Bản chất của các thuật toán này là biểu diễn dữ liệu dựa trên đồ  thị và phân cụm các thành phần theo các thuật toán thiết kế riêng.  Đồ thị là những cấu trúc toán học được sử dụng để đại diện cho mối quan hệ  giữa cặp đối tượng từ một tập hợp xác định. Đồ thị chứa đỉnh (đại diện cho các đối  tượng) và các cạnh nối các đỉnh (đại diện cho mối quan hệ giữa các đối tượng cặp).  Đây là phương pháp cấu trúc dữ liệu quan trọng được sử dụng trong rất nhiều lĩnh  vực như khai thác dữ liệu, xử lý ngôn ngữ tự nhiên, tìm kiếm thông tin và khai thác  thông tin. Trong phân cụm, sự tương đồng giữa các đối tượng được phân cụm có thể  được diễn tả như một đồ thị có trọng số. Trong đó, các đối tượng là các đỉnh và sự  tương đồng là trọng số của các cạnh. Bài toán phân cụm sẽ được đơn giản hóa về  bài toán phân cụm đồ thị mà nhiệm vụ chính là tách các đồ thị phụ dày đặc và kết  nối thưa thớt khỏi nhau dựa trên khái niệm của mật độ nội cụm so với khoảng cách  liên cụm.  Với những lý do trên, tác giả đã chọn đề tài “Phân cụm đồ thị dữ liệu và ứng dụng”  làm  đề  tài  nghiên  cứu  luận  văn  tốt  nghiệp  thạc  sĩ  chuyên  ngành  Khoa học máy tính.      2 2. Mục tiêu, đối tượng và phạm vi nghiên cứu của đề tài Đề tài nhằm thực hiện các mục tiêu sau: - Nghiên cứu tổng quan và đánh giá các phương pháp phân cụm, nghiên cứu  sâu về phương pháp phân cụm dữ liệu dựa trên đồ thị.   - Nghiên cứu một số thuật toán của phương pháp phân cụm dựa trên đồ thị  như: Chameleon, phân cụm đồ thị quang phổ (Spectral Clustering), phân cụm phân  cấp theo đồ thị (thuật toán AntTree và SOMTree). Đánh giá các ưu và nhược điểm  của mỗi thuật toán.  - Cài  đặt  phần  mềm  thử  nghiệm  mô  phỏng  chương  trình  phân  loại  kết  quả  học tập của học sinh theo thuật toán phân cụm đồ thị quang phổ, đánh giá hiệu quả  hoạt động của thuật toán này.  Chính  vì  vậy,  đối  tượng  của  luận  văn  là:  Các  thuật  toán  phân  cụm  dữ  liệu  dựa trên đồ thị. Luận văn sẽ khảo sát và đánh giá một số ứng dụng thực tế của một  số  phương  pháp  phân  cụm  dữ  liệu  dựa  trên  đồ  thị.Tập  trung  sâu  vào  cài  đặt  thử  nghiệm  thuật toán  phân  cụm  dựa  trên  đồ thị  quang  phổ  ứng  dụng  trong phân  tích  đánh giá kết quả học tập của học sinh.   3. Phương pháp luận nghiên cứu - Phương pháp nghiên cứu lý thuyết: Tổng hợp, nghiên cứu các tài liệu về  phân cụm dữ liệu, tập trung sâu vào các phương pháp, thuật toán phân cụm dữ liệu  bằng đồ thị; Tìm hiểu các kiến thức liên quan.  - Phương pháp nghiên cứu thực nghiệm:  Sau  khi  nghiên  cứu  lý  thuyết, phát biểu bài toán phân tích đánh giá kết quả học tập của học sinh, đưa  ra  giải  pháp  xử  lý;  Mô  phỏng  thử  nghiệm  chương  trình  phần  mềm;  Đánh  giá  các kết quả đạt được.  - Phương pháp trao đổi khoa học: Thảo  luận,  xemina,  và trao  đổi ý  kiến  với các chuyên gia.  4. Nội dung và bố cục của luận văn Ngoài phần mở đầu trình bày lý do chọn đề tài và phần kết luận trình bày các  kết quả  đạt được  cũng  như  hướng  phát triển tiếp theo  của  luận  văn này,  nội  dung  nghiên cứu chính được trình bày trong ba chương như sau:       3  Chương 1: Tổng quan về phân cụm dữ liệu. - Nghiên cứu về bài toán phân cụm dữ liệu; Giới thiệu một số phương pháp  phân cụm dữ liệu phổ  biến như: phân cụm phân hoạch, phân cụm  phân cấp, phân  cụm  dựa  trên  mật  độ,  phân  cụm  dựa  trên  lưới,  phân  cụm  dựa  trên  mô  hình,  phân  cụm có dữ liệu ràng buộc và đánh giá các ưu và nhược điểm của mỗi phương pháp.   Chương 2: Thuật toán phân cụm đồ thị dữ liệu. Trình  bày  phương  pháp  phân  cụm  dữ  liệu  dựa  trên  đồ  thị  và  một  số  thuật  toán  như:  Thuật toán  Chameleon, thuật  toán  phân  cụm  quang  phổ, thuật  toán  Ant  Tree, thuật toán  SOM Tree.  Chương 3: Ứng dụng thuật toán đồ thị quang phổ trong việc phân loại kết quả học tập của học sinh. - Phát biểu bài toán, xây dựng chương trình phân loại kết quả học tập của  học sinh theo thuật toán phân cụm dữ liệu quang phổ.         4 CHƯƠNG 1 TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1.1 Khái niệm, mục tiêu và các bước cơ bản của phân cụm dữ liệu 1.1.1 Phân cụm dữ liệu là gì? Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu (Data mining) nhằm  tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong  tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định [6], [14].  Phân cụm dữ liệu là sự phân chia một cơ sở dữ liệu lớn thành các nhóm dữ  liệu trong đó các đối tượng tương tự nhau trong một nhóm. Trong mỗi nhóm, một  số chi tiết có thể không quan tâm đến để đổi lấy dữ liệu đơn giản hóa. Hay ta có thể  hiểu “Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành từng nhóm sao cho  mỗi nhóm đều tương tự nhau theo một tính chất nào đó và những đối tượng ở nhóm  khác sẽ không tương tự như nhau” [1].  Như vậy, bản chất của phân cụm dữ liệu là quá trình nhóm một tập các đối  tượng  tương  tự  nhau  trong  tập  dữ  liệu  vào  các  cụm  sao  cho  các  đối  tượng  thuộc  cùng một cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không  tương đồng. Số các cụm dữ liệu được phân ở đây có thể được xác định trước theo  kinh nghiệm hoặc có thể được tự động xác định. Phân cụm dữ liệu là một ví dụ của  phương pháp học không giám sát. Không giống như phân lớp dữ liệu, phân cụm dữ  liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể  coi phân cụm dữ liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu là  học bằng ví dụ...Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước  tiền xử lí cho các thuật toán khai phá dữ liệu khác  như là phân loại và mô tả đặc  điểm, có tác dụng trong việc phát hiện ra các cụm.  Chúng ta có thể thấy điều này với một ví dụ đơn giản như Hình 1.1. Trong  trường hợp này, chúng ta dễ dàng xác định được 4 cụm dựa vào các dữ liệu đã cho;  các tiêu chí “tương tự” để phân cụm trong trường hợp này là khoảng cách: hai hoặc  nhiều  đối  tượng  thuộc  nhóm  của  chúng  được  “nhóm”  theo  một  khoảng  cách  nhất  định. Điều này được gọi là phân cụm dựa trên khoảng cách.  Một kiểu khác của phân cụm dữ liệu là phân cụm dữ liệu dựa vào khái niệm:  hai hay nhiều đối tượng thuộc cùng nhóm nếu có một định nghĩa khái niệm chung      5 cho tất cả các đối tượng trong đó. Nói cách khác, đối tượng của nhóm phải phù hợp  với  nhau  theo  các  khái  niệm  miêu  tả  đã  được  định  nghĩa,  không  phải  theo  những  biện pháp đơn giản tương tự.    Hình 1.1. Ví dụ về phân cụm dữ liệu [7] 1.1.2 Các mục tiêu của phân cụm dữ liệu Mục tiêu của phân cụm dữ liệu là để xác định các nhóm nội tại bên trong một  bộ dữ liệu không có nhãn. Nhưng làm thế nào để quyết định cái gì đã tạo nên một  phân cụm dữ liệu tốt? Ta có thể thấy rằng không có tiêu chuẩn tuyệt đối “tốt nhất”  mà sẽ phải phụ thuộc vào mục đích cuối cùng của phân cụm dữ liệu. Do đó, người  sử dụng phải cung cấp tiêu chuẩn. Theo cách như vậy, kết quả của phân cụm dữ liệu  sẽ phù hợp với nhu cầu của họ cần.    Hình 1.2. Ví dụ phân cụm các đối tượng dựa trên khoảng cách [7] Ví  dụ,  chúng  ta có  thể  quan  tâm  đến  việc  tìm  kiếm  đối tượng  đại  diện  cho  các nhóm đồng nhất trong “các cụm tự nhiên” và mô tả thuộc tính không biết của  chúng trong việc tìm kiếm các nhóm hữu ích và phù hợp hoặc trong việc tìm kiếm  các đối tượng bất thường trong dữ liệu (cá biệt, ngoại lệ, nhiễu) [1].      6 Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho phân  cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy  đủ.  Vì  vậy,  cần  phải  xây  dựng  chiến  lược  cho  bước  tiền  xử  lí  dữ  liệu  nhằm  khắc  phục  hoặc  loại  bỏ  nhiễu  trước  khi  chuyển  sang  giai  đoạn  phân  tích  cụm  dữ  liệu.  Nhiễu ở đây được hiểu là các đối tượng dữ liệu không chính xác, không tường minh  hoặc  là  các  đối  tượng  dữ  liệu  khuyết  thiếu  thông  tin  về  một  số  thuộc  tính...  Một  trong các kỹ thuật xử lí nhiễu phổ biến là việc thay thế giá trị các thuộc tính của đối  tượng nhiễu bằng giá trị thuộc tính tương ứng. Ngoài ra, dò tìm đối tượng ngoại lai  cũng là một trong những hướng nghiên cứu quan trọng trong phân cụm, chức năng  của nó là xác định một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ  liệu trong cơ sở dữ liệu, tức là các đối tượng dữ liệu không tuân theo các hành vi  hoặc mô hình dữ liệu nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả  của phân cụm.    Hình 1.3. Ví dụ phân cụm các đối tượng dựa trên kích cỡ [7] Theo các nghiên cứu đến thời điểm hiện nay thì chưa có một phương pháp  phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cơ sở  dữ liệu. Hơn  nữa, đối với các phương  pháp  phân cụm  cần  có  cách  thức  biểu  diễn  cấu trúc của cơ sở dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng  một thuật toán phân cụm phù hợp. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề  khó và mở, vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với  nhiều dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng      7 tăng trong  các hệ quản trị dữ liệu và  đây cũng là  một trong những  thách thức lớn  trong lĩnh vực khai phá dữ liệu [3].   1.1.3 Các bước cơ bản để phân cụm - Chọn lựa đặc trưng : Các đặc trưng phải được chọn lựa một cách hợp lý  để có thể “mã hoá” nhiều nhất thông tin liên quan đến công việc quan tâm. Mục tiêu  chính là phải giảm thiểu sự dư thừa thông tin giữa các đặc trưng. Các đặc trưng cần  được tiền xử lý trước khi dùng trong các bước sau.   - Chọn độ đo gần gũi: Đây là một độ đo chỉ ra mức độ tương tự hay không  tương tự giữa hai vector đặc trưng. Phải đảm bảo rằng tất cả các vector đặc trưng  góp phần như nhau trong việc tính toán độ đo gần gũi và không có đặc trưng nào át  hẳn đặc trưng nào. Điều này được đảm nhận bởi quá trình tiền xử lý.   - Tiêu chuẩn phân cụm: Điều này phụ thuộc vào sự giải thích của chuyên  gia  cho  thuật ngữ  “dễ nhận thấy”  dựa  vào  loại của  các cụm  được chuyên gia  cho  rằng đang ẩn dấu dưới tập dữ liệu. Chẳng hạn, một cụm loại chặt (compact) của các  vector đặc trưng trong không gian ℓ-chiều có thể dễ nhận thấy theo một tiêu chuẩn,  trong  khi  một  cụm  loại  “dài và mỏng”  lại  có  thể  được  dễ  nhận  thấy  bởi  một  tiêu  chuẩn khác. Tiêu chuẩn phân loại có thể được diễn đạt bởi hàm chi phí hay một vài  loại quy tắc khác.   - Thuật toán phân cụm: Cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm  làm sáng tỏ cấu trúc cụm của tập dữ liệu.   - Công nhận kết quả: Khi đã có kết quả phân loại thì ta phải kiểm tra tính đúng  đắn của nó. Điều này thường được thực hiện bởi việc dùng các kiểm định phù hợp.   - Giải thích kết quả: Trong nhiều trường hợp, chuyên gia trong lĩnh vực ứng  dụng phải kết hợp kết quả phân loại với bằng chứng thực nghiệm và phân tích để  đưa  ra  các  kết  luận  đúng  đắn.  Trong  một  số  trường  hợp,  nên  có  cả  bước  khuynh  hướng phân cụm; trong bước này có các kiểm định khác nhau để chỉ ra một dữ liệu  có hay không một cấu trúc phân cụm. Ví dụ như tập dữ liệu của ta có thể hoàn toàn  ngẫu nhiên vì vậy mọi cố gắng phân cụm đều vô nghĩa.   Các  lựa  chọn  khác  nhau  của  các  đặc  trưng,  độ  đo  gần gũi,  tiêu  chuẩn phân  cụm có thể dẫn tới các kết quả phân cụm khác nhau. Do đó, việc lựa chọn một cách      8 hợp lý nhất hoàn toàn dựa v ựa vào kiến thức và kinh nghiệm của chuyên gia. Tính ch ên gia. Tính chủ  quan (của chuyên gia) là m ên gia) là một thực tế mà ta phải chấp nhận.     Hình 1 1.4. Các bước trong quá trình phân cụm 1.2 Một số khái niệm cầ ần thiết khi tiếp cận phân cụm dữ liệu 1.2.1 Phân loại các kiểu ud dữ liệu Cho một CSDL D chứa n đối t ột CSDL D chứa n đối tượng trong không gian k chiều trong đó  ều trong đó x, y, z là  các đối tượng thuộc D : xx =(x1,x2,..,xk ); y =(y1,y2,..,yk); z =(z1,z2,..,zk), trong đó  trong đó xi, yi, zi  với i = 1…k là các đặc trưng ho ưng hoặc thuộc tính tương ứng của các đối tượng  ợng x, y, z.   Sau đây là các kiểu dữ liệu:  ểu dữ liệu:   1.2.1.1Phân loại các kiểu u dữ d liệu dựa trên kích thước miền - Thuộc  tính  liên  ttục  (Continuous  Attribute):  nếu  ếu  miền  giá  trị  của  nó  llà  vô  hạn không đếm được   - Thuộc tính rời rạc (Discrette ộc tính rời rạc (Discrette Attribute): Nếu miền giá trị của nó l ếu miền giá trị của nó là tập hữu  hạn, đếm được   - Lớp các thuộc tính nhị phân: l ớp các thuộc tính nhị phân: là trường hợp đặc biệt của thuộc tính rời rạc  ờng hợp đặc biệt của thuộc tính rời rạc  mà miền giá trị của nó chỉ có 2 phần tử đ ền giá trị của nó chỉ có 2 phần tử được diễn tả như : Yes / No ho ư : Yes / No hoặc Nam/Nữ,  False/true,…       9 1.2.1.2 Phân loại các kiểu dữ liệu dựa trên hệ đo Giả sử rằng chúng ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng  với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau :   - Thuộc tính định danh (Nominal Scale): đây là dạng thuộc tính khái quát hoá  của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có  nhiều hơn hai phần tử - nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể  xác định là x ≠ y hoặc x = y.   - Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính  thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì  ta có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x yi thì ta nói x cách y một khoảng xi - yi tương ứng với  thuộc tính thứ i.   - Thuộc  tính  tỉ  lệ  (Ratio  Scale):  là  thuộc  tính  khoảng  nhưng  được  xác  định  một cách tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc cân nặng  lấy điểm 0 làm mốc. Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định  danh và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), thuộc  tính khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số (Numeric).   1.2.2 Độ đo tương tự và phi tương tự Để phân cụm, người ta phải đi tìm cách thích hợp để xác định “khoảng cách”  giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các hàm để đo sự giống  nhau  giữa  các  cặp  đối  tượng  dữ  liệu,  thông  thường  các  hàm  này  hoặc  là  để  tính  độ  tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu.   1.2.2.1 Không gian metric Các độ đo thường được xác định trong không gian độ đo metric. Một không  gian  metric  là  một  tập  các  phần  tử,  trong  đó  có  xác  định  các  “khoảng  cách”  giữa  từng  cặp  phần  tử,  với  những  tính  chất  thông  thường  theo  khoảng  cách  hình  học.  Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) các đối      10 tượng  dữ  liệu  trong  CSDL  D  như  đã  đề  cập  ở  trên  được  gọi  là  một  không  gian  metric nếu:   - Với mỗi cặp phần tử x, y thuộc X đều có xác định, theo một quy tắc nào  đó, một số thực δ(x,y), được gọi là khoảng cách giữa x và y.    - Quy tắc nói trên thoả mãn hệ tính chất sau : δ(x,y) > 0 nếu x ≠ y ;  (ii) δ(x, y)=0 nếu x = y;  (iii) δ(x,y) = δ(y,x) với mọi x,y;  (iv) δ(x,y) ≤ δ(x,z)+δ(z,y).    Hàm δ(x,y) được gọi là một metric của không gian. Các phần tử của X được  gọi là các điểm của không gian này.   1.2.2.2Thuộc tính khoảng cách Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x, y được  xác định bằng các metric khoảng cách như sau:   - Khoảng  cách  Minskowski:  Được  thể  hiện  trong  (1.1)  trong  đó  q  là  số  tự  nhiên dương.  1/ q  n q d  x, y     xi  yi     i 1  (1.1)  - Khoảng cách Euclide : Được thể hiện bởi (1.2), đây là trường hợp đặc biệt  của khoảng cách Minskowski trong trường hợp q=2.  n d  x, y    x y i 2 i   (1.2)  i 1 - Khoảng cách Manhattan : Thể hiện trong (1.3), đây là trường hợp đặc biệt  của khoảng cách Minskowski trong trường hợp q=1.  n d  x, y    xi  yi   (1.3)  i 1 - Khoảng cách cực đại : là trường hợp của khoảng cách Minskowski trong  trường hợp q=∞ thể hiện trong (1.4).   d  x, y   Max in1 xi  yi   (1.4)  1.2.2.3 Thuộc tính định danh Độ đo phi tương tự giữa hai đối tượng x và y được định nghĩa như sau:  d  x, y     pm   p (1.5)    11 Trong đó m là số thuộc tính đối sánh tương ứng trùng nhau, và p là tổng số  các thuộc tính.   1.2.2.4 Thuộc tính có thứ tự Giả sử i là thuộc tính thứ tự có Mi  giá trị (Mi kích thước miền giá trị): Các  trạng thái Mi được sắp thứ tự như sau : [1…Mi], chúng ta có thể thay thế  mỗi giá trị  của thuộc tính bằng giá trị cùng loại ri, với ri ∈{1…Mi}.   Mỗi một thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy chúng ta  chuyển đổi chúng về cùng miền giá trị [0,1] bằng cách thực hiện phép biến đổi sau  cho mỗi thuộc tính :   ri   1   M i 1 j Zi   j (1.6)  Sử  dụng  công  thức  tính  độ  phi tương  tự của thuộc tính  khoảng  đối  với các  giá trị Zi j  , đây cũng chính là độ phi tương tự của thuộc tính có thứ tự.   1.2.2.5 Thuộc tính tỉ lệ Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ. Một  trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính. Hoặc loại  bỏ đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hoá chúng, hoặc gán trọng  số cho mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Với mỗi thuộc tính dữ liệu  đã được gán trọng số tương ứng  wi (1 <= i <= k ), độ tương đồng dữ liệu được xác  định như sau :  n d  x, y   w i 2 xi  yi   (1.7)  i 1 1.3 Những kỹ thuật tiếp cận trong phân cụm dữ liệu Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực  tế,  nó  đều hướng tới hai  mục tiêu chung  đó  là chất lượng  của các cụm  khám  phá  được  và  tốc  độ  thực  hiện của  thuật  toán.  Hiện  nay, các  kỹ  thuật  phân  cụm  có  thể  phân loại theo các phương pháp tiếp cận chính như sau : Phương pháp phân hoạch  (Partitioning  Methods);  Phương  pháp  phân  cấp  (Hierarchical  Methods);  Phương  pháp dựa trên mật độ (Density-Based Methods); Phương pháp dựa trên lưới (GridBased  Methods);  Phương  pháp  dựa  trên  mô  hình  phân  cụm  (Model-Based