 ```! Clustering. (Clustering.lng) Partition items into clusters so that items in the same cluster are close together according to some distance metric; ! We compute a distance, D(i,j) for every pair of ITEMS i, j. The cost of a cluster is the sum of all the D(i,j)'s in the cluster. We assign items to clusters so as to minimize these within cluster distances.; ! Keywords: Classification, Clustering, Data Mining, Grouping, Statistics; SETS: ITEM; ATTRIBUTE: TYPE, SCALE; IXA( ITEM, ATTRIBUTE): RESPONSE; CLUSTER; IXI( ITEM, ITEM) | &1 #LT# &2: D, Y; IXC( ITEM, CLUSTER) : Z; ENDSETS! Clustering problem. Assign items to clusters so that items that are close are assigned to the same clusters; DATA: CLUSTER = C1..C2; ! Surveyed some people who use our exercise equipment, and got their ! Height in cm, Satisfaction level (1 to 5), Favorite equipment color(3 choices); ATTRIBUTE = HGT SATLVL FCOLOR; ! Type of response: Cardinal(1), Ordinal(2), Categorical(3); TYPE = 1 2 3; ITEM = I1..I11; ! ITEM = I1..I20; RESPONSE = 186 4 3 ! 1; 177 3 1 ! 2; 180 5 2 ! 3; 183 4 1 ! 4; 171 2 2 ! 5; 158 1 3 ! 6; 204 5 3 ! 7; 180 4 1 ! 8; 189 3 1 ! 9; 189 1 3 !10; 168 2 2 !11; ! 174 5 3 ! 195 4 1 !13; ! 162 4 2 ! 192 1 3 !15; ! 207 5 2 ! 204 1 1 !17; ! 155 1 2 ! 162 4 3 !19; ! 180 5 1; ; ENDDATA ! Variables: X(i,k) = 1 if item i is assigned to cluster k, Y(i,j) = 1 if items i and j are in the same cluster ; SUBMODEL DOCLUSTER: ! Minimize the distance among items in same cluster; MIN = REDDIF; REDDIF = @SUM( IXI(i,j): D(i,j)*Y(i,j)); ! Each item i must be in some cluster k; @FOR( ITEM(i): @SUM( CLUSTER(k): Z(i,k)) = 1; ); ! Measure interaction. Force Y(i,j) = 1 if i and j in same cluster; @FOR( IXI(i,j): @FOR( CLUSTER(k): Y(i,j) >= Z(i,k) + Z(j,k) - 1; @BND(0, Y(i,j), 1); ); ); ! Z(i,k) can be only 0 or 1; @FOR( IXC(i,k): @BIN( Z(i,k)); ); ! Optionally, some cuts; ! On average, each cluster has NPC*(NPC-1)/2 interaction terms; @SUM( IXI(i,j): Y(i,j)) >= NCLUST*NPC*(NPC-1)/2; ! Optionally, Kill some symmetry; ! We may arbitrarily order the clusters so If item i is in cluster k, then some lower numbered item must be in cluster k-1; ! @FOR( IXC(i,k) | k #GT# 1: Z(i,k) <= @SUM( ITEM( j) | j #LT# i: Z(j,k-1)) ); ! Item 2 cannot be assigned to cluster higher than 2; @SUM( CLUSTER(k) | k #GT# 2: Z(2,k)) = 0; ! If item 2 assigned to cluster 1, then item 3 cannot be assigned to cluster 3; @SUM( CLUSTER(k) | k #GT# 2: Z(3,k)) + Z(2,1) <= 1; ENDSUBMODEL CALC: NITEM = @SIZE( ITEM); NCLUST = @SIZE( CLUSTER); ! Average items per cluster; NPC = @FLOOR( NITEM/ NCLUST); ! Compute the scale factor for each attribute; ! Type 1 is a cardinal measure, so scale by the standard deviation, so most values are < 1; @FOR( ATTRIBUTE(j) | TYPE(j) #EQ# 1: MEAN = @SUM( ITEM(i): RESPONSE(i,j))/NITEM; SD = (@SUM( ITEM(i): ( RESPONSE(i,j)- MEAN)^2)/ NITEM)^0.5; @IFC( SD #GT# 0: SCALE(j) = SD*2^(0.5); @ELSE SCALE(j) = 1; ); ); ! Ordinal attributes scaling. Type 2 is an ordinal measure, so scale by the range so largest value is 1; @FOR( ATTRIBUTE(j) | TYPE(j) #EQ# 2: ENDLO = RESPONSE(1,j); ENDHI = RESPONSE(1,j); @FOR( ITEM(i): ENDLO = @SMIN( ENDLO, RESPONSE(i,j)); ENDHI = @SMAX( ENDHI, RESPONSE(i,j)); ); SCALE(j) = ENDHI - ENDLO; @IFC( SCALE(j) #EQ# 0: SCALE(j) = 1); ); ! Compute distances between all item pairs; TOTDIF = 0; @FOR( IXI(i,j): ! For cardinal and ordinal; D(i,j) = @SUM( ATTRIBUTE(k) | TYPE( k) #EQ# 1 #OR# TYPE(k) #EQ# 2: @ABS( RESPONSE(i,k)- RESPONSE(j,k))/SCALE(k)) + @SUM( ATTRIBUTE(k) | TYPE(k) #EQ# 3 #AND# RESPONSE(i,k) #NE# RESPONSE(j,k): 1); TOTDIF = TOTDIF + D(i,j); ); ! Type 3 is a categorical measure, so score 1 if different, 0 if the same; @SOLVE( DOCLUSTER); RSQD = 1 - REDDIF/TOTDIF; @WRITE( 'Fraction of differences',@NEWLINE(1), ' explained by clustering= ', @FORMAT(RSQD,"6.4F"), @NEWLINE(1)); @WRITE( 'Cluster Contents', @NEWLINE(1)); @FOR( CLUSTER(k): @FOR( IXC(i,k) | Z(i,k) #GT# 0.5: @WRITE( ' ',CLUSTER(k),' ', ITEM(i), @NEWLINE(1)); ); ); ENDCALC ```