基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法

求强连通分量的几种算法的实现与分析作者：陈燕,江克勤来源：《电脑知识与技术》2011年第09期摘要：有向图的强连通性是图论中的经典问题，有着很多重要的应用。

该文给出了求强连通分量的Kosaraju、Tarjan和Gabow三个算法的具体实现，并对算法的效率进行了分析。

关键词：强连通分量；深度优先搜索；Kosaraju算法；Tarjan算法；Gabow算法中图分类号：TP312文献标识码：A文章编号：1009-3044(2011)09-2140-03The Implementation and Analysis of Several Algorithms About Strongly Connected Components CHEN Yan1, JIANG Ke-qin2(1.Nanjing Health Inspection Bureau, Nanjing 210003, China; 2.School of Computer and Information, Anqing Teachers College, Anqing 246011, China)Abstract: Digraph of strong connectivity is the classic problems in graph theory, which arises in many important applications. In this paper, the detailed implementation of Kosaraju, Tarjan and Gabow algorithms is discussed for solving strongly connected components, and the efficiency of three algorithms is analyzed.Key words: strongly connected components; depth first search; Kosaraju; Tarjan; Gabow图的连通性是图论中的经典问题，所谓连通性，直观地讲，就是“连成一片”。

求强连通分量的tarjan算法强连通分量：是有向图中的概念，在一个图的子图中，任意两个点相互可达，也就是存在互通的路径，那么这个子图就是强连通分量。

（如果一个有向图的任意两个点相互可达，那么这个图就称为强连通图）。

如果u是某个强连通分量的根，那么：（1）u不存在路径可以返回到它的祖先。

（2）u的子树也不存在路径可以返回到u的祖先。

•例如：•强连通分量。

在一个非强连通图中极大的强连通子图就是该图的强连通分量。

比如图中子图{1,2,3,5}是一个强连通分量，子图{4}是一个强连通分量。

tarjan算法的基础是深度优先搜索，用两个数组low和dfn，和一个栈。

low数组是一个标记数组，记录该点所在的强连通子图所在搜索子树的根节点的dfn值，dfn数组记录搜索到该点的时间，也就是第几个搜索这个点的。

根据以下几条规则，经过搜索遍历该图和对栈的操作，我们就可以得到该有向图的强连通分量。

算法规则：•数组的初始化：当首次搜索到点p时，Dfn与Low数组的值都为到该点的时间。

•堆栈：每搜索到一个点，将它压入栈顶。

•当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’不在栈中，p 的low值为两点的low值中较小的一个。

•当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’在栈中，p的low值为p的low值和p’的dfn值中较小的一个。

•每当搜索到一个点经过以上操作后（也就是子树已经全部遍历）的low 值等于dfn值，则将它以及在它之上的元素弹出栈。

这些出栈的元素组成一个强连通分量。

•继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。

算法伪代码：tarjan(u){DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值Stack.push(u) // 将节点u压入栈中for each (u, v) in E // 枚举每一条边if (！dfn[v]) // 如果节点v未被访问过{tarjan(v) // 继续向下找Low[u] = min(Low[u], Low[v])}else if (v in S) // 如果节点v还在栈内Low[u] = min(Low[u], DFN[v])if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根do{v = S.pop // 将v退栈，为该强连通分量中一个顶点}while(u == v);}演示算法流程；从节点1开始DFS，把遍历到的节点加入栈中。

基于粗糙集理论的知识发现与推理技术研究随着信息技术的飞速发展，我们所接触到的数据越来越庞大，如何从这些数据中提取出有价值的信息，成为了信息学界的一个重要研究方向。

其中，基于粗糙集理论的知识发现与推理技术，成为了近年来研究的热点之一。

本文将对该领域的研究现状和前沿做一个总结和介绍。

一、粗糙集理论粗糙集理论是Polkowski和Skowron于1982年提出的，是一种从不完备和模糊的数据中提取知识的方法。

其主要思想是在给定的数据集中寻找属性间的约简，以建立一个简化后的数据模型，用来代表原始数据的识别需求。

粗糙集理论的应用广泛，在数据挖掘、模式识别、决策分析等领域都有重要应用。

粗糙集理论的关键概念包括：等价类、下近似集和上近似集等，这些概念的具体解释和使用在不同的应用场景下各有侧重。

二、基于粗糙集理论的知识发现基于粗糙集理论的知识发现是指从粗糙集的等价类中发现存在的规律、模式和特征。

这些规律和模式则可以进一步用于分类、聚类和数据降维等，从而在更广泛的应用中得到具体的应用。

在知识发现的过程中，粗糙集理论可以用在数据特征选择和数据分类等场景下。

以特征选择为例，基于粗糙集理论可以解决多特征冗余的问题。

对于每个特征，可以计算它对分类结果的影响程度，从而保留对分类结果有较大影响的特征，使特征的维度不至于过高，在减少计算复杂度的同时，尽可能保证分类准确率。

三、基于粗糙集理论的知识推理基于粗糙集理论的知识推理是指根据已知的规则和模式，对新数据进行分类或预测等，以逐渐完善数据模型。

知识推理可以采用分类规则、决策树等多种方式来实现，而采用粗糙集理论的知识推理方式，通常使用下近似集和上近似集等概念来进行分类。

在基于粗糙集理论的知识推理中，一般存在两种方式：一种是确定性知识推理，另一种是不确定性知识推理。

其中确定性知识推理通常采用约简算法，用于对数据进行二元分类，而不确定性知识推理则涉及模糊分类和模糊决策等模糊理论中的概念。

粗糙集理论综述收藏进入网络信息时代，随着计算机技术和网络技术的飞速发展，使得各个行业领域的信息急剧增加，如何从大量的、杂乱无章的数据中发现潜在的、有价值的、简洁的知识呢？数据挖掘(Data Mining)和知识发现(KDD)技术应运而生。

粗糙集理论作为一种数据分析处理理论，在1982年由波兰科学家Z.Pawlak创立[1]。

最开始由于语言的问题，该理论创立之初只有东欧国家的一些学者研究和应用它，后来才受到国际上数学界和计算机界的重视。

1991年，Pawlak出版了《粗糙集—关于数据推理的理论》这本专著，从此粗糙集理论及其应用的研究进入了一个新的阶段，1992年关于粗糙集理论的第一届国际学术会议在波兰召开。

1995年ACM将粗糙集理论列为新兴的计算机科学的研究课题。

粗糙集理论作为一种处理不精确(imprecise)、不一致(inconsistent)、不完整(incomplete)等各种不完备的信息有效的工具，一方面得益于他的数学基础成熟、不需要先验知识；另一方面在于它的易用性。

由于粗糙集理论创建的目的和研究的出发点就是直接对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律，因此是一种天然的数据挖掘或者知识发现方法，它与基于概率论的数据挖掘方法、基于模糊理论的数据挖掘方法和基于证据理论的数据挖掘方法等其他处理不确定性问题理论的方法相比较，最显著的区别是它不需要提供问题所需处理的数据集合之外的任何先验知识，而且与处理其他不确定性问题的理论有很强的互补性(特别是模糊理论)。

目前，粗糙集理论的研究方向主要是三个方面：理论上，①利用抽象代数来研究粗糙集代数空间这种特殊的代数结构[2～7]。

②利用拓扑学描述粗糙空间[8]。

③还有就是研究粗糙集理论和其他软计算方法或者人工智能的方法相接合，例如和模糊理论、神经网络、支持向量机、遗传算法等[9～19]。

④针对经典粗糙集理论框架的局限性，拓宽粗糙集理论的框架，将建立在等价关系的经典粗糙集理论拓展到相似关系甚至一般关系上的粗糙集理论[20～23]。

DUFE管理科学与工程研究方法概论学号：2013100654专业：电子商务姓名：徐麟粗糙集理论一、粗糙集的来源与发展智能信息处理是当前信息科学理论和应用研究中的一个热点领域。

由于计算机科学与技术的发展，特别是计算机网络的发展，每日每时为人们提供了大量的信息。

信息量的不断增长，对信息分析工具的要求也越来越高，人们希望自动地从数据中获取其潜在的知识。

特别是近20年间，知识发现(规则提取、数据挖掘、机器学习)受到人工智能学界的广泛重视，知识发现的各种不同方法应运而生。

粗糙集(RoughSet，也称Rough集、粗集)理论是Pawlak教授于1982年提出的一种能够定量分析处理不精确、不一致、不完整信息与知识的数学工具。

粗糙集理论最初的原型来源于比较简单的信息模型，它的基本思想是通过关系数据库分类归纳形成概念和规则，通过等价关系的分类以及分类对于目标的近似实现知识发现。

由于粗糙集理论思想新颖、方法独特，粗糙集理论已成为一种重要的智能信息处理技术，该理论已经在机器学习与知识发现、数据挖掘、决策支持与分析等方面得到广泛应用。

粗糙集理论与应用的核心基础是从近似空间导出的一对近似算子，即上近似算子和下近似算子(又称上、下近似集)。

经典Pawlak模型中的不分明关系是一种等价关系，要求很高，限制了粗糙集模型的应用。

二、粗糙集的理论基础1、概念、可定义集从经典的角度来看，每个概念都包含其内涵和外延。

为了给出概念内涵和外延的具体描述，我们考虑一个简单的知识表达系统，即信息表。

信息表就是一组可定义集的形式化定义如下：在信息表M中，如果称子集XAU是可被属性子集AAAt定义的，当且仅当在语言L(A)中存在一个公式<使得X=m(<)。

否则，X 称为不可定义的。

2、近似空间语言L(A)的所有可定义集正好构造成一个R代数R(U/E(A))，即Def(U，L(A))=R(U/E(A))。

序对apr=(U，E(A))称为一个Pawlak近似空间，简称近似空间。

有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一个强连通分量(S trongly Connected Component, SCC)最关键通用部分：强连通分量一定是图的深搜树的一个子树。

一、Kosaraju算法1. 算法思路基本思路：这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图GT。

(步骤1)先用对原图G进行深搜形成森林(树)，（步骤2）然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT)，能遍历到的顶点就是一个强连通分量。

余下部分和原来的森林一起组成一个新的森林，继续步骤2直到没有顶点为止。

改进思路：当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中(由开篇第一句话可知))，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。

想象一下，如果步骤2是从森林里选择树，那么哪个树是不连通(对于GT来说)到其他树上的呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。

这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i] =j。

那么，我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。

每次深搜都得到一个强连通分量。

隐藏性质:分析到这里，我们已经知道怎么求强连通分量了。

但是，大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢？如果在看上述思路的时候，你的脑子在思考，相信你已经知道了！！！它就是：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。

为什么呢？首先，应该明确搜索后的图一定是有向无环图呢？废话，如果还有环，那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。

寻找强连通分量的方法和证明嘿，咱今儿就来唠唠寻找强连通分量的那些事儿！你知道吗，这强连通分量就像是一个小团体，里面的元素那可是紧密相连啊！就好比一群好朋友，不管谁跟谁都能说得上话，互相都有关系。

那怎么找到这些小团体呢？有一种方法叫 Kosaraju 算法。

这就好像是我们在一个大迷宫里找特定的区域，先顺着一条路走，标记好走过的地方，然后再换个方向走，看看哪些地方是能来回都能走到的，那些就是强连通分量啦！它先对图进行深度优先搜索，然后再把图反转过来，再进行一次深度优先搜索，嘿，神奇吧，这样就能把那些小团体给揪出来啦！还有 Tarjan 算法呢！这就像是一个超级侦探，一点点地去挖掘线索，把那些隐藏的强连通分量给找出来。

它通过巧妙地利用栈和一些标记，就能准确地找到这些紧密相连的部分。

那怎么证明这些算法是有效的呢？这就好像我们要证明一件事情是对的一样。

我们可以从它们的原理出发，看看是不是真的能把该找的都找到，而且不会找错。

就像我们检查自己的作业一样，要仔细认真，不能有一点儿马虎。

你想想看，如果这些算法不靠谱，那我们岂不是白费力气？那可不行！所以证明它们的有效性是非常重要的呀！比如说，我们可以用一些特殊的例子来测试，看看是不是每次都能准确找到强连通分量。

如果都能找到，那说明这个算法厉害呀！而且啊，这些算法可不是随便想出来的，那是经过很多聪明的脑袋瓜琢磨出来的呢！他们就像一群勇敢的探险家，在数学的海洋里不断探索，终于找到了这些宝藏般的方法。

你再想想，要是没有这些方法，我们面对那些复杂的图该怎么办呀？岂不是要抓瞎啦！所以说呀，这些方法和证明可太重要啦！我们在学习这些的时候，可不能死记硬背哦！要理解它们背后的原理，就像理解朋友的心思一样。

只有这样，我们才能真正掌握这些知识，在需要的时候能拿出来用。

哎呀呀，寻找强连通分量的方法和证明，真的是太有意思啦！它们就像一把钥匙，能打开那神秘的图的世界，让我们看到其中的奥秘和精彩。

基于K中心点和粗糙集的KNN分类算法
文武;李培强
【期刊名称】《计算机工程与设计》
【年(卷),期】2018(039)011
【摘要】为有效解决KNN算法在文本分类时效率随着数据规模的增大而降低这一问题,提出基于K中心点(K-Medoids)和粗糙集(rough set)的KNN分类方法(KRS-KNN).通过K中心点算法对文本数据集进行聚合,形成类簇,计算簇心和其它样本点的相异度,将相异度大于最后簇心相异度的样本剔除,运用粗糙集理论对得到的每个类簇进行分割,通过上、下作差得到的边界样本,通过KNN算法确定其最终类别.实验结果表明,文本数据的计算规模得到了降低,提高了文本数据的分类效率.【总页数】6页(P3389-3394)
【作者】文武;李培强
【作者单位】重庆邮电大学通信新技术应用研究中心,重庆400065;重庆信科设计有限公司,重庆400065;重庆邮电大学通信新技术应用研究中心,重庆400065【正文语种】中文
【中图分类】TP391.1
【相关文献】
1.基于粗糙集的快速KNN文本分类算法 [J], 孙荣宗;苗夺谦;卫志华;李文
2.一种基于Canopy和粗糙集的CRS-KNN文本分类算法 [J], 姚彬修;倪建成;于苹苹;曹博;李淋淋
3.基于粗糙集的加权KNN数据分类算法 [J], 刘继宇;王强;罗朝晖;宋浩;张绿云
4.基于邻域粗糙集的加权KNN肿瘤基因表达谱分类算法 [J], 陈智勤
5.一种基于粗糙集的改进KNN文本分类算法 [J], 苟和平;景永霞;冯百明;李勇因版权原因，仅展示原文概要，查看原文内容请购买。

粗糙集和计算智能相结合的数据挖掘算法研究的开题报告一、研究背景随着互联网和移动设备的日益普及，越来越多的数据被产生并被传输，数据的规模也随之呈现指数级增长。

面对如此数量庞大的数据，如何从中挖掘出有价值的信息成为了数据科学领域的一个重要挑战。

数据挖掘作为从数据中获取有用信息的一种方法，已经成为了解决这一挑战的主要方式。

在数据挖掘算法中，集合运算是其中的一个核心部分。

然而，传统的集合运算只考虑了数据项之间的匹配度，没有考虑数据项之间的相似度和模糊性。

这种情况下，会导致结果的不准确和误判。

在此背景下，粗糙集和计算智能相结合的数据挖掘算法应运而生。

粗糙集理论是一种能够处理不确定性和不精确性的数学工具，已经被广泛应用于数据挖掘领域。

计算智能包括神经网络、遗传算法、模糊逻辑等多种方法。

与传统的数据挖掘算法相比，粗糙集和计算智能相结合的数据挖掘算法能够处理更为复杂的数据集，并得出更加准确的结论。

因此，本研究旨在探究粗糙集和计算智能相结合的数据挖掘算法。

二、研究目的和意义本研究的目的是探究粗糙集和计算智能相结合的数据挖掘算法，并应用于实际数据集中。

本研究的意义主要体现在以下几个方面：1.对促进数据科学和数据挖掘领域的发展具有重要意义。

随着数据规模的不断增大，数据挖掘成为了解决大规模数据处理问题的关键技术之一。

本研究探究的算法能够更好地处理数据集中的不确定性和模糊性，使得数据挖掘结果更加准确和可靠。

2.对解决复杂系统建模问题具有重要意义。

复杂系统包括许多不确定性和模糊性因素，使用传统的数据挖掘算法很难做到准确的预测和建模。

本研究将通过粗糙集和计算智能相结合的方法来解决这一问题。

3.对教育教学和科学研究都具有重要意义。

本研究将提供一种新的数据挖掘算法，并将其应用于实际数据集中。

这有助于学生了解数据挖掘算法的原理和应用场景，并为科研工作者提供新的思路和方法。

三、研究内容和方法本研究的主要内容包括以下几个方面：1.对粗糙集理论和计算智能方法进行深入研究，掌握其基本原理和应用方法。