频繁子图挖掘研究综述_鲁慧民
26卷 第3期2009年3月
微电子学与计算机
M IC ROELECTRONICS &COM PUTER
Vol .26 No .3M arch 2009
收稿日期:2008-05-30
基金项目:国家“八六三”计划项目(2008AA 01Z 131)
频繁子图挖掘研究综述
鲁慧民,冯博琴,宋擒豹
(西安交通大学电子与信息工程学院,陕西西安710049)
摘 要:归纳了频繁子图挖掘方法的处理流程,分析评价了频繁子图挖掘的典型算法:广度优先搜索和深度优先搜索的频繁子图挖掘算法,概述了频繁子图挖掘研究的平台———图模型及其产生器,并对频繁子图挖掘方法未来研究方向进行了展望.
关键词:子图同构;频繁子图挖掘;图模型;图产生器
中图分类号:T P391 文献标识码:A 文章编号:1000-7180(2009)03-0156-06
Survey of Frequent Subgraph Mining Research
LU Hui -min ,FENG Bo -qin ,SONG Qin -bao
(School of Electronic and Information Engineering ,Xi ′an Jiaotong U niversity ,Xi ′an 710049,China )
A bstract :T he process of Frequent Subgr aph M ining is summarized in this paper .Broad First Search (BFS ),Depth First Search (DF S ),w hich are the typical mining algo rithms are analyzed and evaluated .T he g raph model and its generator ,w hich is the impo rtant research platform of frequent subg raph mining are introduced .O pen issues and fur ther research di -rections are also discussed .
Key words :subg raph isomorphism ;frequent subg raph mining ;graph pa ttern ;g raph g enerator
1 引言
频繁子图挖掘与相对比较成熟的文本型频繁项
挖掘相比,图的数据量大,结构复杂,对原始的图数据进行频繁子图挖掘难度较大.同时通过边或节点添加生成的候选子图集中往往存在大量的冗余,子图同构的NP 问题等都增加了候选子图支持度计算的复杂性,因此一般的文本数据挖掘方法不再适用于频繁子图挖掘,必须结合图数据格式的特点寻求新的挖掘算法.
Akihiro 等人在2002年首先将Aprio ri 算法思想应用到频繁子图挖掘中,此后各种基于Aprio ri 思想,采用递归的方法来发现频繁子图的挖掘算法相继出现,主要包括AGM 、AcGM 、FSG 等.后来韩家炜等人将FP -grow th 思想应用到频繁子图挖掘中,使图挖掘得到了迅速的发展,主要包括gSpan 、CloseGraph 和FFSM 等,它们主要通过逐渐扩展频
繁边得到频繁子图,但对边的扩展过程略有不同.此
外还出现了一些其它的频繁子图挖掘算法,例如Wang 等于2005年提出了一种基于索引的频繁子图挖掘算法GraphMiner [1];2007年Zhu 等提出一种基于用户约束条件的频繁子图挖掘算法gPrune [2]
,Karste 等提出了适用于动态图挖掘的
Dynamic G REW 算法[3]
等.
作为图挖掘研究的重点,频繁子图挖掘算法得到了广泛深入的研究,文中总结归纳了频繁子图挖掘的处理流程,对典型的频繁子图挖掘算法进行了分析评价,同时介绍了研究频繁子图挖掘的平台———图模型及其产生器,并展望了频繁子图挖掘的未来研究方向.
2 频繁子图挖掘的处理流程
频繁子图挖掘即从输入数据库中挖掘出所有的频繁子图.
(1)频繁子图挖掘的基本概念设是频繁子图,则公式如下:S f rek ={K |∑n
i =1X ik ≥m }
(1)
式中,X i k ∈{0,1},如果子图K 与图数据库中G i 子图同构,则X i k =1,否则X ik =0;m 是最小支持度.
(2)频繁子图挖掘算法的处理流程
频繁子图挖掘算法的基本步骤主要包括图标识、图数据库数据的简化、侯选子图的生成、侯选子图的剪枝、支持度计算等.处理流程如图1所示
.
图1 频繁子图挖掘的处理流程
首先对图进行唯一标识以避免子图同构问题,对图数据进行简化,删除非频繁边或顶点.利用频繁子图挖掘算法挖掘候选子图,对其中的冗余子图进行剪切,计算候选子图的支持度,选择大于最小支持度的候选子图形成频繁子图集.
3 频繁子图挖掘算法
频繁子图挖掘算法按子图挖掘搜索路径分为广度优先搜索算法(Broad First Search ,BFS )和深度
优先搜索算法(Depth First Search ,DFS )[4]
.广度优先搜索算法基于Aprio ri 思想实现,主要包括AGM 、AcGM 、FSG 等,深度优先搜索算法基于FP -g row th 思想实现,主要包括g Span 、CloseGraph 和FFSM 等.
3.1 广度优先搜索算法
AGM 算法是最早采用Apriori 思想的广度优先搜索算法,它采用邻接矩阵来表示图,根据邻接矩阵生成图编码,取其中的最小编码作为图的唯一标识,以解决子图同构的NP 问题.以频繁顶点作为初始
集,利用Apriori 性质(一个项集是频集当且仅当它的所有子集都是频集),采用递归方法挖掘频繁子
图.AGM 算法思想比较简单,但其存在明显的缺
点:首先由频繁k -1-子图集进行自连接生成的候选频繁子图k -项集数量巨大,其次在验证候选频繁子图k -项集的时候需要对整个数据库进行扫描,非常耗时,因此不少研究者提出了改进算法:
(1)基于划分的方法
这种算法先把图数据库分成几个互不相交的单元,每次单独考虑一个单元并对它生成所有的频繁子图,然后把产生的频繁子图进行无损合并,用来生成所有可能的频繁子图集,最后计算这些子图集的支持度.Wang 等在2006年引入了一种基于划分的图挖掘方法PartMiner .该算法首先反复调用图划分算法将数据库中的每一个图划分成更小的子图,将其分组到单元,其次利用现有的基于内存的频繁子图挖掘算法发现每个单元的频繁子图集,通过合并连接操作将每个单元的频繁子图合并,重新得到整个图的频繁子集.
(2)基于采样的方法
先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则,然后对数据库的剩余部分验证这个结果.在图理论研究中,采样往往用来对图进行压缩,便于存储.2005年K rishnamurthy
等提出了一种基于选择随机节点方法[5]
,抽样大小
为源图的30%,此外还有通过随机边的选择来进行抽样的方法.Leskovec 和Faloutsos 在2006年提出了大图(Large Graph )的抽样方法:对静态图的抽样采用“随机行走(random w alks )”方法或类似病毒繁殖的方法选择具有代表性的节点,构建与源图拥有一致特征的抽样图.针对动态图则采用“森林火(Fo rest Fire )”方法进行采样.通过对大图的抽样,然后对其进行频繁子图的挖掘,可以大大减少候选频繁子集的数量,使大图的挖掘成为可能.
(3)基于减少源图数量的方法
减少用于未来扫描的图集的大小.一个基本原理就是当一个图不包含k 频繁子图,则必然不包含k +1的频繁子图集,从而可以将这些图移除,这样在下一遍的扫描中就可以减少要进行扫描的图集的个数.
(4)基于边扩展与约束限制的方法———FSG 与AcGM 算法
Kuramochi 和Kary pis 在2001年提出了一种基于扩展边来高效生成候选子图的算法FSG ,是对
157
第3期鲁慧民,等:频繁子图挖掘研究综述
AGM算法的改进,在候选子图的剪枝策略和计算频繁支持度方面进行了优化.2002年Inokuchi等提出了一种利用限制性条件生成诱导子图作为候选子图,对AGM进行性能改进的方法AcGM,其执行效率比AGM和FSG都高.此外马海兵等于2006年提出一种高效挖掘无序频繁子树的算法,利用最右路径扩展方法构造完整的模式增长空间,然后根据待增长模式的拓扑结构确定其增长点并构造相应投影库,从而挖掘出频繁子树.
3.2 深度优先搜索算法
Han等人在2002年针对类Apriori算法(如FSG、AGM、AcGM)连接和剪枝耗时很大的缺点,提出基于深度优先搜索的gSpan算法.gSpan算法是一种基于FP-grow th思想的频繁子图挖掘算法,其基本思想是利用最小DFS码对图进行唯一标识,以简化子图同构问题.利用最小DFS码作为空间树的一个节点进行最右路径扩展形成k-频繁子图,每次添加一条边,形成k+1-频繁子图,如果k+1 -频繁子图不是最小DFS码形式,则作为冗余删除掉.在支持度的计算上采用对k-频繁子图的事件(Occurrence)进行记录,k+1-频繁子图的支持度可以通过对k-频繁子图的所有Occurrence进行最右扩展得到.其核心算法如下[6]:
Subgraph-M ining(G S,S,s)
1.if s!=min(s)
2.return;
3.S→S∪{s};
4.g enerate all s'potential children with one edge g rowth;
5.Enumerate(s);
6.for each c,c is s'child do
7.If support≥min sup
8.s→c
9.Subgraph-M ining(G S,S,s);
g Span算法对于大型数据库而言效率仍然很低.Yan和Han于2003年提出一种改进的CloseG-raph算法,主要是对频繁闭子图进行挖掘.CloseG-raph的算法思想与gSpan一致,只是在对候选子集进行剪枝的时候采用定理来判断是否进行最右路径扩展.gSpan算法和CloseGraph算法相对于Apriori 算法,它们通过引入新的方法和概念———DFS词典顺序(DFS lex icog raphic Order)、最小DFS码和最右扩展使得无需按Aprio ri算法的思想,而是直接生成频繁子图,大大提高了算法的效率.但gSpan算法和CloseGraph算法在挖掘结果集中考虑了图的标记,即具有不同标记的图被认为是不同的图.而很多情况下,标记不同的图具有相同的结构.为了解决“标记不同但结构相同的图被认为是不同的”的问题, 2005年重庆大学的康艳荣在论文中提出了两种新的算法[7]———极大完全子图挖掘算法(M ax-codeFMCG算法)和频繁子图结构挖掘算法(FSA算法),并将M axcodeFMCG算法与已有的频繁模式挖掘算法FP-Grow th算法相结合,产生一种基于图结构的频繁模式挖掘算法(M axcodeFP-Tree算法).该算法的主要优点是解决了FP-Grow th算法中存在的内存不足的问题,FSA算法则解决了以往的频繁子图挖掘算法中存在的“标记不同但结构相同的图被认为是不同的”的问题,有利于对结构挖掘进行更深入的研究.
此外,2003年Huan等提出了FFSM算法,将图的标准形状变为树结构,并提出了树的一系列操作.首先该算法将图转化为标准的邻接矩阵表示,将子图的同构问题转化为矩阵的操作,图的扩展也转化为对矩阵的连接操作与矩阵的扩展操作.依据给定的参数首先通过枚举找到所有的近似频繁边,并移除在数据库中的非频繁边,接着用深度优先发现所有的最大近似频繁树,这可以通过递归增加一个新节点到已经存在的近似频繁树,直到候选树不再是近似频繁树或在前面已经存在该近似频繁树.FF-SM通过标准码来唯一标识图,避免了子图同构的问题,为每一频繁子图设计一个嵌入集合(Em bed-ding Set).在进行支持度计算时,只扫描嵌入集合即可避免重复扫描数据库,提高了计算支持度的速度和效率,但该算法中的FFSM-Join产生的候选具有不完整性,必须通过FFSM-Ex tension进一步产生候选子图,以保证挖掘结果的完整性.
3.3 其它频繁子图挖掘算法
除以上频繁子图挖掘算法以外,还有基于索引、用户约束、动态图的挖掘算法,以及为提高挖掘效率的并行挖掘处理等.
(1)基于索引的算法
Wang等于2005年提出一种基于索引的算法GraphMiner,用来挖掘频繁子图,利用高效的索引结构AID(Adjacency Index)从大图中挖掘频繁子图. AID索引一般有三层结构:边名表、连接的图编号列表、临近信息.三层结构的AID可以装入内存.一旦建立AID,那么在挖掘过程中,仅用索引来进行挖掘,不再访问源数据库.
(2)基于并行多处理器算法
2006年,Gregory等提出一种适合并行的图挖
158微电子学与计算机2009年
掘管理系统,用尽量少的内存但运行时间却得到改良,还为并行图挖掘设计了任务划分和包系统.任务划分与分配的目的是保证负载均衡,使每一个处理机都能高效率的工作直到挖掘任务完成.动态任务分配允许运行时进行任务分配,给予空闲的处理器额外负载.
(3)基于用户约束的挖掘算法
频繁子图的挖掘在有些算法中忽略了它的目的性,即有些算法针对的是所有的频繁子图的挖掘而往往没有与用户的具体要求结合起来,在实际应用中往往在挖掘时要加以条件限制,一方面可以减少候选频繁子图的数量,提高算法的效率,另一方面可以更清楚的发现与用户要求相联系的内容.2007年
Zhu等人提出了一种基于用户约束条件的图挖掘算法gPrune.
(4)基于动态图的挖掘算法
多种频繁子图挖掘算法都是针对静态图挖掘的,不适用于动态图挖掘.Karsten等提出了对动态图进行挖掘的算法,并对动态图进行了定义,将图数据的动态变化分为两种.一种是所有的数据同步变化,另一种数据的变化是不同步的.他们对Grew[8]进行扩展,使其适用于动态图挖掘,提出Dynamic Grew算法.
此外,针对大图的频繁子图挖掘,Kuramochi和Karypis于2004年提出了HSIGRAM和VSIGRAM 两种算法,该算法除了考虑子图同构问题外还考虑了同一个图的不同子图同构间的交迭(Overlap)问题,是对大图中所有频繁子图进行挖掘比较有效的方法.2004年Huan等人提出了一种基于挖掘最大频繁子图的算法SPIN,首先挖掘出源图数据所有的频繁树,然后再从挖掘出的频繁树挖掘最大频繁子图.该算法除了可以大大减少输出频繁子图的数目,还在很大程度上提高了挖掘速度.
4 图模型及其产生器
4.1 图模型
频繁子图挖掘算法研究基于一定的图模型,因此需要有产生与自然界中的图特性相一致的抽象模型,图模型是进行图挖掘理论研究的基础,将现实世界中各种各样的图抽象出来归纳总结为图模型,便于分析和研究,也有利于在各领域实现研究思路和方法的统一.图模型可以帮助模拟研究现实中的图,将现实中的大图缩小成与其相匹配的小图便于研
究、分析和计算.但要将现实中千差万别的图抽象成统一的图模型却比较困难,图模型的研究主要集中在有规律图形上,主要有幂指数规律(Power Laws)、小直径(Small Diameters)和社区效应(Community Effects)三种[9].此外2000年Broder等人将WWW 的图模型描述为蝶状(a bow tie)结构[10],如图2所示.将Web划分为SCC(Strong ly Connected Compo-nent)、IN、OUT、TENDRI LS四部分.Tauro等人在2001年提出Internet的水母(Jelly fish)结构图模型[11],由核心(Core)、层(Layers)、悬垂节点(Hang-ing Nodes)三部分构成,如图3所示.
图2 WWW的蝶状结构
图3 Internet的水母结构
4.2 图产生器
图产生器产生与自然界图匹配的图模型,为频繁子图挖掘算法的研究提供平台.根据生成图的模型不同,图产生器目前主要分五类:随机模式、择优连接模式、基于最优化模式、地理模式、特殊的In-ternet模式.
(1)随机模式.Erd?s和R′enyi早在1960年就提出随机图产生器[12],由用户提供一定数目的节点N,在每一对不同的节点间按一定概率p添加边.随机模式产生的图只能匹配度分布而不能匹配其它图模型.
(2)择优连接模式.1999年Kleinberg等提出一种与择优连接模式很相似的边拷贝方法[13],主要适用一些聚类性强的图,例如在基于主题的WWW的Web站点,在加入新节点时,它拷贝了已存在的与它具有相似性的节点的边.Winick等在2002年采用“Rich Getting Richer”原则[14],即每次加入一个新节点都要优先连接到已经存在的度高(Hig h De-
159
第3期鲁慧民,等:频繁子图挖掘研究综述
g ree )的节点上.择优连接模式只通过几个简单的步骤即可使产生的图符合幂指数分布,且较低的直径和很好的恢复能力,是目前最流行的模式,但是它没有聚类效果.
(3)基于最优化模式.1999年Carlson 和Doyle 提出HOT (Highly Optimized Tolerance )图产生器[15]
,HOT 能匹配幂指数规律并具有很强的恢复能力,它是考虑资源和效益两者折中的平衡方案,与现实世界中的好多受资源约束的图相符合,但它不能通过适当的参数值修改匹配实际图的特性.
(4)地理模式.有的图模式结构受到地理位置的约束,例如Internet 中地理位置比较靠近的两个路由器之间的连接就很容易,这种图产生器主要有小世界模型(Sm all -World Model )和Waxman 模型(Waxm an Model )两种,如图4、图5所示.Small -World M odel 是在1998年由Watts 和Strogatz 提出的[16],节点安排在一个规则圆形的格子上,每个节点直接与它相邻的节点连接,用实线表示,某些距离远的节点用虚线连接.产生的图具有低直径、高聚类的特点,但不匹配幂指数规则.The Waxman Mod -el [17]是Wax man 在1998年提出的一种按节点间距离概率连接各节点的模型,通常随着距离的增大概率减小,新增加的节点连接到已经存在的距离近的节点.但它也不匹配节点度的幂指数分布,这种简单的思想在2000年被Medina 等应用到BRITE 图产生器来产生网络聚类
.
图4 小世界模型 图5 Waxman 模型
(5)特殊的Internet 模式.2002年Winick 和
Jamin 发展了Internet 图产生器,但是仅匹配互联网自治系统(Internet Autonomous System ,IAS )拓扑中的几个特殊的特征,后来采用择优机制对其进行了改进.
5 频繁子图挖掘研究展望
目前频繁子图挖掘各个方面的研究都取得了很大的成绩,并应用到一些实际的系统中,取得了很好的效果,但对于频繁子图挖掘还有许多方面尚需进
一步深入研究.
(1)图模型.需要进一步研究新的图模型,以尽量多的匹配现实中的图结构,语义网图模型的构建是一个重要的研究方向.
(2)图产生器.要求尽量匹配多的图模型,通过适当的参数值修改来匹配实际图的特性.(3)频繁子图挖掘算法方面.子图同构问题需要进一步研究;候选子图的冗余问题需要进一步解决;对大图的挖掘算法研究还比较少;对不精确的频繁子图、概念频繁子图、加权频繁子图等的挖掘的研究;对优化挖掘算法,减少时间空间的复杂度,采用并行、分布式技术处理也是一个很重要的研究方向;挖掘结果如何实现可视化的研究等.参考文献:
[1]Wang W ,Wang C ,Zhu Y .GraphM iner :a structural pat -tern -mining system for large disk -based graph databases and its application [C ]//P ro ceedings o f the 2005ACM SIG M OD I nterna tio nal Co nference on M anagement of Da -ta .Baltimore ,M ary land :2005:879-881.
[2]Zhu F ,Yan X ,Han J .gP rune :a co nstraint pushing
framewo rk fo r g raph pattern mining [C ]//P roceedings of 2007Pacific -Asia Conference o n Knowledge Discovery and Da ta Mining (PAK DD '07).China :N anjing ,2007:388-400.
[3]K arsten M ,Hans -Peter K ,Pe ter W .Pattern mining in
frequent dy namic subg raphs [C ]//Proceedings o f the 6th Inter national Co nference on Data M ining (ICDM '06).HongKo ng :2006:818-822.
[4]李先通,李建中,高宏.一种高效频繁子图挖掘算法
[J ].软件学报,2007,18(10):2469-2480.
[5]K rishnamurthy V ,F aloutsos M ,Chrobak M ,et al .Re -ducing large internet topologies for faster simulatio ns [C ]//Networ king 2005.Canada :Ontario ,2005:328-341.[6]王艳辉,吴斌,王柏.频繁子图挖掘算法综述[J ].计算
机科学,2005,32(10):193-197.
[7]康艳荣.基于图结构挖掘算法的研究与应用[D ].重庆:
重庆大学,2005.
[8]K uramochi M ,K ary pis G .Grew -a scalable frequent sub -g raph disco very algo rithm [C ]//The 4th I EEE Interna -tio nal Co nference on Data M ining .UK :Brighton ,2004:439-442.
[9]Chakrabar ti D ,Faloutsos C .Graph mining :laws ,genera -tor s ,and algorithms [J ].A CM Computing Surveys ,2006,38(2):1-69.
[10]A ndrei B ,Ravi K ,F arzin M .G raph structure in the
web :ex periments and models [C ]//9th World Wide Web
160
微电子学与计算机2009年
Conference.New York,2000:309-320.
[11]T auro S,Palmer C,Sig anos G.A simple co nceptual
model for the internet topolog y[C]//Global Teleco mmuni-cations Conference,2001(G LOBECOM′01).U SA,
I EEE,T exas.2001:1667-1671.
[12]Erd?s P,Rényi A.O n the evolution of random graphs
[J].Publication of the M athema tical Institute of the Hun-garian A cademy of Science,1960(5):17-61.
[13]K leinberg M,K umar R,Raghav an P.T he web as a
g raph:measurements,models and methods[C]//I nterna-
tional Computing and Combinatorics Co nference.Berlin,
Springer,1999.
[14]Pennock D,Flake G,Lawrence S.Winners don't take
all:characterizing the competition for links o n the web[J].
N ational A cademy of Sciences,2002,99(8):5207-
5211.
[15]Carlson J,Doyle J.Highly optimized tolerance:a mecha-
nism for power laws in designed sy stems[J].P hysical Rev,
1999,60(2):1412-1427.
[16]W atts D,Strogatz H.Collective dynamics of`small-
world'networks[J].Na ture,1998(393):440-442. [17]Wax man B.Routing of multipoint connectio ns[J].
IEEE.Select.A reas Comm,1988(6):1617-1622.
作者简介:
鲁慧民 女,博士研究生.研究方向为数据挖掘、知识管理.冯博琴 男,博士生导师,教授.研究方向为数据挖掘、智能网络.
宋擒豹 男,博士,教授,博士生导师.研究方向为数据挖掘、知识工程.
(上接第155页)
存在的故障有一个准确的定位,集中精力排除主要故障.在电子设备等某些特殊机械设备的使用过程中,底事件的故障概率相当大.对于设备的故障概率进行近似计算,可以按照故障树建树原则,在正确建树的基础上,利用最优权因子[6]进行近似计算,以达到减小近似计算误差的目的.
参考文献:
[1]王国亮,孙新利.故障树法在弹头遥测可靠性分析中的
应用[J].战术导弹技术,2005(5):21-23.
[2]韩小涛,尹项根,张哲.故障树分析法在变电站通信系统
可靠性分析中的应用[J].电网技术,2004(1):56-69.[3]绍延峰,薛红军.故障树分析法在系统故障诊断中的应
用[J].中国制造业信息化,2007(1):72-74.
[4]潘吉安.可靠性维修性可用性评估手册[M].北京:国
防工业出版社,1995.
[5]周璧华,陈彬,石立华.电磁脉冲及其工程防护[M].北
京:国防工业出版社,2003.
[6]孙东平,姚依.故障树分析法及其在导弹故障近似计算
中的应用[J].装备环境工程,2006(4):64-67.
作者简介:
高 晶 女,(1983-),硕士研究生.研究方向为指挥自动化.
161
第3期鲁慧民,等:频繁子图挖掘研究综述
数据挖掘研究现状综述
数据挖掘 引言 数据挖掘是一门交叉学科，涉及到了机器学习、模式识别、归纳推理、统计学、数据库、高性能计算等多个领域。 所谓的数据挖掘（Data Mining）指的就是从大量的、模糊的、不完全的、随机的数据集合中提取人们感兴趣的知识和信息，提取的对象一般都是人们无法直观的从数据中得出但又有潜在作用的信息。从本质上来说，数据挖掘是在对数据全面了解认识的基础之上进行的一次升华，是对数据的抽象和概括。如果把数据比作矿产资源，那么数据挖掘就是从矿产中提取矿石的过程。与经过数据挖掘之后的数据信息相比，原始的数据信息可以是结构化的，数据库中的数据，也可以是半结构化的，如文本、图像数据。从原始数据中发现知识的方法可以是数学方法也可以是演绎、归纳法。被发现的知识可以用来进行信息管理、查询优化、决策支持等。而数据挖掘是对这一过程的一个综合性应用。
目录 引言 (1) 第一章绪论 (3) 1.1 数据挖掘技术的任务 (3) 1.2 数据挖掘技术的研究现状及发展方向 (3) 第二章数据挖掘理论与相关技术 (5) 2.1数据挖掘的基本流程 (5) 2.2.1 关联规则挖掘 (6) 2.2.2 .Apriori算法：使用候选项集找频繁项集 (7) 2.2.3 .FP-树频集算法 (7) 2.2.4.基于划分的算法 (7) 2.3 聚类分析 (7) 2.3.1 聚类算法的任务 (7) 2.3.3 COBWEB算法 (9) 2.3.4模糊聚类算法 (9) 2.3.5 聚类分析的应用 (10) 第三章数据分析 (11) 第四章结论与心得 (14) 4.1 结果分析 (14) 4.2 问题分析 (14) 4.2.1数据挖掘面临的问题 (14) 4.2.2 实验心得及实验过程中遇到的问题分析 (14) 参考文献 (14)
频繁项集挖掘的Apriori改进算法研究
１０００－５８６２（２０１１）０５－０４９８－０５ 频繁项集挖掘的Ａｐｒｉｏｒｉ改进算法研究 栗晓聪滕少华 广东工业大学计算机学院，广东广州５１０００６ 摘要：针对Ａｐｒｉｏｒｉ算法的不足，提出了一种新的优化算法—ＩＡｐｒｉｏｒｉ．该算法应用散列技术优化产生频繁－２项集，优化连接操作减少连接判断的次数，通过对候选项集编码来减少扫描数据库的次数，优化逻辑“与”运算减少不必要的“与”操作次数，缩短生成频繁项集的时间．ＩＡｐｒｉｏｒｉ算法仅需３次扫描数据库．研究结果表明，该算法具有快速、直观、节省内存等优点． Ａｐｒｉｏｒｉ算法；频繁项集；候选项集；ＩＡｐｒｉｏｒｉ算法 ＴＰ３１１Ａ ２０１１－０７－１２ 广东省自然科学基金（０６０２１４８４， ９１５１００９００１０００００７）和广州市越秀区科技计划（２００７－ＧＸ－０２３）资助项目． 滕少华（１９６２－），男，江西南昌人，教授，博士，主要从事协同工作、网络安全和数据挖掘方面的研究．
第５期
２０１１年
第５期
＠＠［１］王琳，滕少华，伍乃骐，等．基于协议分析的散列模式入侵检 测方法［Ｊ］．计算机工程与设计，２００６，２７（１）： ５３－５５．＠＠［２］颜跃进，李舟军，陈火旺，等．基于ＦＰ－Ｔｒｅｅ有效挖掘最大频 繁项集［Ｊ］．软件学报，２００５，１６（２）： ２１５－２２２． ＠＠［３］郭宇红，童云海，唐世渭，等．基于ＦＰ－Ｔｒｅｅ的反向频繁项集 挖掘［Ｊ］．软件学报，２００８，１９（２）： ３３８－３５０． ＠＠［４］ Ｈａｎ Ｊｉａｗｅｉ， Ｐｅｉ Ｊｉａｎ， Ｙｉｎ Ｙｉｗｅｎ， ｅｔ ａｌ． Ｍｉｎｉｎｇ ｆｒｅｑｕｅｎｔ ｍａｔｔｅｒｎｓ ｗｉｔｈｏｕｔ ｃａｎｄｉｄａｔｅ ｇｅｎｅｒａｔｉｏｎ ［Ｊ］． Ｄａｔａ Ｍｉｎｎｉｎｇ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒ， ２００４， ８（１）： ５３－８７． ＠＠［５］Ｊｉａｗｅｉ Ｈａｎ，Ｍｉｃｈｅｌｉｎｅ Ｋａｍｂｅｒ．数据挖掘概念与技术［Ｍ］．范 明，孟小峰，译．北京：机械工业出版社，２００７：１６７－１６１．＠＠［６］ Ｗｕ Ｘｉｎｇｄｏｎｇ， Ｖｉｐｉｎ Ｋｕｍａｒ， Ｒｏｓｓ Ｑｕｉｎｌａｎ Ｊ． Ｔｏｐ １０ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｄａｔａ ｍｉｎｉｎｇ ［Ｊ］． Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ， ２００８，１４（１）： １－３７． ＠＠［７］陈耿，朱玉全，杨鹤标，等．关联规则挖掘中若干关键技术的 研究［Ｊ］．计算机研究与发展，２００５，４２（１０）： １７８５－１７８９．＠＠［８］徐章艳，刘美玲，张师超，等．Ａｐｒｉｏｒｉ算法的三种优化方法［Ｊ］． 计算机工程与应用，２００４，４０（３６）： １９０－１９３． ＠＠［９］傅慧，邹海．基于待与项集的频繁项集挖掘算法的研究［Ｊ］． 计算机工程与设计，２００９，３０（１）： １２９－１３１． ＠＠［１０］徐健辉．生成频繁项集的逻辑“与”运算算法［Ｊ］．计算机应用， ２００４，２４（１１）： ８８－９０． ＠＠［１１］俞燕燕，李绍滋．基于散列的关联规则ＡｐｒｉｏｒｉＴｉｄ改进算法［Ｊ］． 计算机工程，２００８，３４（５）： ６０－６２． ＠＠［１２］柴华昕，王勇．Ａｐｒｉｏｒｉ挖掘频繁项集算法的改进［Ｊ］．计算机 工程与应用，２００７，４３（２４）： １５８－１６１． Ｔｈｅ Ｒｅｓｅａｒｃｈ ｏｎ Ｉｍｐｒｏｖｅｍｅｎｔ ｏｆ Ａｐｒｉｏｒｉ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｍｉｎｉｎｇ Ｆｒｅｑｕｅｎｔ Ｉｔｅｍｓｅｔｓ ＬＩ Ｘｉａｏ－ｃｏｎｇＴＥＮＧ Ｓｈａｏ－ｈｕａ
一种高效频繁子图挖掘算法.2007,18(10)_2469-2480
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.sodocs.net/doc/c48535783.html, Journal of Software , Vol.18, No.10, October 2007, pp.2469?2480 https://www.sodocs.net/doc/c48535783.html, DOI: 10.1360/jos182469 Tel/Fax: +86-10-62562563 ? 2007 by Journal of Software . All rights reserved. 一种高效频繁子图挖掘算法 ? 李先通, 李建中+, 高 宏 (哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001) An Efficient Frequent Subgraph Mining Algorithm LI Xian-Tong, LI Jiang-Zhong +, GAO Hong (School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) + Corresponding author: Phn: +86-451-86415827, E-mail: lijzh@https://www.sodocs.net/doc/c48535783.html,, https://www.sodocs.net/doc/c48535783.html, Li XT, Li JZ, Gao H. An efficient frequent subgraph mining algorithm. Journal of Software , 2007,18(10): 2469?2480. https://www.sodocs.net/doc/c48535783.html,/1000-9825/18/2469.htm Abstract : With the successful development of frequent item set and frequent sequence mining, the technology of data mining is natural to extend its way to solve the problem of structural pattern mining —Frequent subgraph mining. Frequent patterns are meaningful in many applications such as chemistry, biology, computer networks, and World-Wide Web. In this paper we propose a new algorithm GraphGen for mining frequent subgraphs. GraphGen reduces the mining complexity through the extension of frequent subtree. For the best algorithm before, the complexity is O (n 3·2n ), n is the number of frequent edges in a graph dataset. The complexity of GraphGen is ???? ?????n n O n log 25.2, which is improved )log (n n O ? times than the best one. Experiment results prove this theoretical analysis. Key words : frequent pattern mining; subgraph isomorphism; subtree isomorphism; frequent subgraph; spanning tree 摘 要: 由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题——频繁子图挖掘.诸如化学、生物学、计算机网络和WWW 等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间 复杂性是O (n 3·2n ),其中,n 是图集中的频繁边数.提出的算法时间复杂性是???? ?????n n O n log 25.2,性能提高了)log (n n O ?倍. 实验结果也证实了这个理论结果. 关键词: 频繁模式挖掘;子图同构;子树同构;频繁子树;生成树 中图法分类号: TP311 文献标识码: A ? Supported by the National Natural Science Foundation of China under Grant No.60473075 (国家自然科学基金); the Key Program National Natural Science Foundation of China under Grant No.60533110 (国家自然基金重点项目); the National Basic Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973)); the Program for New Century Excellent Talents in University (NCET) under Grant No.NCET-05-0333 (国家教育部新世纪创新人才计划) Received 2006-09-08; Accepted 2006-11-14
《大数据时代下的数据挖掘》试题和答案与解析
《海量数据挖掘技术及工程实践》题目 一、单选题（共80题） 1)( D )的目的缩小数据的取值范围，使其更适合于数据挖掘算法的需要，并且能够得到 和原始数据相同的分析结果。 A.数据清洗 B.数据集成 C.数据变换 D.数据归约 2)某超市研究销售纪录数据后发现，买啤酒的人很大概率也会购买尿布，这种属于数据挖 掘的哪类问题？(A) A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理 3)以下两种描述分别对应哪两种对分类算法的评价标准？ (A) (a)警察抓小偷，描述警察抓的人中有多少个是小偷的标准。 (b)描述有多少比例的小偷给警察抓了的标准。 A. Precision,Recall B. Recall,Precision A. Precision,ROC D. Recall,ROC 4)将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务？(C) A. 频繁模式挖掘 B. 分类和预测 C. 数据预处理 D. 数据流挖掘 5)当不知道数据所带标签时，可以使用哪种技术促使带同类标签的数据与带其他标签的数 据相分离？(B) A. 分类 B. 聚类 C. 关联分析 D. 隐马尔可夫链 6)建立一个模型，通过这个模型根据已知的变量值来预测其他某个变量值属于数据挖掘的 哪一类任务？(C) A. 根据内容检索 B. 建模描述 C. 预测建模 D. 寻找模式和规则 7)下面哪种不属于数据预处理的方法？ (D) A.变量代换 B.离散化
C.聚集 D.估计遗漏值 8)假设12个销售价格记录组已经排序如下：5, 10, 11, 13, 15, 35, 50, 55, 72, 92, 204, 215 使用如下每种方法将它们划分成四个箱。等频（等深）划分时，15在第几个箱子内？ (B) A.第一个 B.第二个 C.第三个 D.第四个 9)下面哪个不属于数据的属性类型：(D) A.标称 B.序数 C.区间 D.相异 10)只有非零值才重要的二元属性被称作：( C ) A.计数属性 B.离散属性 C.非对称的二元属性 D.对称属性 11)以下哪种方法不属于特征选择的标准方法： (D) A.嵌入 B.过滤 C.包装 D.抽样 12)下面不属于创建新属性的相关方法的是： (B) A.特征提取 B.特征修改 C.映射数据到新的空间 D.特征构造 13)下面哪个属于映射数据到新的空间的方法？ (A) A.傅立叶变换 B.特征加权 C.渐进抽样 D.维归约 14)假设属性income的最大最小值分别是12000元和98000元。利用最大最小规范化的方 法将属性的值映射到0至1的范围内。对属性income的73600元将被转化为：(D) A.0.821 B.1.224 C.1.458 D.0.716 15)一所大学内的各年纪人数分别为：一年级200人，二年级160人，三年级130人，四年 级110人。则年级属性的众数是： (A) A.一年级 B.二年级 C.三年级 D.四年级
GIS技术的研究现状及未来发展趋势.
GIS 技术的研究现状及未来发展趋势 摘要:GIS 是随着计算机技术发展而形成的一门新兴技术,其应用程度和范围也随之渗透、延伸,得到了人们的广泛关注。该文综述了地理信.息的发展现状,从多个角度分析当前 GIS 技术发展存在的不足,并在此基础上研究分析了 GIS 技术的未来发展趋势。 关键词:GIS 研究现状发展趋势 0 引言 随着计算机技术的飞速发展、空间技术的日新月异及计算机图形学理论的日渐完善, GIS(Geographic Information System技术也日趋成熟,并且逐渐被人们所认识和接受。近年来, GIS 被世界各国普遍重视,尤其是“数字地球”概念的提出,使其核心技术 GIS 更为各国政府所关注。目前,以管理空间数据见长的 GIS 已经在全球变化与监测、军事、资源管理、城市规划、土地管理、环境研究、农作物估产、灾害预测、交通管理、矿产资源评价、文物保护、湿地制图以及政府部门等许多领域发挥着越来越重要的作用。当前 GIS 正处于急剧发展和变化之中,研究和总结 GIS 技术发展,对进一步开展 GIS 研究工作具有重要的指导意义。因此,本文就目前 GIS 技术的研究现状及未来发展趋势进行总结和分析。 1 GIS 研究现状及其分析 1.1 GIS研究现状 世纪 90年代以来,由于计算机技术的不断突破以及其它相关理论和技术的完善, GIS 在全球得到了迅速的发展。在海量数据存储、处理、表达、显示及数据共享技术等方面都取得了显著的成效,其概括起来有以下几个方面 [1]:①硬件系统采用服务器 /客户机结构,初步形成了网络化、分布式、多媒体 GIS ; ②在 GIS 的设计中, 提出了采用“开放的 CIS 环境” 的概念, 最终以实现资源共享、数据共享为目标; ③高度重视数据标准化与数据质量的问题, 并已形成一些较为可行的数据标准; ④ 面向对象的数据库管理系统已经问世, 正在发展称之为“对象 --关系 DBMS (数据库
流数据频繁模式挖掘算法汇总
频繁模式挖掘 常用的概念： 事务数据库： 时间ID： 项集(item set)： 重要算法： 1、A priori 主要思想就是从大小1开始遍历可能频繁集k，当满足V所有集合子集都在之前计算过的频繁集k中，且出现次数满足频繁要求，则V为k+1频繁集这样做有如下好处：如果一个集合是频繁集，那么它的所有子集都是频繁集； 如果一个集合不是频繁集，那么它的所有超集都不会是频繁集 缺点就是要多次扫描事务数据库 2、F P-growth 可以用来识别包含某个元素的最大频繁集。 FP-growth算法通过构造FP-tree来实现，FP-tree由频繁项集表和前缀树构成。 FP-tree的构建需要扫描两遍数据库， （1）第一遍对所有元素技术并降序排序，然后将数据库中每个事务里的元素按照这个顺序重新排序
（2）按照项头表的顺序逐渐插入元素 ··· （3）FP-tree的挖掘 得到了FP树和项头表以及节点链表，我们首先要从项头表的底部项依次向上挖掘。对于项头表对应于FP树的每一项，我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树，我们将子树中每个节点的的计数设置为叶子节点的计数，并删除计数低于支持度的节点。从这个条件模式基，我们就可以递归挖掘得到频繁项集了。 （1）先从F挖掘 通过它，我们很容易得到F的频繁2项集为{A:2,F:2}, {C:2,F:2}, {E:2,F:2}, {B:2,F:2}。递归合并二项集，得到频繁三项集为{A:2,C:2,F:2}，{A:2,E:2,F:2},...还有一些频繁三项集，就不写了。当然一直递归下去，最大的频繁项集为频繁5项集，为{A:2,C:2,E:2,B:2,F:2}
频繁子图模式挖掘
数据挖掘与商务智能读书报告Using Association Rules for Product Assortment
英文标题：gSpan: Graph-Based Substructure Pattern Mining 中文标题：频繁子图模式挖掘 文献来源：ICDM 2002 一、主要内容（2000～2500字）： （1）论文研究的问题概述 数据挖掘技术及其算法是目前国际上数据库和信息决策领域最前沿的研究方向之一,本文就数据挖掘中基于图结构的gSpan挖掘算法及其应用进行了研究。本文研究了频繁字图挖掘在图数据集的新方法，提出了一种新的算法gSpan，它在没有候选集的情况下发现了频繁子结构。gSpan在图中建立了一种新的字典序，和各图形映射到一个唯一的最小DFS代码作为它的规范的标签。基于这种字典顺序，gSpan采用深度优先的搜索策略高效的挖掘频繁连通子图。研究表明，gSpan大大优于以前的算法。 gSpan算法是图挖掘邻域的一个算法，而作为子图挖掘算法，又是其他图挖掘算法的基础，所以gSpan算法在图挖掘算法中还是非常重要的。gSpan算法在挖掘频繁子图的时候，用了和FP-grown中相似的原理，就是模式增长方法，也用到了最小支持度计数作为一个过滤条件。图算法在程序上比其他的算法更加的抽象，在实现时更加需要空间想象能力。 如果整个数据集图中可以容纳主存，gSpan可以直接应用，否则人们要首先执行基于图的数据投影仪，然后应用gSpan。gSpan是第一个在频繁子图挖掘中使用深度优先搜索的算法。本文介绍DFS字典序和最小DFS码这两种技术，它们形成一种新的规范的标识系统来支持DFS搜索。gSpan在一个步骤里结合了频繁子图的增长和检查，从而加速挖掘过程。 （2）论文研究的理论意义及其应用前景 频繁图挖掘是数据挖掘中一个非常广泛的应用。频繁图挖掘可以理解为从大量的图中挖掘出一些满足给定支持度的频繁图，同时算法需要保证这些频繁图不是重复的。gSpan是一个非常高效的算法，它利用dfs-code序列对搜索树进行编码，并且制定一系列比较规则，从而保证最后只得到序列“最小”的频繁图集合。 由于大部分图挖掘算法都需要利用频繁子图,频繁子图挖掘逐渐成为了数据挖掘领域中的热点研究内容。目前,很多高效的频繁子图挖掘算法已经被提出。其中,gSpan算法是目前公认的最好的频繁子图挖掘算法。然而,在化合物数据集上,还可以利用化合物的特殊结构进一步优化gSpan算法的性能。文献利用了化合物分子结构的对称性和原子类型分布的不均衡
聚类、关联规则挖掘、图数据库
聚类 一、聚类的定义 聚类，属于一种非监督学习方法，它试图在无标签的数据集中发现其分布状况或模式。通常，我们认为同一聚类中的数据点比不同聚类的数据点具有更大的相似性。 二、传统的聚类算法的分类 1、基于划分的聚类算法 主要思想：基于划分的聚类算法通过构造一个迭代过程来优化目标函数，当优化到目标函数的最小值或极小值时，可以得到数据集的一些不相交的子集，通常认为此时得到的每个子集就是一个聚类。 典型方法： k-means算法 FCM算法。 2、层次聚类算法 主要思想：层次聚类方法使用一个距离矩阵作为输入，经过聚类后得到一个反映该数据集分布状况的聚类层次结构图。 层次聚类算法通常分为两种： 凝聚的层次聚类算法：它首先把每个数据点看作是一个聚类，然后以一种自底向上的方式通过不断地选择最近邻居聚类对的合并操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。 分类的层次聚类算法：它首先把所有的数据点看作是一个聚类，然后以一种以自顶向下的方式通过不断地选择最松散簇进行分裂操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。 典型方法： AGNES (AGglomerative NESting) BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) CURE (Clustering Using REpresentative) 3、基于密度的聚类算法 主要思想：基于密度的聚类算法试图通过稀疏区域来划分高密度区域以发现明显的聚类和孤立点，主要用于空间型数据的聚类。 典型方法： DBSCAN (Density-based Spatial Clustering of Application with Noise) OPTICS (Ordering Points to Identify the Clustering Structure) 4、基于网格的聚类算法 主要思想：基于网格的聚类算法是一种基于网格的具有多分辨率的聚类方法。它首先将数据集的分布空间划分为若干个规则网格(如超矩形单元)或灵活的网格(如任意形状的多
空间聚类的研究现状及其应用_戴晓燕
空间聚类的研究现状及其应用＊ 戴晓燕1 过仲阳1 李勤奋2 吴健平1 (1华东师范大学教育部地球信息科学实验室 上海 200062) (2上海市地质调查研究院 上海 200072) 摘 要 作为空间数据挖掘的一种重要手段,空间聚类目前已在许多领域得到了应用。文章在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 关键词 空间聚类 K-均值法 散度 1 前言 随着GPS、GI S和遥感技术的应用和发展,大量的与空间有关的数据正在快速增长。然而,尽管数据库技术可以实现对空间数据的输入、编辑、统计分析以及查询处理,但是无法发现隐藏在这些大型数据库中有价值的模式和模型。而空间数据挖掘可以提取空间数据库中隐含的知识、空间关系或其他有意义的模式等[1]。这些模式的挖掘主要包括特征规则、差异规则、关联规则、分类规则及聚类规则等,特别是聚类规则,在空间数据的特征提取中起到了极其重要的作用。 空间聚类是指将数据对象集分组成为由类似的对象组成的簇,这样在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大,即相异度较大。作为一种非监督学习方法,空间聚类不依赖于预先定义的类和带类标号的训练实例。由于空间数据库中包含了大量与空间有关的数据,这些数据来自不同的应用领域。例如,土地利用、居住类型的空间分布、商业区位分布等。因此,根据数据库中的数据,运用空间聚类来提取不同领域的分布特征,是空间数据挖掘的一个重要部分。 空间聚类方法通常可以分为四大类:划分法、层次法、基于密度的方法和基于网格的方法。算法的选择取决于应用目的,例如商业区位分析要求距离总和最小,通常用K-均值法或K-中心点法;而对于栅格数据分析和图像识别,基于密度的算法更合适。此外,算法的速度、聚类质量以及数据的特征,包括数据的维数、噪声的数量等因素都影响到算法的选择[2]。 本文在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 2 划分法 设在d维空间中,给定n个数据对象的集合D 和参数K,运用划分法进行聚类时,首先将数据对象分成K个簇,使得每个对象对于簇中心或簇分布的偏离总和最小[2]。聚类过程中,通常用相似度函数来计算某个点的偏离。常用的划分方法有K-均值(K-means)法和K-中心(K-medoids)法,但它们仅适合中、小型数据库的情形。为了获取大型数据库中数据的聚类体,人们对上述方法进行了改进,提出了K-原型法(K-prototypes method)、期望最大法EM(Expectation Maximization)、基于随机搜索的方法(ClAR ANS)等。 K-均值法[3]根据簇中数据对象的平均值来计算 ——————————————— ＊基金项目:国家自然科学基金资助。(资助号: 40371080) 收稿日期:2003-7-11 第一作者简介:戴晓燕,女,1979年生,华东师范大学 地理系硕士研究生,主要从事空间数 据挖掘的研究。 · 41 · 2003年第4期 上海地质 Shanghai Geology
文献综述_数据挖掘
数据挖掘简介 数据挖掘的任务 数据挖掘的任务就是从实例集合中找出容易理解的规则和关系。这些规则可以用于预测未来趋势、评价顾客、评估风险或简单地描述和解释给定的数据。通常数据挖掘的任务包括以下几个部分: 数据总结目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值，或者用直方图、饼图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。数据泛化目前主要有两种技术:多维数据分析方法和面向属性的归纳方法。 多维数据分析方法是一种数据仓库技术，也称作联机分析处理(OLAP，onLineAnalysisProeess)。数据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合。决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特别大。因此一种很自然的想法是，把汇集操作结果预先计算并存储起来，以便于决策支持系统使用。存储汇集操作结果的地方称作多维数据库。多维数据分析技术已经在决策支持系统中获得了成功的应用，如著名的SAS数据分析软件包、Businessobject公司的决策支持系统Businessobjeet，以及IBM公司的决策分析工具都使用了多维数据分析技术。 采用多维数据分析方法进行数据总结，它针对的是数据仓库，数据仓库存储的是脱机的历史数据。为了处理联机数据，研究人员提出了一种面向属性的归纳方法。它的思路是，直接对用户感兴趣的数据视图(用一般的SQL查询语言即可获得)进行泛化，而不是像多维数据分析方法那样预先就存储好了泛化数据。方法的提出者对这种数据泛化技术称之为面向属性的归纳方法。原始关系经过泛化操作后得到的是一个泛化关系，它从较高的层次上总结了在低层次上的原始关系。有了泛化关系后，就可以对它进行各种深入的操作而生成满足用户需要的知识，如在泛化关系基础上生成特性规则、判别规则、分类规则，以及关联规则等。数据挖掘的分类 数据挖掘所能发现的知识有如下几种: .广义型知识，反映同类事物共同性质的知识; .特征型知识，反映事物各方面的特征知识; .差异型知识，反映不同事物之间属性差别的知识; .关联型知识，反映事物之间依赖或关联的知识; .预测型知识，根据历史的和当前的数据推测未来数据; .偏离型知识。揭示事物偏离常规的异常现象。 所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家超市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。 数据挖掘的方法 数据挖掘并非一个完全自动化的过程。整个过程需要考虑数据的所有因素和其预定的效用，然后应用最佳的数据挖掘方法。数据挖掘的方法很重要。在数据挖掘的领域里.有一点已经被广泛地接受，即不管你选择哪种方法，总存在着某种协定。因此对实际情况，应该具体分析，根据累积的经验和优秀的范例选择最佳的方法。数据挖掘中没有免费的午餐，也没
数据挖掘在中国的现状和发展研究
数据挖掘在中国的现状和发展研究 导读：本文以科学引文索引数据库(SCI)、工程索引数据库(EI)以及清华全文数据库(CNKI)中有关“数据挖掘”研究文章的统计数据为研究基础，对数据挖掘在我国研究的总体趋势、研究热点、研究分支三个方面进行分析和研究。本文分析了数据挖掘在我国的发展，并对进一步发展我国数据挖掘的理论研究和实际应用提出了建议。 关键字：数据挖掘 0 引言 近年来，随着计算机对数据的生成、收集、存贮和处理能力的大大提高，数据量与日俱增，传统的数据分析工具对海量数据的处理力不从心，数据挖掘技术应运而生。 中国科研工作者近几年来积极开展了对数据挖掘的研究，并在理论研究和实际应用上取得了一定的成绩，但是有关数据挖掘的成功应用还比较少。本文通过对中国有关数据挖掘研究文章数量的统计，对数据挖掘在中国发展的现状及发展趋势进行分析和研究，通过分析有关论文的发表，对数据挖掘在中国的理论研究和实际应用提出建议。 1 数据挖掘的应用与研究发展 数据挖掘是指从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有用知识的过程。数据挖掘是一门新兴的边缘学科，近年来引起了中国学术界和产业界的广泛关注。 数据挖掘出现于20世纪80年代后期，90年代有了突飞猛进的发展。2001年，Gartner Group的一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大关健技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。美国麻省理工学院在2001年1月份的《科技评论》(Technology Review)提出将在未来5年对人类产生重大影响的10大新兴技术，其中第3项就是数据挖掘。 数据挖掘技术已被广泛的应用于各个领域，其中一些典型应用如加州理工学院喷气推进实验室与天文科学家合作开发的SKICAT系统，能够帮助天文学家发现遥远的类星体，是人工智能技术在天文学和空间科学上的第一批成功应用之一；生物学研究中用数据挖掘技术对DNA进行分析利用数据挖掘技术识别顾客的购买行为模式，对客户进行了分析；对银行或商业上经常发生的诈骗行为进行预测IBM公司
数据挖掘实验三应用 Apriori 算法挖掘频繁项集
实验三、应用 Apriori 算法挖掘频繁项集 学院计算机科学与软件学院 ?实验目的： （1）熟悉 VC++编程工具和 Apriori 频繁项集挖掘算法。 （2）根据管理层的需求，确定数据挖掘的任务，明确数据挖掘的功能，也 就是明确要挖掘什么。 （3）由确定的数据挖掘任务，从实验一处理后的结果中，采用切块或切片 等联机分析处理技术，选择出挖掘任务相关数据。 （4）用 VC++编程工具编写 Apriori 算法的程序，对任务相关数据运行 Apriori 算法，挖掘出所有的频繁项集。 1.写出实验报告。 ?实验原理： 1 、Apriori 算法 Apriori 使用一种称作逐层搜索的迭代方法，k 项集用于探索（k+1）项集。 首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项， 找出频繁 1 项集的集合。该集合记作 L 1 。然后，L 1 用于找频繁 2 项集的集合L 2 ，L 2 用于找 L 3 ，如此下去，直到不能再找到频繁 k 项集。找每个 L k 需要一次数据库全扫描。 2、提高频繁项集逐层产生的效率 Apriori 性质：频繁项集的所有非空子集也必须是频繁的。 三、实验内容： 1、实验内容 在给定的数据中提取统一购物篮购买的商品信息，由这些数据构成事务数据库 D，挖掘其中的频繁项集 L。 挖掘频繁项集的算法描述如下： Apriori 算法：使用逐层迭代找出频繁项集 输入：事务数据库 D；最小支持度阈值。 输出：D 中的频繁项集 L。 （1） L 1 = find_frequent_1-itemsets(D); // 挖掘频繁 1-项集，比较容易 （2） for (k=2;L k-1 ≠Φ ;k++) { （3） C k = apriori_gen(L k-1 ,min_sup); // 调用 apriori_gen 方法生成候选频繁 k-项集分为两步：合并、减枝 （4） for each transaction t ∈ D { // 扫描事务数据库 D （5） Ct = subset(C k ,t); （6） for each candidate c ∈ Ct （7） c.count++; // 统计候选频繁 k-项集的计数 （8） } （9） L k ={c ∈ Ck|c.count≥min_sup} // 满足最小支持度的 k-项集即为频 繁 k-项集
大数据时代的空间数据挖掘综述
第37卷第7期测绘与空间地理信息 GEOMATICS ＆SPATIAL INFOＲMATION TECHNOLOGY Vol．37，No．7收稿日期：2014－01－22 作者简介：马宏斌（1982－），男，甘肃天水人，作战环境学专业博士研究生，主要研究方向为地理空间信息服务。 大数据时代的空间数据挖掘综述 马宏斌1 ，王 柯1，马团学 2（1．信息工程大学地理空间信息学院，河南郑州450000；2．空降兵研究所，湖北孝感432000） 摘 要：随着大数据时代的到来，数据挖掘技术再度受到人们关注。本文回顾了传统空间数据挖掘面临的问题， 介绍了国内外研究中利用大数据处理工具和云计算技术，在空间数据的存储、管理和挖掘算法等方面的做法，并指出了该类研究存在的不足。最后，探讨了空间数据挖掘的发展趋势。关键词：大数据；空间数据挖掘；云计算中图分类号：P208 文献标识码：B 文章编号：1672－5867（2014）07－0019－04 Spatial Data Mining Big Data Era Ｒeview MA Hong －bin 1，WANG Ke 1，MA Tuan －xue 2 （1．Geospatial Information Institute ，Information Engineering University ，Zhengzhou 450000，China ； 2．Airborne Institute ，Xiaogan 432000，China ） Abstract ：In the era of Big Data ，more and more researchers begin to show interest in data mining techniques again．The paper review most unresolved problems left by traditional spatial data mining at first．And ，some progress made by researches using Big Data and Cloud Computing technology is introduced．Also ，their drawbacks are mentioned．Finally ，future trend of spatial data mining is dis-cussed． Key words ：big data ；spatial data mining ；cloud computing 0引言 随着地理空间信息技术的飞速发展，获取数据的手 段和途径都得到极大丰富，传感器的精度得到提高和时空覆盖范围得以扩大，数据量也随之激增。用于采集空间数据的可能是雷达、红外、光电、卫星、多光谱仪、数码相机、成像光谱仪、全站仪、天文望远镜、电视摄像、电子 显微镜、CT 成像等各种宏观与微观传感器或设备，也可能是常规的野外测量、人口普查、土地资源调查、地图扫描、 地图数字化、统计图表等空间数据获取手段，还可能是来自计算机、 网络、GPS ，ＲS 和GIS 等技术应用和分析空间数据。特别是近些年来，个人使用的、携带的各种传感器（重力感应器、电子罗盘、三轴陀螺仪、光线距离感应器、温度传感器、红外线传感器等），具备定位功能电子设备的普及，如智能手机、平板电脑、可穿戴设备（GOOGLE GLASS 和智能手表等），使人们在日常生活中产生了大量具有位置信息的数据。随着志愿者地理信息（Volunteer Geographic Information ）的出现，使这些普通民众也加入到了提供数据者的行列。 以上各种获取手段和途径的汇集，就使每天获取的 数据增长量达到GB 级、 TB 级乃至PB 级。如中国遥感卫星地面站现在保存的对地观测卫星数据资料达260TB ，并以每年15TB 的数据量增长。比如2011年退役的Landsat5卫星在其29年的在轨工作期间，平均每年获取8．6万景影像，每天获取67GB 的观测数据。而2012年发射的资源三号（ZY3）卫星，每天的观测数据获取量可以达到10TB 以上。类似的传感器现在已经大量部署在卫 星、 飞机等飞行平台上，未来10年，全球天空、地空间部署的百万计传感器每天获取的观测数据将超过10PB 。这预示着一个时代的到来，那就是大数据时代。大数据具有 “4V ”特性，即数据体量大（Volume ）、数据来源和类型繁多（Variety ）、数据的真实性难以保证（Veracity ）、数据增加和变化的速度快（Velocity ）。对地观测的系统如图1所示。 在这些数据中，与空间位置相关的数据占了绝大多数。传统的空间知识发现的科研模式在大数据情境下已经不再适用，原因是传统的科研模型不具有普适性且支持的数据量受限， 受到数据传输、存储及时效性需求的制约等。为了从存储在分布方式、虚拟化的数据中心获取信息或知识，这就需要利用强有力的数据分析工具来将
数据挖掘文献综述
湘潭大学 本科生专业文献综述 题目: 数据挖掘文献综述 姓名: 林勇 学院: 信心工程学院学院 专业: 自动化 班级: 一班 学号: 2010550113 指导教师: 张莹
0前言 随着计算机技术的迅猛发展，人类正在步入信息社会。面对今天浩如烟海的信息，如何帮助人们有效地收集和选择所感兴趣的信息，更关键的是如何帮助用户在日益增多的信息中自动发现新的概念并自动分析它们之间的关系，使之能够真正地做到信息处理的自动化，这已成为信息技术领域的热点问题。数据挖掘就是为满足这种要求而产生并迅速发展起来的，可用于开发信息资源的一种新的数据处理技术。 1什么是数据挖掘 数据挖掘(Data Mining)，也叫数据开采，数据采掘等，是按照既定的业务目标从海量数据中提取出潜在、有效并能被人理解的模式的高级处理过程。在较浅的层次上，它利用现有数据库管理系统的查询、检索及报表功能，与多维分析、统计分析方法相结合，进行联机分析处理，从而得出可供决策参考的统计分析数据。在深层次上，则从数据库中发现前所未有的、隐含的知识。OLAF'的出现早于数据挖掘，它们都是从数据库中抽取有用信息的方法，就决策支持的需要而言两者是相辅相成的。OLAP可以看作一种广义的数据挖掘方法，它旨在简化和支持联机分析，而数据挖掘的目的是便这一过程尽可能自动化。数据挖掘基于的数据库类型主要有：关系型数据库、面向对象数据库、事务数据库、演绎数据库、时态数据库、多媒体数据库、主动数据库、空间数据库、遗留数据库、异质数据库、文本型、Internet信息库以及新兴的数据仓库(Data Warehouse)等。而挖掘后获得的知识包括关联规则、特征规则、区分规则、分类规则、总结规则、偏差规则、聚类规则、模式分析及趋势分析等。 1.1 数据挖掘的任务 数据挖掘的两个高层目标是预测和描述。前者指用一些变量或数据库的若干已知字段预测其它感兴趣的变量或字段的未知的或未来的值；后者指找到描述数据的可理解模式。根据发现知识的不同，我们可以将数据挖掘任务归纳为以下几类： (1)特征规则。从与学习任务相关的一组数据中提取出关于这些数据的特征式，这些特征式表达了该数据集的总体特征．例如可以从某种疾病的症状中提取
数据挖掘分类算法研究综述终板
数据挖掘分类算法研究综述 程建华 (九江学院信息科学学院软件教研室九江332005 ) 摘要：随着数据库应用的不断深化,数据库的规模急剧膨胀,数据挖掘已成为当今研究的热点。特别是其中的分类问题,由于其使用的广泛性,现已引起了越来越多的关注。对数据挖掘中的核心技术分类算法的内容及其研究现状进行综述。认为分类算法大体可分为传统分类算法和基于软计算的分类法两类。通过论述以上算法优缺点和应用范围，研究者对已有算法的改进有所了解，以便在应用中选择相应的分类算法。 关键词：数据挖掘；分类；软计算；算法 1引言 1989年8月，在第11届国际人工智能联合会议的专题研讨会上，首次提出基于数据库的知识发现(KDD，Knowledge DiscoveryDatabase)技术[1]。该技术涉及机器学习、模式识别、统计学、智能数据库、知识获取、专家系统、数据可视化和高性能计算等领域，技术难度较大，一时难以应付信息爆炸的实际需求。到了1995年，在美国计算机年会(ACM)上，提出了数据挖掘[2](DM，Data Mining)的概念，由于数据挖掘是KDD过程中最为关键的步骤，在实践应用中对数据挖掘和KDD这2个术语往往不加以区分。 基于人工智能和信息系统，抽象层次上的分类是推理、学习、决策的关键，是一种基础知识。因而数据分类技术可视为数据挖掘中的基础和核心技术。其实，该技术在很多数据挖掘中被广泛使用，比如关联规则挖掘和时间序列挖掘等。因此，在数据挖掘技术的研究中，分类技术的研究应当处在首要和优先的地位。目前，数据分类技术主要分为基于传统技术和基于软计算技术两种。 2传统的数据挖掘分类方法 分类技术针对数据集构造分类器，从而对未知类别样本赋予类别标签。在其学习过程中和无监督的聚类相比，一般而言，分类技术假定存在具备环境知识和输入输出样本集知识的老师，但环境及其特性、模型参数等却是未知的。 2.1判定树的归纳分类 判定树是一个类似流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根节点。由判定树可以很容易得到“IFTHEN”形式的分类规则。方法是沿着由根节点到树叶节点的路径，路径上的每个属性-值对形成“IF”部分的一个合取项，树叶节点包含类预测，形成“THEN”部分。一条路径创建一个规则。 判定树归纳的基本算法是贪心算法，它是自顶向下递归的各个击破方式构造判定树。其中一种著名的判定树归纳算法是建立在推理系统和概念学习系统基础上的ID3算法。 2.2贝叶斯分类 贝叶斯分类是统计学的分类方法，基于贝叶斯公式即后验概率公式。朴素贝叶斯分类的分类过程是首先令每个数据样本用一个N维特征向量X={X1，X2，?X n}表示，其中X k是属性A k的值。所有的样本分为m类：C1，C2，?，C n。对于一个类别的标记未知的数据记录而言，若P(C i/X)>P(C j/X)，1≤ j≤m，j≠i，也就是说，如果条件X下，数据记录属于C i类的概率大于属于其他类的概率的话，贝叶斯分类将把这条记录归类为C i类。 建立贝叶斯信念网络可以被分为两个阶段。第一阶段网络拓扑学习，即有向非循环图的——————————————————— 作者简介：程建华（1982-），女，汉族，江西九江，研究生，主要研究方向为数据挖掘、信息安全。