铉 岩, 周传生

(1. 沈阳师范大学 科信软件学院, 沈阳 110034; 2. 沈阳师范大学 教育技术学院, 沈阳 110034)



基于张量距离的高阶近邻传播聚类算法

铉 岩1, 周传生2

(1. 沈阳师范大学 科信软件学院, 沈阳 110034; 2. 沈阳师范大学 教育技术学院, 沈阳 110034)

近邻传播算法(AP)不需要事先指定聚类数目,在程序运行过程中,能够自动识别聚类中心及聚类数目。在同一批数据集上,AP算法聚类结果稳定,鲁棒性好。除此之外,AP聚类算法可以采用多种距离度量方式,聚类结果精确。针对近邻传播算法(AP)不能对异构数据进行聚类的问题,提出一种基于张量距离的高阶AP聚类算法。该算法首先利用张量表示异构数据对象,然后将张量距离引入AP聚类算法,用来度量异构数据对象在张量空间的相似度。张量距离的引入,不但能够度量异构数据对象在数值上的差异,同时能够度量异构数据对象在高阶空间中位置的差异性,有效的捕捉异构数据对象的分布特征。实验结果表示,提出的高阶AP算法能够有效的对异构数据对象进行聚类。

聚类; 异构数据; 张量距离; AP算法

0 引 言

近年来,随着物联网、电子商务和云计算的发展,产生了越来越多的异构数据集[1]。作为数据挖掘的典型技术,聚类采用无监督学习的方式,将数据集划分成多个簇[2]。使得簇内数据对象之间的相似性尽可能大,簇间数据对象的相似性尽可能小[3]。经过数十年的发展,多种典型的聚类算法被相继提出。然而这些经典的聚类算法都只能对结构化数据进行聚类,难以直接对异构数据聚类。

近邻传播算法(Affinity Propagation Clustering, AP)是由Brendan J. Frey和Delbert Dueck于2007年在《Science》杂志上提出的一种新的聚类算法[4]。AP算法不需要事先指定聚类数目。在同一批数据集上,AP算法聚类结果稳定,鲁棒性好[5]。除此之外,AP聚类算法可以采用多种距离度量方式,聚类结果精确[6]。然而AP算法不支持对异构数据的聚类。为了解决这个问题,本文提出一种基于张量距离的高阶近邻传播算法。

1 相关工作

1.1 近邻传播聚类算法

AP聚类算法以相似度矩阵S对角线上的数值s(k,k)作为k点能否成为聚类中心的评判标准,即该值越大,成为聚类中心的可能性就越大,这个值又称作参考度p(preference)[7]。

为了计算参考度,AP聚类算法引入2个信息传播矩阵,即吸引度矩阵R和归属度矩阵A。吸引度值r(i,k)表示从点i发送到候选聚类中心k的数值消息,反映k点是否适合作为i点的聚类中心。计算公式如下:

(1)

归属度值a(i,k)是从候选聚类中心k发送到i的数值消息,反映i点是否选择k作为其聚类中心。计算公式如下:

(2)

(3)

r(i, k)与a (i, k)越强,则k点作为聚类中心的可能性就越大,并且i点隶属于以k点为聚类中心的聚类的可能性也越大。

1.2 异构数据聚类相关工作

近年来,随着异构数据在诸多领域的迅速增加,多种针对异构数据的聚类算法被相继提出[8]。具有代表性的双模态聚类算法是由Long等人提出的块值分解算法和HF-ART算法[9]。

受到双模态异构数据聚类算法的启发,研究人员提出了多种针对多模态异构数据聚类的算法。最为典型的由Long等人提出的频谱关联聚类算法和由Hen等人提出的对称非负矩阵分解算法[10]。由Bekkerman等人提出的联合马尔科夫随机场算法,同时能够用于半监督学习等应用[11]。

2 基于张量距离的高阶近邻传播算法

2.1 基于张量模型的异构数据表示

为了能够对各种异构数据对象进行统一表示,本文利用张量模型表示异构数据对象。张量在数学上可以看作是向量的扩展,例如在同构的意义下,一阶张量为一个向量Rd,N阶张量表示为RI1×I2…×IN,其中N表示张量的阶数,In表示张量第n阶上的维数[12]。

对于异构数据对象而言,通用的张量表示模型定义为:T∈RIt×IS×Iu×…×Ip。在张量模型中,数据的特征表示为张量的阶。

2.2 基于张量距离的高阶近邻传播算法

在弯头1入口处泥浆流体产生切向分速度，二次流开始发展；在弯头1出口处可以观察到完全发展的二次流；在弯头2出口处分速度值最大，二次流强度最强；泥浆在离开弯头部分以后，不再受到离心力的作用，混合相垂直分速度逐渐减小，但由图5e)、图5f)可看出X=5D处二次流仍有一定存留，在X=20D处二次流已基本消失。爬坡管内泥浆所受到的离心力沿流动方向不断变化，当流经弯头2时与弯头1中离心力方向相反，弯头2入口面二次流强度较弯头1出口明显降低，在流过弯头2后涡流方向改变。

在将异构数据对象表示为张量之后,为了度量数据对象在高阶张量空间的独立,本文将张量距离引入近邻传播算法。

对于给定的2个张量X∈RI1×I2×…×In和Y∈RI1×I2×…×In,x和y分别表示张量X和Y向量展开后的表示,则张量X和Y之间的张量距离定义为[13]:

(4)

其中,glm是系数,G是系数矩阵。

引入张量距离的高阶近邻传播聚类算法的主要步骤如下:

步骤1 根据式(4)计算异构数据对象之间的距离,初始化相似度矩阵S;

步骤2 根据式(1)计算样本点间的吸引度值;

步骤3 根据式(2)和式(3)计算样本点间的归属度值;

步骤4 根据式(5)～式(7)更新吸引度矩阵和归属度矩阵;

(5)

(6)

(7)

步骤5 如果迭代次数超过设定的最大值或者聚类中心不再变化,终止计算,根据P值确定聚类中心并且确定各个样本点所属的类别;否则返回步骤2,继续执行。

3 实验与分析

本节通过将本文提出的高阶近邻传播聚类算法和HOPCM算法、传统近邻传播算法进行对比来验证高阶近邻传播聚类算法的有效性[14]。实验采用2个典型的异构数据集:NUS-WIDE和CUAVE。

3.1 评价指标

为了验证基于计算模型的高阶可能性聚类算法的有效性,实验采用E*和RandIndex(RI)作为评价指标[15]。E*用来评估聚类算法产生的聚类中心的准确率,计算方法如公式(8)所示。

(8)

RI用来评估一个聚类将多少个数据对象划分到正确的簇中。设数据集X的一个聚类结构为C={C1,C2,…,CM},数据集的一个划分为P={p1,p2,…,pS},可通过比较C和P以及邻近矩阵与P来评价聚类的质量。对数据集中任一点计算下列项:

SS:如果2个点属于C中同一簇,且P中同一组;

SD:如果2个点属于C中同一簇,但P中属于不同组;

DS:如果2个点不属于C中同一簇,而P中属于同一组;

DD:如果2个点不属于C中同一簇,且P中属于不同组。

设a,b,c,d分别表示SS,SD,DS,DD的数目,则a+b+c+d=M为数据集中所有对的最大数,即M=N(N-1)/2。其中:N为数据集中点的总数。RI指标的计算方式如公式(9)所示:

(9)

通常,RI值越高,表明聚类算法的结果越精确。

3.2 NUS-WIDE数据集

NUS-WIDE数据集是最大的带有标记的Web图像数据集,包含269,648张图像。每张图像均用文本进行标注。为了验证4种算法的鲁棒性,从NUS-WIDE数据集中随机选取部分图片,构成8个数据子集,每个数据子集含有1万张图片,共14个类。在全部数据子集上进行实验,对每个算法,执行5次实验,聚类结果如图1和图2所示。

图1 聚类结果:E*

图2 聚类结果:RI

图1显示了在整个数据子集上3个聚类算法获得到E*值,从实验结果中可以看到,在大部分情况下,提出的高阶近邻传播聚类算法得到的E*值最小。

图2显示本文提出的高阶近邻传播聚类算法得到的RI值最大,也就是说本文提出的聚类算法聚类结果比HOCPM算法更为准确。

3.3CUAVE数据集

表1 聚类结果

CUAVE数据集中包括36名志愿者,每个志愿者分别读0到9这10个数字5次,构成一个同时包含语音和文本的异构数据集。为了验证本文提出的算法的有效性,为数据集中每个数据对象加上文本标记。在CUAVE数据集上执行每个算法5次,聚类结果如表1所示。

由于CUAVE数据集不存在理想的聚类中心,因此本文通过RI指标评估算法的聚类性能。从表1可以看出,在5次实验中本文提出的高阶近邻聚类算法获得到RI值最大。

4 结 论

本文提出一种基于张量距离的高阶近邻传播算法,用于对异构数据进行聚类。为了能够将异构数据对象进行统一表示,采用张量模型对异构数据对象进行表示。通过在近邻传播算法中引入张量距离度量数据对象在高阶张量空间的相似性,捕捉异构数据的分布特征,提高聚类精度。实验结果表明本文提出的算法能够有效的对异构数据进行聚类,比当前算法聚类精确度高。

[1]李朋,刘天华. 云平台下基于粗糙集的并行算法的研究[J]. 沈阳师范大学学报(自然科学版), 2015,33(2):274-278.

[2]ZHANG Qingchen, YANG L T Y, CHEN Zhikui. Privacy preserving deep computation model on cloud for big data feature learning[J]. IEEE Transactions on Computers, 2015,DOI:10.1109/TC.2015.2470255.

[3]ZHANG Qingchen, CHEN Zhikui. A weighted kernel possibilistic c-means algorithm based on cloud computing for clustering big data[J].International Journal of Communication Systems, 2014, 27(9):1378-1391.

[4]FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007,315:972-976.

[5]郭秀娟,陈莹. AP聚类算法的分析与应用[J].吉林建筑大学学报, 2013,30(4):58-61.

[6]刘晓勇,付辉. 一种快速AP聚类算法[J]. 山东大学学报(工学版), 2011,41(4):20-23.

[7]董俊,王锁萍,熊范纶. 可变相似性度量的近邻传播聚类[J].电子信息学报, 2010,32(3):509-514.

[8]LONG B, ZHANG Z, WU X, et al. Spectral clustering for multi-type relational data[C]∥The 23rd International Conference on Machine learning. New York: ACM Press, 2006:585-592.

[9]MENG L, TAN A, XU D. Semi-supervised heterogeneous fusion for multimedia data co-clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2014,26(9):2293-2306.

[10]GU Q, ZHOU J. Co-clustering on manifolds[C]∥Proc of 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2009:359-367.

[11]BEKKERMAN R, SAHAMI M, LEARNED M E. Combinatorial Markov random fields[C]∥Proc. of European Conference on Principles and Practice of Knowledge Discovery in Databases. Berlin: Springer Press, 2006:30-41.

[12]KUANG L, HAO F, YANG L T, et al. A tensor-based approach for big data representation and dimensionality reduction[J]. Emerging Topics in Computing,IEEE Transactions on, 2014,2(3):280-291.

[13]LIU Y, LIU Y, CHAN K, Tensor distance based multilinear locality preserved maximum information embedding[J]. IEEE Transactions on Neural Networks, 2010,21(11):1848-1854.

[14]ZHANG Qingchen, YANG L T, CHEN Zhikui, et al. A high-order possibilistic c-means algorithm for clustering incomplete multimedia data[J].IEEE Systems Journal, 2015,DOI:10.1109/JSYST.2015.2423499.

[15]HAVENS T C, BEZDEK J C, HALL L O, et al. Fuzzy c-means algorithms for very large data[J]. IEEE Transactions on Fuzzy Systems, 2012,20(6):1130-1147.

A high-order affinity propagation clustering algorithm based on tensor distance

XUANYan1,ZHOUChuansheng2

(1. Software College, Shenyang Normal University, Shenyang 110034, China;2. College of Education Technology, Shenyang Normal University, Shenyang 110034, China)

Affinity propagation (AP) algorithm does not need to specify the number of clustering. When running the program, it can automatically identify the clustering center and the number of clustering. On the same data set, the result of AP clustering algorithm is stable and has good robustness. In addition, AP clustering algorithm can get accurate clustering results by using a variety of distance measuring methods. But current affinity propagation algorithm cannot be applied to heterogeneous data clustering. Aiming at this problem, the paper proposes a high-order affinity propagation algorithm based on tensor distance (HTDAP) for clustering heterogeneous data. The proposed algorithm represents each heterogeneous data object by the tensor, and introduces the tensor distance to measure the similarity between two objects. The tensor distance can capture the distribution features of the heterogeneous data sets in the high-order space by calculating the distance of the numerical values between the objects and measure the difference among the coordinate positions. Experimental results show the proposed scheme is effective in heterogeneous data clustering.

clustering; heterogeneous data; tensor distance; affinity propagation

2015-10-09。

辽宁省科技厅高等学校本科专业设置预测系统研究项目(辽教函[1008]225号)。

铉 岩(1988-),女,内蒙古赤峰人,沈阳师范大学硕士研究生; 通信作者: 周传生(1966-),男,安徽霍邱人,沈阳师范大学教授。

1673-5862(2016)01-0096-04

TP391

A

10.3969/ j.issn.1673-5862.2016.01.022