Then explain what you paralleized, and what decomposition you used(task,data, bo
ID: 3743123 • Letter: T
Question
Then explain what you paralleized, and what decomposition you used(task,data, both and in what order) The K-Means Clustering Method Given k, the k-means algorithm is implemented in four steps: Partition objects into k nonempty subsets - Compute seed points as the centroids of the clusters of the current partitioning (the centroid is the center, i.e., mean point, of the cluster) Assign each object to the cluster with the nearest seed point Go back to Step 2, stop when the assignment does not change
Explanation / Answer
Answer: See the pseudo code below:
----------------------------------
//pseducode for k-means clustering alogorithm in C++
Algorithm kmeans(K:int,totalPoints:int,MAXITER:int,Points:vector)
{
//primary terminating condition
if (K > totalPoints)
return;
Clusters[K][]; //vector of arrays to store clusters
//select K values(not duplicates) as centroids
NumIter:int;
Changed:bool;
NumIter = 0; //initialize counter
Changed = TRUE;
while(NumIter < MAXITER && Changed == TRUE)
{
i = 0; //counter for cluster
closestCluster = -1;
minDist = 0;
for(point j in Points)
{
for(cluster i in Clusters)
{
dist = CalculateDistance(Clusters[i],Points[j]);
//check for closest cluster
if (dist < minDist)
{
minDist = dist;
closestCluster = i;
}
}
Clusters[i][j] = Points[j]; //assign point to closest cluster
}
for(cluster i in Clusters)
{
UpdateCluster(Clusters[i],Points in Clusters[i],i);
Changed = TRUE;
}
NumIter++;
}
}
Algorithm CalculateDistance(cluster,point)
{
return sqrt((xi1-xj1)+(xi2-xj2)+...);
}
Algorithm UpdateClusters(Cluster,PointsBelongingToCluster,totalPoints,clusterIndex)
{
for(j = 0;j<p;j++) //p is number of features in each point
{
featureTotal = Sum of features f[clusterIndex][j];
Cluster[j]=featureTotal/totalPoints;
}
}
--------------------------------------
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.