聚类分析研究的挑战性问题范文

本站小编为你精心准备了聚类分析研究的挑战性问题参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

《广东工业大学学报》2014年第二期

聚类分析是一个富有挑战性的任务，尤其是在大数据时代，随着微博、微信等新型社会化媒体的出现，不同来源的数据一方面使数据呈现出TB级／天的增长趋势，另一方面使数据的类型变得更加多样化，使数据的结构变得更为繁杂，这些变化给聚类分析研究带来了新的困难和挑战，具体挑战包括处理多样化数据类型的能力、处理超高维数据的能力、处理不均衡数据的能力、聚类算法的可拓展能力和聚类效果评价的指标选择问题．这些挑战有的是自聚类算法产生以来就已存在，有的则是新时代产生的新问题．

1处理多样化数据类型的能力

随着信息技术的发展，数据的类型变得越来越复杂，同一个研究对象中可能会同时包含着多种不同类型的数据．针对不同的数据类型，研究者们提出了不同的聚类算法．不过在聚类算法产生初期，人们最先关注的是比较容易理解和处理的数值型数据．早在1967年MacQueen就针对数值型数据集提出了非常经典的Kmeans聚类算法，该算法以欧氏距离作为数值属性差异性的度量方法［13］．Kmeans算法实现简单，计算速度快，处理效率高，但不能处理分类型数据．对于分类属性的数据，通常存在两种不同的处理方式，一种是将分类属性转换成多个取值为0和1的数值属性，再利用Kmeans算法进行处理；另一种是由Huang，JoshuaZhexue教授提出的适用于纯分类属性的Kmodes算法，该算法采用匹配差异法度量分类属性之间的差异程度，但这种表示难以准确反映出类中对象的取值情况，导致差异性度量不准确，并且当某个属性取值频度最大的属性值多于一个时，mode不唯一，不同的mode选择可能得到完全相反的结论．事实上，在许多实际应用中，需要处理的数据中往往既含有数值型属性又包含分类型属性，此时使用Kmeans或Kmodes算法都不能有效地解决问题．针对该问题，Huang结合Kmeans和Kmodes算法提出了能够处理混合型属性的Kprototypes聚类算法，但是该方法存在着与Kmodes算法一样的缺点．随后，蒋盛益针对Kprototypes聚类算法的不足，以统计频度作为分类型属性的差异性度量指标并提出了Ksummary算法，该算法很好地提高了聚类效率，但是时间开销较Kprototypes有所增加．为了进一步提高聚类效率，在混合属性差异性度量的基础上又提出了一种基于最小距离原则的聚类算法（也称一趟聚类算法），其基本思想就是将对象依次被并入到与其差异度最小的簇中．一趟聚类算法只需扫描数据集一遍，具有近似线性的时间复杂度、聚类精度高的优点，可拓展性高，适用于划分大规模数据集．所以在处理大数据集时，将一趟聚类算法与其他聚类算法结合而形成的混合聚类算法或聚类融合算法则可以提高聚类效率和质量．另外，谢岳山等为解决聚类融合算法对混合属性数据处理效果不佳的问题，提出了一种基于图论的加权聚类融合算法，在聚类的基础上利用预设的融合函数对数据对象进行权重赋值，同时通过设置各个数据对间边的权重来确定数据之间的关系，并得到加权最近邻图，然后再用图论的方法进行聚类．实验表明，该算法的聚类精度和稳定性优于其他聚类融合算法．上述算法都是将一个对象划分到一个簇中，属于硬聚类．但是在实际领域中，有许多对象往往同时属于多个类，所以目前有许多研究工作对上述算法进行改进形成软聚类以解决实际应用中的现实问题．尽管Kprototypes、Ksummary和一趟聚类算法能够处理混合型属性，但是它们在两种不同类型属性差异性度量和比较方面的有效性还值得商榷．换句话说，在特征空间上，分类属性的取值频度与数值属性的绝对偏差在理论上是不能直接进行大小比较的．因此，如何改进不同类型属性差异度的可比性或提出更有效的混合属性差异度度量方法是未来研究的一个重要挑战．

2处理超高维数据的能力

在高维空间中聚类数据对象是非常有挑战性的，因为数据可能分布非常稀疏，而且会高度偏斜．例如，“双十一购物狂欢节”的背后隐藏着商品品牌销售量和卖家客户数量分布的不平衡性以及用户购买数据的稀疏性．传统聚类算法在处理低维数据时能够表现出较好的性能，但对于高维数据，由于属性数量过多引起的稀疏性问题和属性差异性度量的偏差问题，这往往会导致聚类效果变差．维度灾难是一个非常普遍的现象，若直接采用传统聚类算法往往不能得到所期望的结果．为了更好地满足现实需求，研究者们提出了许多针对高维数据的聚类方法．综观当前研究成果，在面对高维数据时通常都是先对特征空间进行处理，采用特征变换或特征选择的方式来降低特征维度以提高聚类算法的性能．特征变换是根据合适的方法寻求与高维数据等价的低维空间表示，通过将原始特征空间进行变换，重新生成一个维数更小、各维度之间的独立性更强的空间，从而使降维之后的数据所包含的信息与降维之前尽可能地相同或相近［28］．最常用的特征变换方法有小波变换、PCA、LPP和NPE［31］．特征选择是在不同任务需求下选取那些符合要求且彼此之间关联程度较小的最优特征子集的过程，其目的是通过剔除与任务需求不相关和弱相关的特征以降低维度，从而提高学习算法的效率和性能．特征选择算法在寻找最优特征子集时，需要对特征之间的相关性进行评价．对于相同类型的特征一般采用线性相关系数、信息增益、互信息、可分性等指标来度量特征的相关性．而对于混合类型特征的相关性度量而言，通常采用的方法是将连续特征进行离散化，将混合特征之间的相关度计算转化为两个离散特征之间相关性的度量问题．离散化策略一方面会增加额外的时间开销，另一方面也可能会造成信息丢失，从而降低数据的处理效率与质量．为避免这些问题，文献［35］用均方差性质提出了一种混合特征相关性度量方法CMMF，但是如何更有效地将混合特征相关度与同类型特征间相关度进行比较也是当前需要解决的一个重要问题．特征选择的另一种形式是子空间聚类，利用聚类算法在不同子空间中搜索簇群．目前用于处理高维数据的方法大多采用软子空间聚类，其基本思想是：在聚类时将类别看成是模糊的，即每个对象在一定程度上可以看成属于某一簇，在一定程度上又可以看成属于另一个簇，通过对数据集中的各类别赋予不同的特征权重向量，并以此来表示聚类过程中各维特征对此类别贡献的大小．在聚类过程中，不同的特征在不同的类别上有不同的贡献，因此不同的特征在不同类别有不同的特征权重向量，从而形成了若干个“软子空间”．典型软子空间聚类算法子空间方法多采用划分类型的聚类算法，但是这类方法一直存在着聚类个数难以确定的问题．另外，在处理混合类型数据时，子空间聚类该如何更好地分配权重向量也是一个非常难以解决的问题．

3处理不均衡数据的能力

随着信息技术的广泛应用，无论是科学研究还是社会生活的各个领域中都积累了大量的数据，这些数据中可能会存在某类数据对象的数量远远多于其他类别数据，或是很大部分是没有标记，只有少量是有标记的，造成数据分布出现不平衡性．在缺乏类别信息情况下，采用聚类方法就是一种有效的处理方式．而在现实生活中，大多数对象并没有严格的类别，它们在状态和类别方面存在着模糊性，因而进行软划分可能会更加真实和合理，这种现象在不均衡数据集上表现尤为突出．从大量聚类算法的实验中可以看出，相对来说，聚类算法在不均衡数据集上的性能要比在均衡数据集上的性能差．现有的划分聚类算法或层次聚类算法等在处理不均衡数据时，其聚类性能大幅度下降；部分图论聚类算法，如DBSCAN、Chameleon等能有效识别任意大小和不同形状的簇，在处理不均衡数据方面效果相对较好，但它们的时间复杂度都很高，难以处理大规模的数据集．文献［41］结合一趟聚类算法改进了DBSCAN算法，其聚类性能有了较大的提高，在处理不均衡数据方面更有优势，同时也可以应用于大规模数据集．文献［42］和［43］提出的两阶段混合聚类策略能比较有效地处理不均衡文档数据，文献［42］在聚类第二个阶段采用文档权重调整技术，根据文档被错误划分的次数调整文档的权值，以减少文档不平衡分布造成的影响．由于METIS图划分技术对不均衡数据处理效果欠佳，文献［43］提出使用Graclus代替METIS对不均衡数据构成的图进行图划分处理，以提高算法处理不均衡数据的性能．李志华等针对分类属性数据样本间的分布不平衡性、样本的分布与空间距离无关的特点，提出一种基于量子机制的分类属性数据模糊聚类算法．文献［44］和［45］通过修改传统聚类算法目标函数和加入权重系数来提高算法的鲁棒性以及在不均衡数据上的聚类性能．文献［46］和［47］在聚类过程中，考虑了属性的不平衡分布，对不同的分类属性赋予不同的权值以提高聚类算法的扩展性．另外，集成学习和数据抽样也是解决不均衡数据聚类的有效方式，它们通过投票机制或抽样训练的方式改进原始数据的分布结构以降低不均衡性［48，49］．虽然在不均衡数据的处理问题上存在着多种解决方式，但是在对待具体大规模数据时，其算法的效率和效果都有待进一步分析和验证．所以，针对不均衡数据的高性能聚类算法研究也是一个有待深入研究的问题．

4聚类算法的可拓展能力

许多聚类算法在小样本数据数据集上能够表现出很好的性能，但对包含几百万甚至上亿个数据对象的大规模数据集进行聚类可能会产生有偏的结果．因为不同类型的聚类算法都存在着各自的问题：划分聚类算法中聚类数目的选择和聚类初始点的选择是影响算法性能的关键和难点；层次聚类算法虽然不需要预先指定聚类数目，但是它在运行过程中不能回溯处理已经形成的簇结构，且时间复杂度非常高；基于图论的聚类算法易于发现不规则的簇，但图的最优划分是一个NP难问题；基于网络和密度的聚类算法需要预先指定较多参数．上述问题都是影响聚类算法的可扩展性的重要因素，但目前也有不少研究针对这些问题对部分聚类算法进行改进以提高其拓展性．文献［50］提出了一种面向最小包含球问题的核心集求解算法，该算法所得核心集的大小与数据集的维数和大小均无关．文献［51］将该技术用于谱聚类，提出了新的适用于大规模数据集的谱聚类算法．文献［52］结合增量聚类方法对GKMeans算法进行改进，该算法需要最小化辅助聚类函数．而文献［53］和［54］分别在聚类数目确定和聚类初始点的选择方面给出有指导性的处理方式，并使它们能拓展至大规模数据集上．最近，Tzortzis等通过对各个簇指派不同的权重值以寻找到最优的初始聚类点，实验证明该方法具有较好的拓展性，能够应用于大规模数据集［55］．尽管许多聚类算法在经过改进之后能够在一定程度上适用于大规模数据集，但是在面对超大规模的数据集时，还需要研究更有效的、拓展性更好的聚类算法．

5聚类效果评价的指标选择问题

聚类算法产生已经有几十年了，但是关于聚类算法的评估问题一直仍然是一个尚需突破的难题．聚类算法的常见评估指标包括外部评估指标和内部评估指标．外部评估方法是有监督的方法，与聚类算法无关．理想的聚类结果是：具有相同类别的数据对象被聚集到相同的簇中，不同类别的数据对象聚集在不同的簇中，主要的指标有聚类熵、聚类精度和召回率等．聚类熵考虑簇中不同类别数据的分布，聚类熵越小，聚类效果越好．聚类精度的基本出发点是使用簇中数目最多的类别作为该簇的类别标记．聚类召回率能够反映被正确聚类的对象的比率．内部评估方法是利用未知结构数据集的固有特征和量值来进行评价，主要通过考察簇的分离情况和簇的紧凑情况评估聚类效果，常用的指标有SSE、Cophenetic相关系数和stability等．此外，聚类数目也是评估算法性能的一个重要指标．一般而言，SSE、stability聚类熵、聚类簇个数和召回率之间一致性较好，但不绝对，而这些指标往往都和聚类精度有冲突．特别是在进行大数据聚类时，需要聚类成多个簇，需要达到什么样的效果才能有效解决实际问题，这些都需要结合聚类任务以及其他知识进行综合考量．所以，在评价聚类算法的性能时，一般需要根据任务需求选择合适的评估指标．由此可见，解决评估指标之间的矛盾也是一个大挑战，而如何衡量聚类数目以及其他聚类效果评估指标之间的关系是未来需要加强研究的方向．

6结论

聚类分析作为典型的无监督学习方法，是探索数据规律的一种有效工具，也可作为其他学习分析方法的预处理步骤，具有非常广泛的应用价值．本文从理解聚类分析的基本框架出发，将聚类过程分成六个步骤，然后分别就聚类分析框架中各个步骤产生的挑战性问题及解决方法进行了归纳和总结，并提出了未来研究的方向．当然，对于大数据环境下的聚类分析而言，还有一些始终未能解决的或将会出现的挑战性问题的存在．因此，在未来的研究工作中需要进一步解决已存在的挑战性问题，并对新出现的问题开展更多有针对性的研究，以期进一步丰富聚类分析的研究内容和拓展聚类分析的研究方向．

作者：蒋盛益王连喜单位：广东外语外贸大学 思科信息学院图书馆