文摘
并行处理的方法来提高计算机性能已成为发展趋势。基于粗糙集理论和知识减少分治的思想,提出了一种支持并行属性约简处理的分类方法,该方法使相对正域需要反复计算独立,和独立的相对正域计算并行处理;因此,属性约简可以基于此分类方法并行处理。最后,该算法与传统算法进行了分析,通过实验比较,结果表明,该方法在本文中有更多的优势在时间效率,证明了该方法可以提高属性约简的处理效率,使其更适合于大规模数据集。
1。介绍
与网络技术和存储技术的快速发展,尤其是云计算和大数据的发展,出现了许多复杂的问题,它不仅涉及大量计算,还处理大规模的数据,即所谓的大规模数据处理。各种数据的爆炸性增长,推动人类社会进入大数据的时代。大数据具有一系列的特点如高维度、强大的动态、不确定性和随机性,这反映出大数据的1]。如何获取有价值的信息的高度不确定大规模动态数据目前最重要的一个大数据领域的研究内容。为了进一步提高计算机的速度和性能,仅仅依靠提高计算机的性能不能满足要求。另一种方法是引入并行处理技术在不同层次方面的计算机体系结构。并行数据挖掘(2,3),结合并行计算和数据挖掘技术,已广泛应用于社会的各个方面。并行计算在数据挖掘中的应用,尤其是基于粗糙集理论的数据挖掘,是一个值得研究的问题。
粗糙集理论,提出了由波兰数学家pswlak [4- - - - - -6)发展的规则自动生成系统和软计算问题的研究。该理论主要使用上、下近似算子来描述不准确的知识,这是一个聪明的数学工具来处理不一致的和不确定的信息。它能有效地分析和处理各种各样的信息不准确等特点,不完备、不一致和揭示潜在的法律信息。这个理论不仅可以模型非线性、不连续的关系也具有较高的客观性,它能有效地处理大数据。与此同时,它还在决策分析领域取得了极大的成功,模式识别,数据挖掘7,8]。粗糙集的显著特征是,导出问题的决策或分类规则通过属性约简和值约简在保持分类能力不变。粗糙集属性约简理论,与其他理论相结合,可以有效地处理海量数据的高维动态。目前,在大数据领域,粗糙集理论的研究主要集中在模型扩展(9,10和属性约简算法设计11- - - - - -14]。
属性约简,也被称为降维或特征选择,来自机器学习和粗糙集的核心研究内容之一。其目的是删除不相关的属性分类的数据集和提高知识发现的性能数据。目前,属性约简已广泛应用于模式识别和数据挖掘的领域。人们已经做了很多研究在决策表属性约简。由于决策表中属性不同样重要的是,有很多冗余属性的属性集。这些冗余属性决定的结果,但没有影响减少决策的效率。因此,有必要去除这些冗余属性。因此,属性约简的主要想法是消除这些冗余属性,同时保持现有知识的分类能力不变,可以减少数据集的大小和提高知识发现的效率。因此,降低数据的维数通过属性约简算法可以减少训练时间,提高决策的质量。粗糙集属性约简算法不仅可以处理小规模数据也有效地处理大量数据。
并行计算,使用多个计算资源解决计算问题的同时,是一种有效的方法提高计算速度和处理能力的计算机系统,也适用于解决大规模问题的大规模和复杂的过程15]。并行计算的基本思想(16)是使用各个击破的策略将整个问题分解成几个独立的部分,每部分是由一个独立的处理器并行处理。并行计算系统可以是一个特别设计的超级计算机集群具有多个处理器或几个独立的计算机,在某些方面是相互联系的。为了减少大量的数据的维度,许多研究人员与粗糙集理论结合并行计算,划分任务,需要反复计算属性约简过程中为多个的子任务,然后将每个子任务部署到不同的处理器同时处理。最后,减少最终的结果可以通过减少中间结果结合合成技术,和许多成就了在理论研究和平台实现17- - - - - -21]。
基于分治的思想(22),本文将整个问题分为几个问题,然后应用各个击破的策略。粗糙集的知识约简方法基于分治法(23)可以有效地降低问题的复杂性处理和知识约简的效率大大提高。然而,分治法的核心属性是基于分治法和递归的概念;事实上,很难转换non-recursion的递归程序设计,并且没有并发分治法的过程中,因此很难并行实现属性约简。针对各个击破的方法的缺点不能实现并行计算,我们改善各个击破的方法,设计一个支持并行属性约简的分类方法。具体地说,它使得相对正域需要反复计算独立和独立相对正域计算可以并行执行。最后,该算法实现和测试,实验结果表明,该算法并不是有效的各个击破的方法在非平行环境中,但它显然是比“分而治之”的方法在并行环境。
2。相关概念和定义
为方便写作和描述,粗糙集理论的一些基本概念和定义下面列出。
定义1。决策表。让 是一个决策表;在这里是对象的集合,也称为宇宙, 是一个属性设置,和被称为条件属性集和决策属性集,分别不能是空的;也就是说, , 是属性值的集合, 是一个信息函数,它指定每个对象的属性值吗在 。
定义2。不清楚的关系。让 是一个决策表,对于每个属性的子集, 定义一个不清楚的关系<我>B作为 : 。
定义3。上、下近似集。一个决策表,每个属性的子集 和不清楚的关系 ,的上、下近似集基本定义的组吗如下:
定义4。积极的地区。让是一个领域,和等价关系上定义集群 ,和积极的地区的被定义为 : 。
定义5。相对减少。让一个域,是等价关系上定义的集群 ,让 是一个独立的子集相对于 ,如果存在 ;因此,是相对减少相对于 。
定义6。核心属性。让一个域,是等价关系上定义的集群 ;如果 , 是不必要的,相对于在 ;所有必要的属性相对于形成一套;一组被称为的核心 ,命名为 。
定义7。必要的属性。让一个域,和等价关系上定义集群
;如果所有的属性必然是相对于
,
是相对独立的相对于
。
接下来,下面给出了并行计算的相关概念。
定义8。并行计算机是计算机与多处理器并行处理的能力。
定义9。并行处理是信息处理的一种有效形式,强调并发属于一个或多个数据元素上的操作流程,解决一个问题。
定义10。并行算法是一家集同步交互的过程和协调达到给定问题的解决方案。
定义11。数据并行性意味着数据分为几个街区和映射到不同的处理器,分别。每个处理器运行相同的处理程序来处理分配数据。如果没有补充道,与并行相关的开销增加处理速度的功能<我>k次,和增加系统的吞吐量<我>k次了。
定义12。加速系数。 。 的执行时间与单处理器系统,使用一个系统执行所需的时间处理器,和加速度系数是一个标准来衡量系统的性能与多个处理器。
3所示。分治法的应用在属性约简方法
分治法的设计思想是将一个大问题,很难解决直接进入一些规模较小的相同的子问题,分而治之。生成的子问题各个击破的方法通常是较小的模型的原始问题,然后子问题减少到一个点,它很容易找到直接的解决方案。文献[22)提出了一个属性基于分治法的核心解决方案方法,实验证明了该算法的效率和处理大型数据集的适用性。
各个击破的方法找到的核心属性是基于该算法找到积极的领域。在域的划分,决策表分为 ,sub-decision-tables作为 ,它可以看到从定义5孩子的核心属性决策表必须的核心属性的一个子集父母决策表,但它并不一定是真正的子集;也就是说,它是不可能判断属性属于母公司的核心属性决策表,根据先前的核心属性的定义;如果删除该属性的相对积极的领域不同于不删除属性吗 ,然后属性是核心属性。因此,递归算法中找到积极的领域,我们应该首先判断属性核心属性,然后递归地找到积极的域的子域和核心属性。
4所示。基于分类的属性约简
分治法的核心属性是基于分治的思想和递归。虽然很难将递归没有递归程序设计,没有并发分治法的过程中,和很难实现并行属性约简。鉴于分治法的缺点,不能平行,我们改进了方法,设计了一个分类方法,支持并行性。
找到积极的领域分类的决策表实际上是一个过程;决策表中所有实例进行分类根据给定的属性设置,然后分类处理结果如下:每个类别中的所有情况下比较决策属性,如果都是相同的,那么类的实例被添加到积极的领域。如何快速分类决定了算法的性能,以及如何实现分类决定了速度快的算法性能。
4.1。基于分类找到积极的领域
让 是一个决策表, 和 ,如果决策表分类使用直接排序法,排序算法的时间复杂度是至少的 。分类算法在本文中,对每个属性域,我们使用索引方法遍历所有实例的属性值的属性,所以相对应的属性值可以处理所有实例时间,然后每个分类结果根据剩余的属性进行分类,直到最后一个条件属性。分类完成后,我们还需要处理决定每个分类的所有实例的属性。从积极的属性域,我们可以知道,在决策表的实例属性完全相同的条件,如果他们决定属性也相同,那么他们应该被纳入相对正域。接下来,我们给出了积极的地区收购算法基于分类算法1)。
|
||||||||||||||||||||||||||
的过程中发现积极的域的分类方法,考虑到时间和空间复杂性,使用一个预先分配的结构数组,它的大小 ,一个是用于存储分类将被分割,,另一个用于存储划分结果,,他们都是交替使用。同时,该数组是链接,这样的时间和空间复杂性大大降低。
4.2。找到核心属性分类
根据定义的核心属性,让 ,如果 是一个核心属性,那么不平等吗 是真的;也就是说,积极的域值的条件属性集删除属性相对于决策属性小于相对正域值时不删除,我们称之为条件属性的不能被忽略的 ,所以这是一个核心属性。
因此,在这个过程中找到的核心属性。我们首先需要找到所有属性的正域;的目的是防止不一致决策表中,然后找出积极的域命名为后删除属性反过来,最后我们可以验证是否属性是一个核心属性通过比较他们的大小。详细的算法如下所示(算法2)。
|
4.3。算法复杂性分析
在寻找的过程中积极的领域分类的基础上,为每个属性,我们使用索引方法遍历所有类别 ,和时间复杂度 。每个类别索引需要先初始化,初始化时间是复杂的 ,对于每一个类别,遍历类的实例,从实例的数量 ,时间复杂度是 ;因此算法的时间复杂度可以很容易地表示为 和也 ;因此,基于分类算法的时间复杂度 ,和空间的复杂性 。的分类方法寻找核心属性,每个属性都需要积极的领域,所以时间复杂度 ,和空间的复杂性 。
5。基于MPI的并行实现属性约简算法
5.1。并发性在属性约简
并行计算的核心是寻求并发性。我们改善传统串行的决策表属性约简算法和属性约简过程划分为三个部分:决策表的核心属性计算阶段,属性膨胀阶段和属性压缩阶段。这三个部分都需要反复计算的相对正域属性集,并计算相对正域的过程是相对独立的,所以他们都有很好的并发和并行算法可以实现。
虽然各个击破的方法将原始问题划分为小型独立解决问题,递归思想和动态分区不能通过并行算法实现,而分类算法计算每个属性的相对正域,他们是相互独立的,所以可以实现并行计算。属性扩张和属性压缩过程中决策表的属性设置的相对正域计算多次不管分治和分类,这部分可以实现并行计算。
5.2。平行的属性约简算法
根据属性约简过程中并发,下面的平行可获得的属性约简算法和具体实现算法所示3。为了平衡的数量属性之间的分配过程,每个过程是利用最大限度地根据抽屉原理,和我们把属性分配同样,这样的数量属性的不同分配每个进程不是一个以上的;即属性被分配在核心属性,属性扩展,和属性压缩阶段必须分配根据抽屉原理,保证最大化并发性。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
让是一个决策表,是一个条件属性集,决策属性集,是过程的数字,然后呢是进程的数量。
5.3。算法复杂性分析
平行的属性约简算法的时间复杂度,基于MPI并行进程的数量有关。在本文中,我们假定并行进程的数量 ;根据算法的并行处理过程,每个过程是首先分配属性,然后每个流程处理结果根据分配属性,,最后,每个进程的主要过程处理结果发送的主要过程。在属性分配阶段,如果属性的数量超过的数量处理流程,每个流程可分配属性,进行并行处理。如果属性的数量小于的数量处理过程,那么一些过程将不会分配属性。在极端情况下,算法的后期处理,处理属性的数量减少,当然会有一些过程,不能分配属性。此时,并行算法退化成为一个非平行算法。通过这种方式,并行属性约简算法的时间复杂度是显示为公式(2),公式,算法时间常数对并行程序消息传输所需的时间,这是有关网络环境和集群设置。
6。实验和结果
为了验证平行的属性约简算法的有效性,我们进行了多组对比实验测试。KDDCUP99数据集入侵检测数据24),共有4898432条记录,每条记录包含41个属性。我们随机选择20%的数据集,100万块数据进行测试。
测试分为两个阶段。第一阶段测试的非平行性能原始分治算法和基于分类属性约简算法,以及它们之间的差异。…我们首先随机选择10%,20%,100%,100万条记录来生成新的数据集。然后我们测试两种算法的性能在积极的领域,核心属性,属性约简在不同的数据集,通过比较分析得出结论。第二阶段的试验是测试两种算法的性能在并行环境中,并在第一阶段获得的数据集仍然是用于测试,然后两个算法的性能在积极的领域,核心属性,属性约简在不同的数据集进行测试,分别,通过比较分析得出结论。
实验通过使用MPICH.NT.1.2.5进行五台电脑和VS 2008开发工具在Windows环境。系统配置了Windows XP, CPU P4,主要频率为2.93 GHz, 1 g内存。
6.1。非平行测试
非平行测试主要是测试两种算法的性能并分析它们之间的性能差异的原因。根据前面的描述,数据的100万件选择率为10%。为了减少不必要的错误,这两个算法,分别在不同的数据集上运行5次,然后平均运行时间为这个数据集。表的运行时间1显示了属性约简的结果和运行时间不平行程序和图1是两个算法的时间比较。
它可以观察到从表1和图1当有100000块的数据,完成时间两种算法之间的差异非常小。不断增加的数据集,分治算法的性能逐渐比的分类算法。特别是当有900000数据集,分类算法完成时间的增加了近49.5%,分治算法。通过实验分析,分治法的算法性能高于非平行操作的分类。因此,各个击破的方法有更多的优势比分类不平行的环境。
6.2。并行测试
并行测试,为了保持一致性与非平行测试,非平行测试的数据仍在使用,和MPI通信协议用于在PC上运行相同的性能,并计算出的平均运行时间是在同一个测试5次。表2显示了属性约简的结果和并联运行环境中的运行时间,和图2显示了两种算法的时间分析图。最后,为了进一步比较两种算法的性能,比较图的两种算法在并行和环境不平行,如图3。
从表可以清楚地观察到2和图2在一个平行的操作环境,分类算法的性能优于各个击破的方法,及其平均运行时间减少了近30%相比,“分而治之”的方法。通过比较,可以发现,这两个算法的总体运行时间在并行环境中比非平行的环境。然而,它也可以在图中找到2基于分治算法,减少性能有下降的趋势;正如前面所讨论的,各个击破的方法不能用于平行时发现核心属性,独立和每个流程计算的核心属性,这是没有什么不同的非平行的方法。如果核心属性是减少的结果或接近减少的结果,这实际上并行算法降低了运营效率。然而,从图可以清楚地观察到2分类算法优于分治算法的属性约简在并行环境下,和分类并行算法的性能明显优于其他三种算法。这个结果证明了并行分类属性约简算法提出了时间效率方面有更多的优势。
7所示。结论
本文从提高粗糙集知识获取算法的效率,结合分治的思想,分类,和并行性,一个平行的提出了基于粗糙集的属性约简算法。通过改善各个击破的方法没有并行性,支持并行处理的分类方法在并行环境中可以大大提高处理属性约简的效率。实验结果表明,本文提出的算法更适合属性约简处理大规模数据集。
数据可用性
使用的数据来支持本研究的发现可以从相应的作者。
的利益冲突
作者宣称没有利益冲突。
确认
这部分工作是支持下的河南省科技重点项目批准号202102210370。