高维星座图课程报告讲述.doc

课程论文之高维星座图 15085208210003 陈文彬 15085208210010 刘 畅 15085208210021 吴 迪 摘要 星座图是多元数据可视化的一种常用方法,具有形象的特点,可以通过调整权系数来对数据进行交互式挖掘但是传统的星座图缺乏自动调整权系数的较好方法因而限制了其在可视化数据分析和模式识别的进一步应用。本文传统的星座图为星座图并高维星座图的应用进行了研究。 高维星座图增益指数增益 w1,w2,w3,...wp，其中各，且。重要的变量相应的权可以取得大一点，但一般情况下取等权，即 画一个半径为1的上半圆及半圆的底边直径，使每个样本对应半圆内的一个点，称为星。 对于每一个样品xi对应着上半圆内的一个星星和一条折线表示的路径。最后绘制成的星座图如图1所示。其中路径的折点坐标是： ，其中 星星位于路径的终点，其坐标记为，即。 1.2 复数系数星座图 在文献[2]中提出了基于复线性判别算法的星座图权系数优化，从而将传统星图极坐标变换后的角度矩阵复化，如下所示： ，其中i表示虚数单位。 然后复化后的矩阵进行复线性判别分析，并将取得的最优方向作为星座图的权系数向量w。最后绘制样本的复星座图，根据公式： 经过复线性判别算法绘制优化星座图后，前后对比如图2所示，星座图经过优化后类分离度明显提高。原始的n维数据的聚类或者分类的问题便转化为一个二维数据的聚类或者分类的问题，并且该二维图表示上概括了原始数据的鲜明结构信息。 2 基于格理论构造高维星座图 在文献[3]中提出了基于格理论构造高维星座图的方法，相比现有的算法均只适用于星座点个数较少的情况，该方法可以简便地构造星座点数目较大的高维星座图。 2.1 格的简介 一个 n 维空间中的格是中一离散的点集 ,且该点集具有矢量加法下的群结构 .通常 ,一个n维格Λ可以由n个线性无关的基向量 ,1≤ i≤ n来描述 ,而格中的任意一点 x 可以表示成 (1) 其中, i=1,2,?,n.另一种描述格Λ的方法是 通过一个 n × n 维的生成矩阵 G ,G 的各行为基向量 , 1≤i≤n.有了上述定义后,格Λ中任一格点x可表示为 x = aG (2) 其中是一n维整数向量。 定义1 格Λ的最小欧氏距离dmin为Λ中任意两个格点的最小欧氏距离。 定义2 格Λ的重度Nmin为Λ中与任一给定格点距离为dmin的点的个数。 定义3 格Λ的基础体积V(Λ)为Λ中单位体积 (或面积)内格点数的倒数。 对于任意格都有： (3) 2.2 基于格的星座图 在一个基于格的星座图中, 若对应格的重度为Nmin,则在高信噪比的情况下,星座图的误符号率有以下估计式 (4) 其中, N0为加性高斯白噪声的功率.我们可将误符号率估计式改写成： (5) 其中，每二维平均功率表示一个n维星座图的平均功率化到二维空间后的值。它可由下式计算： (6) 其中, M为n维星座图中星座点的个数,xm为表示一 个星座点坐标的 n 维向量. 通过分析不难发现,由于式(5)根号下第二项为信噪比,则格的重度 Nmin 和 这两项将决定星座图的误符号率的大小。特别地,当星座图的维数n并不太大时, 项起主导作用。 定义4 n维星座图C的增益指数(CFM)为： (7) 设计低误符号率高维星座图的问题就可以转换为最大化 CFM .由于每二维平均功率的取值 与最小欧氏距离dmin有关 ,我们可固定dmin来最小化星座图的 (或平均功率). 上文曾提到过设计基于格的星座图的过程包括了格和边界的选取, CFM 可以由下式来表示： (8) 式中，为星座图基础增益，是一个常数；为格Λ的编码增益；而为边界R的成形增益。 基于格设计高维星图的第一步是选取一个致密的格，而编码增益反映了一个n维格Λ的疏密程度，其表达式为： (9) 其中G是格Λ的生成矩阵。由于V(Λ)表示的是格Λ中单位体积（或面积）中格点数的倒数，再加之格点间最小欧氏距离dmin固定，所以编码增益较大的格会更密。 接着，我们要选取一个包含我们想要的星座点个数的n维边界R来构成n维星座图。我们的目标是在最小欧氏距离dmin给定的情况下产生功率节省的星座图，而边界R的成形增益便可作为边界选取的衡量标准。n维空间中一区域R的成形增益可由下式表述： (10) 其中V(R)为区域R的体积（或面积）。由式（10）可发现，具有高成形增益的区域可以提高星座图的功率效率并能够提高系统的性能。另外，在所有区域中，球型边界总是拥有最大的成形增益值。 2.3 小结 格是一种数学结构，能够用来具体描述空间中按一定规律排列的点所构成的集合。任何星座图的CFM值均取决于和 的乘积。格的编码增益 仅取决于格的选择。若格点间最小欧氏距离dmin固定，更密的