在计算机上执行的用于处理多维数据的方法

1.一种在计算机上执行的用于处理多维数据的方法，包括下列诸步 骤：
a)将该多维数据划分为一个或多个聚类；
b)为所述一个或多个聚类生成以及存储聚类信息；
c)为所述一个或多个聚类生成一个或多个降维聚类以及降维信息； 以及
d)存储该降维信息；
递归地执行步骤a)-d)，生成一个多层次的降维聚类；
为该多层次聚类中处于最低层次的聚类生成并存储一个或多个低维 索引。
2.根据权利要求1所述的方法，该数据被存储在一个空间的数据库或 一个多媒体数据库之中，这些数据库含有多个数据记录，其中每一个记 录含有多个字段，所述方法还包括下列诸步骤：
生成被索引为一个矢量集合的该数据库的一种表示，在这里每一个 矢量对应于该数据库中的一行，并且每一个矢量的诸元素则对应于，对 一个特定的行来说，在各列中所包含的值，而该可检索的索引将针对各 列而被生成；以及
所述的划分包括将诸矢量划分为所述的一个或多个聚类。
3.根据权利要求1所述的方法，还包括将该索引全部地存入一部计算 机的主存储器的步骤。
4.根据权利要求1所述的方法，所述生成降维聚类还包括下列诸步 骤：
为所述每一个聚类产生一个转置矩阵以及该转置矩阵的诸特征值； 以及
选择包括最大特征值在内的诸特征值的一个子集，其中该降维信息 包括该转置矩阵以及诸特征值的该子集。
5.根据权利要求4所述的方法，其中为使用降维索引去检索K个与 所指定数据最相似的记录，它包括下列诸步骤：
根据存储的聚类信息，把所指定的数据关联到如上所述的一个或多 个聚类上；
根据所存储的相关聚类的降维信息，把所指定的数据投影到针对该 相关聚类的子空间上；
响应于所述的投影，生成降维信息，它包括已投影的指定数据的一 个正交的余集；
通过该索引检索与已投影的指定数据有K个最相似记录的相关聚 类；
确定是否有任何其他相关的聚类含有K个跟投影的指定数据最相似 的诸记录中的任何一个或多个；以及
重复所述检索，以便找到含有跟该指定数据最相似的K个记录中的 任何一个或多个的所述任何聚类。
6.根据权利要求5的方法，所述的通过索引去检索相关聚类，还包括 如下诸步骤：
计算作为失配指数δ2的一个函数的介于该相关聚类的K个最近邻和 已投影的指定数据之间的距离(D)，这里：
δ2(样板，元素)＝D2(投影的样板，元素)+∑‖正交余集‖2
7.根据权利要求5的方法，该指定的数据包括一个检索样板，它还包 括如下诸步骤：
如上所述的投影步骤包括使用降维信息把该样板投影到与它所属的 聚类有关的一个子空间上；
为一个投影的样板生成样板降维信息，这里所述通过索引的检索是 根据该投影的样板和该样板降维信息；并且
更新K个与检索样板最相似记录的K个最近邻集合。
8.根据权利要求2的方法，所述的选择诸特征值的一个子集是返回结 果的查准率和查全率的一个函数。
9.根据权利要求1的方法，其中为检索与指定数据最相似的K个记 录，该方法包括如下诸步骤：
根据聚类信息识别指定数据所属的一个聚类；
根据该识别出的聚类的降维信息，对该指定的数据进行降维；
响应于如上所述的降维，为降维的指定数据生成降维信息；
使用该降维信息，针对指定数据所属的聚类的一个降维版本，检索 该多维索引；
通过该多维索引检索该聚类中K个最相似的记录；
识别其它的诸候选聚类，它们可能含有与该指定数据的距离比检索 出的K个最相似记录中的最远者更接近的诸记录；
响应于如上所述的确定步骤，检索一个与该指定数据最接近的其它 候选聚类；以及
对所有如上所述的候选聚类，重复如上所述的识别和检索步骤。
10.根据权利要求9的方法，还包括如下诸步骤：
计算作为失配指数δ2的一个函数的介于该聚类的该版本的K个最近 邻跟已投影的指定数据之间的距离(D)，这里，
δ2(样板，元素)＝D2(投影的样板，元素)+∑‖正交余集‖2
11.根据权利要求1的方法，其中聚类信息包括如上所述的一个或多 个聚类的质心信息，它还包括把质心同一个唯一标号关联在一起的步骤。
12.根据权利要求1的方法，其中的数据维数＞8。
13.根据权利要求1的方法，其中为实施一次精确检索，包括如下诸 步骤：
根据存储的聚类信息，把指定的数据关联到一个聚类；
响应于如上所述的关联步骤，根据针对一个聚类的降维版本所存储 的降维信息，对指定的数据进行降维；以及
根据已降维的指定数据，检索与指定数据相匹配的该聚类的降维版 本。
14.根据权利要求13的方法，所述的检索还包括进行线性扫描以匹配 该指定数据的步骤。
15.根据权利要求1的方法，其中为执行一次精确检索，包括步骤：
递归地使用如下诸步骤：
使用存储的聚类信息，寻找指定数据所属的聚类；以及
使用存储的降维信息对指定的数据进行降维，直至到达降维聚类层 次结构中相应的最低层次；以及
使用诸低维索引，检索与指定数据相匹配的该聚类的降维版本。
16.根据权利要求1的方法，其中为执行相似检索，还包括步骤：
递归地使用如下诸步骤：
使用存储的聚类信息，寻找指定数据所属的聚类；以及
使用存储的降维信息，对指定的数据进行降维，以便与降维聚类层 次结构中的最低层次相一致；
从该指定数据所属的所述层次结构中处于一个最低层次的一个最终 聚类开始，检索候选的诸最终聚类，后者含有在诸降维聚类的层次结构 中处于每一个层次上的该指定数据的K个最近邻中的一个或多个；以及
对于每一个候选的最终聚类，执行一次聚类内部检索，以便找到该 指定数据的K个最近邻。
17.根据权利要求1的方法，其中为执行相似检索，还包括如下诸步 骤：
对指定数据进行降维；
递归地执行如下诸步骤：使用存储的聚类信息，寻找已降维的指定 数据所属的聚类；以及使用存储的降维信息，对降维的指定数据进行降 维，以便与降维聚类层次结构中的一个最低层次相一致；
从该指定数据所属的所述层次结构中处于一个最低层次的一个最终 聚类开始，检索候选的诸最终聚类，后者含有在诸降维聚类的层次结构 中处于每一个层次上的该已降维的指定数据的K个最近邻中的一个或多 个；以及
对每一个候选的最终聚类，执行一次聚类内部检索，以便找到该已 降维的指定数据的K个最近邻。
18.根据权利要求1的方法，其中数据存储在数据库中，还包括如下 诸步骤：
对数据库进行降维，并生成有关该数据库的降维信息；以及
存储与该数据库有关的降维信息；其中所述的划分步骤对应于所述 的降维步骤。
19.根据权利要求18的方法，其中为执行一次精确检索，包括如下诸 步骤：
根据数据库的降维信息，对指定的数据进行降维；
响应于如上所述的降维，根据该聚类信息，把已降维的指定数据关 联到其中一个聚类；
根据相关聚类的降维信息，把该指定的数据降维到由相关聚类所规 定的一个降维聚类；以及
根据该指定数据的一个降维版本，检索一个匹配的降维聚类。
20.根据权利要求18的方法，其中为执行相似检索，包括如下诸步骤：
使用与该数据库有关的降维信息，对指定的数据进行降维；
根据该聚类信息，寻找已降维的指定数据所属的该聚类；
根据一个已识别出的聚类的降维信息，对已降维的指定数据再次进 行降维；
检索经过再次降维的指定数据所属的该聚类的一个降维版本；
在该聚类中通过多维索引检索K个与该经过再次降维的指定数据最 相似的记录；
估计是否有任何其它聚类含有比检索出的K个记录中的最远者更接 近指定数据的记录；
响应如上所述的估计步骤，检索出一个最接近于该指定数据的其他 聚类；以及
对所有如上所述的其它聚类重复进行所述的估计和检索步骤。
21.根据权利要求18的方法，其中数据存储在数据库中，还包括如下 步骤：为如上所述的一个或多个已降维的诸聚类生成并存储一个或多个 可检索的降维索引。
22.根据权利要求18的方法，其中为执行一次精确检索，包括如下诸 步骤：
根据所存储的聚类信息，把指定的数据关联到一个聚类；
响应于如上所述的关联，把指定的数据分解为由相关聚类以及针对 该相关聚类而存储的降维信息所定义的一个降维聚类；以及
根据已分解的指定数据，在如上所述的索引中检索一个匹配的降维 聚类。
23.根据权利要求22的方法，其中检索提问式包括一个检索样板，还 包括如下诸步骤：
所述的关联包括根据所存储的聚类信息使该检索样板跟一个聚类相 符合；
所述的分解包括根据所存储的降维信息把该检索样板投影到一个相 符合的聚类的一个子空间上；以及
所述的检索包括执行一次聚类内部检索，以便找到一个投影样板。
24.根据权利要求1的方法，还包括如下诸步骤：
(a)生成聚类边界，它们相应于如上所述的聚类的几何形状的一个 零阶近似；
(b)借助于一个最小界限盒子，对每一个聚类的几何形状作出近似， 并从这里生成每个聚类的几何形状的一阶近似；
(c)把该界限盒子划分为2K个超矩形，这里所述的划分在每一维 的一个中点处进行；
(d)仅保留包含诸数据点的超矩形，并从这里生成该聚类的几何形 状的二阶近似；以及
(e)针对每一个保留的超矩形重复如上所述的步骤(c)和(d)， 以便依次生成该聚类的几何形状的3阶，4阶，......，n阶的近似。
25.根据权利要求24的方法，其中为检索每一个聚类的几何结构的多 层次近似，还包括如下诸步骤：
使用与该数据库有关的降维信息，对指定的数据进行降维；
根据该聚类信息，寻找已降维的指定数据所属的聚类；
根据一个相符合的聚类的降维信息，对已降维的指定数据再次进行 降维；
检索该经过再次降维的指定数据所属的该聚类的一个降维版本；
通过该多维索引，在该聚类中检索跟经过再次降维的指定数据最相 似的K个记录；
估计是否有一个或多个其它聚类含有比已检索出来的K个记录中最 远者更接近指定数据的记录；
根据该聚类的诸边界，只要一个其它聚类含有指定数据的K个最近 邻中的一个或多个，就保留该聚类；
根据越来越精确的对该几何形状的近似，迭代地确定是否有一个保 留的聚类可能包含K个最近邻中的一个或多个，并且只有当该聚类在相 继的近似过程的层次结构中在最精确的层次上被接受，才继续保留该已 保留的聚类；以及
响应于如上所述的迭代地确定的步骤，识别出一个含有数据的该K 个最近邻中的一个或多个的保留聚类作为一个候选聚类。

本发明涉及一个改进的信息系统。本发明的一个独特的方面就是涉 及生成和检索多维数据的简洁表示。本发明的一个更为独特的方面就是 在数据库系统中，使用有关的聚类与降维信息，来生成和检索多维数据 的简洁的索引表示。\n多维索引对各种空间的数据库来说是基础性的，它广泛地用于地理 信息系统(GIS)，联机分析处理(OLAP)，以便使用一个大型的数据 仓库以及各种多媒体数据库进行决策支持，在上述数据仓库和多媒体数 据库中，需要从图象和视频数据中抽取高维的诸特征矢量。\n决策支持正在迅速成为一项(促进)业务成功的关键技术。决策支 持允许一项业务从一个正在使用中的数据库中演绎有用的信息，后者通 常被称为一个数据仓库。该正在使用的数据库保存(当前)情况信息， 而该数据仓库典型地保存历史信息。数据仓库的用户通常更感兴趣的是 判别趋势，而不是注视孤立的个别记录。决策支持查询(或检索提问式) 在计算上是如此繁重并且要大量地使用群聚方法。这将导致长的完成延 迟以及不可接受的对生产能力的约束。\n某些用以减小延迟的已知技术是对频繁地提出的查询进行预先计 算，或者使用采样技术，或同时使用二者。具体地说，在非常大的关系 型数据库或数据仓库中，将联机分析处理(OLAP)技术，例如数据立方 体用于决策支持最近已经受到日益增长的关注(参看，例如，Jim Gray， Adam Bosworth，Andrew Layman，以及Hamid Pirahesh等人所写的 论文“数据立方体：一个用于对群聚、交叉表，以及部分和进行归一化的 关系聚集算子”，发表于国际数据工程会议论文集，1966年，新奥尔良， 第152-160页)(“Gray”)。在这里，诸用户典型地从数据仓库将该 历史数据视为多维数据立方体。在该立方体中的每一个单元(或晶格点) 是一个含有感兴趣的聚集，例如总销售额，的一个视图。\n多维的诸索引可以被用来回答不同类型的查询，包括：\n寻找在已索引的各列上具有所指定的数值的(诸)记录(精确检索)；\n寻找处于[a1，a2]，[b1，b2]，...，[z1，z2]之中的(诸)记录，这里a，b， 和z代表不同的维(范围检索)；以及\n寻找k个最相似于一个用户指定的样板或实例的诸记录(k-最近邻 检索)。\n多维索引也适用于图象的开采。图象开采的一个例子就是由IBM公 司在媒体矿工(MEDIAMINER)名称下注册商标的产品，它提供两种工 具：按图象内容查询(QBIC)；以及图象矿工(IMAGEMINER)，后 者用于通过分析其内容、而不是通过检索一个人工地生成的相关关键字的 列表，去取出图象。\nQBIC适合于用关键字不能提供一个适当的结果的应用场合，例如在 博物馆以及美术馆的图书馆中；或者在用于电子商务的联机仓库照片中， 在这里，各种视觉的产品目录让你使用颜色和纹理，例如墙纸和式样，按 细目进行检索。\n诸如图象矿工这样的图象开采应用让你使用像“森林风景”，“冰雪” 或“圆柱体”这样的概念性的提问式。诸如颜色、纹理和等高线这样的图 象内容被组合为能被该系统自动识别的诸简单对象。\n这些简单对象在一个知识库中被表示。这个采用文字叙述的分析结果 随后被索引以备以后检索。\n在执行一个数据库查询的过程中，该数据库检索程序访问一部分存储 的数据以及一部分索引结构，所访问的数据量取决于查询的类型以及该用 户提供的数据，还取决于该索引算法的效率。大型数据库是这样的：该数 据以及至少一部分索引结构驻留在该计算机系统的存储器层次结构中较大 的、较慢的、和较廉价的部分，通常包括一个或多个硬盘。在检索过程中， 该数据以及该索引结构的一部分被装入该存储器层次结构中的较快的诸部 分，例如该主存储器以及一级或多级高速缓冲存储器。该存储器层次结构 中的较快的诸部分通常是比较昂贵的，并因而仅构成该存储器层次结构的 存储容量的一个较小的百分比。一段使用能全部装入一级或多级高速缓冲 存储器的诸指令的程序跟一个此外还使用驻留在该主存储器的诸指令和数 据的过程相比，前者显得更块和更有效，而后者跟一段同时使用驻留在硬 盘的指令和数据的程序相比，也是较快的。技术上的限制是这样的：高速 缓冲存储器和主存储器的成本使得它如此之昂贵，以致于无法建立具有足 够(容量)的主存储器或高速缓冲存储器的计算机系统，用以完整地容纳 诸大型数据库。\n因此，存在对一种改进的索引技术的需求，该技术生成如此大小的诸 索引，使得大多数或全部索引在任何时间都能驻留在主存储器里面，并使 得在检索过程中，从该硬盘传输到该主存储器的数据量受到限制。本发明 能满足这样一种需求。\n若干已知的空间索引技术，例如R-树，可以被用于范围查询以及最 近邻查询。例如，在A.Guttman于1994年6月在美国明尼苏达州波士顿 举行的ACM SIGMOD数据管理会议上发表的论文“R-树：一种用于空 间检索的动态索引结构”中，就能找到关于R-树的叙述。然而，随着该 特征空间的维数的增加，这些技术的效率急剧地下降，因为该检索空间变 得越来越稀疏。例如，众所周知，当维数大于8时，诸如R-树那样的方 法是不能用的，在这里，有用性的标准就是完成一次请求的时间跟通过顺 序地扫描该数据库中的每一个记录以完成该请求所需的时间相比较。在高 维空间中常规索引技术的低效率是一种众所周知的被称为“维数的灾难” 的现象的结果，例如，在V.Cherkassky，J.H.Friedman，和H.Wechsles等 人所著的“从统计学到神经网络”一书中，就对此作了叙述，该书属于北 大西洋公约组织的ASI丛书，第136卷，Springer-Verlag公司1994年 出版。维数的灾难的相关结果就是，对于具有一个高维数的诸特征空间来 说，将该索引空间聚类为超立方体是一种低效率的方法。\n由于将现有的空间索引技术用于一个高维特征空间的索引带来的是低 效率，业界熟知的各种现有技术都是去降低一个特征空间的维数。例如， 可以用下列两种方法来降低维数：一种是借助于变量子集的选择(也称为 特征选择)，另一种是先进行单值分解，随后进行变量子集的选择，例如， 正如C.T.Chen在“线性系统理论和设计”一书中所教导的那样，该书由 Holt，Rinchart and Winton公司于1984年出版，参看该书附录E。变量 子集选择是在统计学研究中的一个众所周知的和活跃的领域，并且已经提 出了若干方法学的问题(参看例如，Shibata等发表于生物统计学杂志 I981年第68卷第1期第45-54页的论文：“回归变量的一种最佳选择”)。 只有在许多变量(数据库中的诸列)都是高度相关的情况下，在一个索引 生成系统中这些方法才是有效的。但在现实世界的数据库中，这种假设一 般来说是不正确的。\n因此，也存在对一种用于高维数据的改进的索引技术的需求，甚至在 存在不是高度相关的诸变量的情况下。本技术从存储器利用和检索速度的 观点出发，应当生成有效的诸索引。本发明能满足这些需求。\n按照前述各项需求，本发明专注于一种用于生成多维数据的简洁表示 的改进的装置与方法。本发明具有为诸数据库生成可检索的多维索引的诸 特征。本发明具有用于灵活地生成诸索引以及用于有效地进行精确与相似 检索的其他诸特征。本发明还具有用于生成简洁的索引的其他诸特征，在 检索过程中，上述索引有利地限制着从硬盘传输到主存储器的数据量。\n本发明的一项应用的一个例子就是用于多维索引。对空间数据库来 说，多维索引是基础性的，它广泛地应用于：地理信息系统(GIS)；使 用大型数据仓库用于决策支持的联机分析处理(OLAP)；以及用于开采 多媒体数据库的图象开采产品，在上述数据库中，需要从图象和视频数据 中抽取高维的诸特征矢量。\n一种具有本发明诸特征的计算机化方法的一个实例包括下列诸步骤： a)将该多维数据划分为一个或多个聚类；b)为诸聚类生成与存储聚类 信息；c)为诸聚类生成一个或多个降维聚类以及降维信息；以及d)存 储该降维信息。本发明还具有为诸降维聚类生成和存储一个降维索引的其 他特征。\n依赖于在每一个个别的聚类中使用的精确空间索引技术，通过使用相 应的索引机制就能检索该目标矢量。例如，常规的多维空间索引技术包括 但不局限于能在每一个聚类里面用于索引的该R-树。另一方面，若没有 可利用的空间索引结构，则该聚类内部检索机制可能是一种穷举检索或者 线性扫描。\n在一个优选实施例中，该降维步骤是一个单值分解过程，并且根据已 分解的指定数据，为找到一个匹配的降维聚类而检索该索引。该降维信息 的一个例子就是一个由单值分解过程生成的转置矩阵(包括诸特征至和诸 特征矢量)以及该转置矩阵的被选定的诸特征值。\n一种具有本发明诸特征的生成多维索引的方法的另一个例子包括下列 诸步骤：生成一个矢量集合，作为待索引的数据库的一种表示，其中每一 个矢量对应于该数据库的一行，并且对该特定的行来说，每一个矢量的诸 元素对应于包含在必须为其生成一个索引的诸列中的的诸数值；然后使用 一种聚类技术将该矢量集合划分为一个或多个群(也称为聚类)，同时生 成和存储与该聚类有关的聚类信息；接着对每一个群单独地使用一种降维 技术，以便在该聚类中生成诸元素的一个低维表示，并带有降维信息；使 用一种针对该聚类的维数生成有效索引的技术，为每一个降维聚类生成一 个索引。\n根据本发明的另一个特征，本方法可以单独地应用于每一个降维聚 类，因此本方法成为递归的。当该维数不能再降低时，递归地应用降维和 聚类二者的过程结束。\n根据本发明的另一个特征，作为索引生成的第一步(在该数据库划分 步骤之前)，可以对整个数据库实行一个降维步骤。在执行该划分(也称 为聚类)与降维诸步骤的过程中，也生成聚类与降维信息以备检索阶段使 用。\n根据本发明的又一个特征，可以适当地选择该聚类步骤以便于该降维 步骤的实行。这一步可以这样来完成，例如，借助于一种聚类方法，它能 根据该数据的局部协方差结构来划分该空间，取代原先将由一个空间不变 距离函数，例如该欧几里德距离，所导出的损失最小化的方法。\n本发明还具有这样的特征，用于估计是否还有其他诸聚类，它们应含 有离开该指定数据的距离比已检出的k个最相似元素中的最远者更近一 些的诸元素。正如业界所熟知的那样，聚类信息可以被用来重建该分区的 边界，而这些边界可以被用来确定是否有一个聚类能含有k个最近邻中的 一个。专业人士将理解到，该聚类的诸边界是对该聚类本身结构的一种简 单近似，换句话说，不可能从该边界的数学形式去告诉人们是否有一些聚 类的诸元素靠近该边界上的任何给定位置。作为一个例子，考虑这样一种 情况：该数据库含有两个球形的数据聚类，并且这两个聚类彼此相距甚远。 本例的一条合理的边界应该是一个超平面，它垂直于这两个聚类的质心的 连线并跟这两个质心等距。由于诸聚类是广阔地分开的，所以在靠近边界 处没有数据点。在另一个例子中，该边界可以十分靠近这两个聚类的大量 元素。相应地，本发明还具有这样的特征：使用一种对每一个聚类的实际 几何结构的多层次的近似，去确定是否有一个聚类能含有该指定数据的k 个最近邻中的一个或多个。\n在一个优选实施例中，本发明被体现为存储在一个程序存储装置里面 的软件，它可以被一部实际装有一段该机器可执行的诸指令组成的程序的 机器所读出，以便执行下列的诸方法步骤：生成多维数据的各种简洁表示， 有效地进行精确与相似检索；为诸数据库生成可检索的多维索引；并使用 这些索引进行精确与相似检索。\n从下面结合诸附图所作的详细说明中，本发明的这些和其他特征和优 点将变得更加明显，在附图中：\n图1表示一个联网的客户机/服务器系统的方框图的一个例子；\n图2表示诸数据点的分布以及在划分聚类之后降维的直觉知识的一个 例子；\n图3表示将一个3维空间中的3个点投影到一个2维空间，使得该投 影保留这3点中的任何两点之间的相对距离的一个例子；\n图4表示将一个3维空间中的3个点投影到一个2维空间，而该相对 距离的大小顺序受到该投影的影响的一个例子；\n图5表示介于该原始空间的诸点以及该投影子空间之间的距离的计算 的一个例子；\n图6表示从该数据库中的数据生成该多维索引的一种逻辑流的一个例 子；\n图7表示实行该数据的降维过程的一种逻辑流的一个例子；\n图8表示使用在没有递归分解和聚类的条件下生成的该索引的一次精 确检索的逻辑流的一个例子；\n图9表示使用在递归分解和聚类的条件下生成的该索引的一次精确检 索的逻辑流的一个例子；\n图10表示使用在没有递归分解和聚类的条件下生成的该索引进行一 次k-最近邻检索的逻辑流的一个例子；\n图11表示使用在递归分解和聚类的条件下生成的该索引的一次k- 最近邻检索的逻辑流的一个例子；\n图12表示在一个3维空间中的数据的一个例子，以及一种基于欧克里 特距离的聚类技术跟一种适应于该数据的局部结构的聚类技术的结果比 较；\n图13表示一种适应于该数据的局部结构的聚类技术的逻辑流的一个例 子；\n图14表示在一个3维空间中的一个复杂超平面以及使用一个3维象限 树生成算法生成的两次连续的近似的一个例子；以及\n图15表示使用诸聚类的几何形状的多次连续近似，来确定是否含有比 从一个给定矢量起算的一个固定距离更接近的诸元素的诸聚类的逻辑流的 一个例子。\n图1描述具有本发明诸特征的一种客户机/服务器结构的一个例子。 如该图所描述的那样，多个客户机(101)以及多个服务器(106)通过 一个网络(102)被互连在一起。该服务器(106)包括一个数据库管理 系统(DBMS)(104)以及直接访问存储装置(DASD)(105)。典 型地在该客户机(101)准备一次查询，并通过该网络提交到该服务器 (106)。该查询典型地包括指定的数据，例如一个用户提供的实例或检 索样板，该查询还跟一个数据库管理系统(DBMS)(104)进行交互， 以便检索或更新存储在该DASD(105)中的一个数据库。DBMS的一个 例子就是由IBM公司所销售的，其商标为DB2。\n根据本发明的一个方面，查询需要多维的(数据)，例如，空间索引 (包括范围查询以及最近邻查询)将激活该多维索引处理器(107)。该 多维索引处理器(107)(将参考图8-11加以说明)负责检索那些满足 一定的约束条件的诸矢量或诸记录，上述约束条件是由该查询基于一个或 多个简洁的多维索引(108)和聚类(111)以及由本发明的索引生成逻 辑(将参考图6和7加以说明)生成的降维信息(112)来说明的。本发 明大多数(如果不是全部)的简洁索引(108)最好被存储在该服务器 (106)的主存储器和/或高速缓冲存储器里面。专业人士将理解到，一 个数据库，例如一个空间数据库，可以驻留在一个或多个系统之中。专业 人士也将理解到，该多维索引处理器(107)和/或该索引生成逻辑 (110)可以被组合或者被纳入作为该DBMS(104)的一部分。该有效 的索引生成逻辑(110)以及该多维索引处理器(也被称为检索逻辑)可 以作为软件被实实在在地嵌入到能在该服务器(106)上执行的一种计算 机程序产品中去。\n一项应用的一个例子就是用于一个超级市场的仓储销售点交易，包括 该商店位置的地理坐标(经度和纬度)。在这里，该服务器(106)最好 也能支持决策支持的应用类型，以便从该存储的数据中发现知识或模式。 例如，一个联机分析(OLAP)处理器(103)可以被用来截取涉及OLAP 的诸查询，以便使它们的处理更加简便。根据本发明，该OLAP处理器， 可能与该DBMS相结合，使用该多维索引处理器(107)，针对涉及OLAP 的诸查询去检索该索引(108)。专业人士将理解到，本发明的索引生成 逻辑(110)适用于一个数据仓库的多维数据立方体表示。一种用于生成 一个数据仓库的多维数据立方体表示的方法和系统在共同未决的美国专利 申请S/N 08/843,290，1997年4月14日由Castelli等人申请，题为“生 成一个数据立方体的多维表示的系统与方法”的专利中作了说明，该文被 全部收入本文作为参考文献。\n多媒体数据是从空间索引中获益的数据的另一个例子。诸如音频，视 频和图象这样的多媒体数据可以从用于索引的该亚数据中分开地被存储。 该亚数据中能够被用来简化该媒体的索引与检索的重要成分就是从该原始 数据中抽取的诸特征矢量。例如，一种纹理，彩色直方图以及形状都可以 从该图象的各区域抽取，并且被用来构成用于检索的诸索引(108)。\n图象开采应用的一个例子就是QBIC，它是IBM的DB2图象扩展 器的集成的检索设备。QBIC包括一个图象查询处理器(服务器)，以及 一个样本客户机，后者包括一个HTML图形用户接口以及相关的公共网 关接口(CGI)，把它们结合在一起，以形成一个完整的应用的基础。该 服务器以及该客户机都是可扩展的，因此一个用户可以开发一个针对特定 应用的图形匹配功能，并把它添加到QBIC中去。该图象检索服务器允许 基于视频图象内容的大型图象数据库的查询。它具有下列特征：\n在视频介质中进行查询。“把像这样的图象显示给我看”，在这里， 你定义“像”甚麽，意味着依照颜色、布局、纹理，等等。\n根据对该查询图象的相似程度来排列诸图象。\n自动建立图象索引，在这里关于颜色和纹理的数字描述符被存储。在 一次检索过程中，这些特性被用来寻找相似的图象。\n视频查询跟文本查询或按参数(例如一个日期)查询的组合。\n类似地，可以这样来生成索引，首先，生成待索引为一组矢量的该数 据库的一种表示，在这里每一个矢量对应于该数据库中的一行，并且对于 该特定的行来说，每一个矢量的诸元素对应于在各列(必须为每一列生成 一个索引)中所含有的诸数值。\n用一组矢量作为该数据库的一种表示在业界中是众所周知的。该表示 可以用，但不局限于，下列方法来生成：针对该数据库的每一行，生成一 个等于待生成的索引的维数的长度的阵列；并将必须为它生成一个索引的 相应的行中各列所含有的数值拷贝到该阵列的诸元素中去。\n假设一个矢量v的第i个元素为vi，则该矢量v可以表示为\nv＝[vI...vN]    (1)\n式中，“N”为被用于索引的该矢量的维数。\n该客户机一方通常可以指定三种类型的查询，它们全都需要某种空间 索引的形式，如在背景情况中所说明的那样：\n(1)精确查询：指定一个矢量，并且跟该矢量匹配的诸记录或多媒 体数据将被检索出来；\n(2)范围查询：指定该矢量的每一维的上下限，\n(3)最近邻查询：基于一种相似性度量，最“相似的”诸矢量将被 检索出来。\n介于两个矢量v1和v2之间最常用的相似性度量，就是该欧几里德 距离度量d，它被定义为\nd2＝∑(V1i-V2i)2       (2)\n要注意的是，并不是所有的各个维i都有必要参与范围查询或最近邻 查询的计算过程。在这两种情况下，可以指定该维的一个子集以便把诸结 果检索出来。\n图2表示在一个多维空间中，诸矢量的分布的一个例子。如图所示， 为了表示整个空间，总共需要3个维。然而，由于聚类201、202和203分 别被定位于该x-y，y-z，和z-x诸平面，所以，为了表示每一个个别的聚 类，只需要两个维。因此，可以归结为，通过对该数据进行适当的聚类， 就能实现降维。仅用单值分解不能实现同样的降维，它只能对该特征空间 进行重新定向，使得在该空间中的轴符合于主要的各个维(在本例中为3)。\n消除一个矢量中的一个或多个维等效于将诸原点投影到一个子空间。 方程式(2)表示，只有在其矢量中个别元素不同的那些维才需要被计算。 其结果是，将一个矢量投影到一个子空间并不影响该距离的计算，假定在 该原始空间中那些被消除的元素不发生变化。\n图3表示在该原始空间以及一个投影的子空间中距离计算的一个例 子，在这里该投影能使该3点中任何两点的相对距离保持不变。如图所示， 在该原始的3维(3-D)空间中，点(301)到另一个点(302)的距 离，比它到第3点(303)的距离更远一些。这里，这些点(分别是304、 305和306)在2维(2-D)子空间中的投影保留了诸点之间的相对距 离。\n图4表示将在一个3维空间中的3个点投影到一个2维空间的例子， 在这里该投影影响了该相对距离的大小顺序。如图所示，在该3维空间中， 点(401)和(402)之间的距离大于点(402)和(403)之间的距离。 然而在本例中，在各自的投影点(404)和(405)之间的距离短于点 (405)和(406)之间的投影距离。因此，在该投影子空间中，介于两 点之间的相对距离可能没有被保留。\n下面，将导出一种方法学，用以估计将诸矢量投影到子空间时所能导 致的最大误差。该过程开始于确定该最大误差的边界。将一个聚类的质心 表示为Vc，它被定义为\n$V_c=\frac{1}{N}\Sigma V_i---\left(3\right)$\n式中，N为包括诸矢量{V1，...，VN}在内的该聚类中矢量的总数。 该聚类被投影到一个k维子空间之后，不失一般性地说，最后(n-k) 个维被消除，在该子空间中，任何两个矢量之间的距离，跟在原始空间时 相比，都引入了一个误差，该误差项为\n\n下列的不等式立即成立：\n\n$\le \underset{i=k+1}{\overset{n}{\Sigma }}{\left(2\max \left(\right|V_{1,i}|,|V_{2,i}\left|\right)\right)}^2---\left(5\right)$\n$\le 4\underset{i=k+1}{\overset{n}{\Sigma }}\max {\left(\right|V_{1,i}|,|V_{2,i}\left|\right)}^2$\n方程式(5)表明，在该子空间中，因计算距离而引起的最大误差是 有界的。\n图5表示根据本发明在计算距离时一种近似方法的例子。介于一个样 板点T(501)和一个上位点V(506)之间的距离由方程式(2)给出。 这个欧几里德距离就以下各点来说是不变的：参考坐标系的旋转；坐标系 的原点的变换；坐标轴的映射；以及诸坐标的定序。接着，不失一般性。 令该点V(506)属于图5中的聚类1。随后考虑由聚类1的协方差矩阵 中的诸特征矢量所定义的参考坐标系，并且令该参考坐标系的原点为质心 1。在聚类1(505)中，该样板点T(501)到一个上位点V的距离可 以被写成\n$d^2=\underset{i=1}{\overset{n}{\Sigma }}{(T_i-V_i)}^2---\left(6\right)$\n式中，诸坐标Ti和Vi都是相对于该参考系而言的。下一步，通过 将最后n-k+1个坐标设置为0，将聚类1(505)的诸元素投影到子空 间1。现在，介于该样板点T(501)以及V (506)在子空间1上的 投影V’(507)之间的距离为\n$d^{12}=\underset{i=1}{\overset{n}{\Sigma }}{(T_i-V_i)}^2+\underset{i=k+1}{\overset{n}{\Sigma }}{\left(T_i\right)}^2$\n$={d_1}^2+{d_2}^2---\left(7\right)$\n项d1是介于该样板点在子空间1上的投影(504)，称为投影1，以 及V(506)在子空间1上的投影V’(507)之间的欧几里德距离；项 d2是该样板点T(501)以及投影1(504)(它在子空间1上的投影) 之间的距离；换句话说，d2是介于该样板点T(501)与子空间1之间 的距离。现在，在计算介于该样板点T(501)以及该矢量V(506) 之间的距离时，通过用方程式(7)来置换方程式(6)，所引入的近似 就可以被界定。初等几何学教导说，这里的3个点T(501)，V(506) 和V，(507)决定一个唯一的2维子空间(一个平面)。为了使讨论简化， 令这个平面对应于图5所示的平面(520)。则在方程式(6)中所定义 的距离d等于连结T(501)和V(506)的线段的长度，在方程式(7) 中所定义的距离d’就是连结T(501)和V’(507)的线段的长度。 在初等几何学中有一条众所周知的定理说，三角形一边的长度大于其余两 边的长度之差的绝对值，并且短于它们之和。这就包含着下述的意思：用 在方程式(7)中所定义的距离d’来置换在方程式(6)中所定义的距 离d，引入的误差小于或等于连结V(506)和V’(507)的线段的长 度；因此，平方误差的边界为\n\n图6表示一份流程图的一个例子，该流程图用于生成一个降维聚类的 层次结构，并且为处于该层次结构底部的诸聚类生成低维的索引。在步骤 601，一个聚类过程取原始数据(602)作为输入，将该数据划分为诸数据 聚类(603)，并根据该分区的诸细节生成聚类信息(604)。原始数据 中的每一行包括一个由方程式(1)所定义的矢量属性。该聚类算法可以 从，但不局限于，业界熟知的任何一种聚类或矢量量化算法中选择，像下 列诸作者所教导的那样，例如：Leonard Kauffman和Peter J. Rousseeuw所著的书“找出数据中的群”，John Wiley & Sons公司 出版，1990年，或者Yoseph Linde，Andres Buzo和Robert M.Gray所 写的论文“一种用于矢量量化器设计的算法”，发表于“IEEE通信汇刊” 杂志，COM-28卷，第1期，1980年1月，第84-95页。由一种聚 类算法的学习阶段所产生的聚类信息(604)随算法的不同而改变；这样 的信息允许该算法的分类阶段产生任何新的、以前没有见过其样本的聚类 数目，并且为每一个聚类生成一个代表性的矢量。最好是，该聚类信息包 括诸聚类的诸质心，每一个连结着一个唯一的标号(参看例如，Yoseph Linde，Andres Buzo和Robert M.Gray等在“一种用于矢量量化器设计 的算法”，上)。在步骤605，一个顺序逻辑开始执行，它控制诸操作的 流程，使得以下诸操作被个别地和顺序地施加到每一个聚类。专业人士将 理解到，在多重计算电路的情况下，可以用一个调度逻辑电路来代替该顺 序逻辑电路(605)，前者在不同的计算电路上开始同时的计算，其中的 每一个对一个不同的数据聚类进行操作。在步骤606，该降维逻辑(606) 接收一个数据聚类(603)并产生降维信息(607)以及一个降维后的数 据聚类(608)。在步骤609，执行一项结束条件测试(将在下面讨论)。 若不满足该结束条件，则在步骤611，通过用降维后的数据聚类(608) 去置换该原始数据(602)以及该过程返回到步骤601，递归地执行步骤 601-609。若在步骤610满足该结束条件，则为该聚类生成一个可检索的 索引(612)。在步骤613，若已经分析过的聚类数目等于该聚类算法在 步骤601中所产生的诸聚类(603)的总数，则该计算过程结束。否则， 该过程返回到步骤605。聚类数目的选择通常由用户进行，但也存在为业 界所熟知的自动步骤；参看例如，Brian Everitt所著“聚类分析”一书第 4章第2节，Halsted出版社，1973年出版。\n步骤609的结束条件测试的一个例子可以基于数据体积V(X)的概念， 它被定义为\n$V\left(X\right)={\Sigma }_{i=1}^m{n}_i$\n式中X为诸记录的一个集合，ni为第i个记录的大小，并且该总和 表示X的诸元素的全部。若在降维步骤606之前，诸记录具有相同的大小 S，并且n表示在一个聚类中记录的数目，则该聚类的体积为Sn。若S表 示经过降维步骤606之后的一个记录的大小，则在降维之后该聚类的体积 为S’n。通过比较诸体积Sn和S’n，就可以测试该结束条件，若Sn＝ S’n，则结束。\n在另一个实施例中，不存在步骤609中的结束条件测试，并且不进行 本方法的递归应用。\n图7表示步骤606的降维逻辑的一个例子。如图所示，在步骤701， 一个单值分解逻辑(701)取该数据聚类(702)作为输入，并生成一个 转置矩阵(703)以及该转置矩阵(703)的诸特征值(704)(或诸特 性值)。转置矩阵的诸列是该矩阵的诸特征矢量(或诸特性矢量)。用于 单值分解的各种算法在业界中是众所周知的；参看例如，R.A.Horn和C， R.Johnson所著“矩阵分析”一书，Cambridge大学出版社(1985年)。 专业人士将理解到，可以用执行相同的或等效的操作的任何逻辑来代替单 值分解逻辑。在一个可供选择的实施例中，可以用在业界中众所周知的主 成分分析逻辑来代替该单值分解逻辑。\n在步骤705，一个排序逻辑取诸特征值(704)作为输入，并生成按 大小降序(706)排序的诸特征值。该排序逻辑可以是为业界所熟知的多 种排序逻辑中的任何一种。在步骤707，该选择逻辑根据一种选择标准， 选出含有最大的特征值(708)的有序的诸特征值(706)的一个子集。 该选择逻辑可以是，但不局限于，选出诸特征值的最小群，其和大于该转 置矩阵(703)的迹线的一个用户指定的百分比，正如业界所熟知的那样， 该迹线就是在该对角线上的诸元素的总和。在本例中，该转置矩阵(703) 以及该选定的诸特征值(708)包括降维信息(607)。另一方面，也可 以基于一种查准率与查全率的折衷(将在下面讨论)来选择诸特征值。\n在步骤709，该转置逻辑取该数据聚类(702)以及该转置矩阵 (703)作为输入，并将由该转置矩阵所指明的一种转置施加到该数据聚 类(702)的诸元素之上，同时生成一个转置后的数据聚类(710)。在 步骤711，诸选定的特征值(708)以及该转置的数据聚类(710)被用 来生成该降维后的数据聚类(712)。在一个优选实施例中，通过保留最 小的维数来完成降维，使得相应的特征值的集合至少相当于全部变量的一 个固定的百分比，例如该固定百分比可以取值为等于95％。\n另一方面，也可以基于一种查准率与查全率的折衷来选择诸特征值。 为了理解查准率和查全率，重要的是记住，用本发明的一种方法来进行的 检索操作可以是近似的(下面将参考图10-11加以说明)。在一个具有N 个元素的数据库中，用k来表示一个样板的所希望的最近邻的数目。这 里，由于该操作是近似的，典型地，一个用户要求返回多于k个的若干结 果。令n表示返回结果的数目，在该n个结果中，仅有c个是正确的， 在这个意义上，它们对该样板来说就是那k个最近邻。查准率就是返回的 诸结果中正确的部分所占的比例，并且被定义为\n查准率＝c/n，\n而查全率则是通过检索被返回的诸正确结果所占的比例，那就是，\n查全率＝c/k.\n由于查准率和查全率随着样板的选择而发生改变，所以它们的期望值 就是该系统性能的一个较好的度量。因此，查准率和查全率二者都意味着 取自诸样板的分布的期望值(E)，它们是固定值n和k的一个函数：\n查准率＝E(c)/n，\n查全率＝E(c)/k.\n要注意的是，随着返回结果的数目增加，查准率减小而查全率增加。 一般来说，查准率与查全率的趋势不是单调的。由于E(c)依赖于n，通 常可以将效率对查全率的曲线描绘为n的一个参数函数。在一个优选的实 施例中，一个申请人指定所希望的该检索的查准率以及被允许的查全率的 下限。然后该降维逻辑根据查准率和查全率按下列步骤进行降维：在按降 序对诸特征值进行排序之后，该降维逻辑(步骤606，图6)去除对应于 该最小特征值的维，并根据从该原始训练集随机选出的或由该用户提供的 诸样本的一个测试集，估计所得结果的查准率对查全率的函数。从该查准 率对查全率的函数出发，该降维逻辑导出一个能达到所希望的查全率的查 准率的一个最大值nmax。随后该降维逻辑通过去除对应于次最小特征值的 维，迭代执行该相同的过程，并计算在达到所希望的查全率的条件下相应 的查准率。当计算所得的查准率低于该用户指定的阈值时，该迭代过程结 束，并且该降维逻辑仅保留在结束条件出现的前一瞬间在迭代过程中所保 留的那一个维。\n在本发明的另一个实施例中，该申请人仅指定所希望的查全率的一个 值，并且该降维逻辑估计在达到所希望的查全率的条件下，增加查准率所 付出的代价。这个代价有两种成分：其一随着维数的增加而减小，因为在 较低维数的空间中，计算距离以及检索诸最近邻是更加有效的；其二是一 种增加的成分，这是基于这样的事实：为了保证所希望的查全率数值，随 着被保留的维数的降低，检索结果的数目应当增加。即使使用各种有效的 方法，要检出一个较大数目n的最近邻，(其代价)是比较昂贵的，因为 随着所希望的结果的数目增加，应当被分析的检索空间的这一部分也随之 增加。然后该降维逻辑通过详尽的检索，寻找在达到该用户指定的查全率 数值、并使检索费用为最低的条件下，能保留的维数。\n该聚类和单值分解过程可以递归地应用于诸矢量(步骤601-611) 直至达到一个结束条件为止。一种这样的结束条件可以是每一个聚类的维 数不再像本文所描述的那样继续降低。可选择地，诸如R-树那样的更常 见的空间索引技术也可以应用于每一个聚类。这些技术对于那些维数已经 最小化的诸聚类来说是更为有效的。由此将对一组高维矢量完成整个索引 生成过程。\n正如将在下面参考图8-15所说明的那样，本发明也具有使用多维数 据的简洁表示来进行有效检索的诸特征。专业人士将理解到，本发明的各 种检索方法并不局限于本文所叙述的多维数据的特定的简洁表示。\n图8表示一种基于根据本发明生成的可检索的索引(108或612)的 精确检索过程的逻辑流程的一个例子。在本例中，该索引是在不进行该聚 类以及单值分解过程的递归应用的条件下生成的。精确检索是检出跟一个 检索提问式、例如一个检索样板精确地匹配的一个或多个记录的过程。如 图所示，在步骤802，该多维索引处理器(107)(也称为聚类检索逻辑) 接收到包括指定的数据在内的一个提问式，诸如一个检索样板(801)。 在步骤802，在图6的步骤601中所生成的聚类信息(604)被用来识别 该检索样板所属的该聚类。在步骤803，在图6的步骤606中生成的降维 信息(607)被用来将该输入样板投影到与在步骤802中所识别的该聚类 有关的该子空间，并生成一个投影的样板(804)。在步骤805，一个聚 类内部检索逻辑使用在图6的步骤610中所生成的可检索的索引(612) 去检索该投影样板。要注意的是，若没有空间索引结构可供利用的话，则 在每一个聚类之内，最简单的检索机制就是进行一次线性扫描(或者线性 检索)。在大多数场合，当该聚类的维数相当小(在多数情况下小于10) 时，诸如R-树那样的空间索引结构能提供较好的效率(与线性扫描相 比)。\n图9表示基于根据本发明生成的一种可检索的多维索引(108或 612)的精确检索过程的逻辑流程的另一个例子。在这里，该索引(108 或612)是在该聚类与降维逻辑的递归应用的条件下生成的。精确检索是 检出与该检索样板精确地匹配的一个或多个记录的过程。如图所示，一个 包括诸如一个检索样板那样的被指定的数据被用来作为该聚类检索逻辑的 输入，在步骤902，它类似于图8的步骤802中的聚类检索逻辑。在步骤 902，图6的步骤(601)所生成的聚类信息(604)被用来识别该检索样 板(901)所属的聚类。在步骤903(类似于图8的步骤803)，在图6 的步骤606中所产生的降维信息(607)，被用来将该输入样板投影到与 在步骤902中所识别的该聚类有关的该子空间，并生成一个投影样板 (904)。在步骤905，要确定该当前的聚类是不是结尾的，那就是说， 在该多维索引建立过程中，有没有更多的递归的聚类与单值分解步骤被施 加到该聚类。若该聚类不是结尾的，则在步骤907，该检索样板(901) 被该投影样板(904)所置换，并且该过程返回到步骤902。在步骤906， 若该聚类是结尾的，则该聚类内部检索逻辑使用该可检索的索引去检索该 投影样板。如同所指出的那样，若没有空间索引结构可供利用的话，则最 简单的聚类内部检索机制就是进行一次线性扫描(或者线性检索)。在大 多数场合，当该聚类的维数相当小(在多数情况下小于10)时，诸如R -树那样的空间索引结构能提供较好的效率(与线性扫描相比)。\n本发明也具有这样的诸特征，用以评定在其他诸聚类中，是否含有这 样的诸元素，它们跟已被检出的k个最相似的的元素中距离最远者相比， 更接近于该指定的数据。如同业界所熟知那样，聚类信息可以被用来重建 该分区的边界，并且这些边界可以被用来确定一个聚类是否含有k个最近 邻当中的一个。专业人士将理解到，该聚类的边界是对该聚类本身的结构 的一种简单近似。换句话说，不可能从该边界的数学形式去告诉人们，在 靠近该边界的任何给定位置上是否存在该聚类的诸元素。作为一个例子， 考虑这样一种情况：该数据库包括两个球形的数据聚类，它们互相之间距 离甚远。对这种情况来说，一个合理的边界应当是一个垂直于这两个聚类 的质心的连线并与这两个质心等距的超平面。然而，由于这两个聚类相距 甚远，所以在靠近边界处没有数据点。在其他例子中，该边界可能跟两个 聚类的大量元素十分靠近。\n正如将在下面参考图14和15加以说明的那样，除了聚类信息以外， 本发明还具有针对每一个聚类的实际几何结构，计算和存储一个多层次的 近似这样的特征；并且使用该近似结构去识别那些可能含有跟一个给定矢 量的距离短于一个固定数值的诸元素的那些聚类。\n图10表示基于根据本发明生成的一个索引(612)的一次k-最近邻 检索过程的一份流程图的一个例子。在这个例子中，该索引是在没有递归 地应用该聚类与单值分解过程的条件下生成的。该k-最近邻检索返回在 该数据库中与提问式相匹配的k个最接近的行。所希望的匹配数目 (nr)，k(1000)在步骤1002中被用来对该含有k个元素的最近邻集 合(1009)进行初始化，因此它最多含有k个元素，并且因此在下一个 步骤开始之前它是空的。在步骤1003，该聚类检索逻辑接收该检索提问式， 例如该检索样板(1001)，并使用在图6的步骤601中所生成的该聚类信 息(604)，以确定该检索样板属于那一个聚类。在步骤1004，使用该降 维信息(607)，将样板投影到与它所属的该聚类有关的该子空间。该投 影步骤1004产生一个投影样板(1006)以及降维信息(1005)，后者包 括该投影样板(1006)的一个正交余集(它被定义为该检索样板(1001) 以及该投影样板(1006)的矢量差)，以及该正交余集的欧几里德长度。 在步骤1007，该降维信息(1005)以及该投影样板(1006)可以被该聚 类内部检索逻辑所使用，后者使用该多维索引，更新该含有k个元素的最 近邻集合(1009)。根据本发明，合适的聚类内部检索逻辑包括业界所熟 知的最近邻检索方法；参看例如，Belur V.Desarathy(编者)所著的“最 近邻模式分类技术”一书，IEEE计算机学会(1991年)。具有本发明诸 特征的一种聚类内部检索逻辑(步骤1007)的一个例子包括下列诸步骤： 首先，计算该投影样板(1006)跟该聚类诸成员之间在已降维的矢量空间 中的平方距离；其结果被追加到该检索样板(1001)跟该聚类的子空间之 间的平方距离之上，该最终结果被定义为该正交余集的平方长度之“和” (在步骤(1004)进行计算，它是该降维信息(1005)的一部分)：\nδ2(样板，元素)＝D2(投影的样板，元素)+∑‖正交余集‖2\n若在步骤1007开始时该含有k个元素的最近邻集合为空，并且若在 该聚类中诸元素的数目大于k，则该聚类内部检索(逻辑)用该聚类中最 接近该投影样板(1006)的k个元素来填充该含有k个元素的最近邻集 合，否则就用该聚类的全部元素来填充。该含有k个元素的最近邻集合 中的每一个元素都跟一个对应的失配指数δ2有关。\n若在步骤1007开始时，该含有k个元素的最近邻集合不为空，则当 一个其失配指数δ2小于当前与该含有k个元素的最近邻集合(1009) 中的诸元素有关的诸索引中的最大者的元素出现时，该聚类内部检索逻辑 在步骤1007更新该含有k个单元的最近邻集合。更新该含有k个元素的 最近邻集合的方法是这样的：从该含有k个元素的最近邻集合(1009) 中去除具有最大失配指数δ2的那个元素，并为它置换该新发现的元素。\n若该含有k个元素的最近邻集合(1009)含有少于k个元素，则 该缺失的诸元素被认为是处于无限远处的诸元素。在步骤1008，要确定是 否存在含有诸最近邻的另一个候选的聚类。这个步骤取该聚类信息(604) 作为输入，由此它能确定该聚类的边界。若不合该检索样板(1001)的一 个聚类的边界跟该含有k个元素的最近邻集合(1009)中的最远的元素 相比为更近时，则该聚类就是一个候选者。若不存在候选者，则该过程结 束，并且该含有k个元素的最近邻集合(1009)的内容作为一个结果被返 回。否则，该过程返回到步骤1004，在这里，该当前的聚类现在就成为在 步骤1008中所确认的候选聚类。\n图11表示基于根据本发明生成的一个检索索引(612)的k-最近邻 检索过程的一份流程图的一个例子。在这里，该索引是在该聚类以及单值 分解过程的递归应用的条件下生成的。该k-最近邻检索向采取一个检索 样板形式的指定的数据返回该数据库中最接近的k行。如图所示，在步骤 1102，该含有k个元素的最近邻集合被初始化以便清空，并且所希望的匹 配数目k(1000)被用来初始化该含有k个元素的最近邻聚合(1111)， 因此它最多可以包括k个元素。在步骤1103，该聚类检索逻辑取该检索 样板(1101)作为输入，并使用在图6的步骤601中所生成的聚类信息 (604)，将该检索样板合并到一个相应的聚类中去。在步骤1104，根据 在图6的步骤606所生成的降维信息(607)，该样板(1101)被投影到 一个与在步骤1103中所确认的聚类相连结的子空间。在步骤1104，一个 投影样板(1106)以及降维信息(1105)被生成。最好是，该降维信息 (1105)包括该投影样板(1106)的正交余集(它被定义为该检索样板 (1101)以及该投影样板(1106)之间的矢量差)，以及该正交余集的 欧几里德长度。在步骤1107，要确定该当前聚类是不是结尾的，那就是说， 在该索引建立过程中，有没有更多的聚类和单值分解的诸递归步骤被施加 到该当前聚类。若该当前聚类不是结尾的，则在步骤1108，用该投影样板 (1106)来置换该检索样板(1101)，并且该过程返回到步骤1103。否 则，在步骤1109，该降维信息(1105)以及该投影样板(1106)被该聚 类内部检索逻辑用来根据该可检索的索引(612)更新该含有k个元素的 最近邻集合(1111)。根据本发明的合适的聚类内部检索逻辑包括业界所 熟知的各种最近邻检索方法中的任何一种；参看例如，Belur V.Desarathy (编者)所著的“最近邻模式分类技术”一书，IEEE计算机学会，1991 年。具有本发明诸特征的一种聚类内部检索逻辑(步骤1007)包括下列诸 步骤：首先，计算该投影样板(1006)跟该聚类的诸成员之间在已降维的 该矢量空间中的平方距离，其结果被追加到该检索样板(1001)以及该聚 类的子空间之间的平方距离之上，其结果被定义为诸正交余集(在步骤 (1004)中进行计算，它是该降维信息(1005)的一部分)：\nδ2(样板，元素)＝D2(投影的样板，元素)+∑‖正交余集‖2\n在步骤1109开始时，若该含有k个元素的最近邻集合(1111)为 空，则该聚类内部检索逻辑按下列内容填充该含有k个元素的最近邻集合 (1111)：若该聚类中的元素数目大于k，则以该聚类中最接近该投影 样板(1106)的k个元素来填充，若该聚类中的元素数目少于或等于k， 则以该聚类中全部元素来填充。该含有k个元素的最近邻集合(1111) 最好是跟它的对应的失配指数δ2相连结。\n在步骤1109开始时，若该含有k个元素的最近邻集合(1111)不为 空，当一个元素被发现，它的失配指数δ2小于当前与该含有k个元素的 最近邻集合(1111)相连结的诸索引中的最大者，则该聚类内部检索逻辑 更新该含有k个元素的最近邻集合。该更新应包括从该含有k个元素的 最近邻集合(1111)中去除具有最大失配指数δ2的元素，并且用新发现 的元素来置换它。\n若该含有k个元素的最近邻集合(1111)含有少于k个元素，则该 缺失的诸元素被认为是处于无限远处的诸元素。在步骤1110，要确定在该 层次结构中，当前这一层是不是顶层(在实行该第一聚类步骤之前)。若 当前层是顶层，则该过程结束，并且该含有k个元素的最近邻集合 (1111)的内容作为一个结果被返回。若该当前层不是顶层，则在步骤 1114，在该当前层计算一个候选的聚类，那就是，一个含有该k个最近邻 中的某几个的聚类。使用该降维信息(1105)以及该聚类信息(604)来 进行这次检索。在步骤1114，该聚类信息(604)被用来确定该聚类的边 界。若不含该检索样板(1001)的一个聚类的边界跟该含有k个元素的 最近邻集合(1111)的最远的元素相比显得更近时，则该聚类就是一个候 选者。若不存在候选者，则在步骤1113，该当前层被设置为该层次结构的 先前的一层，并且更新该降维信息，同时该过程返回到步骤1110。若存在 一个候选者，则在步骤1115，该样板被投影到该候选的聚类，由此更新该 投影样板(1106)，并且该降维信息也被更新。然后，该过程返回到步骤 1107。\n图12(a)-12(c)对仅根据相似性的聚类技术(例如，根据每一个聚类 的该元素以及对应的诸质心之间的欧几里德距离的最小化，正如Linde， Buzo和Gray等在“一种用于矢量量化设计的算法”(上)一书中所教 导的那样)与使用一种适应于该数据的局部结构的算法的聚类的各种结果 进行比较。图12(a)表示一个参考坐标系(1201)以及一个矢量集合 (1202)。若使用一种基于每一个聚类的诸元素与该对应的质心的该欧几 里德距离的最小化的聚类技术，则图12(b)表示一种可能的结果：该矢量 集合(1202)被诸超平面(1203)和(1204)区分为3个聚类，即， 聚类1(1205)，聚类2(1206)和聚类3(1207)。所得到的诸聚类 含有彼此相似的诸矢量，但没有俘获该数据的结构，并且会导致次最佳的 降维。图12(c)表示使用一种适应于该数据的局部结构的算法进行聚类的 结果。由此得到3个聚类，聚类1(1208)，聚类2(1209)和聚类3 (1210)，它们较好地俘获了该数据的局部结构，并且更适合于进行独立 的降维。\n图13表示适应于该数据的局部结构的聚类算法的一个例子。在步骤 1302，使用待聚类的矢量集合(1301)以及所希望的聚类数目来选择该质 心(1303)的初始值。在一个优选的实施例中，使用任何已知的不带置换 的采样技术，以随机方式为每一个聚类的所希望的数目NC选择该矢量集 合中的一个元素。在步骤1304，例如使用基于该欧几里德距离的任何已知 方法，生成诸聚类的第一个集合。其结果是，诸样本被划分为NC个聚类 (1305)。在步骤1306，NC个聚类中的每一个的质心(1307)被计算， 例如，被计算为该聚类中诸矢量的一个平均值。在步骤1308，使用该单值 分解逻辑(图7，步骤701)可以计算出诸聚类(1305)的诸特征值和诸 特征矢量(1309)。在步骤1310，使用该质心信息(1307)、诸特征矢 量和诸特征值(1309)被用来为每一个聚类生成一个不同的距离度量。对 一个特定的聚类来说，该距离度量的一个例子就是在该旋转空间中由诸特 征矢量所定义的加权欧几里德距离，其权值等于诸特征值的平方根。\n由诸逻辑步骤1312、1313和1314所形成的环路生成新的诸聚类。 在步骤1312，一个控制逻辑对该矢量集合(1301)中的所有矢量迭代执 行步骤1313和1314。在步骤1313，使用该距离度量(1311)来计算被 选定的示例矢量与该聚类的每一个质心之间的距离。在步骤1314，该矢量 被分配到该最近的聚类，由此更新诸聚类(1305)。在步骤1315，若一 个结束条件到达，该过程结束；否则在步骤1306该过程继续进行下去。在 一个优选实施例中，若在两次相继的迭代之间诸聚类的组成没有发生变 化，则该计算过程结束。\n图14表示在一个3维空间中一个复杂表面(1401)的一个例子，以 及基于一个3维象限树的两次连续的近似，正如Samet，H.在“用边界代 码对象限树进行区域表示”一书第163-170页(1980年3月)中所教导 的那样。该第一近似(1402)是一个最小的界限盒子。第二近似(1403) 是生成一个象限树的第二步，在这里，通过在每一维的中点处劈开该界限 盒子，已经将该界限盒子切分为8个超矩形，并且仅保留那些与该表面相 交的诸超矩形。\n在一个优选的实施例中，这种近似的层次结构被生成为一棵k维的象 限树。具有本发明诸特征的用以产生这种近似的层次结构的已知方法的一 个例子包括下列诸步骤：生成该聚类边界，它对应于对该聚类的几何形状 的零阶近似；借助于一个最小界限盒子，对每一个聚类的凸出的外壳作出 近似，由此对每一个聚类的几何形状生成一个1阶近似，通过在每一维的 中点上进行切割，将该界限盒子划分为2k个超矩形；仅保留那些含有诸 点的超矩形，由此生成对该聚类的几何尺寸的一个2阶近似；对每一个被 保留的超矩形重复执行最后两个步骤，以便连续地生成对该聚类的几何形 状的3阶，4阶，…。n阶近似。\n图15表示使用对该聚类的几何形状的连续近似的层次结构，去识别可 能含有离开一个给定的数据点的距离比一个事先说明的距离更近的诸元素 的诸聚类的逻辑流程的一个例子。在一个实施例中，一个聚类的几何形状 就是该聚类的一个凸出的外壳。在另一个实施例中，一个聚类的几何形状 是一个包围所有诸点的连接起来的弹性表面。这个逻辑可以被用来检索候 选的诸聚类，例如在图10中的步骤1008。现在参考图15，在步骤1502， 诸聚类的原始集连同它们的几何近似(1501)的层次结构被输入到该过 程。在步骤1502，该候选集(1505)被初始化为该原始集(1501)。在 步骤1506，通过将对该几何形状的当前近似设置为0阶近似，来执行另一 个初始化步骤。在一个优选实施例中，诸聚类的0阶几何形状近似由用以 生成诸聚类的聚类算法的判决区域给出。在步骤1507，对该聚类的几何形 状的当前近似跟该数据点(1503)之间的距离被计算出来。比该候选集 (1505)离开更远的所有聚类都被抛弃，并且生成诸聚类的一个保留集 (1508)。在步骤1509，要确定在该层次结构中，是否存在较好的近似。 若不存在较好的近似，则通过将该结果集(1512)设置为等于该当前保留 集(1508)以结束该计算。否则，在步骤1510，该候选集(1505)被设 置为该当前保留集(1508)，该当前几何近似被设置为在该层次结构中的 较好近似，并且该过程返回到步骤1507。\n要注意的是，借助于一个优选实施例，连同可供选择的诸实施例，已 经对本发明作了说明，对专业人士来说，各种修改和改进都可能出现。因 此，应当理解，该详细的描述应当被构成一个例子，而不是一种限制。本 发明由所附的权利要求书适当地加以规定。