一种基于距离度量的设备故障案例高维索引结构技术

摘要

本发明公开了一种基于距离度量的设备故障案例高维索引结构技术。在本发明中，提出了一种新的高维数据索引结构，它根据设备状态案例的聚集特性将空间动态划分成网格结构，使得空间上相邻的案例被放置在一起，同时，利用待查询矢量与两个参考点的距离与查询阈值之间的关系，大范围排除不可能的数据，大大提高了查询的效率，减少了CPU代价，同时本发明提出的索引结构具有对数据分布不敏感的特点，为设备故障诊断的工程智能化奠定了基础。

说明书

技术领域

本发明属于机械设备信息的数据挖掘和聚类分析等领域，涉及设备故障案例的相似案例检索技术，具体涉及一种基于距离度量的设备故障案例高维索引结构。

背景技术

随着设备监测与诊断技术在企业的广泛应用，特别是远程监测与诊断技术在大型装备制造企业的应用，设备故障案例得以充分积累。在这种背景下，如何充分利用这些案例，以指导未知故障的判断，引起了人们的极大兴趣。从本质上来说，设备故障案例可以看成由多种特征形成的一个高维数据，设备故障案例集形成一个高维数据库，因此，设备故障案例的利用问题可以转换为对案例库的相似查询问题，即k近邻查询，进而设备故障案例的索引结构就成为一个关键问题。

在提出的众多的索引结构和查询算法中，例如：BK-Tree，FQ-Tree，R-Tree等，它们各有优缺点。集中反映在以下二个方面：1)随着维数的增加，查询效率下降。例如目前的主流多维索引结构在处理维数较低的情况时具有比较好的效率，但是一旦维数较高时就会显得力不从心，即使采用降维技术也不一定能取得理想的结果。这是因为采用此种技术可能会导致有效信息的丢失，尤其不适合处理特种空间中的特征向量相关性很小的情况。2)高额计算代价。高维度量空间的距离计算次数随着数据的增加明显增加。

设备故障案例其特征维数可以高达上百维，同时，设备故障案例有其自身的特点，即相同故障案例在高维空间表现中一定的聚集特性，因此迫切需要适应于设备故障案例的高维数据索引结构，以满足设备故障案例综合利用的需求。

发明内容

本发明的目的在于克服上述现有技术不足，提供一种基于距离度量的设备故障案例高维索引结构技术，适应于对设备故障案例进行k近邻查询的索引结构，该索引结构根据设备故障案例的聚集特性，通过建立有效的规则以减少距离计算次数，在此基础上再对设备故障案例采用范围查询方法进行查询，可以大大提高查询效率。本发明的基本操作步骤如下：

(1)按一定的规则对轴进行组织，并按一定的规则在该轴上选定两个参考点，将待插入的矢量插入到一个特定位置，记录该矢量到两个参考点的距离，其目的是使得在高维空间中的矢量之间的距离可以根据矢量与两个参考点之间的距离进行估算；

(2)检索时先计算待查询矢量与参考点之间的距离，由于参考点位于轴上，因此矢量与多个参考点的距离计算时间仅与维数有关；

(3)根据待查询矢量与参考点之间的距离计算结果，得出查询结果可能的超始位置和结束位置，扫描这些位置上存放的矢量数据，就可以得到相应的查询结果。因为不再扫描整个数据文件，所以大大减少磁盘访问代价，提高了查询速度。

具体步骤如下：

(1)对特征轴按数据在轴上概率分布密度的大小进行排序，优先选择数据概率分布密度大，且划分次数没有达到参数ε规定的特征轴对数据进行划分；

(2)将根节点设置为当前节点；

(3)如果根节点为空，按步骤(1)选定一根轴，并以内部节点形式记录该轴；

(4)如果当前节点为内部节点，循环遍历该内部节点的划分结构集合，找出包含待插入的数据点的一个划分结构，即R_L＜x_i≤R_R，其中i为内部节点对应的轴，x_i为构造索引结构时待插入的数据点在第i轴上的投影轴；

(5)如果R_L＜x_i≤(R_L+R_R)/2，则将当前节点置为该划分结构的左边区域指针PLR，否则，将当前节点置为该划分结构的右边区域指针PRR；

(6)如果当前节点为叶子节点，且叶子节点中包含的数据点个数大于等于m，并且还有轴可供划分，则调用分裂算法，并将当前节点置为将添加的内部节点，跳转到2；

(7)计算数据点对应叶子节点对应划分结构的左，右参考点的距离，并将数据点插入叶子节点，返回。

所述的分裂算法为：

(1)设置当前划分结构为指向叶子节点的划分结构；

(2)如果当前划分结构中(R_R-R_L)≤1/ε，跳转到(3)，将当前划分结构划分为二个：{R_L，(R_L+R_R)/2，PLR1，PLR2}、{(R_L+R_R)/2，R_R，PRR1，PRR2}，其中PLR1子树中的叶子节点中的数据点在当前划分结构所在轴的投影满足R_L＜x_i≤(R_L+R_R)/4，PLR2子树中的叶子节点中的数据点在当前划分结构所在轴的投影满足(R_L+R_R)/4＜x_i≤(R_L+R_R)/2；PRR1子树中的叶子节点中的数据点在当前划分结构所在轴的投影满足(R_L+R_R)/2＜x_i≤3(R_L+R_R)/4，PRR2子树中的叶子节点中的数据点在当前划分结构所在轴的投影满足3(R_L+R_R)/3＜x_i≤(R_L+R_R)，返回；

(3)按数据在轴上的分布密度大小排序，选择分布密度小于指向该叶子节点的划分结构所对应轴后的第一个轴；

(4)对应选择的轴，生成一个内部节点，并将指向该叶子节点的划分结构指向生成的内部节点；

(5)设置当前节点为(4)生成的内部节点，重新插入叶子节点中的数据点。

利用待查询矢量与位于轴上的参考点的距离对查询结果空间范围进行排除。

建立索引结构时的划分次数ε取[15，25]。

建立索引结构时的阈值m取[80，120]。

本发明提出的基于范围剪枝的案例高维索引结构，将估算距离用的参考点固定在轴上，减少了与参考点距离计算的次数，同时，具有对数据分布的不敏感特性，具有很高的查询效率。

附图说明

图1为数据结构存储示意图。

图2为分裂算法中通过添加轴来存储数据点的示意图。

图3为分裂算法中通过分裂中间节点来存储数据点的示意图。

图4为本发明提出的索引结构与顺序结构的平均查询时间对比图。

图5为本发明提出的索引结构与R-Tree结构的平均查询时间对比图。

图6为本发明提出的索引结构距离计算次数与实际检点数的比例。

下面结合附图对本发明的内容作进一步详细说明。

具体实施方式

参见图1所示，其中内部节点记录对某一特征轴进行划分的信息，内部节点由多个划分结构组成；划分结构记录了对特征轴进行划分的具体信息，包括一对参考点，参考点所指向的左，右参考区域，例如图中(R1，R2)，(R2，R3)，(R3，R4)就分别代表轴上的一对参考点。轴上的一对参考点，如(R3，R4)将整个数据空间划分为两个部分，其划分的左边区域中的数据点到R3的距离小于等于到R4的距离，而右边区域中的数据点到R3的距离大于到R4的距离；叶点节点记录了相应数据点在顺序存储中的索引号，以及到左，右参考点的距离。

参见图2所示，分裂算法中通过添加轴来存储数据点的执行条件为：叶子节点的存储的数据点个数等于参数规定的阈值m时，并且此时第i轴的被划分次数等于划分次数参数ε。

参见图3所示，分裂算法中通过分裂中间节点来存储数据点的执行条件为：叶子节点的存储的数据点个数等于参数规定的阈值m时，并且此时第i轴的被划分次数小于划分次数参数ε。

参照图4、图5所示，本发明提出的设备故障案例索引结构与顺序扫描、R-Tree树索引结构进行了性能对比实验，实验选取包含60万个均匀分布的20维向量。其中本发明索引结构的参数为：划分次数ε为10，阈值m为100。实验首先测试了索引结构随着数据点数的增加时索引时间的变化，随机地选取100个查询数据点，计算范围查询阈值为0.1时所消费的平均查询时间。

参照图6所示，从图4中可以看出，本发明提出的索引结构其平均查询时间稍高于顺序索引结构，但从图6来看，考虑到磁盘读写的影响时，顺序索引结构需要将所有数据点读入内存，而本发明提出的结构只需要将所需要的数据点数读入，能够大大缩短磁盘I/O读写所需的时间。

为进一步说明本发明提出的索引结构，设集合Θ在M维空间第i轴上的取值范围为[Min(z_i)，Max(z_i)]，则点D₀(D₀＝{z_j}，j＝1，...，M，当j≠i时，z_j＝0，当j＝i时z_j＝z_iMin)，D₁(D₁＝{z_j}，j＝1，...，M，当j≠i时，z_j＝0，当j＝i时z_j＝z_iMax)，将集合划分为二个部分：X₀，X₁，使得集合X₀中任一点到D₀的距离小于等于到D₁的距离，集合X₁中任一点到D₀的距离大于到D₁的距离，记X₀中点X到D₀，D₁的距离分别为λ₀，λ₁，点Q到D₀，D₁的距离分别为λ₂，λ₃，则X与Q的距离λ满足条件λ≥|λ₂-λ₃|/2，据此，在本发明中，采用划分结构来标明对轴(特征量)的某一次划分，其形如：{R_L，R_R，PLR，PRR}，其中R_L代表该次划分的左边参考点，R_R代表该次划分的右边参考点，PLR(左边区域指针，Pointer of LeftRegion)指定由左、右参考点所划定的左边区域(左边区域由内部节点或者叶子节点构成)的指针(该区域中的矢量数据到左参考点的距离小于到参考点的距离)，PRR(右边区域指针，Pointer of Right Region)代表由左、右参考点所划定的右边区域(右边区域由内部节点或者叶子节点构成)的指针(该区域中的矢量数据到左参考点的距离大于等于到右参考点的距离)；采用内部节点标识对某一维轴进行划分的划分结构的集合及轴的编号，其形如(i，(R_L1，R_R1，PLR₁，PRR₁)，(R_L2，R_R2，PLR₂，PRR₂)，...，(R_LL，R_RL，PLR_L，PRR_L))，其中：i表示内部节点对应的轴，下标L(L≤ε，ε表示对轴最多允许的划分次数)表示对轴进行划分的次数，且有R_Rj＝R_L(j+1)，R_L1＝0，R_RL＝1，即在划分结构集合中各划分结构所覆盖的轴的范围不重复，并且将各划分结构联接起来，形成对数据集在轴上的投影范围；采用叶子节点标识包含矢量数据索引集合及矢量到父节点中包含的左，右参考点的距离。

构造本发明提出索引结构的具体步骤如下：

(1)对特征轴按数据在轴上概率分布密度的大小进行排序，优先选择数据概率分布密度大，且划分次数没有达到参数ε规定的特征轴对数据进行划分；

(2)对应于待插入的数据点，将根节点设置为当前节点；

(3)如果根节点为空，按(1)选定一根轴，并以内部节点形式记录该轴；

(4)如果当前节点为内部节点，循环遍历该内部节点的划分结构集合，找出包含该待插入的数据点的一个划分结构，即R_L＜x_i≤R_R，其中i为内部节点对应的轴，x_i为构造索引结构时待插入的数据点在第i轴上的投影轴；

(5)如果R_L＜x_i≤(R_L+R_R)/2，则将当前节点置为该划分结构的左边区域指针PLR，否则，将当前节点置为该划分结构的右边区域指针PRR；

(6)如果当前节点为叶子节点，且叶子节点中包含的数据点个数大于等于m，并且还有轴可供划分，则调用分裂算法，并将当前节点置为将添加的内部节点，跳转到2；

(7)计算数据点对应叶子节点对应划分结构的左，右参考点的距离，并将数据点插入叶子节点，返回。

具体的分裂算法为：

(1)设置当前划分结构为指向叶子节点的划分结构；

(2)如果当前划分结构中(R_R-R_L)≤1/ε，跳转到(3)，将当前划分结构划分为二个：{R_L，(R_L+R_R)/2，PLR1，PLR2}、{(R_L+R_R)/2，R_R，PRR1，PRR2}，其中PLR1子树中的叶子节点中的数据点在当前划分结构所在轴的投影满足R_L＜x_i≤(R_L+R_R)/4，PLR2子树中的叶子节点中的数据点在当前划分结构所在轴的投影满足(R_L+R_R)/4＜x_i≤(R_L+R_R)/2；PRR1子树中的叶子节点中的数据点在当前划分结构所在轴的投影满足(R_L+R_R)/2＜x_i≤3(R_L+R_R)/4，PRR2子树中的叶子节点中的数据点在当前划分结构所在轴的投影满足3(R_L+R_R)/3＜x_i≤(R_L+R_R)，返回；

(3)按数据在轴上的分布密度大小排序，选择分布密度小于指向该叶子节点的划分结构所对应轴后的第一个轴；

(4)对应选择的轴，生成一个内部节点，并将指向该叶子节点的划分结构指向生成的内部节点；

(5)设置当前节点为(4)生成的内部节点，重新插入叶子节点中的数据点。

利用待查询矢量与位于轴上的参考点的距离对查询结果空间范围进行排除。

实施例：

对应查询点Q＝{x₁，...，x_N}，范围查询阈值为T，其具体的范围查询算法如下：

(1)将根节点设置为当前节点；

(2)如果当前节点为内部节点，找出内部节点中满足R_Lj＜x_i≤R_Rj的划分结构，并将其设置当前划分结构

(3)以当前划分结构为中心，在内部节点的划分结构集合中向前和向后搜索，在向前搜索中，如果如满足公式T＜|λ₂-λ₃|/2(其中λ₂，λ₃为Q到左，右参考点的距离)，则停止向前搜索，在向后搜索中，如果满足公式T＜|λ₂-λ₃|/2，则停止向后搜索，同时，在搜索过程中执行(4)和(5)。

(4)如果查询点到左参考点的距离小于到右参考点的距离，将当前节点置为该划分结构的左边区域指针PLR，重复第(2)；

(5)如果查询点到左参考点的距离大于等于到右参考点的距离，，将当前节点置为该划分结构的右边区域指针PRR，重复第(2)；

(6)如果当前节点为叶子节点，如果叶子节点中的数据点到左，右参考点的距离与查询数据点到左，右参考点的距离都满足公式T≥|λ₂-λ₃|/2，则计算距离，如果距离小于阈值T，加入结果集合，否则，跳过该数据点。

本发明中，有关参数的确定准则如下：

1)划分次数ε：对于相同的划分次数，不同的数据分布类型对查询时间的影响不大。同时，随着划分次数的增多，查询时间将会有下降的趋势，当划分次数达到一定程度时，再增加划分次数反而会造成查询时间的少量增加。这说明在数据点数一定时，增加划分次数可以更好的实现范围剪枝，减少距离计算的次数，当划分次数增加到某一数值时，相对于一定的数据点数，空间中的网格已经足够小，再增加划分次数并不会减少距离计算次数，反而增加了在内部节点上检索的时间，造成整体查询时间上的增加。

2)阈值m：对于相同的数据点个数和维数，相同阈值条件下，不同的数据分布类型对查询时间的影响不大。同时，随着阈值m的增大，查询时间有下降趋势。这说明在数据点数一定时，同时划分次数一定时，增加阈值m可以更好地实现单点减枝，减少在内部节点上的检索时间。但阈值m越大，在数据点数一定时，索引结构划分的网格也将变大，因而应用范围剪枝的效果不明显，需要更多的距离计算。

总之，本发明提出了基于范围剪枝的案例高维索引结构，并通过实验分析证明该索引结构具有对数据分布的不敏感特性。同时，实验结果表明本发明的索引结构比顺序扫描、R-Tree树索引结构具有更好的检索性能，具有很高的查询效率。