Adaptive Affinity Propagation Clustering in MapReduce Environment - Technologies and Applications of Artificial Intelligence - page 212

The maximum preference ( ) in the range is the value which clusters the N data
points into N clusters, and this is equal to the maximum similarity, since a preference
lower than that would make the object better to have the data point associated with
that maximum similarity assigned to be a cluster member rather than an exemplar.
The derivation for is similar to . Compute dpsim1max ∑ ,

,

dpsim2max ∑ max,,, , Compute the minimal value of prefe-

rence 1 2 .
After computing the range of preferences, we can scan through preferences space
to find the optimal clustering result. Different preferences would lead to different
cluster results. Cluster validation techniques are used to evaluate which clustering
result is optimal for the datasets. The preference step is very important to scan the
space adaptively, where ⁄ . To sample the whole space, we set
the base of scanning step as ⁄ .
We employ the global silhouette index as the validity indices. The silhouette index
is introduced by Rousseeuw [12] as a general graphical aid for interpretation and vali-
dation of cluster analysis, which provides a measure of how well a data point is classi-
fied when it is assigned to a cluster in according to both the tightness of the clusters
and the separation among clusters.
The global silhouette index is defined as follows:
GS

∑

(3)

Local silhouette index is defined as:

,

∑

(4)

Where is the count of the objects in class j , is the average distance
between object i and the objects in the same class j , is the minimum average
distance between object i and objects in class closet to class j . The largest global sil-
houette index indicates the best clustering quality and the optimal number of clusters
[12-13]. A series of global silhouette index values corresponding to clustering
result with different number of cluster are calculated. The optimal clustering result is
found when is largest.
The AAP clustering method steps are as follow:
Step1: Apply Preferences Range algorithm to computing the range of preferences:

, (5)

Step2: Initialize the preferences:

(6)
Step3: Update the preferences:

(7)
Step4: Apply the AP algorithm to generating K clusters.
Step5: Terminate until is largest.