种混合属性数据的聚类算法
摘 要： 提出一种基于属性分解的随机分组的改进方法，以提高聚类算法的稳定性和适用性。实验仿真结果表明，改进算法具有很好的稳定性和应用性。
关键词： 聚类；混合数据；分类属性
所谓聚类，就是将物理或抽象对象的集合构成为由类似的对象组成多个类或簇的过程。由聚类所生成的簇是一组数据对象的集合，同一簇中的数据对象尽可能相似，不同簇中的数据对象尽可能相异[1]。聚类算法在许多领域获得了广泛应用[2]，但是，由于在实际应用中，许多数据集不仅包含数值属性的数据，同时也包含如地图颜色、几何纹理等分类属性的数据。因此使得基于传统的欧式距离划分的聚类算法难以适用于混合属性数据集的要求。为此各研究学者就此问题进行了深入地研究和探讨。
MacQueen 所提出的k-means 方法[3]是最早、也是最简单的聚类方法，但是该方法只能对数值属性的对象集进行聚类，无法对分类属性和混合型属性的对象集进行聚类。Huang 提出的k-modes 算法和k-prototypes 算法[4]推广了k-means 方法，使之可以对分类属性和混合型属性的数据集进行聚类。同时陈宁、陈安、周龙骧进一步提出了模糊k-prototypes 算法，并利用引进模糊聚类算法来提高聚类结果的准确性[5]。
上述方法在聚类过程中，均利用分类型属性简单匹配相异度，将分类型属性的数据转化为数值型属性数据间的基于距离的计算问题，从而解决了对混合属性数据集的聚类问题。但是上述方法在对分类属性数据和混合型属性数据进行聚类时，总会存在一些如聚类结果的随机性和不稳定性等缺点，甚至有时会出现空聚类[6-7]现象。
为此，本文在k-prototypes 算法的基础上进行改进，利用随机分组的思想动态地选取初始原型点，同时对分类属性数据采取属性分解的方法进行处理，从而提高算法的稳定性和适用性，使聚类结果更加理想化。
1 相关观念
聚类是将数据对象分成类或簇的过程，使同一个簇中的对象之间具有很高的相似度，而不同簇中的对象高度相异[2]。其中对象间的相异度度量用来表示对象间的相异程度，代价函数用来表示对象间的相似程度。
2 算法的改进
k-modes 算法和k-prototypes 算法在聚类混合属性数据时，对初值有明显的依赖，导致聚类结果不理想，甚至出现聚类空集的现象。因此本文在原有算法的基础上进一步改进，利用随机分组确定初始原型的方法，然后对随机分组得到的初始原型进一步加工处理，使得聚类结果对初值的依赖性有所降低，从而使聚类结果更合理、稳定，达到改进算法的目的。
2.1 分类属性处理算法
假定数据对象x 是具有m 维属性的数据对象，其中含有m1个数值型数据和m2个分类型属性。那么，可以直观地将数据对象x 看成分别有m1维数值属性和m2维分类属性组成，其中m2维分类属性又可以分别看成由多维数据值组成。例如：表2中的分类型属性“渠道”可以看成是由“直接”、“间接”2维分类数据值组成的；分类型属性“语义范畴”可以看成是由“植物”、“语言”2维分类数据组成的。在计算中，分别将分类型属性看成是由多维的分类属性数据值组成的。
对象1的分解原型表示为：
1={2，{0(直接) ，1(间接)}，{1(植物) ，0(语言)}}；
对象2的分解原型表示为：
2={2，{1(直接) ，0(间接)}，{0(植物) ，1(语言)}}；
对象3的分解原型表示为：
3={3，{1(直接) ，0(间接)}，{1(植物) ，0(语言)}}；
对象4的分解原型表示为：
4={3，{0(直接) ，1(间接)}，{1(植物) ，0(语言)}}；
对象5的原型表示为：
5={2，{1(直接) ，0(间接)}，{0(植物) ，1(语言)}}； 则对象1，2，5组成的聚类Q1的分解原型可以表示为： Q1={2，{2/3(直接) ，1/3(间接)}，{0(植物) ，3/3(语言)}}； 则对象3，4组成的聚类Q2的分解原型可以表示为：
Q2={2，{1/2(直接) ，1/2(间接)}，{2/2(植物) ，0(语言)}}；
然后利用式(2)计算对象与聚类之间的距离，得到其中的最小距离。通过这种方式，可以有效地避免在分类属性中出现频率少的属性值丢失的现象，从而得到更合理的聚类的结果。
2.2 随机分组算法
随机分组算法的基本原理是依据需要聚类的个数k 和数据集中所包含数据的个数n 。将总数为n 的数据集划分为count=n/k组，然后从count 组中分别选择数据对象k 次，构成k 个聚类的初始原型值。
算法流程：
(1)分组数据集。已知数据集X={x1，x2，…，xn}是包含n 个数据对象的集合。依据数据集中数据个数n 和需要聚类的个数k ，将整个数据集分组成为count=n/k组，即数据集X={[x1，x2，…，xk]，[xk+1，…，x2k]，…}。如果分组后数据集中还有剩余的对象未分配，则将剩余的对象分配到任意组中，本文选择将其分配到第一个分组中。
(2)随机获得一个初始点。将数据集分组成为子数据集后，依次从count 个子数据集中随机选择一个数据对象，形成由count 个数据对象组成的新的子数据集。将这个新的子数据集中的所有m1个数值型属性中的值利用式(5)计算平均值作为初始点的对应的数值型属性的值，对于分类型属性的值，则利用2.1节的分类属性数据处理方法进行处理后作为初始值的对应分类型属性的值。
3) 重复步骤(2)k次，得到k 个初始点，作为聚类分析的k 个原型点。
2.3 聚类算法描述
改进算法的流程和k-prototypes 算法的流程基本相同。具体算法描述如下：
(1)将数据集中的每一个数据对象按照2.1节中的分类属性数据值的处理方法进行处理。
(2)利用随机分组算法获得k 个初始原型点，每一个初始原型点对应一个聚类原型初值。
(3)将数据集中剩下的任一个对象分配给一个聚类，根据相异度度量的距离公式计算的结果确定一个聚类的原型与它最近，分配给该聚类后，将聚类的原型更新。
4) 在所有的数据对象全部分配给聚类之后，重新计算该数据对象与当前每一个聚类之间的距离。如果发现一个数据对象它的最近原型属于另一个聚类而不是当前的聚类，将该数据对象重新分配给另一个聚类并更新两个聚类的原型。
(5)重复算法(4)，直到数据集中的所有数据对象再没有对象变更聚类为止。
3 实验分析
一般评价聚类结果均是采用“误分率”等统计方法。在本文的仿真实验中，通过将本文的改进算法和k-prototypes 算法进行比较，采用错误的分类数目来评价聚类算法性能。错误的分类数目，即对算法的聚类结果和数据集本身进行比较，聚类结果中没有被正确分配到相应聚类的数据对象的数目。本文通过两个数据集进行实验。
(1)采用UCI 数据集中的abalone 数据集进行测试。该数据集包括涉及生活领域的8个类别的4 177个数据对象，其中含有1个分类型属性，1个整数型属性和6个实数型属性。分类属性数据对象中含有1 528个记录为F(父) 值，1 307个记录为M(母) 值，还有1 342个记录为I(未成年人) 值。
如图1所示，在改变聚类个数的情况下，通过比较两种算法的聚类结果的错误分类数目可知，改进算法在一定程度上比原有算法的稳定性更高。
(2)采用UCI 数据集中的post-operative patient数据集。该数据集中还有涉及生活领域的9个类别的90个数据对象，其中还有8个分类属性和1个整数型属性，包含有2个记录为I(病人送加护病房) ，24个对象为S(病人准备回家) ，64个对象为A(病人送去普通病房) 。 由图2可知，在分类属性较多的混合属性数据集中，改进算法的稳定性仍在一定程度上优于原型算法，保证了改进算法对于混合属性数据聚类结果的稳定性和有效性。
对于数值型数据和分类型数据的混合数值的聚类，目前虽然有一些算法，如k-modes 算法和k-prototypes 算法。但是这些算法在选择聚类初始点时过于随机，导致聚类结果不理想。因此本文提出了一种基于分类属性数据分解的随机分组选择初始原型的改进算法。但是在本文的改进算法中，仍然存在一些缺点，例如，聚类个数仍是人为确定，不能动态确定适合数据集合理的聚类的个数。因此，为了使改进算法的适应性和稳定性更好，同时使数据集的聚类结果与输入数据对象的顺序无关，动态确定聚类合理的聚类个数是今后的研究重点。 参考文献
[1] 王欣，徐腾飞，唐连章，等.SQL Server2005数据挖掘实例分析[M].北京，中国水利水电出版社，2008.
[2] Han Jiawei， KAMBER M. Data mining concepts and techniques[M]. 北京：机械工业出版社，2001.
[3] CHRISTOPHER J， BURGES C. A tutorial on support vector machines for pattern recognition[J]. Data Mining and knowledge Discovery， 1998： 2(2)： 121-167.
[4] VAPNIK V N. An overview of statistical learning theory[J]. IEEE Trans on Neural Network ， 1999； 10(5)：988-999.
[5] 张文生，王珏. 利用支持向量机构造函数型连接网络的研究[J].计算机科学，2001，28(5)：172-177.
[6] 赵立江，黄永青. 混合属性数据聚类初始点选择的改进[J].广西师范大学学报：自然科学报，2007，25(4)：102-105.
[7] 林培俊，王宇. 对类属性和混合属性数据聚类的一种有效地算法[J].计算机工程与应用，2004，40(1)：190-191.
种混合属性数据的聚类算法
摘 要： 提出一种基于属性分解的随机分组的改进方法，以提高聚类算法的稳定性和适用性。实验仿真结果表明，改进算法具有很好的稳定性和应用性。
关键词： 聚类；混合数据；分类属性
所谓聚类，就是将物理或抽象对象的集合构成为由类似的对象组成多个类或簇的过程。由聚类所生成的簇是一组数据对象的集合，同一簇中的数据对象尽可能相似，不同簇中的数据对象尽可能相异[1]。聚类算法在许多领域获得了广泛应用[2]，但是，由于在实际应用中，许多数据集不仅包含数值属性的数据，同时也包含如地图颜色、几何纹理等分类属性的数据。因此使得基于传统的欧式距离划分的聚类算法难以适用于混合属性数据集的要求。为此各研究学者就此问题进行了深入地研究和探讨。
MacQueen 所提出的k-means 方法[3]是最早、也是最简单的聚类方法，但是该方法只能对数值属性的对象集进行聚类，无法对分类属性和混合型属性的对象集进行聚类。Huang 提出的k-modes 算法和k-prototypes 算法[4]推广了k-means 方法，使之可以对分类属性和混合型属性的数据集进行聚类。同时陈宁、陈安、周龙骧进一步提出了模糊k-prototypes 算法，并利用引进模糊聚类算法来提高聚类结果的准确性[5]。
上述方法在聚类过程中，均利用分类型属性简单匹配相异度，将分类型属性的数据转化为数值型属性数据间的基于距离的计算问题，从而解决了对混合属性数据集的聚类问题。但是上述方法在对分类属性数据和混合型属性数据进行聚类时，总会存在一些如聚类结果的随机性和不稳定性等缺点，甚至有时会出现空聚类[6-7]现象。
为此，本文在k-prototypes 算法的基础上进行改进，利用随机分组的思想动态地选取初始原型点，同时对分类属性数据采取属性分解的方法进行处理，从而提高算法的稳定性和适用性，使聚类结果更加理想化。
1 相关观念
聚类是将数据对象分成类或簇的过程，使同一个簇中的对象之间具有很高的相似度，而不同簇中的对象高度相异[2]。其中对象间的相异度度量用来表示对象间的相异程度，代价函数用来表示对象间的相似程度。
2 算法的改进
k-modes 算法和k-prototypes 算法在聚类混合属性数据时，对初值有明显的依赖，导致聚类结果不理想，甚至出现聚类空集的现象。因此本文在原有算法的基础上进一步改进，利用随机分组确定初始原型的方法，然后对随机分组得到的初始原型进一步加工处理，使得聚类结果对初值的依赖性有所降低，从而使聚类结果更合理、稳定，达到改进算法的目的。
2.1 分类属性处理算法
假定数据对象x 是具有m 维属性的数据对象，其中含有m1个数值型数据和m2个分类型属性。那么，可以直观地将数据对象x 看成分别有m1维数值属性和m2维分类属性组成，其中m2维分类属性又可以分别看成由多维数据值组成。例如：表2中的分类型属性“渠道”可以看成是由“直接”、“间接”2维分类数据值组成的；分类型属性“语义范畴”可以看成是由“植物”、“语言”2维分类数据组成的。在计算中，分别将分类型属性看成是由多维的分类属性数据值组成的。
对象1的分解原型表示为：
1={2，{0(直接) ，1(间接)}，{1(植物) ，0(语言)}}；
对象2的分解原型表示为：
2={2，{1(直接) ，0(间接)}，{0(植物) ，1(语言)}}；
对象3的分解原型表示为：
3={3，{1(直接) ，0(间接)}，{1(植物) ，0(语言)}}；
对象4的分解原型表示为：
4={3，{0(直接) ，1(间接)}，{1(植物) ，0(语言)}}；
对象5的原型表示为：
5={2，{1(直接) ，0(间接)}，{0(植物) ，1(语言)}}； 则对象1，2，5组成的聚类Q1的分解原型可以表示为： Q1={2，{2/3(直接) ，1/3(间接)}，{0(植物) ，3/3(语言)}}； 则对象3，4组成的聚类Q2的分解原型可以表示为：
Q2={2，{1/2(直接) ，1/2(间接)}，{2/2(植物) ，0(语言)}}；
然后利用式(2)计算对象与聚类之间的距离，得到其中的最小距离。通过这种方式，可以有效地避免在分类属性中出现频率少的属性值丢失的现象，从而得到更合理的聚类的结果。
2.2 随机分组算法
随机分组算法的基本原理是依据需要聚类的个数k 和数据集中所包含数据的个数n 。将总数为n 的数据集划分为count=n/k组，然后从count 组中分别选择数据对象k 次，构成k 个聚类的初始原型值。
算法流程：
(1)分组数据集。已知数据集X={x1，x2，…，xn}是包含n 个数据对象的集合。依据数据集中数据个数n 和需要聚类的个数k ，将整个数据集分组成为count=n/k组，即数据集X={[x1，x2，…，xk]，[xk+1，…，x2k]，…}。如果分组后数据集中还有剩余的对象未分配，则将剩余的对象分配到任意组中，本文选择将其分配到第一个分组中。
(2)随机获得一个初始点。将数据集分组成为子数据集后，依次从count 个子数据集中随机选择一个数据对象，形成由count 个数据对象组成的新的子数据集。将这个新的子数据集中的所有m1个数值型属性中的值利用式(5)计算平均值作为初始点的对应的数值型属性的值，对于分类型属性的值，则利用2.1节的分类属性数据处理方法进行处理后作为初始值的对应分类型属性的值。
3) 重复步骤(2)k次，得到k 个初始点，作为聚类分析的k 个原型点。
2.3 聚类算法描述
改进算法的流程和k-prototypes 算法的流程基本相同。具体算法描述如下：
(1)将数据集中的每一个数据对象按照2.1节中的分类属性数据值的处理方法进行处理。
(2)利用随机分组算法获得k 个初始原型点，每一个初始原型点对应一个聚类原型初值。
(3)将数据集中剩下的任一个对象分配给一个聚类，根据相异度度量的距离公式计算的结果确定一个聚类的原型与它最近，分配给该聚类后，将聚类的原型更新。
4) 在所有的数据对象全部分配给聚类之后，重新计算该数据对象与当前每一个聚类之间的距离。如果发现一个数据对象它的最近原型属于另一个聚类而不是当前的聚类，将该数据对象重新分配给另一个聚类并更新两个聚类的原型。
(5)重复算法(4)，直到数据集中的所有数据对象再没有对象变更聚类为止。
3 实验分析
一般评价聚类结果均是采用“误分率”等统计方法。在本文的仿真实验中，通过将本文的改进算法和k-prototypes 算法进行比较，采用错误的分类数目来评价聚类算法性能。错误的分类数目，即对算法的聚类结果和数据集本身进行比较，聚类结果中没有被正确分配到相应聚类的数据对象的数目。本文通过两个数据集进行实验。
(1)采用UCI 数据集中的abalone 数据集进行测试。该数据集包括涉及生活领域的8个类别的4 177个数据对象，其中含有1个分类型属性，1个整数型属性和6个实数型属性。分类属性数据对象中含有1 528个记录为F(父) 值，1 307个记录为M(母) 值，还有1 342个记录为I(未成年人) 值。
如图1所示，在改变聚类个数的情况下，通过比较两种算法的聚类结果的错误分类数目可知，改进算法在一定程度上比原有算法的稳定性更高。
(2)采用UCI 数据集中的post-operative patient数据集。该数据集中还有涉及生活领域的9个类别的90个数据对象，其中还有8个分类属性和1个整数型属性，包含有2个记录为I(病人送加护病房) ，24个对象为S(病人准备回家) ，64个对象为A(病人送去普通病房) 。 由图2可知，在分类属性较多的混合属性数据集中，改进算法的稳定性仍在一定程度上优于原型算法，保证了改进算法对于混合属性数据聚类结果的稳定性和有效性。
对于数值型数据和分类型数据的混合数值的聚类，目前虽然有一些算法，如k-modes 算法和k-prototypes 算法。但是这些算法在选择聚类初始点时过于随机，导致聚类结果不理想。因此本文提出了一种基于分类属性数据分解的随机分组选择初始原型的改进算法。但是在本文的改进算法中，仍然存在一些缺点，例如，聚类个数仍是人为确定，不能动态确定适合数据集合理的聚类的个数。因此，为了使改进算法的适应性和稳定性更好，同时使数据集的聚类结果与输入数据对象的顺序无关，动态确定聚类合理的聚类个数是今后的研究重点。 参考文献
[1] 王欣，徐腾飞，唐连章，等.SQL Server2005数据挖掘实例分析[M].北京，中国水利水电出版社，2008.
[2] Han Jiawei， KAMBER M. Data mining concepts and techniques[M]. 北京：机械工业出版社，2001.
[3] CHRISTOPHER J， BURGES C. A tutorial on support vector machines for pattern recognition[J]. Data Mining and knowledge Discovery， 1998： 2(2)： 121-167.
[4] VAPNIK V N. An overview of statistical learning theory[J]. IEEE Trans on Neural Network ， 1999； 10(5)：988-999.
[5] 张文生，王珏. 利用支持向量机构造函数型连接网络的研究[J].计算机科学，2001，28(5)：172-177.
[6] 赵立江，黄永青. 混合属性数据聚类初始点选择的改进[J].广西师范大学学报：自然科学报，2007，25(4)：102-105.
[7] 林培俊，王宇. 对类属性和混合属性数据聚类的一种有效地算法[J].计算机工程与应用，2004，40(1)：190-191.