I'm just introduced to data mining as I'm working on a project in clustering.Now I have to implement K-Medoid Clustering.I googled, found the algorithm and also saw a good example in Wikipedia.But I have a few doubts regarding the algorithm and I think it's better if I pose them wrt to the example in Wikipedia.There were a number of points and the initial medoids arec1 = (3,4) and c2 = (7,4)Now using Manhattan Distance the clusters areCluster1 = {(3,4)(2,6)(3,8)(4,7)}Cluster2 = {(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)}Now they have calculated the cost for this arrangement as cost = 20Everything seems clear till now. But now the algorithm is performing an unique thing that is randomly selecting a new medoid and calculating the new cost.I'm quoting So moving to O would be a bad idea, so the previous choice was good. So we try other nonmedoids and found that our first choice was the best. So the configuration does not change and algorithm terminates here.Also I have found in other resources that the time complexity is O(k(n-k)^2) where n = number of points and k = number of clusters.Now my question is how many times I have to elect a new medoid before concluding that there are no better possibilities?Also if I have to find the best case then I believe I have to find all possible combinations and that costs me O(n!).Then why they are saying choose randomly and not use brute force? What am i missing? Can anyone help?Thanks in advance.
K Medoid Clustering using PAM
data mining;clustering