静岡理工科大学 菅沼ホーム 目次 索引

クラスター分析

    1. A. C++
    2. B. Java
    3. C. JavaScript
    4. D. PHP
    5. E. Ruby
    6. F. Python
    7. G. C#
    8. H. VB

  プログラムは,クラスター分析を行うためのものです.データの入力方法に関しては,プログラムの最後に提示してある入力例に対する説明を参考にして下さい.

  1. C++

    /****************************/
    /* クラスター分析           */
    /*      coded by Y.Suganuma */
    /****************************/
    #include <stdio.h>
    
    void cluster(int, int, int, int, double **, int *);
    double range(int, int, int, int, double **);
    double range_c(int, double, double, double, int, int, int);
    
    int main()
    {
    	double **x;
    	int i1, i2, k, k1, L, n, N, *g;
    	int method;
    					// 方法,グループ数,変数の数,及び,データの数
    	scanf("%d %d %d %d", &method, &L, &n, &N);
    
    	g = new int [N];
    	x = new double * [N];
    					// データ
    	for (i1 = 0; i1 < N; i1++) {
    		x[i1] = new double [n];
    		for (i2 = 0; i2 < n; i2++)
    			scanf("%lf", &x[i1][i2]);
    	}
    					// クラスター分析
    	cluster(method, L, N, n, x, g);
    					// 出力
    	k = 1;
    	while (k <= L) {
    		k1 = -1;
    		printf("グループ %d\n", k);
    		for (i1 = 0; i1 < N && k1 < 0; i1++) {
    			if (g[i1] >= 0)
    				k1 = g[i1];
    		}
    		for (i1 = 0; i1 < N; i1++) {
    			if (g[i1] == k1) {
    				printf("   %d", i1);
    				for (i2 = 0; i2 < n; i2++)
    					printf(" %f", x[i1][i2]);
    				printf("\n");
    				g[i1] = -1;
    			}
    		}
    		k++;
    	}
    
    	for (i1 = 0; i1 < N; i1++)
    		delete [] x[i1];
    	delete [] x;
    	delete [] g;
    
    	return 0;
    }
    
    /*********************************/
    /* クラスター分析                */
    /*      method : =1 : 最短距離法 */
    /*               =2 : 最長距離法 */
    /*               =3 : メジアン法 */
    /*               =4 : 重心法     */
    /*               =5 : 群平均法   */
    /*               =6 : ウォード法 */
    /*      L : グループの数         */
    /*      N : データの数           */
    /*      n : 変量の数             */
    /*      x : データ               */
    /*      g : 所属するグループ番号 */
    /*********************************/
    #include <math.h>
    
    void cluster(int method, int L, int N, int n, double **x, int *g)
    {
    	double **r, min;
    	int ci = 0, cj = 0, i1, i2, k, M = N, *n_g;
    					// 初期設定
    	k   = (method < 4) ? 0 : 1;
    	n_g = new int [N];
    	r   = new double * [N];
    	for (i1 = 0; i1 < N; i1++) {
    		g[i1]   = i1;
    		n_g[i1] = 1;
    		r[i1]   = new double [N];
    		for (i2 = i1+1; i2 < N; i2++)
    			r[i1][i2] = range(k, i1, i2, n, x);
    	}
    	for (i1 = 0; i1 < N; i1++) {
    		for (i2 = i1+1; i2 < N; i2++)
    			r[i2][i1] = r[i1][i2];
    	}
    					// 実行
    	while (M > L) {
    						// 最小距離のクラスターを探す
    		min = -1.0;
    		for (i1 = 0; i1 < N; i1++) {
    			if (g[i1] == i1) {
    				for (i2 = i1+1; i2 < N; i2++) {
    					if (g[i2] == i2) {
    						if (min < 0.0 || r[i1][i2] < min) {
    							min = r[i1][i2];
    							ci  = i1;
    							cj  = i2;
    						}
    					}
    				}
    			}
    		}
    						// クラスターを融合し,他のクラスターとの距離を計算
    		for (i1 = 0; i1 < N; i1++) {
    			if (g[i1] == i1) {
    				for (i2 = i1+1; i2 < N; i2++) {
    					if (g[i2] == i2) {
    						if (i1 != cj && i2 != cj) {
    							if (i1 == ci) {
    								r[i1][i2] = range_c(method, r[ci][i2], r[cj][i2], r[ci][cj],
                                                        n_g[ci], n_g[cj], n_g[i2]);
    								r[i2][i1] = r[i1][i2];
    							}
    							else if (i2 == ci) {
    								r[i1][i2] = range_c(method, r[i1][ci], r[i1][cj], r[ci][cj],
                                                        n_g[ci], n_g[cj], n_g[i2]);
    								r[i2][i1] = r[i1][i2];
    							}
    						}
    					}
    				}
    			}
    		}
    
    		n_g[ci] += n_g[cj];
    		for (i1 = 0; i1 < N; i1++) {
    			if (g[i1] == cj)
    				g[i1] = ci;
    		}
    
    		M--;
    	}
    					// 領域の開放
    	for (i1 = 0; i1 < N; i1++)
    		delete [] r[i1];
    	delete [] r;
    	delete [] n_g;
    }
    
    /*********************************************/
    /* 2つのデータ間の距離                      */
    /*      method : =0 : ユークリッド距離       */
    /*               =1 : ユークリッド距離の2乗 */
    /*      i,j : データ番号                     */
    /*      n : 変量の数                         */
    /*      x : データ                           */
    /*      return : 距離                        */
    /*********************************************/
    double range(int method, int i, int j, int n, double **x)
    {
    	double x1, r = 0.0;
    	int i2;
    
    	for (i2 = 0; i2 < n; i2++) {
    		x1  = x[i][i2] - x[j][i2];
    		r  += x1 * x1;
    	}
    	if (method == 0)
    		r = sqrt(r);
    
    	return r;
    }
    
    /***********************************************/
    /* 2つのクラスター間の距離                    */
    /*      method : =1 : 最短距離法               */
    /*               =2 : 最長距離法               */
    /*               =3 : メジアン法               */
    /*               =4 : 重心法                   */
    /*               =5 : 群平均法                 */
    /*               =6 : ウォード法               */
    /*      Dio : クラスターiとクラスターoとの距離 */
    /*      Djo : クラスターjとクラスターoとの距離 */
    /*      Dij : クラスターiとクラスターjとの距離 */
    /*      ni : クラスターiに含まれるデータ数     */
    /*      nj : クラスターjに含まれるデータ数     */
    /*      no : クラスターoに含まれるデータ数     */
    /*      x,y : データ                           */
    /*      return : 距離                          */
    /***********************************************/
    double range_c(int method, double Dio, double Djo, double Dij, int ni, int nj, int no)
    {
    	double r = 0.0;
    	int nk;
    
    	switch (method) {
    					// 最短距離法
    		case 1:
    			r = (Dio <= Djo) ? Dio : Djo;
    			break;
    					// 最長距離法
    		case 2:
    			r = (Dio >= Djo) ? Dio : Djo;
    			break;
    					// メジアン法
    		case 3:
    			r = 0.5 * Dio + 0.5 * Djo - 0.25 * Dij;
    			break;
    					// 重心法
    		case 4:
    			nk = ni + nj;
    			r  = ni * Dio / nk + nj * Djo / nk - (double)ni * nj * Dij / ((double)nk * nk);
    			break;
    					// 群平均法
    		case 5:
    			nk = ni + nj;
    			r  = ni * Dio / nk + nj * Djo / nk;
    			break;
    					// ウォード法
    		case 6:
    			nk = ni + nj;
    			r  = ((ni + no) * Dio + (nj + no) * Djo - no * Dij) / ((double)nk + no);
    			break;
    	}
    
    	return r;
    }
    
    /*
    ---------データ例(コメント部分を除いて下さい)---------
    1 3 2 100   // クラスター間距離を計算する方法(method),クラスタの数(L,クラスタの数がこの値になったら終了),変数の数(n),及び,データの数(N)
    66.813742 25.509139   // x, y
    50.813965 25.537399
    74.048072 39.627578
    14.792737 67.086620
    42.838304 11.391394
    32.301288 68.001189
    24.436877 42.170217
    60.451432 36.760112
    24.314984 30.052427
    55.573736 63.561140
    72.162565 19.845151
    43.217518 90.320780
    51.888313 53.074269
    28.150842 40.674284
    31.619668 57.984410
    64.360526 49.975656
    53.702823 79.538952
    45.052136 35.297650
    4.702717 49.420025
    92.649989 5.431771
    65.403044 56.028507
    48.797150 30.888271
    40.806244 14.484027
    84.355436 53.896156
    50.133508 76.624964
    49.405414 78.403179
    76.824779 41.008448
    63.246400 40.075843
    78.538747 62.910356
    64.396460 56.299403
    77.152853 44.325319
    80.592411 36.177862
    48.763290 43.966714
    58.789819 90.533976
    13.684999 67.266671
    75.163001 81.909246
    46.451671 56.376068
    65.105023 34.563928
    45.815747 20.164535
    33.227702 44.477025
    41.061314 -54.334662
    40.021202 -65.490282
    22.829721 -56.861792
    43.917033 -43.558827
    40.723550 -43.188580
    53.309317 -69.996428
    31.463381 -31.506555
    24.313168 -52.662580
    17.433859 -57.468181
    32.457761 -93.127719
    9.183688 -31.686863
    10.186332 -44.173216
    27.925638 -62.236940
    9.356182 -42.291381
    23.036540 -27.153692
    -16.261328 -35.185462
    29.557288 -31.933335
    36.519228 -59.269642
    25.692837 -57.033021
    22.797337 -52.169044
    15.312205 -70.370841
    22.086548 -25.219727
    50.448475 -34.825824
    30.814475 -40.968689
    28.798789 -65.737936
    59.822791 -25.673863
    16.224354 -48.408079
    6.867234 -61.804123
    44.250439 -50.598095
    54.117605 -20.539278
    -43.244836 -3.374350
    -19.122981 -9.026765
    -4.632598 27.480272
    26.647517 24.535738
    19.527239 1.573533
    -29.982384 26.884977
    -11.856633 -24.568687
    -9.244616 -3.343794
    -15.656771 32.298241
    -22.152364 24.203428
    -34.526986 -27.862305
    -60.500060 -18.400603
    -6.902336 21.631805
    -46.863390 -27.364383
    -36.999128 4.181449
    -24.599285 -17.177658
    -24.814923 9.906257
    -7.845930 9.388576
    -36.128527 5.644606
    -31.522759 11.282073
    -12.500001 24.953627
    -21.330455 -0.830663
    -21.270652 -1.890803
    -23.750951 5.435622
    -25.563039 22.105947
    -16.047432 -5.815069
    -34.280972 30.657254
    -36.264330 -8.759981
    -12.109507 -15.804752
    -33.227330 -5.857611
    */
    			

  2. Java

      アプレット版では,任意のデータに対して画面上で実行することができます.
    /****************************/
    /* クラスター分析           */
    /*      coded by Y.Suganuma */
    /****************************/
    import java.io.*;
    import java.util.StringTokenizer;
    
    public class Test {
    	public static void main(String args[]) throws IOException
    	{
    		double x[][];
    		int i1, i2, k, k1, L, n, N, g[];
    		int method;
    		StringTokenizer str;
    		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    					// 方法,グループ数,変数の数,及び,データの数
    		str = new StringTokenizer(in.readLine(), " ");
    		method = Integer.parseInt(str.nextToken());
    		L = Integer.parseInt(str.nextToken());
    		n = Integer.parseInt(str.nextToken());
    		N = Integer.parseInt(str.nextToken());
    
    		g = new int [N];
    		x = new double [N][n];
    					// データ
    		for (i1 = 0; i1 < N; i1++) {
    			str = new StringTokenizer(in.readLine(), " ");
    			for (i2 = 0; i2 < n; i2++)
    				x[i1][i2] = Double.parseDouble(str.nextToken());
    		}
    					// クラスター分析
    		cluster(method, L, N, n, x, g);
    					// 出力
    		k = 1;
    		while (k <= L) {
    			k1 = -1;
    			System.out.println("グループ " + k);
    			for (i1 = 0; i1 < N && k1 < 0; i1++) {
    				if (g[i1] >= 0)
    					k1 = g[i1];
    			}
    			for (i1 = 0; i1 < N; i1++) {
    				if (g[i1] == k1) {
    					System.out.print("   " + i1);
    					for (i2 = 0; i2 < n; i2++)
    						System.out.print(" " + x[i1][i2]);
    					System.out.println();
    					g[i1] = -1;
    				}
    			}
    			k++;
    		}
    	}
    
    	/*********************************/
    	/* クラスター分析                */
    	/*      method : =1 : 最短距離法 */
    	/*               =2 : 最長距離法 */
    	/*               =3 : メジアン法 */
    	/*               =4 : 重心法     */
    	/*               =5 : 群平均法   */
    	/*               =6 : ウォード法 */
    	/*      L : グループの数         */
    	/*      N : データの数           */
    	/*      n : 変量の数             */
    	/*      x : データ               */
    	/*      g : 所属するグループ番号 */
    	/*********************************/
    	static void cluster(int method, int L, int N, int n, double x[][], int g[])
    	{
    		double r[][], min;
    		int ci = 0, cj = 0, i1, i2, k, M = N, n_g[];
    					// 初期設定
    		k   = (method < 4) ? 0 : 1;
    		n_g = new int [N];
    		r   = new double [N][N];
    		for (i1 = 0; i1 < N; i1++) {
    			g[i1]   = i1;
    			n_g[i1] = 1;
    			for (i2 = i1+1; i2 < N; i2++)
    				r[i1][i2] = range(k, i1, i2, n, x);
    		}
    		for (i1 = 0; i1 < N; i1++) {
    			for (i2 = i1+1; i2 < N; i2++)
    				r[i2][i1] = r[i1][i2];
    		}
    					// 実行
    		while (M > L) {
    						// 最小距離のクラスターを探す
    			min = -1.0;
    			for (i1 = 0; i1 < N; i1++) {
    				if (g[i1] == i1) {
    					for (i2 = i1+1; i2 < N; i2++) {
    						if (g[i2] == i2) {
    							if (min < 0.0 || r[i1][i2] < min) {
    								min = r[i1][i2];
    								ci  = i1;
    								cj  = i2;
    							}
    						}
    					}
    				}
    			}
    						// クラスターを融合し,他のクラスターとの距離を計算
    			for (i1 = 0; i1 < N; i1++) {
    				if (g[i1] == i1) {
    					for (i2 = i1+1; i2 < N; i2++) {
    						if (g[i2] == i2) {
    							if (i1 != cj && i2 != cj) {
    								if (i1 == ci) {
    									r[i1][i2] = range_c(method, r[ci][i2], r[cj][i2],
                                                            r[ci][cj], n_g[ci], n_g[cj], n_g[i2]);
    									r[i2][i1] = r[i1][i2];
    								}
    								else if (i2 == ci) {
    									r[i1][i2] = range_c(method, r[i1][ci], r[i1][cj],
                                                            r[ci][cj], n_g[ci], n_g[cj], n_g[i2]);
    									r[i2][i1] = r[i1][i2];
    								}
    							}
    						}
    					}
    				}
    			}
    
    			n_g[ci] += n_g[cj];
    			for (i1 = 0; i1 < N; i1++) {
    				if (g[i1] == cj)
    					g[i1] = ci;
    			}
    
    			M--;
    		}
    	}
    
    	/*********************************************/
    	/* 2つのデータ間の距離                      */
    	/*      method : =0 : ユークリッド距離       */
    	/*               =1 : ユークリッド距離の2乗 */
    	/*      i,j : データ番号                     */
    	/*      n : 変量の数                         */
    	/*      x : データ                           */
    	/*      return : 距離                        */
    	/*********************************************/
    	static double range(int method, int i, int j, int n, double x[][])
    	{
    		double x1, r = 0.0;
    		int i2;
    
    		for (i2 = 0; i2 < n; i2++) {
    			x1  = x[i][i2] - x[j][i2];
    			r  += x1 * x1;
    		}
    		if (method == 0)
    			r = Math.sqrt(r);
    
    		return r;
    	}
    
    	/***********************************************/
    	/* 2つのクラスター間の距離                    */
    	/*      method : =1 : 最短距離法               */
    	/*               =2 : 最長距離法               */
    	/*               =3 : メジアン法               */
    	/*               =4 : 重心法                   */
    	/*               =5 : 群平均法                 */
    	/*               =6 : ウォード法               */
    	/*      Dio : クラスターiとクラスターoとの距離 */
    	/*      Djo : クラスターjとクラスターoとの距離 */
    	/*      Dij : クラスターiとクラスターjとの距離 */
    	/*      ni : クラスターiに含まれるデータ数     */
    	/*      nj : クラスターjに含まれるデータ数     */
    	/*      no : クラスターoに含まれるデータ数     */
    	/*      x,y : データ                           */
    	/*      return : 距離                          */
    	/***********************************************/
    	static double range_c(int method, double Dio, double Djo, double Dij, int ni, int nj, int no)
    	{
    		double r = 0.0;
    		int nk;
    
    		switch (method) {
    					// 最短距離法
    			case 1:
    				r = (Dio <= Djo) ? Dio : Djo;
    				break;
    					// 最長距離法
    			case 2:
    				r = (Dio >= Djo) ? Dio : Djo;
    				break;
    					// メジアン法
    			case 3:
    				r = 0.5 * Dio + 0.5 * Djo - 0.25 * Dij;
    				break;
    					// 重心法
    			case 4:
    				nk = ni + nj;
    				r  = ni * Dio / nk + nj * Djo / nk - (double)ni * nj * Dij / ((double)nk * nk);
    				break;
    					// 群平均法
    			case 5:
    				nk = ni + nj;
    				r  = ni * Dio / nk + nj * Djo / nk;
    				break;
    					// ウォード法
    			case 6:
    				nk = ni + nj;
    				r  = ((ni + no) * Dio + (nj + no) * Djo - no * Dij) / ((double)nk + no);
    				break;
    		}
    
    		return r;
    	}
    }
    
    /*
    ---------データ例(コメント部分を除いて下さい)---------
    1 3 2 100   // クラスター間距離を計算する方法(method),クラスタの数(L,クラスタの数がこの値になったら終了),変数の数(n),及び,データの数(N)
    66.813742 25.509139   // x, y
    50.813965 25.537399
    74.048072 39.627578
    14.792737 67.086620
    42.838304 11.391394
    32.301288 68.001189
    24.436877 42.170217
    60.451432 36.760112
    24.314984 30.052427
    55.573736 63.561140
    72.162565 19.845151
    43.217518 90.320780
    51.888313 53.074269
    28.150842 40.674284
    31.619668 57.984410
    64.360526 49.975656
    53.702823 79.538952
    45.052136 35.297650
    4.702717 49.420025
    92.649989 5.431771
    65.403044 56.028507
    48.797150 30.888271
    40.806244 14.484027
    84.355436 53.896156
    50.133508 76.624964
    49.405414 78.403179
    76.824779 41.008448
    63.246400 40.075843
    78.538747 62.910356
    64.396460 56.299403
    77.152853 44.325319
    80.592411 36.177862
    48.763290 43.966714
    58.789819 90.533976
    13.684999 67.266671
    75.163001 81.909246
    46.451671 56.376068
    65.105023 34.563928
    45.815747 20.164535
    33.227702 44.477025
    41.061314 -54.334662
    40.021202 -65.490282
    22.829721 -56.861792
    43.917033 -43.558827
    40.723550 -43.188580
    53.309317 -69.996428
    31.463381 -31.506555
    24.313168 -52.662580
    17.433859 -57.468181
    32.457761 -93.127719
    9.183688 -31.686863
    10.186332 -44.173216
    27.925638 -62.236940
    9.356182 -42.291381
    23.036540 -27.153692
    -16.261328 -35.185462
    29.557288 -31.933335
    36.519228 -59.269642
    25.692837 -57.033021
    22.797337 -52.169044
    15.312205 -70.370841
    22.086548 -25.219727
    50.448475 -34.825824
    30.814475 -40.968689
    28.798789 -65.737936
    59.822791 -25.673863
    16.224354 -48.408079
    6.867234 -61.804123
    44.250439 -50.598095
    54.117605 -20.539278
    -43.244836 -3.374350
    -19.122981 -9.026765
    -4.632598 27.480272
    26.647517 24.535738
    19.527239 1.573533
    -29.982384 26.884977
    -11.856633 -24.568687
    -9.244616 -3.343794
    -15.656771 32.298241
    -22.152364 24.203428
    -34.526986 -27.862305
    -60.500060 -18.400603
    -6.902336 21.631805
    -46.863390 -27.364383
    -36.999128 4.181449
    -24.599285 -17.177658
    -24.814923 9.906257
    -7.845930 9.388576
    -36.128527 5.644606
    -31.522759 11.282073
    -12.500001 24.953627
    -21.330455 -0.830663
    -21.270652 -1.890803
    -23.750951 5.435622
    -25.563039 22.105947
    -16.047432 -5.815069
    -34.280972 30.657254
    -36.264330 -8.759981
    -12.109507 -15.804752
    -33.227330 -5.857611
    */
    			
    アプレット版
    /****************************/
    /* クラスター分析           */
    /*      coded by Y.Suganuma */
    /****************************/
    import java.awt.*;
    import java.awt.event.*;
    import java.applet.*;
    import java.util.StringTokenizer;
    
    public class Cluster extends Applet implements ActionListener, ItemListener {
    	int meth = 1;
    	Choice ch;
    	TextField tx1, tx2, tx3;
    	TextArea ta1, ta2;
    	Button bt;
    	Font f = new Font("TimesRoman", Font.BOLD, 20);
    
    	/************/
    	/* 初期設定 */
    	/************/
    	public void init()
    	{
    					// レイアウト,背景色,フォント
    		setLayout(new BorderLayout(5, 5));
    		setBackground(new Color(225, 255, 225));
    		setFont(f);
    					// 上のパネル
    		Panel pn1 = new Panel();
    		add(pn1, BorderLayout.NORTH);
    
    		pn1.add(new Label("方法:"));
    		ch = new Choice ();
    		ch.addItem("最短距離法");
    		ch.addItem("最長距離法");
    		ch.addItem("メジアン法");
    		ch.addItem("重心法");
    		ch.addItem("群平均法");
    		ch.addItem("ウォード法");
    		pn1.add(ch);
    		ch.addItemListener(this);
    
    		pn1.add(new Label("グループ数:"));
    		tx1 = new TextField("3", 2);
    		pn1.add(tx1);
    
    		pn1.add(new Label("変数の数:"));
    		tx2 = new TextField("2", 2);
    		pn1.add(tx2);
    
    		pn1.add(new Label("データの数:"));
    		tx3 = new TextField("100", 3);
    		pn1.add(tx3);
    					// 中央のパネル(データ)
    		Panel pn2 = new Panel();
    		add(pn2, BorderLayout.CENTER);
    
    		pn2.add(new Label("データ:"));
    		ta1 = new TextArea("66.813742 25.509139\n50.813965 25.537399\n74.048072 39.627578\n14.792737 67.086620\n42.838304 11.391394\n32.301288 68.001189\n24.436877 42.170217\n60.451432 36.760112\n24.314984 30.052427\n55.573736 63.561140\n72.162565 19.845151\n43.217518 90.320780\n51.888313 53.074269\n28.150842 40.674284\n31.619668 57.984410\n64.360526 49.975656\n53.702823 79.538952\n45.052136 35.297650\n4.702717 49.420025\n92.649989 5.431771\n65.403044 56.028507\n48.797150 30.888271\n40.806244 14.484027\n84.355436 53.896156\n50.133508 76.624964\n49.405414 78.403179\n76.824779 41.008448\n63.246400 40.075843\n78.538747 62.910356\n64.396460 56.299403\n77.152853 44.325319\n80.592411 36.177862\n48.763290 43.966714\n58.789819 90.533976\n13.684999 67.266671\n75.163001 81.909246\n46.451671 56.376068\n65.105023 34.563928\n45.815747 20.164535\n33.227702 44.477025\n41.061314 -54.334662\n40.021202 -65.490282\n22.829721 -56.861792\n43.917033 -43.558827\n40.723550 -43.188580\n53.309317 -69.996428\n31.463381 -31.506555\n24.313168 -52.662580\n17.433859 -57.468181\n32.457761 -93.127719\n9.183688 -31.686863\n10.186332 -44.173216\n27.925638 -62.236940\n9.356182 -42.291381\n23.036540 -27.153692\n-16.261328 -35.185462\n29.557288 -31.933335\n36.519228 -59.269642\n25.692837 -57.033021\n22.797337 -52.169044\n15.312205 -70.370841\n22.086548 -25.219727\n50.448475 -34.825824\n30.814475 -40.968689\n28.798789 -65.737936\n59.822791 -25.673863\n16.224354 -48.408079\n6.867234 -61.804123\n44.250439 -50.598095\n54.117605 -20.539278\n-43.244836 -3.374350\n-19.122981 -9.026765\n-4.632598 27.480272\n26.647517 24.535738\n19.527239 1.573533\n-29.982384 26.884977\n-11.856633 -24.568687\n-9.244616 -3.343794\n-15.656771 32.298241\n-22.152364 24.203428\n-34.526986 -27.862305\n-60.500060 -18.400603\n-6.902336 21.631805\n-46.863390 -27.364383\n-36.999128 4.181449\n-24.599285 -17.177658\n-24.814923 9.906257\n-7.845930 9.388576\n-36.128527 5.644606\n-31.522759 11.282073\n-12.500001 24.953627\n-21.330455 -0.830663\n-21.270652 -1.890803\n-23.750951 5.435622\n-25.563039 22.105947\n-16.047432 -5.815069\n-34.280972 30.657254\n-36.264330 -8.759981\n-12.109507 -15.804752\n-33.227330 -5.857611\n", 15, 15);
    		pn2.add(ta1);
    
    		pn2.add(new Label(" "));
    		bt = new Button("OK");
    		bt.setBackground(Color.pink);
    		bt.addActionListener(this);
    		pn2.add(bt);
    					// 下のパネル(結果)
    		Panel pn3 = new Panel();
    		add(pn3, BorderLayout.SOUTH);
    
    		pn3.add(new Label("結果:"));
    		ta2 = new TextArea(7, 70);
    		pn3.add(ta2);
    	}
    
    	/************************/
    	/* 選択されたときの処理 */
    	/************************/
    	public void itemStateChanged(ItemEvent e)
    	{
    		if (e.getItemSelectable() == ch) {
    			meth = ch.getSelectedIndex() + 1;
    		}
    	}
    
    	/******************************/
    	/* ボタンが押されたときの処理 */
    	/******************************/
    	public void actionPerformed(ActionEvent e)
    	{
    		if (e.getSource() == bt) {
    					// データ
    			int L = Integer.parseInt(tx1.getText());
    			int n = Integer.parseInt(tx2.getText());
    			int N = Integer.parseInt(tx3.getText());
    
    			int g[] = new int [N];
    			double x[][] = new double [N][n];
    
    			String ss = ta1.getText();
    			StringTokenizer str = new StringTokenizer(ss, " \n");
    			for (int i1 = 0; str.hasMoreTokens() && i1 < N; i1++) {
    				for (int i2 = 0; i2 < n; i2++)
    					x[i1][i2] = Double.parseDouble(str.nextToken());
    			}
    					// 計算
    			cluster(meth, L, N, n, x, g);
    
    			int k = 1;
    			ta2.setText("");
    			while (k <= L) {
    				int k1 = -1;
    				ta2.append("グループ " + k + "\n");
    				for (int i1 = 0; i1 < N && k1 < 0; i1++) {
    					if (g[i1] >= 0)
    						k1 = g[i1];
    				}
    				for (int i1 = 0; i1 < N; i1++) {
    					if (g[i1] == k1) {
    						ta2.append("   " + i1);
    						for (int i2 = 0; i2 < n; i2++)
    							ta2.append(" " + String.format("%.5f",x[i1][i2]));
    						ta2.append("\n");
    						g[i1] = -1;
    					}
    				}
    				k++;
    			}
    		}
    	}
    
    	/*********************************/
    	/* クラスター分析                */
    	/*      method : =1 : 最短距離法 */
    	/*               =2 : 最長距離法 */
    	/*               =3 : メジアン法 */
    	/*               =4 : 重心法     */
    	/*               =5 : 群平均法   */
    	/*               =6 : ウォード法 */
    	/*      L : グループの数         */
    	/*      N : データの数           */
    	/*      n : 変量の数             */
    	/*      x : データ               */
    	/*      g : 所属するグループ番号 */
    	/*********************************/
    	void cluster(int method, int L, int N, int n, double x[][], int g[])
    	{
    		double r[][], min;
    		int ci = 0, cj = 0, i1, i2, k, M = N, n_g[];
    					// 初期設定
    		k   = (method < 4) ? 0 : 1;
    		n_g = new int [N];
    		r   = new double [N][N];
    		for (i1 = 0; i1 < N; i1++) {
    			g[i1]   = i1;
    			n_g[i1] = 1;
    			for (i2 = i1+1; i2 < N; i2++)
    				r[i1][i2] = range(k, i1, i2, n, x);
    		}
    		for (i1 = 0; i1 < N; i1++) {
    			for (i2 = i1+1; i2 < N; i2++)
    				r[i2][i1] = r[i1][i2];
    		}
    					// 実行
    		while (M > L) {
    						// 最小距離のクラスターを探す
    			min = -1.0;
    			for (i1 = 0; i1 < N; i1++) {
    				if (g[i1] == i1) {
    					for (i2 = i1+1; i2 < N; i2++) {
    						if (g[i2] == i2) {
    							if (min < 0.0 || r[i1][i2] < min) {
    								min = r[i1][i2];
    								ci  = i1;
    								cj  = i2;
    							}
    						}
    					}
    				}
    			}
    						// クラスターを融合し,他のクラスターとの距離を計算
    			for (i1 = 0; i1 < N; i1++) {
    				if (g[i1] == i1) {
    					for (i2 = i1+1; i2 < N; i2++) {
    						if (g[i2] == i2) {
    							if (i1 != cj && i2 != cj) {
    								if (i1 == ci) {
    									r[i1][i2] = range_c(method, r[ci][i2], r[cj][i2],
                                                                r[ci][cj], n_g[ci], n_g[cj], n_g[i2]);
    									r[i2][i1] = r[i1][i2];
    								}
    								else if (i2 == ci) {
    									r[i1][i2] = range_c(method, r[i1][ci], r[i1][cj],
                                                                r[ci][cj], n_g[ci], n_g[cj], n_g[i2]);
    									r[i2][i1] = r[i1][i2];
    								}
    							}
    						}
    					}
    				}
    			}
    
    			n_g[ci] += n_g[cj];
    			for (i1 = 0; i1 < N; i1++) {
    				if (g[i1] == cj)
    					g[i1] = ci;
    			}
    
    			M--;
    		}
    	}
    
    	/*********************************************/
    	/* 2つのデータ間の距離                      */
    	/*      method : =0 : ユークリッド距離       */
    	/*               =1 : ユークリッド距離の2乗 */
    	/*      i,j : データ番号                     */
    	/*      n : 変量の数                         */
    	/*      x : データ                           */
    	/*      return : 距離                        */
    	/*********************************************/
    	double range(int method, int i, int j, int n, double x[][])
    	{
    		double x1, r = 0.0;
    		int i2;
    
    		for (i2 = 0; i2 < n; i2++) {
    			x1  = x[i][i2] - x[j][i2];
    			r  += x1 * x1;
    		}
    		if (method == 0)
    			r = Math.sqrt(r);
    
    		return r;
    	}
    
    	/***********************************************/
    	/* 2つのクラスター間の距離                    */
    	/*      method : =1 : 最短距離法               */
    	/*               =2 : 最長距離法               */
    	/*               =3 : メジアン法               */
    	/*               =4 : 重心法                   */
    	/*               =5 : 群平均法                 */
    	/*               =6 : ウォード法               */
    	/*      Dio : クラスターiとクラスターoとの距離 */
    	/*      Djo : クラスターjとクラスターoとの距離 */
    	/*      Dij : クラスターiとクラスターjとの距離 */
    	/*      ni : クラスターiに含まれるデータ数     */
    	/*      nj : クラスターjに含まれるデータ数     */
    	/*      no : クラスターoに含まれるデータ数     */
    	/*      x,y : データ                           */
    	/*      return : 距離                          */
    	/***********************************************/
    	double range_c(int method, double Dio, double Djo, double Dij, int ni, int nj, int no)
    	{
    		double r = 0.0;
    		int nk;
    
    		switch (method) {
    					// 最短距離法
    			case 1:
    				r = (Dio <= Djo) ? Dio : Djo;
    				break;
    					// 最長距離法
    			case 2:
    				r = (Dio >= Djo) ? Dio : Djo;
    				break;
    					// メジアン法
    			case 3:
    				r = 0.5 * Dio + 0.5 * Djo - 0.25 * Dij;
    				break;
    					// 重心法
    			case 4:
    				nk = ni + nj;
    				r  = ni * Dio / nk + nj * Djo / nk - (double)ni * nj * Dij / ((double)nk * nk);
    				break;
    					// 群平均法
    			case 5:
    				nk = ni + nj;
    				r  = ni * Dio / nk + nj * Djo / nk;
    				break;
    					// ウォード法
    			case 6:
    				nk = ni + nj;
    				r  = ((ni + no) * Dio + (nj + no) * Djo - no * Dij) / ((double)nk + no);
    				break;
    		}
    
    		return r;
    	}
    }
    			

  3. JavaScript

      ここをクリックすると,任意のデータに対して画面上で実行することができます.
    <!DOCTYPE HTML>
    
    <HTML>
    
    <HEAD>
    
    	<TITLE>クラスター分析</TITLE>
    	<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8">
    	<SCRIPT TYPE="text/javascript">
    		meth = 1;
    		function main()
    		{
    					// データ
    			let L = parseInt(document.getElementById("L").value);
    			let n = parseInt(document.getElementById("n").value);
    			let N = parseInt(document.getElementById("n_data").value);
    			let g = new Array();
    			let x = new Array();
    			for (let i1 = 0; i1 < N; i1++)
    				x[i1] = new Array();
    			let ss = (document.getElementById("data").value).split(/ {1,}|\n{1,}/);
    			let k = 0;
    			for (let i1 = 0; i1 < N; i1++) {
    				for (let i2 = 0; i2 < n; i2++) {
    					x[i1][i2] = parseFloat(ss[k]);
    					k++;
    				}
    			}
    					// 計算
    			cluster(meth, L, N, n, x, g);
    
    			k = 1;
    			str = "";
    			while (k <= L) {
    				let k1 = -1;
    				str = str + "グループ " + k + "\n";
    				for (let i1 = 0; i1 < N && k1 < 0; i1++) {
    					if (g[i1] >= 0)
    						k1 = g[i1];
    				}
    				for (let i1 = 0; i1 < N; i1++) {
    					if (g[i1] == k1) {
    						str = str + "  " + (i1 + 1);
    						for (let i2 = 0; i2 < n; i2++)
    							str = str + " " + x[i1][i2];
    						str = str + "\n";
    						g[i1] = -1;
    					}
    				}
    				k++;
    			}
    			document.getElementById("ans").value = str;
    		}
    
    		/*********************************/
    		/* クラスター分析                */
    		/*      method : =1 : 最短距離法 */
    		/*               =2 : 最長距離法 */
    		/*               =3 : メジアン法 */
    		/*               =4 : 重心法     */
    		/*               =5 : 群平均法   */
    		/*               =6 : ウォード法 */
    		/*      L : グループの数         */
    		/*      N : データの数           */
    		/*      n : 変量の数             */
    		/*      x : データ               */
    		/*      g : 所属するグループ番号 */
    		/*********************************/
    		function cluster(method, L, N, n, x, g)
    		{
    			let min;
    			let ci = 0;
    			let cj = 0;
    			let i1;
    			let i2;
    			let k;
    			let M = N;
    			let n_g = new Array();
    			let r   = new Array();
    			for (i1 = 0; i1 < N; i1++)
    				r[i1] = new Array();
    						// 初期設定
    			k   = (method < 4) ? 0 : 1;
    			for (i1 = 0; i1 < N; i1++) {
    				g[i1]   = i1;
    				n_g[i1] = 1;
    				for (i2 = i1+1; i2 < N; i2++)
    					r[i1][i2] = range(k, i1, i2, n, x);
    			}
    			for (i1 = 0; i1 < N; i1++) {
    				for (i2 = i1+1; i2 < N; i2++)
    					r[i2][i1] = r[i1][i2];
    			}
    						// 実行
    			while (M > L) {
    							// 最小距離のクラスターを探す
    				min = -1.0;
    				for (i1 = 0; i1 < N; i1++) {
    					if (g[i1] == i1) {
    						for (i2 = i1+1; i2 < N; i2++) {
    							if (g[i2] == i2) {
    								if (min < 0.0 || r[i1][i2] < min) {
    									min = r[i1][i2];
    									ci  = i1;
    									cj  = i2;
    								}
    							}
    						}
    					}
    				}
    							// クラスターを融合し,他のクラスターとの距離を計算
    				for (i1 = 0; i1 < N; i1++) {
    					if (g[i1] == i1) {
    						for (i2 = i1+1; i2 < N; i2++) {
    							if (g[i2] == i2) {
    								if (i1 != cj && i2 != cj) {
    									if (i1 == ci) {
    										r[i1][i2] = range_c(method, r[ci][i2], r[cj][i2],
                                                        r[ci][cj], n_g[ci], n_g[cj], n_g[i2]);
    										r[i2][i1] = r[i1][i2];
    									}
    									else if (i2 == ci) {
    										r[i1][i2] = range_c(method, r[i1][ci], r[i1][cj],
                                                        r[ci][cj], n_g[ci], n_g[cj], n_g[i2]);
    										r[i2][i1] = r[i1][i2];
    									}
    								}
    							}
    						}
    					}
    				}
    
    				n_g[ci] += n_g[cj];
    				for (i1 = 0; i1 < N; i1++) {
    					if (g[i1] == cj)
    						g[i1] = ci;
    				}
    
    				M--;
    			}
    		}
    
    		/*********************************************/
    		/* 2つのデータ間の距離                      */
    		/*      method : =0 : ユークリッド距離       */
    		/*               =1 : ユークリッド距離の2乗 */
    		/*      i,j : データ番号                     */
    		/*      n : 変量の数                         */
    		/*      x : データ                           */
    		/*      return : 距離                        */
    		/*********************************************/
    		function range(method, i, j, n, x)
    		{
    			let x1;
    			let r = 0.0;
    			let i2;
    
    			for (i2 = 0; i2 < n; i2++) {
    				x1  = x[i][i2] - x[j][i2];
    				r  += x1 * x1;
    			}
    			if (method == 0)
    				r = Math.sqrt(r);
    
    			return r;
    		}
    
    		/***********************************************/
    		/* 2つのクラスター間の距離                    */
    		/*      method : =1 : 最短距離法               */
    		/*               =2 : 最長距離法               */
    		/*               =3 : メジアン法               */
    		/*               =4 : 重心法                   */
    		/*               =5 : 群平均法                 */
    		/*               =6 : ウォード法               */
    		/*      Dio : クラスターiとクラスターoとの距離 */
    		/*      Djo : クラスターjとクラスターoとの距離 */
    		/*      Dij : クラスターiとクラスターjとの距離 */
    		/*      ni : クラスターiに含まれるデータ数     */
    		/*      nj : クラスターjに含まれるデータ数     */
    		/*      no : クラスターoに含まれるデータ数     */
    		/*      x,y : データ                           */
    		/*      return : 距離                          */
    		/***********************************************/
    		function range_c(method, Dio, Djo, Dij, ni, nj, no)
    		{
    			let r = 0.0;
    			let nk;
    
    			switch (method) {
    						// 最短距離法
    				case 1:
    					r = (Dio <= Djo) ? Dio : Djo;
    					break;
    						// 最長距離法
    				case 2:
    					r = (Dio >= Djo) ? Dio : Djo;
    					break;
    						// メジアン法
    				case 3:
    					r = 0.5 * Dio + 0.5 * Djo - 0.25 * Dij;
    					break;
    						// 重心法
    				case 4:
    					nk = ni + nj;
    					r  = ni * Dio / nk + nj * Djo / nk - ni * nj * Dij / (nk * nk);
    					break;
    						// 群平均法
    				case 5:
    					nk = ni + nj;
    					r  = ni * Dio / nk + nj * Djo / nk;
    					break;
    						// ウォード法
    				case 6:
    					nk = ni + nj;
    					r  = ((ni + no) * Dio + (nj + no) * Djo - no * Dij) / (nk + no);
    					break;
    			}
    
    			return r;
    		}
    
    		/********/
    		/* 方法 */
    		/********/
    		function set_m()
    		{
    			let sel = document.getElementById("meth");
    			for (let i1 = 0; i1 < 6; i1++) {
    				if (sel.options[i1].selected) {
    					meth = i1 + 1;
    					break;
    				}
    			}
    		}
    	</SCRIPT>
    
    </HEAD>
    
    <BODY STYLE="font-size: 130%; background-color: #eeffee;">
    
    	<H2 STYLE="text-align:center"><B>クラスター分析</B></H2>
    
    	<DL>
    		<DT>  テキストフィールドおよびテキストエリアには,例として,テキストエリアに与えられた 100 個のデータに対してクラスター分析を行う場合に対する値が設定されています.他の問題を実行する場合は,それらを適切に修正してください.
    	</DL>
    
    	<DIV STYLE="text-align:center">
    		方法:<SELECT ID="meth" onChange="set_m()" STYLE="font-size:100%">
    			<OPTION SELECTED>最短距離法
    			<OPTION>最長距離法
    			<OPTION>メジアン法
    			<OPTION>重心法
    			<OPTION>群平均法
    			<OPTION>ウォード法
    		</SELECT> 
    		グループの数:<INPUT ID="L" STYLE="font-size: 100%" TYPE="text" SIZE="2" VALUE="3"> 
    		変数の数:<INPUT ID="n" STYLE="font-size: 100%" TYPE="text" SIZE="2" VALUE="2"> 
    		データの数:<INPUT ID="n_data" STYLE="font-size: 100%" TYPE="text" SIZE="3" VALUE="100"><BR><BR>
    		データ:<TEXTAREA ID="data" COLS="25" ROWS="15" STYLE="font-size: 100%">
    66.813742 25.509139
    50.813965 25.537399
    74.048072 39.627578
    14.792737 67.086620
    42.838304 11.391394
    32.301288 68.001189
    24.436877 42.170217
    60.451432 36.760112
    24.314984 30.052427
    55.573736 63.561140
    72.162565 19.845151
    43.217518 90.320780
    51.888313 53.074269
    28.150842 40.674284
    31.619668 57.984410
    64.360526 49.975656
    53.702823 79.538952
    45.052136 35.297650
    4.702717 49.420025
    92.649989 5.431771
    65.403044 56.028507
    48.797150 30.888271
    40.806244 14.484027
    84.355436 53.896156
    50.133508 76.624964
    49.405414 78.403179
    76.824779 41.008448
    63.246400 40.075843
    78.538747 62.910356
    64.396460 56.299403
    77.152853 44.325319
    80.592411 36.177862
    48.763290 43.966714
    58.789819 90.533976
    13.684999 67.266671
    75.163001 81.909246
    46.451671 56.376068
    65.105023 34.563928
    45.815747 20.164535
    33.227702 44.477025
    41.061314 -54.334662
    40.021202 -65.490282
    22.829721 -56.861792
    43.917033 -43.558827
    40.723550 -43.188580
    53.309317 -69.996428
    31.463381 -31.506555
    24.313168 -52.662580
    17.433859 -57.468181
    32.457761 -93.127719
    9.183688 -31.686863
    10.186332 -44.173216
    27.925638 -62.236940
    9.356182 -42.291381
    23.036540 -27.153692
    -16.261328 -35.185462
    29.557288 -31.933335
    36.519228 -59.269642
    25.692837 -57.033021
    22.797337 -52.169044
    15.312205 -70.370841
    22.086548 -25.219727
    50.448475 -34.825824
    30.814475 -40.968689
    28.798789 -65.737936
    59.822791 -25.673863
    16.224354 -48.408079
    6.867234 -61.804123
    44.250439 -50.598095
    54.117605 -20.539278
    -43.244836 -3.374350
    -19.122981 -9.026765
    -4.632598 27.480272
    26.647517 24.535738
    19.527239 1.573533
    -29.982384 26.884977
    -11.856633 -24.568687
    -9.244616 -3.343794
    -15.656771 32.298241
    -22.152364 24.203428
    -34.526986 -27.862305
    -60.500060 -18.400603
    -6.902336 21.631805
    -46.863390 -27.364383
    -36.999128 4.181449
    -24.599285 -17.177658
    -24.814923 9.906257
    -7.845930 9.388576
    -36.128527 5.644606
    -31.522759 11.282073
    -12.500001 24.953627
    -21.330455 -0.830663
    -21.270652 -1.890803
    -23.750951 5.435622
    -25.563039 22.105947
    -16.047432 -5.815069
    -34.280972 30.657254
    -36.264330 -8.759981
    -12.109507 -15.804752
    -33.227330 -5.857611
    		</TEXTAREA> 
    		<BUTTON STYLE="font-size: 100%; background-color: pink" onClick="main()">OK</BUTTON><BR><BR>
    		<TEXTAREA ID="ans" COLS="50" ROWS="10" STYLE="font-size: 100%;"></TEXTAREA>
    	</DIV>
    
    </BODY>
    
    </HTML>
    			

  4. PHP

    <?php
    /****************************/
    /* クラスター分析           */
    /*      coded by Y.Suganuma */
    /****************************/
    
    					// 方法,グループ数,変数の数,及び,データの数
    	fscanf(STDIN, "%d %d %d %d", $method, $L, $n, $N);
    
    	$g = array($N);
    	$x = array($N);
    					// データ
    	for ($i1 = 0; $i1 < $N; $i1++) {
    		$x[$i1]      = array($n);
    		$str         = trim(fgets(STDIN));
    		$x[$i1][0]   = floatval(strtok($str, " "));
    		for ($i2 = 1; $i2 < $n; $i2++)
    			$x[$i1][$i2] = floatval(strtok(" "));
    	}
    					// クラスター分析
    	cluster($method, $L, $N, $n, $x, $g);
    					// 出力
    	$k = 1;
    	while ($k <= $L) {
    		$k1 = -1;
    		printf("グループ %d\n", $k);
    		for ($i1 = 0; $i1 < $N && $k1 < 0; $i1++) {
    			if ($g[$i1] >= 0)
    				$k1 = $g[$i1];
    		}
    		for ($i1 = 0; $i1 < $N; $i1++) {
    			if ($g[$i1] == $k1) {
    				printf("   %d", $i1);
    				for ($i2 = 0; $i2 < $n; $i2++)
    					printf(" %f", $x[$i1][$i2]);
    				printf("\n");
    				$g[$i1] = -1;
    			}
    		}
    		$k++;
    	}
    
    /*********************************/
    /* クラスター分析                */
    /*      method : =1 : 最短距離法 */
    /*               =2 : 最長距離法 */
    /*               =3 : メジアン法 */
    /*               =4 : 重心法     */
    /*               =5 : 群平均法   */
    /*               =6 : ウォード法 */
    /*      L : グループの数         */
    /*      N : データの数           */
    /*      n : 変量の数             */
    /*      x : データ               */
    /*      g : 所属するグループ番号 */
    /*********************************/
    function cluster($method, $L, $N, $n, $x, &$g)
    {
    	$ci = 0;
    	$cj = 0;
    	$M  = $N;
    					// 初期設定
    	$k   = ($method < 4) ? 0 : 1;
    	$n_g = array($N);
    	$r   = array($N);
    	for ($i1 = 0; $i1 < $N; $i1++) {
    		$g[$i1]   = $i1;
    		$n_g[$i1] = 1;
    		$r[$i1]   = array($N);
    		for ($i2 = $i1+1; $i2 < $N; $i2++)
    			$r[$i1][$i2] = range_d($k, $i1, $i2, $n, $x);
    	}
    	for ($i1 = 0; $i1 < $N; $i1++) {
    		for ($i2 = $i1+1; $i2 < $N; $i2++)
    			$r[$i2][$i1] = $r[$i1][$i2];
    	}
    					// 実行
    	while ($M > $L) {
    						// 最小距離のクラスターを探す
    		$min = -1.0;
    		for ($i1 = 0; $i1 < $N; $i1++) {
    			if ($g[$i1] == $i1) {
    				for ($i2 = $i1+1; $i2 < $N; $i2++) {
    					if ($g[$i2] == $i2) {
    						if ($min < 0.0 || $r[$i1][$i2] < $min) {
    							$min = $r[$i1][$i2];
    							$ci  = $i1;
    							$cj  = $i2;
    						}
    					}
    				}
    			}
    		}
    						// クラスターを融合し,他のクラスターとの距離を計算
    		for ($i1 = 0; $i1 < $N; $i1++) {
    			if ($g[$i1] == $i1) {
    				for ($i2 = $i1+1; $i2 < $N; $i2++) {
    					if ($g[$i2] == $i2) {
    						if ($i1 != $cj && $i2 != $cj) {
    							if ($i1 == $ci) {
    								$r[$i1][$i2] = range_c($method, $r[$ci][$i2], $r[$cj][$i2], $r[$ci][$cj],
                                                        $n_g[$ci], $n_g[$cj], $n_g[$i2]);
    								$r[$i2][$i1] = $r[$i1][$i2];
    							}
    							else if ($i2 == $ci) {
    								$r[$i1][$i2] = range_c($method, $r[$i1][$ci], $r[$i1][$cj], $r[$ci][$cj],
                                                        $n_g[$ci], $n_g[$cj], $n_g[$i2]);
    								$r[$i2][$i1] = $r[$i1][$i2];
    							}
    						}
    					}
    				}
    			}
    		}
    
    		$n_g[$ci] += $n_g[$cj];
    		for ($i1 = 0; $i1 < $N; $i1++) {
    			if ($g[$i1] == $cj)
    				$g[$i1] = $ci;
    		}
    
    		$M--;
    	}
    }
    
    /*********************************************/
    /* 2つのデータ間の距離                      */
    /*      method : =0 : ユークリッド距離       */
    /*               =1 : ユークリッド距離の2乗 */
    /*      i,j : データ番号                     */
    /*      n : 変量の数                         */
    /*      x : データ                           */
    /*      return : 距離                        */
    /*********************************************/
    function range_d($method, $i, $j, $n, $x)
    {
    	$r = 0.0;
    
    	for ($i2 = 0; $i2 < $n; $i2++) {
    		$x1  = $x[$i][$i2] - $x[$j][$i2];
    		$r  += $x1 * $x1;
    	}
    	if ($method == 0)
    		$r = sqrt($r);
    
    	return $r;
    }
    
    /***********************************************/
    /* 2つのクラスター間の距離                    */
    /*      method : =1 : 最短距離法               */
    /*               =2 : 最長距離法               */
    /*               =3 : メジアン法               */
    /*               =4 : 重心法                   */
    /*               =5 : 群平均法                 */
    /*               =6 : ウォード法               */
    /*      Dio : クラスターiとクラスターoとの距離 */
    /*      Djo : クラスターjとクラスターoとの距離 */
    /*      Dij : クラスターiとクラスターjとの距離 */
    /*      ni : クラスターiに含まれるデータ数     */
    /*      nj : クラスターjに含まれるデータ数     */
    /*      no : クラスターoに含まれるデータ数     */
    /*      x,y : データ                           */
    /*      return : 距離                          */
    /***********************************************/
    function range_c($method, $Dio, $Djo, $Dij, $ni, $nj, $no)
    {
    	$r = 0.0;
    
    	switch ($method) {
    					// 最短距離法
    		case 1:
    			$r = ($Dio <= $Djo) ? $Dio : $Djo;
    			break;
    					// 最長距離法
    		case 2:
    			$r = ($Dio >= $Djo) ? $Dio : $Djo;
    			break;
    					// メジアン法
    		case 3:
    			$r = 0.5 * $Dio + 0.5 * $Djo - 0.25 * $Dij;
    			break;
    					// 重心法
    		case 4:
    			$nk = $ni + $nj;
    			$r  = $ni * $Dio / $nk + $nj * $Djo / $nk - $ni * $nj * $Dij / ($nk * $nk);
    			break;
    					// 群平均法
    		case 5:
    			$nk = $ni + $nj;
    			$r  = $ni * $Dio / $nk + $nj * $Djo / $nk;
    			break;
    					// ウォード法
    		case 6:
    			$nk = $ni + $nj;
    			$r  = (($ni + $no) * $Dio + ($nj + $no) * $Djo - $no * $Dij) / ($nk + $no);
    			break;
    	}
    
    	return $r;
    }
    
    /*
    ---------データ例(コメント部分を除いて下さい)---------
    1 3 2 100   // クラスター間距離を計算する方法(method),クラスタの数(L,クラスタの数がこの値になったら終了),変数の数(n),及び,データの数(N)
    66.813742 25.509139   // x, y
    50.813965 25.537399
    74.048072 39.627578
    14.792737 67.086620
    42.838304 11.391394
    32.301288 68.001189
    24.436877 42.170217
    60.451432 36.760112
    24.314984 30.052427
    55.573736 63.561140
    72.162565 19.845151
    43.217518 90.320780
    51.888313 53.074269
    28.150842 40.674284
    31.619668 57.984410
    64.360526 49.975656
    53.702823 79.538952
    45.052136 35.297650
    4.702717 49.420025
    92.649989 5.431771
    65.403044 56.028507
    48.797150 30.888271
    40.806244 14.484027
    84.355436 53.896156
    50.133508 76.624964
    49.405414 78.403179
    76.824779 41.008448
    63.246400 40.075843
    78.538747 62.910356
    64.396460 56.299403
    77.152853 44.325319
    80.592411 36.177862
    48.763290 43.966714
    58.789819 90.533976
    13.684999 67.266671
    75.163001 81.909246
    46.451671 56.376068
    65.105023 34.563928
    45.815747 20.164535
    33.227702 44.477025
    41.061314 -54.334662
    40.021202 -65.490282
    22.829721 -56.861792
    43.917033 -43.558827
    40.723550 -43.188580
    53.309317 -69.996428
    31.463381 -31.506555
    24.313168 -52.662580
    17.433859 -57.468181
    32.457761 -93.127719
    9.183688 -31.686863
    10.186332 -44.173216
    27.925638 -62.236940
    9.356182 -42.291381
    23.036540 -27.153692
    -16.261328 -35.185462
    29.557288 -31.933335
    36.519228 -59.269642
    25.692837 -57.033021
    22.797337 -52.169044
    15.312205 -70.370841
    22.086548 -25.219727
    50.448475 -34.825824
    30.814475 -40.968689
    28.798789 -65.737936
    59.822791 -25.673863
    16.224354 -48.408079
    6.867234 -61.804123
    44.250439 -50.598095
    54.117605 -20.539278
    -43.244836 -3.374350
    -19.122981 -9.026765
    -4.632598 27.480272
    26.647517 24.535738
    19.527239 1.573533
    -29.982384 26.884977
    -11.856633 -24.568687
    -9.244616 -3.343794
    -15.656771 32.298241
    -22.152364 24.203428
    -34.526986 -27.862305
    -60.500060 -18.400603
    -6.902336 21.631805
    -46.863390 -27.364383
    -36.999128 4.181449
    -24.599285 -17.177658
    -24.814923 9.906257
    -7.845930 9.388576
    -36.128527 5.644606
    -31.522759 11.282073
    -12.500001 24.953627
    -21.330455 -0.830663
    -21.270652 -1.890803
    -23.750951 5.435622
    -25.563039 22.105947
    -16.047432 -5.815069
    -34.280972 30.657254
    -36.264330 -8.759981
    -12.109507 -15.804752
    -33.227330 -5.857611
    */
    
    ?>
    			

  5. Ruby

    ############################
    # クラスター分析
    #      coded by Y.Suganuma
    ############################
    
    #############################################
    # 2つのデータ間の距離
    #      method : =0 : ユークリッド距離
    #               =1 : ユークリッド距離の2乗
    #      i,j : データ番号
    #      n : 変量の数
    #      x : データ
    #      return : 距離
    #############################################
    def rng(method, i, j, n, x)
    
    	r = 0.0
    
    	for i2 in 0 ... n
    		x1  = x[i][i2] - x[j][i2]
    		r  += x1 * x1
    	end
    	if method == 0
    		r = Math.sqrt(r)
    	end
    
    	return r
    end
    
    ###############################################
    # 2つのクラスター間の距離
    #      method : =1 : 最短距離法
    #               =2 : 最長距離法
    #               =3 : メジアン法
    #               =4 : 重心法
    #               =5 : 群平均法
    #               =6 : ウォード法
    #      dio : クラスターiとクラスターoとの距離
    #      djo : クラスターjとクラスターoとの距離
    #      dij : クラスターiとクラスターjとの距離
    #      ni : クラスターiに含まれるデータ数
    #      nj : クラスターjに含まれるデータ数
    #      no : クラスターoに含まれるデータ数
    #      x,y : データ
    #      return : 距離
    #############################################
    def rng_c(method, dio, djo, dij, ni, nj, no)
    
    	r = 0.0
    			# 最短距離法
    	if method == 1
    		if dio <= djo
    			r = dio
    		else
    			r = djo
    		end
    			# 最長距離法
    	elsif metho == 2
    		if dio >= djo
    			r = dio
    		else
    			r = djo
    		end
    			# メジアン法
    	elsif metho == 3
    		r = 0.5 * dio + 0.5 * djo - 0.25 * dij
    			# 重心法
    	elsif metho == 4
    		nk = ni + nj
    		r  = ni * dio / nk + nj * djo / nk - Float(ni * nj * dij) / Float(nk * nk)
    			# 群平均法
    	elsif metho == 5
    		nk = ni + nj
    		r  = ni * dio / nk + nj * djo / nk
    			# ウォード法
    	elsif metho == 6
    		nk = ni + nj
    		r  = ((ni + no) * dio + (nj + no) * djo - no * dij) / Float(nk + no)
    	end
    
    	return r
    end
    
    #################################
    # クラスター分析
    #      method : =1 : 最短距離法
    #               =2 : 最長距離法
    #               =3 : メジアン法
    #               =4 : 重心法
    #               =5 : 群平均法
    #               =6 : ウォード法
    #      ll : グループの数
    #      nn : データの数
    #      n : 変量の数
    #      x : データ
    #      g : 所属するグループ番号
    #      coded by Y.Suganuma
    #################################
    
    def cluster(method, ll, nn, n, x, g)
    
    			# 初期設定
    	ci = 0
    	cj = 0
    	mm = nn
    	if method < 4
    		k = 0
    	else
    		k = 1
    	end
    	n_g = Array.new(nn)
    	for i1 in 0 ... nn
    		n_g[i1] = 1
    	end
    	r = Array.new(nn)
    	for i1 in 0 ... nn
    		r[i1] = Array.new(nn)
    		g[i1] = i1
    		for i2 in i1+1 ... nn
    			r[i1][i2] = rng(k, i1, i2, n, x)
    		end
    	end
    	for i1 in 0 ... nn
    		for i2 in i1+1 ... nn
    			r[i2][i1] = r[i1][i2]
    		end
    	end
    			# 実行
    	while mm > ll
    				# 最小距離のクラスターを探す
    		min = -1.0
    		for i1 in 0 ... nn
    			if g[i1] == i1
    				for i2 in i1+1 ... nn
    					if g[i2] == i2
    						if min < 0.0 or r[i1][i2] < min
    							min = r[i1][i2]
    							ci  = i1
    							cj  = i2
    						end
    					end
    				end
    			end
    		end
    				# クラスターを融合し,他のクラスターとの距離を計算
    		for i1 in 0 ... nn
    			if g[i1] == i1
    				for i2 in i1+1 ... nn
    					if g[i2] == i2
    						if i1 != cj and i2 != cj
    							if i1 == ci
    								r[i1][i2] = rng_c(method, r[ci][i2], r[cj][i2], r[ci][cj], n_g[ci], n_g[cj], n_g[i2])
    								r[i2][i1] = r[i1][i2]
    							elsif i2 == ci
    								r[i1][i2] = rng_c(method, r[i1][ci], r[i1][cj], r[ci][cj], n_g[ci], n_g[cj], n_g[i2])
    								r[i2][i1] = r[i1][i2]
    							end
    						end
    					end
    				end
    			end
    		end
    
    		n_g[ci] += n_g[cj]
    		for i1 in 0 ... nn
    			if g[i1] == cj
    				g[i1] = ci
    			end
    		end
    
    		mm -= 1
    	end
    end
    
    ss     = gets().split(" ")
    method = Integer(ss[0])   # 方法
    ll     = Integer(ss[1])   # グループ数
    n      = Integer(ss[2])   # 変数の数
    nn     = Integer(ss[3])   # データの数
    
    g      = Array.new(nn)
    x      = Array.new(nn)
    for i1 in 0 ... nn
    	x[i1] = Array.new(n)
    end
    
    for i1 in 0 ... nn   # データ
    	ss = gets().split(" ")
    	for i2 in 0 ... n
    		x[i1][i2] = Float(ss[i2])
    	end
    end
    
    cluster(method, ll, nn, n, x, g)
    
    k = 1;
    while k <= ll
    	k1 = -1
    	print("グループ " + String(k) + "\n");
    	for i1 in 0 ... nn
    		if g[i1] >= 0
    			k1 = g[i1]
    			break
    		end
    	end
    	for i1 in 0 ... nn
    		if g[i1] == k1
    			print("   " + String(i1))
    			for i2 in 0 ... n
    				print(" " + String(x[i1][i2]))
    			end
    			print("\n")
    			g[i1] = -1
    		end
    	end
    	k += 1
    end
    
    =begin
    ---------データ例(コメント部分を除いて下さい)---------
    1 3 2 100   # クラスター間距離を計算する方法(method),クラスタの数(ll,クラスタの数がこの値になったら終了),変数の数(n),及び,データの数(nn)
    66.813742 25.509139   # x, y
    50.813965 25.537399
    74.048072 39.627578
    14.792737 67.086620
    42.838304 11.391394
    32.301288 68.001189
    24.436877 42.170217
    60.451432 36.760112
    24.314984 30.052427
    55.573736 63.561140
    72.162565 19.845151
    43.217518 90.320780
    51.888313 53.074269
    28.150842 40.674284
    31.619668 57.984410
    64.360526 49.975656
    53.702823 79.538952
    45.052136 35.297650
    4.702717 49.420025
    92.649989 5.431771
    65.403044 56.028507
    48.797150 30.888271
    40.806244 14.484027
    84.355436 53.896156
    50.133508 76.624964
    49.405414 78.403179
    76.824779 41.008448
    63.246400 40.075843
    78.538747 62.910356
    64.396460 56.299403
    77.152853 44.325319
    80.592411 36.177862
    48.763290 43.966714
    58.789819 90.533976
    13.684999 67.266671
    75.163001 81.909246
    46.451671 56.376068
    65.105023 34.563928
    45.815747 20.164535
    33.227702 44.477025
    41.061314 -54.334662
    40.021202 -65.490282
    22.829721 -56.861792
    43.917033 -43.558827
    40.723550 -43.188580
    53.309317 -69.996428
    31.463381 -31.506555
    24.313168 -52.662580
    17.433859 -57.468181
    32.457761 -93.127719
    9.183688 -31.686863
    10.186332 -44.173216
    27.925638 -62.236940
    9.356182 -42.291381
    23.036540 -27.153692
    -16.261328 -35.185462
    29.557288 -31.933335
    36.519228 -59.269642
    25.692837 -57.033021
    22.797337 -52.169044
    15.312205 -70.370841
    22.086548 -25.219727
    50.448475 -34.825824
    30.814475 -40.968689
    28.798789 -65.737936
    59.822791 -25.673863
    16.224354 -48.408079
    6.867234 -61.804123
    44.250439 -50.598095
    54.117605 -20.539278
    -43.244836 -3.374350
    -19.122981 -9.026765
    -4.632598 27.480272
    26.647517 24.535738
    19.527239 1.573533
    -29.982384 26.884977
    -11.856633 -24.568687
    -9.244616 -3.343794
    -15.656771 32.298241
    -22.152364 24.203428
    -34.526986 -27.862305
    -60.500060 -18.400603
    -6.902336 21.631805
    -46.863390 -27.364383
    -36.999128 4.181449
    -24.599285 -17.177658
    -24.814923 9.906257
    -7.845930 9.388576
    -36.128527 5.644606
    -31.522759 11.282073
    -12.500001 24.953627
    -21.330455 -0.830663
    -21.270652 -1.890803
    -23.750951 5.435622
    -25.563039 22.105947
    -16.047432 -5.815069
    -34.280972 30.657254
    -36.264330 -8.759981
    -12.109507 -15.804752
    -33.227330 -5.857611
    =end
    			

  6. Python

    # -*- coding: UTF-8 -*-
    import numpy as np
    import sys
    from math import *
    
    #############################################
    # 2つのデータ間の距離
    #      method : =0 : ユークリッド距離
    #               =1 : ユークリッド距離の2乗
    #      i,j : データ番号
    #      n : 変量の数
    #      x : データ
    #      return : 距離
    #############################################
    def rng(method, i, j, n, x) :
    
    	r = 0.0
    
    	for i2 in range(0, n) :
    		x1  = x[i][i2] - x[j][i2]
    		r  += x1 * x1
    	if method == 0 :
    		r = sqrt(r)
    
    	return r
    
    ###############################################
    # 2つのクラスター間の距離
    #      method : =1 : 最短距離法
    #               =2 : 最長距離法
    #               =3 : メジアン法
    #               =4 : 重心法
    #               =5 : 群平均法
    #               =6 : ウォード法
    #      Dio : クラスターiとクラスターoとの距離
    #      Djo : クラスターjとクラスターoとの距離
    #      Dij : クラスターiとクラスターjとの距離
    #      ni : クラスターiに含まれるデータ数
    #      nj : クラスターjに含まれるデータ数
    #      no : クラスターoに含まれるデータ数
    #      x,y : データ
    #      return : 距離
    #############################################
    def rng_c(method, Dio, Djo, Dij, ni, nj, no) :
    
    	r = 0.0
    			# 最短距離法
    	if method == 1 :
    		if Dio <= Djo :
    			r = Dio
    		else :
    			r = Djo
    			# 最長距離法
    	elif metho == 2 :
    		if Dio >= Djo :
    			r = Dio
    		else :
    			r = Djo
    			# メジアン法
    	elif metho == 3 :
    		r = 0.5 * Dio + 0.5 * Djo - 0.25 * Dij
    			# 重心法
    	elif metho == 4 :
    		nk = ni + nj
    		r  = ni * Dio / nk + nj * Djo / nk - float(ni * nj * Dij) / float(nk * nk)
    			# 群平均法
    	elif metho == 5 :
    		nk = ni + nj
    		r  = ni * Dio / nk + nj * Djo / nk
    			# ウォード法
    	elif metho == 6 :
    		nk = ni + nj
    		r  = ((ni + no) * Dio + (nj + no) * Djo - no * Dij) / float(nk + no)
    
    	return r
    
    #################################
    # クラスター分析
    #      method : =1 : 最短距離法
    #               =2 : 最長距離法
    #               =3 : メジアン法
    #               =4 : 重心法
    #               =5 : 群平均法
    #               =6 : ウォード法
    #      L : グループの数
    #      N : データの数
    #      n : 変量の数
    #      x : データ
    #      g : 所属するグループ番号
    #      coded by Y.Suganuma
    #################################
    
    def cluster(method, L, N, n, x, g) :
    
    			# 初期設定
    	ci = 0
    	cj = 0
    	M  = N
    	if method < 4 :
    		k = 0
    	else :
    		k = 1
    	n_g = np.ones(N, np.int)
    	r   = np.empty((N, N), np.float)
    	for i1 in range(0, N) :
    		g[i1]   = i1
    		for i2 in range(i1+1, N) :
    			r[i1][i2] = rng(k, i1, i2, n, x)
    	for i1 in range(0, N) :
    		for i2 in range(i1+1, N) :
    			r[i2][i1] = r[i1][i2]
    			# 実行
    	while M > L :
    				# 最小距離のクラスターを探す
    		min = -1.0
    		for i1 in range(0, N) :
    			if g[i1] == i1 :
    				for i2 in range(i1+1, N) :
    					if g[i2] == i2 :
    						if min < 0.0 or r[i1][i2] < min :
    							min = r[i1][i2]
    							ci  = i1
    							cj  = i2
    				# クラスターを融合し,他のクラスターとの距離を計算
    		for i1 in range(0, N) :
    			if g[i1] == i1 :
    				for i2 in range(i1+1, N) :
    					if g[i2] == i2 :
    						if i1 != cj and i2 != cj :
    							if i1 == ci :
    								r[i1][i2] = rng_c(method, r[ci][i2], r[cj][i2], r[ci][cj], n_g[ci], n_g[cj], n_g[i2])
    								r[i2][i1] = r[i1][i2]
    							elif i2 == ci :
    								r[i1][i2] = rng_c(method, r[i1][ci], r[i1][cj], r[ci][cj], n_g[ci], n_g[cj], n_g[i2])
    								r[i2][i1] = r[i1][i2]
    
    		n_g[ci] += n_g[cj]
    		for i1 in range(0, N) :
    			if g[i1] == cj :
    				g[i1] = ci
    
    		M -= 1
    
    ############################
    # クラスター分析
    #      coded by Y.Suganuma
    ############################
    
    line   = sys.stdin.readline()
    ss     = line.split()
    method = int(ss[0])   # 方法
    L      = int(ss[1])   # グループ数
    n      = int(ss[2])   # 変数の数
    N      = int(ss[3])   # データの数
    
    g      = np.empty(N, np.int)
    x      = np.empty((N, n), np.float)
    
    for i1 in range(0, N) :   # データ
    	line = sys.stdin.readline()
    	ss   = line.split()
    	for i2 in range(0, n) :
    		x[i1][i2] = float(ss[i2])
    
    cluster(method, L, N, n, x, g)
    
    k = 1;
    while k <= L :
    	k1 = -1
    	print("グループ " + str(k));
    	for i1 in range(0, N) :
    		if g[i1] >= 0 :
    			k1 = g[i1]
    			break
    	for i1 in range(0, N) :
    		if g[i1] == k1 :
    			print("   " + str(i1), end="")
    			for i2 in range(0, n) :
    				print(" " + str(x[i1][i2]), end="")
    			print()
    			g[i1] = -1
    	k += 1
    
    """
    ---------データ例(コメント部分を除いて下さい)---------
    1 3 2 100   # クラスター間距離を計算する方法(method),クラスタの数(L,クラスタの数がこの値になったら終了),変数の数(n),及び,データの数(N)
    66.813742 25.509139   # x, y
    50.813965 25.537399
    74.048072 39.627578
    14.792737 67.086620
    42.838304 11.391394
    32.301288 68.001189
    24.436877 42.170217
    60.451432 36.760112
    24.314984 30.052427
    55.573736 63.561140
    72.162565 19.845151
    43.217518 90.320780
    51.888313 53.074269
    28.150842 40.674284
    31.619668 57.984410
    64.360526 49.975656
    53.702823 79.538952
    45.052136 35.297650
    4.702717 49.420025
    92.649989 5.431771
    65.403044 56.028507
    48.797150 30.888271
    40.806244 14.484027
    84.355436 53.896156
    50.133508 76.624964
    49.405414 78.403179
    76.824779 41.008448
    63.246400 40.075843
    78.538747 62.910356
    64.396460 56.299403
    77.152853 44.325319
    80.592411 36.177862
    48.763290 43.966714
    58.789819 90.533976
    13.684999 67.266671
    75.163001 81.909246
    46.451671 56.376068
    65.105023 34.563928
    45.815747 20.164535
    33.227702 44.477025
    41.061314 -54.334662
    40.021202 -65.490282
    22.829721 -56.861792
    43.917033 -43.558827
    40.723550 -43.188580
    53.309317 -69.996428
    31.463381 -31.506555
    24.313168 -52.662580
    17.433859 -57.468181
    32.457761 -93.127719
    9.183688 -31.686863
    10.186332 -44.173216
    27.925638 -62.236940
    9.356182 -42.291381
    23.036540 -27.153692
    -16.261328 -35.185462
    29.557288 -31.933335
    36.519228 -59.269642
    25.692837 -57.033021
    22.797337 -52.169044
    15.312205 -70.370841
    22.086548 -25.219727
    50.448475 -34.825824
    30.814475 -40.968689
    28.798789 -65.737936
    59.822791 -25.673863
    16.224354 -48.408079
    6.867234 -61.804123
    44.250439 -50.598095
    54.117605 -20.539278
    -43.244836 -3.374350
    -19.122981 -9.026765
    -4.632598 27.480272
    26.647517 24.535738
    19.527239 1.573533
    -29.982384 26.884977
    -11.856633 -24.568687
    -9.244616 -3.343794
    -15.656771 32.298241
    -22.152364 24.203428
    -34.526986 -27.862305
    -60.500060 -18.400603
    -6.902336 21.631805
    -46.863390 -27.364383
    -36.999128 4.181449
    -24.599285 -17.177658
    -24.814923 9.906257
    -7.845930 9.388576
    -36.128527 5.644606
    -31.522759 11.282073
    -12.500001 24.953627
    -21.330455 -0.830663
    -21.270652 -1.890803
    -23.750951 5.435622
    -25.563039 22.105947
    -16.047432 -5.815069
    -34.280972 30.657254
    -36.264330 -8.759981
    -12.109507 -15.804752
    -33.227330 -5.857611
    """
    			

  7. C#

    /****************************/
    /* クラスター分析           */
    /*      coded by Y.Suganuma */
    /****************************/
    using System;
    
    class Program
    {
    	static void Main()
    	{
    		Test1 ts = new Test1();
    	}
    }
    
    class Test1
    {
    	public Test1()
    	{
    		char[] charSep = new char[] {' '};
    					// 方法,グループ数,変数の数,及び,データの数
    		String[] str = Console.ReadLine().Split(charSep, StringSplitOptions.RemoveEmptyEntries);
    		int method   = int.Parse(str[0]);
    		int L        = int.Parse(str[1]);
    		int n        = int.Parse(str[2]);
    		int N        = int.Parse(str[3]);
    
    		int[] g      = new int [N];
    		double[][] x = new double [N][];
    		for (int i1 = 0; i1 < N; i1++)
    			x[i1] = new double [n];
    					// データ
    		for (int i1 = 0; i1 < N; i1++) {
    			str = Console.ReadLine().Split(charSep, StringSplitOptions.RemoveEmptyEntries);
    			for (int i2 = 0; i2 < n; i2++)
    				x[i1][i2] = double.Parse(str[i2]);
    		}
    					// クラスター分析
    		cluster(method, L, N, n, x, g);
    					// 出力
    		int k = 1;
    		while (k <= L) {
    			int k1 = -1;
    			Console.WriteLine("グループ " + k);
    			for (int i1 = 0; i1 < N && k1 < 0; i1++) {
    				if (g[i1] >= 0)
    					k1 = g[i1];
    			}
    			for (int i1 = 0; i1 < N; i1++) {
    				if (g[i1] == k1) {
    					Console.Write("   " + (i1+1));
    					for (int i2 = 0; i2 < n; i2++)
    						Console.Write(" " + x[i1][i2]);
    					Console.WriteLine();
    					g[i1] = -1;
    				}
    			}
    			k++;
    		}
    	}
    
    	/*********************************/
    	/* クラスター分析                */
    	/*      method : =1 : 最短距離法 */
    	/*               =2 : 最長距離法 */
    	/*               =3 : メジアン法 */
    	/*               =4 : 重心法     */
    	/*               =5 : 群平均法   */
    	/*               =6 : ウォード法 */
    	/*      L : グループの数         */
    	/*      N : データの数           */
    	/*      n : 変量の数             */
    	/*      x : データ               */
    	/*      g : 所属するグループ番号 */
    	/*********************************/
    	void cluster(int method, int L, int N, int n, double[][] x, int[] g)
    	{
    					// 初期設定
    		int k   = (method < 4) ? 0 : 1;
    		int[] n_g = new int [N];
    		double[][] r   = new double [N][];
    		for (int i1 = 0; i1 < N; i1++) {
    			r[i1]   = new double [N];
    			g[i1]   = i1;
    			n_g[i1] = 1;
    			for (int i2 = i1+1; i2 < N; i2++)
    				r[i1][i2] = range(k, i1, i2, n, x);
    		}
    		for (int i1 = 0; i1 < N; i1++) {
    			for (int i2 = i1+1; i2 < N; i2++)
    				r[i2][i1] = r[i1][i2];
    		}
    					// 実行
    		int ci = 0, cj = 0, M = N;
    		while (M > L) {
    						// 最小距離のクラスターを探す
    			double min = -1.0;
    			for (int i1 = 0; i1 < N; i1++) {
    				if (g[i1] == i1) {
    					for (int i2 = i1+1; i2 < N; i2++) {
    						if (g[i2] == i2) {
    							if (min < 0.0 || r[i1][i2] < min) {
    								min = r[i1][i2];
    								ci  = i1;
    								cj  = i2;
    							}
    						}
    					}
    				}
    			}
    						// クラスターを融合し,他のクラスターとの距離を計算
    			for (int i1 = 0; i1 < N; i1++) {
    				if (g[i1] == i1) {
    					for (int i2 = i1+1; i2 < N; i2++) {
    						if (g[i2] == i2) {
    							if (i1 != cj && i2 != cj) {
    								if (i1 == ci) {
    									r[i1][i2] = range_c(method, r[ci][i2], r[cj][i2],
                                                            r[ci][cj], n_g[ci], n_g[cj], n_g[i2]);
    									r[i2][i1] = r[i1][i2];
    								}
    								else if (i2 == ci) {
    									r[i1][i2] = range_c(method, r[i1][ci], r[i1][cj],
                                                            r[ci][cj], n_g[ci], n_g[cj], n_g[i2]);
    									r[i2][i1] = r[i1][i2];
    								}
    							}
    						}
    					}
    				}
    			}
    
    			n_g[ci] += n_g[cj];
    			for (int i1 = 0; i1 < N; i1++) {
    				if (g[i1] == cj)
    					g[i1] = ci;
    			}
    
    			M--;
    		}
    	}
    
    	/*********************************************/
    	/* 2つのデータ間の距離                      */
    	/*      method : =0 : ユークリッド距離       */
    	/*               =1 : ユークリッド距離の2乗 */
    	/*      i,j : データ番号                     */
    	/*      n : 変量の数                         */
    	/*      x : データ                           */
    	/*      return : 距離                        */
    	/*********************************************/
    	double range(int method, int i, int j, int n, double[][] x)
    	{
    		double x1, r = 0.0;
    
    		for (int i2 = 0; i2 < n; i2++) {
    			x1  = x[i][i2] - x[j][i2];
    			r  += x1 * x1;
    		}
    		if (method == 0)
    			r = Math.Sqrt(r);
    
    		return r;
    	}
    
    	/***********************************************/
    	/* 2つのクラスター間の距離                    */
    	/*      method : =1 : 最短距離法               */
    	/*               =2 : 最長距離法               */
    	/*               =3 : メジアン法               */
    	/*               =4 : 重心法                   */
    	/*               =5 : 群平均法                 */
    	/*               =6 : ウォード法               */
    	/*      Dio : クラスターiとクラスターoとの距離 */
    	/*      Djo : クラスターjとクラスターoとの距離 */
    	/*      Dij : クラスターiとクラスターjとの距離 */
    	/*      ni : クラスターiに含まれるデータ数     */
    	/*      nj : クラスターjに含まれるデータ数     */
    	/*      no : クラスターoに含まれるデータ数     */
    	/*      x,y : データ                           */
    	/*      return : 距離                          */
    	/***********************************************/
    	double range_c(int method, double Dio, double Djo, double Dij, int ni, int nj, int no)
    	{
    		double r = 0.0;
    		int nk;
    
    		switch (method) {
    					// 最短距離法
    			case 1:
    				r = (Dio <= Djo) ? Dio : Djo;
    				break;
    					// 最長距離法
    			case 2:
    				r = (Dio >= Djo) ? Dio : Djo;
    				break;
    					// メジアン法
    			case 3:
    				r = 0.5 * Dio + 0.5 * Djo - 0.25 * Dij;
    				break;
    					// 重心法
    			case 4:
    				nk = ni + nj;
    				r  = ni * Dio / nk + nj * Djo / nk - (double)ni * nj * Dij / ((double)nk * nk);
    				break;
    					// 群平均法
    			case 5:
    				nk = ni + nj;
    				r  = ni * Dio / nk + nj * Djo / nk;
    				break;
    					// ウォード法
    			case 6:
    				nk = ni + nj;
    				r  = ((ni + no) * Dio + (nj + no) * Djo - no * Dij) / ((double)nk + no);
    				break;
    		}
    
    		return r;
    	}
    }
    
    /*
    ---------データ例(コメント部分を除いて下さい)---------
    1 3 2 100   // クラスター間距離を計算する方法(method),クラスタの数(L,クラスタの数がこの値になったら終了),変数の数(n),及び,データの数(N)
    66.813742 25.509139   // x, y
    50.813965 25.537399
    74.048072 39.627578
    14.792737 67.086620
    42.838304 11.391394
    32.301288 68.001189
    24.436877 42.170217
    60.451432 36.760112
    24.314984 30.052427
    55.573736 63.561140
    72.162565 19.845151
    43.217518 90.320780
    51.888313 53.074269
    28.150842 40.674284
    31.619668 57.984410
    64.360526 49.975656
    53.702823 79.538952
    45.052136 35.297650
    4.702717 49.420025
    92.649989 5.431771
    65.403044 56.028507
    48.797150 30.888271
    40.806244 14.484027
    84.355436 53.896156
    50.133508 76.624964
    49.405414 78.403179
    76.824779 41.008448
    63.246400 40.075843
    78.538747 62.910356
    64.396460 56.299403
    77.152853 44.325319
    80.592411 36.177862
    48.763290 43.966714
    58.789819 90.533976
    13.684999 67.266671
    75.163001 81.909246
    46.451671 56.376068
    65.105023 34.563928
    45.815747 20.164535
    33.227702 44.477025
    41.061314 -54.334662
    40.021202 -65.490282
    22.829721 -56.861792
    43.917033 -43.558827
    40.723550 -43.188580
    53.309317 -69.996428
    31.463381 -31.506555
    24.313168 -52.662580
    17.433859 -57.468181
    32.457761 -93.127719
    9.183688 -31.686863
    10.186332 -44.173216
    27.925638 -62.236940
    9.356182 -42.291381
    23.036540 -27.153692
    -16.261328 -35.185462
    29.557288 -31.933335
    36.519228 -59.269642
    25.692837 -57.033021
    22.797337 -52.169044
    15.312205 -70.370841
    22.086548 -25.219727
    50.448475 -34.825824
    30.814475 -40.968689
    28.798789 -65.737936
    59.822791 -25.673863
    16.224354 -48.408079
    6.867234 -61.804123
    44.250439 -50.598095
    54.117605 -20.539278
    -43.244836 -3.374350
    -19.122981 -9.026765
    -4.632598 27.480272
    26.647517 24.535738
    19.527239 1.573533
    -29.982384 26.884977
    -11.856633 -24.568687
    -9.244616 -3.343794
    -15.656771 32.298241
    -22.152364 24.203428
    -34.526986 -27.862305
    -60.500060 -18.400603
    -6.902336 21.631805
    -46.863390 -27.364383
    -36.999128 4.181449
    -24.599285 -17.177658
    -24.814923 9.906257
    -7.845930 9.388576
    -36.128527 5.644606
    -31.522759 11.282073
    -12.500001 24.953627
    -21.330455 -0.830663
    -21.270652 -1.890803
    -23.750951 5.435622
    -25.563039 22.105947
    -16.047432 -5.815069
    -34.280972 30.657254
    -36.264330 -8.759981
    -12.109507 -15.804752
    -33.227330 -5.857611
    */
    			

  8. VB

    '**************************'
    ' クラスター分析           '
    '      coded by Y.Suganuma '
    '**************************'
    Imports System.Text.RegularExpressions
    
    Module Test
    
    	Sub Main()
    
    		Dim MS As Regex = New Regex("\s+") 
    					' 方法,グループ数,変数の数,及び,データの数
    		Dim str() As String   = MS.Split(Console.ReadLine().Trim())
    		Dim method As Integer = Integer.Parse(str(0))
    		Dim L As Integer      = Integer.Parse(str(1))
    		Dim n As Integer      = Integer.Parse(str(2))
    		Dim NN As Integer     = Integer.Parse(str(3))
    
    		Dim g(NN) As Integer
    		Dim x(NN,n) As Double
    					' データ
    		For i1 As Integer = 0 To NN-1
    			str = MS.Split(Console.ReadLine().Trim())
    			For i2 As Integer = 0 To n-1
    				x(i1,i2) = Double.Parse(str(i2))
    			Next
    		Next
    					' クラスター分析
    		cluster(method, L, NN, n, x, g)
    					' 出力
    		Dim k As Integer = 1
    		Do While k <= L
    			Dim k1 As Integer = -1
    			Console.WriteLine("グループ " & k)
    			Dim i1t As Integer = 0
    			Do While i1t < NN and k1 < 0
    				If g(i1t) >= 0
    					k1 = g(i1t)
    				End If
    				i1t += 1
    			Loop
    			For i1 As Integer = 0 To NN-1
    				If g(i1) = k1
    					Console.Write("   " & (i1+1))
    					For i2 As Integer = 0 To n-1
    						Console.Write(" " & x(i1,i2))
    					Next
    					Console.WriteLine()
    					g(i1) = -1
    				End If
    			Next
    			k += 1
    		Loop
    
    	End Sub
    
    	'*******************************'
    	' クラスター分析                '
    	'      method : =1 : 最短距離法 '
    	'               =2 : 最長距離法 '
    	'               =3 : メジアン法 '
    	'               =4 : 重心法     '
    	'               =5 : 群平均法   '
    	'               =6 : ウォード法 '
    	'      L : グループの数         '
    	'      NN : データの数          '
    	'      n : 変量の数             '
    	'      x : データ               '
    	'      g : 所属するグループ番号 '
    	'*******************************'
    	Sub cluster(method As Integer, L As Integer, NN As Integer, n As Integer,
    	            x(,) As Double, g() As Integer)
    
    					' 初期設定
    		Dim k As Integer
    		If method < 4
    			k = 0
    		Else
    			k = 1
    		End If
    		Dim n_g(NN) As Integer
    		Dim r(NN,NN) As Double
    		For i1 As Integer = 0 To NN-1
    			g(i1)   = i1
    			n_g(i1) = 1
    			For i2 As Integer = i1+1 To NN-1
    				r(i1,i2) = range(k, i1, i2, n, x)
    			Next
    		Next
    		For i1 As Integer = 0 To NN-1
    			For i2 As Integer = i1+1 To NN-1
    				r(i2,i1) = r(i1,i2)
    			Next
    		Next
    					' 実行
    		Dim ci As Integer = 0
    		Dim cj As Integer = 0
    		Dim M As Integer  = NN
    		Do While M > L
    						' 最小距離のクラスターを探す
    			Dim min As Double = -1.0
    			For i1 As Integer = 0 To NN-1
    				If g(i1) = i1
    					For i2 As Integer = i1+1 To NN-1
    						If g(i2) = i2
    							If min < 0.0 or r(i1,i2) < min
    								min = r(i1,i2)
    								ci  = i1
    								cj  = i2
    							End If
    						End If
    					Next
    				End If
    			Next
    						' クラスターを融合し,他のクラスターとの距離を計算
    			For i1 As Integer = 0 To NN-1
    				If g(i1) = i1
    					For i2 As Integer = i1+1 To NN-1
    						If g(i2) = i2
    							If i1 <> cj and i2 <> cj
    								If i1 = ci
    									r(i1,i2) = range_c(method, r(ci,i2), r(cj,i2),
                                                   r(ci,cj), n_g(ci), n_g(cj), n_g(i2))
    									r(i2,i1) = r(i1,i2)
    								ElseIf i2 = ci
    									r(i1,i2) = range_c(method, r(i1,ci), r(i1,cj),
                                                   r(ci,cj), n_g(ci), n_g(cj), n_g(i2))
    									r(i2,i1) = r(i1,i2)
    								End If
    							End If
    						End If
    					Next
    				End If
    			Next
    
    			n_g(ci) += n_g(cj)
    			For i1 As Integer = 0 To NN-1
    				If g(i1) = cj
    					g(i1) = ci
    				End If
    			Next
    
    			M -= 1
    		Loop
    
    	End Sub
    
    	'*******************************************'
    	' 2つのデータ間の距離                      '
    	'      method : =0 : ユークリッド距離       '
    	'               =1 : ユークリッド距離の2乗 '
    	'      i,j : データ番号                     '
    	'      n : 変量の数                         '
    	'      x : データ                           '
    	'      return : 距離                        '
    	'*******************************************'
    	Function range(method As Integer, i As Integer, j As Integer, n As Integer, x(,) As Double)
    
    		Dim x1 As Double
    		Dim r As Double = 0.0
    
    		For  i2 As Integer = 0 To n-1
    			x1  = x(i,i2) - x(j,i2)
    			r  += x1 * x1
    		Next
    		If method = 0
    			r = Math.Sqrt(r)
    		End If
    
    		Return r
    
    	End Function
    
    	'*********************************************'
    	' 2つのクラスター間の距離                    '
    	'      method : =1 : 最短距離法               '
    	'               =2 : 最長距離法               '
    	'               =3 : メジアン法               '
    	'               =4 : 重心法                   '
    	'               =5 : 群平均法                 '
    	'               =6 : ウォード法               '
    	'      Dio : クラスターiとクラスターoとの距離 '
    	'      Djo : クラスターjとクラスターoとの距離 '
    	'      Dij : クラスターiとクラスターjとの距離 '
    	'      ni : クラスターiに含まれるデータ数     '
    	'      nj : クラスターjに含まれるデータ数     '
    	'      no : クラスターoに含まれるデータ数     '
    	'      x,y : データ                           '
    	'      return : 距離                          '
    	'*********************************************'
    	Function range_c(method As Integer, Dio As Double, Djo As Double, Dij As Double,
    	                 ni As Integer, nj As Integer, no As Integer)
    
    		Dim r As Double = 0.0
    		Dim nk As Integer
    
    		Select Case method
    					' 最短距離法
    			Case 1
    				If Dio <= Djo
    					r = Dio
    				Else
    					r = Djo
    				End If
    					' 最長距離法
    			Case 2
    				If Dio >= Djo
    					r = Dio
    				Else
    					r = Djo
    				End If
    					' メジアン法
    			Case 3
    				r = 0.5 * Dio + 0.5 * Djo - 0.25 * Dij
    					' 重心法
    			Case 4
    				nk = ni + nj
    				r  = ni * Dio / nk + nj * Djo / nk - ni * nj * Dij / (nk * nk)
    					' 群平均法
    			Case 5
    				nk = ni + nj
    				r  = ni * Dio / nk + nj * Djo / nk
    					' ウォード法
    			Case 6
    				nk = ni + nj
    				r  = ((ni + no) * Dio + (nj + no) * Djo - no * Dij) / (nk + no)
    		End Select
    
    		Return r
    
    	End Function
    
    End Module
    
    /*
    ---------データ例(コメント部分を除いて下さい)---------
    1 3 2 100   // クラスター間距離を計算する方法(method),クラスタの数(L,クラスタの数がこの値になったら終了),変数の数(n),及び,データの数(N)
    66.813742 25.509139   // x, y
    50.813965 25.537399
    74.048072 39.627578
    14.792737 67.086620
    42.838304 11.391394
    32.301288 68.001189
    24.436877 42.170217
    60.451432 36.760112
    24.314984 30.052427
    55.573736 63.561140
    72.162565 19.845151
    43.217518 90.320780
    51.888313 53.074269
    28.150842 40.674284
    31.619668 57.984410
    64.360526 49.975656
    53.702823 79.538952
    45.052136 35.297650
    4.702717 49.420025
    92.649989 5.431771
    65.403044 56.028507
    48.797150 30.888271
    40.806244 14.484027
    84.355436 53.896156
    50.133508 76.624964
    49.405414 78.403179
    76.824779 41.008448
    63.246400 40.075843
    78.538747 62.910356
    64.396460 56.299403
    77.152853 44.325319
    80.592411 36.177862
    48.763290 43.966714
    58.789819 90.533976
    13.684999 67.266671
    75.163001 81.909246
    46.451671 56.376068
    65.105023 34.563928
    45.815747 20.164535
    33.227702 44.477025
    41.061314 -54.334662
    40.021202 -65.490282
    22.829721 -56.861792
    43.917033 -43.558827
    40.723550 -43.188580
    53.309317 -69.996428
    31.463381 -31.506555
    24.313168 -52.662580
    17.433859 -57.468181
    32.457761 -93.127719
    9.183688 -31.686863
    10.186332 -44.173216
    27.925638 -62.236940
    9.356182 -42.291381
    23.036540 -27.153692
    -16.261328 -35.185462
    29.557288 -31.933335
    36.519228 -59.269642
    25.692837 -57.033021
    22.797337 -52.169044
    15.312205 -70.370841
    22.086548 -25.219727
    50.448475 -34.825824
    30.814475 -40.968689
    28.798789 -65.737936
    59.822791 -25.673863
    16.224354 -48.408079
    6.867234 -61.804123
    44.250439 -50.598095
    54.117605 -20.539278
    -43.244836 -3.374350
    -19.122981 -9.026765
    -4.632598 27.480272
    26.647517 24.535738
    19.527239 1.573533
    -29.982384 26.884977
    -11.856633 -24.568687
    -9.244616 -3.343794
    -15.656771 32.298241
    -22.152364 24.203428
    -34.526986 -27.862305
    -60.500060 -18.400603
    -6.902336 21.631805
    -46.863390 -27.364383
    -36.999128 4.181449
    -24.599285 -17.177658
    -24.814923 9.906257
    -7.845930 9.388576
    -36.128527 5.644606
    -31.522759 11.282073
    -12.500001 24.953627
    -21.330455 -0.830663
    -21.270652 -1.890803
    -23.750951 5.435622
    -25.563039 22.105947
    -16.047432 -5.815069
    -34.280972 30.657254
    -36.264330 -8.759981
    -12.109507 -15.804752
    -33.227330 -5.857611
    */
    			

静岡理工科大学 菅沼ホーム 目次 索引