Overview on algorithm

Basic K-Means Algorithm #

This is how the standard algorithm work

1) Initialization: randomly select K data points as the initial centroids
i) repeat  i
    i.1) Assignment step: form K clusters by assigning all points to closest centroid
    i.2) Update step: recompute the centroid of each cluster
until) stopping conditions are met

Complexity: O(ikn) with i iterations, k centroids, n points

Details

• K is the number of clusters
• centroid is the mean of the points in cluster
• closeness is measured by a distance based on some features of points
• stopping conditions deal with convergence (centroids don't change, few points change clusters,...)

Basic K-Medoids Algorithm

K-medoids is similar to k-Means, but instead of choosing the centroid as the mean of the cluster elements, it defines the center as the element whose distance to all the others is minimal.

The most common realisation of k-medoid clustering is the Partitioning Around Medoids (PAM) algorithm and is as follows:

1) Initialization: randomly select K data points as the initial medoids
i) repeat i
	i.1) Assignment step: form K clusters by assigning all points to closest medoid
	i.2) Update step: for each medoid m and each data point o associated to m:  
		swap m and o and compute the total cost of the configuration   
		(that is, the average dissimilarity of o to all the data points associated to m).     
		Select the medoid o with the lowest cost of the configuration.  
until) stopping conditions are met

Complexity: O(ik(n-k)^2) with i iterations, k medoids, n points

Definition of the Algorithm #

To generalize the clustering algorithm we need to define a function
f : Email -> Point
that maps email on a point. PM this is a point on a multi-dimensional space.

Two approaches have been considered to characterize spam email features. The set of values can be regarded as a feature vector that represents the email’s position in a n-dimensional feature space.

The first way uses directly quantifiable properties for which you can compute an average such as its date.This space has been called Sn.

The second one uses instead features without a computable "mean" such as any string feature encoding. This space has been called Ss.

So we have to define distance for each feature and how to compute them only in one, how to compute a new centroid and how to combine spaces in an unique space Sn+s.

Let's consider a feature vector representing a data point such as PM = ([n]|[s]) with [n] a set of Sn features and [s] a set of Ss features.

1. Select k data points as the initial centers [C] based on certain criteria (randomly)
2. For each PM compute a distance D = sum ( Wi * NDi ) with Wi the weight for feature i and NDi the normalized distance for features ndi.
3. On the basis of D every PM can be associated to the closest center among [C]
4. Each center C is linked to a cluster containg containing some PM, we have (C, [PM]).
   To compute the new [C], for each center C = ( [cn] | [cs] ): 4. Let [cn] be the projection of the center C in the Sn space
   4. Set each feature cn as the mean on the numeric feature n of the data points associated to C 4. Let [cs] be the projection of the center C in the Ss space 4. Set each feature cs as the medoid on the string feature s of the data points associated to C
5. The new center of the cluster will be the combination of its projections, C = ( [cn] | [cs] )
6. After the update step, continue to step 2) until stop condition are met.

Improvement

If we identify some correlation between features sn and ss that belong to different space Sn and Ss, we can improve the update step that uses Medoids. In this case, a feature ss could varie little within a cluster computed on feature sn. So let's proceed as follows for step 4.3 and 4.4:
4.3 Choose a number p of data points that are closest to cn in the Sn space. Note p can be smaller than the total number of points assigned to c
4.4 Determine the projection of c in Ss that is cs using k-medoids on the p items chosen above In this way we can save time, because we reduce input number for the update step.