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

山东大学学报(工学版) ›› 2011, Vol. 41 ›› Issue (4): 56-60.

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

李玉鑑,孟东霞*,桂智明

北京工业大学计算机学院,北京100124

收稿日期:2011-04-15 出版日期:2011-08-16 发布日期:2011-04-15
通讯作者: 孟东霞(1986- ),女,河北沧州人,硕士生,主要研究方向为模式识别. E-mail: mengdx@emails.bjut.edu.cn E-mail:mengdx@emails.bjut.edu.cn
作者简介:李玉鑑(1968- ),男,湖南邵东人,教授,博士,博士生导师,主要研究方向为模式分析和机器智能. E-mail:liyujian@bjut.edu.cn
基金资助:
国家自然科学基金资助项目(60775010);北京市自然科学基金资助项目(4112009, 4113067,4113068);北京市教委科技发展资助项目(KM201010005012);北京工业大学高层次人才培养资助项目

Fast computation of characteristic boundary points for improving geometric ensembles

LI Yu-jian, MENG Dong-xia*, GUI Zhi-ming

College of Computer Science and Technology, Beijing University of Technology, Beijing 100124, China

Received:2011-04-15 Online:2011-08-16 Published:2011-04-15

摘要/Abstract

摘要：

针对优化几何集成方法(optimized geometric ensembles, OGE)在计算特征边界点集合的过程中包含大量冗余运算且效率较低的缺陷,分别利用Gabriel近邻规则及其启发式搜索法加速特征边界点的选取过程,提出了两种改进的几何集成方法——Gabriel OGE和启发式OGE,并与OGE进行比较实验。实验结果表明,虽然Gabriel OGE中计算特征边界点的时间复杂度与OGE一样,但是因为减少了大量数学运算,计算速度明显提高;而启发式OGE不仅将平均时间复杂度降低为O(dM²),而且在处理大数据集时,计算效率最高。Gabriel OGE和启发式OGE在保证分类结果的同时有效提高了特征边界点集合的计算速度,大幅度减少时间消耗。

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

Abstract:

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 with OGE in computing characteristic boundary points, it became much faster for reducing a number of redundant algorithm computations. Heuristics OGE could not only decreases the average time complexity to O(dM²), 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 when having the same classification results with OGE.

Key words: piecewise linear classifier, geometric ensembles, Gabriel neighboring rule, heuristic algorithm, characteristic boundary points

李玉鑑,孟东霞*,桂智明. 几何集成的改进——特征边界点快速计算[J]. 山东大学学报(工学版), 2011, 41(4): 56-60.

LI Yu-jian, MENG Dong-xia*, GUI Zhi-ming. Fast computation of characteristic boundary points for improving geometric ensembles[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(4): 56-60.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed