核函数在划分聚类中的应用与实现

摘要：聚类是数据挖掘的一种重要方法，核函数是能够将低维不可分的数据映射到高维空间进行线性可分时能够降低数据处理难度的重要手段。介绍了聚类算法和核函数的特点。通过引入基于核函数的相似性测度，对k-平均聚类算法和围绕中心点的划分（PAM）算法在Matlab上做了改进和实现。

关键词：核函数；划分聚类；k-折交叉验证；PAM（围绕中心点的划分）；主成分分析

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2013）27-6185-04

随着智能化的到来，机器学习技术得到广泛的重视。当前，数据挖掘技术的发展，以及社会应用对云计算、大数据等的要求也越来越高。分类、关联规则、聚类、时间序列与序列模式、Web挖掘、空间挖掘技术等得到了较快发展。作为一种基于统计学习理论的支持向量机（SVM）成为了数据挖掘的一种比较重要且有特色的方法，在分类、聚类方面有着很重要的意义。支持向量机使用结构风险最小化原则代替经验风险最小化原则，采用将低维空间映射到高维空间，在非线性、小样本、二分类、高维模式应用环境中具有一些明显的优势。

支持向量机目前在二分类问题中得到了深入的研究，在多类分类问题的求解上也提出了很多解决办法。聚类作为数据挖掘的另一个重要领域，则相对于分类而言，研究的较少。文献[6]对将支持向量机的思想应用于聚类做了简单的介绍，并且提出了采用主成分分析（PCA）进行特征提取的一种线性降维的简单算法。

支持向量机具有的明显优势，有一个很重要的原因，就是采用了核函数（但核函数不一定只用在SVM上）。该文根据核函数在支持向量机上进行有效分类的启发，将核函数思想应用到划分聚类上，在Matlab环境下进行了应用与实现。

1 核函数

核函数对支持向量机的分类性能有影响。核函数的形式的选取，参数的选择，都是核函数的应用必须考虑的问题。

核函数具有以下优点：

2）采用核函数可以处理高维数据。这是因为采用核函数后，输入空间的维数对核函数的矩阵没有影响。这样就避免了所谓的“维数灾难”，并且计算量得到了减小。

3）核函数对于支持向量机是至关重要的，但核函数的思想绝不仅仅只用于支持向量机处理上。实际上，只要一个应用，在建立模型后存在内积形式，都可以采用K（x，x’）去替换，这样就有可能改进目标算法。这样，核函数思想就可以与聚类算法相结合，在聚类的预处理步骤上，能够设计出各种基于核函数的子算法，更重要的是这两部分的设计可以独立开展，根据不同的应用环境进行筛选，找出合适的算法。

4）核函数有多种形式，相同的核函数的参数也会不同。有些应用，适合采用某一种核函数，而有些应用可能要采用另一种核函数。

核函数应用中，Mercer定理具有很重要的意义。Mercer定理指出：要证明K是一个核函数，不必去寻找Φ变换函数，只需要在数据训练集上求出各个内积Kij，然后只要判断一下矩阵K是不是半正定矩阵就可以了。满足Mercer条件的函数就能作为核函数。

2 聚类

2.1 聚类简介

聚类和分类一样，是数据挖掘的一项重要功能。分类是一种有监督的学习。而聚类与分类不同，聚类中要划分的组（簇）事先是不确定的，而是由数据决定的，因此聚类是一种无监督的学习。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类具有重要的意义和普遍的价值。在日常生活中，经常有“物以类聚，人以群分”的说法，聚类能够很好地刻画数据的属性以及群体行为特征。聚类的目标就是将数据采用某种算法，根据数据本身的属性，划分成若干组（簇），分组的依据是在同一个组（簇）中的数据之间具有较高的相似度，在不同的组（簇）中具有很低的相似度。

目前，数据挖掘技术以及大数据技术面对的是巨大的、复杂的、异构的数据集，聚类分析算法面临很大的挑战。一个好的聚类分析算法应该考虑以下一些方面：

1） 可伸缩性：聚类算法在小数据集和大数据集上均能得出有效的结论；

2） 能够处理各种数据类型的属性，并且能够处理高维、稀疏数据；

3） 能够根据数据本身的特征，找出任意形状的组（簇），而不是仅仅发现类球类的簇；

4） 对专业领域知识依赖性低；聚类的结果应该是易于理解、便于应用；

5）数据集输入的顺序对聚类的结果影响较小；

6） 能够对噪声进行处理；能够根据实际应用的约束条件进行聚类。

2.2 距离与相似度的度量

从聚类的概念上可以看出，数据元素之间的相似度是聚类分析中很重要的因素。如何来定义数据对象之间的相似度，对聚类分析的质量有决定作用。相似度在通常情况下可以用距离d（xi，xj）来衡量，当xi与xj相似时，d（xi，xj）值较小；而当xi与xj不相似时，d（xi，xj）较大。

常用的度量标准有：

1）两个数据对象之间的距离函数（相似性测度）

对于具有连续特征的数据集空间，常用的距离函数有明科夫斯基距离、二次型距离、余弦距离等；对于二元类型的数据集，可以采用简单匹配系数（SMC）、Jaccard系数和Rao系数进行描述。

2） 簇间距离（不相似性测度）

描述两个簇间的距离，可以有以下一些方法：

采用两个簇中相距最远的两个数据之间的距离来表示簇间距离（最远距离法）；

采用两个簇中相距最近的两个数据之间的距离来表示簇间距离（最近距离法）；

采用两个簇中的中心点的距离作为簇间距离，簇的中心可以用该簇所有元素的算术平均表示（簇中心点法）；

采用两个簇中任意的两个数据对象之间的距离表示簇间距离（簇平均法）；

除了以上四种方法外，还可以采用离差平方和来描述簇间距离。

2.3 聚类的类型

聚类的类型按照不同的标准，有不同的分法。这里根据聚类分析算法的设计思路，将聚类分成以下5种类型。

1）划分聚类

这是最基本的聚类方法，划分思想比较接近日常生活。若给定l个数据（可以是多维），将这l个数据划分成k类，k

划分聚类的方法常用的有：k-平均、k-原型、k-中心点、k-模、PAM、CLARA以及CLARANS等。

2）层次聚类

层次聚类就是采用自顶向下（分裂）或自底向上（凝聚）的方法，相继地分裂或合并，直到终止条件满足的一种聚类算法。分裂的算法有DIANA算法，凝聚的算法有AGNES。

3） 密度聚类

该方法不采用距离作为相似性度量，可以很好地解决前述算法偏向于得出类似于球类的聚类结果。密度聚类采用数据是否属于相连的密度域，采用直接密度可达、密度可达来寻找相连密度域的数据，将符合要求的数据插入到相应的组（簇）中。典型的密度聚类算法是DBSCAN。

4）网格聚类

CLIQUE算法、STING算法等是常用的网格聚类算法。网格聚类算法首先将数据空间划分成有限个单元的网格，以后的处理都是基于每个单元进行。该类算法速度快，因为与所处理的数据个数没有关系，而只与数据空间中的单元的个数有关。该类算法很有价值，不需要事先给定聚类的簇个数，能够发现任意形状、任意大小的簇，且计算结果与数据输入顺序无关。

5）模型聚类

给一个簇先设定一个模型，然后以这个模型为依据去寻找满足模型的数据，将其归于该模型对应的簇。基于神经网络的模型有SOM，基于统计学模型的方法有Gaussian Mixture Model（混合高斯模型）。

本文主要对划分聚类的k-平均算法和PAM算法进行。

3 核函数在划分聚类中的应用与实现

3.1 核函数与聚类结合研究现状

文献[1]对核函数在支持向量机上的应用做了探讨，并采用了k-折交叉验证与网格搜索法，对Breast Cancer数据集上采用多项式、RBF和Sigmoid核函数进行了实验验证；文献[2]采用最小包含球的思想，介绍了一种核向量机（CVM），并与SVM做了比较；文献[3]认为主成分分析（PCA）降维的目的是对原始数据的重构，而不是为了进行分类，因此会降低分类效果，于是提出了采用高斯核函数和核化离散差判别分析的一种核化聚类判别分析方法（KSCDA）；文献[4]将多项式核函数、RBF核函数和Sigmoid核函数应用到了遥感图像几何校正中并做了详细的实验验证；文献[5]将Gauss核函数的应用到了航空AE3007发动机一次引气故障的诊断中，对Gauss核函数的参数和相应的支持向量机的惩罚因子C的不同组合作了较为详尽的论述；文献[6]对核函数的原理与性质作了较为深入的介绍，并对聚类和主成分分析（PCA）给出了应用的一般思路；文献[7]对数据挖掘中聚类的原理和算法做了较为详细的介绍，特别是对划分聚类、密度聚类、层次聚类和网格聚类做了较为详尽的举例；文献[8]则采用基于余弦函数的夹角大小来进行相似度测度定义，并应用到了自底向上的凝聚层次聚类中，对6个元素的高维稀疏矩阵进行了实验仿真；文献[9]对常用的核函数，运用Libsvm工具箱，在Matlab平台上做了一些实验验证，得出了一些直观的效果；文献[10]将核函数思想应用到了自组织映射（SOM）网络流量分析，提出了kSOM方法，能够对有多个统计特征属性的网络流量在应用层进行分类。

3.2 核函数在聚类分析中的应用要点

根据对聚类和核函数的特点分析，根据文献[8]，发现核函数的思想在聚类中的应用可以通过对相似度度量上来进行设计。例如，在判断两个向量的相似度时，采用传统的距离计算方法，对于复杂的高维稀疏矩阵，往往计算量大，由于有了核函数的思想，可以采用计算两个向量的夹角的大小进行数据对象的相似度判别。

于是根据空间解析几何原理，夹角的大小cos（θ）=xi·xj/（||xi||*||xj||）；

其中θ∈[0，π/2]。当夹角越小时，两个数据对象越相似；夹角越大时，两个数据对象就越不相似。

更进一步，借用支持向量机中核函数的应用的思想，将相似度夹角的计算可以简单地改成带有核函数K（x，x’），这样对于计算高维、稀疏空间向量的相似度带来很大方便。

3.2.1 核函数在k-平均聚类算法上的应用

k-平均算法，是一个最简单、最基本的聚类算法。该算法的思想是初始随机给定k个簇中心，按照最邻近原则把待分类数据划分到相应的簇，然后按平均法重新计算各个簇的中心，确定新的簇心。一直迭代，直到准则函数收敛。由于k-平均算法要频繁计算两个数据之间的距离，因此，核函数思想应用到k-平均算法能够解决高维稀疏数据之间的距离计算。算法如下：

算法目标：输入l个数据和需要聚类出的簇的个数k，得出聚类的k个簇

1）输入未聚类的l个初始数据点集和簇的个数k；

2）随机选取k个数据作为初始的中心；

3）计算每个数据与簇中心的余弦相似测度，并聚类到与该数据最相似的簇中去；

这里由于采用了核函数思想，将传统的距离用计算余弦夹角相似测度，而余弦夹角的相似测度的计算又引入了核函数的思想，对于内积的计算可以通过所采用的核函数进行。核函数可以选择多项式核函数、RBF核函数和Sigmoid核函数等。

4）计算每个簇中所有数据的相似测度平均值，并将这个平均值作为新的聚类中心。若计算结果满足所设定的准则函数，则转7；

5）重复3，计算每个数据到簇中心的余弦相似测度，并聚类到与该数据最相似的簇中去；

6）重复4，计算每个簇中所有点的相似测度平均值，并将这个平均值作为新的簇中心

7）输出聚类的结果k个簇

3.2.2核函数在围绕中心点划分（PAM）算法上的应用

PAM算法选用簇中位置最靠近中心的数据作为中心点，然后把l个对象划分成k个簇。可以最初随机选取k个对象作为中心点，反复用非中心点数据来代替中心点，这样找出更加合理的中心点。从PAM的执行过程中可以看出，PAM算法在替换中心点时，计算代价非常高。PAM算法克服了k-平均聚类对噪声数据和孤立点数据的敏感性，但在处理大数据集上，由于替换中心点的复杂性，失去了k-平均聚类对处理大数据集的相对高效与可伸缩性。

究其原因，PAM算法中在用非中心点替换中心点时，在计算代价上的组合情况较多。因此，采用基于余弦相似测度的核函数应用，在传统PAM算法的两点之间距离的计算上，采用核函数进行，可能会对效率有所提高。

对于PAM算法，算法的步骤基本不需要改变，主要将算法中的用非中心点代替中心点试探时，在计算代价和总代价时，改为采用余弦相似测度来进行度量。

3.3采用核函数的两个划分聚类算法性能

算法的实现采用了 Matlab 7.1，数据集采用了用Matlab 7.1随机产生的100个5维空间的数据myData，并进行了一些手工调整。在聚类时，采用了标准的k-平均聚类、标准的PAM聚类，以及采用了改进的核函数聚类的k-平均聚类和PAM聚类算法。核函数采用了RBF核函数、多项式核函数以及Sigmoid核函数。

4 结束语

将核函数的思想应用到划分聚类中，对k-平均聚类算法和PAM算法在距离的计算上改为采用了基于核函数的余弦相似测度的计算，从效果上看，在k-平均聚类算法性能的提高上要优于PAM算法。这是因为PAM对数据量较大的数据集效率下降的较快。下一步的工作，准备将核函数的思想应用到另外两种能够处理较大数据集的划分聚类算法CLARA算法和CLARANS中去。

参考文献：

[1] 奉国和.SVM分类核函数及参数选择比较[J].计算机工程与应用，2011，47（3）：123-128.

[2] 许敏.核向量机算法研究及应用[J].无锡职业技术学院学报，2012，11（4）：73-76.

[3] 李天恩，何桢.基于改进的核化聚类判别分析的故障识别[J].管理工程学报，2012，26（3）：34-41.

[4] 孙军，黎琪，李和睿.支持向量机遥感图像几何校正中的不同核算法的比较[J].四川兵工学报，2012，33（8）：76-80.

[5] 郑波.基于Gauss核函数的SVM故障诊断技术研究[J].中国民航飞行学院学报，2012，23（3）：49-51.

[6] 邓乃扬，田英杰.支持向量机-理论、算法与拓展[M].北京：科学出版社，2009：81-111

[7] 毛国君，段立娟.数据挖掘原理与算法[M].北京：清华大学出版社，2005：156-181

[8] 陈森平，陈启买，吴志杰.基于核函数的层次聚类算法[J].暨南大学学报，2011，32（1）：31-35.

[9] 张倩，杨耀权.基于支持向量机核函数的研究[J].电力科学与工程，2012，28（5）：42-45.

[10] 胡婷，王勇，陶晓玲.基于核函数的SOM网络流量分类方法[J].计算机工程与设计，2011，32（4）：1195-1198.