主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
齐红,刘大有,胡成全,卢明,赵亮.基于搜索空间划分的概念生成算法.软件学报,2005,16(12):2029-2035
基于搜索空间划分的概念生成算法
An Algorithm for Generating Concepts Based on Search Space Partition
投稿时间:2004-04-26  修订日期:2005-01-07
DOI:
中文关键词:  形式概念分析  概念格  搜索空间  闭包系统  闭集
英文关键词:formal concept analysis  concept lattice  search space  closure system  closed set
基金项目: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(吉林省科技发展计划重大项目)
作者单位
齐红 吉林大学,计算机科学与技术学院,吉林,长春,130012 
刘大有 吉林大学,计算机科学与技术学院,吉林,长春,130012
符号计算与知识工程教育部重点实验室(吉林大学),吉林,长春,130012 
胡成全 吉林大学,计算机科学与技术学院,吉林,长春,130012 
卢明 吉林大学,计算机科学与技术学院,吉林,长春,130012 
赵亮 吉林大学,计算机科学与技术学院,吉林,长春,130012 
摘要点击次数: 2865
全文下载次数: 3495
中文摘要:
      概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用.概念格的构造在其应用过程中是一个主要问题.提出了一种基于搜索空间划分的概念生成算法SSPCG(search space partition based concepts generation),它将属性集合的幂集看作初始闭包搜索空间,迭代地将每个搜索空间划分为一些子搜索空间,并引入了子搜索空间的有效性判断,只搜索那些能生成正规闭包的子搜索空间,有效地提高了搜索效率;同时,在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度.由于所有子搜索空间是独立的,所以该算法可以很容易地扩展为并行算法.在随机生成的数据集和真实数据集上进行的实验测试表明,本算法的时间性能要优于Ganter提出的NextClosure算法.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利