Incomplete Multiview Clustering via Late Fusion

Yongkai Ye, Xinwang Liu, Qiang Liu, Xifeng Guo, Jianping YinComput. Intell. Neurosci 2018 · DOI

TL;DR

This paper introduces a novel "late fusion" approach for multiview clustering when some data views are incomplete. Instead of trying to fill in missing data (imputation) or combining views early, it clusters each view independently and then intelligently combines these results to achieve a more robust final clustering. This method shows improved performance over existing techniques, especially when dealing with significant data incompleteness.

What Problem Does This Paper Address?

In many real-world scenarios, data about the same samples comes from multiple sources or "views" (e.g., text and images of a product). Clustering aims to group similar samples. Multiview clustering leverages these multiple sources to improve clustering accuracy. However, a common challenge is that some views might be incomplete – data is missing for certain samples due to sensor failures, user non-participation, or other reasons.

Most existing methods for incomplete multiview clustering rely on either:

  1. Early Fusion: Trying to combine information from different views before clustering, often by imputing (filling in) missing data. This can be problematic as imputation can introduce noise or bias.
  2. Imputation-based methods: Explicitly filling in missing data points using techniques like zero-filling, mean-filling, or k-nearest neighbors, and then applying standard multiview clustering.

The authors argue that even with missing data, the clustering results from the visible instances within a single view can still be reliable. They propose that a more natural approach is to perform clustering on each view's available data and then combine these individual clustering results in a "late fusion" step. This avoids the pitfalls of imputation and early fusion.

Methods

The proposed method, "Incomplete Multiview Clustering via Late Fusion," consists of two main steps:

  1. Clustering Visible Instances in Each View: For each available view, the authors apply kernel k-means clustering to the instances that are not missing. They assume that the random missingness of data doesn't fundamentally alter the cluster structure within that view. The output of this step for each view is a zero-one indicator matrix representing the cluster assignments for the visible instances.
  2. Late Fusion of Clustering Results: This is the core innovation. The clustering results from each view (represented by the indicator matrices) are treated as compressed representations of the instances. The goal is to find a unified clustering decision (a final indicator matrix Y) that best groups these compressed representations across all views, while still respecting the k-means objective.
  3. They formulate an optimization problem to find this consensus clustering decision Y.
  4. An alternate updating algorithm is developed to solve this problem. This algorithm iteratively updates the cluster assignments (Y) and the cluster centroids (M) until convergence. The convergence of this iterative process is theoretically proven.
  5. The method uses kernel k-means, which maps data into a higher-dimensional space to find non-linear relationships, making it suitable for complex data.

Datasets

The authors evaluate their method on six benchmark datasets commonly used in multiple kernel learning:

  • Caltech101: Object categorization dataset.
  • CCV: Consumer video analysis benchmark.
  • Digital: Handwritten numerals dataset.
  • Flower17: Flower categorization dataset.
  • Flower102: Larger flower categorization dataset.
  • ProteinFold: Protein fold recognition dataset.

For experimental purposes, they artificially introduce missing data to these datasets to simulate incomplete multiview scenarios.

Key Insights and Ideas

  • Reliability of Incomplete Views: The paper's central hypothesis is that clustering results from visible instances in incomplete views are surprisingly robust. Figures 1 and 2 visually demonstrate that even with significant missing data (up to 90%), the cluster structure and centroids remain relatively stable. This insight is crucial for justifying the late fusion approach.
  • Late Fusion as a Natural Extension: Instead of forcing incomplete data into early fusion or imputation, late fusion offers a more direct way to leverage the information that is available. It allows each view to contribute its best guess, which is then refined by considering consistency across other views.
  • Importance of Initialization: The performance of the late fusion method is sensitive to the initial clustering decision (Yº). The paper empirically shows that different initialization methods (like using the results from imputation methods or the best single view) lead to varying final performance. This highlights the need for careful selection of the initial clustering.
  • Late Fusion as Refinement: The late fusion step can be viewed as a refinement process for the initial clustering. It corrects and improves upon the initial assignments by considering information from multiple views, leading to better overall clustering.

Key Results

  • Superior Performance: The proposed late fusion method consistently outperforms several imputation-based methods and a representative early fusion method (Partial View Clustering - PVC) across the six benchmark datasets, especially as the incomplete sample ratio increases.
  • Significant Boosts: In many cases, late fusion provides a substantial improvement over the initial clustering decision. For instance, on the Digital dataset with 80% missing samples, late fusion boosted performance by up to 27% compared to the initial "Best Single View" (BS) result.
  • Initialization Matters: While late fusion generally improves results, the choice of initialization significantly impacts the final outcome. The "Best Single View" (BS) and "Alignment-Maximization Filling" (AF) methods are identified as strong initializations, with AF showing the best overall late fusion performance across datasets.
  • Refining Early Fusion: The method can even improve upon results from early fusion methods like PVC, demonstrating its ability to refine existing clustering decisions.

Limitations and Future Work

  • Initialization Dependency: The authors acknowledge that finding a universally optimal initialization method is challenging. While they provide guidance based on empirical results, the performance is still tied to this initial step.
  • Fixed Number of Clusters: The current method assumes the number of clusters (K) is known beforehand.
  • Kernel k-Means Choice: The paper uses kernel k-means for single-view clustering. The authors suggest exploring other density-based clustering methods for single views and investigating how different single-view clustering techniques impact late fusion performance.
  • Deep Learning Integration: They propose exploring deep learning techniques, such as 3DConvNets, for feature learning and late fusion to potentially achieve even better results.
  • Automatic Cluster Generation: Future work could focus on automatically determining the number of clusters, which is often unknown in real-world applications.

Summary updated

BibTeX
@article{ye2018incomplete,
  author = {Yongkai Ye and Xinwang Liu and Qiang Liu and Xifeng Guo and Jianping Yin},
  title = {{Incomplete Multiview Clustering via Late Fusion}},
  journal = {Comput. Intell. Neurosci.},
  year = {2018},
  doi = {10.1155/2018/6148456},
}
Figure