与粗糙集数据挖掘使用地图——减少

布勒帕蒂尔
我的学生(计算机),AISSMS COE,印度浦那

文摘

一个巨大的数据挖掘和知识发现展览的数据量的巨大的挑战以出乎意料的速度增长。不同的技术用于检索意义的数据。粗糙集是其中之一。这种方法是基于下近似、上近似。现有方法计算粗糙集近似以串行方式。因此,我们提出一个并行的方法。使用映射-规约模式开发了管理许多大规模计算。最近推出了使用映射-规约模式技术得到了考虑从科学界和工业界都在大数据的适用性分析。近似的有效计算改善粗糙集的性能是至关重要的一步。挖掘大量数据,并行计算模式,算法和不同的方法用于研究领域。在这篇文章中,我们解释了粗糙集并行计算方法。通过使用映射-规约模式我们可以达到同样的。 Because of map-reduce we can generate rules and abstract attributes of massive data.

关键字

大数据;使用映射-规约模式;粗糙集;

介绍

从最近几个十年,数据存储在数据库的规模一直在增加每一天,因此我们面临很多困难,获得有价值的数据。已经很难达到准确和有用的信息存储在数据库中的数据是成长每一天。找出规则或有趣的和有用的模式在数据库中存储数据,使用数据挖掘技术。存储大量的增加数据库中的数据,也就是信息爆炸,需要将这些数据转换成必要和有用的信息。使用传统的统计分析技术不能满足要求的数据。

数据挖掘是一个重要的过程,确定有效的,未知的和潜在的有用的和容易理解的依赖关系数据。随着信息技术的发展,数据量由许多应用程序将处理经常穿过peta-scale阈值,而这反过来会增加计算的要求。数据处理和知识发现[1]。大规模数据一直是一个热门话题数据挖掘中数据处理和大规模数据的知识发现总是数据挖掘中的一个热门话题。数据挖掘中最大的问题是缺乏和不定性。这个问题是解决了通过使用新的理论和程序,例如模糊集、遗传算法、粗糙集。

二世。相关工作

在[1]的作者提出了一种并行计算方法粗糙集近似。因此,算法的并行方法的基础上,提出使用映射-规约模式技术处理大量的数据。一个广泛的实验评估在不同的大型数据集显示提出的并行数据挖掘的方法是有效的。扩大数据在应用程序使算法基于粗糙集具有挑战性的任务。由于粗糙集近似的计算是必要的步骤,高效算法的发展成为一个重要的任务。作者解释了所需的所有算法使用映射-规约模式。在论文[2]中,作者解释了数据挖掘的目的对于大规模数据,并行计算模式和算法研究领域的典型方法。现在从大数据挖掘知识,他因此算法使用映射-规约模式基于大致对应理论。本文综合评价在大型数据集的表现表明,该证明可以有效地大数据的过程。作者解释了粗糙集和用例描述的历史[3]。 He also introduced a knowledge discovery paradigm for multi-attribute and multi-criteria decision support, based on the concept of rough sets. Rough set theory provides mathematical tools for dealing with granularity of information and possible inconsistencies in the description of objects. In paper [4], the mathematical principles of rough sets theory are explained and a sample application about rule discovery from a decision table by using different algorithms in rough sets theory is presented. In the document author described basic concepts of rough set and its advantage.

三世。粗糙集

粗糙集理论是一种强大的数学工具由pswlak z在1980年代初,已广泛应用于从数据库中提取知识[1]。通过使用数据中发现隐藏的模式识别部分和全部依赖项的数据。它还可以使用null或缺失值。在决策,它证实,粗糙集方法有一个强大的本质在处理不确定性。粗糙集可以单独使用,但通常它们是与其他方法如模糊集一起使用,统计方法、遗传算法等RST已经应用于多个领域包括图像处理、数据挖掘、模式识别、医学信息学、知识发现和专家系统。

基本粗糙集是依靠近似即上近似和下近似如下提到的计算之后。

一个¯·近似——低下近似包含所有数据基于属性没有任何歧义。

一个¯·上近似对象可能属于一组,不能被描述为不属于基于知识的属性集。

一个¯·边界地区这些上下近似定义之间的差异粗糙集的边界地区。

一组是脆,如果边界区域是空的。或一组是粗糙的,是否非空的边界地区。强调在粗糙集处理模糊性和不确定性决策。数据挖掘是一门学科,对数据分析有重要的贡献,新发现的有意义的知识,和自主决策。粗糙集理论提供了一个可行的方法从数据中提取决策规则。粗糙集理论(RST)采用数学建模类数据分类问题,然后变成了决策支持系统是一种非常有用的工具,尤其是在混合数据,模糊的概念和不确定数据参与决策过程[6]。

让T是决策表和T = (U) U是通用集和属性设置。如果B和X U近似X只使用B中包含的信息通过构造B-lower和B-upper近似(X)表示,分别

有许多应用程序相关的大量数据,如关联规则挖掘、序列模式挖掘、文本挖掘和时态数据挖掘的算法基于粗糙集理论。数据存储在数据库中迅速发展,除了数据的有效利用成为一个问题。因此数据挖掘技术用于发现规则或有趣的和有用的数据从存储模式。如果数据不完整或不准确,结果从数据库中提取数据发现阶段将不符和nonmeaningful。粗糙集理论是一种新的数学方法中使用的智能数据分析和数据挖掘,如果数据是不确定的或不完整的。[2]粗糙集在认知科学和人工智能,重视决策分析、专家系统和机器学习,归纳推理。

四。例如

如上面图所示,有两类属性(年龄、氨基酸)和一个决策属性(走)。我们可以从这个表生成规则使用粗糙集属性的价值。只有走“是的”或“不”。我们要通过考虑决策属性值计算近似‘是的’。

降低近似包含数据没有歧义。在我们的示例中对象x1, x4, x5价值‘是的’。我们不能添加x4的下近似集,因为对象x3相同类值作为x4。它形成歧义。因此,我们排除x4。在上近似的情况下,我们选择对象决定属性值“不”。我们发现对象x2, x3, x5和x7决定价值的“不”。但这集包含的对象与歧义。在我们的示例中x3 x4 class属性值一样但不同决策价值。这样我们可以添加上近似的对象类型。 As a result, lower approximation of our decision table is {x1, x6} and upper approximation is {x1, x3, x4, x6}. As the boundary region is difference between these two sets, it contains objects {x3, x4}. Here boundary region is non-empty, hence it is rough set.

诉使用映射-规约模式

使用映射-规约模式允许分布式处理的Map和Reduce函数。[2]使用映射-规约模式将输入文件划分为没有块的“输入分割”方法。它是用于处理数据在商品硬件。

第一步:输入读者:

它把输入转化成适当的大小分割即块和分配一个分裂每个地图的功能。输入读者从稳定的存储器读取数据并生成键/值对。

步骤2:映射器

这过程一个键/值对并生成另一个键/值对。许多这样的地图功能运行在并行跨集群分区的数据,产生一组中间键/值对。

步骤3:比较函数

输入每个减少从地图上跑的机器和存储使用应用程序比较函数。

步骤4:配分函数

给出的配分函数的关键和还原剂的数量并返回的索引所需的减少。重要的是要选择一个分区函数,给出了一个近似均匀分布的数据还原剂分配更多的数据负载均衡操作完成。

第五步:减速机

reduce函数合并所有中间值,与相同的中间键相关联。

第六步:输出

使用映射-规约模式允许开发人员编写和部署代码,直接运行在集群中的每个数据节点服务器。代码理解数据的格式存储在文件中的每个块,可以实现简单的算法和复杂得多。它可以用来处理大量数据的并联平行在大型集群可靠和容错的方式。因此,它的优点呈现Map / Reduce可用用户[2]。

粗糙集近似得到并行方法获得的相同的系列方法。但使用地图减少我们可以运行独立的阶段并行计算等价类,计算决策类,构造基于使用映射-规约模式的关联。因此时间非常少比传统的粗糙集方法计算。除此之外我们还可以生成大量数据的规则,并且能够抽象属性与粗糙集使用使用映射-规约模式以更有效的方式。

第六,提出了系统

现有计算方法粗糙集执行内存中处理。首先,这类计算等价类,然后决定。并在最后决定类的近似计算。现有方法计算粗糙集连续。它不能处理大型数据集。因此我们提出了并行方法执行的Hadoop平台可能删除数据大小限制由于透明的溢出。

数据分区、容错、执行调度由MapReduce框架本身提供。MapReduce是为了处理大量数据和巨大的集群(成千上万的服务器)。MapReduce是一种编程框架,该框架允许执行用户代码在一个大集群。所有用户必须写两个函数:Map和Reduce。在映射阶段,输入数据分布在映射器的机器,每台机器然后并行处理数据的一个子集,并产生一个或多个<关键;为每个数据记录值>对。接下来,在洗牌阶段,这些<键,值>对重新分区,每个分区内排序),这样值对应于相同的关键组成值{v1;v2;:::}。最后,在降低阶段,每个减速器机过程的一个子集<键,{v1; v2; :::}> pairs in parallel and writes the final results to the distributed file system. The map and reduce tasks are defined by the user while the shuffle is accomplished by the system.Even though the former pseudo code is written in terms of string inputs and outputs, conceptually the map and reduce functions supplied by the user have associated types.

地图(k1, v1)→列表(k2 v2)

减少(k2,列表(v2)→列表(v2)

两个程序员指定的功能:

•地图

输入:键/值对(k1, v1)

输出:中间键/值对列表(k2, v2)

•减少

输入:中间键/值对(k2,列表(v2))

输出:列表的值列表(v2)

即输入键和值都来自一个不同的领域比输出键和值。k1, k2是两个不同的密钥用于MapReduce阶段和一样v1, v2是不同的值。中间键和值都来自同一个域作为输出键和值。

提出系统我们可以计算粗糙集的等价类和决策类并行使用theMap-Reduce技术。等价类之间的关联和决策类的决策表也可以并行执行。上下近似计算等价类和决策类之间的关联。然而,如果我们直接计算近似,内存可能溢出因为等价类和决策类都包含太多的对象在处理大型数据集。因此我们可以计算粗糙集近似的指标即为每个决策类的集合信息。计算近似的指标后,我们直接输出近似。图的并行计算方法粗糙集近似如下所示。

他获得的粗糙集近似平行的方法获得的相同的系列方法。但使用地图减少我们可以运行独立的阶段并行计算等价类,计算决策类,构造基于使用映射-规约模式的关联。因此时间非常少比传统的粗糙集方法计算。除此之外我们还可以生成大量数据的规则,并且能够抽象属性与粗糙集使用使用映射-规约模式以更有效的方式。

使用映射-规约模式框架提供了干净的抽象数据分析任务和底层之间参与确保可靠的大规模计算系统的挑战。使用映射-规约模式运行时系统可以透明地探索并行性和进度组件分配资源来执行。

七世。特性提出系统的减

我们可以测量的性能提出了系统使用三个特点如下所述。

•加快:

来测量加速,我们保持数据集不变,增加节点的数目(计算机)系统。加速的大系统由下列公式定义[8]:

加速(p) = T1 / Tp;

p是节点的数目(电脑),T1是一个节点的执行时间,Tp p节点上的执行时间。我们可以对数据集执行加速评价截然不同的大小和结构。(电脑)变化从一个节点的数目。在串行现有系统p乘以产量的计算机数量的加速p。然而,线性加速是很难实现的,因为沟通成本增加集群的数量变得很大。

•规模:

扩大的能力被定义为p乘以较大系统执行p乘以较大的工作在相同的执行时间[8]。

扩大(D, p) = TD1 /计划书

D是数据集,TD1 D在一个节点上执行时间,计划书的执行时间是在p p×D节点。检查是否该系统处理更大的数据集,当更多的节点。因此,我们可以执行扩大实验,我们可以增加数据集的大小成正比系统中节点的数目。

•尺寸:

大小被定义为以下公式[8]:

大小(D, p) = TSp /壹空间

TSp是p×D的执行时间,壹空间的执行时间是D。尺寸分析的计算机数量在系统常数,和成长的数据集的大小通过因子p。大小措施需要多久一个给定的系统,当数据集的大小是p乘以大于原来的数据集。

第七章结论

到目前为止,许多基于粗糙集算法为数据挖掘开发。但扩大数据在应用这些算法基于粗糙集具有挑战性的任务。粗糙集近似的计算是非常重要的一步。我们可以提高质量和速度的计算近似。这是一个方法,我们有很多的机会来实现速度和准确度。

在本文中,我们提出了一个并行的粗糙集方法。通过使用映射-规约模式我们可以达到同样的。因为使用映射-规约模式我们可以生成规则和抽象属性的大规模数据。未来的工作将包括并行频繁模式挖掘探索的另一种方法计算属性空间,这与大量的信息系统属性,如用于数学,可以有效地分析。

引用

Junbo张,天瑞李•阮ZizheGao, ChengbingZhaoa,并行计算方法粗糙集近似的,j . Zhang et al。/信息科学194 (2012)209 - 223
一个。Pradeepa1安东尼SelvadossThanamaniLee2博士,hadoop文件系统和基本概念的Mapreduce内部和关闭粗糙集近似的,国际先进的研究在计算机和通信EngineeringVol杂志》上。2,问题10,2013年10月
基于粗糙集的决策支持的罗马Slowinski研究所计算机科学技术与系统研究所波兰波兹南大学科学院华沙,波兰
Esenler MertBaMathematical工程部,Yildiz技术大学一个°stanbul,土耳其的粗糙集理论作为象征性的数据挖掘方法:应用程序完整的决策表的
MehranRiki,哈桑雷大学锡斯坦和Baluchestan扎黑丹、伊朗数学系,粗糙集理论的介绍和应用在数据分析。
阿格涅斯卡诺瓦克——Brzezinska粗糙集理论的决策支持系统
x, j .贼鸥,惠普Kriegel”大型空间数据库的快速并行聚类算法,数据挖掘和知识发现”(1999)263 - 290.10.1023 /:1009884809343