grid_cluster_analysis.cpp

这是一个GPS相关的程序

			if( pCluster->asInt(iElement) < 0 || pCluster->asInt(iElement) >= nCluster )
			{
				pCluster->Set_Value(iElement, iElement % nCluster);
			}

			nClusterElements++;
		}
		else
		{
			pCluster->Set_Value(iElement, -1);
		}
	}

	if( Parameters("UPDATEVIEW")->asBool() )
	{
		DataObject_Update(pCluster, 0, nCluster, true);
	}


	//-----------------------------------------------------
	// Hauptschleife der Iteration

	for(nPasses=1, bContinue=true; bContinue && Process_Get_Okay(false); nPasses++)
	{
		//-------------------------------------------------
		for(iCluster=0; iCluster<nCluster; iCluster++)
		{
			Variances[iCluster]	= 0;
			nMembers [iCluster]	= 0;

			for(iGrid=0; iGrid<nGrids; iGrid++)
			{
				Centroids[iCluster][iGrid]	= 0;
			}
		}

		//-------------------------------------------------
		for(iElement=0; iElement<nElements; iElement++)
		{
			if( pCluster->asInt(iElement) >= 0 )
			{
				iCluster	= pCluster->asInt(iElement);
				nMembers[iCluster]++;

				for(iGrid=0; iGrid<nGrids; iGrid++)
				{
					Centroids[iCluster][iGrid]	+= Grids[iGrid]->asDouble(iElement);
				}
			}
		}

		//-------------------------------------------------
		for(iCluster=0; iCluster<nCluster; iCluster++)
		{
			d		= nMembers[iCluster] > 0 ? 1.0 / (double)nMembers[iCluster] : 0;

			for(iGrid=0; iGrid<nGrids; iGrid++)
			{
				Centroids[iCluster][iGrid]	*= d;
			}
		}


		//-------------------------------------------------
		// Sift and Shift..

		SP		= 0;
		nShifts	= 0;

		for(iElement=0; iElement<nElements && bContinue; iElement++)
		{
			if( !(iElement % (nElements / 100)) && !Set_Progress(iElement, nElements) )
			{
				bContinue	= false;
			}

			if( pCluster->asInt(iElement) >= 0 )
			{
				minVariance	= -1;

				for(iCluster=0; iCluster<nCluster; iCluster++)
				{
					Variance	= 0;

					for(iGrid=0; iGrid<nGrids; iGrid++)
					{
						d			= Centroids[iCluster][iGrid] - Grids[iGrid]->asDouble(iElement);
						Variance	+= d * d;
					}

					if( minVariance<0 || Variance<minVariance )
					{
						minVariance	= Variance;
						minCluster	= iCluster;
					}
				}

				if( pCluster->asInt(iElement) != minCluster )
				{
					pCluster->Set_Value(iElement, minCluster);
					nShifts++;
				}

				SP						+= minVariance;
				Variances[minCluster]	+= minVariance;
			}
		}


		//-------------------------------------------------

		if( nShifts == 0 || (SP_Last >= 0 && SP >= SP_Last) )
		{
			bContinue	= false;
		}

		Process_Set_Text(CSG_String::Format(SG_T("%s: %d >> %s %f"),
			_TL("pass")		, nPasses,
			_TL("change")	, SP_Last < 0.0 ? SP : SP_Last - SP
		));

		SP_Last		= SP;

		if( Parameters("UPDATEVIEW")->asBool() )
		{
			DataObject_Update(pCluster, 0, nCluster);	// Update_Output();
		}
	}

	nElements	= nClusterElements;

	return( SP );
}


///////////////////////////////////////////////////////////
//														 //
//					Hill-Climbing						 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------
double CGrid_Cluster_Analysis::HillClimbing(long &nElements, int nCluster)
{
	//-----------------------------------------------------
	// Variablen...

	bool	bContinue;
	int		iElement, iGrid, iCluster, jCluster, kCluster, nClusterElements, noShift, nPasses;
	double	d, e, n_iK, n_jK, V, VMin, V1, V2, SP, SP_Last	= -1;


	//-----------------------------------------------------

	for(iCluster=0; iCluster<nCluster; iCluster++)
	{
		Variances[iCluster]	= 0;
		nMembers [iCluster]	= 0;

		for(iGrid=0; iGrid<nGrids; iGrid++)
		{
			Centroids[iCluster][iGrid]	= 0;
		}
	}


	//-----------------------------------------------------
	// Anfangspartition (Standard falls nicht vorgegeben)

	for(iElement=0, nClusterElements=0; iElement<nElements; iElement++)
	{
		for(iGrid=0, bContinue=true; iGrid<nGrids && bContinue; iGrid++)
		{
			if( Grids[iGrid]->is_NoData(iElement) )
			{
				bContinue	= false;
			}
		}

		if( bContinue )
		{
			if( pCluster->asInt(iElement) < 0 || pCluster->asInt(iElement) >= nCluster )
			{
				pCluster->Set_Value(iElement, iElement % nCluster);
			}

			nClusterElements++;

			iCluster	= pCluster->asInt(iElement);

			nMembers[iCluster]++;

			V			= 0.0;

			for(iGrid=0; iGrid<nGrids; iGrid++)
			{
				d							 = Grids[iGrid]->asDouble(iElement);
				Centroids[iCluster][iGrid]	+= d;
				V							+= d * d;
			}

			Variances[iCluster]	+= V;
		}
		else
		{
			pCluster->Set_Value(iElement, -1);
		}
	}


	//-----------------------------------------------------

	SP	= 0.0;

	for(iCluster=0; iCluster<nCluster; iCluster++)
	{
		d	= nMembers[iCluster] != 0 ? 1.0 / (double)nMembers[iCluster] : 0;
		V	= 0.0;

		for(iGrid=0; iGrid<nGrids; iGrid++)
		{
			Centroids[iCluster][iGrid]	*= d;
			e							 = Centroids[iCluster][iGrid];
			V							+= e * e;
		}

		Variances[iCluster]	-= nMembers [iCluster] * V;
		SP					+= Variances[iCluster];
	}

	if( Parameters("UPDATEVIEW")->asBool() )
	{
		DataObject_Update(pCluster, 0, nCluster, true);
	}


	//-----------------------------------------------------
	// Hauptschleife der Iteration

	noShift		= 0;

	for(nPasses=1, bContinue=true; bContinue && Process_Get_Okay(false); nPasses++)
	{
		//-------------------------------------------------
		for(iElement=0; iElement<nElements && bContinue; iElement++)
		{
			if( !(iElement % (nElements / 100)) && !Set_Progress(iElement, nElements) )
			{
				bContinue	= false;
			}

			if( pCluster->asInt(iElement) >= 0 )
			{
				if( noShift++ >= nElements )
				{
					bContinue	= false;
				}
				else
				{

					//---------------------------------------------
					iCluster	= pCluster->asInt(iElement);

					if( nMembers[iCluster] > 1 )
					{
						V	= 0.0;

						for(iGrid=0; iGrid<nGrids; iGrid++)
						{
							d	= Centroids[iCluster][iGrid] - Grids[iGrid]->asDouble(iElement);
							V	+= d * d;
						}

						n_iK	= nMembers[iCluster];
						V1		= V * n_iK / (n_iK - 1.0);
						VMin	= -1.0;

						//-----------------------------------------
						// Bestimme Gruppe iCluster mit evtl. groesster Verbesserung...

						for(jCluster=0; jCluster<nCluster; jCluster++)
						{
							if( jCluster != iCluster )
							{
								V	= 0.0;

								for(iGrid=0; iGrid<nGrids; iGrid++)
								{
									d	= Centroids[jCluster][iGrid] - Grids[iGrid]->asDouble(iElement);
									V	+= d * d;
								}

								n_jK	= nMembers[jCluster];
								V2		= V * n_jK / (n_jK + 1.0);

								if( VMin < 0 || V2 < VMin )
								{
									VMin		= V2;
									kCluster	= jCluster;
								}
							}
						}


						//-----------------------------------------
						// Gruppenwechsel und Neuberechnung der Gruppencentroide...

						if( VMin >= 0 && VMin < V1 )
						{
							noShift				= 0;
							Variances[iCluster]	-= V1;
							Variances[kCluster]	+= VMin;
							SP					= SP - V1 + VMin;
							V1					= 1.0 / (n_iK - 1.0);
							n_jK				= nMembers[kCluster];
							V2					= 1.0 / (n_jK + 1.0);

							for(iGrid=0; iGrid<nGrids; iGrid++)
							{
								d							= Grids[iGrid]->asDouble(iElement);
								Centroids[iCluster][iGrid]	= (n_iK * Centroids[iCluster][iGrid] - d) * V1;
								Centroids[kCluster][iGrid]	= (n_jK * Centroids[kCluster][iGrid] + d) * V2;
							}

							pCluster->Set_Value(iElement, kCluster);

							nMembers[iCluster]--;
							nMembers[kCluster]++;
						}
					}
				}
			}
		}

		Process_Set_Text(CSG_String::Format(SG_T("%s: %d >> %s %f"),
			_TL("pass")		, nPasses,
			_TL("change")	, SP_Last < 0.0 ? SP : SP_Last - SP
		));

		SP_Last		= SP;

		if( Parameters("UPDATEVIEW")->asBool() )
		{
			DataObject_Update(pCluster, 0, nCluster);	// Update_Output();
		}
	}

	nElements	= nClusterElements;

	return( SP );
}


///////////////////////////////////////////////////////////
//														 //
//														 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------