Chương 1 đã trình bày những nội dung chủ yếu về cấu trúc mạng nơron các đơn vị xử lý, trạng thái kích hoạt, các luật học và môi trường hệ thống có thể hoạt động được. Về tổng thể, hình trạng mạng noron được chia làm hai loại là mạng noron truyền thẳng và mạng noron hồi quy. Thuật toán học mạng noron được chia làm hai nhóm chính đó là học có giám sát và học không có giám sát. - 16 - -- Chương 2: PHÂN CỤM DỮ LIỆU VỚI MÔ HÌNH SOM 2.
Phân cụm dữ liệu 2. Khái niệm PCDL là một kỹ thuật quan trọng và phổ biến trong xử lý thông tin, nhằm khám phá cấu trúc của các mẫu dữ liệu để tạo ra các nhóm dữ liệu từ tập dữ liệu lớn và mối quan hệ giữa chúng bằng cách tổ chức chúng thành các cụm dữ liệu. PCDL là một kỹ thuật tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên, tìm ẩn, quan trọng trong tập dữ liệu lớn. Từ đó cung cấp thông tin và tri thức hữu ích cho việc ra quyết định.
PCDL là quá trình nhóm các điểm dữ liệu trong CSDL thành các cụm sao cho tại những điểm trong cùng một cụm có độ tương ứng lớn và những điểm không cùng một cụm có độ tương ứng là rất nhỏ. Độ tương tự giữa các đối tượng được xác định dựa trên những giá trị đặc tả đối tượng. Thông thường phép đo khoảng cách thường được dùng để đánh giá độ tương tự hay không tương tự giữa các đối tượng dữ liệu. Mô hình phân cụm dữ liệu - 17 - -- Hình 2.1 mô tả một ví dụ về PCDL.
Như đã thấy, ở hình 2.1 (a) thể hiện mẫu đầu vào và ở hình 2.1 (b) là các cụm được nhóm dựa vào sự tương đồng của các đối tượng. Quá trình phân cụm là quá trình tìm ra các đối tượng trong CSDL một cách tự động. PCDL giải quyết vấn đề tìm một cấu trúc trong tập hợp dữ liệu chưa biết trước các thông tin về lớp hay các thông tin về tập huấn luyện. Vì vậy, PCDL là một phương pháp học không giám sát hay nói cách dễ hiểu thì PCDL là một ví dụ của phương pháp học không có thầy.
Không giống như phân lớp dữ liệu, PCDL không đòi hỏi phải định trước các lớp và mẫu dữ liệu huấn luyện đã gắn nhãn lớp. Vì thế, có thể coi PCDL 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, PCDL còn được sử dụng như một bước tiền xử lý cho các bài toán KPDL khác như 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. Đã có rất nhiều thuật toán cũng có như hệ thống được phát triển cho bài toán phân cụm trong CSDL lớn.
PCDL được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau như phân tích dữ liệu, xử lý ảnh, nhận dạng mẫu, sinh vật học, đánh giá thị trường, kinh doanh, giáo dục, … Sự đa dạng của thuật toán phân cụm là do sự khác nhau của những ứng dụng thực tế, dẫn tới những yêu cầu về dữ liệu khác nhau và việc sử dụng thuật toán phân cụm cũng khác nhau. Phân cụm và các thành phần trong phân cụm dữ liệu Mục đích của phân cụm là làm giảm kích thước dữ liệu bằng cách phân loại hoặc nhóm các thành phần dữ liệu giống nhau. Phân cụm dữ liệu là quá trình áp dụng các phương pháp, thuật toán để tổ chức dữ liệu thành các nhóm có những đặc điểm tương tự nhau. Một cụm là một tập hợp dữ liệu mà các phần tử tương tự nhau trong cùng một cụm và các phần tử không tương tự sẽ thuộc một cụm khác.
Phân tích cụm được sử dụng để đưa ra những số liệu thống kê nhằm xác định những đặc điểm khác nhau giữa các cụm. - 18 - -- Mẫu đại diện: Đề cập đến số lớp, số mẫu có sẵn và số lượng, chủng loại, quy mô của các tính năng có sẵn cho các thuật toán phân cụm. Lựa chọn đặc trưng là quá trình xác định các đặc trưng ban đầu của tập hợp con để sử dụng trong phân cụm. Trích chọn đặc trưng là việc sử dụng một hoặc nhiều biến đổi từ đặc trưng đầu vào để tạo ra đặc trưng mới nổi bật.
Những kĩ thuật này có thể được sử dụng để có một tập hợp các đặc trưng được sử dụng trong phân cụm dữ liệu. Mẫu lân cận: Thường được đo bằng một hàm khoảng cách thực hiện trên từng cặp mẫu. Có nhiều phương pháp đo khoảng cách được áp dụng trong phân cụm dữ liệu trong đó phổ biến nhất là phương pháp đo khoảng cách Euclide. Các bước nhóm dữ liệu có thể được thực hiện bằng nhiều cách khác nhau.
Các cụm đầu ra có thể phân vùng dữ liệu thành các nhóm hoặc mỗi một mẫu có thể biến đổi các thành viên trong cụm đầu ra. Trừu tượng hóa dữ liệu: Là quá trình rút ra một đại diện đơn và nhỏ gọn của một tập dữ liệu. Trong phân cụm dữ liệu trừu tượng hóa dữ liệu là mô tả nhỏ gọn mỗi cụm thường mô tả các cụm nguyên mẫu hoặc các mẫu đại diện trọng tâm. Đánh giá tính đúng đắn là mục tiêu và được thực hiện để xác định đầu ra có ý nghĩa hay không.
Một số kỹ thuật phân cụm dữ liệu 2. Phân cụm phân hoạch (Partitionnal Clustering) Phân cụm phân hoạch phân chia dữ liệu thành các tập số. Kiểm tra tất cả các hệ thống tập hợp con có thể là tính toán không khả thi. Di chuyển lặp đi lặp lại các điểm trong cụm.
Sau khi các cụm được xây dựng phương pháp phân cụm phân hoạch sẽ xem xét lại các cụm để cải thiện các cụm tốt hơn. Với dữ liệu thích hợp sẽ đem lại hiệu quả cao trong phân cụm. Ý tưởng chính của kỹ thuật phân cụm dữ liệu D có n đối tượng cho trước thành k phần, mỗi phần đại diện cho một cụm (k đối tượng đại diện có - 19 - -- thể được chọn ngẫu nhiên hoặc theo tiêu chuẩn của người sử dụng), với mỗi cụm phải ít nhất một đối tượng chỉ thuộc về một cụm. Kỹ thuật phân cụm phân hoạch tốt cho việc tìm các cụm hình cầu trong không gian Euclide.
Ngoài ra, kỹ thuật này cũng phụ thuộc vào khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ gần nhau với mỗi điểm khác nhau. Đối với các thuật toán phân cụm phân hoạch thì độ phân cụm rất lớn khi xác định nghiệm tối ưu toàn cục do phải tìm kiếm tất cả các cách có thể để phân chia tập dữ liệu. Chính vì vậy, trên thực tế để giải quyết các ứng dụng người ta thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của các cụm cũng như thể định hướng cho quá trình tìm kiếm phân cụm dữ liệu. Với số lượng các cụm dữ liệu cần chia cho trước, kỹ thuật này thực hiện phép nhân phân hoạch ban đầu.
Sau đó, nó liên tục tinh chỉnh cho đến khi thu được một phân hoạch mong muốn, thỏa nãm các điều kiện ràng buộc cho trước. Ví dụ về phân cụm phân hoạch với k=3 (a) và k=4 (b) Như vậy, các thuật toán phân cụm phân hoạch cải tiến tiêu chuẩn phân cụm bằng cách xác định các độ đo tương tự giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Với chiến lược như trên, ý - 20 - -- tưởng chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược “tham lam” để rìm kiếm nghiệm. Điển hình trong kỹ thuật phân cụm phân hoạch là thuật toán: k-means, k-medoids, PAM (Partitioning Around Medoids), CLARA (Clustering LARge Application), CLARANS (Clustering LARge ApplitionNS).
Dưới đây trình bày một thuật toán điển hình là thuật toán k-means. Phân cụm phân cấp (hierarchical Clustering) Cấu trúc phân cụm phân cấp xây dựng trên một hệ thống phân cấp cụm. Các cụm chứa các nút cụm con. Các cụm ngang hàng được phân chia thành các điểm cùng cụm cha.
Cách tiếp cận này cho phép tìm hiểu chi tiết dữ liệu ở các cấp độ khác nhau. Phương pháp phân cụm được chia làm hai loại: Phân cụm phân cấp tích tụ Bottom - Up và phân cụm phân cấp chia nhóm Top- Down. Phân cụm phân cấp tích tụ khởi đầu với một điểm cụm và kết hợp đệ quy với 2 hoặc nhiều cụm thích hợp nhất. Một cụm chia tách bắt đầu với một cụm của tất cả các điểm dữ liệu và đệ quy chia tách các cụm thích hợp nhất.
Quá trình này tiếp tục cho đến khi đạt được một tiêu chí dừng lại được. Phân cụm phân cấp dựa trên kết quả thống kê kết quả liên kết trong cụm. Kỹ thuật phân cụm phân cấp xây dựng cây phân cấp bằng cách sắp xếp các đối tượng trong tập dữ liệu đã cho, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Cây phân cụm này có thể này được xây dựng bằng hai phương pháp: hòa nhập cụm (agglomerative) và chia tách cụm (divisive).
Một số kỹ thuật phân cụm phân cấp a) Phương pháp hòa nhập cụm Phương pháp hòa nhập cụm được thực hiện theo hướng tiếp cận “từ dưới lên” (Bottom-up), sử dụng chiến lược “tham lam” trong quá trình phân cụm. Nó bắt đầu bằng cách đặt mỗi đối tượng vào trong cụm riêng biệt và sau đó tiến hành hòa nhập các cụm nguyên tử này vào trong các cụm càng ngày càng lớn hơn theo một độ đo tương tự nào đó cho tới khi tất cả các đối tượng nằm trong một cụm đơn hoặc tới khi các điều kiện dừng cho trước được thỏa. Hầu hết các kỹ thuật phân cụm phân cấp thuộc về loại này, chúng chỉ khác nhau về định nghĩa độ tương tự giữa các cụm. Một số thuật toán được phát triển dựa trên kỹ thuật này như: BIRCH (Tian Zhang và các đồng nghiệp, 1996), CURE (Sudipto Guha và các đồng nghiệp, 1998), ROCK (Sudipto Guha và các đồng nghiệp, 1999), … b) Phương pháp chia tách cụm Ngược lại với phương pháp hòa nhập cụm, phương pháp chia tách cụm được thực hiện theo hướng tiếp cận “từ trên xuống” (Top-down), sử dụng chiến lược “chia để trị” trong quá trình phân cụm.
Phương pháp này bắt đầu với tất cả các đối tượng được xếp trong một cụm, chia nhỏ nó theo giá trị của một độ đo tương tự nào đó thành các cụm ngày càng nhỏ hơn cho tới khi mỗi - 22 - -- một đối tượng là cụm hoặc cho tới khi một trong các điều kiện dừng cho trước được thỏa.