C-means clustering using CUDA on GPU
Summary:
The computational demands for multivariate clustering are increasing rapidly, and therefore processing large data sets is time consuming on a single CPU. To address the computational demands, we implemented the cmeans clustering algorithm, using the NVIDIA's CUDA's framework and the latest GPU devices on the Delta machine.
Fuzzy C-Means Clustering
Fuzzy c-means is an algorithm of clustering which allows one element to belong to two or more clusters with different probability. This method is frequently used in multivariate clustering. This algorithm is based on minimization of the following objective function:
Here, M is a real number greater than 1, N is the number of elements, Uij is the value of membership of Xi in cluster Cj, xi is the ith of d-dimensional measured data, cj is the d-dimension center of the cluster, and ||Xi-Cj|| is any norm expressing the similarity between any measured data and the center. Fuzzy partitioning is performed through an iterative optimization of the objective function shown above. Within each iteration, the algorithm updates the membership uij and the cluster centers cj by:
This iteration will stop when
, where 'e' is a termination criterion between 0 and 1, and k represents the iteration steps.
Algorithm of CUDA C-means:
1) Copy data to GPU
2) DistanceMatrix kernel
3) MembershipMatrix kernel
4) UpdateCenters kernel, copy partial centers to host from GPUs
5) ClusterSizes kernel, copy cluster sizes to host from each GPU
6) Aggregate partial cluster centers and reduce
10) Compute difference between current cluster centers and previous iteration.
11) Compute cluster distance and memberships using final centers.
CUDA kernels of C-means program:
1) DistanceMatrix
2) MembershipMatrix
3) UpdateCetners
4) ClusterSizes
CUDA C-means performance on Delta:
Figure 1: C-means performance using GPU and CPU
Reference:
[1] http://en.wikipedia.org/wiki/Cluster_analysis
[2] Scalable Data Clustering using GPU Clusters, Andrew Pangborn, Gregor von Laszewski
The computational demands for multivariate clustering are increasing rapidly, and therefore processing large data sets is time consuming on a single CPU. To address the computational demands, we implemented the cmeans clustering algorithm, using the NVIDIA's CUDA's framework and the latest GPU devices on the Delta machine.
Fuzzy C-Means Clustering
Fuzzy c-means is an algorithm of clustering which allows one element to belong to two or more clusters with different probability. This method is frequently used in multivariate clustering. This algorithm is based on minimization of the following objective function:
Here, M is a real number greater than 1, N is the number of elements, Uij is the value of membership of Xi in cluster Cj, xi is the ith of d-dimensional measured data, cj is the d-dimension center of the cluster, and ||Xi-Cj|| is any norm expressing the similarity between any measured data and the center. Fuzzy partitioning is performed through an iterative optimization of the objective function shown above. Within each iteration, the algorithm updates the membership uij and the cluster centers cj by:
This iteration will stop when
, where 'e' is a termination criterion between 0 and 1, and k represents the iteration steps.Algorithm of CUDA C-means:
1) Copy data to GPU
2) DistanceMatrix kernel
3) MembershipMatrix kernel
4) UpdateCenters kernel, copy partial centers to host from GPUs
5) ClusterSizes kernel, copy cluster sizes to host from each GPU
6) Aggregate partial cluster centers and reduce
10) Compute difference between current cluster centers and previous iteration.
11) Compute cluster distance and memberships using final centers.
CUDA kernels of C-means program:
1) DistanceMatrix
2) MembershipMatrix
3) UpdateCetners
4) ClusterSizes
CUDA C-means performance on Delta:
Figure 1: C-means performance using GPU and CPU
Reference:
[1] http://en.wikipedia.org/wiki/Cluster_analysis
[2] Scalable Data Clustering using GPU Clusters, Andrew Pangborn, Gregor von Laszewski
(1 vote)
Futuregrid is a resource provider for