几何集成的改进——特征边界点快速计算  

Fast computation of characteristic boundary points for improving geometric ensembles

作　　者：李玉鑑[1] 孟东霞[1] 桂智明[1] 

机构地区：[1]北京工业大学计算机学院,北京100124

出　　处：《山东大学学报（工学版）》2011年第4期56-60,共5页Journal of Shandong University（Engineering Science）

基　　金：国家自然科学基金资助项目(60775010);北京市自然科学基金资助项目(4112009;4113067;4113068);北京市教委科技发展资助项目(KM201010005012);北京工业大学高层次人才培养资助项目

摘　　要：针对优化几何集成方法(optimized geometric ensembles,OGE)在计算特征边界点集合的过程中包含大量冗余运算且效率较低的缺陷,分别利用Gabriel近邻规则及其启发式搜索法加速特征边界点的选取过程,提出了两种改进的几何集成方法———Gabriel OGE和启发式OGE,并与OGE进行比较实验。实验结果表明,虽然Gabriel OGE中计算特征边界点的时间复杂度与OGE一样,但是因为减少了大量数学运算,计算速度明显提高;而启发式OGE不仅将平均时间复杂度降低为O(dM2),而且在处理大数据集时,计算效率最高。Gabriel OGE和启发式OGE在保证分类结果的同时有效提高了特征边界点集合的计算速度,大幅度减少时间消耗。In order to solve the low efficiency of optimized geometric ensembles（OGE） caused by a large number of redundant computations in constructing the set of characteristic boundary points,two improved geometric ensembles——Gabriel OGE and heuristics OGE were proposed respectively by applying Gabriel neighboring rule and its heuristics,which could accelerate the computation of characteristic boundary points compared with OGE in experiments.The results showed that although Gabriel OGE had the same time complexity as OGE in computing characteristic boundary points,it became much faster for reducing a number of redundant algorithm computations.Heuristics OGE could not only decrease the average time complexity to O（dM2）,but also have the most efficiency when dealing with a large dataset.Gabriel OGE and heuristics OGE could effectively increase the computing speed and greatly reduce the computing time while having the same classification results as OGE.

关 键 词：分片线性分类器 几何集成 Gabriel近邻规则 启发式搜索法 特征边界点 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]