大数据典型相关分析的云模型方法.pdf

2013 年 10 月 Journal on Communications October 2013 第 34 卷第 10 期 通 信 学 报 Vol.34 No.10 大数据典型相关分析的云模型方法 杨静，李文平，张健沛（哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001）摘 要：针对传统大数据典型相关分析（CCA,canonical correlation analysis）方法的高复杂度在面临大数据 PB 级数据规模时不再适应的现状，提出了一种基于云模型的大数据 CCA 方法。该方法在云计算架构的基础上，通过云运算将各端点云合并为中心云，并据此产生中心云滴，以中心云滴作为大数据的不确定性复原小样本，在其上施以 CCA 运算，中心云滴的较小数据量提高了运算效率。在真实数据集上的实验结果验证了该方法的有效性。关键词：大数据；典型相关分析；云模型；云运算；云计算 中图分类号：TP391 文献标识码：B 文章编号：1000-436X(2013)10-0121-14 Canonical correlation analysis of big data based on cloud model YANG Jing,LI Wen-ping,ZHANG Jian-pei(College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China)Abstract:The complexity of traditional CCA methods is too high to meet the requirements to analyze big data due to their huge scale which is reaching the level of peta-byte.A novel approach to CCA was proposed to mine the big data by introducing the cloud model which is a brand-nowel theory about the uncertainty artificial intelligence.A distributed ar-chitecture based on cloud computing was established.All of the clouds distributing on the nodes of the distributed archi-tecture were combined to a center cloud via cloud operation(where cloud is a synopsis of data and which is a concept coming from the cloud theory).A type of virtual sample of data called cloud drops created based on the center cloud.Fi-nally the computing of CCA was imposed on the cloud drops.The CCA was impose on the cloud drops with less volume,which improves the efficiency.Experimental results on real data sets indicate the effectiveness of this method.Key words:big data;canonical correlation analysis(CCA);cloud model;cloud operation;cloud computing 1 引言 自 2008 年 9 月Nature杂志推出名为“大数据”（big data）的封面专栏1以来，产业界和学术界便掀起了大数据研究热潮。数据量巨大是大数据的首要特性，通常认为PB级别及其以上的数据称为“大数据”。大数据还具有稀疏价值特性，即大数据所携带的信息在刻画某特定知识方面是冗余的。这些特性为大数据挖掘带来了巨大的挑战。大数据典型相关分析（CCA,canonical correla-tion analysis）是大数据研究的重要内容之一，它不仅有助于揭示大数据间的相关关系，而且可提取蕴含于大数据中的低维特征。大数据CCA可用于大数据特征融合2、机器学习3、数据降维4、数据流挖掘5等领域。因此大数据CCA具有重要的意义。大数据 CCA 研究极具挑战性，其困难不仅源于 CCA 本身具有的高复杂度，而且也来自大收稿日期：2013-04-21；修回日期：2013-07-30 基金项目：国家自然科学基金资助项目(61370083,61073043,61073041)；高等学校博士学科点专项科研基金资助项目(20112304110011,20122304110012)；黑龙江省自然科学基金资助项目（F200901）；哈尔滨市科技创新人才研究专项基金（优秀学科带头人）资助项目(2011RFXXG015)Foundation Items:The National Natural Science Foundation of China(61370083,61073043,61073041);The Research Fund for the Doctoral Program of Higher Education of China(20112304110011,20122304110012);The Natural Science Foundation of Heilong-jiang Province(F200901);The Harbin Special Funds for Technological Innovation Research(2011RFXXG015)doi:10.3969/j.issn.1000-436x.2013.10.015 122 通 信 学 报 第 34 卷 数据巨大规模以及稀疏价值等特性。面向传统数据的 CCA 方法的高空间复杂度在面临大数据PB 级规模时已不再适应。针对此问题，本文拟研究一种基于云模型的大数据 CCA 方法，期望该方法能克服大数据巨大规模所带来的高复杂度等困难。云理论是一种实现定量数据和定性概念之间相互转换的不确定性人工智能方法，最早由我国学者李德毅院士提出。云的具体实现称为云模型。云模型在信任评估6,7、时间序列挖掘8以及图像分割9等广泛领域得到了成功应用。然而，将云模型与CCA结合，以用于大数据研究还鲜有学者涉足，本研究拟在此方面展开初探工作。本文首先根据逆向云发生器生成各云端的数据概要；其次将数据概要发送至中心云端，利用云运算操作产生中心云数字特征；最后根据中心云数字特征，利用正向云发生器产生中心云滴，在中心云滴上施加 CCA 操作。中心云数字特征刻画了各云端中数据的语言值，据此产生的中心云滴是原来大数据的不确定性复原小样本。中心云滴在概念粒度上携带了原始数据的重要信息，从这个意义上来说，研究中心云滴不是在原始数据上直接计算，是探讨大数据挖掘的一个良好视角；此外，中心云滴的小样本特性为 CCA 赢得了效率。2 基础知识回顾 2.1 CCA CCA是研究2个随机向量之间相关性的一种常用多元统计方法10。给定p维随机向量X和q维随机向量Y，pq，CCA的目标是寻找投影向量k 和k，使得在方差TTvar()var()1kk=XY的约束下，Pearson相关系数 TTTTT(,)()()xyxxyykkkkkkkk =C X Y C C (1)达到最大值。其中，TTxyyx=CCXY为 X 和 Y 之间的互协方差矩阵，而Txx=CXX和Tyy=CYY分别为X 和 Y 的自协方差矩阵。称TkX 和TkY 为 X 和 Y的第 k 对典型相关变量，其相关系数称为第 k 个典型相关系数。CCA 实质是一个最优化问题。以第一对典型变量为例（省略1和1下标），即求 TTT11,max,s.t.1,1 xyxxyypq =C C C (2)其中，s.t.表示约束条件，为实数域。用拉格朗日（Lagrange）乘子法求解式(2)有 11yyyx=C C (3a)12xyyyyxxx=C C CC(3b)式(3b)是广义特征值问题，由此解出和，代入式(3a)可得。即为所求典型相关系数。CCA 有多种解法，如基于 SVD 的方法等，具体可参阅文献11,12。2.2 云和云模型 设U为定量论域，C为其上的定性概念，若xU 是C的随机实现，且x对C的确定度()0,1x是有稳定倾向的随机数。:0,1,()Uxx 则x在U上的分布称为云（cloud），而x称为云滴（cloud drop）13。云理论用期望Ex、熵En和超熵He3 个数字特征来表征概念的整体定量特性。在不至混淆时，也将云的 3 个数字特征构成的三元组(,)Ex En He称为云。云模型是云的具体实现。由云数字特征产生云滴的实现称为正向云发生器，而由云滴群得到云数字特征的实现称为逆向云发生器。由于正态分布的普适性，建立在其上的正态云是各种云模型中最重要的一种。期望曲线是云理论研究数据集在空间中随机分布统计规律的重要方法，一般方程为 22exp()/2()yxExEn=(4)云运算是云理论中用语言值进行计算和推理的重要基础。给定 2 个一维云1111(,)CEx En He和2222(,)CEx En He，则1C加2C之和(,)C Ex En He可以定义为 1222122212()()()()ExExExEnEnEnHeHeHe=+=+=+(5)需要补充的是，“云”一词有趣地同时光顾了云计算和云理论，为了不至于混淆，本文所述云端皆指云计算平台中的分布式节点或机群，而其他关于云的词汇，特指云理论中的概念。此外，应将云第 10 期 杨静等：大数据典型相关分析的云模型方法 123 运算和云计算区别开来。云运算是云理论中对云进行操作的规则，属于不确定性人工智能范畴；而云计算是一种计算范式，强调计算资源的有效利用和整合，与云运算截然不同。3 相关工作 人类在科研和工程实践项目中收集的大量数据多数具有大数据特性，但将大数据抽象出来作为一门独立科学进行研究还是最近的事14。在生物信息学等领域，Benjamin等人深入研究了在系统神经生物学领域担当重要角色的生理电大数据压缩及存储等问题15；Aronova等人将生物学研究中收集的数据视为大数据，从大科学（big science）视角挖掘这类数据蕴含的重要知识16；Werner则更进一步，从方法论角度分析了如何应对大数据生物学带来的挑战17。在数据挖掘等领域，Alfredo等人从数据仓库和OLAP等视角分析了多维大数据研究存在的问题以及研究趋势18；Steven等人研究了大数据挖掘中的在线特征选择问题19；Simon等人基于模糊查找词典（fuzzy find dictionary）研究了一种面向数据流大数据的数据流聚类方法20；John研究了大数据上的并行学习问题21。在面向大数据的程序开发和存储等方面，Thomas等人探讨了如何在大数据上构建程序实现问题22；Yu等人提出了一种可扩展的用于大数据分析的分布式系统23；Kyuseok以及Jens等人同时探讨了MapReduce架构在大数据分析中的应用24,25；Divyakant等人分析了大数据及云计算现状和研究挑战26；Huiqi等人研究了在云平台上进行可视聚类的一种方法体系27。此外，也有学者开始涉足大数据安全方面的研究，如Colin等人探讨了大数据中存在的安全问题及解决策略28。大数据研究还刚刚起步，尽管有学者探讨了基于云计算平台的大数据存储方法，但未发现关于大数据 CCA 的研究报告，也未发现在此方面基于云理论的研究方法，期望本研究能对此做出些许初探性工作。4 大数据 CCA 方法 本节重点研究基于云模型的大数据 CCA 方法（BDCCA,big data CCA）。首先阐述面向大数据的云架构，其次重点探讨端点云的生成方法，再次研究端点云的合并技术。下文约定运算符,为欧氏内积，而为 Hadamard 积。4.1 面向大数据的分布式云架构 就容量而言，PB 级数据量被认为是大数据的显著特性，这一特性使得大数据一般通过机群等分布式方式存储。迄今为止，云平台是大数据存储的理想载体。本研究假设大数据以分布式方式存储在云端。图 1 刻画了所提出的由若干个云端构成的大数据分布式云架构。此云架构从功能上分 4 层：1）顶层为数据存储层，其中，第i个云端存储第i段数据Datai；2）第 2层为多维逆向云发生器（MBCG,multidimensional backward cloud generator）层，其核心任务在于由原始数据产生各云端的云，即端点云；3）第 3 层为中心云端（center node），该层主要进行云合并运算，并用于产生和存储中心云滴；4）第 4 层为应用层（applications），基于中心云滴，在此层可进行CCA等挖掘或分析任务。在大数据分布式云架构中：1)根据多维逆向云发生器MBCG，由第i个云端中的数据Datai产生端点云(,)iiiiCEx En He，简记为iC；2)将iC传送至中心云端的云收集器（collector）；3)将云收集器中的云传送至多维云合并节点（MCC,multidimensional cloud combiner）；4)根据多维云合并运算，将所有云iC合并为中心云(,)C Ex En He，简记为C；5)将中心云C传送至多维正向云发生器(MFCG,multi-dimensional forward cloud generator)节点；6)根据MFCG，由中心云C产生中心云滴；7)应用层中CCA等任务到中心云端获取中心云滴，并据此进行相应的挖掘任务。此云计算架构用于处理大数据是合适的。1)各云端向中心云端仅传送数据概要，即由云数字特征构成的三元组，如此小的数据量传送是快速的；2)由中心云产生的中心云滴群规模往往较小，这有助于提高 CCA 的运算速度。4.2 BDCCA 执行流程 BDCCA 的基本思路在于：1)在各云端利用逆向云发生器根据当前云端中数据并行生成云（即云数字特征）；2)将各端点云发送至中心云端，利用多维云合并操作，在中心云端产生中心云；3)根据中心云，利用正向云发生器产生中心云滴；4)在中心云滴上施加 CCA 操作。图 2 描述了其执行流程。124 通 信 学 报 第 34 卷 图 1 大数据分布式云架构 图 2 BDCCA 执行流程 第 10 期 杨静等：大数据典型相关分析的云模型方法 125 数据在每个云端分为iX和iY两部分，其中，ip niX和iq niY，in为第i个云端中的样本数目，p为iX的维数，q为iY的维数。特别地，同类数据的维数在所有云端都一致，而样本数目可以不同。此外，云端个数m、各云端标识符iN、云重要度向量T12(,)m=以及中心云滴数目等需预先设定。流程执行结束后，输出典型相关系数向量 以及对应典型相关向量为列的矩阵U、V。基于式(3)，可通过特征分解或 SVD 等方法求解 X和 Y 的典型相关系数和典型相关变量，具体可参阅文献11。本文将采用文献30的多维正向正态云发生器产生中心云滴群(,)xdrop X 和(,)ydrop Y。限于篇幅，此两点不再赘述。图 2 所示流程中，产生各端点云以及在中心云端进行云合并是关键，后文将分别详述这两点，一方面后文将对多维逆向云发生器进行改进，使之适宜于在大数据环境下产生各端点云；另一方面将提出一种一次合并多个多维云的方法，以提高大数据环境下云合并运算的效率。4.3 端点云生成 所谓端点云的生成，是指根据逆向云发生器，由云端中数据产生云的过程。本文采用无确定度的多维逆向正态云发生器30作为端点云的生成模型。尽管已将大数据存储于分布式云架构各云端（如图 1 所示），但是由于大数据的巨大容量特性，在每个云端所存储的数据量往往还较大，现存多维逆向正态云发生器不再满足大数据环境下计算效率的要求，对之加以改进是必要的。为了提高多维逆向正态云发生器在大数据环境下产生云的效率，本文基于随机采样法，采用启发式云生成策略，将多维逆向正态云发生器拓展到大数据情形。4.3.1 大数据随机采样 本文借鉴随机子空间法29思想，在各云端进行大数据随机采样。设各云端将大数据分为若干块，首先对每块按照相同划分方式将其分割成s个子块；然后将所有块中相同位置的子块转换成列向量并进行组合，形成一个子块集，如图 3 所示。基于划分的数据块，在每个子块集上执行随机采样。对第i个子块集iT，根据随机子空间法思想，随机产生*r维索引向量*12,irjjj=I，*rr，则下一次迭代时将加大随机采样的样本容量；反之若iC负向偏离1iC，即1iiCC，则下一次迭代时将减小随机采样的样本容量。其中，0，为常量。此策略的 2 个关键问题在于，其一每次迭代后云的更新；其二相邻两次更新所生成云之间差异的刻画或度量。图 3 数据子块划分 126 通 信 学 报 第 34 卷 4.3.3 云的部分增量式更新 每次迭代后的云更新是云的启发式生成策略需要解决的首要问题。云更新即是云期望11nkkxn=Ex、熵/2n=EA和超熵2enn=HSEE的更新。其中 11|nkkn=A|xx 211()()1nkkkn=Sxxxx 若记 1111=()()|iiiniikkinikikiknikikxn=Exxxxxx|xx(6)其中，in为第i次迭代后的样本1inkk=x总容量，而in为第i次迭代进行随机采样所得的样本1inkk=x容量，显然-1=+iiinnn。云增量式更新的本质在于：用1ixE刻画ixE；根据1i 求解i；由1i 计算i。本研究主要更新前两者，故称为部分增量式更新。设第1i 次迭代后所生成的云为111(,iiiCxnEE 1)ieH，并记第i次迭代进行随机采样所得样本对应的云为(,)iiiiCxneEEH。则第i次迭代后所得云的期望为 11iiiiiinxnxxn+=EEE(7)这只需注意到 11111111111()/iiinikkinniikkkkiiiiiiiiixnnnnnn nnxnxn=+=+ExxxEE 其中，11inikkixn=Ex为样本1inkk=x的均值向量。记211()()=()iinnikikikikk=xxxxxx，1=21()inkik=xx，221=()iixx，并留意到11(inkk=x 1)0i=x，则有 11112211211111221111112()()()2()()()1()=iiiiiinnikikikknnkiiikikknniikikkiin=+=+xxxxxxxxxxxxxx(8)22111211:1111iiiiiiiinnnnn=+=+SS可得 (9)由于绝对值缺乏良好的代数性质，因此要获得A的增量表达式是困难的。本研究在迭代过程中只需跟踪云期望向量ixE和中间向量i 即可，而不需跟踪i 的改变量。定理 1 阐述了其理由。定理 1 令1112=iiiin=+，i=2211211,=(),=()iniikiiik=xxxx。则当0i 时，0i。证明 221211=()0,=()0inkiiik=xxxx，所以当0i 时，120,0，从而有 1111-1-11|=iiinnikikikknkiik=+|xx|xx|xx 所以可得0i。定理 1 表明，若迭代终止条件为相邻两次更新生成云的差异足够小，则只需考察云期望向量ixE和中间向量i 的改变量是否小于给定阈值即可。需要补充的是，云部分增量式更新的根本目的不是为了增量式求解各端点云，而是云生成的启发式策略中进行不重复随机采样时用于判断迭代的终止条件，因为部分增量式更新具有较快的速度。4.3.4 云差异的弦度量 相邻两次更新所生成云之间差异的刻画是云第 10 期 杨静等：大数据典型相关分析的云模型方法 127 启发式生成策略需解决的又一重要问题。由定理 1可知，用云期望向量ixE及中间向量i 的改变量来刻画第i次迭代后所生成云iC与迭代前的云1iC之差异iC是合适的。即 1211212222,iiiixx=EE 其中，2为2l范数，本研究用弦度量定义iC为 1122121222221122(,),(,)(+)(+)iC =(10)这种间接度量方式除了具有相邻云之间差异的刻画能力外，其另外 2 个优点在于：规范性，即0,1iC；异常值的不敏感性，显然ixE和i 对异常值是敏感的，当异常值出现时，可对弦度量对应的 Riemann 球面做一个适当旋转，此旋转对应着异常值的2l范数的一个变换，变换后的值为非异常值，其优势是保持弦度量不变。限于篇幅，本研究不再深入探讨异常值的检测及处理等细节。4.3.5 改进的多维逆向云发生器算法 基于大数据随机采样法以及启发式的云生成策略，本文对无确定度的多维逆向正态云发生器30进行改进，使其适宜于大数据环境下云的快速生成。改进后的算法如下。算法 1 大数据多维逆向云发生器 BDMBCG。输入：子块数目s，初始抽样率0r，云差异阈值。输出：云(,)CxneEEH。1)初始化：将分块存储在当前云端的数据按4.3.1节所述的数据子块划分方式将其分割成s个子块，并求每个子块大小0s，置0 0nr s=，置r为小于n的随机正整数。2)进行两次容量分别为n和r的不重复随机采样，并根据式(6)计算均值向量0 xE和1xE以及中间向量0 和1，再根据式(10)求云差异C。3)WHILE C且数据未抽样完时。4)01xx=EE，01=，+nn r=。5)执行容量为r的不重复随机采样，当所剩样本不足r时，抽取剩余样本的12。6)根据式(7)更新1xE，并根据式(8)更新1。7)根据式(10)求云差异C。8)IF /2CC 9)产生小于 r 的随机正整数 t，并置r=t；10)ELSE 11)产生介于(r,s0)之间的随机正整数t，并置r=t；12)ENE 13)置CC=。14)END /End While 15)2111n=S，11|nkkn=A|xx。16)21,/2,xxnenn=EEEA HSEE。算法 1 的最后两步表明，尽管云部分增量式更新的根本目的不是为了增量式求解各端点云，但却达到了部分增量式求解的目的，因为求解云(,CxE,)neEH时，只重新计算中间量A，其余量直接应用算法在启发式迭代过程中增量更新的值。注：1)算法 1 在各个云端执行，本研究假设数据X和Y作为云端公共变量可直接访问，因此算法输入省略此数据项；2)每个云端数据X和Y的容量往往不相等，由于 CCA 要求输入的两组样本容量一致，因此算法执行后还需进行一次随机采样，其操作在小样本容量对应的数据上进行，所抽取样本量为算法 1 执行后获得的两组样本量之差值。4.4 多维云合并 在式(5)对应的云合并运算中，每次仅能进行一对云加法运算，如果通过反复调用方式每次合并一对云，每合并一次，云的总个数仅减少一个，因为新生成的云还需要加入合并操作，这在云端较多时将增大时间开销，特别在大数据环境下，其效率会遭受质疑；另一方面，式(5)也未顾及 2 个云重要性的差异，在大数据环境中，由于受数据收集或存储策略等差异的影响，不同云端的数据可能存在重要性差异，因此各云端传送到中心云端的云的合并应体现各云端之差异。针对前述不足，本文借鉴文献30用于概念粒度提升的跃升策略的相邻云合并思想，提出了一种适宜于大数据的云合并运算方法。给定 m 个p维云(,)iiiiCxneEEH(1,2,i=)m，以及刻画每个云重要度的向量12(,=128 通 信 学 报 第 34 卷 T)m，1i=，记 12(,)xmxxx=MEEE 12(,)nmnnn=MEEE 12(,)hmeee=MHHH 111(),(),()jjjxpnpepxeneeh=EEH。若合并后的云为(,)CxneEEH，则有 ,/,/jnnjixxnjiehneeehe=rrrrr (11)其中，1,2,jp=，=nnjrM 1，Txxj=rM 1，h=r ThjM 1，=rnr，而j1为第j个元素为 1，其余元素为 0 的p维单位列向量。()jnnip me=M求解方法为：令(,)jjjjixinieiCeeh为第i个p维云iC的第j个维度构成的一维云，其期望曲线方程为()jiyx。设 (),()(),1,2,()0,jjjiikjiyxyxyxkpyx =若其他 则有 1()d2jjniiUeyxx=其中，U为第i个p维云iC的第j个维度对应论域，1,2,;1,2,im jp=。与已有方法相比，本文提出的云合并方法呈现出 3 个特点：1)能对各云端传入中心云端的云进行一次性合并；2)云合并中体现了不同云端的重要性差异；3)合并的是多维云，而非一维云。5 仿真实验及结果分析 5.1 实验数据及仿真云平台 实验涉及 3 个数据集。1)带噪声的线性数据集 LN：这是一个合成数据集，数据X和Y每个属性来自于线性数据，然后叠加符合高斯分布 N(1,2)的样本扰动每个属性值。每次产生的数据包括 10 个维度。2)真实数据集 PAMAP2：这是对 18 个不同物理活动进行监视所收集的数据（http:/archive.ics.uci.edu/ml/datasets/PAMAP2+Physical+Activity+Mon-itoring），包括3 850 505 行记录，含52 个属性。实验选取的属性为惯性测量单元 IMU（inertial mea-surement units），前两组实验选取手部 IMU（IMU hand）的前 10 个属性，而第三组实验将手部 IMU作为一组（包括 17 个属性），而胸部 IMU（IMU chest）作为另一组（包括 17 个属性）。3)真实数据集IDS：网络入侵检测数据集IDS31记录了网络链接中正常链接和攻击性链接（intrusions or attacks）的行为数据，共包括494 021 条记录，含41 个属性。实验选取其中的连续属性（包括 34 个）进行测试，前两组实验选取前 10 个属性；第三组实验将前12 个属性为一组，其余为另一组。实验前已删除数据集中具有缺失值的记录，且对每个属性在均值 4 倍方差外的值用均值替换。CCA 以及多维云发生器对数据约束较少，一般认为，只要总体接近正态分布的实数都可采用。选择 PAMAP2 和 IDS 数据集的理由在于它们是得到大量文献广泛采用的标准数据集，而且其容量较大，已接近仿真实验平台的资源上限。实验从上述 3 个数据集中选取的每个属性都是总体接近正态分布的实数。图 4 是从 PAMAP2数据集手部IMU中随机挑选出的两列数据（IMU6和 IMU12）的分布直方图。数据已规范化为均值0，方差 1。设置了 25 个云端，将数据均分为 25个相邻块，每个云端分配一块。其中，图 4(a)为总体分布直方图，而图 4(b)图 4(c)和图 4(d)分别为第 3 号17 号和 23 号云端中的数据分布直方图。由图 4 可以看出，不论是总体数据还是分配到各云端的数据都接近正态分布；此外，不同云端的均值偏移不同，且方差范围有所区别，此现象说明4.4 节研究多维云合并是必要的。笔者在做本实验前还对手部 IMU 其他属性、胸部 IMU 的各属性以及 LN 和 IDS 数据集的连续属性都进行了类似的分布情况观察分析，结果与在 IMU6 和 IMU12 上的观察结果相似，篇幅所限，不再赘述。因此，尽管所选数据集与真实大数据在容量上有一定的差异，但就仿真而言，数据容量数据总体分布和各云端的数据分布等都有一定的代表性。实验在单台微机上通过仿真完成。为仿真数据在各云端的存储，实验为每个云端创建一个文件夹，每个文件夹下存储若干纯文本文件，每个文本文件存储一个数据块。每个实验开始前，先将各数据集切分为相邻块并存储到对应文本文件中。实验为每个云端启动一个独立线程，所有云端第 10 期 杨静等：大数据典型相关分析的云模型方法 129 对应线程并行执行。每个线程从所属云端对应文件夹下读取相应数据，并分配一块内存用于存储相应数据。各线程根据读取的数据生成各端点云。若内存资源不足时，正在读取数据的线程挂起，当内存资源可用时再唤醒。在需计算运行时间的实验中，线程从挂起到唤醒所耗时间忽略。图 4 IMU6 和 IMU12 分布直方图 为中心云端启动一个独立线程，并分配一块互斥访问的内存，用于存储各云端传回的云。当所有端点云都传回后，中心云端对应线程基于此内存块中的云完成云合并、中心云滴产生以及 CCA 运算。实验通过 C#语言实现，在 Microsoft Visual Studio 2010 Ultimate-CHS 环境中完成，作图工具选用 MATLAB R2011a。实验计算机配置为双核 2.8 GHz CPU、4.0 GB 内存，操作系统为 Windows 7 Professional。5.2 实验一：各参数对端点云生成的影响 为验证本文改进的多维逆向云发生器 BDMBCG的有效性，本实验评估各参数对端点云生成的影响。为叙述方便，将改进前的多维逆向云发生器记为 MBCG。由于 BDMBCG 在每个云端运行，因此本组实验设置云端数目为 1，即在 1 个云端观察，并设数据集在每个云端分为 10 块存储。需考察的参数包括数据子块数目s、初始抽样率0r和云差异阈值。实验将云(,)CxneEEH视为3p上的子空间，p为维数，用算法改进前计算出的云1C和改进后所得的云2C对应的列子空间11col()=SC和22col()=SC的距离12(,)d S S作为误差error的度量，定义为 12122(,)errord=SSS SPP(12)其中，H1H()iiiii=SPC C CC为到iC对应的子空间iS上的正交投影算子，1,2i=。需要补充的是，式(12)与式(10)刻画的 2 种云差异的区别：条件不同，式(12)需求出云期望、熵和超熵后才有意义，而式(10)只需给出云期望向量和中间向量；目的不同，式(12)用于直接度量2 种算法产生的云之间的差异，而式(10)用于间接度量同一算法在云部分增量式更新过程中相邻时刻产生的云之间的差异。由于算法 1 执行后云已经生成，因此用式(12)刻画BDMBCG生成的云与MBCG生成的云之间的差异是合理的。由上述两点区别得出的结论是，引入式(10)和式(12)是必要的，而且不可用一方代替另一方或交换其位置。每组实验重复 100 次，以观察不同参数下云的平均差异和计算时间。每次生成 LN 数据 200 000 条记录，每条记录包括10 维；从PAMAP2 数据集随机抽取200 000 条相邻记录，其属性选取为手部 IMU 前10 个属性；并从 IDS 数据集中随机抽取 200 000 条相邻记录，其属性选取前 10 个连续属性维度。130 通 信 学 报 第 34 卷 首先，考察数据子块数目s对生成云的影响及计算时间的差异。初始抽样率00.35r=，云差异阈值0.1=。图 5 为误差比较图，而图 6 为 3 个数据集上的平均计算时间比较图。图 5 不同子块数目下所生成云的误差 由图 5 可见，随着子块数目s的增大，误差逐渐减小。当s增加到 1 000 时，误差已接近 0.05。此现象表明，适当增大子块数目有助于提高计算精度。但图 6 却表明，随着子块数目的增大，BDMBCG 所需时间略有上升。因此在一定精度范围内，子块数目选择适中为宜。此外，真实数据集 PAMAP2 和 IDS 上的误差比合成数据集 LN 上的误差略小。图 6 不同子块数目下平均运行时间 其次，评估初始抽样率0r对生成云的影响。数据子块数目400s=，云差异阈值0.1=。图 7 为误差比较图，而图 8 为不同初始抽样率0r的平均运行时间。图 7 不同初始抽样率下所生成云的误差 由图 7 可以看出，在00.3r 时各数据集上误差都较大；当0r在 0.200.45 范围内时，误差下降趋势明显；而此后误差逐渐接近 0.05 左右，且波动较小，其趋势几乎延续到00.8r=。但是，并不是初始抽样率越大越好，观察图 8 可以发现，当0r变小或增大时，3 个数据集上平均运行时间持续增加。图 8 不同初始抽样率下平均运行时间 再次，观察云差异阈值对生成云的影响及计算时间的差异。初始抽样率00.4r=，数据子块数目400s=对。图 9 为误差比较图，而图 10 呈现了 3 个数据集上的平均运行时间。由图 9 可以看出，当0.15时，误差持续增大。图 10 表明，生成云的平均运行时间随着云差异阈值的增大不断减少。结合两图观察发现，当介于0.08,0.15时，能获得一个兼顾较低误差和较少运行时间的折中方案。图 9 不同云差异阈值下所生成云的误差 图 10 不同云差异阈值下平均运行时间 第 10 期 杨静等：大数据典型相关分析的云模型方法 131 5.3 实验二：多维云合并运算的效率分析 本实验将式(5)对应的原始云合并方法（记为“original”）与本文提出的一次性合并多个多维云的云运算方法（如式(11)所示，不妨记为“new”）进行比较，评估不同云端数目对云合并效率的影响。对于式(5)对应的原始云合并，通过反复迭代，每次合并 2 个云，将前一次合并后的云加入当前云的集合再次合并，直至最终合并为一个云为止。对于同一云端数目icn，实验重复进行 50 次。第i次实验中，云重要度皆为1/icn。每次实验生成维数为 10 的 LN 数据5210icn 条记录；并从PAMAP2 数据集和 IDS 数据集中各随机抽取52 10条相邻记录icn次，属性选取与实验一相同。按抽取顺序将数据平均分配到icn个云端。之后在每个云端并行调用算法 1 的 BDMBCG(400s=、00.3r=、0.1=)生成每个端点云，并将生成的云传回中心云端。本实验仅仅评估在中心云端上合成中心云的效率。图 11 为不同云端数目下，在 3 个数据集上云合并的平均运行时间比较图。由图 11 可以看出，随着云端数目的增大，原始的云合并操作所需时间迅速上升，而本文提出的一次性合并多个多维云的操作所需时间上升幅度却相对较小。此现象表明，本文提出的云合并操作对于所提出的大数据分布式云架构是合适的，云端数目增大并未显著提高云合并的时间开销。图 11 云合并运行时间比较 5.4 实验三：BDCCA 的有效性评估 为验证本文所提BDCCA的有效性，本组实验将 BDCCA 与 经 典 CCA（记 为 NaiveCCA）、ApproxCCA32和LS-CCA33进行对比分析，考察不同云滴群大小、不同云端数目以及不同数据总容量下，典型相关系数的精度以及BDCCA的执行效率。典型相关系数的精度用其误差error刻画。error定义为 NaiveCCA 在原始大数据上所得典型相关系数NavieCCAr分别与其他几种方法所得典型相关系数之差的绝对值，即 NavieCCA0errorrr=(13)其中，0r取BDCCAr、ApproxCCAr或LS CCAr。BDCCAr表示BDCCA 在云滴群上所得的典型相关系数，而ApproxCCAr和LS CCAr分别表示 ApproxCCA 和 LS-CCA在原数据上所得的典型相关系数。基于 BDCCA 求典型相关系数的过程为：对于每个实验，首先在每个云端并行调用算法 1 的BDMBCG 生成每个端点云，并将生成的云传回中心云端；其次根据式(11)进行云合并；第三采用文献30中的多维正向正态云发生器产生中心云滴群(,)xdrop X 和(,)ydrop Y；最后在X和Y上执行CCA 操作。本节所有实验在每个云端前两步的参数设置同实验二，且所有实验在数据集 PAMAP2 和 IDS上进行。在 PAMAP2 数据集上，实验将手部