A Set Correlation Model for
Partitional Clustering
Michael E. HOULE

Nguyen Xuan VINH

NII

National ICT Australia, University of New South Wales

WhyWhat

Traditional clustering-based data discovery tools
often fail when the data sets are very large or have
many attributes, or have performance parameters thatare very difficult to tune in practice. We havedeveloped a novel formulation for partitional dataclustering that overcomes many of these difficulties,
based on the generic Relevant Set Correlation (RSC)
model.

The new model, GlobalRSC, resembles the famous Kmeans clustering heuristic, but with a sharedneighbor similarity measure instead of the Euclidean
distance. Unlike K-means and most other clustering
heuristics that can only work with real-valued data
and distance measures taken from specific families,
GlobalRSC has the advantage that it can work withany distance measure, and any data representation.

The Model
QUERY RELEVANT SETS

 How can we cluster when the nature

INTER-SET ASSOCIATION Pearson correlation formula:

CLUSTER COHERENCE

CLUSTERING CRITERION

 Association criterion – if v belongs

 Note: neighborhood size is variable,

to cluster set C, then the items
relevant to v should belong to C.
• R(C,Q(v,|C|)) should be high.

depending upon the cluster size.

of the data is hidden from us?
 Only assumption: oracle providing

relevancy rankings for queries-byexample.
 Q(q, k): ranked relevant set for query

item q, of size k.
 Clusters to be patterned on queryrni 1xi y i  n x y

 x  nx  y  ny ni 12i2ni 12i2AB

 Applying this to coordinate pairs ofof cluster sizes.

set vectors for A, B  S gives setcorrelation between A and B :R( A, B) relevant set (QRS) Q(q, k) for someq in S.

 A B S  A  S  B   A  B
SA  B S total correlation between a set andthe (same-sized) relevant sets ofits members.

D( A)  dist 2 ( A, c( A)) R( A, Q(v, A ))1 K
 R( A, Q(v, A ))n i 1 vATHE CLUSTERING HEURISTIC

R( A)  R( A, Q(v, A ))n i 1 vA Discovers globular/compact clusters.

 Discovers globular/compact clusters.

 Works on numeric data.

 Works with any data type.

 Works only with certain distance measures Any primary distance measure can be(such as the Euclidean distance, Bregman
divergences).

cluster coherence.

vA

GlobalRSC:
 Clustering criterion measures averagecluster coherence.
1 Kn i 1 vA Clustering criterion maximizes total

R( A) COMPARISON WITH K-MEANS

K-Means: Clustering criterion measures averagecluster coherence.
1 K

 Set correlation is unbiased in terms

 Measure of cluster coherence: theemployed.

 2-phase hill-climbing heuristic similar to K-means: consider reassigningeach data point to a new cluster, in such a way that the objective value
is increased.
 Batch update: update cluster membership after all data points has been

considered. Fast but does not ensure objective improvement.
 Incremental update: cluster membership is updated right away for eachpoint. Slow but objective improvement is guaranteed, ensuring
convergence.
 Complexity:2~nO dn2 log n KGlobalRSC
High-Dimensional Data Neighborhood construction becomes
expensive.
 Local optimization approaches becomeless efficient without a good initialization.

 3 microarrays data sets with known class labels.
B1: 384 genes x 17 conditions
B2: 237 genes x 17 conditions
B3: 205 genes x 20 conditions

Scalability
 Initialization: using greedyRSC.
 Construction of neighborhoods
using approximate similarity search
structures, such as RCT or SASH.
 Restrict largest cluster size.

 ALOI data sets, 110250 images of 1000 common objects.
I1: 13943 images x 641 features
I2: 110250 images x 641 features

 Reuters Corpus Volume I (RCV1).
 T1: 200,000 documents x 320648 features
 T2: 20,000 documents x 320648 features

連絡先： Michael E. HOULE (フール マイケル) ／ 国立情報学研究所 客員教授
TEL : 03-4212-2538

FAX : 03-3556-1916

Email : meh@nii.ac.jp