案例索引BCS-Tree及其构建方法研究  

Research on Case Index BCS-Tree and Its Constructing Method

作　　者：范海雄[1] 刘付显[1] 夏璐[1] 

机构地区：[1]空军工程大学防空反导学院,西安710051

出　　处：《计算机研究与发展》2013年第12期2629-2641,共13页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展计划基金项目(613900201);国家自然科学基金项目(51075395);全军军事学研究生课题项目(2011JY002-504);空军工程大学研究生创新基金项目(HX1112);防空反导学院优秀博士论文扶持基金项目(DY12104);空军工程大学防空反导学院研究生创新基金项目(HX1112)

摘　　要：为克服现有案例索引方法存在的不足,提出了一种新的索引结构BCS-Tree.首先,对松弛聚类(graph-based relaxed clustering,GRC)算法进行了自适应改进,以克服现有基于聚类方法受初值影响大、只能适应凸形聚类等缺点;其次,将KICA与最小外接矩阵(minimum bounding rectangle,MBR)结合,增强了MBR方法对非线性和非正态分布数据的处理能力;然后,在给出双基点选择方法的基础上,提出了基于改进GRC和双基点聚类分割的BCS-Tree构建方法;最后,基于对查询点和案例数据之间可能分布关系的全面分析,设计了BCS-Tree的查询算法,并结合理论推导和实例验证,对BCS-Tree及其查询算法进行了分析.结果证明,所提的索引构建方法具有较强的参数鲁棒性和适用性,且BCS-Tree及其查询算法具有良好的检索效能.Aiming at the existing problems in case index study, a new method, called BCS-Tree, is proposed. Firstly, the GRC algorithm is improved in self-adaptive way, which can solve deficiencies of being seriously affected by initial values and just applying to convex cluster based on existing cluster methods. Then the handling ability of MBR method for the nonlinearity and no normality data is enhanced by integrating KICA with MBR. After analyzing existing method, the dual reference point selection method is designed. Moreover, the BCS-Tree constructing method is presented based on the improved GRC algorithm and dual reference point clustering splitting. Finally, based on comprehensive analyzing the possible distributing relation between query point and case data, the BCS-Tree query algorithm is designed. Furthermore, the BCS-Tree and query algorithm are analyzed by theory derivation and instance verification. The result proves that the BCS-Tree index constructing method presented in this paper is of better robustness and applicability, and BCS-Tree together with the query algorithm is of better searching efficiency. For case-based reasoning and case index research domain, the BCS-Tree provides effective method supporting and new research thoughts.

关 键 词：案例索引 BCS-Tree 松弛聚类 核独立分量分析 最小外接矩阵(MBR) 聚类分割 

分 类 号：TP311.132[自动化与计算机技术—计算机软件与理论] TP182[自动化与计算机技术—计算机科学与技术]