一种基于动态降维的数据约简方法
2017-02-25陈衡
陈 衡
(淮北职业技术学院 教务处，安徽 淮北 235000)
一种基于动态降维的数据约简方法
陈 衡
(淮北职业技术学院 教务处，安徽 淮北 235000)
根据数据处理形式的不同,提出基于动态降维的数据约简方法和多维度动态降维算法。通过引入数据冗余删除理论，降低数据的冗余程度；采用数据降维技术，实现数据清洗，数据结构并行，提升核心数据的知识表示能力。最后通过实验验证了本方法的有效性。
数据降维；数据约简；数据优化
大数据是大规模聚合的多格式自主异构数据源。[1]大规模海量数据是大数据的首要特征，数据信息的获取依赖于大规模数据中心和存储区域网络结点。海量的大数据不仅导致数据具有异质性，也使得数据具有互不相同的维度属性。因此，最大程度的减小大数据的数据规模，提高有价值数据比，显得尤为迫切。[2]此外，为了避免存储和处理横向资源的消耗，大数据流需要在线处理。高速性大数据处理是其第二个关键因素。高速性指的是处理数据流的高频率，例太阳能动力学天文台每天产生超过1T字节的数据，只有在约简或数据压缩之后，快速大数据分析才可能实现。另一方面，大数据集所带来的维数灾难，使得数据表示与计算十分困难。为了最大限度地挖掘有效知识模式，数百万的相关维度信息(包括变量，特征，属性等)需要在不影响原始语义的前提下，尽可能多的简化。如研究互联网用户的搜索概况，必然涉及用户行为的配置文件，该文件是包含搜索、页面浏览和点击流数据的稀疏矩阵，具有高维度的搜索关键字和网址。[3]类似地，个人基因组高通量测序不仅增加了数据的容量，降低了处理速度，也会带来数据维度的增加。[4]因此，有必要降低大数据的维度，同时保留最重要且有价值的数据信息。
1 相关理论
1.1 冗余删除理论
大数据分析的关键环节是解决数据冗余问题。引起数据冗余的三个主要环节是数据添加重复节点阶段、扩展数据集阶段以及数据复制阶段。对于存储机制而言，在集群级别的最大可用性数据必然会引起数据冗余。因此，有必要删除重复数据，研究冗余消除方法。
面向集群的重复数据删除的核心是基于磁盘备份的大数据聚类备份系统。存储在多个磁盘和分区上的冗余数据需要大数据处理系统具备分布式集群处理能力。重复数据删除技术使用散列函数，处理不同的数据块(分区)，降低节点内与节点间的通信开销，提高存储效率。大规模集群重复数据删除面临的主要问题：由于信息过载，仅仅删除服务器级别的重复数据，无法完全降低通信开销。研究解决信息孤岛中数据路由，显得尤为重要。另一个核心环节是磁盘组索引查找问题，即在频繁的随机I / O查找和索引过程中，解决好大型数据集的重复块索引同时，兼顾维持系统内存的开销，降低客户端备份负载。
重复数据删除技术基于簇中局部数据相似性，主要涉及有状态或无状态路由选择，对重复数据的位置进行判断，将类似的数据传输到同一节点或分发到整个集群的相同节点，降低通信开销，并执行相应优化操作。[5]为了降低通信和删除无效节点间重复数据的系统开销，采用基于混合技术的理论与方法。综合使用基于相似性和局部优先理论，重点解决节点间重复数据的过度删除问题，同时平衡了数据删除与集群可扩展性之间的关系。使用归一化重复数据删除率，评价上述理论的计算效率，可用公式1表示：
( 公式1)
其中P和L分别表示数据集的物理空间和逻辑空间， T表示用于重复数据删除的处理时间。此外，DT表示重复数据的删除吞吐量，DR表示总体重复数据删除率。归一化的有效重复删除比率(Normalized Effective Reduplication Ratio，NEDR)用于衡量群集范围内重复数据删除和存储的不平衡程度，如公式2所示：
( 公式2)
公式2中，CDR表示集群级重复数据的删除比率，SDR表示单节点级重复数据的删除率。α表示存储空间的平均使用率，而σ表示群集范围的存储使用标准偏差。
相比之下，系统在处理具有相同习惯的移动用户数据时，生成大量相似的冗余数据量以及大量缺乏时空相关性的感知数据。面向移动网络的数据转发框架，消除采样网络的冗余以节省资源消耗。框架以两个数据转发协议为核心，即基于Epidemic融合路由协议以及二进制发散与等待融合协议(Binary Spray and Wait with Fusion，BSWF)。模拟感知数据的智能融合以消除冗余。重复数据删除技术能够在不同的环境中处理不同级别的数据集合，包括移动网络、集群、云和数据中心等。因此，具体的应用模型是确定选择何种方法的关键。
1.2 模糊分类理论
模糊分类方法能够有效解决医疗大数据的结构化提取问题，主要涉及大数据流的存储以及临床医学知识模式的挖掘等领域。基于自主选择的对冲模糊分类器(LHNFCSFs)[6]用以减少数据尺寸，增加选择功能，并执行分类操作。该分类器在自适应模糊神经网络中，通过整合分类器以及过滤嘈杂冗余数据，加强了特征空间的表达能力，提高了分类器的精度。结果表明，通过减少医疗大数据维度问题，提高数据分类性能。
张量是用高维数据进行多维表示的量纲工具，基于矩阵角度分析，则是对多阶方阵进行多线性运算，即相同的参考量在不同的坐标中，按约定准则进行变换。处理大张量问题是一个具有挑战性的任务。张力分解(Tensor Decomposition ，TD)能够将高维数据分解成若干规模较小但具有代表性的张量。TD主要分成三类，包括典范分解(Canonical Polybasic Decomposition ，CPD)，塔克分解(Tucker decomposition)和张量链(Tensor Trains ，TT)。TD方案规定了张量分解的约束，这些分解方案降低了大数据集的维度并建立张量之间的互连张量网络(Tensor Networks ，TNs)。利用最优化算法寻找因子矩阵并用线性和非线性最小二乘法进行优化。张量分解策略与聚类分析、层次分类、数据融合、异常检测、模式识别、数据集成、时间序列分析、预测建模以及多向组件分析等理论结合，用于降低大型科学计算中的维度。特征哈希散列(Feature Hashing，FH)通过随机分配的方法，将实际空间中的特征集映射成低维空间的新维度。通常，所有降维技术都会降低数据质量。
由于大数据流的输入会引起高维特征空间膨胀，特征提取方法(Feature Extraction Methods，FEM)需要占用内存中的整个数据空间，增加了计算的复杂度，降低分类器的整体性能。增量偏最小二乘法(Incremental Partial Least Squares，IPLS)是偏最小二乘法的变体，该方法有效地减小了大规模数据流的维度，提高了分类精度。算法过程可表示为：采用目标函数进行历史数据更新，获取主要数据投影方向；通过基于克雷洛夫序列和偏最小二乘支持向量机之间的等价关系，计算其余数据的投影方向。通常将IPLS与增量类间散射方法和增量最大间距技术等结合，用于增量测准。结果显示IPLS改善了计算的精度，提高了计算性能。
2 基于数据降维的约简算法
2.1 数据预处理
数据预处理是大数据处理的第二个重要阶段，主要方法是基于语义分析 (使用本体)或关联数据结构。其核心是利用低内存预滤波器处理数据流、URL以及基因组数据，结合二维峰值检测方法降低数据规模。
大数据约简可以过滤Internet安全应用程序中的恶意URL[7]。文献[7]中提出了两种特征缩减技术，提取特征词汇，描述特征结果。然而词汇特征识别需要首先解决恶意URL地址信息不断发生改变，检测软件难以搜索的问题。选择被动攻击性(用于密集特征提取)和置信加权算法(用于稀疏特征提取)作为在线学习算法，通过训练模型，提取特征信息。
数据预处理技术高度依赖于大数据的性质，目前领域内尚无有效的统一处理大数据流的理论与方法。
2.2 数据降维算法
由于大量数据流的出现，引起了数据“维数灾难”，即数以百万计的数据变量和维度表示，增加了存储和计算大数据的时间复杂度。面向不同应用背景的数据降维方法能够有效降低数据维度，主要有基于聚类分析方法、分布式计算方法、特征选择技术、模糊逻辑实现技术、分布式尺寸缩小方法以及模糊逻辑分析等。
动态量子聚类算法(DQC)能够实现可视化高维数据展示。[8]在高维特征空间中，基于密度分析相关变量数据的子集。DQC支持并行环境中的高度分布式数据处理，具有良好的可扩展性。DQC其核心是通过构造一个潜在代理函数来估计数据点的密度，即概率密度函数的估计。应用于n维特征空间，以每个数据点为中心的高斯函数的和(参见公式3)。 DQC还定义了一个满足薛定谔方程的向量函数(见公式4)，利用势能定义哈密尔顿算子函数，从子集中计算高斯函数并将结果乘以量子时间进化算子，然后计算每个中心的高斯函数。大型复杂的数据集可以在没有任何先验假设或使用任何专家信息的前提下，进行计算分析。此外，DQC还可用于噪声数据识别，以消除不重要的属性，进而应用于大数据分析领域。
(公式3)
( 公式4)
势函数可以定义在相同的n维特征空间，为函数满足时间独立的薛定谔方程。传统的降维算法使用高斯最大似然估计，只能处理20,000个变量以内的数据集。通过应用平行分治策略，可以将特征空间应用到一百万个变量，实现数据降维。所提出的算法是高度可扩展的且计算效率高于现有算法，如Glasso算法和ALM算法。[9]
数据集的知识发现具有很大的挑战性。基于分布式k-均值的降维算法，克服现有的大规模并行架构的局限性，采用局部还原技术，改进计算性能。减少的数据量估计表示为公式5。
( 公式5)
通常，在线学习技术能充分发挥其输入端的功能优势，但当处理高维特征空间时，整体效率较低。在线特征选择(Online Features Selection，OFs)方法，对输入端的数据规模加以限制，在线学习者只能使用固定长度的工作集，进而减轻系统负载。基于稀疏正则化的数据截断技术，研究了活动特征的选择预测算法。在批处理模式下，该算法优于UCI数据集的RAND和PEtrun算法，在线学习模式效率较高。[10]
数据核心集是基于大数据的约简后的精简集，具有与原数据集相同的信息表示能力。核心集的属性因知识发现算法的不同而有所区别。例基于k分量数据图的核心集能够表示大数据中的所有k分量的数据集。同样，包含K聚类半径R的核心集则代表具有相同半径的k簇近似大数据。使用k-均值、主成分分析(Principal Component Analysis，PCA)和投影聚类等算法，将大规模并行数据流映射成核心数据集组件，将大数据减小到可管理的规模，降低了总体数据的复杂性。[11]
多维度数据动态降维算法(Multi-dimension Dynamic Dimensionality Reduction algorithm，MDDR)的步骤描述如下：
输入 数据列表List
输出 Ci表示动态更新后的数据信息权重，i表示数据列表List的维度
1)计算原始数据List的数据维度，记为i；
2)对于n维特征空间，以每个数据点为中心的高斯函数的和，利用公式3计算，记为ηi；
3)依据公式4，计算每组数据的向量函数，获取每组数据的中心高斯函数，记为Gi；
4)结合基于分布式k-均值的降维算法，计算降低后的数据量估计值，记为Ki；
5)依次遍历出每组数据的中心高斯函数值，判断该数值Gi是否小于Ki，若小于该数值，则输出数据列表List的维度集i。
3 实验与分析
为验证本文MDDR算法的有效性，本节将设计对比实验，以分析比较该方法的优缺点，实验结果进行有效性分析。
数据约简的评价指标涉及数据约简的准确率和召回率。其中准确率表示约简数据集与初始测试数据集合的维度比率，表示为公式6。
( 公式6)
上式中，L是初始数据集的维度数值， Nt表示约简后的数据维度。
召回率定义为数据列表中用户选择的数据维度与初始数据集维度的比率。表示为公式7。
( 公式7)
本文选取数据分析的常用数据集DataCrossing模拟实验数据集信息。并将MDDR算法与RED编码算法、并行压缩算法以及Sketching算法做对比分析。设置数据列表的长度分别是1TB，10TB，100TB。实验结果如图1、2所示。
通过分析实验结果，在数据量为1TB和10TB时，在准确率和召回率上较其他方法性能较高，但在数据量达到10TB时，性能指标在准确率和召回率上，数值低于RED压缩算法，但优于剩余算法；MDDR算法的整体波动性较其他算法较大。本算法在处理小规模数据时，性能较稳定，而处理数据量较大时，算法稳定性相对一般。本算法下一步的改进方向是通过优化本模型的动态参数设置方法，获取自适应的阈值参数，达到参数的动态平衡，以提升模型处理较大数据量的稳定性。
[1]Wu X et al. Data mining with big data. IEEE Trans Knowl Data Eng.2014 ,26(1):97-107.
[2]Che D, Safran M, Peng Z . From big data to big data mining: challenges, issues, and opportunities. Database systems for advanced applications .2013,14(2):98-104.
[3]Battams K.Stream processing for solar physics: applications and implications for big solar data. arXiv preprint arXiv. 2014, 10(1):140-150.
[4]Zhai Y, Ong Y-S, Tsang IW.The emerging ‘‘big dimensionality’’.Comput Intell Mag IEEE.2014,9(3):14-26.
[5]Fan J, Han F, Liu H . Challenges of big data analysis. Nat Sci Rev 2014,1(2):293-314.
[6]Ward RM et al .Big data challenges and opportunities in high-throughput sequencing. Syst Biomed .2013,1(1):29-34.
[7]Weinstein M et al. Analyzing big data with dynamic quantum clustering. arXiv preprint arXiv: 2013, 4(5):131-139 .
[8]Hsieh C-J et al .BIG & QUIC: sparse inverse covariance estimation for a million variables. In: Advances in neural information processing systems , 2013,11(5):151-162.
[9]Vervliet N et al . Breaking the curse of dimensionality using decompositions of incomplete tensors: tensor-based scientific computing in big data analysis. IEEE Signal Process Mag .2014,31(5):71-79 .
[10]Feldman D, Schmidt M, Sohler C . Turning big data into tiny data: constant-size coresets for k-means, pca and projective clustering. In: Proceedings of the twenty-fourth annual ACMSIAM symposium on discrete algorithms ,2013,20(15):171-182 .
[11]Dong W et al .Tradeoffs in scalable data routing for deduplication clusters. Information Processing Systems .2015,13(20):150-162 .
Class No.:TP391 Document Mark：A
(责任编辑：宋瑞斌)
Data Reduction Method Based on Dynamic Dimension Reduction
Chen Heng
(Huaibei Vocational Technical College， HuaiBei, AnHui 235000，China)
According to the different forms of data processing, a data reduction method based on dynamic dimension reduction is proposed. By introducing data redundancy, the degree of data redundancy is reduced. The data reduction techniques is proposed to achieve the aims of data cleaning, and finally the optimization algorithm of multi-dimension dynamic dimensionality reduction algorithm are put forward, which enhances the core capability of knowledge representation. The validity of this method is verified by experiment.
data dimension reduction; data reduction; data optimization
陈衡，硕士，讲师。淮北职业技术学院。研究方向：计算机应用。
安徽省高校质量工程项目(2013sxzx033)；安徽省高校质量工程项目(2015zjjh051)；淮北职业技术学院自然科学重点项目(2016A4)。
1672-6758(2017)03-0020-5
TP391
A
