度量空间最优完全划分索引寻找方法、装置及相关组件

摘要

本发明公开了度量空间最优完全划分索引寻找方法、装置及相关组件，该方法包括：利用选点方法从数据集中选取n个支撑点，构成支撑点空间，然后将数据映射至支撑点空间；将划分方式的权值向量设置为划分支撑点空间超平面的法向量候选集；按照多种选取排列方式在法向量候选集中各选取n个线性无关的法向量，得到对应的多种选取排列结果，并作为对应的划分方式；利用每一种划分方式中的n个线性无关的法向量对支撑点空间进行完全线性划分，得到对应的划分结果；在每一种排列方式对应的划分结果中，根据落入目标区域内的数据个数确定最优的划分方式。本发明实施例可以确定不同划分方式的性能差异，进而获得性能最优的划分方式。

权利要求

1.一种度量空间最优完全划分索引寻找方法，其特征在于，包括：将预先设置的数据集中的数据输入至度量空间中，并利用选点方法从所述数据集中选取n个支撑点，构成支撑点空间，然后将数据映射至所述支撑点空间；

将预先设置的划分方式的权值向量设置为划分支撑点空间超平面的法向量候选集；

按照多种选取排列方式在所述法向量候选集中各选取n个线性无关的法向量，得到对应的多种选取排列结果，并将每一种选取排列结果作为对应的划分方式；

所述权值向量为m个，其中，m大于n；

所述按照多种选取排列方式在所述法向量候选集中各选取n个线性无关的法向量，得到对应的多种选取排列结果，并将每一种选取排列结果作为对应的划分方式，包括：n

在m个权值向量中选取n个线性无关的法向量，得到Am种选取排列结果，并将每一种选取排列结果作为对应的划分方式；

利用每一种划分方式中的n个线性无关的法向量对所述支撑点空间进行完全线性划分，得到每一种排列方式对应的划分结果；

所述利用每一种划分方式中的n个线性无关的法向量对所述数据进行完全线性划分，得到每一种排列方式对应的划分结果，包括：n

分别利用Am种划分方式中的n个线性无关的法向量对所述数据进行完全线性划分，得n到Am个划分结果；

所述利用每一种划分方式中的n个线性无关的法向量对所述支撑点空间进行完全线性划分，得到每一种排列方式对应的划分结果，包括：将n个线性无关的法向量依次标记为v1,v2，…,vn；

利用k个v1法向量的平行超平面对所述支撑点空间划分为k个第一子空间；

对于每一第一子空间，利用k个v2法向量的平行超平面划分得到k个第二子空间；

n

以此类推，直至穷尽n个线性无关的法向量划分得到k个子空间；

在每一种排列方式对应的划分结果中，根据落入目标区域内的数据个数确定对应的划分方式的性能差异，以此确定最优的划分方式。

2.根据权利要求1所述的度量空间最优完全划分索引寻找方法，其特征在于，所述利用选点方法从所述数据集中选取n个支撑点，构成支撑点空间，包括：利用最远优先遍历算法从所述数据集中选取n个支撑点构成支撑点空间。

3.根据权利要求1所述的度量空间最优完全划分索引寻找方法，其特征在于，所述目标区域为每一划分方式对应的划分边界L的r‑邻域。

4.根据权利要求3所述的度量空间最优完全划分索引寻找方法，其特征在于，所述在每一种排列方式对应的划分结果中，根据落入目标区域内的数据个数确定对应的划分方式的性能差异，包括：将落入r‑邻域内数据个数最少的n个线性无关的法向量对应的划分方式判定为最优划分方式。

5.一种度量空间最优完全划分索引寻找装置，其特征在于，包括：数据映射单元，用于将预先设置的数据集中的数据输入至度量空间中，并利用选点方法从所述数据集中选取n个支撑点，构成支撑点空间，然后将数据映射至所述支撑点空间；

候选集设置单元，用于将预先设置的划分方式的权值向量设置为划分支撑点空间超平面的法向量候选集；

法向量选取单元，用于按照多种选取排列方式在所述法向量候选集中各选取n个线性无关的法向量，得到对应的多种选取排列结果，并将每一种选取排列结果作为对应的划分方式；

所述权值向量为m个，其中，m大于n；

所述法向量选取单元包括：

n

选取排列结果获取单元，用于在m个权值向量中选取n个线性无关的法向量，得到Am种选取排列结果，并将每一种选取排列结果作为对应的划分方式；

完全线性划分单元，用于利用每一种划分方式中的n个线性无关的法向量对所述支撑点空间进行完全线性划分，得到每一种排列方式对应的划分结果；

所述完全线性划分单元包括：

n

划分结果获取单元，用于分别利用Am种划分方式中的n个线性无关的法向量对所述数n据进行完全线性划分，得到Am个划分结果；

所述完全线性划分单元包括：

标记单元，用于将n个线性无关的法向量依次标记为v1,v2，…,vn；

第一划分单元，用于利用k个v1法向量的平行超平面对所述支撑点空间划分为k个第一子空间；

第二划分单元，用于对于每一第一子空间，利用k个v2法向量的平行超平面划分得到k个第二子空间；

n

穷尽单元，用于以此类推，直至穷尽n个线性无关的法向量划分得到k个子空间；

性能确定单元，用于在每一种排列方式对应的划分结果中，根据落入目标区域内的数据个数确定对应的划分方式的性能差异，以此确定最优的划分方式。

6.一种计算机设备，其特征在于，包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现如权利要求1至4任一项所述的度量空间最优完全划分索引寻找方法。

7.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如权利要求1至4任一项所述的度量空间最优完全划分索引寻找方法。

说明书

度量空间最优完全划分索引寻找方法、装置及相关组件

技术领域

[0001] 本发明涉及计算机软件技术领域，特别涉及度量空间最优完全划分索引寻找方法、装置及相关组件。

背景技术

[0002] 现有的度量空间树形索引大多是基于距离划分的，利用数据到支撑点的距离关系将数据空间划分成多个较小的区域以求在进行范围查找时可以排除掉部分区域而提高搜索的效率。基于划分的度量空间索引在创建索引时，或基于空间或基于数据分布将数据空间划分成多个子区域。现有的基于划分的度量空间索引，根据划分结果的子空间的逻辑形态，大多可以分为以球形划分为基础和以超平面为基础两部分。

[0003] 基于球形划分的索引方法利用支撑点和半径作为参数将空间划分成多个球子空间，典型的形态有以vp‑tree为代表的对空间进行球形划分和以M‑tree为代表的层次球形划分两种。vp‑tree直接利用数据到支撑点的距离，将数据划分成球内和球外两个部分，而M‑tree利用最小边界球的形式将数据进行平衡划分。

[0004] 基于超平面划分的核心思想是将数据划分到离自己最近的支撑点所代表的区域，划分后的空间在逻辑上显现出Voronoi的形态。基于超平面划分的最基本形式是Jeffrey K.Uhlmann提出来的超平面树gh‑tree和Sergey Brin提出了GNA‑tree。超平面划分的结果具有良好的几何特性，其划分所得的各区域之间不相互重叠。

[0005] 但是当前对经典索引的优化，在划分边界的形态上着手对索引进行优化的方式较少，BM‑index利用数据到支撑点距离的加权信息进行划分，是目前少有的从划分边界的形态上对索引进行优化例子。造成这种局面的原因一方面是不同索引之间的性能比较都是通过各自的实验进行的，而不同的索引方法的索引条件往往是不相同的，性能影响也由多个因素共同决定，支撑点的不同、划分方式的不同、索引的平衡性等等都会对索引的性能造成较大的影响。利用不同的索引直接进行性能比较，没有一套统一的模型可以客观地对不同方法的优劣进行评价，因此无法客观地反映潜藏在实验背后的不同划分方式的内在差异，同时实验采用的数据集的不同和实验环境的差异也大大降低了仅利用实验结果得出的结论的客观性。另一方面，度量空间中不同的划分方式的形态各异难以统一，而大部分数学工具都无法在度量空间中使用，因此对划分方式的探索没有明确的研究方向，从而加大了从划分方式对索引进行优化的难度。

发明内容

[0006] 本发明实施例提供了一种度量空间最优完全划分索引寻找方法、装置及相关组件，旨在对不同的划分方式的性能进行衡量，以确定最优的划分方式。

[0007] 第一方面，本发明实施例提供了一种度量空间最优完全划分索引寻找方法，包括：

[0008] 将预先设置的数据集中的数据输入至度量空间中，并利用选点方法从所述数据集中选取n个支撑点，构成支撑点空间，然后将数据映射至所述支撑点空间；

[0009] 将预先设置的划分方式的权值向量设置为划分支撑点空间超平面的法向量候选集；

[0010] 按照多种选取排列方式在所述法向量候选集中各选取n个线性无关的法向量，得到对应的多种选取排列结果，并将每一种选取排列结果作为对应的划分方式；

[0011] 利用每一种划分方式中的n个线性无关的法向量对所述支撑点空间进行完全线性划分，得到每一种排列方式对应的划分结果；

[0012] 在每一种排列方式对应的划分结果中，根据落入目标区域内的数据个数确定对应的划分方式的性能差异，以此确定最优的划分方式。

[0013] 第二方面，本发明实施例提供了一种度量空间最优完全划分索引寻找装置，包括：

[0014] 数据映射单元，用于将预先设置的数据集中的数据输入至度量空间中，并利用选点方法从所述数据集中选取n个支撑点，构成支撑点空间，然后将数据映射至所述支撑点空间；

[0015] 候选集设置单元，用于将预先设置的划分方式的权值向量设置为划分支撑点空间超平面的法向量候选集；

[0016] 法向量选取单元，用于按照多种选取排列方式在所述法向量候选集中各选取n个线性无关的法向量，得到对应的多种选取排列结果，并将每一种选取排列结果作为对应的划分方式；

[0017] 完全线性划分单元，用于利用每一种划分方式中的n个线性无关的法向量对所述支撑点空间进行完全线性划分，得到每一种排列方式对应的划分结果；

[0018] 性能确定单元，用于在每一种排列方式对应的划分结果中，根据落入目标区域内的数据个数确定对应的划分方式的性能差异，以此确定最优的划分方式。

[0019] 第三方面，本发明实施例提供了一种计算机设备，包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现如第一方面所述的度量空间最优完全划分索引寻找方法。

[0020] 第四方面，本发明实施例提供了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如第一方面所述的度量空间最优完全划分索引寻找方法。

[0021] 本发明实施例提供了一种度量空间最优完全划分索引寻找方法、装置及相关组件，该方法包括：将预先设置的数据集中的数据输入至度量空间中，并利用选点方法从所述数据集中选取n个支撑点，构成支撑点空间，然后将数据映射至所述支撑点空间；将预先设置的划分方式的权值向量设置为划分支撑点空间超平面的法向量候选集；按照多种选取排列方式在所述法向量候选集中各选取n个线性无关的法向量，得到对应的多种选取排列结果，并将每一种选取排列结果作为对应的划分方式；利用每一种划分方式中的n个线性无关的法向量对所述支撑点空间进行完全线性划分，得到每一种排列方式对应的划分结果；在每一种排列方式对应的划分结果中，根据落入目标区域内的数据个数确定对应的划分方式的性能差异，以此确定最优的划分方式。本发明实施例将不同划分方式对应的权值向量作为超平面对支撑点空间进行完全线性划分，从而根据不同的划分结果确定各划分方式的性能差异，进而可以获得性能最优的划分方式。

附图说明

[0022] 为了更清楚地说明本发明实施例技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0023] 图1为本发明实施例提供的一种度量空间最优完全划分索引寻找方法的流程示意图；

[0024] 图2为本发明实施例提供的一种度量空间最优完全划分索引寻找方法的子流程示意图；

[0025] 图3为本发明实施例提供的一种度量空间最优完全划分索引寻找装置的示意性框图；

[0026] 图4为本发明实施例提供的一种度量空间最优完全划分索引寻找装置的子示意性框图；

[0027] 图5为本发明实施例提供的一种度量空间最优完全划分索引寻找方法中的示例示意图。

具体实施方式

[0028] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0029] 应当理解，当在本说明书和所附权利要求书中使用时，术语“包括”和“包含”指示所描述特征、整体、步骤、操作、元素和/或组件的存在，但并不排除一个或多个其它特征、整体、步骤、操作、元素、组件和/或其集合的存在或添加。

[0030] 还应当理解，在此本发明说明书中所使用的术语仅仅是出于描述特定实施例的目的而并不意在限制本发明。如在本发明说明书和所附权利要求书中所使用的那样，除非上下文清楚地指明其它情况，否则单数形式的“一”、“一个”及“该”意在包括复数形式。

[0031] 还应当进一步理解，在本发明说明书和所附权利要求书中使用的术语“和/或”是指相关联列出的项中的一个或多个的任何组合以及所有可能组合，并且包括这些组合。

[0032] 下面请参见图1，图1为本发明实施例提供的一种度量空间最优完全划分索引寻找方法的流程示意图，具体包括：步骤S101～S105。

[0033] S101、将预先设置的数据集中的数据输入至度量空间中，并利用选点方法从所述数据集中选取n个支撑点，构成支撑点空间，然后将数据映射至所述支撑点空间；

[0034] S102、将预先设置的划分方式的权值向量设置为划分支撑点空间超平面的法向量候选集；

[0035] S103、按照多种选取排列方式在所述法向量候选集中各选取n个线性无关的法向量，得到对应的多种选取排列结果，并将每一种选取排列结果作为对应的划分方式；

[0036] S104、利用每一种划分方式中的n个线性无关的法向量对所述支撑点空间进行完全线性划分，得到每一种排列方式对应的划分结果；

[0037] S105、在每一种排列方式对应的划分结果中，根据落入目标区域内的数据个数确定对应的划分方式的性能差异，以此确定最优的划分方式。

[0038] 本实施例中，首先利用数据集构建支撑点空间，并将数据集中的数据映射至支撑点空间，然后根据不同划分方式的权值向量构建一法向量候选集，并从其中选取n个线性无关的法向量对支撑点空间进行完全线性划分，因而可以理解的是，所述法向量候选集中的权值向量的个数一定是大于或者等于n的。由于选取n个线性无关的法向量的方式具有多种，因此可以将每一种选取排列方式作为对应的划分方式，并对支撑点空间进行完全线性划分，从而可以根据落入目标区域内的数据多少对不同的划分方式的性能进行判定，进而可以在多个划分方式中选取性能最优的划分方式。

[0039] 本发明实施例在对多种划分方式进行范围搜索时，不需要对每种划分方式编写一套代码进行索引的建立来进行划分方式优劣的比较，只需要通过将不同划分方式映射到支撑点空间的线性表达作为参数传入即可进行比较。通过结合多种划分方式对索引性能进行判断，为找到更优的划分提供了可能。而索引性能可以看成是划分方式的划分性能，也就是k能否通过该索引进行最大化的划分。比如通过完全线性划分，将数据分成n份，如果可以排k k
除掉n–1份，便可以只保留最后一份，如此便可以无需对n–1份的数据进行搜索。另外，本实施例不需要明确地知道划分方式的划分边界在度量空间中的具体形态，只需要知道该不知名形态在支撑点空间中的线性表达即可进行性能比较，极大地提高了比较的时间成本和效率。

[0040] 本实施例通过对不同的划分方式进行分析，在最大程度上保留不同划分方式的性能特性的基础上，采用统一的划分模型‑‑‑完全线性划分对不同的划分方式进行统一。利用统一后的模型(即本实施例提供的度量空间最优完全划分索引寻找方法)对不同划分方式之间的性能差异进行判定，利用相同的支撑点、相同的划分子区域数目，可以减少划分以外的因素对索引性能的影响，提高比较的公平性、结论的可靠性。并且应用完全线性划分实现基于球形的划分和超平面的划分，将球形划分和超平面划分进行了统一，将多种划分边界映射到支撑点空间中，以线性表达的形式表现在支撑点空间中，将划分边界不同的问题转换为线性表达式不同的问题，不再局限于某一种划分方式，而是通过查找出排除率最高的线性表达式，提高划分性能。其次，本实施例利用统一模型(即本实施例提供的度量空间最优完全划分索引寻找方法)，通过对划分边界在支撑点空间的线性表达，为找出更优良的划分方式提供了可能。

[0041] 可以理解的是，在实际操作中，当将数据映射到支撑点空间时，也会把划分边界映射到支撑点空间中，且划分边界在支撑点空间中是以线性方程的形式表达出来的。例如：GH划分，假设选取两个支撑点p1、p2，GH划分的实质是将数据划分到离自己更近的支撑点，则有划分边界d(s,p1)＝d(s,p2)，s为任一数据点。如果将数据映射到以p1、p2为支撑点的支撑点空间，则x轴代表d(s,p1),y轴代表d(s,p2)，划分边界在该支撑点空间中的表达形式为x＝y。

[0042] 度量空间是一种覆盖范围很广的数据类型的抽象，度量空间可以定义为一个二元组(S，d)，其中S是有限非空的数据集合，而d是定义在S上的具有如下性质的距离函数:

[0043] (1)非负性：对于任意x,y S,d(x,y)≥0，并且d(x,y)＝0x＝y。

[0044] (2)对称性：对于任意x,yS,d(x,y)＝d(y,x)。

[0045] (3)三角不等性：对于任意x、y,、zS,d(x,y)+d(y,z)≥d(x,z)。

[0046] 度量空间(M,d)，S＝{si|si∈M,i＝1,2,...,m}，S中选择的n个支撑点P＝{p1,p2,...,pn}，对于 以其到支撑点的距离d(s,pi)作为坐标，可以定义一个从M到n维空间的映射，并用sp表示s在n维空间中的像，则有：

[0047] FP,d:M‑>Rn:sP≡FP,d(s)＝(f1(s),f2(s),...,fn(s))＝(d(s,p1),d(s,p2),...,d(s,pn))∈FP,d(M)。

[0048] 那么，支撑点空间FP,d(S)就是S在Rn的像：

[0049] FP,d(s)＝{sP|sP＝d(s,p1),d(s,p2),...,d(s,pn)),s∈S}。

[0050] 假设度量空间中三个数据点s1、s2、s3，其中d(s2,s1)＝12，d(s2,s3)＝23，d(s1,s3)＝13，当选用s1、s3两个数据点作为支撑点时，得到的支撑点空间维度即为2，同时，s1、s2、s3在支撑点空间中的像分别为s1P＝(d(s1,s1),d(s1,s3))＝(0,13)、s2P＝(d(s2,s1),d(s2,s3))＝(12,23)、s3P＝(d(s3,s1),d(s3,s3))＝(13,0)。

[0051] 另外，本实施例所述的数据集可以是随机均匀向量、DNA、蛋白质、二维地图边界数据等等，所述数据集的数据维度可以是1～5维，且数据格式统一。

[0052] 在一实施例中，所述步骤S101包括：

[0053] 利用最远优先遍历算法从所述数据集中选取n个支撑点构成支撑点空间。

[0054] 本实施例中，所述选点算法采用最远优先遍历算法，所述最远优先遍历算法(Farthest FirstTraversal，FFT)可以选出数据拐角的点，具有线性的空间复杂度和时间复杂度。当然，在其他实施例中，还可以采用其他的选点算法，例如k‑means选点算法(多种k值确定以及如何选取初始点方法)。

[0055] 在一实施例中，所述权值向量为m个，其中，m大于n；

[0056] 所述步骤S103包括：

[0057] 在m个权值向量中选取n个线性无关的法向量，得到 种选取排列结果，并将每一种选取排列结果作为对应的划分方式。

[0058] 本实施例中，所述法向量候选集中包括m个权值向量，从中选取n个线性无关的法向量，那么共有 选取排列结果，继而可以将每一种选取排列结果作为一种划分方式，用于对支撑点空间进行划分。

[0059] 需要说明的是，本实施例中的m个向量可以线性有关，也可以线性无关，但是需要确保选取的n个法向量线性无关，因为只有当选取n个线性无关的法向量，才可以保证n维向量空间的每个方向的信息都会被考虑到。

[0060] 另外，如果法向量候选集中包含n个权值向量，那么则会是针对某一种划分方式所扩展出来的n个线性无关的法向量。而本实施例选用m个权值向量，也就相当于对多种划分方式进行组合，从不同的划分方式中选取不同数量的法向量，共n个，如此便可以在当前的多种划分方式中找到最优的划分向量组合，即最优划分方式。同时，m的大小可以根据实际情况确定，即在实际应用过程中，需要组合哪些划分方式来寻找最优划分方式，便可以输入这些划分方式的权值向量。

[0061] 在一实施例中，所述步骤S104包括：

[0062] 分别利用 种划分方式中的n个线性无关的法向量对所述支撑点空间进行完全线性划分，得到 个划分结果。

[0063] 本实施例中，利用 种划分方式，便可以得到 个划分结果。例如利用 种划分方式对支撑点空间进行完全线性划分，便可以得到 个划分结果，即12个划分结果。

[0064] 在一实施例中，如图2所示，所述步骤S104还包括：步骤S201～S204。

[0065] S201、将n个线性无关的法向量依次标记为v1,v2，…,vn；

[0066] S202、利用k个v1法向量的平行超平面对所述支撑点空间划分为k个第一子空间；

[0067] S203、对于每一第一子空间，利用k个v2法向量的平行超平面划分得到k个第二子空间；

[0068] S204、以此类推，直至穷尽n个线性无关的法向量划分得到kn个子空间。

[0069] 本实施例中，利用n个线性无关的法向量进行(n，k)完全线性划分。具体来说，对于n个支撑点的支撑点空间，选定n个线性无关的有序向量作为划分超平面的法向量，并依次标记v1,…,vn。然后利用k个以v1为法向量的平行超平面将支撑点空间划分为k个第一子空间，再对每个第一子空间利用k个以v2为法向量的平行超平面(作用于不同子空间的平行超n平面可能不同)进一步划分为k个第二子空间，如此类推，直至穷尽n个法向量产生k个子空间。

[0070] 举例来说，如图5所示，该区域被三个超平面划分，每个平面将空间分成两部分，共分成八个子空间。

[0071] 另外，对于球面划分来说，在将球面映射到支撑点空间后，其线性表达也是以超平面形式出现的，如VP(即VP‑Tree，近邻搜索之制高点树)的划分边界映射到支撑点空间中的表达形式为x＝r。

[0072] 在一实施例中，所述目标区域为每一划分方式对应的划分边界L的r‑邻域。

[0073] 本实施例中，划分边界L的r‑邻域是指划分边界L“附近”的一个区域，当范围搜索R(q,r)的中心q落入该区域时，进行范围搜索时划分边界两边的区域都无法被排除，记作Nr(L)。

[0074] 从r‑邻域的定义可知，在进行范围查找时，q落入某个划分边界的r‑邻域的机率越大，该划分边界有效地排除掉另一半数据的概率越低，该划分边界的剪枝能力越差。也即，r‑邻域大小和划分边界的剪枝能力成负相关关系。

[0075] 在一实施例中，所述步骤S105包括：

[0076] 将落入r‑邻域内数据个数最少的n个线性无关的法向量对应的划分方式判定为最优划分方式。

[0077] 本实施例中，利用划分之后数据落入r‑邻域内的数据的多少判断各索引的剪枝能力，从而确定各划分方式性能的优劣。因此，在n个线性无关的法向量进行完全线性划分后落入r‑邻域内的数据最少时，对应的划分方式即为最优划分方式。

[0078] 图3为本发明实施例提供的一种度量空间最优完全划分索引寻找装置300的示意性框图，该装置300包括：

[0079] 数据映射单元301，用于将预先设置的数据集中的数据输入至度量空间中，并利用选点方法从所述数据集中选取n个支撑点，构成支撑点空间，然后将数据映射至所述支撑点空间；

[0080] 候选集设置单元302，用于将预先设置的划分方式的权值向量设置为划分支撑点空间超平面的法向量候选集；

[0081] 法向量选取单元303，用于按照多种选取排列方式在所述法向量候选集中各选取n个线性无关的法向量，得到对应的多种选取排列结果，并将每一种选取排列结果作为对应的划分方式；

[0082] 完全线性划分单元304，用于利用每一种划分方式中的n个线性无关的法向量对所述支撑点空间进行完全线性划分，得到每一种排列方式对应的划分结果；

[0083] 性能确定单元305，用于在每一种排列方式对应的划分结果中，根据落入目标区域内的数据个数确定对应的划分方式的性能差异，以此确定最优的划分方式。

[0084] 在一实施例中，所述数据映射单元301包括：

[0085] 最远优先遍历单元，用于利用最远优先遍历算法从所述数据集中选取n个支撑点构成支撑点空间。

[0086] 在一实施例中，所述权值向量为m个，其中，m大于n；

[0087] 所述法向量选取单元303包括：

[0088] 选取排列结果获取单元，用于在m个权值向量中选取n个线性无关的法向量，得到种选取排列结果，并将每一种选取排列结果作为对应的划分方式。

[0089] 在一实施例中，完全线性划分单元304包括：

[0090] 划分结果获取单元，用于分别利用 种划分方式中的n个线性无关的法向量对所述数据进行完全线性划分，得到 个划分结果。

[0091] 在一实施例中，如图4所示，完全线性划分单元304还包括：

[0092] 标记单元401，用于将n个线性无关的法向量依次标记为v1,v2，…,vn；

[0093] 第一划分单元402，用于利用k个v1法向量的平行超平面对所述支撑点空间划分为k个第一子空间；

[0094] 第二划分单元403，用于对于每一第一子空间，利用k个v2法向量的平行超平面划分得到k个第二子空间；

[0095] 穷尽单元404，用于以此类推，直至穷尽n个线性无关的法向量划分得到kn个子空间。

[0096] 在一实施例中，所述目标区域为每一划分方式对应的划分边界L的r‑邻域。

[0097] 在一实施例中，所述性能确定单元305包括：

[0098] 判定单元，用于将落入r‑邻域内数据个数最少的n个线性无关的法向量对应的划分方式判定为最优划分方式。

[0099] 由于装置部分的实施例与方法部分的实施例相互对应，因此装置部分的实施例请参见方法部分的实施例的描述，这里暂不赘述。

[0100] 本发明实施例还提供了一种计算机可读存储介质，其上存有计算机程序，该计算机程序被执行时可以实现上述实施例所提供的步骤。该存储介质可以包括：U盘、移动硬盘、只读存储器(Read‑Only Memory，ROM)、随机存取存储器(Random Access Memory，RAM)、磁碟或者光盘等各种可以存储程序代码的介质。

[0101] 本发明实施例还提供了一种计算机设备，可以包括存储器和处理器，存储器中存有计算机程序，处理器调用存储器中的计算机程序时，可以实现上述实施例所提供的步骤。当然计算机设备还可以包括各种网络接口，电源等组件。

[0102] 说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的系统而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。应当指出，对于本技术领域的普通技术人员来说，在不脱离本申请原理的前提下，还可以对本申请进行若干改进和修饰，这些改进和修饰也落入本申请权利要求的保护范围内。

[0103] 还需要说明的是，在本说明书中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的状况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。