| 情報学部 | 菅沼ホーム | 目次 | 索引 |
/****************************/
/* クラスター分析 */
/* 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;
}
/*********************************************/
/* ２つのデータ間の距離 */
/* method : =0 : ユークリッド距離 */
/* =1 : ユークリッド距離の２乗 */
/* 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;
}
/***********************************************/
/* ２つのクラスター間の距離 */
/* 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
*/
/****************************/
/* クラスター分析 */
/* 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--;
}
}
/*********************************************/
/* ２つのデータ間の距離 */
/* method : =0 : ユークリッド距離 */
/* =1 : ユークリッド距離の２乗 */
/* 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;
}
/***********************************************/
/* ２つのクラスター間の距離 */
/* 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
*/
<!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--;
}
}
/*********************************************/
/* ２つのデータ間の距離 */
/* method : =0 : ユークリッド距離 */
/* =1 : ユークリッド距離の２乗 */
/* 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;
}
/***********************************************/
/* ２つのクラスター間の距離 */
/* 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>
<?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--;
}
}
/*********************************************/
/* ２つのデータ間の距離 */
/* method : =0 : ユークリッド距離 */
/* =1 : ユークリッド距離の２乗 */
/* 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;
}
/***********************************************/
/* ２つのクラスター間の距離 */
/* 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
*/
?>
############################
# クラスター分析
# coded by Y.Suganuma
############################
#############################################
# ２つのデータ間の距離
# method : =0 : ユークリッド距離
# =1 : ユークリッド距離の２乗
# 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
###############################################
# ２つのクラスター間の距離
# 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
# -*- coding: UTF-8 -*-
import numpy as np
import sys
from math import *
#############################################
# ２つのデータ間の距離
# method : =0 : ユークリッド距離
# =1 : ユークリッド距離の２乗
# 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
###############################################
# ２つのクラスター間の距離
# 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
"""
/****************************/
/* クラスター分析 */
/* 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--;
}
}
/*********************************************/
/* ２つのデータ間の距離 */
/* method : =0 : ユークリッド距離 */
/* =1 : ユークリッド距離の２乗 */
/* 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;
}
/***********************************************/
/* ２つのクラスター間の距離 */
/* 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
*/
'**************************'
' クラスター分析 '
' 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
'*******************************************'
' ２つのデータ間の距離 '
' method : =0 : ユークリッド距離 '
' =1 : ユークリッド距離の２乗 '
' 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
'*********************************************'
' ２つのクラスター間の距離 '
' 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
*/
| 情報学部 | 菅沼ホーム | 目次 | 索引 |