一种基于子空间聚类的局部相关性可视分析方法

计算机辅助设计与图形学学报

Journal of Computer-Aided Design & Computer Graphics

Vol. 28 No.11 Nov. 2016 一种基于子空间聚类的局部相关性可视分析方法

夏佳志1), 张亚伟1), 张 健1)*, 蒋 广1), 李 瑞1), 陈 为2) 1)2)

(中南大学信息科学与工程学院 长沙 410083)

(浙江大学CAD&CG国家重点实验室 杭州 310058) (211072@csu.edu.cn)

摘 要: 数据子集局部存在的维度相关性往往被数据集全体所掩盖. 为了发现有意义的数据子集, 并揭示其表达的维度局部相关性, 提出一种局部相关性可视分析方法. 首先采用基于测地距离和局部子空间距离的二维散点图揭示子空间聚类模式; 然后基于近似覆盖面积和平均距离进行相关显著性估计, 给出可能具有局部相关性的二维子空间推荐; 最后实现了可视分析系统, 并通过案例分析验证了可视分析系统的有效性.

关键词：维度相关性; 子空间聚类; 可视分析; 高维数据 中图法分类号：TP391.41

Local Correlation Visual Analysis Based on Subspace Clustering

Xia Jiazhi1), Zhang Yawei1), Zhang Jian1)*, Jiang Guang1), Li Rui1), and Chen Wei2)

1)2)

(School of Information Science and Engineering, Central South University, Changsha 410083) (State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou 310058)

Abstract: The dimension correlations which exist in subset of data are often obscured in the full dataset. We propose a local correlation visual analysis approach to detect meaningful data subset and reveal local dimension correlations. First, a scatter plot is adopted to visually reveal the subspace cluster. The two dimensions of the scatter plot are defined based on geodesic distance and the distance between local subspaces correspondingly. Next, an estimation for correlation significance is proposed based on covering area and mean distance of the data. Subsequently, the 2-dimensional subspaces which reveal local correlations are suggested. Last, a visual analysis system is implemented and case studies demonstrates the effectiveness and efficiency of our system.

Key words: dimension correlation; subspace clustering; visual analysis; high-dimensional data 相关性分析是维度约减、维度抽取等高维数据处理常用技术的基础, 是数据挖掘与高维数据可视分析中的重要问题. 传统的维度相关性都定义在数据集中的全体数据上, 体现了全局相关性. 但在实际的数据集中, 维度之间的相关性往往存在着数据上的局部性[1]. 如图1所示, 数据集中不同

的数据子集体现出不同的维度相关性. 在进行全局相关性分析时, 维度局部相关性往往被数据集全体所掩盖. 进一步, 只有具有内在联系的数据子集才能揭示有意义的维度相关性. 例如, 当支持局部相关性的数据子集构成一个聚类时, 其意义是清晰的; 反之, 在任意2个维度张成的平面上, 任取

收稿日期: 2016-04-29; 修回日期: 2016-07-25. 基金项目: 国家自然科学基金青年基金(61309009); 教育部博士点基金(20130162130001); 湖南省科技计划项目(2015JC3044). 夏佳志(1984—), 男, 博士, 副教授, 硕士生导师, CCF会员, 主要研究方向为数据可视化、计算机图形学; 张亚伟(1991—), 女, 硕士研究生, 主要研究方向为数据可视化; 张 健(1974—), 男, 博士, 讲师, 论文通讯作者, 主要研究方向为网络安全、信息可视化; 蒋 广(1995—), 男, 在校学生; 李 瑞(1996—), 男, 在校学生; 陈 为(1974—), 男, 博士, 教授, 博士生导师, CCF会员, 主要研究方向为科学可视化、信息可视化和可视分析.

1856

计算机辅助设计与图形学学报 第28卷

一线段状区域, 区域内的数据子集都支持2个维度之间的线性关系. 但这些数据点之间往往缺乏内在联系, 无法说明其所支持的相关性的意义. 因而, 维度局部相关性分析的挑战在于发现支持局部相关性的聚类. 这包括了2个方面的问题: 1) 在高维空间中发现聚类; 2) 如何检测聚类是否支持维度间的相关性关系. 针对这些问题, 本文提出一种基于子空间聚类的可视分析方法. 首先, 本文采用基于测地距离和局部子空间距离的投影方法, 将高维数据投影到二维, 揭示数据的聚类情况; 其次, 本文基于发现的聚类, 在聚类子空间的正交二维子空间中检测维度相关性; 最后, 本文实现了交互式可视分析系统, 并应用此系统对多个数据集进行了分析.

图1 存在局部线性相关的四维数据

1 相关工作

1.1 相关性分析

相关性分析的目标是发现变量间潜在的相关关系. 变量间的相关性可以是任意的线性和非线性函数. 线性相关性检测最常用的是皮尔逊相关系数[2]. 由于皮尔逊相关系数计算简单, 可解释性较好, 已成为使用最广泛的线性相关性度量. 非线性相关性度量中, 比较成功的方法是最大信息系数(maximal information coefficient, MIC)[3]. MIC的定义基于覆盖在散点图上的网格划分和互信息, 它对于不同形式的线性或非线性相关性具有通用性, 对具有同等程度噪音的不同形式的相关性具有均等性, 因此被认为是良好的相关性度量. MIC的思想启发了本文的非线性相关性检测方法. 但MIC需要采用动态规划方法计算多个不同的网格划分, 算法复杂度和实现难度都相对较高.

1.2 自动化子空间聚类方法

数据挖掘领域的研究表明, 高维数据集往往由一系列低维子空间中的聚类构成[4]. 在全空间的欧氏距离度量下, 这些低维的聚类往往被不相关的维度所掩盖; 只有在合适的子空间中, 对应的数

据子集才体现出聚类特征. 按照寻找子空间与寻找聚类2个任务的先后顺序, 子空间聚类方法可以分为自顶向下和自底向上2个类型[5-6]. 自顶向下的方法包括PROCLUS[4], PreDeCon[7]等; 首先估计聚类, 再检测聚类所在的子空间. 自底向上的方法包括CLIQUE[8], SUBCLU[9]等; 首先检测存在聚类的子空间, 再检测子空间中的聚类. 但是, 自动子空间聚类方法得到的结果往往高度冗余, 并且难以解释和理解.

1.3 可视分析与子空间聚类

交互式可视分析为易于理解的子空间聚类和维度相关性的研究提供了有力的分析工具. 用户的洞察力在交互式分析框架中得到了发挥. 可视分析已经成为数据挖掘的重要方法, 马昱欣等[10]对相关工作做了详细的综述. Farber等[11]提出了对于自动子空间聚类结果的交互式可视化方案. Turkay等[12-13]提出在数据空间与维度空间同时对高维数据进行探索. 类似地, Yuan等[14]提出了层次化的交互式子空间可视分析方法. 但这些方法缺乏有效的交互导引, 其可视分析流程在一定程度上依赖于试错探索, 效率有待提高.

2 子空间聚类与子空间关联聚类

子空间聚类的目标是寻找在低维子空间中具有密集特征的聚类. 聚类中的个体在对应空间中的投影距离越近, 表示聚类特征越强. 本文将子空间聚类所定义的聚类简称为聚类, 所关注的子空间称为聚类子空间.

子空间关联聚类方法是子空间聚类的扩展, 对维度局部相关性进行了研究[4]. 子空间关联聚类(如ORCLUS[15]等)关注的是在度之间存在关联关系的数据子集, 在这个数据子集中的任意数据可以被同子集中的其他数据近似线性表达. 一般认为, 关联聚类的本征维度越低, 所描述的关联聚类越有意义. 当本征维度为2时, 问题退化为寻找2个维度之间的局部线性相关性. 子空间关联聚类方法提供了分析局部相关性的思路, 其中二维的关联聚类揭示了2个维度或方向之间的局部相关性. 本文将子空间关联聚类定义的聚类称为关联聚类, 所关注的子空间称为关联子空间.

给定d中的聚类C, 其协方差矩阵记为ΣC.

ΣC的特征分解记为ΣC=VCECVCT, 其中ECdiag(e1,e2,,ed); e1≤e2≤≤ed; VC为特征

第11期

夏佳志, 等: 一种基于子空间聚类的局部相关性可视分析方法 1857

向量矩阵, VC[v1,v2,,vd]. 对于子空间聚类任务, 聚类子空间即方差较小的特征向量张成的子空间, 有

e

iS{v1,v2,,v}, maxi1

d≤.

e ii1

另一方面, 给定子空间S中的关联聚类C,

对其做特征分解C|SVC|SEC|SVTC|S. 其本征维度为其方差较大的特征向量的数量, 有

1e

|S|minii0

|S|≥(1)

eii1

当|S|时, 对于C, S中的每一个维度

都是的, 这样的关联聚类没有意义. 因此, 子空间关联聚类只考虑|S|的情况. 根据式(1),

C在e1,e2,,e|S|维张成的子空间中方差较小,

呈密集特征, 符合子空间聚类的定义. 反之, 维的子空间聚类C, 也可以看作本征维度为d的关联聚类.

基于以上分析, 对于给定的某子空间中的聚类C, 本文得到以下推论:

推论1. 聚类C的子空间聚类定义与子空间关联聚类定义是等价的.

推论2. 当Sd时, 聚类子空间与关联子空间互为正交补(如图2所示, 数据在图2b所示聚类子空间V中呈密集特征, 而在图2a所示关联子空间d/V中呈非线性特征).

图2 聚类子空间与关联子空间

推论3. 一般情况下, 关联子空间包含在聚类子空间的正交补中.

对于推论1需要注意的是, 子空间聚类方法与子空间关联聚类方法可能得到不同的结果. 如图1所示, 数据集在d3与d4构成的子空间中呈现为一个聚类, 而在d1与d2构成的子空间中呈现为2个关联聚类.

基于推论3, 本文提出在聚类子空间的正交补空间中寻找维度的关联关系. 由于本文仅关注特征维度为2的关联聚类, 即2个维度之间的关联关系, 所以本文的寻找范围限定为属于正交补空间的二维子空间.

3 局部相关性可视分析系统

3.1 基于局部子空间距离和测地距离的二维散点图

为了在高维数据中寻找聚类和相应的子空间, 本文采用LSD-GD(local subspace difference-geodesic distance)视图, 其将2个距离度量分别应用于2个维度上的布局, 并将高维数据投影到二维平面上, 构成二维的散点图. 第一个度量是数据点的局部子空间之间的距离. LSD估计每个数据点的局部子空间, 然后给出局部子空间之间的距离. 第二个度量是数据点之间的测地距离. 由于维度灾难的影响, 高维空间中的全维度欧氏距离往往难以刻画数据的内蕴结构. 该方法用k-邻域图估计高维数据中的低维流形结构, 并在流形结构上计算测地距离. 相对全空间中的欧氏距离, 测地距离能更准确地反映高维数据的内蕴结构. 图3所示为一个包含3个3维高斯聚类的6维数据在LSD-GD视图上的投影结果, 图4用平行坐标图展示了原始数据.

图3 6维数据的LSD-GD视图投影

3.2 二维平面中的局部相关性显著性估计

给定维子空间S={d1,d2,,d}中的聚类C, 有意义的维度相关性可能存在于正交子空间

d/S={d1,d2,,dn}中. 要寻找d/S中任意

2个维度之间的线性和非线性相关性, 可能的一种办法是采用散点图矩阵直接绘制各个二维子空间. 但对于n个维度, 一共有n

2

个二维子空间

1858

计算机辅助设计与图形学学报 第28卷

图4 包含3个三维高斯聚类的6维数据

需要绘制和观察. 在维度较高时, 对绘制空间和用户感知能力都提出了较高的要求.

本文提出对二维子空间中存在线性或非线性相关性的可能性进行估计, 并基于该可能性对二维子空间进行排序. 通过优先呈现存在相关性可能性较高的子空间, 可以显著地降低绘制需求和用户的工作量. 对于全局线性相关性, 皮尔逊相关系数等可以简便地计算并准确地衡量. 但对于本文需要检测的局部相关性(图1), 包括非线性相关性, 则需要定义新的度量.

本文算法基于以下的观察: 线性或者非线性的相关性, 其数据集中分布在一维线段或曲线周围, 数据分布的区域面积较小. 反之, 无相关性的数据往往随机分布在二维区域内, 数据分布的面积较大. 因此, 数据分布的面积能够部分地体现维度的相关性关系. 本文采用图5所示近似的覆盖面积计算方法: 给定聚类C, 其中的点的数量为n, 将二维平面均匀划分为

n+1

n+1的网格. 如果

有C中的点落在某网格中, 则记该网格值为1; 否则为0. 记所有值为1的网格数量为m, 则C的覆盖面积比例为

Caream

n+1

n+1

图5 覆盖面积的近似计算

另一方面, 当C在二维平面上存在聚类模式时, 其覆盖面积也往往较小, 为了区分聚类与相关性, 本文同时统计了数据点之间的平均距离L. 当数据存在聚类模式时, 数据点之间的平均距离较小; 反之, 数据点之间的平均距离较大. 由概率密度积分可知, 在[0,1]×[0,1]的矩形上均匀随机分布的2个点的距离的数学期望E(L)约为0.521 4; 为了数值范围的稳定性, 本文定义LnormL/0.5214.

综合以上2个因素, 本文采用rCLnorm/Carea

作为局部相关性的度量. rC值越大, 表示存在局部相关性的可能越大, 本文构造了6组不同的二维数据, 包括呈线性相关性、非线性相关性、聚类与随机噪声等分布特征, 其rC值与皮尔逊相关系数值r如图6所示.

3.3 可视分析界面设计

本文提出的可视分析系统界面如图7所示. 其中可视化组件包括数据信息面板、LSD-GD视图、二维散点图、基于局部方向显著性排序的散点图列表, 以及分析结果展示列表. 3.3.1 数据信息面板

数据信息面板(图7a)提供了数据集的选择、数据集信息、kNN基本参数、选中点的各属性值等与数据相关的基本信息. 3.3.2 LSD-GD视图

图7b 所示LSD-GD视图以二维散点图的方式呈现局部度量空间, 提供了缩放、平移、悬停、套索选择以及子空间提取等交互操作. 在图7b中, LSD-GD视图呈现出4个密集模式, 表明在该数据集中存在4个聚类, 将其标注为C1, C2, C3及C4. 进一步地, 可在4个聚类的正交二维子空间中进行探索.

3.3.3 子空间视图

子空间视图由二维散点图(图7c)及散点图列表(图7d)组成. 基于局部相关性的显著性对这些正交二维子空间进行排序, 选中某个二维子空间后,

散点图(图7c)中呈现出放大的效果. 其中散点图(图7c)提供了套索选择操作、查看选中点或所有点

第11期

夏佳志, 等: 一种基于子空间聚类的局部相关性可视分析方法 1859

图6 6组数据的局部相关性系数rC与皮尔逊相关系数r

图7 系统界面

的散点图操作, 以及将有意义的散点图添加到结果列表视图操作; 散点图列表(图7d)提供了选择、上下换页操作.

3.3.4 结果展示列表视图

图7e所示结果列表视图呈现了有意义的二维子空间的散点图. 用户在子空间视图中选择可能存在相关性模式的二维散点图, 将其呈现在该区域中.

空间的正交二维子空间进行探索. 散点图列表中展示了根据rC值进行排序的二维子空间列表, 排序越靠前, 存在相关性关系的可能性越大. 因此, 只需要查看列表中居于前列的少数二维子空间. 图8b~8d分别展示了C1, C2, C3所在聚类子空间的正交二维子空间的排序结果. 在维度d5和d6之间, 聚类C3呈现出有3个分枝的分段线性关系. 根据相关性关系, 聚类C3可以进一步划分为3个聚类; 而在C1和C2的正交二维子空间中, 未检测到维度相关性.

4 可视分析实例

本节通过可视分析2个人造的数据集和1个真实数据集实例来展示系统.

4.1 人造6维数据集

该数据集共有950个数据点, 6个维度, 数据集包括3个三维高斯聚类, 在不相关的维度上, 数据由均匀分布的噪声组成.

LSD-GD视图显示数据集中存在3个聚类, 如 图8a所示, 将其标记为C1,C2和C3; 对其聚类子

4.2 人造9维数据集

该数据集共有1100个数据点, 9个维度, 数据集包括4个三维高斯聚类, 在不相关的维度上, 数据由均匀分布的噪声组成.

如图9a所示通过LSD-GD视图可以发现数据集被分为4个聚类C1, C2, C3和C4, 其聚类子空间分别记为V1, V2, V3和V4.

图9b~9e分别呈现了V1, V2, V3和V4的前4个

1860

计算机辅助设计与图形学学报 第28卷

图8 人造6维数据集

图9 人造9维数据集

正交二维子空间. 探索发现C3在维度d7, d8和d9两两之间都呈现了图9d所示的非线性关系. 结合3个视图的分析, C3在d7, d8和d9张成的三维空间呈螺旋线. 同时, C4在维度d5和d6之间呈现出分段图9c所示的线性关系. 对于其他聚类, 未检测到其所支持的维度相关性.

原始数据集包含2 100个数据点, 19个维度, 7个类别. 文中用到的数据去掉了5个冗余维度和9个异常数据点.

LSD-GD视图显示, 数据集中存在3个聚类,将其标记图10a所示的C1, C2和C3. 图10b~10d分别呈现了C1, C2和C3所在聚类子空间的正交二维子空间的排序结果. 探索发现, C1, C2和C3都在多组维度之间呈现出不同的线性相关性.

4.3 Image Segmentation数据集

Image Segmentation数据来源于UCI数据集,

图10 Image Segmentation数据集

第11期

夏佳志, 等: 一种基于子空间聚类的局部相关性可视分析方法 1861 5 实验比较与分析

表1给出了本文方法与皮尔逊相关系数、MIC的实验结果比较. 实验数据集来自文献[3], 包括7个不同分布的数据. 从实验结果可见, 皮尔逊相关系数难以表达维度间的非线性关系, 而MIC方法较为准确地反映了维度间的非线性关系. 相对于MIC方法, 本文提出的rC值反映了相似的趋势, 但在不同数据上的数值差异较小. 由于数据6的拟合误差更小, 表现出了更强的非线性关系, 本文方法将其排在第1位, 而MIC方法将其排在第2位.

但另一方面, 由于数据7的覆盖面积较小, 虽然数据7并没有表现出非线性关系, 本文方法将其排在第4位, 在数据4之前. 综合考虑排序质量与计算复杂度, 本文方法更适合实时的可视分析任务.

表2给出了在带噪声情况下的实验结果比较. 实验数据来自于本文的人造6维数据和人造9维数据. 从实验结果可见, 皮尔逊相关系数无论在是否存在噪声情况下, 都无法反映维度间的相关性; 而MIC方法也难以处理带有大量噪声的情况. 本文的可视分析方法可以通过子空间聚类去掉噪声, 取得的相关性趋势与MIC方法(无噪声情况)相似.

表1 rC与皮尔逊、MIC的实验结果比较

统计量 皮尔逊 MIC MIC排序

(1) 0.000 0.800 1 0.275 3

0.000 0.200 5 0.187 7

(2) 0.000 0.200 5 0.190 6

(3) 0.100 0.400 3 0.222 5

(4) 0.100 0.400 3 0.295 2

(5) 0.000 0.600 2 0.567 1

(6) 0.000 0.200 5 0.268 4

(7) rC rC排序

表2 本文实验数据下rC与皮尔逊、MIC的比较

实验数据

皮尔逊 有噪声 无噪声

(图8d)

(图9d)

(图9e)

参考文献(References):

[1] Günnemann S, Färber I, Virochsiri K, et al. Subspace correla-tion clustering: finding locally correlated dimensions in sub-space projections of the data[C] //Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2012: 352-360 [2] Pearson K. Mathematical contributions to the theory of evolu-tion. III. regression, heredity, and panmixia[J]. Philosophical Transactions of the Royal Society of London, 16, 187: 253- 318

[3] Reshef D N, Reshef Y A, Finucane H K, et al. Detecting novel

associations in large data sets[J]. Science, 2011, 334(6062): 1518- 1524

[4] Aggarwal C C, Wolf J L, Yu P S, et al. Fast algorithms for pro-jected clustering[C] //Proceedings of the ACM SIGMOD In-ternational Conference on Management of Data. New York: ACM Press, 1999: 61-72

[5] Kriegel H P, Kröger P, Zimek A. Clustering high-dimensional

data: a survey on subspace clustering, pattern-based clustering, and correlation clustering[J]. ACM Transactions on Knowledge Discovery from Data, 2009, 3(1): Article No.1

[6] Parsons L, Haque E, Liu H. Subspace clustering for high di-mensional data: a review[J]. ACM SIGKDD Explorations Ne-wsletter, 2004, 6(1): 90-105

[7] Bohm C, Railing K, Kriegel H P, et al. Density connected clus-tering with local subspace preferences[C] //Proceedings of the 4th IEEE International Conference on Data Mining. Los Alami-tos: IEEE Computer Society Press, 2004: 27-34

[8] Agrawal R, Gehrke J, Gunopulos D, et al. Automatic subspace

MIC 有噪声 无噪声0.145 0.9070.138 0.5660.209 0.998

rC

0.012 0.2210.004 0.0390.205 0.949

2.6581.02.609

6 结 语

本文针对高维数据相关性中存在数据局部性的问题, 提出基于子空间聚类的可视分析方法, 通过可视分析的手段找到有意义的数据子集, 进而分析数据子集所可能体现的维度相关性. 本文对子空间聚类与子空间关联聚类的联系与区别进行了分析, 提出在聚类的正交子空间中寻找局部相关性, 并提出了2个维度之间的相关显著性度量; 基于此进行的二维子空间排序减少了绘制与视觉感知上的负担. 可视分析实例证明, 本文方法可以有效地检测出聚类所表达的局部相关性, 具有较强的实用性.

1862

计算机辅助设计与图形学学报

第28卷

clustering of high dimensional data[J]. Journal of Data Mining and Knowledge Discovery, 2005, 11(1): 5-33

[9] Kröger P, Kriegel H P, Kailing K. Density-connected subspace

clustering for high-dimensional data[C] //Proceedings of the 4th SIAM International Conference on Data Mining, Los Alam-ito: IEEE Computer Society Press, 2004: 246-257

[10] Ma Yuxin, Cao Zhendong, Chen Wei. A survey of visualiza-tion-driven interactive data mining approaches[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(1): 1- 8(in Chinese)

(马昱欣, 曹震东, 陈 为. 可视化驱动的交互式数据挖掘方法综述[J]. 计算机辅助设计与图形学学报, 2016, 28(1): 1-8)

[11] Farber I, Tatu A, Keim D, et al. Subspace search and visualiza-tion to make sense of alternative clusterings in high-dimensi-onal data[C] //Proceedings of the IEEE Conference on Visual Analytics Science and Technology. Los Alamito: IEEE Com-

puter Society Press, 2012: 63-72

[12] Turkay C, Filzmoser P, Hauser H. Brushing dimensions--a dual

visual analysis model for high-dimensional data[J]. IEEE Tran-sactions on Visualization & Computer Graphics, 2011, 17(12): 2591-2599

[13] Turkay C, Lundervold A, Lundervold A J, et al. Representative

factor generation for the interactive visual analysis of high-di-mensional data[J]. IEEE Transactions on Visualization & Com-puter Graphics, 2012, 18(12): 2621-2630

[14] Yuan X R, Ren D H, Wang Z C, et al. Dimension projection

matrix/tree: interactive subspace visual exploration and analy-sis of high dimensional data[J]. IEEE Transactions on Visuali-zation & Computer Graphics, 2013, 19(12): 2625-2633 [15] Aggarwal C C, Yu P S. Finding generalized projected clusters

in high dimensional spaces[C] //Proceedings of the ACM SIG-MOD International Conference on Management of Data. New York: ACM Press, 2000: 70-81