聚类分析之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（误差平⽅和），不断迭代，直到⽬标函数
函数prototype
值不变。
同时，K-prototype算法提出了混合属性簇的原型，我们可以理解原型就是数值属性聚类的质⼼。混合属性中存在数值属性和分类属性，其原型的定义是数值属性原型⽤属性中所有属性取值值的均值，分列属性原型是分类属性中选取属性值取值频率最⾼的属性。合起来就是原型。
相异度距离: ⼀般来说，数值属性的相异度⼀般选⽤欧式距离，在K-prototype算法中混合属性的相异度分为属性属性和分类属性分开求，然后相加。
对于分类属性：我们使⽤海明威距离，即属性值相同，为0 ；属性值不同，为1。
对于分类属性:
对于数值属性：
计算数值属性对应的欧式距离
则数据和簇的距离（相异度）为：
其中前P个数值属性，后m个是分类属性，是簇Q的原型的j属性，u是分类属性的权重因⼦
其K-prototype的⽬标函数是：
⽬标函数这个定义对于算法来说很重要，都是作者⾃⼰想出来的。然后进⾏实验验证的。看论⽂最难学的就是⽬标函数。⼈家想出来的很⽜，但是⾃⼰却没有能⼒想出来，还是得多看论⽂。
有了相异度和原型的定义。
算法的步骤是：
输⼊：聚类簇的个数k，权重因⼦
输出：产⽣好的聚类。
步骤：从数据集中随机选取k个对象作为初始的k个簇的原型
遍历数据集中的每⼀个数据，计算数据与k个簇的相异度。然后将该数据分配到相异度最⼩的对应的簇中，每次分配完毕后，更新簇的原型
然后计算⽬标函数，然后对⽐⽬标函数值是否改变，循环直到⽬标函数值不在变化为⽌。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。