Data Mining: The Textbook

Determination of bad medoids: The determination of “bad” medoids from S_best is per-
formed as follows: The medoid of the cluster with the least number of points is bad. In addition, the medoid of any cluster with less than (n/k) · minDeviation points is bad, where minDeviation is a constant smaller than 1. The typical value was set to 0.1. The assumption here is that bad medoids have small clusters either because they are outliers or because they share points with another cluster. The bad medoids are replaced with random points from the candidate medoid set M .


Refinement phase: After the best set of medoids is found, a final pass is performed over the data to improve the quality of the clustering. The dimensions associated with each medoid are computed differently than in the iterative phase. The main difference is that to analyze the dimensions associated with each medoid, the distribution of the points in the clusters at the end of the iterative phase is used, as opposed to the localities of the medoids. After the new dimensions have been computed, the points are reassigned to medoids based on the Manhattan segmental distance with respect to the new set of dimensions. Outliers are also handled during this final pass over the data. For each medoid i, its closest other medoid is computed using the Manhattan segmental distance in the relevant subspace of medoid i. The corresponding distance is referred to as its sphere of influence. If the Man-hattan segmental distance of a data point to each medoid is greater than the latter’s sphere of influence, then the data point is discarded as an outlier.
7.4.3 ORCLUS

The arbitrarily ORiented projected CLUStering (ORCLUS) algorithm finds clusters in arbi-trarily oriented subspaces, as illustrated in Fig. 7.2b. Clearly, such clusters cannot be found by axis-parallel projected clustering. Such clusters are also referred to as correlation clus-ters. The algorithm uses the number of clusters k, and the dimensionality l of each subspace E_i as an input parameter. Therefore, the algorithm returns k different pairs (C_i, E_i), where the clusterC_i is defined in the arbitrarily oriented subspace E_i. In addition, the algorithm reports a set of outliers O. This method is also referred to as correlation clustering. Another difference between the PROCLUS and ORCLUS models is the simplifying assumption in the latter that the dimensionality of each subspace is fixed to the same value l. In the former case, the value of l is simply the average dimensionality of the cluster-specific subspaces.

The ORCLUS algorithm uses a combination of hierarchical and k-means clustering in conjunction with subspace refinement. While hierarchical merging algorithms are generally more effective, they are expensive. Therefore, the algorithm uses hierarchical representatives that are successively merged. The algorithm starts with k_c = k₀ initial seeds, denoted by S.

7.4. HIGH-DIMENSIONAL CLUSTERING

223

Algorithm ORCLUS(Data: D, Clusters: k, Dimensions: l)

begin
Sample set S of k₀ > k points from D;

k_c = k₀; l_c = d;
Set each Ei to the full data dimensionality;
_{α = 0.5; β = e}−log(d/l)·log(1/α)/log(k0/k)_;
while (k_c > k) do
begin
Assign each data point in D to closest seed in S using projected distance in E_i to create C_i;
Re-center each seed in S to centroid of cluster C_i;

Use PCA to determine subspace E_i associated with C_i by selecting smallest l_c eigenvectors of covariance matrix of C_i;