Similarity-based clustering methods separate data into clusters according to
the pairwise similarity between the data, and the pairwise similarity is
crucial for their performance. In this paper, we propose {\em Clustering by
Discriminative Similarity (CDS)}, a novel method which learns discriminative
similarity for data clustering. CDS learns an unsupervised similarity-based
classifier from each data partition, and searches for the optimal partition of
the data by minimizing the generalization error of the learnt classifiers
associated with the data partitions. By generalization analysis via Rademacher
complexity, the generalization error bound for the unsupervised
similarity-based classifier is expressed as the sum of discriminative
similarity between the data from different classes. It is proved that the
derived discriminative similarity can also be induced by the integrated squared
error bound for kernel density classification. In order to evaluate the
performance of the proposed discriminative similarity, we propose a new
clustering method using a kernel as the similarity function, CDS via
unsupervised kernel classification (CDSK), with its effectiveness demonstrated
by experimental results.

本文提出了一种名称为 CDS 的新的聚类方法，其使用学习出的判别式相似度对数据集进行无监督聚类，并通过 Rademacher 复杂度对其进行了一般化分析。同时，使用核密度分类的积分平方误差界也可以导出所得到的判别相似度。在使用核函数作为相似度函数的情况下，使用 CDS 聚类方法的有效性已通过实验结果得到证明。

数据聚类的判别相似度

Discriminative Similarity for Data Clustering

Many similarity-based clustering methods work in two separate steps including
similarity matrix computation and subsequent spectral clustering. However,
similarity measurement is challenging because it is usually impacted by many
factors, e.g., the choice of similarity metric, neighborhood size, scale of
data, noise and outliers. Thus the learned similarity matrix is often not
suitable, let alone optimal, for the subsequent clustering. In addition,
nonlinear similarity often exists in many real world data which, however, has
not been effectively considered by most existing methods. To tackle these two
challenges, we propose a model to simultaneously learn cluster indicator matrix
and similarity information in kernel spaces in a principled way. We show
theoretical relationships to kernel k-means, k-means, and spectral clustering
methods. Then, to address the practical issue of how to select the most
suitable kernel for a particular clustering task, we further extend our model
with a multiple kernel learning ability. With this joint model, we can
automatically accomplish three subtasks of finding the best cluster indicator
matrix, the most accurate similarity relations and the optimal combination of
multiple kernels. By leveraging the interactions between these three subtasks
in a joint framework, each subtask can be iteratively boosted by using the
results of the others towards an overall optimal solution. Extensive
experiments are performed to demonstrate the effectiveness of our method.

为解决相似性测量困难及非线性相似性未被充分考虑等问题，在核空间中提出一种模型，同时学习聚类指示器矩阵和相似度信息，并通过多核学习能力进一步扩展模型以选择最合适的内核。该模型可自动完成三个子任务以获得最佳聚类解决方案。