凝集型クラスタリング

agg.php

<?php
/*
	実行例
	php agg.php 0,1,3,5.5,10,7,8.8
*/

// 区切り文字
$IN_DELIM = ',';	// クラスタ内区切り文字
$OUT_DELIM = ' | ';	// クラスタ間区切り文字



// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- //
// 比較方法いろいろ
// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- //
// 単連結法 single-link method (クラスタ同士の比較では最も近いところを比較する)
function single_calc($lhs, $rhs)
{
	return $rhs[0] - $lhs[count($lhs) - 1];
}
// 完全連結法 complete-link method (クラスタ同士の比較では最も遠いところを比較する)
function complete_calc($lhs, $rhs)
{
	return $rhs[count($rhs) - 1] - $lhs[0];
}
// 重心法 centroid method (クラスタ同士の比較では重心同士を比較する)
function centroid_calc($lhs, $rhs)
{
	$rhs = array_sum($rhs) / count($rhs);
	$lhs = array_sum($lhs) / count($lhs);
	return $rhs - $lhs;
}
// 距離を測る
function calc_dist($lhs, $rhs, $calc)
{
	global $IN_DELIM;
	$lhs = explode($IN_DELIM, $lhs);
	$rhs = explode($IN_DELIM, $rhs);
	return $calc($lhs, $rhs);
}

// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- //
// メイン処理
// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- //
function Main()
{
	// 引数解釈
	global $argv;
	$inputs = $argv[1];
	print "inputs = $inputs\n";
	$inputs = explode(',', $inputs);

	// ソート
	print "start.\n\n";
	sort($inputs);

	// それぞれについて処理を行う
	DoLogic($inputs, 0, 'single_calc');
	DoLogic($inputs, 1, 'complete_calc');
	DoLogic($inputs, 2, 'centroid_calc');

	// 出力結果のフラッシュ
	PrintColFlush();
	print "\nend.\n";
}

// 処理をする
function DoLogic($inputs, $col, $calc)
{
	// 処理開始
	PrintCol($col, $calc . "\n");
	while(1){
		PrintCol($col, "--\n");
		// まず表示
		global $OUT_DELIM;
		PrintCol($col, join($OUT_DELIM, $inputs) . "\n");

		// 要素数が1なら終了
		$n = count($inputs);
		if($n <= 1)break;

		// 最短距離を探す
		$min_dist = 100000;
		$min_i = -1;
		for($i = 0; $i < $n - 1; $i++){
			$dist = calc_dist($inputs[$i], $inputs[$i + 1], $calc);
			if($dist < $min_dist){
				$min_dist = $dist;
				$min_i = $i;
			}
		}

		// 最短距離のものを連結する
		global $IN_DELIM;
		array_splice($inputs, $min_i, 2, $inputs[$min_i] . $IN_DELIM . $inputs[$min_i + 1]);
	}
}

// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- //
// 出力用
// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- //
$g_cols;
function PrintCol($col, $text)
{
	global $g_cols;
	$text = rtrim($text, "\n");
	if(!isset($g_cols[$col]))$g_cols[$col] = array();
	$g_cols[$col][] = $text;
}
function PrintColFlush()
{
	global $g_cols;

	// それぞれの幅を求める。行数を求める
	$max_line_count = 0;
	$widths = array(0, 0, 0);
	for($i = 0; $i < 3; $i++){
		$max_width = 0;
		foreach($g_cols[$i] as $line){
			$max_width = max($max_width, strlen($line));
		}
		$widths[$i] = $max_width + 6;
		$max_line_count = max($max_line_count, count($g_cols[$i]));
	}

	// それぞれを出力する
	for($i = 0; $i < $max_line_count; $i++){
		for($j = 0; $j < 3; $j++){
			$line = isset($g_cols[$j][$i])?$g_cols[$j][$i]:'';
			$width = $widths[$j];
			print $line;
			$w = strlen($line);
			//print "width = $width, w = $w\n";
			print str_repeat(' ', $width - $w);
		}
		print "\n";
	}
}

// 処理実行
Main();