应能保证操作的并行性和可恢复性 简单性和鲁 ；（4） 棒性 ， 复杂的访问方法可能在某一方面性能优异 但 ， 更新算法 更新算法在具体应用中可以看作 3.2.3 是一连串的删除操作及其随后的插入操作 这里不 ， 付出的代价如果是计算量大又易于出错 却不如简 ， 再赘述 。 、 单 鲁棒性强的结构 ；（5） 于空间数据的检索比较快 高效性 一方面要求方法对 ， 3.3 基于 B-tree 的索引结构 性能的下降在对数曲线 经过多年对多维数据索引的研究 ， 范围内 ， 另一方面 ， 又希望索引范围相对于整个数据 的索引结构 大都采用平衡树的概念 。 ， 提出了大量 ， 即从根结点到 在树的形状上 。 聚类精度 层次化的聚类原则[5]， 索的 B-Tree： 库比较小 即搜索空间小 存储利用 率 高 ， ；（6） 当索引结构嵌入到大规模的数据库系统中时 ， 集 成 性 ， 响应尽可能地小 。 构建算法 3.2 构建高维数据索引结构能缩短聚类时间 提高 ， 高维索引方法实际上是基于数据空间的 所有数据结点的访问长度是相同的 ， 影 ， 即表现为高度一致 。 这里访问长度又称为索引高度 ， 从任意结点到数据结点的访问长度称为结点的级 显然 ， 数据结点对应第 级 0 。 1984 年 Guttman 其思想是将空间目标及索引空间用其最小 。 提出 R-tree[8]， 包 围 矩 形 MBR （Minimum Bounding Rectangle） 来 近 结构上类似于早期用于数据检 似表示 ， 以简化计算 、 减少存储空间 ； 将空间上邻近 数据矢量存储在数据结点 空间位置 的目标组织在同一结点或同一分枝 ， 邻近的矢量尽可能存储在同一结点 数据结点之间 ， 以层次化目录结构来组织 ， 每一个目录结点都指向 下一级的一个子树 。 访问次数 1 是空间数据对象 。 图 结点最大容量 ）。 插入算法 插入算法的基木步骤 3.2.1 个适合容纳新数据的叶子结点 找到一 :(1) 并将新数据插入到 ， 索路径的平均数量增加 要较多的存储空间 叶子结点中 ；(2) 如果此叶子结点中容纳的数据超过 提出了 R+-tree； 可以减少外存 ， 树的实例 左边 ， 是 是一个二维 2 右边是对应 层 R 树 其中 ， 然而由于允许区间重叠 ， R M=3（M 导致了搜 ， ； 每一维的区间都要储存 ， 为了避免索引空间重叠的问题 ， 为了减少了查询中对外存的访问次 需 。 了限制 ， 则 此 结 点 按 照 一 定 的 规 则 分 裂 为 两 个 新 数出现了 Cell-tree[9]等 。 与传统索引结构相比 高维 ， 的 叶 子 结 点 ；(3) 对叶子结点的上层目录结点作相应 空间索引并没有一种标准的代数定义 也没有相应 ， 的修改以适应下层分裂和包围的变化 如果上层结 的描述语言 。 ， 点包含叶子结点的数目也超出了目录结点的容量限 制 ， 则目录结点亦按一定的规则分裂 按照上面 ；(4) 的算法一直向上 ， 如果根结点也发生分裂的话 则树 ， 的高度增加 1， 并建立一个新的根结点 成为分裂后 ， 两个结点的上层结点 。 图 1 R 树用来存储 2 维矩形的示例 插入是索引结构最重要的操作之一 由于各个 ， 局限性 3.4 结点之间的重叠和目录区域对数据空间覆盖的不完 ， 整性 使得选择插入结点成为难点 ， 的选择也对索引结构的效率起重要的作用 。 引结构正是通过改进分裂方式使性能提高 同时 。 分裂方式 不少索 如 采用了无重叠分裂方式 [6]， Tree 制再插入 分裂方式 ” ， 而 ， 采用 X- 强 并都取得了良好的检索效果[7]。 查询到 R*-Tree “ 删除算法 删除算法的基本步骤 3.2.2 要删除的数据所在的叶子结点 ：(1) 删除此数据 ；(3) 如果因此造成叶子结点包含数据的数目小于限定值 ；(2) 等人用一种代价模型对基于边界区域 Webber 的索引结构和基于空间划分 （BR） 进行了性能上的分析 的索引结构 得到了如下几点结论 [10]：（1） 对任何通过数据聚类和 空 间 划 分 而 形 成 的 索 引 结 （SP） ， 构 时 ， ， 总存在一个维数 d， 当索引结构的维数超过 其性能不如简单的顺序扫描 ；（2） d 在任何索引结 构上进行相似性查询时 杂度趋近于 O(N)；（3） 划分而形成的索引结构 随着维数的升高 ， 对任何通过数据聚类和空 间 ， 其时间复 在进行相似性搜索时 总存 ， ， 的话 ， 则将此结点中的所有数据移出 删除此结点 ， ， 在一个维数 d， 当索引结构的维数超过 时 ， d 所有的 然后把移出的数据再插入到索引中 。 数据块都会被访问 。 126 

应用示例与实验评估 4 表 3 主成份系数 ， 都按照科学 的表现 ， 目前 高等院校对于学生德 智 、 、 体 、 能等各方面 实用 、 、 简便等原则设置一套综 合指标评价体系 。 多指标综合评价的基本思想是把 多个单项指标组合起来 ， 形成一整套包含各个侧面 的综合指标内容 。 它的数学实质就是把高维空间中 的样本映射到低维的状态空间上 研究样本的基本特性[11]。 综合成为少量的主成份 ， 构造综合评价函数来获取数 再以这些主成份的贡献率 聚类分析时把原有的指标 通过投影直接来 ， 为权数进行加权平均 ， 据资源的聚类处理结果 。 结合闽西职业技术学院教学评估体系中对于课 程设置相应属性的分类要求 将反映高等院校学生 , 学业领域中不同课程的属性共 大类别 5 （ 全校公共 基础课 X1、 全校公共选修课 X2、 业选修课 X4 和实践教学环节 X5） 专业必修课 X3、 作为具体指标 专 以 , 闽西职业技术学院计算机系某届学生的学业信息数 据库为基础 围绕 ， “ 学习质量 ” 这一用户主题信息 确 ， 定其各自对于 学习质量 所能够提取的内容 分析 “ 与归纳出相应的基本特点 ” 反映进行数据库主成份提 以及进行相应聚类预处理的重要意义[12]。 ， 根据数据库主成份的定义对已有数据库信息进 取的有效性 ， , 行数据表转换 ， 并实施标准化处理 获得如表 ， 所示 1 基于数据相关度矩阵表进行 的数据相关度矩阵表 数据库主成份提取 ， 和累计贡献率 。 获得如表 所示的有关特征值 2 ， 如表 并据此计算变量指标对应相关主成 所示 ）。 3 标准化处理后的数据相关度矩阵 X2 X3 X4 X5 0.675 134 1 0.573 864 0.514 171 1 0.597 970 0.635 341 0.565 918 0.514 171 0.635 341 0.537 918 0.565 918 0.451 659 特征值及累计贡献率 1 0.600 968 1 0.439 905 0.537 918 0.451 659 0.600 968 X1 X2 X3 X4 X5 f 1 f 2 f 3 f4 f 5 0.358 990 - 0.561 930 0.078 256 0.693 080 0.056 007 0.380 740 - 0.288 450 - 0.183 580 - 0.566 880 - 0.287 700 0.431 600 0.083 690 - 0.031 730 - 0.255 900 0.675 950 0.415 920 0.365 650 0.164 810 0.108 000 - 0.641 330 0.336 070 0.272 490 - 0.798 770 0.232 090 0.026 275 的各项系 在表 3 数均为正数 主成份系数中 第一主成份 f1 且非常接近 ， ( 左右 )， 0.4 这表明 5 ， 都在 项指标对于综合反映最终用户主题是比较均衡的 ， 从而减少综合 完全可以放弃使用其他主成份指标 ， 评价的工作量 提高效率 但是 , 。 , 第一主成份 的贡献 f1 率仅为 不充分 67.1%， 说明它所包含的数据对象信息量并 并未达到主成份分析方法所要求的方差贡 , 献率基本阈值 （85%)[13]。 尽管前 3 个主成份指标的累 计贡献率达到 据对象信息量 , 表明包含绝大部分的原始数 84.4%, 是数据库主成份提取的理论最佳值 ， 但是还需要通过实验具体验证 。 这一主题 围绕 学习质量 , “ 个主成份指标进行实验 ” 分别对学业信息数 实验分别从实验 。 据库的 5 结论的准确率 、 第一主成份指标 三主成份指标 成份指标这 5 得到结论的时间消耗这两个方面对 第一和第二主成份指标 、 第一至第四主成份指标以及全部主 第一至第 、 、 种情况获取数据 图 显示在以上 2 5 。 得到结论的时间消耗 种情况下 , 实验结论的准确率 、 与标准消耗的比率 标准耗时率 ( ) 以及相应的性能价 格比率 准确率 / ( 标准耗时率 ) 之间的实验对比 。 1.02 1.00 0.98 0.96 0.94 0.92 0.90 0.88 0.86 结论准确率 标准耗时率 性能价格比 1 2 3 4 5 主成份选择的对比图 图 图 表明 , 2 2 选择提取 个主成份不仅是理论最 3 份的结果 （ 表 1 相 关 度 X1 X2 X3 X4 X5 X1 1 0.675 134 0.573 864 0.597 970 0.439 905 表 2 第 q 主轴 特征值 方差贡 献率 /% 累计贡 献率 /% 1 2 3 4 5 佳值 ， 也是实验结论的最佳值 因此 ， ， 数据库预处理 聚类提取 3 个主成份后 ， 其与标准化变量之间的关 4.694 20 0.647 81 0.565 92 0.319 27 0.161 97 系为 ： 67.1 9.2 8.1 4.6 2. 3 Y1 =0.35899x1 +0.38074x2 +0.4316x3 +0.41592x4 + 67.1 76.3 84.4 96.2 100 0.33607x5 Y2=-0.56193x1-0.28845x2+0.08369x3+0.36565x4+ 127 

梅承力 周源华 . ， 高维数据空间索引的研究 红外与激光 [J]. [5] 工程 ，2002，31(1)：77- 81. [6]Berchtold S.,et al.The X- Tree:An index structure for High- di- mensional Data [C]//Proc. of the 22nd Int’ l Conf. on VLDB.San Fransisco：Morgan Kanfmann Pubbishers,1996:28- 39. [7]Beckmann N.,et al.The R*- tree:An Efficient and Robust Ac- cess Method for Points and Rectangles[C]//Proc.of ACM- SIGMOD. Atlantic City：ACM Press,1990:322- 331. [8]Guttman A..R- Trees:A dynamic index structure for spatial search[C] //Proceedings of ACM- SIGMOD. Boston：MCM Press， 1984:47- 57. [9]Gunther O..The design of the cell tree:An object- oriented index structure for geometric database[C]//Proceedings of ICDE. LosAn- geles：IEEE Computer Society 1989，1989:598- 605. [10]Webber R.,et al.A quantitative analysis and performance study for similarity- search in high- dimensional sapce [C]//Proc. of the 24th Int’ l Conf. on VLDB.New York:Morgan Kaufmann Publish- ers，1998:194- 205. 盛子宁 多指标评估体系的主成分分析及应用实例 上 [J]. [11] 海海运学院学报 . ，2003，24(3)：251- 253. 0.27249x5 Y3=0.078256x1-0.18358x2-0.03173x3 +0.16481x4 -0.79877x5 结果与讨论 5 利用降维的思路把相关数据库的主成份进行提 , , ， 根据统计学处理数据对象的一些定义和方 有利于特 对数据库整体进行分析和聚类预处理 取分析 法 定主题数据资源的整理和挖掘 有参考依据的数据对象信息 后 源整理过程中时间消耗与空间消耗的大幅度减少 研究表明 高维空间索引 技术的融合提供了切入点 。 数据集的聚类结构可以帮助构造高效的 这个共同点为研究树型索引与聚类 有利于提供有价值 , 、 尤其是主成份提取以 有利于数据资 数据对象的操作数量大幅度降低 。 ， ， , , 。 宋 中 山 . ， 数 据 挖 掘 中 的 聚 类 算 法 电 脑 知 [J]. 参考文献 张 嫣 [1] ， 识与技术 ： 安 中 印 ，2007(7):15- 17. 吴 玲 达 蔡 益 朝 贺 玲 [2] 算机应用研究 ， ， ，2007(1):10- 13. [3] 学报 姜斌 [4] 的应用 ， 数 据 挖 掘 中 的 聚 类 算法 综 述 计 [J]. . 夏骄雄 徐俊 ， ， 吴耿锋 .“ 数据库主成份提取 方法及其应 ” [12] 用 计算机工程与应用 ，2006，42(20)：134- 137；202. [J]. 杨 质 敏 高 维 数 据 的 降 维 方 法 研 究 及其 应 用 长 沙 大 学 [J]. . [13 ]JolliffeI . T. Principalcomponent analysis [M]. NewYork : ，2003,27(16)：58- 61. 等 潘景昌 郭 强 ， ， 和 相 融 性 度 量 在 聚 类 算 法 中 . PCA Springer- Verlag,1986:111- 198. 责任编辑 潘伟彬 ： 电子科技大学学报 [J]. ，2007,36(6):1292- 1295. Study of high-dimensional reduction method in cluster analysis XIE Feng-ping （Computer Department, Minxi Vocational and Technical College, Longyan, Fujian, 364021, China） Abstract：High-dimensional data is able to describe complicated information. However, the difficulty of processing high-dimensional data limits its application. This paper describes methodologies of dimension reduction algorithm and index structure to solve dimension reduction problem. The projection on the most differentiation of the data object is defined as principal component, by leading the cluster analysis into the preprocessing of data resource on the colleges and universities, and cluster reduction of the data sets are reached. The application example is given to illustrate the effectiveness for exploration model. Key words：cluster analysis; high-dimensional data; dimension reduction algorithm; index structure 128