A modified k-means clustering algorithm with Mahalanobis distance for clustering incomplete data sets /
Iresh Granada Moreno.
- 2009
- 94 leaves.
Thesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2009
Cluster analysis is an art of finding grounds in data in such a way that objects in the same group are similar to each other, whereas objects in different groups are as dissimilar as possible. The most commonly used clustering algorithm is the K-means with Euclidean distance. However, such distance function neglects the covariance among the variables in calculating distances. To account for this issue, the Mahalanobis distance is used. However, occurrence of missing values is inevitable and clustering such kind of data set is impossible. Existing method such as case deletion and mean imputation for treating missing values are very prone to producing erroneous conclusions by imputing unreliable estimates and significantly reducing the data set. To avoid these problems, modifications of the K-means clustering algorithm's two most essential elements, allocation and representation, were made. Allocation, which was defined by the Mahalanobis distance, was modified to compute distances between two vectors and to compute variances with some unknown values. The representation which was defined by arithmetic mean was modified to estimate mean where there are one or more unknown values of the certain attribute. The proposed algorithm was applied to Iris and Bupa incomplete data sets simulated under MCAR and MAR assumptions with different levels of missing values. Under MAR, case deletion has the highest cluster recovery at 5% of the samples. However, it was totally outperformed by the proposed algorithm as the occurrences of missing values in the sample increased. In general, the modified k-means with Mahalanobis distance has outdone the rest of the algorithms when applied to both data sets.