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

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

一种新的概念格并行构造算法

概念格作为形式概念分析理论中的核心数据结构,在数据挖掘和知识发现、人工智能、信息检索、粗糙集[1]等领域得到了广泛的应用。概念格的构造在其应用过程中是一个主要问题。提出了一种基于闭包系统划分的概念格并行构造算法——Para_Prun算法,它将概念集合看作初始闭包系统,引入了子闭包系统的有效性判断,迭代生成相互独立的多个子闭包系统,然后在每个子闭包系统中独立生成概念,有效地提高了概念的求解速度。最后用实验证明了算法的正确性和有效性。     

基于同层节点集划分的模糊概念格并行构造算法

形式概念分析理论在诸多计算机领域得到广泛应用。模糊概念格的构造仍是其在应用过程中的一个主要问题。为提高模糊概念格的构造效率,对串行算法进行并行化改造,提出模糊概念格的并行构造算法。该算法对节点进行层次划分,给出了同层节点的定义,得出同层节点构造任务相互独立的重要性质,并引入映射函数简化搜索空间的遍历,提高搜索模糊概念格的效率,并行构造模糊概念格,达到了提高构造效率的目的。实验表明该算法在面对大规模的构造任务时,具有良好的性能。     

模糊形式概念并行构造算法

形式概念分析理论已经广泛地应用于计算机诸多领域.当前,模糊概念格直接构造仍然是该领域主要问题之一,其构造过程具有指数级时间复杂度.为了提高模糊概念格构造效率,文中对串行模糊概念构造算法进行并行化改进,将模糊集合组合搜索空间映射为自然数区间,简化了搜索空间表示、划分和遍历过程,进而提出并行模糊概念构造算法(ParallelFuzzyNextClosure,ParaFuNeC).该算法对搜索空间均匀划分,子搜索空间彼此独立,从而避免并行任务之间同步、通讯等时间耗费,达到提高模糊概念构造效率的目标.时间复杂度分析和实验结果表明该算法在大规模计算任务情况下,加速比随着并行度的提高呈正比增长趋势.另外,串行比例指标表明ParaFuNeC算法在大规模计算任务情况下具有更好的可扩展性.     

利用二部图生成概念格

概念格作为一种有效的知识发现与数据处理的工具,在许多领域得到了广泛应用,概念格的构造在其应用中具有重要的意义。每个概念格的形式背景都可以对应一个二部图,本文通过二部图的极大完全子图的概念来生成概念格,给出了基于二部图的深度优先的概念格的迭代算法。首先,对形式背景进行必要的约简;其次,利用二部图的极大完全子图得到顶层概念的直接子概念;最后,通过求二部图的导出子图来简化形式背景,并得出每个概念的直接子概念和所有子概念,从而生成概念格。     

基于内涵亏值的概念格渐进式构建

为了避免构建概念格时的繁琐过程,提高概念格构建的效率,提出了一种基于内涵亏值通过查找顶元素来快速渐进式生成概念格的新方法。首先,形式化地定义了顶元素、旧概念、产生概念、新概念、产生子概念、内涵亏值集合、剩留父概念、超集删除与正则队列;提出了概念格元素是否为顶元素的判定定理并给出了其证明;其次,在原概念格的正则队列中依次取概念元素,经超集删除后得到剩留父概念;最后,从剩留父概念查找其所在等价类的顶元素,逐步生成新概念格的正则队列。理论分析时间复杂度较基于属性的渐进式概念格生成（CLIF_A）算法与FastAddIntent算法有效降低,在实验例证对比中,概念数目大于150时,所用时间远少于对比算法。实验结果表明该算法方法简单,构建效率较对比算法明显提高。     

基于概念的序列模式挖掘研究

现有的序列模式算法大都需要频繁访问数据库,效率低.本文提出了一种只需访问数据库一次的基于概念的序列模式算法SPC(Sequential Pattern Algorithm Based on Concept).它利用概念来保存信息,通过划分搜索空间得到概念,并在保证数据挖掘结果正确的前提下采用项有序,合并等价子空间和舍弃无效子空间等手段减少搜索空间数量,提高了效率.     

基于负载均衡的模糊概念并行构造算法

提高模糊概念格直接构造效率是形式概念分析领域的主要问题之一,而当前基于模糊伽罗瓦联系的闭包运算仍是构造模糊概念的主要计算负荷,为此,提出一种基于负载均衡的并行构造模糊概念算法.该算法使用树状结构组织,遍历由自然数区间简化的搜索空间,逐级并行产生模糊概念、缩减搜索区间,并通过重新划分子搜索空间,实现各个计算节点负载均衡.实验结果表明,所提出的算法在稀疏数据集上表现优秀,能够有效地提高模糊概念构造效率.     

基于属性的概念格快速渐进式构造算法

概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用,概念格的构造在其应用过程中是一个主要问题.提出了采用树结构对概念格节点进行组织,研究了基于属性的概念格渐进式构造算法.概念格节点的树结构组织可以约束更新格节点和产生子格节点的搜索范围,从而可以有效地减少算法的执行时间.在随机生成的数据集上进行的实验测试表明,本算法的时间性能更优越.     

树状结构组织的属性优先的概念格渐进式算法

通过对概念格渐进式构造过程的分析,采用树结构对概念格节点进行组织,研究了利用这种树状组织的渐进式生成属性优先的概念格的构造算法。并结合实例说明了概念格的树结构组织在属性优先的渐进式生成概念格时,能有效地缩小产生子格节点的搜索范围和新增格节点的父节点和子节点的搜索范围,从而能快速生成概念格。     

一种概念格渐进式构造算法

概念格是形式概念分析理论的一种数据结构,它以独特优势在许多领域获得了广泛应用,如信息检索、软件工程、知识发现等,而概念格的构造效率问题是其应用的前提。相对传统算法需要遍历原始概念格中所有结点才能确定新概念的产生子的不足,减少了概念格更新过程中需遍历的概念结点数并缩小了新概念的产生子的父概念的搜索范围,提高和改善了效率。     

一种基于二叉树的快速穷举化搜索算法

本文在构造具有方向导向性的完全二叉树的基础上,提出了一种适合研究蛋白质构象的格子模型快速穷举搜索算法,该算法通过使用序列分解、排列分类方法,将复杂度为2^m种的CN^m次搜索变成复杂度为m种的CN^m次搜索,大大提高了利用格子模型搜索蛋白质能量最低构象的速度。同时,由于二叉树良好的方向性,有效地避免了搜索的盲目性。     

Fast and memory efficient mining of frequent closed itemsets

This paper presents a new scalable algorithm for discovering closed frequent itemsets, a lossless and condensed representation of all the frequent itemsets that can be mined from a transactional database. Our algorithm exploits a divide-and-conquer approach and a bitwise vertical representation of the database and adopts a particular visit and partitioning strategy of the search space based on an original theoretical framework, which formalizes the problem of closed itemsets mining in detail. The algorithm adopts several optimizations aimed to save both space and time in computing itemset closures and their supports. In particular, since one of the main problems in this type of algorithms is the multiple generation of the same closed itemset, we propose a new effective and memory-efficient pruning technique, which, unlike other previous proposals, does not require the whole set of closed patterns mined so far to be kept in the main memory. This technique also permits each visited partition of the search space to be mined independently in any order and, thus, also in parallel. The tests conducted on many publicly available data sets show that our algorithm is scalable and outperforms other state-of-the-art algorithms like CLOSET+ and FP-CLOSE, in some cases by more than one order of magnitude. More importantly, the performance improvements become more and more significant as the support threshold is decreased.     

基于溢出性原理的联盟结构生成算法

联盟结构的生成问题中由于搜索空间的联盟结构数目太大,因而搜索联盟结构的最底两层建立一个最坏情况下的边界值是必要的,边界值将最优的联盟结构限制在某个限界内,通过进一步的搜索可以在任意时间内得到一个较优值。根据联盟的溢出性质,文中提出了一种新的建立边界值的方法,即对任意不相交的联盟集合计算其上下边界的值,通过搜索特定的联盟结构集合建立最坏情况下的边界值。联盟的边界值建立以后,可以在任意时间内得到一个较优值,通过搜索剩余的联盟结构集合,可以对边界值和返回的联盟结构进一步优化。在此基础上文中提出了基于溢出性质的任意时间算法。实验结果表明,采用新的方法建立边界值,使得算法的收敛速度更快,效率更高。     

自适应近似树

在大规模多媒体数据库中进行基于内容的检索，高维数据牵引结构的研究是重要问题，提出了一种有效的高维索引结构－自适应近似树，阐述了它的结构，给出了构建和检索算法，它结合了树结构和顺序检索的共同优点，针对不同的数据分布情况可以自适应地调整结构，维数较低或数据分布偏斜较大时它呈现树的结构，高维或数据分布密集时呈现顺序扫描的结构，以达到更优的检索效率，在结构上，对MBR使用了压缩存储的方法以节省存储空间，在算法中充分利用了空间划分是MBS和MBR共存的特点，减少了大量复杂的计算，从而大大提高检索效率。     

双群体伪并行差分进化算法研究及应用

为了提高差分进化算法的全局搜索能力和收敛速率,本文提出了一种双群体伪并行差分进化算法.该算法结合差分进化算法DE/best/2/bin变异方式局部搜索能力强、收敛速度快,和DE/rand/1/bin变异方式全局搜索能力强、鲁棒性好的特点,采用串行算法结构实现并行差分进化算法独立进化、信息交换的思想.为使初始化个体均匀分布在搜索空间,提高算法收敛到全局最优解的鲁棒性,提出了一种基于平均熵的初始化策略.典型Benchmarks函数测试和非线性系统模型参数估计结果表明,该方法能显著提高算法的收敛速率和全局搜索能力.