{"id":2490,"date":"2015-06-08T22:22:46","date_gmt":"2015-06-08T21:22:46","guid":{"rendered":"http:\/\/www.blopig.com\/blog\/?p=2490"},"modified":"2015-06-08T22:22:46","modified_gmt":"2015-06-08T21:22:46","slug":"clustering-algorithms","status":"publish","type":"post","link":"https:\/\/www.blopig.com\/blog\/2015\/06\/clustering-algorithms\/","title":{"rendered":"Clustering Algorithms"},"content":{"rendered":"

Clustering is a task of organizing data into groups (called clusters), such that members of each group are more similar to each other than to members of other groups. This is a brief description of three popular clustering algorithms \u2013 K-Means<\/a>, UPGMA<\/a> and DBSCAN<\/a><\/strong>.<\/p>\n

\"Cluster<\/a>

Cluster analysis<\/p><\/div>\n

K-Means<\/a> is arguably the simplest and most popular clustering algorithm<\/strong>. It takes one parameter \u2013 the expected number of clusters k<\/strong>. At the initialization step a set of k means<\/strong> m1<\/sub>, m2<\/sub>,\u2026, mk <\/sub>is generated (hence the name). At each iteration step the objects in the data are assigned to the cluster whose mean yields the least within-cluster sum of squares. After the assignments, the means are updated<\/strong> to be centroids of the new clusters. The procedure is repeated until convergence<\/strong> (the convergence occurs when the means no longer change between iterations).<\/p>\n

The main strength of K-means is that it’s simple and easy to implement<\/strong>. The largest drawback of the algorithm is that one needs to know in advance how many clusters the data contains<\/strong>. Another problem is that with wrong initialization<\/strong> the algorithm can easily converge to a local minimum<\/strong>, which may result in suboptimal partitioning of data.<\/p>\n

UPGMA <\/a>is a simple hierarchical clustering method<\/strong>, where the distance between two clusters is taken to be the average of distances between individual objects in the clusters. In each step the closest clusters are combined, until all objects are in clusters where the average distance between objects is lower than a specified cut-off<\/strong>.<\/p>\n

The UPGMA algorithm is often used for construction of phenetic trees<\/strong>. The major issue with the algorithm is that the tree it constructs is ultrametric<\/strong>, which means that the distance from root to any leaf is the same. In context of evolution, this means that the UPGMA algorithm assumes a constant rate<\/strong> of accumulation of mutations, an assumption which is often incorrect.<\/p>\n

DBSCAN <\/a>is a density-based algorithm<\/strong> which tries to separate the data into regions of high density, labelling points that lie in low-density areas as outliers. The algorithm takes two parameters – \u03b5 and minPts<\/strong> and looks for points that are density-connected<\/em><\/strong> with respect to \u03b5. A point p is said to be density reachable<\/em><\/strong> from point q if there are points between p and q, such that one can traverse the path from p to q never moving further than \u03b5 in any step. Because the concept of density-reachability is not symmetric<\/strong> a concept of density-connectivity is introduced. Two points p and q are density-connected if there is a point o such that both p and q are density reachable from o. A set of points is considered a cluster if all points in the set are mutually density-connected and the number of points in the set is equal to or greater than minPts<\/strong>. The points that cannot be put into clusters are classified as noise<\/strong>.<\/p>\n

\"a)Illustrates<\/a>

a) Illustrates the concept of density-reachability.
b) Illustrates the concept of density-connectivity<\/p><\/div>\n

The DBSCAN algorithm can efficiently detect clusters with non-globular shapes<\/strong> since it is sensitive to changes in density only. Because of that, the clustering reflects real structure present in the data. The problem with the algorithm is the choice of parameter \u03b5<\/strong> which controls how large the difference in density needs to be to separate two clusters.<\/p>\n","protected":false},"excerpt":{"rendered":"

Clustering is a task of organizing data into groups (called clusters), such that members of each group are more similar to each other than to members of other groups. This is a brief description of three popular clustering algorithms \u2013 K-Means, UPGMA and DBSCAN. K-Means is arguably the simplest and most popular clustering algorithm. It […]<\/p>\n","protected":false},"author":31,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","wikipediapreview_detectlinks":true,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"ngg_post_thumbnail":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"ppma_author":[493],"class_list":["post-2490","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"authors":[{"term_id":493,"user_id":31,"is_guest":0,"slug":"jaroslaw","display_name":"jaroslaw nowak","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/d3ddaccc000bffff018a1bdedaebefb1ac9454506ae5203150e7b3efd8dd9a6e?s=96&d=mm&r=g","0":null,"1":"","2":"","3":"","4":"","5":"","6":"","7":"","8":""}],"_links":{"self":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts\/2490","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/users\/31"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/comments?post=2490"}],"version-history":[{"count":7,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts\/2490\/revisions"}],"predecessor-version":[{"id":2499,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts\/2490\/revisions\/2499"}],"wp:attachment":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/media?parent=2490"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/categories?post=2490"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/tags?post=2490"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=2490"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}