subclust.cpp

减聚类的类代码

		{
			maxPoint[i] = m_pX[m_nDimension*maxPotIndex + i];
		}
//		maxPoint[0] = m_pX[2*maxPotIndex];
//		maxPoint[1] = m_pX[2*maxPotIndex+1];

		maxPotRatio = maxPotVal/refPotVal;

		if(maxPotRatio > acceptRatio)
		{
			// the new peak value is significant, accept it
			findMore = 1;
		}
		else if( maxPotRatio > rejectRatio)
		{
			// accept this data point only if it achieves a good balance between having
			// a reasonable potential and being far from all existing cluster centers
			for(i=0; i<m_nClusters; i++)
			{
				for(j=0; j<m_nDimension; j++)
				{
					dxElse[j] = (maxPoint[j] - m_pCent[m_nDimension*i+j]) * accumMultp[j];
				}

//				dxElse[0] = (maxPoint[0] - m_pCent[2*i])*accumMultp[0];
//				dxElse[1] = (maxPoint[1] - m_pCent[2*i+1])*accumMultp[1];
				
				dxSq = 0;				
				for(j=0; j<m_nDimension; j++)
				{
					dxSq += dxElse[j]*dxElse[j];
				}
//				dxSq = dxElse[0]*dxElse[0] + dxElse[1]*dxElse[1];

				if(minDistSq <0 || dxSq < minDistSq)
				{
					minDistSq = dxSq;
				}

			}
			
			minDist = sqrt(minDistSq);
			if(maxPotRatio + minDist >= 1)
			{
				// tentatively accept this data point as a cluster center
				findMore = 1;
			}
			else
			{
				// remove this point from further consideration, and continue
				findMore = 2;
			}
		}

		if(findMore == 1)
		{
			// 将maxPoint加入到centers中
			for(j=0; j<m_nDimension; j++)
			{
				m_pCent[m_nClusters*m_nDimension + j] = maxPoint[j];
			}
//			m_pCent[m_nClusters*2] = maxPoint[0];
//			m_pCent[m_nClusters*2+1] = maxPoint[1];

			// 标记中心的位置
			m_pClusterCenterLabel[m_nClusters] = maxPotIndex;
			m_nClusters ++;
			
			// subtract potential from data points near the new cluster center
			for(j=0; j<m_nPoints; j++)
			{
				for(k=0; k<m_nDimension; k++)
				{
					dx[k] = (maxPoint[k]-m_pX[m_nDimension*j+k])*sqshMultp[k];
				}
				
//				dx[2*j] = (maxPoint[0]-m_pX[2*j])*sqshMultp[0];
//				dx[2*j+1] = (maxPoint[1]-m_pX[2*j+1])*sqshMultp[1];
				
				tmpsum = 0;
				for(k=0; k<m_nDimension; k++)
				{
					tmpsum += pow(dx[k],2);
				}
//				pPotVals[j] -= maxPotVal*exp(-4*(dx[2*j]*dx[2*j]+dx[2*j+1]*dx[2*j+1]));
				
				pPotVals[j] -= maxPotVal*exp(-4*tmpsum);
				if(pPotVals[j]<0)
					pPotVals[j] = 0;
			}
			// find the data point with the highest remaining potential
			maxPotIndex = FindMax(pPotVals,maxPotVal);
		}
		else if(findMore == 2)
		{
			// Set the potential value of the false center to 0
			pPotVals[maxPotIndex] = 0;
			// find the next highest potential as the new xk and re-test
			maxPotIndex = FindMax(pPotVals,maxPotVal);
		}
	}
	
	// Scale all points back to values in the original range
	for(j=0; j<m_nPoints; j++)
	{
		for(k=0; k<m_nDimension; k++)
		{
			m_pX[m_nDimension*j+k] = m_pX[m_nDimension*j+k]*(maxX[k]-minX[k]) + minX[k];
		}

//		m_pX[2*j] = m_pX[2*j]*(maxX[0]-minX[0]) + minX[0];
//		m_pX[2*j+1] = m_pX[2*j+1]*(maxX[1]-minX[1]) + minX[1];
	}
	// Scale the cluster centers from the normalized values back to values in
	// the original range
	for(j=0; j<m_nClusters; j++)
	{
		for(k=0; k<m_nDimension; k++)
		{
			m_pCent[m_nDimension*j+k] = m_pCent[m_nDimension*j+k]*(maxX[k]-minX[k]) + minX[k];
		}

//		m_pCent[2*j] = m_pCent[2*j]*(maxX[0]-minX[0]) + minX[0];
//		m_pCent[2*j+1] = m_pCent[2*j+1]*(maxX[1]-minX[1]) + minX[1];
	}
	//输出聚类中心矩阵
	m_mClusters = Double_Matrix(m_nClusters,m_nDimension,m_pCent);

	//创建类标记
	CreateLabel();

	//释放内存
	SAFE_DELETE_ARRAY(maxPoint);
	SAFE_DELETE_ARRAY(dxElse);
	SAFE_DELETE_ARRAY(minX);
	SAFE_DELETE_ARRAY(maxX);
	SAFE_DELETE_ARRAY(dx);
	SAFE_DELETE_ARRAY(pPotVals);
	SAFE_DELETE_ARRAY(m_pClusterCenterLabel);
	SAFE_DELETE_ARRAY(m_pCent);
	//计算sigmas
	//...
}

/////////////////////////////////////////////////////////////////////////
//
// Function: CreateLabel()
// Parameter:
//
// Return:
//   
// Description: 为每个样本点写类标记, 标记存储在pLabel中
//				对任一个样本点计算与每个类中心的距离，选
//				取最小距离的类中心作为自己所属类的类中心
// Modification:
//			05/24/2005	jg.yuan		add to m_nDimension		
////////////////////////////////////////////////////////////////////////

void CSubclust::CreateLabel()
{
	if(m_pLabel == NULL)
	{
		return;
	}
	
	int i,j,k;
	double minDist = 0xffffff;
	int minFlag = -1;
	
	// 为距离计算分配空间
	double* pDistVals = NULL;
	try{
		pDistVals = new double[m_nClusters];
	}
	catch (CMemoryException* pME) {
		pME->ReportError();
	}
	ASSERT(pDistVals);
	memset(pDistVals,0,sizeof(double)*m_nClusters);
	
	double tmpsum = 0;
	for(i=0; i<m_nPoints; i++)
	{
		// 计算第i个点与所有中心的距离
		// 同时记录与之距离最小的中心位置
		minDist = 0xffffff;
		for(j=0; j<m_nClusters; j++)
		{
			tmpsum = 0;
			for(k=0; k<m_nDimension; k++)
			{
				tmpsum += pow(m_pX[m_nDimension*i+k] - m_pCent[m_nDimension*j+k], 2);
			}
			pDistVals[j] = sqrt( tmpsum );
			if(minDist > pDistVals[j])
			{
				minDist = pDistVals[j];
				minFlag = j;
			}
		}
		//if( minDist <= DIST_THRESHOLD)
		{
			m_pLabel[i] = minFlag;
		}
	}
	
	SAFE_DELETE_ARRAY(pDistVals);
}

/////////////////////////////////////////////////////////////////////////
//
// Function: ComputeAvgCenter()
// Parameter:
//
// Return: 成功返回true，否则返回false
//   
// Description: 根据已经计算出来的点的类标记，求每个类的平均中心
// 		
////////////////////////////////////////////////////////////////////////

bool CSubclust::ComputeAvgCenter()
{
	if(m_nClusters <= 0 || m_pLabel == NULL || m_pX == NULL)
		return false;
	
	int j = 0;
	int k = 0;
	
	// 初始化存储区
	if(m_pAvgCenter != NULL)
	{
		memset(m_pAvgCenter,0,sizeof(double)*m_nClusters*m_nDimension);
	}

	// 每一个类别的计数器
	int* pClusterCnt = NULL;
	try{
		pClusterCnt = new int[m_nClusters];
	}
	catch (CMemoryException* pME) {
		pME->ReportError();
	}
	if(pClusterCnt == NULL)
	{
		return false;
	}
	memset(pClusterCnt,0,sizeof(int)*m_nClusters);
	
	// 统计累加和
	for(j=0; j<m_nPoints; j++)
	{
		for(k=0; k<m_nDimension; k++)
		{
			m_pAvgCenter[m_nDimension*m_pLabel[j]] += m_pX[m_nDimension*j+k];
		}

//		m_pAvgCenter[2*m_pLabel[j]] += m_pX[2*j];
//		m_pAvgCenter[2*m_pLabel[j]+1] += m_pX[2*j+1];
		
		pClusterCnt[m_pLabel[j]] ++;
	}
	// 平均
	for(j=0; j<m_nClusters; j++)
	{
		for(k=0; k<m_nDimension; k++)
		{
			m_pAvgCenter[m_nDimension*j+k] /= pClusterCnt[j];
		}

//		m_pAvgCenter[2*j] /= pClusterCnt[j];
//		m_pAvgCenter[2*j+1] /= pClusterCnt[j];
	}
	
	SAFE_DELETE_ARRAY(pClusterCnt);
	return true;	
}

/////////////////////////////////////////////////////////////////////////
//
// Function: GetClusters()
// Parameter:
//
// Return:	相减聚类所产生的类中心数组指针
//   
// Description: 相减聚类,同时标记每个点的类标记
// 		
////////////////////////////////////////////////////////////////////////

//double* CSubclust::GetClusters()
//{
//	return m_pCent;
//}

/////////////////////////////////////////////////////////////////////////
//
// Function: GetClustersMatrix()
// Parameter:
//
// Return:	相减聚类所产生的类中心矩阵形式
//   
// Description: 相减聚类,同时标记每个点的类标记
// 		
////////////////////////////////////////////////////////////////////////

Double_Matrix CSubclust::GetClustersMatrix()
{
	return m_mClusters;
}

/////////////////////////////////////////////////////////////////////////
//
// Function: GetClustersNum()
// Parameter:
//
// Return:	相减聚类产生的类中心个数
//   
// Description: 
// 		
////////////////////////////////////////////////////////////////////////

int CSubclust::GetClustersNum()
{
	return m_nClusters;
}

/////////////////////////////////////////////////////////////////////////
//
// Function: GetClusterCenterLabel()
// Parameter:
//
// Return:	相减聚类产生的类中心在样本点集中的位置
//   
// Description: 
// 		
////////////////////////////////////////////////////////////////////////

//int* CSubclust::GetClusterCenterLabel()
//{
//	return m_pClusterCenterLabel;
//}

/////////////////////////////////////////////////////////////////////////
//
// Function: GetPointLabel()
// Parameter:
//
// Return:	样本点类标记数组指针（暂时没用）
//   
// Description: 
// 		
////////////////////////////////////////////////////////////////////////

//int* CSubclust::GetPointLabel()
//{
//	return m_pLabel;
//}