12.45 k-modes 型算法的类中心表示与收 敛性分析
目前分类型数据的类中心表示方式有单值和多值两种。1998 年，Huang [4] 提出了 k-modes 算法，用 modes 来表示类中心，选择出现频率最高的值代表类，强调主流的属性值代表类，其他值为噪音，是典型的单值表示方式。单值表示方式由于简单易实现且聚类优化模型有很好的数学性质，保证了求解算法的收敛性，但它并不能充分刻画类的特性。San et al [17] 提出了多值表示类的方式，并应用于分类型数据的聚类。在该方法中，类是由每个属性上所有属性值来表示，并通过属性值在类内出现频率作为权值反映它对该类的代表能力，强调所有的值都对类有代表性，仅仅是代表能力不同。Kim et al [18] 将其扩展，提出了模糊 modes，并将其用于模糊 k-modes聚类算法。Lee 和 Pedrycz 提出了一种通用的多值类表示方式[19] ，类是由每个属性上属性值频率较高的前几个值来表示，通过属性值在类内出现频率作为权值反映它对该类的代表能力，强调部分的值被用于代表类，其他值为噪；其他基于频率的类中心表示方式都可以看作该方法的特例。
多值代表方法克服了单值代表方法的缺点，但却带来聚类算法的迭代收敛性无法保证，同时现有聚类优化算法仅在多值类表示方式退化为单值类表示方式时，才能保证算法的收敛性。为了解决这一问题，Bai et al [20] 研究了类的表示方式与聚类优化算法的收敛性关系，分析了现有多值类代表的聚类优化算法不能收敛的原因，构建了基于正则项的聚类优化模型，从根本上解决了多值类表示 k-modes型聚类算法的收敛性问题。
