基于搜索空间划分的概念生成算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

Supported bythe National Natural Science Foundation of China under Grant No60173006(国家自然科学基金);the National High-Tech Research and Development Plan of China under Grant No2003AA118020(国家高技术研究发展计划(863));the Major Program of Science and Technology Development Plan of Jilin Provinceof China under Grant No.20020303(吉林省科技发展计划重大项目)


An Algorithm for Generating Concepts Based on Search Space Partition
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用.概念格的构造在其应用过程中是一个主要问题.提出了一种基于搜索空间划分的概念生成算法SSPCG(search space partition based concepts generation),它将属性集合的幂集看作初始闭包搜索空间,迭代地将每个搜索空间划分为一些子搜索空间,并引入了子搜索空间的有效性判断,只搜索那些能生成正规闭包的子搜索空间,有效地提高了搜索效率;同时,在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度.由于所有子搜索空间是独立的,所以该算法可以很容易地扩展为并行算法.在随机生成的数据集和真实数据集上进行的实验测试表明,本算法的时间性能要优于Ganter提出的NextClosure算法.

    Abstract:

    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. This paper proposes a new algorithm called SSPCG (search space partition based concepts generation) based on the closures search space partition. The algorithm divides the closures search space into several subspaces in accordance with the criterions prescribed ahead, and introduces an efficient scheme to recognize the valid ones, which bounds searching just in these valid subspaces. An intermediate structure is employed to judge the validity of a subspace and compute closures more efficiently. Since the partition of the search space is recursive and the searching in subspaces is independent, a parallel version can be directly reached. The algorithm is experimental evaluated and compared with the famous NextClosure algorithm proposed by Ganter for random generated data, as well as for real application data. The results show that the algorithm performs much better than the later.

    参考文献
    相似文献
    引证文献
引用本文

齐红,刘大有,胡成全,卢明,赵亮.基于搜索空间划分的概念生成算法.软件学报,2005,16(12):2029-2035

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2004-04-26
  • 最后修改日期:2005-01-07
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号