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

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

Definition of the Algorithm #

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 the sender ID, or any other string feature encoding. This space has been called Sm.

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

Computing centroid

For each center

• Let cn be the projection of the center in the Sn space. Set cn as the mean of the equivalent features of the examples classified to c.
• Choose a number p of mails that are closest to cn in the Sn space. p can be smaller than the total number of mails assigned to c.
• Determine the projection of c in Sm that is cm using k-medoids on the p items chosen above.
• The new center of the cluster will be the combination of its projections, c=[cn cm]*

Note: in this algorithm there is a strong assumption: a correlation between Sn and Sm, in fact we compute cm, only on points that belong to cluster previously computed in Sn. It isn't always right.

Similarity

TODO