Abstract: To address the difficulty of defining a meaningful distance measure for categorical data clustering, a new categorical data clustering algorithm was proposed based on Bayesian probability estimation. Firstly, a probability model with automatic attribute-weighting was proposed, in which each categorical attribute is assigned an individual weight to indicate its importance for clustering. Secondly, a clustering objective function was derived using maximum likelihood estimation and Bayesian transformation, then a partitioning algorithm was proposed to optimize the objective function which groups data according to the weighted likelihood between objects and clusters instead of the pairwise distances. Thirdly, an expression for estimating the attribute weights was derived, indicating that the weight should be inversely proportional to the entropy of category distribution. The experiments were conducted on some real datasets and a synthetic dataset. The results show that the proposed algorithm yields higher clustering accuracy than the existing distance-based algorithms, achieving 5%-48% improvements on the Bioinformatics data with meaningful attribute-weighting results for the categorical attributes.

Key words: data clustering, categorical attribute, attribute weighting, Bayesian clustering, probability model

摘要： 针对类属型数据聚类中对象间距离函数定义的困难问题，提出一种基于贝叶斯概率估计的类属数据聚类算法。首先，提出一种属性加权的概率模型，在这个模型中每个类属属性被赋予一个反映其重要性的权重；其次，经过贝叶斯公式的变换，定义了基于最大似然估计的聚类优化目标函数，并提出了一种基于划分的聚类算法，该算法不再依赖于对象间的距离，而是根据对象与数据集划分间的加权似然进行聚类；第三，推导了计算属性权重的表达式，得出了类属型属性权重与其符号分布的信息熵成反比的结论。在实际数据和合成数据集上进行了实验，结果表明，与基于距离的现有聚类算法相比，所提算法提高了聚类精度，特别是在生物信息学数据上取得了5%~48%的提升幅度，并可以获得有实际意义的属性加权结果。

关键词: 数据聚类, 类属型属性, 属性加权, 贝叶斯聚类, 概率模型