大数据下数据挖掘算法综述

时间:2022-12-07 10:19:43

大数据下数据挖掘算法综述

【摘要】在互联网发展的早期,虽然每天也会产生很多新的数据,但是数据量相对而言还可以用人力分析的方法来处理,并且对于固定的某个站点和角度去切入的话,所需要处理的数据量就更少了。随着互联网的飞速发展,每天产生的全新数据越来越多,并且呈指数态势上升,大量的数据中势必蕴含着大量有价值的信息,如果能抽取出这些信息,那么对于企业的发展和社会的发展都将大有裨益,在这个背景之下,很多数据挖掘处理方法应运而生。数据挖掘即使用计算机工具从海量的数据中挖掘出有价值的模式和规律,并用这些模式和规律去预测和指导未来的行为。在当今的互联网背景之下,最为常用的数据挖掘算法有频繁模式挖掘、聚类分析、决策树和贝叶斯网络等,本文将从若干方面入手,条理系统地介绍一下各类数据挖掘算法的原理、使用方法以及适用范围,力求为数据挖掘算法的应用提供一个良好的参考和指导。

【关键词】数据挖掘;频繁模式挖掘;聚类分析

1导论

1.1背景问题.当今互联网上90%以上的数据都是在两年内产生的,并且每天产生的数据量仍然在以巨大的速度上升,在这样的背景之下,对于海量的数据仅仅有接收和存储的能力是不够的,还需要对这些数据进行有效的处理,进而获取能指导未来行为的规律和模式,并提高企业、社会、组织和机构的效益以及效率。计算机处理数据的速度很快,但是从海量数据中挖掘规律并不是简单的操作,因此需要有行之有效的数据挖掘算法来完成在数据中“沙里淘金”的过程,因此各种数据挖掘算法也就应运而生了。1.2研究综述.在数据挖掘领域中,涌现了一大批各式各样的算法,其中应用最为广泛的是频繁模式挖掘、聚类分析、决策树和随机森林、贝叶斯网络这四类,其他算法很多是基于这四大类算法的改进和扩展。其中频繁模式挖掘的作用是从大量的数据(事务集)中获取某些项之间的相关模式,它可以用于指导项之间的关联分析。聚类分析的作用是对于大量的数据进行聚类操作,通过查看哪些数据聚拢在一起来对数据进行分类和相关分析。决策树是通过以数据中各个属性为分类依据将数据不算分类,最终构成一个树的形态,用于对数据进行分类判别处理;随机森林是使用多棵决策树同时进行判别和分类,最终投票选出结果。贝叶斯网络同样是一种分类算法,在已知“执因索果”的前提条件下,通过条件概率和贝叶斯概率公式,进行“执果索因”的操作,是贝叶斯公式的成功运用。1.3本文介绍.本文从频繁模式挖掘和聚类分析的角度出发,分别对这两个算法进行介绍和分析。每一部分算法都分为三个部分,分别是算法介绍、算法过程以及算法分析。算法介绍部分主要是关于算法的主要思想,算法过程部分介绍了算法具体模型和执行过程,在算法分析部分,本文从算法的优缺点和应用场景分别给出了解释和说明。

2频繁模式挖掘

2.1算法介绍.频繁模式挖掘的目的是在大量的数据中获取到频繁出现的模式,这些模式以规则的形式出现,即X→Y的形式,其中X和Y都是项集,即若干项组成的集合,这个规则表示的含义是“若项集X出现,则项集Y也可能会出现”,那么如果要度量这个规则是否可用,需要从两个方面入手,即这个规则足够常见以及这个规则足够可信。对于“足够常见”的度量,有一个度量指标叫做支持度,对于集合S来说,它的支持度表示为sup(s)={ti|S奂ti,ti奂T}T,其中T是全体数据,以事务集的形式给出(即若干原始项集构成的列表),ti是事务集中的一个事务(即一个原始项集)。一个集合的支持度越高,那么它就出现得越频繁。对于“足够可信”的度量,有一个度量指标叫置信度,对于规则X→Y而言,它的置信度表示为conf(X→Y)=sup(X∪Y)sup(X),即集合X∪Y的支持度与集合X的支持度的比值。对于一个合格有用的规则而言,它的支持度和置信度要同时满足一定的标准才可以被接受,因此对于频繁模式挖掘需要另外设置两个阈值,分别是最小支持度阈值min_sup和最小置信度阈值min_conf,只有指定的规则同时满足这两个阈值的情况下,才可以认为该规则是可以被接受的。对于具体的问题,最小支持度阈值和最小置信度阈值往往不同。2.2算法过程.对于频繁模式挖掘而言,算法的步骤一共分为两个大部分,即频繁模式的计算和频繁规则的计算,下边分别介绍这两个部分:2.2.1频繁模式的计算.频繁模式也叫频繁项集,即从给定的数据集中找到那些频繁出现的项集。频繁模式的计算方法很多,如Fk-1×F1、Fk-1×Fk-1和FPTree等,这里着重介绍Fk-1×F1方法,下边是计算过程:(1)首先计算所有的1-频繁项集,并放入1-频繁项集的集合中;(2)对于当前的轮次(初始值为1),求两个集合Fk的笛卡尔积,然后求出结果中所有的频繁项集,对于(k-频繁项集,放入其所属的集合中;(3)进入下一轮次,重复执行2)的操作;(4)如果某一轮中没有新的频繁项集产生,则算法终止。2.2.2频繁规则的计算.频繁规则的计算是要基于频繁模式的,简证如下:对于集合X1奂X,X2奂X,X1∩X2=覫,X1∪X2=X,X1≠覫,X2≠覫而言,所有可能的规则X1→X2的支持度都是X本身的支持度sup(X),因此如果直接求规则会产生大量重复的计算,并且如果X不是频繁项集,那么规则X1→X2肯定也不是我们需要的规则,因此欲求频繁规则,则应先求频繁模式,再由频繁模式导出规则。对于给定频繁项集X,从中导出规则的算法过程如下:(1)对于中的每一项,都构造出类似X-xi的规则形式,并挑选出其中的有效规则备用;(2)两两合并后件中只有一个元素不同的规则,然后形成一个新的规则,判断其是否是有效的,如果是,则仍然放入规则集合中,留待以后计算;(3)重复以上过程直到没有新的规则产生。2.3算法特点.对于频繁模式挖掘而言,它适合求取大量的数据中某些事务之间的关联,并且过程简洁明了,非常易于编写和修改扩展。但是同样地,频繁模式挖掘算法的理论时间复杂度是指数级的,虽然经过重重优化之后的实际表现不错,但是整体仍然需要进行大量的计算,因此当数据集特别大的时候,使用频繁模式挖掘很难迅速准确地得到期待的结果。

3聚类分析

3.1算法介绍.对于给定的数据,如果数据中的若干属性都可以量化,则能够把一个单个数据的n个属性当做坐标方向的偏移量,然后可以把这个数据映射到n维笛卡尔坐标系中的一个点,这样就可以把给定的大量数据转换成n维坐标系统的若干点,通过对这些点进行分析和处理,进而得到分类情况,最终可以得到数据之间的关联和分类情况。对于聚类分析算法而言,关键点是如何判定两个点之间在什么情况下应该被聚拢在一起(即聚类依据),根据聚类依据的不同,聚类分析算法中又可以延伸出若干不同的算法,如划分聚类、层次聚类、密度聚类、网格聚类、图聚类和谱聚类等等,这些聚类方法各有特点和使用场景,在这里我们主要选取划分聚类来介绍。3.2算法过程.在划分聚类中,最为著名的就是K-Means算法,即“K均值”算法。它的主要思想是将欧几里得距离作为聚类依据,将坐标系中的点聚拢成不同的分类,假设要将指定的数据分成k类,那么算法过程如下:(1)在给定的点集中随机选取K个点作为初始的聚类中心;(2)对于点集的每一个点,都计算其与K个聚类中心的距离,选取距离最近的那个聚类中心所在的簇作为当前点所属的簇;(3)聚类结束之后,重新对每一簇计算新的聚类中心,计算方法是求各个点的平均值;(4)如此迭代,知道聚类中心不再发生变化为止,此时即得到了K个簇。3.3算法特点.算法适合于数据各个属性易于量化和抽取的数据,并且有着明确的分类需求,而且事先制定了簇的数目。但是当没有确切的簇的数目被指定的时候,K-Means算法有时候并不一定会有很好的结果。

4结论

4.1本文结论.本文从数据挖掘的角度出发,在大数据的背景下梳理了常见的数据挖掘算法,并且给出了不同的数据挖掘算法各自不同的特点,给其他人提供了思路和借鉴。4.2研究展望.本文本次只从若干方法入手来分析,数据挖掘领域仍然有很多的算法未被梳理,之后本文将继续沿着这个方向梳理数据挖掘领域更多的算法。参考文献[1]郑伟.数据挖掘在人工智能上的应用实践.[2]王雷.基于大数据挖掘的国防交通建设研究.[3]葛俊言.数据挖掘技术的应用研究.[4]张佳.计算机数据挖掘技术及其应用探析.[5]罗之皓.知识图谱的Top-k摘要模式挖掘方法.[6]何镇宏.并行频繁项集挖掘算法研究.[7]柴变芳.基于主动学习先验的半监督Kmeans聚类算法.[8]金辉.自然最近邻优化的密度峰值聚类算法.[9]魏杰.基于K-means聚类算法改进算法的研究.

作者:郑州外国语学校 单位:郑州外国语学校