数据流降维算法研究

作     者：单燕 

作者单位：南京邮电大学 

学位级别：硕士

导师姓名：李玲娟

授予年度：2016年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：数据流 降维 线性主成分分析 非线性核主成分分析 Storm平台 

摘      要：随着现代信息技术的发展,数据流作为一种新型的、更切合实际的数据模型广泛出现在众多应用领域,各种应用已提出了数据流实时处理需求。由于数据流中的数据经常呈现高维性,其中包含的大量冗余特征会极大地影响机器学习和数据挖掘算法的效率。降维算法作为高维数据预处理的重要方式之一,可以有效地消除冗余特征,改善挖掘算法的效率和性能。但是传统的降维算法已无法满足数据流的实时性处理要求,因此针对数据流的特点,采用合适的数据结构,研究有效的数据流降维算法,已成为目前数据流管理研究的一个热点。为此,本文针对数据流的特点,分别研究了适用于数据流的线性降维算法和非线性降维算法。首先,本文深入研究了经典线性降维算法PCA,分析了其在处理的数据类型及时间效率等方面的不足,结合数据流的实时性、无限性等特点,提出了一种基于主成分分析的数据流降维算法(Data stream dimensionality reduction algorithm based on principal component analysis),简称SPCA,此算法利用滑动窗口和概要结构适应动态数据流变化,不仅能有效地消除数据流中的冗余特征以实现降维,而且可以有效地处理混合属性的数据。其次,本文基于所设计的SPCA算法,进一步改进了主成分分析的相关系数矩阵计算公式,并将改进的相关系数矩阵的计算过程和线性投影阶段进行分布式并行,设计了分布式并行化的数据流降维算法DPSPCA(Distributed Parallel SPCA),并将DPSPCA算法部署到分布式流平台Storm上进行实现和测试,性能测试实验结果表明,DPSPCA能有效提高数据流降维的效率和速度。最后,为了满足数据流的多样性,弥补SPCA算法只能处理线性数据的不足,本文设计了基于核主成分分析(KPCA)的数据流非线性降维算法(Data stream dimensionality reduction algorithm based on kernel principal component analysis),简称SKPCA。同样针对数据流的特性,对核主成分分析算法做了适当改进,通过设定阈值来判定动态数据流流量,针对不同的流量选择不同的方法计算核矩阵,然后再进行核主成分分析。综上所述,本文对数据流降维算法的研究具有一定的理论性和较高的实用价值。所设计的算法不仅能降低数据属性的维数、减小空间需求、提高处理效率,而且具有良好的性能,能提高后续数据挖掘的效率。借助数据流处理平台,算法效率可进一步提高。