駆け足で読むRで学ぶクラスタ解析 第４章 階層的手法

• 全要素を別個のクラスタとした段階から、クラスタ間の距離がもっとも近い２つのクラスタを１つのクラスタとみなす、という処理を繰り返し、最終的に１つのクラスタに纏め上げ、その過程で作ったクラスタの包含関係をクラスタ構造の全体とする手法
• クラスタ間の距離の定め方によって、手法名がついている
• 手法
  • 群平均法(group average method)
  • 単連結法(single linkage method)
  • 完全連結法(complete linkage method)
  • ウォード法(Ward method)
  • 重心法(centroid method)
  • メディアン法(median method)
• Javaで
  • 群平均法
    • クラスタ間の距離は、構成要素同士ペアのすべての距離の平均で定義する
      • 

	public static double distGroupAverage(double[][] a,double[][] b){
		double ret=0;
		for(int i=0;i<a.length;i++){
			for(int j=0;j<b.length;j++){
				ret+=distance(a[i],b[j]);
			}
		}
		ret /=(double)(a.length+b.length);
		return ret;
	}
public static double distance(double[] a, double[] b){
		double ret=0;
		for(int i=0;i<a.length;i++){
			ret += (a[i]-b[i])*(a[i]-b[i]);
		}
		ret = Math.sqrt(ret);
		return ret;
	}

• • 単連結法
    • クラスタ間の距離は、構成要素同士ペアの距離の最小値で定義する
      • 

public static double distSingleLinkage(double[][] a,double[][] b){
		double ret=distance(a[0],b[0]);
		for(int i=0;i<a.length;i++){
			for(int j=0;j<b.length;j++){
				double tmpdist=distance(a[i],b[j]);
				if(ret>tmpdist){
					ret=tmpdist;
				}
			}
		}
		
		return ret;
	}

• • 完全連結法
    • クラスタ間の距離は、構成要素同士ペアの距離の最大値で定義する
      • 

public static double distCompleteLinkage(double[][] a,double[][] b){
		double ret=distance(a[0],b[0]);
		for(int i=0;i<a.length;i++){
			for(int j=0;j<b.length;j++){
				double tmpdist=distance(a[i],b[j]);
				if(ret<tmpdist){
					ret=tmpdist;
				}
			}
		}
		
		return ret;
	}

• • ウォード法
    • クラスタ間の距離は、クラスタでくくったときに、クラスタ内平方和が、クラスタにくくる前のペアの平方和の和より増えるが、この増分で定義する
      • 
      • 

public static double distWard(double[][] a, double[][] b){
		double ret = 0;
		double secondMa=secondMoment(a);
		double secondMb=secondMoment(b);
		double[][] aplusb=new double[a.length+b.length][a[0].length];
		for(int i=0;i<a.length;i++){
			for(int j=0;j<a[i].length;j++){
				aplusb[i][j]=a[i][j];
			}
		}
		for(int i=0;i<b.length;i++){
			for(int j=0;j<b[i].length;j++){
				aplusb[i+a.length][j]=b[i][j];
			}
		}
		double secondMaplusb=secondMoment(aplusb);
		ret=secondMaplusb-secondMa-secondMb;
		
		return ret;
	}
	public static double secondMoment(double[][] a){
		double ret = 0;
		double[] center = centerWithoutWeight(a);
		for(int i=0;i<a.length;i++){
			for(int j=0;j<a[i].length;j++){
				ret += (a[i][j]-center[j])*(a[i][j]-center[j]);
			}
		}
		
		return ret;
	}
public static double[] centerWithoutWeight(double[][] a){
		double[] ret = new double[a[0].length];
		int sum=a.length;
		for(int i=0;i<a.length;i++){
			//sum+=weight[i];
			for(int j=0;j<a[i].length;j++){
				
				ret[j]+=a[i][j];
			}
		}
		for(int i=0;i<ret.length;i++){
			ret[i]/=sum;
		}
		return ret;
	}
	public static double[] centerWithWeight(double[][] a, double[] weight){
		double[] ret = new double[a[0].length];
		int sum=0;
		for(int i=0;i<a.length;i++){
			sum+=weight[i];
			for(int j=0;j<a[i].length;j++){
				
				ret[j]+=weight[i]*a[i][j];
			}
		}
		for(int i=0;i<ret.length;i++){
			ret[i]/=sum;
		}
		return ret;
	}

• • 重心法
    • クラスタ間の距離は、重心間の距離の自乗で定義する
      • 

public static double distCentroid(double[][] a, double[][] b){
		double ret = 0;
		double[] centera=centerWithoutWeight(a);
		double[] centerb=centerWithoutWeight(b);
		ret = distance(centera,centerb);
		ret *=ret;
		return ret;
	}

• • メディアン法
    • 重心法と同様だが、重心は、クラスタ化の進行に伴って、併合後のクラスタの重心として、併合前の２クラスタの中点として定義する点が異なる
      • 
• Rでの解析
  • hclust関数
    • 参考
    • こちらも参考