2015, Vol. 26
聚类(clustering)在数据挖掘、模式识别等领域中有着重要的作用,在识别数据的内在结构方面尤其有效.聚类主要应用于语音识别、字符识别、图像分割、数据压缩和信息检索等[1].迄今为止,聚类还没有一个公认的形式化定义,本文使用如下描述:聚类是将一个数据集划分为若干组或类的过程,通过聚类,使得同一组内的数据对象具有较高的相似度,而不同组中的数据对象则是不相似的[2, 3].聚类通常需要计算数据集中数据之间的距离,因此当数据的维度很大时,传统的聚类方法计算速度会急速下降,同时会消耗大量的内存.当今社会处在数据急剧膨胀的时代,数据的规模和维度都在不断增大,传统的聚类方法很多难以适应这一趋势.尤其是移动计算平台的高速发展,其平台自身的特性限制了算法的内存使用规模,因此,以往的很多方法若不进行改进,在这类平台上将无法运行.然而,聚类分析本身依然具有很多优势,所以需要一种可以快速分析高维数据的聚类方法.
本文提出了一种新型的基于近邻(nearest neighbors)的数据表示,在此基础上进行聚类,实验中取得了很好的效果.我们使用近邻查找,找到样本的k最近邻,在新的数据表示中,将近邻所在位置赋值为1,非近邻位置赋值为0.实验表明:这种表示具有较高的准确率;同时,使用我们的压缩方法后,可以在准确率不变的情况下有效降低存储空间和运行时内存使用.
本文第1节对聚类算法进行简单的介绍.第2节详细介绍我们的方法.第3节为具体的实验和结果分析.第4节给出结论.
1 聚 类由于数据的类型、维度等多种因素,没有一种聚类方法可以对所有的数据都适用[3].从最基本的聚类思想衍生出了多种聚类方法,可以根据聚类规则、距离计算方式等标准对聚类算法进行分类[4].常见的聚类算法主要有基于划分的算法、基于层次的算法、基于密度的算法、基于网格的算法和基于模型的算法等,其中具代表性的是K-means问题的Lloyd方法.
K-means这个词最早由MacQueen于1967年使用[5],该问题的提出可以追溯到1957年,标准算法最早由Lloyd在1957年给出,但直到1982年,才发表了算法详细步骤和数学证明[6].K-means的算法思想是:在给定的数据集D=[x1,x2,…,xn]中,每个向量均为d维,将n个数据分成k个簇的集合S=[s1,s2,…,sk],其中,si是集合{x1,x2,…,xn} 的子集,任si∩sj=∅且$\bigcup\nolimits_{i=1}^{k}{{{s}_{i}}}=D\text{.}$K-means的目标是使簇内距离和最小(within-cluster sum of squares),该目标用公式表示为
| $\arg {{\min }_{S}}\sum\nolimits_{i=1}^{k}{\sum\nolimits_{x\in {{s}_{i}}}{||x-{{\mu }_{i}}|{{|}^{2}}}}$ | (1) |
其中,μi是属于si的数据的中心,用公式表示为
| ${{\mu }_{i}}=\frac{\sum\nolimits_{x\in {{s}_{i}}}{x}}{|{{s}_{i}}|}$ | (2) |
求解K-means问题的Lloyd方法具体算法描述如下:
算法1.
输入:簇个数k,数据集D.
输出:k个簇的集合S.
1) 从D中随机选择k个点作为每个簇的中心
2) repeat
3) 对于每个数据x∈D,找到距离最近的簇的中心μi,标记x属于第i簇
4) 根据公式(2)更新每个簇中心的值
5) Until 目标函数(公式(1))值的变化在阈值内或达到循环次数,退出
Lloyd方法是最经典的聚类算法,实现简单且具有很好的性能.同时,Lloyd方法是具有可伸缩性的,可以适应分布式计算.但它也有一些缺点:(1) 对聚类中心的初始值很敏感;(2) 对于分类属性不适用;(3) 对于“噪音”和孤立点(outlier)数据是敏感的.
使用传统的Lloyd方法进行聚类时需要存储完整的数据集,同时将数据集全部或部分加载到内存中进行计算,在数据量大或平台存储空间限制时,算法难以发挥作用.本文提出的基于近邻表示的聚类算法可以较好地解决这个问题.
2 基于近邻表示的聚类算法 2.1 简 介本文提出了一种基于近邻表示的聚类方法.该方法可以取得更高的准确率,同时使用的内存较少.第3节将对该方法的性能进行分析.在文献[7]中使用数据集本身作为过匹配的字典,代替通用字典来表示数据集当中的数据,文中提到:如果每一类数据都可以找到足够的训练数据来构造字典,那么所有的测试数据将可以由字典中与它同类的数据线性表示.所以我们有理由相信,一个样例可以由与它相似的样例来表示.另一篇文献[8]阐述了近邻结构信息包含了较强的类别信息,可以有效地判断数据相似与否.由此我们提出:通过存储数据的近邻结构关系来替代数据本身,而这种近邻关系本身是以0-1向量的形式存在,故可以在该表示上使用数据压缩,压缩后所需要的存储量将远远小于原始数据本身,这就是基于近邻表示的聚类方法的基本思想.
为使文章表述清晰,下面我们约定本文中将使用的一些符号.D∈$\mathbb{R}$n×m表示n个m维数据组成的数据集,也可以表示[x1,x2,…,xn],并且xi=[xi1,xi2,…,xin],xij表示数据xi在第j维的值.
2.2 方法细节对于数据集D中的任意数据xi,首先我们计算它的近邻Ni,Ni=[ni1,ni2,…,nik]表示向量xi的邻居集合,nij为第j个邻居在D中的下标.若j∈Ni,则设置xi的近邻表示 ${{{x}'}_{i}}$中的${{{x}'}_{ij}}$为1,否则为0.因此,xi基于近邻的表示为${{{x}'}_{i}}=[{{{x}'}_{i1}},{{{x}'}_{i2}},...,{{{x}'}_{in}}]$,其中,${{{x}'}_{ij}}$等于0,表示j不在Ni中;等于1,表示j在Ni中.即,xi和xj是邻居.上文提到,D中的数据xi可以由与它相似的数据表示,因此我们相信,xi的近邻数据包含了这个数据本身的有效信息.故,我们使用${{{x}'}_{i}}$来代替xi.若两个数据具有相似的近邻表示,也就意味着它们很有可能是同一个类别中的数据,因此可以在近邻表示上进行聚类.
在图 1中,我们使用k=5的情况举例说明了如何生成一个近邻表示.一张16×16图片的原始数据xi是一个256×1的向量,我们找到xi的5个近邻,将近邻所在的位置赋为1,非近邻所在位置赋为0,这样就得到了基于近邻表示的向量${{{x}'}_{i}}.{{{x}'}_{i}}$具有如下优点:(1) 是一个0-1向量,因此可以压缩存储,节省空间;(2) 可以通过修改聚类算法,直接计算两个压缩后向量之间的距离,使用压缩后的向量可以有效节约内存空间,降低运算时间,下一节我们将详细描述数据压缩和使用压缩后的向量进行计算的细节;(3) 包含了原始数据xi的有效信息.
|
Fig.1 How to generate NN-based representation (k=5) 图 1 如何得到基于近邻的表示(k=5) |
但是,这样做会有两个困难:(1) 当数据量增大时,寻找近邻本身会需要很长的计算时间,若计算xi与其他所有点之间的距离并从中找到k个距离最小的点,则时间复杂度为O(nm-m+n),n为数据集大小,m为数据的维度; (2) 若只存储基于近邻的0-1向量,对于新数据将无法计算它的最近邻,而存储原始数据则耗费大量的存储空间.
对于上述两个问题,我们的解决方法是选择FLANN(fast library for approximate nearest neighbors)[9]替代传统的KNN算法.FLANN是一个高维空间中进行快速近似近邻查找的库,它包含了一系列高效的近邻查找算法和一个根据数据集自动匹配最优算法和参数的系统.在FLANN作者提供的实验中,在众多的数据集上,与现有的近似近邻搜索算法相比,FLANN的查询效率是最高的.FLANN的高效使得第1个问题得到很好的解决,同时, FLANN会生成一个模型文件,通过这个模型文件,我们可以找到任何数据在原始数据中的最近邻,而无需原始数据,这样就不需要存储原始数据.这个模型文件通常都非常小,不会带来额外的存储负担.
2.3 数据压缩与距离计算在解决上述两个问题后,我们将产生的0-1向量进行压缩存储,将0-1向量的每一个值仅用一个比特(bit)表示,这样,存储的效率比最初的0-1向量提高了8倍.但是在计算压缩后向量之间的相似度时,需要使用大量的除法和移位操作,为了提高运算效率,我们使用了一个256×8的表,通过查表可以将一个字节(byte)还原成8个0-1值,只需要一个数组下标访问操作.
压缩近邻表示具体算法描述如下,其中,S为N中的近邻表示经过压缩后组成的集合:
算法2.
输入:近邻表示集合N.
输出:压缩表示集合S.
1) for i←1:n
2) for j←1:k
3) xi的第j个近邻为index←Nij
4) block←$\left\lfloor index/8 \right\rfloor $
5) bit←index mod 8
4) S[i][block]的第bit位赋为1
7) end
8) end
压缩的数据在距离计算时需要将比特(bit)数据替换成真实数据,压缩数据中,一个字节(byte)称为一个block,在计算过程中需要用到一张映射表dataMap,这张表中存储的是一个字节与其包含的8个0-1比特的映射关系,可以直接通过字节对应的数值查询,具体算法描述如下:
算法3.
输入:压缩向量v,映射表dataMap.
输出:真实数据d.
1) repeat
2) index←v[block]
3) realValue[0,…,7]←dataMap[index]
4) for i←0:7
5) d[8×block+i]←realValue[i]
6) end
7) Until 遍历v所有的block
恢复一个Byte查表需要9次运算,包括1次寻址和8次赋值;而位运算对于每个bit都需要先移位再获取bit信息,至少需要16次运算.因此,使用查表与直接使用位运算相比有明显的优势.
在解决了上述问题之后,我们的方法变得切实可行,并且理论上运行速度和节约使用空间都有很大的提升.下面我们在实验中对方法进行了验证.
3 实 验在这一节,我们将展现我们方法在公开数据集上的具体表现.本节将详细阐述数据集的选取、实验参数设置和评价指标等细节.代码使用C++实现,运行平台为Visual Studio,CPU为Intel i7-4770,内存8G.
3.1 数据集本次实验中我们使用了6个数据集:COIL20[10],USPS,ATT face database(ORL)[11],Yale database[12], COIL100[13]和MNIST[14].Yale和ORL是人脸数据集,USPS和MNIST是手写数据集,COIL20和COIL100是物体数据集.
• COIL20:我们使用经过预处理版本的COIL20数据集,其中所有物品照片中的背景均被忽略了,并且照片均为可以覆盖物体的最小方形区域.数据集有20个不同物体,每个物体有72张照片,每张图片由32×32的256灰度值组成,因此,每张照片可以由一个1 024维的向量表示.
• USPS:一个手写数据集,我们使用它的一个常用子集,共9 298张照片.每张图片由16×16位的256灰度值组成,因此,每张照片可以由一个256维的向量表示.
• Yale Database:包含了15个个体的gif格式图片,每个人有11张照片,分别是不同的面部表情或场景,包括中间照光、左侧照光、右侧照光、戴眼镜、不戴眼镜、高兴、沮丧、瞌睡、惊奇和眨眼.每张图片由32×32的256灰度值组成,因此,每张照片可以由一个1 024维的向量表示.
• ATT face database(ORL):有40个不同的人,每个人有10张照片,每个人的照片有灯光、面部表情和面部细节的不同.所有的照片均是在昏暗的背景中面部朝前完成的.每张图片由32×32的256灰度值组成,因此,每张照片可以由一个1 024维的向量表示.
• COIL100:COIL20的扩充版本,拥有100个不同物体,每个物体拥有72张图片,每张图片由32×32位的256灰度值组成,因此,每张照片可以由一个1 024维的向量表示.
• MNIST:一个手写数据集,拥有60 000张训练照片和10 000张测试照片,我们使用了其中的子集共10 000张.每张图片由28×28的256灰度值组成,因此,每张照片可以由一个784维的向量表示.
3.2 评价指标实验的评价指标采用准确率(accuracy,简称AC):对于一个给定的数据xi,ri和si分别是其聚类结果和原始标记值,则AC通过以下公式计算:
| $AC=\sum\nolimits_{i=1}^{n}{\frac{\delta ({{s}_{i}},map({{r}_{i}}))}{n}}$ | (3) |
其中,n为数据集的大小;δ(x,y)是一个二值函数,在x=y时等于1,否则为0;Map是一个映射函数,将聚类得到的标记映射到对应的真实标记上.目前,通常使用的映射方法是Kuhn-Munkres算法 [15, 16, 17].
3.3 参数设置为了能够准确地评价我们方法的效果,我们选取了最经典的聚类算法:k-means(Lloyd方法).比较两种方法的结果:k-means,Bit k-means.k-means的输入为原始数据,Bit k-means的输入为压缩后的近邻表示,两个算法的具体逻辑相同,只是适应不同表示的数据输入.所有的这些方法只需要一个输入参数,即,聚类的个数K.同时,由于我们选用FLANN作为近邻查找算法,需要确定两个参数:近邻个数k和检查次数(check number).因为聚类算法的初始化使用了随机函数,我们将每次实验的初始随机数种子设置为0,运行10次.
为了能够公平地比较运行结果,我们需要为所有的FLANN设置相同的参数,所以需要找FLANN的相对最佳参数.对于检查次数,我们选取COIL20的结果作为标准,结果见表 1.
|
Table 1 Check number experiments 表 1 检查次数实验 |
由表 1,我们可以确定检查次数选择1 024.
由于每个数据集的大小均不相同,我们还需要找到一个合理的近邻个数k,使得结果的准确性较高并且是稀疏的.实验中,我们从整个数据集的2.5%,5%,7.5%和10%中做选择,具体结果见表 2~表 7;
|
|
Table 2 KNN size experiment: COIL20 表 2 近邻个数实验:COIL20 |
|
|
Table 3 KNN size experiment: USPS 表 3 近邻个数实验:USPS |
|
|
Table 4 KNN size experiment: Yale 表 4 近邻个数实验:Yale |
|
|
Table 5 KNN size experiment: ORL 表 5 近邻个数实验:ORL |
|
|
Table 6 KNN size experiment: COIL100 表 6 近邻个数实验:COIL100 |
|
|
Table 7 KNN size experiment: MNIST 表 7 近邻个数实验:MNIST |
由表 2~表 7,综合在各个数据集上的表现,我们选取整个数据集的5%作为近邻个数(k)的值,即k=0.05n.
3.4 实验结果在检查次数为1 024、k为整个数据集的5%的参数设置下,我们对两种方法进行了实验,每种方法运行10次,得到实验结果图 2(x轴为次数,y轴为准确率).同时,针对10次的准确率统计得到最高准确率(max AC)和平均准确率(average AC),详情见表 8.
|
Fig.2 Results on six datasets 图 2 6个数据集的实验结果 |
|
|
Table 8 Average AC and max AC表 8 平均准确率和最高准确率 |
在实验结果图中,从左上到右下分别为以下数据集的结果:COIL20,ORL,Yale,USPS,COIL100和MNIST.从表 8平均准确率来看,在COIL20,Yale和COIL100上,我们的方法比现有方法有提升,在ORL,USPS和MNIST上准确率稍有下降.ORL中准确率略有下降,与ORL本身每个类别的数据过少有关.由于每个类的数据过少,这样,每个数据的近邻个数相对较多,因此被误判为同一类的概率就会相应地增加,最终导致了整体准确率的下降.而真实世界的数据集中,单类样例个数往往远大于ORL中的10,因此这种情况在实际中发生的概率较小.
从表 8最高准确率来看,我们的方法在COIL20,Yale,USPS,COIL100均取得了更高的准确率,其中,COIL20数据集上Bit k-means相对k-means提高了8%,Yale数据集上提高了29.8%.综合而言,基于近邻表示的聚类方法在准确率上取得了更好的表现.
MNIST,USPS数据集为手写数据集,数字一共有10种(0~9),某些数字在增加了手写的误差后,差别变得很小,如0,9和8,7和1,5和6.因此,这些数据的近邻都很相似,这时候再对基于近邻表示的向量进行相似度计算时,极少的近邻差异就会被归入不同类别,这大大增加了出错的概率.因此,我们的方法在数据集的数据近邻均非常相似时会有一定的局限性,这是以后需要加以改进的.
3.5 内存空间分析在实际的运行过程中,k-means需要的数据部分内存大小为n×m×8字节,其中,n为样本(instance)个数,m为属性(dimension)个数,8表示double类型的长度.Bit k-means需要的数据部分内存大小为n×n/8字节,当n≤64×m时,我们的方法使用的内存空间会更小,这个分析同样适用于数据在硬盘上的存储.因此,该方法在属性较多的数据,如文本、图像等,具有较好的应用前景.具体的压缩结果见表 9,其中,space表示原始数据使用的空间, compress表示使用我们的近邻表示方法并进行压缩后的空间,单位为KB.
|
|
Table 9 Compress result 表 9 压缩效果 |
我们对程序的运行时间也进行了统计,具体结果见表 10,时间的单位是s.从结果我们可以看出,当n>m时,新的表示在压缩前是比原始数据大的,这样在计算距离时需要更大的计算量,因此运行时间有一定的增加.我们的程序针对新的表示的二值特性做了一些优化,提升了运行效率,但依然无法消除数据维度变大带来的影响.因此,我们的表示更适用于属性维度较高的场景.
|
|
Table 10 Running time 表 10 运行时间 |
本文使用基于近邻的聚类方法,大大降低了数据存储和内存开销;同时,在一定程度上提高了聚类的准确性.但该方法对于数据差异较小的数据集有一定的局限性,仍需要加以改进.对于属性较多数据,我们的方法可以显著降低运行内存和存储开销.
| [1] | Sun JG, Liu J, Zhao LY. Clustering algorithms research. Ruan Jian Xue Bao/Journal of Software, 2008,19(1):48-61 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/19/48.htm |
| [2] | Zhu M. Introduction to Data Mining. Hefei: Press of University of Science and Technology of China, 2002. 138-139 (in Chinese). |
| [3] | Jain AK, Dubes RC. Algorithms for Clustering Data. Prentice-Hall, Inc., 1988. 1-334. |
| [4] | Gelbard R, Goldman O, Spiegler I. Investigating diversity of clustering methods: An empirical comparison. Data & Knowledge Engineering, 2007,63(1):155-166 . |
| [5] | MacQueen J. Some methods for classification and analysis of multivariate observations. In: Proc. of the 5th Berkeley Symp. on Mathematical Statistics and Probability. 1967. 281-297. |
| [6] | Lloyd S. Least squares quantization in PCM. IEEE Trans. on Information Theory, 1982,28(2):129-137. [10.1109/TIT.1982.10564 89] |
| [7] | Wright J, Yang AY, Ganesh A, Sastry SS, Ma Y. Robust face recognition via sparse representation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2009,31(2):210-227 . |
| [8] | Wu JX. Balance support vector machines locally using the structural similarity kernel. In: Proc. of the Pacific-Asia Conf. on Knowledge Discovery and Data Mining. 2011. 112-123 . |
| [9] | Muja M, Lowe DG. Fast approximate nearest neighbors with automatic algorithm configuration. In: Proc. of the Int’l Conf. on Vision Theory and Applications. 2009. 331-340.. |
| [10] | Nene SA, Nayar SK, Murase H. Columbia object image library (COIL-20). Technical Report, CUCS-005-96, New York: Department of Computer Science, Columbia University, 1996.. |
| [11] | Samaria FS, Harter AC. Parameterisation of a stochastic model for human face identification. 1994. In: Proc. of the 2nd IEEE Workshop on the Applications of Computer Vision.138-142 . |
| [12] | Belhumeur PN, Hespanha JP, Kriegman D. Eigenfaces vs. fisherfaces: Recognition using class specific linear projection. IEEE Trans. on Pattern Analysis and Machine Intelligence, 1997,19(7):711-720 . |
| [13] | Nayar SK, Nene SA, Murase H. Columbia object image library (coil 100). Technical Report, CUCS-006-96, New York: Department of Computer Science, Columbia University, 1996. |
| [14] | LeCun Y, Bottou L, Bengio Y, Haffner P. Gradient-Based learning applied to document recognition. Proc. of the IEEE, 1998, 86(11):2278-2324 . |
| [15] | Kuhn HW. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2005,52(1):7-21 . |
| [16] | Kuhn HW. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly, 1956,3(4):253-258 . |
| [17] | Munkres J. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial & Applied Mathematics, 1957,5(1):32-38 . |
| [1] | 孙吉贵,刘杰,赵连宇.聚类算法研究.软件学报,2008,19(1):48-61. http://www.jos.org.cn/1000-9825/19/48.htm |
| [2] | 朱明.数据挖掘导论.合肥:中国科学技术大学出版社,2002.138-139. |