pg.ddx.io  pgsql-students@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Akansha Singh <akansha.singh@oracle.com>
To: Pgsql-Students <pgsql-students@postgresql.org>
Subject: Topic: Agglomerative clustering
Date: Mon, 29 Apr 2013 05:11:42 -0700 (PDT)
Message-ID: <2701ba0a-ce70-45db-9cc2-bf098c019780@default> (raw)
List-Unsubscribe:  <mailto:majordomo@postgresql.org?body=unsub%20pgsql-students>

hi
 i have another clustering algorithm.. Please give your suggestions for this one whether it can be implemented? I will be obliged.

Agglomerative Clustering
In agglomorative clustering, each data point is initially placed in a cluster by itself. At each step, two clusters with the highest similarity score are merged. The output of agglomerative clustering is a tree, where the leaves are the data items. At any intermediate step, the clusters so far are different trees. When two clusters are merged by the algorithm, the respective trees are merged by making the roots of these trees the left and right children of a new node (so that the total number of trees decreases by 1). In the end, the process yields a single tree. See here for an example.

This algorithm closely resembles Kruskal's algorithm for Minimum Spanning Tree construction. In Kruskal's algorithm, at each step the smallest edge connecting two components is added till there is only one component left. Each new edge added merges two components.  This can be seen as clustering where the similarity score between two components is the negative the length of the smallest edge between any two points in the cluster.

Many different clustering algorithms can be obtained by varying the similarity measures between clusters. Some examples of similarity measures are the following. Here, A and B are two clusters, and sim(A,B) is the similarity measure between them. The similarity measure sim(u,v) between input data items u and v is specified as input. Typically, the similarity is a number between 0 and 1, with larger values implying greater similarity.

Regards
Akansha SIngh


-- 
Sent via pgsql-students mailing list (pgsql-students@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-students



Message-ID: <2701ba0a-ce70-45db-9cc2-bf098c019780@default>
Permalink:  ../2701ba0a-ce70-45db-9cc2-bf098c019780@default/
Also on:    postgresql.org/message-id/2701ba0a-ce70-45db-9cc2-bf098c019780@default

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-students@postgresql.org
  Cc: akansha.singh@oracle.com
  Subject: Re: Topic: Agglomerative clustering
  In-Reply-To: <2701ba0a-ce70-45db-9cc2-bf098c019780@default>
  References: <2701ba0a-ce70-45db-9cc2-bf098c019780@default>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox