P1: SUD
Data Mining and Knowledge Discovery KL657-03-Huang October 27, 1998 12:59
Data Mining and Knowledge Discovery 2, 283–304 (1998)
c
° 1998 Kluwer Academic Publishers. Manufactured in The Netherlands.
Extensions to the k-Means Algorithm for Clustering
Large Data Sets with Categorical Values
ZHEXUE HUANG huang@mip.com.au
ACSys CRC, CSIRO Mathematical and Information Sciences, GPO Box 664, Canberra, ACT 2601, Australia
Abstract. The k-means algorithm is well knownforitsefficiencyinclusteringlarge data sets. However, working
only on numeric values prohibits it from being used to cluster real world data containing categorical values. In
this paper we present two algorithms which extend the k-means algorithm to categorical domains and domains
with mixed numeric and categorical values. The k-modes algorithm uses a simple matching dissimilarity measure
to deal with categorical objects, replaces the means of clusters with modes, and uses a frequency-based method to
update modes in the clustering process to minimise the clustering cost function. With these extensionsthek-modes
algorithm enables the clustering of categorical data in a fashion similar to k-means. The k-prototypes algorithm,
through the definition of a combined dissimilarity measure, further integrates the k-means and k-modes algorithms
to allow for clustering objects described by mixed numeric and categorical attributes. We use the well known
soybean disease and credit approval data sets to demonstrate the clustering performance of the two algorithms.
Our experiments on two real world data sets with half a million objects each show that the two algorithms are
efficient when clustering large data sets, which is critical to data mining applications.
Keywords: data mining, cluster analysis, clustering algorithms, categorical data
1. Introduction
Partitioning a set of objects in databases into homogeneous groups or clusters (Klosgen and
Zytkow, 1996) is a fundamental operation in data mining. It is useful in a number of tasks,
suchasclassification (unsupervised)(Cormack, 1971), aggregationandsegmentation(IBM,
1996) or dissection (Cormack, 1971). For example, by partitioning objects into clusters,
interesting object groups may be discovered, such as the groups of motor insurance policy
holders with a high average claim cost (Williams and Huang, 1996), or the groups of clients
in a banking database having a heavy investment in real estate.
Clustering (Anderberg, 1973; Jain and Dubes, 1988; Kaufman and Rousseeuw, 1990) is
a popular approach to implementing the partitioning operation. Clustering methods par-
tition a set of objects into clusters such that objects in the same cluster are more similar
to each other than objects in different clusters according to some defined criteria. Statisti-
cal clustering methods (Anderberg, 1973; Everitt, 1974; Kaufman and Rousseeuw, 1990)
partition objects according to some (dis)similarity measures, whereas conceptual clustering
methods cluster objects according to the concepts objects carry (Michalski and Stepp, 1983;
Fisher, 1987).
Current address: MIP, level 3, 60 City Rd, Southbank Vic 3006, Melbourne, Australia.
剩余21页未读，继续阅读
资源评论
