词条 | K-medoids | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
释义 |
The {{math|k}}-medoids or PAM algorithm is a clustering algorithm reminiscent to the {{math|k}}-means algorithm. Both the {{math|k}}-means and {{math|k}}-medoids algorithms are partitional (breaking the dataset up into groups) and both attempt to minimize the distance between points labeled to be in a cluster and a point designated as the center of that cluster. In contrast to the {{math|k}}-means algorithm, {{math|k}}-medoids chooses data points as centers (medoids or exemplars) and can be used with arbitrary distances, while in {{math|k}}-means the centre of a clusters is not necessarily one of the input data points (it is the average between the points in the cluster). The PAM method was proposed in 1987[1] for the work with norm and other distances. {{math|k}}-medoid is a classical partitioning technique of clustering, which clusters the data set of {{math|n}} objects into {{math|k}} clusters, with the number {{math|k}} of clusters assumed known a priori (which implies that the programmer must specify k before the execution of the algorithm). The "goodness" of the given value of {{math|k}} can be assessed with methods such as silhouette.It is more robust to noise and outliers as compared to {{math|k}}-means because it minimizes a sum of pairwise dissimilarities instead of a sum of squared Euclidean distances. A medoid can be defined as the object of a cluster whose average dissimilarity to all the objects in the cluster is minimal, that is, it is a most centrally located point in the cluster. AlgorithmsThe most common realisation of {{math|k}}-medoid clustering is the Partitioning Around Medoids (PAM) algorithm. PAM uses a greedy search which may not find the optimum solution, but it is faster than exhaustive search. It works as follows:
The runtime complexity of the original PAM algorithm per iteration of (3) is , but this can be reduced to .[2] Algorithms other than PAM have also been suggested in the literature, including the following Voronoi iteration method:[3]{{r|park}}
However, Voronoi iteration finds much worse results, as it does not allow reassigning points to other clusters while changing means, and thus only explores a much smaller search space.[2] The approximate algorithms CLARA and CLARANS trade runtime for optimality. CLARA applies PAM on multiple subsamples, keeping the best result. CLARANS works on the entire data set, but only explores a subset of the possible swaps of medoids and non-medoids. Demonstration of PAM{{tone|date=September 2015}}Cluster the following data set of ten objects into two clusters i.e. {{math|k {{=}} 2}}. Consider a data set of ten objects as follows :
Step 1Two observations ( and ) are randomly selected as medoids (cluster centers). Manhattan distances are calculated to each center to associate each data object to its nearest medoid (marked in bold).
Since the points {{math|(2,6)}} {{math|(3,4)}} {{math|(3,8)}} and {{math|(4,7)}} are closer to {{math|c1}} hence they form one cluster whilst the remaining points form another cluster. Therefore, the clusters become: {{math|Cluster1 {{=}} {(2,6)(3,4)(3,8)(4,7)} }} {{math|Cluster2 {{=}} {(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)} }} The total cost of this clustering is the sum of the distance between a data point and its cluster center: Step 2Select one of the nonmedoids {{mvar|O′}} Let us assume {{math|O′ {{=}} (7,3)}}, i.e. {{math|x7}}. So now the medoids are {{math|c1(3,4)}} and {{math|O′(7,3)}} If {{tmath|c_1}} and {{mvar|O′}} are new medoids, calculate the total cost involved By using the formula in the step 1
So cost of swapping medoid from {{math|c2}} to {{mvar|O′}} is So moving to {{mvar|O′}} would be a bad idea, so the previous choice was good. So we try other nonmedoids points to get minimum distance. It may happen some data points may shift from one cluster to another cluster depending upon their closeness to medoid. In some standard situations, k-medoids demonstrate better performance than k-means. An example is presented in Fig. 2. The most time-consuming part of the k-medoids algorithm is the calculation of the distances between objects. If a quadratic preprocessing and storage is applicable, the distances matrix can be precomputed to achieve consequent speed-up. See for example,[5] where the authors also introduce a heuristic to choose the initial {{mvar|k}} medoids. Software
References1. ^Kaufman, L. and Rousseeuw, P.J. (1987), Clustering by means of Medoids, in Statistical Data Analysis Based on the –Norm and Related Methods, edited by Y. Dodge, North-Holland, 405–416. {{DEFAULTSORT:K-Medoids}}2. ^1 {{cite arxiv|last=Schubert|first=Erich|last2=Rousseeuw|first2=Peter J.|date=2018-10-12|title=Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms|eprint=1810.05691|class=cs.LG}} 3. ^T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning, Springer (2001), 468–469. 4. ^The illustration was prepared with the Java applet, E.M. Mirkes, K-means and K-medoids: applet. University of Leicester, 2011. 5. ^H.S. Park , C.H. Jun, A simple and fast algorithm for K-medoids clustering, Expert Systems with Applications, 36, (2) (2009), 3336–3341. 1 : Cluster analysis algorithms |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。