聚类分析之k-prototype算法解析

K-prototype是处理混合属性聚类的典型算法。继承Kmean算法和Kmode算法的思想。并且加入了描述数据簇的原型和混合属性数据之间的相异度计算公式。

常规定义：X={X1，X2，X3………Xn}表示数据集（含有n个数据），其中数据有m个属性。

 数据Xi={X11，X12，X13……….X1m} 

Aj表示属性j  

dom(Aj) 表示属性j的值域：   对于数值属性，值域dom(Aj)表示是取值范围；对于分类属性，值域dom(Aj)表示集合

Xij 表示数据I 的第j个属性。

同样，数据Xi也可表示为

数据总共有m个属性，不妨设前p个属性为数值属性(r代表)，后m-r个属性为分类属性（c代表）

K-prototype算法是设定了一个目标函数，类似于kmean的SSE（误差平方和），不断迭代，直到目标函数值不变。

同时，K-prototype算法提出了混合属性簇的原型，我们可以理解原型就是数值属性聚类的质心。混合属性中存在数值属性和分类属性，其原型的定义是数值属性原型用属性中所有属性取值值的均值，分列属性原型是分类属性中选取属性值取值频率最高的属性。合起来就是原型。

相异度距离: 一般来说，数值属性的相异度一般选用欧式距离，在K-prototype算法中混合属性的相异度分为属性属性和分类属性分开求，然后相加。

对于分类属性：我们使用海明威距离，即属性值相同，为0 ；属性值不同，为1。

对于分类属性:

对于数值属性：

       计算数值属性对应的欧式距离

 则数据 和簇的距离（相异度）为：

其中 前P个数值属性，后m个是分类属性， 是簇Q的原型的j属性 ，u是分类属性的权重因子

其K-prototype的目标函数是：

目标函数这个定义对于算法来说很重要，都是作者自己想出来的。然后进行实验验证的。看论文最难学的就是目标函数。人家想出来的很牛，但是自己却没有能力想出来，还是得多看论文。

有了相异度和原型的定义。

算法的步骤是：

输入：聚类簇的个数k， 权重因子

输出：产生好的聚类。

步骤：从数据集中随机选取k个对象作为初始的k个簇的原型

遍历数据集中的每一个数据，计算数据与k个簇的相异度。然后将该数据分配到相异度最小的对应的簇中，每次分配完毕后，更新簇的原型

然后计算目标函数，然后对比目标函数值是否改变，循环直到目标函数值不在变化为止。