C---+----1----+----2----+----3----+----4----+----5----+----6----+----7-C C======================================================================C C C C ********************************************* C C CAH : DISTANCES REELLES ( 1 ETAPE SEULEMENT ) C C ********************************************* C C C C C C ARGUMENTS D'ENTREE : C C ------------------ C C C C LINK : TYPE DE DISTANCE INTERGROUPE C C LINK = 1 : SINGLE LINKAGE C C LINK = 2 : COMPLETE LINKAGE ( DEFAUT ) C C LINK = 3 : AVERAGE LINKAGE : MOYENNE QUADRATIQUE C C C C K : NOMBRE DE GROUPES EN ENTREE C C IL Y A K-1 GROUPES EN SORTIE , MAIS K RESTE INCHANGE C C CAR C'EST UN INDICE DE BOUCLE DANS L'APPELANT C C C C N : NOMBRE D'INDIVIDUS C C C C C C ARGUMENTS D'ENTREE-SORTIE : C C ------------------------- C C C C DIS : MATRICE DES DISTANCES , DIMENSION (N,N) C C C C TRIANGULAIRE INFERIEURE : DISTANCES ENTRE INDIVIDUS C C ( TRIANGULAIRE INFERIEURE INCHANGEE ) C C C C TRIANGULAIRE SUPERIEURE : DISTANCES ENTRE GROUPES C C EN ENTREE : K LIGNES ET K COLONNES LUES C C EN SORTIE : K-1 LIGNES ET K-1 COLONNES ECRITES C C C C SD2G : SOMME DES CARRES DES DISTANCES DE CHAQUE INDIVIDU C C A L'ENSEMBLE DES INDIVIDUS DE SON GROUPE C C ( INITIALISE LORSQUE K = N ) C C C C EFF : EFFECTIFS DES GROUPES C C ( INITIALISE LORSQUE K = N ) C C C C NGI : NUMEROS DE GROUPE DES INDIVIDUS C C ( INITIALISE LORSQUE K = N ) C C C C IPM : INDICE DU POINT MOYEN DE CHAQUE GROUPE C C ( INITIALISE LORSQUE K = N ) C C C C IPM0 : INDICE DU POINT MOYEN DES N INDIVIDUS C C ( INITIALISE AUTOMATIQUEMENT LORSQUE K = N ) C C C C DELTA : CRITERE D'ARRET (CLUSTER GAIN) POUR CHAQUE VALEUR DE K C C ( INITIALISE A ZERO LORSQUE K = N ) C C C C C C ARGUMENTS DE SORTIE : C C ------------------- C C C C G1 : NUMERO DU GROUPE FUSIONNE AVEC G2 C C G2 : NUMERO DU GROUPE FUSIONNE AVEC G1 C C SMD : DISTANCE G1-G2 C C C C KOPT : NOMBRE DE CLASSES REALISANT LE MAXIMUM DE DELTA C C ( EN CAS D'EGALITES , ON GARDE LE PLUS PETIT ) C C C C======================================================================C C C APPEL DE LA ROUTINE : CALCUL DE KOPT , PUIS ARRET A K = KOPT C L'APPEL AVEC K=1 NE SERT QU'A INITIALISER TOUT LORSQUE N=1 C ------------------------------------------------------------ C C DO K = N , 1 , -1 C CALL RCAH1E ( LINK , K , N , DIS , SD2G , C , EFF , NGI , IPM , IPM0 , C , DELTA , G1 , G2 , SMD , KOPT ) C END DO C C DO K = N , KOPT+1 , -1 C CALL RCAH1E ( LINK , K , N , DIS , SD2G , C , EFF , NGI , IPM , IPM0 , C , DELTA , G1 , G2 , SMD , KOPT1 ) C END DO C C======================================================================C C SUBROUTINE RCAH1E ( LINK , K , N , DIS , SD2G , , EFF , NGI , IPM , IPM0 , , DELTA , G1 , G2 , SMD , KOPT ) C IMPLICIT INTEGER ( A - Z ) C INTEGER EFF (K) , NGI (N) , IPM (K) C DOUBLE PRECISION DFLOAT , DSQRT , , DIS (N,N) , SD2G (N) , DELTA (N) , SMD , , N1 , N2 , D2 , , ZERO , UN C DATA ZERO , UN / 0.D0 , 1.D0 / C C C C ... INITIALISATIONS C --------------- C IF ( K .GT. N .OR. K .LT. 1 ) RETURN C IF ( K .EQ. N ) THEN C C SEULE LA TRIANGULAIRE INFERIEURE EST EN ENTREE C DO I = 2 , N DO J = 1 , I-1 DIS (J,I) = DIS (I,J) END DO END DO C C POINT MOYEN GLOBAL : IPM0 C IPM0 = 1 DO I = 1 , N SD2G (I) = ZERO DO J = 1 , I-1 SD2G (I) = SD2G (I) + DIS (I,J) * DIS (I,J) END DO DO J = I+1 , N SD2G (I) = SD2G (I) + DIS (J,I) * DIS (J,I) END DO IF ( SD2G (I) .LT. SD2G (IPM0) ) IPM0 = I END DO C C N GROUPES AU 1-ER APPEL C DO I = 1 , N SD2G (I) = ZERO EFF (I) = 1 NGI (I) = I IPM (I) = I DELTA (I) = ZERO END DO C KOPT = N C ENDIF C IF ( K .EQ. 1 ) RETURN C C C ... RECHERCHE DES DEUX GROUPES LES PLUS PROCHES : G1 < G2 C ----------------------------------------------------- C G1 = 1 G2 = 2 SMD = DIS (G1,G2) C DO I2 = 2 , K DO I1 = 1 , I2-1 IF ( DIS (I1,I2) .LT. DIS (G1,G2) ) THEN G1 = I1 G2 = I2 SMD = DIS (G1,G2) ENDIF END DO END DO C C C ... FUSION DES GROUPES G1 ET G2 ( REMARQUE : G1 < G2 ) C G1 DEVIENT ( G1 U G2 ) ; K DEVIENT G2 ; G2 SUPPRIME C --------------------------------------------------- C N1 = DFLOAT (EFF(G1)) N2 = DFLOAT (EFF(G2)) C C C ... RECALCUL DE DELTA : RETRAIT DES CONTRIBUTIONS DE G1 ET G2 C DISTANCES ENTRE INDIVIDUS DANS LA TRIANGULAIRE INFERIEURE C --------------------------------------------------------- C D2 = ZERO IF ( IPM0 .GT. IPM (G1) ) D2 = DIS ( IPM0 , IPM (G1) ) IF ( IPM0 .LT. IPM (G1) ) D2 = DIS ( IPM (G1) , IPM0 ) C DELTA (K-1) = DELTA (K) - (N1-UN) * D2 * D2 C D2 = ZERO IF ( IPM0 .GT. IPM (G2) ) D2 = DIS ( IPM0 , IPM (G2) ) IF ( IPM0 .LT. IPM (G2) ) D2 = DIS ( IPM (G2) , IPM0 ) C DELTA (K-1) = DELTA (K-1) - (N2-UN) * D2 * D2 C C C ... MISE A JOUR DES DISTANCES C ------------------------- C c ... G1 DEVIENT : G1 U G2 : RECALCUL DES DISTANCES A G1 : DEBUT C GOTO ( 100 , 200 , 300 ) , LINK GOTO 200 C C C ... SINGLE LINKAGE C 100 DO I = 1 , G1-1 IF ( DIS (I,G1) .GT. DIS (I,G2) ) DIS (I,G1) = DIS (I,G2) END DO DO I = G1+1 , G2-1 IF ( DIS (G1,I) .GT. DIS (I,G2) ) DIS (G1,I) = DIS (I,G2) END DO DO I = G2+1 , K IF ( DIS (G1,I) .GT. DIS (G2,I) ) DIS (G1,I) = DIS (G2,I) END DO C GOTO 400 C C C ... COMPLETE LINKAGE C 200 DO I = 1 , G1-1 IF ( DIS (I,G1) .LT. DIS (I,G2) ) DIS (I,G1) = DIS (I,G2) END DO DO I = G1+1 , G2-1 IF ( DIS (G1,I) .LT. DIS (I,G2) ) DIS (G1,I) = DIS (I,G2) END DO DO I = G2+1 , K IF ( DIS (G1,I) .LT. DIS (G2,I) ) DIS (G1,I) = DIS (G2,I) END DO C GOTO 400 C C C ... AVERAGE LINKAGE C 300 DO I = 1 , G1-1 DIS (I,G1) = DSQRT ( ( N1*DIS(I,G1)*DIS(I,G1) + + N2*DIS(I,G2)*DIS(I,G2) ) / (N1+N2) ) END DO DO I = G1+1 , G2-1 DIS (G1,I) = DSQRT ( ( N1*DIS(G1,I)*DIS(G1,I) + + N2*DIS(I,G2)*DIS(I,G2) ) / (N1+N2) ) END DO DO I = G2+1 , K DIS (G1,I) = DSQRT ( ( N1*DIS(G1,I)*DIS(G1,I) + + N2*DIS(G2,I)*DIS(G2,I) ) / (N1+N2) ) END DO C GOTO 400 C C C ... G1 DEVIENT : G1 U G2 : RECALCUL DES DISTANCES A G1 : FIN C C C ... K DEVIENT G2 : FIN DE LA MISE A JOUR DES DISTANCES C 400 DO I = 1 , G2-1 DIS (I,G2) = DIS (I,K) END DO DO I = G2+1 , K-1 DIS (G2,I) = DIS (I,K) END DO C C C ... MISE A JOUR DES EFFECTIFS C ------------------------- C EFF (G1) = EFF (G2) + EFF (G1) EFF (G2) = EFF (K) EFF (K) = 0 C C C ... MISE A JOUR DES NUMEROS DE CLASSES DES INDIVIDUS C ------------------------------------------------ C DO I = 1 , N IF ( NGI (I) .EQ. G2 ) NGI (I) = G1 END DO C DO I = 1 , N IF ( NGI (I) .EQ. K ) NGI (I) = G2 END DO C C C ... RECALCUL DE SD2G POUR LES POINTS DE G1 = G1 U G2 C ------------------------------------------------ C DO I = 1 , N IF ( NGI (I) .EQ. G1 ) THEN SD2G (I) = ZERO DO J = 1 , I-1 IF ( NGI (J) .EQ. G1 ) THEN SD2G (I) = SD2G (I) + DIS (I,J) * DIS (I,J) ENDIF END DO DO J = I+1 , N IF ( NGI (J) .EQ. G1 ) THEN SD2G (I) = SD2G (I) + DIS (J,I) * DIS (J,I) ENDIF END DO ENDIF END DO C C C ... RECALCUL DU POINT MOYEN DE G1 = G1 U G2 C --------------------------------------- C IPM (G2) = IPM (K) IPM (K) = 0 C IPM (G1) = 0 DO I = 1 , N IF ( NGI (I) .EQ. G1 ) THEN IF ( IPM (G1) .EQ. 0 ) THEN IPM (G1) = I ELSE IF ( SD2G (I) .LT. SD2G (IPM (G1)) ) IPM (G1) = I ENDIF ENDIF END DO C C C ... RECALCUL DE DELTA : AJOUT DE LA CONTRIBUTION DE G1 = G1 U G2 C DISTANCES ENTRE INDIVIDUS DANS LA TRIANGULAIRE INFERIEURE C ------------------------------------------------------------ C D2 = ZERO IF ( IPM0 .GT. IPM (G1) ) D2 = DIS ( IPM0 , IPM (G1) ) IF ( IPM0 .LT. IPM (G1) ) D2 = DIS ( IPM (G1) , IPM0 ) C DELTA (K-1) = DELTA (K-1) + (N1+N2-UN) * D2 * D2 C C CALCUL EQUIVALENT MAIS PLUS LONG C CC DELTA (K-1) = ZERO CC DO I = 1 , K-1 CC D2 = ZERO CC IF ( IPM0 .GT. IPM (I) ) D2 = DIS ( IPM0 , IPM (I) ) CC IF ( IPM0 .LT. IPM (I) ) D2 = DIS ( IPM (I) , IPM0 ) CC DELTA (K-1) = DELTA (K-1) + DFLOAT (EFF(I)-1) * D2 * D2 CC END DO C C C ... DELTA MAXIMUM C ------------- C IF ( DELTA (K-1) .GE. DELTA (KOPT) ) KOPT = K-1 C C C ... K EST UN INDICE DE BOUCLE A L'APPEL : NE PAS L'ECRASER C ------------------------------------------------------ C CCC K = K -1 C RETURN C END