基于搜索空间划分的并行概念生成算法  

A Parallel Algorithm Based on Search Space Partition for Generating Concepts

作　　者：齐红[1] 刘大有[1] 胡成全[1] 卢明[1] 赵亮[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012

出　　处：《计算机科学》2005年第4期55-58,共4页Computer Science

基　　金：国家自然科学基金(项目编号60173006);国家高技术研究发展计划(项目编号2003AA118020);吉林省科技发展计划重大项目(吉科合字20020303);吉林大学符号计算与知识工程教育部重点实验室资助

摘　　要：概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用。概念格的构造在其应用过程中是一个主要问题。本文提出了一种基于搜索空间划分的并行概念生成算法,它对整个闭包搜索空间进行划分,并引入一种有效的测试方法,只搜索那些能生成正规闭包的子搜索空间,从而有效提高搜索效率;同时,在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度;由于所有子搜索空间相对独立,因此很容易得到一个井行的概念生成算法。Concept Lattice, the core data structure in Formal Concept Analysis, has been used widely in machine learning, data mining and knowledge discovery, information retrieval, etc. The main difficulty with concept lattice- based system comes from the lattice construction itself. In this paper, a parallel algorithm based on the closure search space partition for computing concepts is proposed. This algorithm divides the closure search space into several sub- spaces in accordance with criterions prescribed ahead and introduces an efficient scheme to recognize the valid ones, in which the searching for closures is bounded. An intermediate structure is employed to judge the validity of a subspace and compute closures more efficiently. Since the searching in subspaces are independent tasks, a parallel algorithm based on search space partition can be directly reached.

关 键 词：生成算法 空间划分 并行 搜索空间 数据结构 分析理论 机器学习 知识发现 数据挖掘 信息检索 应用过程 测试方法 搜索效率 运算速度 概念格 闭包 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]