综合利用属性分布相似 性 、空 间距离 以及交 叉最近 邻表三 种度量方法 , 提出了一 种综合 有效的 高维数 据相似 性度量 方法 。 但是 , 该方法中所涉及的相似性度 量公式复杂 , 导致 在海量高维数据聚类过 程中的 时间复 杂度较高 , 实 用性不 强 。 文献[ 5] 提出了一种基于共享最近邻的高维聚类 算法 , 其算法思想在于度量各数据间最近邻数据对象中的交叉情 况 , 交叉程度越大 , 数据间的相似度也越大 , 但是 , 该文中数 据对象相似性度量公式 不能完 全反映 数据间的 相似程 度 。 文献[ 6 , 7] 提出了一 种基于 地球引力 模型的 属性数 据相异 度计算方法 , 其中文献[ 6] 将地球引力模型中涉及到的距离 值改为对象属性间的信 息熵 , 避免了 高维空 间中距 离的计 算 。 文献[ 8] 提出了投影最近邻的概念 , 它根据各点用一个 准则函数挑选相关的维 , 仅利 用这些 相关的 维计算 其它点 与该点的相似度 。 由于将原高维空间中相似度度量问题转 化成在低维子空间中的 相似度 计算 , 因此这 种方法 可以继 续采用原低维空间中 的距离计 算函数 。 但是 , 该方法 中用 来选择各点的相关维 的质量准 则函数 难以确 定 。 文献[ 9] 提出了 一种用 于高维数 据的相 似度函 数 Hsim( ), 该函数 避免了原有的低维空间上定义的距离函数在高维空间中的 不适用性 , 即随着维数的增加 , 最大和最小距离之间的对比 越来越不明显 , 点与点之间的距离对比性 不复存在 , 一个点 到它的最远邻和最近 邻的距离 几乎是 相等的 。 但是 , 该相 似度函数不适于对分类属性数据的相似性度量 。
1 引言
现实生活中广泛使 用的大 量数据 , 以及 对这些 数据 中 潜在有用的信息和知识的迫切需要促进了 数据挖掘理论与 技术的快速发展 。 聚类分析作为数据挖掘所采用的关键 技
＊ 收稿日期 : 2009 -11-15 ; 修订日期 : 2010 -02-09
基金项目 : 国家科技支撑计划资助项目( 2007BA H 16B03) ; 国家 863 计划资助项目( 2009A A 12Z228) 作者简介 : 谢明霞( 1985 ) , 女 , 湖北武汉人 , 硕士生 , 研究方向为空间数据挖掘和 G IS ; 郭建忠 , 教授 , 研究方向为地理信息系统 。 通讯地址 : 450052 河南省郑州市陇海中路 66 号解放军信息工程大学测绘学院 6 系 3 队 ; Tel : 13303852026 ; E -mail : xm x0424 @yah oo . cn Address : In sti tu te of Surveyi ng and M appi ng , Inf orm at ion Engineeri ng U ni versi ty , Zhengzhou , H enan 450052 , P . R.分 析而言 , 定义数据 对象之间的 相似度是 至 关重要的一步 , 相似度定义 得恰当 与否直 接影响 数据聚 类 的效果 。 针对不同类型 的应用 和数据 类型 , 具有不 同的 相 似度定义方法 。 传统的相似性度量方法有距离度量和相 似 系数计算 。 在高维空间 中 , 常 用的欧 几里德 等经典 距离 度 量方法不能很好反映 数据间 的相对 距离 , 即与任 一对象 之 间的最近和最远距离的相对差异随着维度 的增长将趋近于 0 。 因此 , 在基于欧几里德等经典距离度量方法基础上所 作 的改进高维数据相似 性度量 方法 , 也避免 不了高 维空间 中 “ 维灾” 所 带 来的 问 题 。 常 用 的 相 似 系 数 计 算 方 法 包 括 Cosine 度量 、 Pearson 相 关 系 数以 及 J accard 系 数等 。 其 中 , Cosine 度量和 Pearson 相关 系数适 于高 维空间 中数 值 型数据的相似性度量 , 而不 能用于 分类属 性数据 相似度 的 计算 , 另 一方面由于其计算的复杂度 , 增加了高维数据聚 类 的时间复杂度 , 影响了聚类的效率 , 导致基于此的高维数 据 聚类方法的实用性 不强 。 Jaccard 系数 是度 量两个 二元 变 量集合的重叠程度 , 因 此在 使用 Jaccard 系 数进行 相似 性 度量时 , 需要将区间标度型 、分类 、序数 、比例标度变量等 转 化为二元变量 , 在 转化 过程 中 必然 丢失 大量 有用 的 信息 。 J accard 系数可以较好地反映高 维数据在 属性上 的相似 程 度 , 但不能反映其在高维空间距离上的相似程度 。 针对高维数据的相似性度量方法的研 究 , 文献[ 3] 提 出 了一种对象组的相似 性计算 方法 , 该方法 首先将 高维稀 疏 矩阵转换为二态数据 矩阵 , 根据二 态数据 矩阵计 算对象 组 的相似度 。 由于该方法 在整个 聚类的 执行过 程中 , 只需 要 进行一次数据扫描 , 大大 提高了 算法的 效率 。 但该 方法 仅 适用于对具体的数据 值不感 兴趣的 情况下 , 即可 以将现 实 问题中的区间标度型 、分 类 、序 数 、比 例标度 变量等 转化 为 二态变量时 , 很大程度上限制了该方法的适用性 。 文献[ 4]
CN 43-1258/ T P ISSN 1007-130X
计算机工程与科学
CO M P U T ER ENG IN EERI NG & SCIENCE
2010 年第 32 卷第 5 期 V ol. 32 , No. 5 , 2010
文章编号 : 1007-130X( 2010) 05-0092-05
＊
高维数据相似性度量方法研究 Research on the Similarity M easurement of High Dimensional Data
谢明霞 1 , 2 , 郭建忠 1 , 张海波 3 , 陈 科 1 XIE Ming -xia1 , 2 , GUO Jian -zhong1 , ZHANG Hai -bo3 , CHEN Ke1 ( 1. 解放军 信息工程大学测绘学院 , 河南 郑州 450052 ; 2. 75719 部队 , 湖北 武汉 430074 ; 3. 68029 部队 , 甘肃 兰州 730020) ( 1. Institute of Surveying and Mapping , Information Engineering University , Zhengzhou 450052 ; 2. Corps 75719 , Wuhan 430074 ; 3. Corps 68029 , Lanzhou 730020 , China ) 摘 要 : 将低维空间中的距离度量方法( 如 Lk -范数) 应用于高维 空间时 , 随着维数 的增加 , 对象 之间距 离的对 比性将 不复存在 。 研究高维数据有效的距离或相似( 相异) 度度量方法是一个 重要且具有挑战性的课题 。 通过对传统的距离度量 或相似性( 相异性) 度量方法在高维空间中表现出的不适应性 的分析 , 并对现有 的应用于高 维数据的 相似性度量 方法进行 总结 , 提出了高维数据相似性度量函数 Hsim( X , Y )的改进方法 HDsim ( X , Y)。 函数 HDsim( X , Y )整合了各类型数据的 相似性度量方 法 , 在处理数值型 、二值型以及分类属性数据上充分体现了原 Hsim( 处理数值型数据 、 Jaccard 系数处 X , Y) 理二值数据以及匹配率处理分类属性数据的优越性 。 通过有 效性及实例分析 , 充分论证了 HDsim( X , Y )在高维空间中的 有效性 。 Abstract : T he re exists no co mpa riso n between the dista nces of the objects with the increase of dimension when the method of distance mea surement for low dimensional space is adopted in hig h dime nsio nal space .T he study of efficient methods for distance mea surement o r similarity ( dissimilarity)measurement in hig h dimensio na l space is ve ry impor tant and challeng ing .T he impro ved function HDsim( X , Y )is pr oposed to mea sure the similarity between the o bjects in hig h dimensional space through analy zing the inapplicability o f the traditio nal measurement being used in high dimensio nal space and summa rizing the e xisting methods to similarity measurement fo r hig h dimensional da ta .T he methods fo r similarity measure ment to all kinds of data have been integ ra ted by function HDsim ( X , Y ), which takes full advantag e o f the original functio n Hsim( X , Y)in dealing with nume rical data , the J accard coefficient in dealing w ith the binary data , and the matching ratio in dealing with the catego rical da ta . V alidity and case analysis demo nstr ate that the function HDsim ( X , Y)is effective in co mputing the simila rity be tw een the o bjects in hig h dime nsio nal space . 关键词 : 高维数据 ; 相似性度量 ; 属性相似性 ; 空间相似性 Key words : hig h dimensional data ; similarity measur eme nt ; attribute similarity ; spatial similarity doi : 10 . 3969/ j . issn . 1007 -130X . 2010 . 05 . 025 中图分类号 : T P18 文献标识码 : A 术之一 , 已广泛用于 诸多应 用领域中 , 如 市场研 究 、模 式识 别 、数据分析 、图像处理 、机器学习等 。 随着人类获取数据手 段的逐 步发展 , 大量 的数据 通过 传感器和其它的数据采集设备源源不断地收集 。 在地学领 域 , 随着卫星和遥感技术的广泛应用 , 日益丰富的空间和非 空间数据得到收集和存储 ; 在医疗领域 , 各种医疗成像大量