集成分类器及该装置的分类方法

摘要

本发明涉及集成分类器及该装置的分类方法。本发明为了解决现有空间栅格数据监督分类领域中存在速度慢、精度低、属性子集具有偏置特性以及属性子集为非确定多项式的问题。本发明采用属性划分方式，将训练数据子集与并行计算技术结合起来，且能应用于高纬度栅格数据；并采用模糊粗糙集理论作为高纬度属性并行划分的标准，使得每个子集即有自己独立特性，又保持了决策完整性，适应于离散型、连续型的异构数据。本发明应用于遥感与地理信息系统领域。

说明书

技术领域

本发明涉及遥感与地理信息系统领域。

背景技术

在现有空间栅格数据监督分类领域中，主要应用的技术包括神经网、支持向量机、决策树、贝叶斯、KNN等算法。这些算法采用的主要手段就是输入训练数据算法进行学习产生“分类模型”，通过“分类模型”可以进一步预测位置数据的类别信息。对于高维度数据，通常采用“属性选取”算法，降低维度提高速度。

当前所采用的另外一项重要技术就是“集成分类器”，集成分类器通过异构的多个分类器组合进行投票，期望获得比单一分类器更高的分类精度。

.在处理空间栅格数据过程中，经常需要面对海量的、超高维度的数据，如某些空间数据包含2000个以上的空间属性，数据量在几个TB以上，要快速有效的处理这些数据将会面临一些困难：

（1）速度问题：数据量过大时，尤其是维度加大的时候，算法训练分类模型的开销也将加大，当前流行的基于C++的SVM算法程序（如：LIBSVM）可能数个小时也不能获得训练结果，或者直到内存空间耗尽也无法存储分析结果。

（2）属性子集问题：为了提高速度，很多算法均采用“属性选取”。一方面，从一个很大的属性集选取合适的属性子集是一个非确定多项式问题，组合数目过多难以穷举；近似最优的子属性通常具有“偏置”特性，某些类目的预测精度会有一定损失。

（3）精度问题：为了解决精度问题，很多算法采用“集成分类器”技术，就是将训练数据划分为多个子集，然后在进行训练，投票。对于高维度数据栅格，一方面，由于数据量较大，所以难以保证子分类器之间的差异，而多个子分类器过于近似将达不到“集成”和“投票”的目的；另一方面，大量的属性对应部分的训练数据子集，将导致“过度拟合”现象；这两种问题均导致分类精度降低。

综上所述在现有空间栅格数据监督分类领域中存在速度慢、精度低、属性子集具有偏置特性以及属性子集为非确定多项式的问题。

发明内容

本发明为了解决现有空间栅格数据监督分类领域中存在速度慢、精度低、属性子集具有偏置特性以及属性子集为非确定多项式的问题，从而提出了集成分类器及该装置的分类方法。

集成分类器的分类方法,它包括下述步骤：

步骤一、采用多进程和多线程组合的方式读取待处理的栅格数据，具体过程包括如下步骤：

A、输入集成分类器的子分类器个数n；

n为子分类器的个数，n大于等于2，通过期望算法将栅格数据的所有空间属性按照决策能力分为n份，每个分类器均具备全集全部的分类能力，

B、启动n+1个进程；

其中，n+1个进程为Rank 0、Rank 1…Rankn；Rank0为管理进程，Rank 1…Rankn均为运算进程，运算进程Rank 1…Rankn分别与n个子分类器一一对应，

C、在当前进程为管理进程Rank 0时，构造空的粗糙关系表，将待处理的栅格数据均匀划分给每个运算进程；启动n个线程，每个线程单独对应一个运算进程；

其中，线程包括第1线程、第2线程…第n线程，

D、在当前进程为运算进程时，每个进程均同时读取待处理的栅格数据；

步骤二、管理进程Rank0维护属性离散化区间表，并将该属性离散化区间表均匀划分给多个线程，所述多个线程同时启动对相应的空间连续属性的栅格数据进行离散化；

步骤三、管理进程Rank0将空间属性均匀分给n个运算进程处理，并收集n个运算进程的处理结果、构建完整的粗糙关系表，将该粗糙关系表发给每个运算进程，每个运算进程根据粗糙关系表建立一个属性子集；

步骤四、管理进程Rank0将每个运算进程根据所对应的属性子集进行并行训练子分类器产生模型，该子分类器为与所述的进程一一对应的子分类器，每个子分类器进行预测该子分类器对应的属性子集的类型，统计所有子分类器预测结果，以投票选举的方式选取投票最多的预测结果。

集成分类器，它包括下述装置：

用于多进程和多线程组合的方式读取待处理的栅格数据的装置，该装置包括如下模块：

用于输入集成分类器的子分类器个数n的模块；

其中，n为子分类器的个数，n大于等于2，通过期望算法将栅格数据的所有空间属性按照决策能力分为n份，每个分类器均具备全集全部的分类能力，

用于启动n+1个进程的模块；

其中，n+1个进程为Rank 0、Rank 1…Rankn；Rank0为管理进程，Rank 1…Rankn均为运算进程，运算进程Rank 1…Rankn分别与n个子分类器一一对应，

用于在当前进程为管理进程Rank 0时，构造空的粗糙关系表，将待处理的栅格数据均匀划分给每个运算进程；启动n个线程，每个线程单独对应一个运算进程的模块；

其中，线程包括第1线程、第2线程…第n线程，

用于在当前进程为运算进程时，每个进程均同时读取待处理的栅格数据的模块；

用于管理进程Rank0维护属性离散化区间表，并将该属性离散化区间表均匀划分给多个线程，所述多个线程同时启动对相应的空间连续属性的栅格数据进行离散化的装置；

用于管理进程Rank0将空间属性均匀分给n个运算进程处理，并收集n个运算进程的处理结果、构建完整的粗糙关系表，将该粗糙关系表发给每个运算进程，每个运算进程根据粗糙关系表建立一个属性子集的装置；

用于管理进程Rank0将每个运算进程根据所对应的属性子集进行并行训练子分类器产生模型，该子分类器为与所述的进程一一对应的子分类器，每个子分类器进行预测该子分类器对应的属性子集的类型，统计所有子分类器预测结果，以投票选举的方式选取投票最多的预测结果的装置。

本发明具有以下优势：

（1）采用属性划分方式，而不是样本划分方式构造训练数据子集。

（2）将训练数据子集与并行计算技术结合起来，应用于高纬度栅格数据。

（3）应用模糊粗集理论作为高纬度属性并行划分的标准，使得每个子集即有自己独立特性，又保持了决策完整性。

（4）适应于离散型、连续型的异构数据。

附图说明

图1为集成分类器的分类方法的流程图；

图2为采用多进程和多线程组合的方式读取待处理的栅格数据具体步骤的流程图；

图3为每个线程启动对相应的空间连续属性的栅格数据进行离散化的具体步骤流程图；

图4为离散化过程中各线程之间的关系图，图中2≤l≤n，；

图5为粗糙关系表的构造和属性使用表的关系图；

图6为训练产生模型阶段的流程图。

具体实施方式

具体实施方式一、结合图1和图2具体说明本实施方式，本实施方式所述的集成分类器的分类方法，它包括下述步骤：

步骤一、采用多进程和多线程组合的方式读取待处理的栅格数据，具体过程包括如下步骤：

A、输入集成分类器的子分类器个数n；

n为子分类器的个数，n大于等于2，通过期望算法将栅格数据的所有空间属性按照决策能力分为n份，每个分类器均具备全集全部的分类能力，

B、启动n+1个进程；

其中，n+1个进程为Rank 0、Rank 1…Rankn；Rank0为管理进程，Rank 1…Rankn均为运算进程，运算进程Rank 1…Rankn分别与n个子分类器一一对应，

C、在当前进程为管理进程Rank 0时，构造空的粗糙关系表，将待处理的栅格数据均匀划分给每个运算进程；启动n个线程，每个线程单独对应一个运算进程；

其中，线程包括第1线程、第2线程…第n线程，

D、在当前进程为运算进程时，每个进程均同时读取待处理的栅格数据；

步骤二、管理进程Rank0维护属性离散化区间表，并将该属性离散化区间表均匀划分给多个线程，所述多个线程同时启动对相应的空间连续属性的栅格数据进行离散化；

步骤三、管理进程Rank0将空间属性均匀分给n个运算进程处理，并收集n个运算进程的处理结果、构建完整的粗糙关系表，将该粗糙关系表发给每个运算进程，每个运算进程根据粗糙关系表建立一个属性子集；

步骤四、管理进程Rank0将每个运算进程根据所对应的属性子集进行并行训练子分类器产生模型，该子分类器为与所述的进程一一对应的子分类器，每个子分类器进行预测该子分类器对应的属性子集的类型，统计所有子分类器预测结果，以投票选举的方式选取投票最多的预测结果。

本实施方式在步骤三之后，各个进程均获得“属性子集”，各个进程通过属性子集并行训练一个指定的分类器（如：ID3，SVM，神经网此类模型为传统算法），可以用相对较小的数据量（相对数百维，本算法每个子集的大小通常10-20个，数据量缩小数十被倍）快速训练产生模型。这些模型在决策过程中可以只用投票选举的形式如图6所示，可以有效的防止过度拟合，增加分类精度。

本实施方式所述的投票选举方式为：假如目前有n个分类器，对于一个需要预测的对象x，这n个分类器分别作出预测，期中m1个分类器决策认为是”A类型”，m2个分类器决策认为是“B”类型，。这时以投票，少数服从多数为原则，取较多分类器认同的决策为集成分类器整体的决策。就是投票选举过程。

具体实施方式二、本实施方式与具体实施方式一所述的集成分类器的分类方法的区别在于，步骤A所述的栅格数据是高维度栅格数据。

本实施方式对于海量的高维度的栅格数据，传统算法速度慢精度低，而本专利达到快速处理栅格数据，获取分类模型，而且由于采用异构决策机制，所以分类精度也较高。

具体实施方式三、结合图3具体说明本实施方式，本实施方式与具体实施方式一或二所述的集成分类器的分类方法的区别在于，步骤二所述每个线程启动对相应的空间连续属性的栅格数据进行离散化的具体步骤为：

步骤二一、设置聚类个数为ceil；

步骤二二、在该线程启动的空间连续属性的最大值和最小值之间求取均匀分布聚类初始中心；

步骤二三、根据K-Means算法对均匀分布聚类初始中心进行聚类，形成ceil个聚类；

步骤二四、对于每一个聚类输出其最小和最大值，形成ceil个值域区间；

步骤二五、将所述ceil个值域区间构成一个区间列表。

本实施方式通过离散化，获得离散化区间，通过这组区间就可以将原有的连续数据变为有限个数的1,2,3,4等数字，明晰关系，加快比对分析速度。对于多进程情况下，所有数据的处理流程如图4。

具体实施方式四、本实施方式与具体实施方式一或二所述的集成分类器的分类方法的区别在于，所述的步骤三中所述的粗糙关系表是一个二维表，表示二个属性直接的交叠程度，粗糙关系为1表示属性直接相关性最强，粗糙关系为0表示最不相关，粗糙关系表如下：

具体实施方式五、本实施方式与具体实施方式四所述的集成分类器的分类方法的区别在于，步骤三中每个运算进程根据粗糙关系表建立一个属性子集的具体步骤为：

步骤三一、在所述运算进程的粗糙关系表中随机选择一对粗糙关系不相关的属性，该属性的状态为“未使用”，将该属性加入所述运算进程的属性子集中，该子集为与所述运算进程一一对应的子集，并将其标记为“已使用”，

属性的状态为“已使用”或“未使用”；

步骤三二、在所述运算进程中，根据公式（8）计算每一对“未使用”的属性与所述运算进程的属性子集的关系，

属性与属性子集的粗糙关系为：

$>\mathrm{RTD}=\underset{1}{\overset{n}{\Sigma }}{\mathrm{RT}}_{(b,\mathrm{an})}---\left(8\right)$>

其中，b表示所述运算进程的属性子集，an表示任意一对“未使用”的属性，RT_(b，an)表示所述运算进程的属性子集与任意一对“未使用”的属性的粗糙关系；

步骤三三、选出计算结果最小的属性，将该属性加入到所述运算进程的属性子集中，并将所述运算进程的属性子集标记为“已使用”；

步骤三四、根据公式（6）计算所述运算进程的属性子集与维度全集D的关系；

$>{\gamma }_D\left(w\right)=\frac{\mathrm{Card}\left(\underset{X⋐\mathrm{IND}\left(w\right)}{U}{\mathrm{POS}}_D\left(X\right)\right)}{\mathrm{Card}\left(U\right)}---\left(6\right)$>

其中，w表示所述运算进程的属性子集，IND(w)为w子集所对应的不可区分关系，也就是在集合W中的元素，认为是区分不开的，不可比较的；Card(U)为计算集合的秩，为cardinal的缩写；POS_D(X)为X对应于D的正域，更一般的说法是，X集合被D集合完全包含；

步骤三五、当γ_D(w)=1时，输出所述运算进程的属性子集；

步骤三六、当γ_D(w)=0时，在所述运算进程中，根据公式（8）计算每一对“未使用”的属性与所述运算进程的属性子集的关系。

根据Pawlak的粗集理论，一个信息系统S可以被看作是一个数据表。它可以由对S＝(U，A)表示，其中：论域U是非空有限集合；A是非空有限的属性集合；对于A中的每一个元素a∈A,存在一个映射a:U→V_a,其中V_a是a取值的集合。一个决策表就是形如S＝(U，A∪{d})的信息系统,其中是决策属性。对于任意的属性集合存在一个不可区分关系IND(P)：

$>\mathrm{IND}\left(P\right)=\{(x,y)\in U^2|\forall a\in P,a\left(x\right)=a\left(y\right)\}---\left(1\right)$>

其中，x和y均为多维空间下的，多维度矢量；

一个基于P不可区分关系的等价类可以定义为：

[x]_p={y∈U |(x,y)∈IND(P)}                                    （2）

根据不可区分关系可以定义上下近似集.令集合X∈U，X可以由下面两个集合近似的表示：

下近似集：上近似集：如果那么对就称之为粗糙集。定义正域、负域和边域：X为一个集合，表示X的下近似集，[x]_D∩X表示X的上近似集，

POS_D(X)=DX                                         (3)

$>{\mathrm{NEG}}_D\left(X\right)=1-\bar{D}X---\left(4\right)$>

BND_D(X)=NEG_D(X)-POS_D(X)                            (5)

粗集的一个重要概念是属性之间的依赖度。属性Q对于属性D的依赖程度可以定义为(属性依赖度，由γ表示)：

$>{\gamma }_D\left(w\right)=\frac{\mathrm{Card}\left(\underset{X⋐\mathrm{IND}\left(w\right)}{U}{\mathrm{POS}}_D\left(X\right)\right)}{\mathrm{Card}\left(U\right)}---\left(6\right)$>

根据公式（6）可知当子集R为所有维度（属性）的总和时，公式（6）结果为1。当D₁={a₁},D₂={a₁,a₂}时计算Diff(D2D1）=γ_D2(Q)-γ_D1(Q)，此时如果Diff值较大，说明a1和a2维度覆盖的决策领域不同且范围较大，适合组合一起；如果Diff值较小，说明a1和a2维度覆盖的决策领域相近（极端情况a2=a1，Diff＝0两个属性没有任何区别），两个属性不适合组合在一起。所以粗糙关系表中的每一个表项计算公式为：

粗糙关系RT_(a1,a2）=1-(γ_{a1，a2}(Q)-γ_a1(Q))                      (7）

对于一个属性b与一个属性集D={a₁,a₂,…,a_n},其粗糙关系为:

$>\mathrm{RTD}=\underset{1}{\overset{n}{\Sigma }}{\mathrm{RT}}_{(b,\mathrm{an})}---\left(8\right)$>

粗糙关系计算量较大，需要按照图5进行并行，在计算之后可以遍历粗糙关系表来计算“属性与集合关系”该过程为一个求和统计过程，计算量较小。在粗糙关系表建立之后，获得各个属性子集。

具体实施方式六、本实施方式所述的集成分类器的分类方法，它包括下述步骤：

用于多进程和多线程组合的方式读取待处理的栅格数据的装置，该装置包括如下模块：

用于输入集成分类器的子分类器个数n的模块；

其中，n为子分类器的个数，n大于等于2，通过期望算法将栅格数据的所有空间属性按照决策能力分为n份，每个分类器均具备全集全部的分类能力，

用于启动n+1个进程的模块；

其中，n+1个进程为Rank 0、Rank 1…Rankn；Rank0为管理进程，Rank 1…Rankn均为运算进程，运算进程Rank 1…Rankn分别与n个子分类器一一对应，

用于在当前进程为管理进程Rank 0时，构造空的粗糙关系表，将待处理的栅格数据均匀划分给每个运算进程；启动n个线程，每个线程单独对应一个运算进程的模块；

其中，线程包括第1线程、第2线程…第n线程，

用于在当前进程为运算进程时，每个进程均同时读取待处理的栅格数据的模块；

用于管理进程Rank0维护属性离散化区间表，并将该属性离散化区间表均匀划分给多个线程，所述多个线程同时启动对相应的空间连续属性的栅格数据进行离散化的装置；

用于管理进程Rank0将空间属性均匀分给n个运算进程处理，并收集n个运算进程的处理结果、构建完整的粗糙关系表，将该粗糙关系表发给每个运算进程，每个运算进程根据粗糙关系表建立一个属性子集的装置；

用于管理进程Rank0将每个运算进程根据所对应的属性子集进行并行训练子分类器产生模型，该子分类器为与所述的进程一一对应的子分类器的装置。

用于管理进程Rank0将每个运算进程根据所对应的属性子集进行并行训练子分类器产生模型，该子分类器为与所述的进程一一对应的子分类器，每个子分类器根据模糊粗糙集理论进行预测该子分类器对应的属性子集的类型，统计所有子分类器预测结果，以投票选举的方式选取投票最多的预测结果的装置。

具体实施方式七、本实施方式与具体实施方式六所述的集成分类器的分类方法的区别在于，所述的栅格数据是高维度栅格数据。

具体实施方式八、本实施方式与具体实施方式六或七所述的集成分类器的分类方法的区别在于，用于管理进程Rank0维护属性离散化区间表，并将该属性离散化区间表均匀划分给多个线程，所述多个线程同时启动对相应的空间连续属性的栅格数据进行离散化的装置，包括如下模块：

用于设置聚类个数为ceil的模块；

用于在该线程启动的空间连续属性的最大值和最小值之间求取均匀分布聚类初始中心的模块；

用于根据K-Means算法对均匀分布聚类初始中心进行聚类，形成ceil个聚类的模块；

用于将每一个聚类输出其最小和最大值，形成ceil个值域区间的模块；

用于将所述ceil个值域区间构成一个区间列表的模块。

具体实施方式九、本实施方式与具体实施方式六所述的集成分类器的分类方法的区别在于，所述的粗糙关系表是一个二维表，表示二个属性直接的交叠程度，粗糙关系为1表示属性直接相关性最强，粗糙关系为0表示最不相关，粗糙关系表如下：

具体实施方式十、本实施方式与具体实施方式六所述的集成分类器的分类方法的区别在于，用于管理进程Rank0将空间属性均匀分给n个运算进程处理并收集n个运算进程的处理结果、构建完整的粗糙关系表，将该粗糙关系表发给每个运算进程，每个运算进程根据粗糙关系表建立一个属性子集的装置，包括如下模块：

用于在所述运算进程的粗糙关系表中随机选择一对粗糙关系不相关的属性，该属性的状态为“未使用”，将该属性加入所述运算进程的属性子集中，该子集为与所述运算进程一一对应的子集，并将其标记为“已使用”的模块，

属性的状态为“已使用”或“未使用”；

用于在所述运算进程中，根据公式（8）计算每一对“未使用”的属性与所述运算进程的属性子集的关系的模块，

属性与属性子集的粗糙关系为：

$>\mathrm{RTD}=\underset{1}{\overset{n}{\Sigma }}{\mathrm{RT}}_{(b,\mathrm{an})}---\left(8\right)$>

其中，b表示所述运算进程的属性子集，an表示任意一对“未使用”的属性，RT_(b，an)表示所述运算进程的属性子集与任意一对“未使用”的属性的粗糙关系；

用于选出计算结果最小的属性，将该属性加入到所述运算进程的属性子集中，并将所述运算进程的属性子集标记为“已使用”的模块

用于根据公式（6）计算所述运算进程的属性子集与维度全集D的关系的模块；

$>{\gamma }_D\left(w\right)=\frac{\mathrm{Card}\left(\underset{X⋐\mathrm{IND}\left(w\right)}{U}{\mathrm{POS}}_D\left(X\right)\right)}{\mathrm{Card}\left(U\right)}---\left(6\right)$>

其中，w表示所述运算进程的属性子集，IND(w)为w子集所对应的不可区分关系，Card(U)为计算集合的秩，POS_D(X)为X对应于D的正域；

用于在当γ_D(w)=1时，输出所述运算进程的属性子集的模块；

用于在当γ_D(w)=0时，在所述运算进程中，根据公式（8）计算每一对“未使用”的属性与所述运算进程的属性子集的关系的模块。