One of the most serious difficulties in the analysis of high-dimensional data sets
involves the treatment of measures of similarity. Although similarity measures
often retain some discriminative ability as the dimension increases, the similarity
values themselves are often difficult to interpret. Methods for search, clustering
and feature selection that perform quantitive tests of similarity values (as
opposed to comparative tests) are particularly susceptible to this problem. This
presentation will be concerned with combinatorial models of clustering based on
shared neighbor information, and their application to feature selection, subspace
clustering, and multiple clustering. The models assume a secondary, derived form
of similarity measure based on the intersection properties of neighborhoods
defined according to the original similarity measure. The use of secondary similarity
has been recently shown to offer solutions that are more robust and more scalable
with respect to the dimension of the data.
For similarity search and their applications, the distance measures commonly
used in practice are known to be sensitive to local variations within the data
distribution, as well as the number of data features involved (the dimension).
These dependencies can severely limit the the efficiency and accuracy of the
search, and ultimately the quality of the solution — a phenomenon often referred
to as the curse of dimensionality. Generally speaking, as the number of data
features increases, pairwise distance values tend to concentrate tightly about their
mean, reducing the overall discriminative ability of the similarity measure. The
effect occurs for a broad range of data distributions and similarity measures, and
can be so pronounced as to cast doubt upon whether efficient nearest neighbor
search is even achievable in higher dimensions [
In general, any improvement in the discriminative ability of the similarity
measure employed can be expected to yield improvements in the performances
of solutions based on it. Some simple enhancement strategies involve the use of
shared neighbor (SN) information, in which a secondary similarity between two
points v and w is defined in terms of data objects in the common intersection of
neighborhoods based at v and w, where the neighborhoods themselves are
determined according to a supplied primary similarity measure. The primary measure
can be any function that determines a well-defined ranking of the data objects
relative to the query. Recent studies have shown that secondary similarity
measures based on SN information are generally more robust in higher dimensions
than their associated primary distance measures, since the neighborhoods of
object pairs drawn from a common cluster tend to have significantly more items in
common than to pairs drawn from different clusters [
Shared-neighbor information has been used to guide clustering algorithms for
almost 40 years [
In order to account for the effects of varying k, the Relevant-Set
Correlation (RSC) model for clustering was proposed [
The RSC model quantifies the quality of cluster candidates of any arbitrary
size (allowing the comparison of any two candidates regardless of their size), the
degree of association between pairs of cluster candidates, and the degree of
association between clusters and individual data items. An efficient greedy selection
strategy, GreedyRSC, has been developed based on RSC, and was shown to be
very competitive in practice [
This presentation will be concerned with an extension of the RSC model to account for multiple sources of neighborhood information. Each of these sources is assumed to have its own similarity measure based on its own collection of data features (which may or may not contain features also used by other sources). Like the original RSC model, the extended model relies only on the neighborhood rankings produced according to the sources, and has no knowledge of the nature of the similarity measure or features involved.
The extension of RSC will be seen to have implications for subspace clustering and feature selection, as well as multiclustering. In particular, the discussion will include the following potential applications of the extended model: – The significance of data sets can be simultaneously assessed with respect to object membership as well as the number of sources of neighborhood information. If each source is associated with its own collection of features, the model in effect assesses the significance of the association of a particular group of objects with a collection of features. – Under the model, the combination of sources that are most strongly associated with a putative cluster can be identified very efficiently. – In applications for which multiple clusterings of the data have been generated, the model can be used to decide to which clustering a particular candidate cluster is best aligned. This can potentially serve as a foundation upon which multiple clustering criteria can be designed.