Clustering Two by Two

An earlier post covered the K-Means clustering algorithm, in this post I will cover hierarchical agglomerative clustering (HAC).  The HAC algorithm starts with each observation as a cluster and successively groups them based on shortest distance or highest similarity until all observations belong to a single cluster. There are  several ways to judge closest or most similar when comparing two clusters. They include the cluster average, the furthest members or nearest members; this post uses the nearest members algorithm.

The first step is to create a table of data.  Then compute the distance between clusters which will be used to successively cluster the observations.   The last step is displaying the results. Programs like R offer neat dendrogram graphics not available in SQL; to overcome this the post will offer code to dynamically create a table of clusters for each pass. Not ideal, but passable.

To keep it easy and visual, each observation has two dimensions that are randomly determined on a 0-100 scale.  The first query creates the data table while the loop assigns a value to the dimensions X1 and X2 which in this case is displayed below.  Note your results will differ because X1 and X2 are randomly assigned each time the program is run.

create table #data (id int, x1 float, x2 float)

declare @id int
set @id =1
while @id<=12
begin
insert into #data select @id, round(dbo.fx_rand()*100,0), round(dbo.fx_rand()*100,0)
set @id = @id+1
end

select x1,x2,id from #data

Distance is computed between all observation pairs using euclidean distance by joining the data table to itself on the observation id.  Redundant distances (A to B = B to A) and irrelevant pairs (A to A) are eliminating by specifying that the id in the first table is greater than the id in the second.  Other measures of distance could be used as well as the inverse of similarity; similar items are usually defined as near to each other (low distance) and dissimilar far apart (high distance).  The cluster ids are overwritten as clusters are merged and therefore archived in the aid2 and bid2 fields.

create table #distance (aid int, bid int,aid2 int, bid2 int, distance float )

insert into #distance select a.id, b.id,a.id, b.id, power(power(a.x1-b.x1,2)+power(a.x2-b.x2,2),.5) distance from #data a join #data b on a.id >b.id

The clusters are stored in the #hierarchy table as a parent-child relations ship. Starting with the individual observations as a parent id (and 0 as the child id), the algorithm finds the nearest pair of clusters, insets them into the hierarchy table as children and assigns the next sequential id as parent.  In the distance table the id's for the merged clusters are updated to the new parent id. This insures that the nonmembers of a cluster are compared to their nearest neighbor from within a cluster and saves time in recalculating the distance matrix. The algorithm stops when all clusters have the same cluster id in the distance table.

create table #hierarchy( cid int, pid int, pass int)

declare @aid int, @bid int, @pid int, @pass int
set @pass = 0
insert into #hierarchy (cid,pid, pass) select 0 ,id,@pass from #data

while 1=1
begin 
set @pass = @pass+1
select top 1 @aid = aid, @bid = bid from #distance where aid<>bid  order by distance, newid() 
if @@rowcount = 0 break

select @pid = max(pid)+1 from  #hierarchy
insert into #hierarchy(cid,pid, pass)  select @aid, @pid, @pass
insert into #hierarchy(cid,pid, pass)  select @bid, @pid, @pass

update #distance set aid = @pid where aid in (@aid, @bid)
update #distance set bid = @pid where bid in (@aid, @bid)
end

The next problem is how to display the results.  As noted earlier the usual way to display HAC is through snappy graphic known as a dendrogram, but since TSQL offers no graphics an alternate solution is to create a table that shows the clustering using the parent ids.  The following query uses dynamic SQL to build a table adding a column for each pass populated with id's of the parent cluster

create table #list (p0 int)

insert into #list select pid from #hierarchy where pass = 0 

declare @pass int

declare @sql varchar(200)

set @pass = 1

while @pass<= (select max(pass) from #hierarchy)

begin

set @sql = 'alter table #list add p'+cast(@pass as varchar)+' int'

exec (@sql)

set @sql = 'Update l  set p'+cast(@pass as varchar)+ '= 

case when pid is null then p'+cast(@pass-1 as varchar)+' else pid end from #list l

left join  #hierarchy b

on p'+cast(@pass-1 as varchar)+' = cid and pass ='+ cast(@pass as varchar)

exec (@sql)

set @pass = @pass+1

end

select * from #list  

order by p11 ,p10 ,p9 ,p8 ,p7 ,p6 ,p5 ,p4 ,p3 ,p2 ,p1 ,p0 

p0	p1	p2	p3	p4	p5	p6	p7	p8	p9	p10	p11
8	8	8	8	8	8	8	19	19	19	19	23
12	12	12	12	12	12	18	19	19	19	19	23
5	5	14	14	14	14	18	19	19	19	19	23
6	13	14	14	14	14	18	19	19	19	19	23
9	13	14	14	14	14	18	19	19	19	19	23
11	11	11	11	11	11	11	11	11	11	22	23
7	7	7	7	16	16	16	16	16	21	22	23
10	10	10	10	16	16	16	16	16	21	22	23
2	2	2	2	2	2	2	2	20	21	22	23
3	3	3	3	3	17	17	17	20	21	22	23
1	1	1	15	15	17	17	17	20	21	22	23
4	4	4	15	15	17	17	17	20	21	22	23

The results conform with the visual evident clustering above.  Immediately 9 & 6 cluster followed by 5 while next 1 & 4 start  new cluster; all clearly close together in the above chart.  Ultimately  the data set forms two clusters one with  8, 6, 12 & 9  and the other with the balance  which is again consistent with the visual expectations.

K Means Clustering

Perhaps the most successful data mining algorithm after simple statistics and regression is the clustering algorithm known as k-means.  It is a deceptively simple iterative processes that applies easily understood similarity measures to group observations (records) into homogeneous clusters.  It has a wide variety of applications including identifying extreme observations , data reduction, document clustering and more; a quick Google search will reveal all.

The basic algorithm is simple:

1. Prepare the data set (initially consider only ratio data, a future post will go into catagorical data).  There really is no limit on the number of attributes that can be considered, however the more there are the less influence each will have on the cluster assignment processes. To ensure no single attribute overwhelms the analysis, normalize the data by subtracting the attribute average and dividing by the standard deviation.
2. Select the number of clusters and randomly assign each observation to one of the clusters   A draw-back of k-means is that the user must pre-specify the number of clusters rather than have the ideal number identified by the algorithm. 
3. Calculate the mean  for each attribute for each cluster.
4. For each observation calculate the similarity to each cluster mean and if the observation is more similar to a different cluster than which it is currently assigned, re-assign it to the more similar cluster.
5. Repeat steps 3 & 4 till observations stop moving between clusters.

There are a variety of similarity measures, but the most frequently used for ratio data is the inverse of the Euclidean distance. The nearest cluster is the most similar and the distance is calculated as the sum of the square of the difference between the observation's attribute value and the cluster mean  for that attribute. This model will use the absolute value of the difference rather than squaring which tends to reduce the impact of an extreme observation.  If the data is categorical, like in document clustering where the attributes are words and the values are the frequency for a given document, cosine similarity, (A*B)/ ((A^2)^.5)((B^2)^.5), produces good results

In addition to the raw data table  where each record is an observation made up of attributes, the SQL program requires 2 tables: 1. the data in vector  format (#data), 2. the observations aka records by cluster (#class).  The first table converts the matrix data into a vector (essentially each record is row, column, value where row is the record id and column is the attribute name with value is the value normalized through sub-queries from the raw data table).  The second keeps track of the cluster membership of each id.

create table #rawdata (id int,area float, rooms float, price float)

insert into #rawdata select 1, 2201,3,400

insert into #rawdata select 2, 1600,3,330

insert into #rawdata select 3, 2400,3,369

insert into #rawdata select 4, 1416,2,232

insert into #rawdata select 5, 3000,4,540

select id, 'area' attribute, (area-(select avg(area) from #rawdata))/(select stdev(area) from #rawdata) value  into #data from #rawdata

union all

select id, 'rooms' , (rooms-(select avg(rooms) from #rawdata))/(select stdev(rooms) from #rawdata)  from #rawdata

union all

select id, 'price' , (price-(select avg(price) from #rawdata))/(select stdev(price) from #rawdata)  from #rawdata

select id, cast(2*dbo.fx_rand() as int) class into #class from #data  group by id

In the last query the id's are randomly assigned to one of 2 classes (the highlighted statement beginning with the number of clusters).  Ideally SQL would permit this using the built-in rand() statement, but it generates a single random number per query and doesn't change with each record in the results.  Two work around for this are first, create a view vw_rand and a user defined function fx_rand():

create view vw_rand 
as

select rand() as random

create function fx_rand ()

returns float

as

begin

return (select random from vw_rand)

end

The second solution which is simpler than creating views and functions is to replace fx_rand () with cast(right(checksum(newid()),3) as float)/1000  to generate a pseudo random number between 0.000 and 0.999.  While both return "random" numbers their validity has not to the best of my knowledge been evaluated; for the purposes of this algorithm they both appear to work.

Next is the heart of the program that summarizing the attribute data for the observations by cluster and then compares each record to each cluster updating the assignment if a different cluster is closer.  This continues until the stopping condition --no further re-assignments are made--is met.  

while 1=1

begin 

;with cte1 as

(select attribute, class, avg(value) mean 

from #data d join #class c on d.id = c.id  group by attribute, class),

cte2 as 

(select d.id,c.class, sum(abs(d.value-c.mean)) dist  from cte1 c join #data d on c.attribute = d.attribute 

group by d.id, c.class),

cte3 as 

(select id, min(dist) mindist from cte2  group by id),

cte4 as

(select  a.id, min(class) newclass  from cte3 a join cte2 b on  mindist = dist group by a.id)

update c set class = newclass from #class c join cte4 b on c.id = b.id where class<>newclass

if @@rowcount = 0 break

end 

The query uses a common table expressions (CTE) which makes programming easier than creating and dropping temporary tables or stacking sub-queries like so many planes over O'Hare but has the disadvantage of not working outside T-SQL and the results of the interim steps are not available for debugging.  The first CTE  calculates the centers for each of the attributes for each cluster.  The second  calculates the distance to each cluster for each observation; if you want to use the Pythagorean based calculation change abs(d.value-c.mean) to power(d.value-c.mean,2). CTE3 identifies the shortest distance to a cluster and CTE4 identifies the cluster associated with that shortest distance with any ties going arbitrarily to the cluster with the lower class number.  Finally, any observations with new cluster assignments are updated and the processes stops is repeated until no further updates are made.

To evaluate the effects of the algorithm, use the following 2 queries to link  first the initial clusters then  the results back to the raw data table:

select c.id,c.class cluster, area, rooms,price from #class c  join #rawdata d on c.id = d.id  order by c.id

select class cluster, count(1) freq, avg(area) avg_area, avg(rooms) avg_rooms, avg(price) avg_price from #class c  join #rawdata d on c.id = d.id 
group by class

Initial clusters:

id	cluster	area	rooms	Price
1	1	2201	3	400
2	1	1600	3	330
3	0	2400	3	369
4	0	1416	2	232
5	0	3000	4	540

cluster	freq	avg area	avg rooms	avg price
0	3	2272.0	3	380.3
1	2	1900.5	3	365.0

After running the algorithm record 1 was moved to cluster 0 and record 4 was moved to cluster 1 and from the summary table it is evident that greater distinction is made on all variables with cluster 0 being the larger more expensive houses.

id	cluster	area	rooms	Price
1	0	2201	3	400
2	1	1600	3	330
3	0	2400	3	369
4	1	1416	2	232
5	0	3000	4	540

cluster	freq	avg area	avg rooms	avg price
0	3	2533.7	3.3	436.3
1	2	1508.0	2.5	281.0

A couple of final issues to consider.  First, k-means can be sensitive to the initial cluster assignments especially when there are many clusters.  Should this happen run the program several times to identify a preferred solution, much like the pocked solution in the post on the Perceptron.  Finally,  it is not uncommon for k-means to produce a solution with fewer clusters than originally specified, particularly when the sample size is small.  Running the above with 3 clusters produces a 2 cluster solution.  Either go with the fewer clusters or try a different similarity measure.