Evolving Clustering Method (ECM)

ECM Algorithm

This is based on the concept of dynamically adding and modifying the clusters as new data is presented, where the modification to the clusters affects both the position of the clusters and the size of the cluster, in terms of a radius parameter associated with each cluster that determines the boundaries of that cluster. ECM has only one parameter, which drives the addition of clusters, known as the distance threshold $D_{thr}$ . When new clusters are added, their centres are set to equal the example that triggered their creation, and the radius $R$ of a new cluster is initially set to zero. $R$ grows as more vectors are allocated to the cluster. Due to the mechanism by which $R$ is updated, it cannot exceed $D_{thr}$ . The ECM algorithm is shown below:

Create the first cluster centre from the first example $I_{0}$

for each subsequent vector $I_{n}$ do

Find the minimum distance $D_{min}$ between $I_{n}$ and each cluster centre $C_{n}$

if $D_{min}$ is less than any cluster radius then

Add $I_{n}$ to the nearest cluster

else

FInd the cluster $a$ with minimum value of $S_{i, j}$ , where $S_{i, j} = D_{i, j} + R_{i, j}$ , $D_{i, j}$ is the distance between the cluster centre and vector $j$ , and $R_{i}$ is the radius of cluster $i$

if $S_{i, a} > 2 D_{thr}$ then

Create a new cluster

else

Update $a$

end if

end for

When cluster $a$ is updated, its centre is shifted closer to $I_{n}$ and its radius $R_{a} (t + 1)$ is set according to the equation below:

$R_{a} (t + 1) = \frac{S_{i, a}}{2}$

The new centre of $a, C_{a} (t + 1)$ is set so that its distance is on the line between $C_{a} (t)$ and $I_{n}$ at a distance of $R_{a} (t + 1) .$

Maintained by Dr Michael J. Watts