高维数据可视分析中维度及数据布局方法研究

摘要

科技的发展使各行各业都能轻易的收集到海量的、动态的高维数据，如何高效的处理、分析和可视化这些高维数据成为当今的一个研究热点。
　　在高维数据处理方面，回归分析是利用数理统计的方法来揭示两种或多种维度之间的相互依赖关系（相关性），如果存在这种关系，那么在可视化时，所有的样本都会以某种趋势展现出来，如果不存在这种关系，那么可视化的效果就是一群离散点;聚类分析是将数据集中的样本按照一定的关系，划分为几个组，同一个组中的相似性很大，不同组之间的相似性很小。
　　平行坐标[1](Parallel Coordinates)是一种成熟的高维数据可视化方法，可以精确地显示样本在各个维度上的分布情况;雷达图[2](Radar Chart)作为平行坐标的变形，经常应用于财务、气象、多指标分析等多维数据的可视化中;RadViz[3](Radial Coordinate Visualization)作为雷达图的改进形式，是一种基于圆形平行坐标的可视化方法，将高维数据的维度以点的形式均匀的投影到二维平面的单位圆周上，样本数据同样以点的形式投影到同一个圆中，可以清晰地观察样本的分布情况。
　　在RadViz图中，高维数据的维度均匀地投影到圆周上形成维度点，它不能显示维度之间的相关性特征，为此我们提出了一个基于MDS(Multidimensional Scaling)算法[4][5]和一个基于TSP(Travelling Salesman Problem)算法[6]改进RadViz图中维度投影到平面上的布局方法，首先以Pearson相关系数[7]建立维度相关性矩阵（矩阵中的每个元素是对应数据维度之间的相关系数），再通过变换函数将维度相关性矩阵变换为平面上维度点之间的欧氏距离矩阵（矩阵中的每个元素是平面上维度点之间的欧氏距离），再采用TSP算法将维度投影到固定长度的线段上成为维度点，然后将该线段映射到平面的单位圆周上，从而得到数据维度向平面点的投影，最后采用CM(Circle Move)算法调整维度点在圆周上的位置，使全局应力误差最小，从而实现RadViz方法中对维度相关性的展示。
　　在采用MDS算法调整RadViz的维度点布局时，同样先将维度投影到一维线段上并映射到单位圆周上，实现数据维度向平面点的投影，再采用CM算法调整维度点在圆周上的位置，使应力误差最小，从而实现RadViz方法中对维度相关性的展示。维度点在平面上的位置确定后，我们再采用广义重心坐标GBC[8](Generalized Barycentric Coordinates)的方法，将样本点投影到圆中实现RadViz的可视化。
　　我们还分别对MDS算法中距离矩阵的PTI(Proportion of Triangle Inequality)指标，点的初始位置生成方法和点位置的调整策略三个方面，与全局应力误差值之间的关系进行详细的讨论，并提出了改进MDS算法，进一步降低全局应力误差值的方法。1）我们定义了距离矩阵的PTI指标，然后随机生成了多个PTI值不同的距离矩阵，并根据MDS算法进行一维和二维的降维计算，获得相应的全局应力误差，得出了PTI指标和对应的全局应力误差之间的反相关关系，从而提出了在服从距离矩阵中的数值大小单调性约束的条件下，对距离矩阵中的数值进行幂函数运算，以提高PTI指标，降低MDS算法降维过程中的全局应力误差;2)针对Random方法实现点的初始位置生成的方式，导致MDS算法的最终结果不可复制的问题，我们提出了一种基于TSP(Travelling Salesman Problem on Circle)算法实现点的初始位置生成和一种基于DRGT(Delineated Range and Generated in Turn)算法实现点的初始位置生成来替代Random方法，从而实现了实验结果的可复制性;3）针对位移策略中力导向算法不收敛的问题，我们设计了SEFM(Systematic Error in the same direction First Move)算法来替代力导向算法，并通过对力导向算法和SEFM算法进行加权的方式，来进一步降低全局应力误差。最后我们将不同的点的初始位置生成方法和不同的位移策略两两组合实现MDS降维时,全局应力误差的变化情况进行了对比，从而获得更好的MDS算法。

目录

声明

摘要

第1章 引言

1．1 研究背景

1．2 高维数据可视分析研究现状

1．2．1 高维数据降维技术

1．2．2 高维数据样本分析方法

1．2．3 高维数据可视化方法

1．3 本文主要工作

1．4 本文结构

第2章 一种改进的RadViz可视化方法

2．1 问题提出

2．2 维度距离矩阵

2．2．1 高维数据集合定义

2．2．2 维度相关性矩阵

2．2．3 维度距离矩阵的变换

2．3 维度向单位圆投影的算法

2．3．1 RadViz算法

2．3．2 MDS算法

2．3．3 TSP算法

2．3．4 小结

2．4 基于CM算法实现维度布局优化

2．4．1 维度点的圆周移动方案

2．4．2 维度点布局的全局应力误差计算

2．5 样本点的投影

2．5．1 样本点的投影方法

2．5．2 样本点的布局标准

2．6 实验过程及结果分析

2．6．1 CM算法的迭代对全局应力误差的影响

2．6．2 维度点布局的全局应力误差结果分析

2．6．3 维度点位置的调整对样本点投影精度的影响

2．6．4 RadViz的改进在其他数据集上的应用

第3章 一种改进的MDS算法

3．1 欧式距离矩阵的PTI与点的数量对全局应力误差的影响

3．1．1 相关系数矩阵的建立

3．1．2 PTI对全局应力误差的影响

3．1．3 点的数量对全局应力误差的影响

3．1．4 小结

3．2 点的初始位置生成方法

3．2．1 问题提出

3．2．2 基于TSP算法生成点的初始位置

3．2．3 基于DRGT算法生成点的初始位置

3．2．4 实验过程及结果分析

3．2．5 小结

3．3 点位置的调整策略

3．3．1 力的计算和权重的设置

3．3．2 基于加权力导向算法的点位置调整策略

3．3．3 基于SEFM算法以及加权SEFM算法的位移策略

3．4 实验过程及结果分析

3．4．1 SEFM算法与力导向算法的对比

3．4．2 数据点初始位置生成方法和调整策略的多种组合对比

3．4．3 不同数据集上的实验过程及结果对比

3．5 本章小结

第4章 总结与展望

参考文献

致谢

附录