Có một số phương pháp được phân loại thành ba nhóm chính bao gồm: kỹ thuật tìm kiếm không gian con, kỹ thuật phân cụm dựa trên tương quan và kỹ thuật song cụm (biclustering).
Kỹ thuật Tìm kiếm Không gian con (Subspace Search Technique)
Một phương pháp tìm kiếm không gian con tìm kiếm nhiều không gian con để tìm cụm. Do đó, một cụm là tập con các đối tượng giống nhau trong một không gian con. Sự tương đồng được đạt được bằng các đo lường truyền thống bao gồm khoảng cách hoặc mật độ.
Ví dụ, thuật toán CLIQUE là kỹ thuật phân cụm không gian con. Nó xác định các không gian con và các cụm trong những không gian con đó theo trình tự tăng chiều số và sử dụng tính chất phản đơn điệu (antimonotonicity) để cắt tỉa các không gian con mà không có cụm nào tồn tại. Thách thức lớn hơn mà kỹ thuật tìm kiếm không gian con đối mặt là cách tìm kiếm hiệu quả một chuỗi các không gian con.
Có hai loại phương pháp như sau:
- Phương pháp Bottom-up (từ dưới lên): bắt đầu từ không gian con chiều thấp và tìm kiếm không gian con chiều cao hơn chỉ khi có thể có cụm trong những không gian con chiều cao hơn đó. Có nhiều phương pháp cắt tỉa được phân tích để giảm số lượng không gian con chiều cao hơn cần tìm kiếm. CLIQUE là ví dụ của phương pháp bottom-up.
- Phương pháp Top-down (từ trên xuống): bắt đầu từ không gian đầy đủ và tìm kiếm đệ quy các không gian con nhỏ hơn và nhỏ hơn. Phương pháp top-down chỉ hiệu quả nếu giả định cục bộ (locality assumption) có hiệu lực, yêu cầu không gian con của một cụm có thể được xác định bởi lân cận cục bộ.
Phương pháp Phân cụm Dựa trên Tương quan (Correlation-Based Clustering Methods)
Trong khi các phương pháp tìm kiếm không gian con tìm kiếm cụm với độ tương đồng được tính bằng các chỉ số truyền thống như khoảng cách hoặc mật độ, các phương pháp dựa trên tương quan có thể tìm các cụm được biểu diễn bằng các mô hình tương quan tiên tiến hơn.
Một phương pháp dựa trên PCA trước tiên sử dụng PCA (Phân tích Thành phần Chính) để chuyển đổi sang một tập hợp các chiều mới không tương quan, sau đó khai thác cụm trong không gian mới hoặc các không gian con của nó. Ngoài PCA, các phép biến đổi không gian khác có thể được sử dụng, bao gồm biến đổi Hough hoặc chiều fractal.
Phương pháp Song cụm (Biclustering Methods)
Trong một số ứng dụng, cần phải phân cụm cả đối tượng và thuộc tính cùng một lúc. Các cụm kết quả được gọi là biclusters và đáp ứng bốn yêu cầu sau:
- Chỉ một nhóm nhỏ đối tượng tham gia vào một cụm.
- Một cụm chỉ chứa một số nhỏ thuộc tính.
- Một đối tượng có thể tham gia nhiều cụm, hoặc không tham gia cụm nào.
- Một thuộc tính có thể nằm trong nhiều cụm, hoặc không nằm trong cụm nào.
Các kỹ thuật song cụm lần đầu được đề xuất để đáp ứng nhu cầu khám phá dữ liệu biểu hiện gen (gene expression data). Gen là đơn vị truyền đặc điểm từ sinh vật đến hậu duệ. Thông thường, gen bao gồm một đoạn DNA.
Gen rất quan trọng đối với mọi sinh vật vì chúng xác định một số protein và chuỗi RNA chức năng. Chúng ảnh hưởng đến thông tin để xây dựng và duy trì tế bào của sinh vật và truyền đặc điểm di truyền cho hậu duệ.
Genotype là cấu trúc di truyền của một tế bào, sinh thể hoặc cá thể. Phenotype là đặc điểm biểu hiện của sinh thể. Biểu hiện gen là cấp độ quan trọng trong di truyền học vì genotype gây ra phenotype.