Scaling EM (Expectation Maximization) Clustering to Large Databases
Scaling EM (Expectation Maximization) Clustering to Large Databases
复制标题
DOI：
--
复制
发表时间：
1998-11
期刊：
影响因子：
--
通讯作者：
P. Bradley;U. Fayyad;Cory Reina
中科院分区：
文献类型：
--
作者：
P. Bradley;U. Fayyad;Cory Reina
实用的统计聚类算法通常以迭代细化优化过程为中心，以计算最大化数据拟合的局部最优聚类解决方案。这些算法通常需要多次数据库扫描才能收敛，并且在每次扫描中它们都需要访问数据表中的每条记录。对于大型数据库，扫描成本变得异常昂贵。我们提出了期望最大化（EM）算法的可扩展实现。数据库社区专注于基于距离的聚类方案，并且已经开发了用于对数值或分类数据进行聚类的方法。与基于距离的算法（例如 K-Means）不同，EM 为基础数据源构建适当的统计模型，并自然地推广到包含离散值和连续值数据的集群数据库。可扩展方法基于算法所需的基本统计数据的分解：识别可压缩的数据区域和必须在内存中维护的区域。该方法在有限的主内存缓冲区的范围内运行，并且最多需要一次数据库扫描。根据主内存缓冲区的大小以及当前聚类模型与数据的拟合程度，尽可能保留数据分辨率。我们扩展了该方法以有效地同时更新多个模型。计算测试表明，这种可扩展的方案优于基于采样的方法——将传统内存中实现“扩展”到大型数据库的直接替代方案。 1 预备知识和动机 数据聚类在许多领域都很重要，包括数据挖掘[FPSU96]、统计数据分析[KR89,BR93]、压缩[ZRL97]和矢量量化[DH73]。应用包括数据分析和建模 [FDW97、FHS96]、图像分割、营销、欺诈检测、预测建模、数据汇总、一般数据报告任务、数据清理和探索性数据分析 [B*96]。集群是关键的数据挖掘步骤，在大型数据库上执行此任务至关重要。将 EM 聚类扩展到大型数据库 Bradley、Fayyad 和 Reina 2 聚类的一般观点将其置于密度估计的框架中 [S86、S92、A73]。聚类可以被视为识别数据源的密集区域。概率密度函数的有效表示是混合模型，它断言数据是对应于 k 个聚类的 k 个单独分量密度的组合。基本上，问题是这样的：给定数据记录（观察），识别数据中的一组 k 个总体，并提供每个总体的模型（密度分布）。由于该模型假设人口的混合，因此通常称为混合模型。期望最大化 (EM) 算法 [DLR77、CS96] 是一种有效且流行的技术，用于估计混合模型参数或将模型拟合到数据库。 EM 算法迭代地细化初始聚类模型以更好地拟合数据，并终止于局部最优解或基础聚类标准的鞍点 [DLR77，B95]。目标函数是给定模型的数据的对数似然，衡量概率模型对数据的拟合程度。其他类似的迭代细化聚类方法包括流行的 K-Means 类型算法 [M67、DH73、F90、BMS97、SI84]。虽然这些方法在数据库和数据挖掘文献 [NH94、ZRL97、BFR98] 中受到关注，但它们计算正确的数据统计模型的能力有限。 K-Mean 算法最小化簇中数据记录之间的欧氏距离平方和与簇的均值向量。该分配标准隐含地假设聚类由位于 k 个聚类均值 [BB95, B95] 处的球形高斯分布表示。由于 K 均值算法利用欧几里得度量，因此它不能推广到离散或分类数据的聚类问题。 K 均值算法还使用隶属函数，将每个数据记录精确地分配到一个簇。这一严格的标准不允许集群中数据记录的成员身份存在不确定性。混合模型框架放宽了这些假设。由于混合模型的概率性质，任意形状的簇（即非球形等）可以通过选择合适的分量密度函数（例如泊松、非球形高斯等）来有效表示。通过将离散数据分布与这些属性相关联（例如多项式、二项式等），可以类似地处理分类或离散数据。考虑一个简单的示例，其中的数据包含两个属性：年龄和收入。人们可以选择将数据建模为单个集群，并报告数据记录的平均年龄为 41 岁，平均收入为 26,000 美元/年（具有相关方差）。然而，这可能具有相当的欺骗性和信息量。数据可能是工作人员、退休人员以及 Bradley、Fayyad 和 Reina 3 个孩子的混合数据。信息更丰富的摘要可能会识别这些子集或集群，并报告集群参数。这些结果如表 1.1 所示： 表 1.1：按细分“名称”（未给出）划分的样本数据摘要 规模 平均年龄 平均收入 “工作” 45% 38 $45K “退休” 30% 72 $20K “儿童” 20% 12 $0
Practical statistical clustering algorithms typically center upon an iterative refinement optimization procedure to compute a locally optimal clustering solution that maximizes the fit to data. These algorithms typically require many database scans to converge, and within each scan they require the access to every record in the data table. For large databases, the scans become prohibitively expensive. We present a scalable implementation of the Expectation-Maximization (EM) algorithm. The database community has focused on distance-based clustering schemes and methods have been developed to cluster either numerical or categorical data. Unlike distancebased algorithms (such as K-Means), EM constructs proper statistical models of the underlying data source and naturally generalizes to cluster databases containing both discrete-valued and continuous-valued data. The scalable method is based on a decomposition of the basic statistics the algorithm needs: identifying regions of the data that are compressible and regions that must be maintained in memory. The approach operates within the confines of a limited main memory buffer and requires at most a single database scan. Data resolution is preserved to the extent possible based upon the size of the main memory buffer and the fit of the current clustering model to the data. We extend the method to efficiently update multiple models simultaneously. Computational tests indicate that this scalable scheme outperforms sampling-based approaches – the straightforward alternatives to “scaling” traditional in-memory implementations to large databases. 1 Preliminaries and Motivation Data clustering is important in many fields, including data mining [FPSU96], statistical data analysis [KR89,BR93], compression [ZRL97], and vector quantization [DH73]. Applications include data analysis and modeling [FDW97,FHS96], image segmentation, marketing, fraud detection, predictive modeling, data summarization, general data reporting tasks, data cleaning and exploratory data analysis [B*96]. Clustering is a crucial data mining step and performing this task over large databases is essential. Scaling EM Clustering to Large Databases Bradley, Fayyad, and Reina 2 A general view of clustering places it in the framework of density estimation [S86, S92, A73]. Clustering can be viewed as identifying the dense regions of the data source. An efficient representation of the probability density function is the mixture model, which asserts that the data is a combination of k individual component densities, corresponding to the k clusters. Basically, the problem is this: given data records (observations), identify a set of k populations in the data, and provide a model (density distribution) of each of the populations. Since the model assumes a mixture of populations, it is often referred to as a mixture model. The Expectation-Maximization (EM) algorithm [DLR77, CS96] is an effective and popular technique for estimating the mixture model parameters or fitting the model to the database. The EM algorithm iteratively refines an initial cluster model to better fit the data and terminates at a solution which is locally optimal or a saddle point of the underlying clustering criterion [DLR77, B95]. The objective function is log-likelihood of the data given the model measuring how well the probabilistic model fits the data. Other similar iterative refinement clustering methods include the popular K-Means-type algorithms [M67,DH73,F90,BMS97,SI84]. While these approaches have received attention in the database and data mining literature [NH94,ZRL97,BFR98], they are limited in their ability to compute correct statistical models of the data. The K-Mean algorithm minimizes the sum of squared Euclidean distances of between data records in a cluster and the cluster’s mean vector. This assignment criterion implicitly assumes that clusters are represented by spherical Gaussian distributions located at the k cluster means [BB95, B95]. Since the K-Mean algorithm utilizes the Euclidean metric, it does not generalize to the problem of clustering discrete or categorical data. The K-Mean algorithm also uses a membership function which assigns each data record to exactly one cluster. This harsh criteria does not allow for uncertainty in the membership of a data record in a cluster. The mixture model framework relaxes these assumptions. Due to the probabilistic nature of the mixture model, arbitrary shaped clusters (i.e. non-spherical, etc.) can be effectively represented by the choice of suitable component density functions (e.g. Poission, non-spherical Gaussians, etc.). Categorical or discrete data is similarly handled by associating discrete data distribution over these attributes (e.g. Mutinomial, Binomial, etc.). Consider a simple example with data consisting of 2 attributes: age and income. One may choose to model the data as a single cluster and report that average age over the data records is 41 years and an average income is $26K/year (with associated variances). However, this may be rather deceptive and uninformative. The data may be a mixture of working people, retired people, and Scaling EM Clustering to Large Databases Bradley, Fayyad, and Reina 3 children. A more informative summary might identify these subsets or clusters, and report the cluster parameters. Such results are shown in Table 1.1: Table 1.1: Sample data summary by segment “name” (not given) Size Average Age Average Income “working” 45% 38 $45K “retired” 30% 72 $20K “children” 20% 12 $0