source/cluster/unres/src/hc.f

   1 C***********************  Contents  ****************************************
   2 C* Sample driver program, VAX-11 Fortran; **********************************
   3 C* HC: O(n^2) time, O(n^2) space hierarchical clustering, Fortran 77 *******
   4 C* HCASS: determine cluster-memberships, Fortran 77. ***********************
   5 C* HCDEN: draw upper part of dendrogram, VAX-11 Fortran. *******************
   6 C* Sample data set: last 36 lines. *****************************************
   7 C***************************************************************************
   8 C      REAL DATA(18,16),CRIT(18),MEMBR(18)
   9 C      REAL CRITVAL(9)
  10 C      INTEGER IA(18),IB(18)
  11 C      INTEGER ICLASS(18,9),HVALS(9)
  12 C      INTEGER IORDER(9),HEIGHT(9)
  13 C      DIMENSION NN(18),DISNN(18)
  14 C      REAL D(153)
  15 C      LOGICAL FLAG(18)
  16 C IN ABOVE, 18=N, 16=M, 9=LEV, 153=N(N-1)/2.
  17 C
  18 C
  19 C       OPEN(UNIT=21,STATUS='OLD',FILE='SPECTR.DAT')
  20 C
  21 C
  22 C      N = 18
  23 C      M = 16
  24 C      DO I=1,N
  25 C        READ(21,100)(DATA(I,J),J=1,M)
  26 C      ENDDO
  27 C 100  FORMAT(8F7.1)
  28 C
  29 C
  30 C      LEN = (N*(N-1))/2
  31 C      IOPT=1
  32 C      CALL HC(N,M,LEN,IOPT,DATA,IA,IB,CRIT,MEMBR,NN,DISNN,FLAG,D)
  33 C
  34 C
  35 C      LEV = 9
  36 C      CALL HCASS(N,IA,IB,CRIT,LEV,ICLASS,HVALS,IORDER,CRITVAL,HEIGHT)
  37 C
  38 C
  39 C      CALL HCDEN(LEV,IORDER,HEIGHT,CRITVAL)
  40 C
  41 C
  42 C      END
  43 C++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++C
  44 C                                                            C
  45 C  HIERARCHICAL CLUSTERING using (user-specified) criterion. C
  46 C                                                            C
  47 C  Parameters:                                               C
  48 C                                                            C
  49 Cremoved  DATA(N,M)         input data matrix,               C
  50 C  DISS(LEN)         dissimilarities in lower half diagonal  C
  51 C                    storage; LEN = N.N-1/2,                 C
  52 C  IOPT              clustering criterion to be used,        C
  53 C  IA, IB, CRIT      history of agglomerations; dimensions   C
  54 C                    N, first N-1 locations only used,       C
  55 C  MEMBR, NN, DISNN  vectors of length N, used to store      C
  56 C                    cluster cardinalities, current nearest  C
  57 C                    neighbour, and the dissimilarity assoc. C
  58 C                    with the latter.                        C
  59 C  FLAG              boolean indicator of agglomerable obj./ C
  60 C                    clusters.                               C
  61 C                                                            C
  62 C  F. Murtagh, ESA/ESO/STECF, Garching, February 1986.       C
  63 C                                                            C
  64 C------------------------------------------------------------C
  65       SUBROUTINE HC(N,M,LEN,IOPT,IA,IB,CRIT,MEMBR,NN,DISNN,
  66      X                FLAG,DISS)
  67       REAL MEMBR(N)
  68       REAL DISS(LEN)
  69       INTEGER IA(N),IB(N)
  70       REAL CRIT(N)
  71       DIMENSION NN(N),DISNN(N)
  72       LOGICAL FLAG(N)
  73       REAL INF
  74       DATA INF/1.E+20/
  75 C
  76 C  Initializations
  77 C
  78       DO I=1,N
  79          MEMBR(I)=1.
  80          FLAG(I)=.TRUE.
  81       ENDDO
  82       NCL=N
  83 C
  84 C  Construct dissimilarity matrix
  85 C
  86       DO I=1,N-1
  87          DO J=I+1,N
  88             IND=IOFFSET(N,I,J)
  89 cinput            DISS(IND)=0.
  90 cinput            DO K=1,M
  91 cinput               DISS(IND)=DISS(IND)+(DATA(I,K)-DATA(J,K))**2
  92 cinput            ENDDO
  93             IF (IOPT.EQ.1) DISS(IND)=DISS(IND)/2.
  94 C           (Above is done for the case of the min. var. method
  95 C            where merging criteria are defined in terms of variances
  96 C            rather than distances.)
  97           ENDDO
  98        ENDDO
  99 C
 100 C  Carry out an agglomeration - first create list of NNs
 101 C
 102       DO I=1,N-1
 103          DMIN=INF
 104          DO J=I+1,N
 105             IND=IOFFSET(N,I,J)
 106             IF (DISS(IND).GE.DMIN) GOTO 500
 107                DMIN=DISS(IND)
 108                JM=J
 109   500    CONTINUE
 110          ENDDO
 111          NN(I)=JM
 112          DISNN(I)=DMIN
 113       ENDDO
 114 C
 115   400 CONTINUE
 116 C     Next, determine least diss. using list of NNs
 117       DMIN=INF
 118       DO I=1,N-1
 119          IF (.NOT.FLAG(I)) GOTO 600
 120          IF (DISNN(I).GE.DMIN) GOTO 600
 121             DMIN=DISNN(I)
 122             IM=I
 123             JM=NN(I)
 124   600    CONTINUE
 125       ENDDO
 126       NCL=NCL-1
 127 C
 128 C  This allows an agglomeration to be carried out.
 129 C
 130       I2=MIN0(IM,JM)
 131       J2=MAX0(IM,JM)
 132       IA(N-NCL)=I2
 133       IB(N-NCL)=J2
 134       CRIT(N-NCL)=DMIN
 135 C
 136 C  Update dissimilarities from new cluster.
 137 C
 138       FLAG(J2)=.FALSE.
 139       DMIN=INF
 140       DO K=1,N
 141          IF (.NOT.FLAG(K)) GOTO 800
 142          IF (K.EQ.I2) GOTO 800
 143          X=MEMBR(I2)+MEMBR(J2)+MEMBR(K)
 144          IF (I2.LT.K) THEN
 145                            IND1=IOFFSET(N,I2,K)
 146                       ELSE
 147                            IND1=IOFFSET(N,K,I2)
 148          ENDIF
 149          IF (J2.LT.K) THEN
 150                            IND2=IOFFSET(N,J2,K)
 151                       ELSE
 152                            IND2=IOFFSET(N,K,J2)
 153          ENDIF
 154          IND3=IOFFSET(N,I2,J2)
 155          XX=DISS(IND3)
 156 C
 157 C  WARD'S MINIMUM VARIANCE METHOD - IOPT=1.
 158 C
 159          IF (IOPT.EQ.1) THEN
 160             DISS(IND1)=(MEMBR(I2)+MEMBR(K))*DISS(IND1)+
 161      X                 (MEMBR(J2)+MEMBR(K))*DISS(IND2)-
 162      X                 MEMBR(K)*XX
 163             DISS(IND1)=DISS(IND1)/X
 164          ENDIF
 165 C
 166 C  SINGLE LINK METHOD - IOPT=2.
 167 C
 168          IF (IOPT.EQ.2) THEN
 169             DISS(IND1)=MIN(DISS(IND1),DISS(IND2))
 170          ENDIF
 171 C
 172 C  COMPLETE LINK METHOD - IOPT=3.
 173 C
 174          IF (IOPT.EQ.3) THEN
 175             DISS(IND1)=MAX(DISS(IND1),DISS(IND2))
 176          ENDIF
 177 C
 178 C  AVERAGE LINK (OR GROUP AVERAGE) METHOD - IOPT=4.
 179 C
 180          IF (IOPT.EQ.4) THEN
 181             DISS(IND1)=(MEMBR(I2)*DISS(IND1)+MEMBR(J2)*DISS(IND2))/
 182      X                 (MEMBR(I2)+MEMBR(J2))
 183          ENDIF
 184 C
 185 C  MCQUITTY'S METHOD - IOPT=5.
 186 C
 187          IF (IOPT.EQ.5) THEN
 188             DISS(IND1)=0.5*DISS(IND1)+0.5*DISS(IND2)
 189          ENDIF
 190 C
 191 C  MEDIAN (GOWER'S) METHOD - IOPT=6.
 192 C
 193          IF (IOPT.EQ.6) THEN
 194             DISS(IND1)=0.5*DISS(IND1)+0.5*DISS(IND2)-0.25*XX
 195          ENDIF
 196 C
 197 C  CENTROID METHOD - IOPT=7.
 198 C
 199          IF (IOPT.EQ.7) THEN
 200             DISS(IND1)=(MEMBR(I2)*DISS(IND1)+MEMBR(J2)*DISS(IND2)-
 201      X          MEMBR(I2)*MEMBR(J2)*XX/(MEMBR(I2)+MEMBR(J2)))/
 202      X          (MEMBR(I2)+MEMBR(J2))
 203             ENDIF
 204 C
 205          IF (I2.GT.K) GOTO 800
 206          IF (DISS(IND1).GE.DMIN) GOTO 800
 207             DMIN=DISS(IND1)
 208             JJ=K
 209   800    CONTINUE
 210       ENDDO
 211       MEMBR(I2)=MEMBR(I2)+MEMBR(J2)
 212       DISNN(I2)=DMIN
 213       NN(I2)=JJ
 214 C
 215 C  Update list of NNs insofar as this is required.
 216 C
 217       DO I=1,N-1
 218          IF (.NOT.FLAG(I)) GOTO 900
 219          IF (NN(I).EQ.I2) GOTO 850
 220          IF (NN(I).EQ.J2) GOTO 850
 221          GOTO 900
 222   850    CONTINUE
 223 C        (Redetermine NN of I:)
 224          DMIN=INF
 225          DO J=I+1,N
 226             IND=IOFFSET(N,I,J)
 227             IF (.NOT.FLAG(J)) GOTO 870
 228             IF (I.EQ.J) GOTO 870
 229             IF (DISS(IND).GE.DMIN) GOTO 870
 230                DMIN=DISS(IND)
 231                JJ=J
 232   870       CONTINUE
 233          ENDDO
 234          NN(I)=JJ
 235          DISNN(I)=DMIN
 236   900    CONTINUE
 237       ENDDO
 238 C
 239 C  Repeat previous steps until N-1 agglomerations carried out.
 240 C
 241       IF (NCL.GT.1) GOTO 400
 242 C
 243 C
 244       RETURN
 245       END
 246 C
 247 C
 248       FUNCTION IOFFSET(N,I,J)
 249 C  Map row I and column J of upper half diagonal symmetric matrix
 250 C  onto vector.
 251       IOFFSET=J+(I-1)*N-(I*(I+1))/2
 252       RETURN
 253       END
 254 C+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++C
 255 C                                                               C
 256 C  Given a HIERARCHIC CLUSTERING, described as a sequence of    C
 257 C  agglomerations, derive the assignments into clusters for the C
 258 C  top LEV-1 levels of the hierarchy.                           C
 259 C  Prepare also the required data for representing the          C
 260 C  dendrogram of this top part of the hierarchy.                C
 261 C                                                               C
 262 C  Parameters:                                                  C
 263 C                                                               C
 264 C  IA, IB, CRIT: vectors of dimension N defining the agglomer-  C
 265 C                 ations.                                       C
 266 C  LEV:          number of clusters in largest partition.       C
 267 C  HVALS:        vector of dim. LEV, used internally only.      C
 268 C  ICLASS:       array of cluster assignments; dim. N by LEV.   C
 269 C  IORDER, CRITVAL, HEIGHT: vectors describing the dendrogram,  C
 270 C                all of dim. LEV.                               C
 271 C                                                               C
 272 C  F. Murtagh, ESA/ESO/STECF, Garching, February 1986.          C
 273 C                                                               C
 274 C HISTORY                                                       C
 275 C                                                               C
 276 C Bounds bug fix, Oct. 1990, F. Murtagh.                        C
 277 C Inserted line "IF (LOC.GT.LEV) GOTO 58" on line 48.  This was C
 278 C occassioned by incorrect termination of this loop when I      C
 279 C reached its (lower) extremity, i.e. N-LEV.  Without the       C
 280 C /CHECK=(BOUNDS) option on VAX/VMS compilation, this inserted  C
 281 C statement was not necessary.                                  C
 282 C---------------------------------------------------------------C
 283       SUBROUTINE HCASS(N,IA,IB,CRIT,LEV,ICLASS,HVALS,IORDER,
 284      X        CRITVAL,HEIGHT)
 285       include 'sizesclu.dat'
 286       include 'COMMON.IOUNITS'
 287       integer ICLASS(maxconf,maxconf-1)
 288       INTEGER IA(N),IB(N),HVALS(LEV),IORDER(LEV),
 289      X        HEIGHT(LEV)
 290       REAL CRIT(N),CRITVAL(LEV)
 291 C
 292 C  Pick out the clusters which the N objects belong to,
 293 C  at levels N-2, N-3, ... N-LEV+1 of the hierarchy.
 294 C  The clusters are identified by the lowest seq. no. of
 295 C  their members.
 296 C  There are 2, 3, ... LEV clusters, respectively, for the
 297 C  above levels of the hierarchy.
 298 C
 299       HVALS(1)=1
 300       HVALS(2)=IB(N-1)
 301       LOC=3
 302       DO 59 I=N-2,N-LEV,-1
 303          DO 52 J=1,LOC-1
 304             IF (IA(I).EQ.HVALS(J)) GOTO 54
 305   52     CONTINUE
 306          HVALS(LOC)=IA(I)
 307          LOC=LOC+1
 308   54     CONTINUE
 309          DO 56 J=1,LOC-1
 310             IF (IB(I).EQ.HVALS(J)) GOTO 58
 311   56     CONTINUE
 312          IF (LOC.GT.LEV) GOTO 58
 313          HVALS(LOC)=IB(I)
 314          LOC=LOC+1
 315   58     CONTINUE
 316   59  CONTINUE
 317 C
 318       DO 400 LEVEL=N-LEV,N-2
 319          DO 200 I=1,N
 320             ICL=I
 321             DO 100 ILEV=1,LEVEL
 322   100       IF (IB(ILEV).EQ.ICL) ICL=IA(ILEV)
 323             NCL=N-LEVEL
 324             ICLASS(I,NCL-1)=ICL
 325   200    CONTINUE
 326   400  CONTINUE
 327 C
 328       DO 120 I=1,N
 329       DO 120 J=1,LEV-1
 330       DO 110 K=2,LEV
 331       IF (ICLASS(I,J).NE.HVALS(K)) GOTO 110
 332          ICLASS(I,J)=K
 333          GOTO 120
 334   110 CONTINUE
 335   120 CONTINUE
 336 C
 337       WRITE (iout,450) (j,j=2,LEV)
 338   450 FORMAT(4X,' SEQ NOS',8(i2,'CL'),10000(i3,'CL'))
 339       WRITE (iout,470) (' ---',j=2,LEV)
 340   470 FORMAT(4X,' -------',10000a4)
 341       DO 500 I=1,N
 342       WRITE (iout,600) I,(ICLASS(I,J),J=1,LEV-1)
 343   600 FORMAT(I11,8I4,10000i5)
 344   500 CONTINUE
 345 C
 346 C  Determine an ordering of the LEV clusters (at level LEV-1)
 347 C  for later representation of the dendrogram.
 348 C  These are stored in IORDER.
 349 C  Determine the associated ordering of the criterion values
 350 C  for the vertical lines in the dendrogram.
 351 C  The ordinal values of these criterion values may be used in
 352 C  preference, and these are stored in HEIGHT.
 353 C  Finally, note that the LEV clusters are renamed so that they
 354 C  have seq. nos. 1 to LEV.
 355 C
 356       IORDER(1)=IA(N-1)
 357       IORDER(2)=IB(N-1)
 358       CRITVAL(1)=0.0
 359       CRITVAL(2)=CRIT(N-1)
 360       HEIGHT(1)=LEV
 361       HEIGHT(2)=LEV-1
 362       LOC=2
 363       DO 700 I=N-2,N-LEV+1,-1
 364          DO 650 J=1,LOC
 365             IF (IA(I).EQ.IORDER(J)) THEN
 366 C              Shift rightwards and insert IB(I) beside IORDER(J):
 367                DO 630 K=LOC+1,J+1,-1
 368                   IORDER(K)=IORDER(K-1)
 369                   CRITVAL(K)=CRITVAL(K-1)
 370                   HEIGHT(K)=HEIGHT(K-1)
 371   630          CONTINUE
 372                IORDER(J+1)=IB(I)
 373                 CRITVAL(J+1)=CRIT(I)
 374                 HEIGHT(J+1)=I-(N-LEV)
 375                LOC=LOC+1
 376             ENDIF
 377   650   CONTINUE
 378   700 CONTINUE
 379       DO 705 I=1,LEV
 380          DO 703 J=1,LEV
 381             IF (HVALS(I).EQ.IORDER(J)) THEN
 382                IORDER(J)=I
 383                GOTO 705
 384             ENDIF
 385   703    CONTINUE
 386   705 CONTINUE
 387 C
 388       RETURN
 389       END
 390 C+++++++++++++++++++++++++++++++++++++++++++++++++C
 391 C                                                 C
 392 C  Construct a DENDROGRAM of the top 8 levels of  C
 393 C  a HIERARCHIC CLUSTERING.                       C
 394 C                                                 C
 395 C  Parameters:                                    C
 396 C                                                 C
 397 C  IORDER, HEIGHT, CRITVAL: vectors of length LEV C
 398 C          defining the dendrogram.               C
 399 C          These are: the ordering of objects     C
 400 C          along the bottom of the dendrogram     C
 401 C          (IORDER); the height of the vertical   C
 402 C          above each object, in ordinal values   C
 403 C          (HEIGHT); and in real values (CRITVAL).C
 404 C                                                 C
 405 C  NOTE: these vectors MUST have been set up with C
 406 C        LEV = 9 in the prior call to routine     C
 407 C        HCASS.
 408 C                                                 C
 409 C  F. Murtagh, ESA/ESO/STECF, Garching, Feb. 1986.C
 410 C                                                 C
 411 C-------------------------------------------------C
 412       SUBROUTINE HCDEN(LEV,IORDER,HEIGHT,CRITVAL)
 413       include 'COMMON.IOUNITS'
 414       CHARACTER*80 LINE
 415       INTEGER IORDER(LEV),HEIGHT(LEV)
 416       REAL CRITVAL(LEV)
 417       INTEGER OUT(3*LEV,3*LEV)
 418       INTEGER UP,ACROSS,BLANK
 419       DATA UP,ACROSS,BLANK/'|','-',' '/
 420 C
 421 C
 422       DO I=1,3*LEV
 423         DO J=1,3*LEV
 424           OUT(I,J)=BLANK
 425         ENDDO
 426       ENDDO
 427 C
 428 C
 429       DO I=3,3*LEV,3
 430          I2=I/3
 431 C
 432          J2=3*LEV+1-3*HEIGHT(I2)
 433          DO J=3*LEV,J2,-1
 434             OUT(J,I)=UP
 435          ENDDO
 436 C
 437          DO K=I,3,-1
 438             I3=INT((K+2)/3)
 439             IF ( (3*LEV+1-HEIGHT(I3)*3).LT.J2) GOTO 100
 440             OUT(J2,K)=ACROSS
 441          ENDDO
 442   100    CONTINUE
 443 C
 444       ENDDO
 445 C
 446 C
 447       IC=3
 448       DO I=1,3*LEV
 449       IF (I.EQ.IC+1) THEN
 450                    IDUM=IC/3
 451                    IDUM=LEV-IDUM
 452                    DO L=1,LEV
 453                       IF (HEIGHT(L).EQ.IDUM) GOTO 190
 454                    ENDDO
 455   190              IDUM=L
 456                    WRITE(iout,200) CRITVAL(IDUM),(OUT(I,J),J=1,3*LEV)
 457                    IC=IC+3
 458                    ELSE
 459                    LINE = ' '
 460                    WRITE(iout,210) (OUT(I,J),J=1,3*LEV)
 461       ENDIF
 462   200 FORMAT(1H ,8X,F12.2,4X,27000A1)
 463   210 FORMAT(1H ,24X,27000A1)
 464       ENDDO
 465       WRITE(iout,250)
 466       WRITE(iout,220)(IORDER(J),J=1,LEV)
 467       WRITE(iout,250)
 468   220 FORMAT(1H ,24X,9000I3)
 469       WRITE(iout,230) LEV
 470   230 FORMAT(1H ,13X,'CRITERION        CLUSTERS 1 TO ',i3)
 471       WRITE(iout,240) LEV-1
 472   240 FORMAT(1H ,13X,'VALUES.      (TOP ',i3,' LEVELS OF HIERARCHY).')
 473   250 FORMAT(/)
 474 C
 475 C
 476       RETURN
 477       END