Distance calculation between clusters by Lance-Williams Updating Formula. Lance-Williams更新式によるクラスタ間の距離計算

LanceWilliamsUpdatingFormula.cpp

#include <cmath>

// クラスタ C1 = C1a∪C1b のとき、クラスタC1とC2の距離をC2とC1a, C1bの距離情報から求めることができる。
// 計算時間はクラスタのメンバ数に依存しない。
// 参考 http://ibisforest.org/index.php?Lance-Williams%20updating%20formula

//! Lance-Williams Updating Formula
/*!
    @param[in] dist_1a2 distance between C1a and C2
    @param[in] dist_1b2 distance between C1b and C2
    @param[in] dist_1a1b distance between C1a and C1b
    @param[in] num_1a number of members in C1a
    @param[in] num_1b number of members in C1b
    @param[in] num_2 number of members in C2
    @return distance between C1 and C2 (C1 = C1a ∪ C1b)
*/
float updateFormula(
	float dist_1a2,
	float dist_1b2,
	float dist_1a1b,
	float alpha_a,
	float alpha_b,
	float beta,
	float gamma
) const
{
	return ( alpha_a * dist_1a2 ) + ( alpha_b * dist_1b2 ) + ( beta * dist_1a1b ) + ( gamma * abs( dist_1a2 - dist_1b2 ) );
}


//! Nearest Method (single linkage method)
float calcFormulaNearest(
	float dist_1a2,
	float dist_1b2,
	float dist_1a1b,
	unsigned int num_1a,
	unsigned int num_1b,
	unsigned int num_2
) const
{
	return updateFormula( dist_1a2, dist_1b2, dist_1a1b, 0.5f, 0.5f, 0.0f, (-0.5f) );
}


//! Furthest Method (complete linkage method)
float calcFormulaFurthest(
	float dist_1a2,
	float dist_1b2,
	float dist_1a1b,
	unsigned int num_1a,
	unsigned int num_1b,
	unsigned int num_2
) const
{
	return updateFormula( dist_1a2, dist_1b2, dist_1a1b, 0.5f, 0.5f, 0.0f, 0.5f );
}


//! Group Average Method
float calcFormulaGroupAvg(
	float dist_1a2,
	float dist_1b2,
	float dist_1a1b,
	unsigned int num_1a,
	unsigned int num_1b,
	unsigned int num_2
) const
{
	float alpha_a = static_cast< float >( num_1a ) / ( num_1a + num_1b );
	float alpha_b = static_cast< float >( num_1b ) / ( num_1a + num_1b );
	return updateFormula( dist_1a2, dist_1b2, dist_1a1b, alpha_a, alpha_b, 0.0f, 0.0f );
}


//! Ward Method
float calcFormulaWard(
	float dist_1a2,
	float dist_1b2,
	float dist_1a1b,
	unsigned int num_1a,
	unsigned int num_1b,
	unsigned int num_2
) const
{
	unsigned int n = num_1a + num_1b + num_2;
	float alpha_a = static_cast< float >( num_1a + num_2 ) / n;
	float alpha_b = static_cast< float >( num_1b + num_2 ) / n;
	float beta = ( -1.0f ) * num_2 / n;
	return updateFormula( dist_1a2, dist_1b2, dist_1a1b, alpha_a, alpha_b, beta, 0.0f );
}


//! Centroid Method
float calcFormulaCentroid(
	float dist_1a2,
	float dist_1b2,
	float dist_1a1b,
	unsigned int num_1a,
	unsigned int num_1b,
	unsigned int num_2
) const
{
	unsigned int n1 = num_1a + num_1b;
	float alpha_a = static_cast< float >( num_1a ) / n1;
	float alpha_b = static_cast< float >( num_1b ) / n1;
	float beta = ( -1.0f ) * ( num_1a * num_1b ) / ( n1 * n1 );
	return updateFormula( dist_1a2, dist_1b2, dist_1a1b, alpha_a, alpha_b, beta, 0.0f );
}


//! Median Method
float calcFormulaMedian(
	float dist_1a2,
	float dist_1b2,
	float dist_1a1b,
	unsigned int num_1a,
	unsigned int num_1b,
	unsigned int num_2
) const
{
	return updateFormula( dist_1a2, dist_1b2, dist_1a1b, 0.5f, 0.5f, -0.25f, 0.0f );
}