一种高效频繁子图挖掘算法.2007,18(10)_2469-2480

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.sodocs.net/doc/291212783.html,

Journal of Software , Vol.18, No.10, October 2007, pp.2469?2480 https://www.sodocs.net/doc/291212783.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/291212783.html,, https://www.sodocs.net/doc/291212783.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/291212783.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

2470 Journal of Software软件学报 V ol.18, No.10, October 2007

由于图具有广泛的应用性,所以针对图挖掘的研究也越来越引起人们的重视.很多领域内的数据都可抽象为图,如给定物质的化学结构能被抽象为无向标号图(其中的节点对应着原子,而边则对应着原子间的化合键),生物学、XML、计算机网络和WWW中的数据也可抽象为图,用于进一步的研究.

图挖掘可以粗略地分为频繁子图挖掘、图聚类与图分类等等.频繁子图挖掘的目的是找到在图集中频繁出现的子图.由于频繁子图挖掘结果可作为图聚类、图分类等其他图挖掘研究的基础,也使得频繁子图的挖掘工作具有更加深远的影响.目前,频繁子图的挖掘结果已经应用于一些应用领域内,如在PTE(predictive toxicology evaluation challenge)项目中的应用,其目的是找到频繁出现的与有毒物质具有相同子结构的物质.Borgelt和Berthold在文献[1]中证明了使用图描述和采用频繁子图挖掘技术对这个问题研究的有效性.其他的基于频繁子图挖掘的应用包括录像索引、提高结构化数据库的存储效率、高效索引技术和WEB信息管理等.

但是随着图和图集规模的扩大,现有频繁子图挖掘算法在效率上已不能满足需求.在PTE项目中,图的规模还比较小(20个节点与边),节点度的平均值也较小(≤4),节点标号集却相对较大(>60).但在蛋白质研究领域内抽象出的图则大得多,虽然节点标号集相对较小(20个标号左右),但图的尺寸更大(100~1 000个节点或边),每个节点的度也更大(在某些例子中达到6~20).因此,要设计适合更大、更复杂图集的挖掘算法,提高频繁子图的挖掘效率势在必行.

初期的频繁子图挖掘算法,将工作重点集中在近似技术(SUBDUE[2])和小规模数据库上(inductive logic programming).

近期的频繁子图挖掘算法可以分为两类:一类是广度优先算法(broad first search,简称BFS).这类算法采用了类Apriori性质去枚举重复出现的子图.这类算法包括AGM[3,4]和FSG[5].AGM在图集中搜索所有“诱导”子图.图G的诱导子图G′的节点为V(G′)?V(G),G′的边为V(G′)中节点在图G中的所有边.FSG则利用边增长的方式查找所有图集中的频繁连通子图.因为采用了Apriori性质,即在扩展边的过程中,通过两个n条边候选图进行乘积以得到(n+1)条边的候选图,这样做会生成大量重复候选子图,降低了算法的整体效率.

频繁子图挖掘算法的另一类是具有更好执行效率的深度优先算法(depth first search,简称DFS).这类算法包括gSpan,CloseSpan和FFSM等.所有算法均通过逐步扩展频繁边得到频繁子图,但每个算法对图的扩展过程略有不同.Yan和Han在文献[6]中提出的算法gSpan是典型的深度优先算法[7],频繁子图G是通过对其父亲子图G′增加一条新的频繁边而得到的.与枚举所有潜在子图不同,gSpan方法保存一个频繁子图G的子图同构列表,这样做的好处是能减少制约效率的同构测试次数.不过,gSpan并不能避免子图同构测试,边的扩展算法复杂性也很高,达到了O(2n),使总的时间复杂性高达O(2n·2n).在文献[8]中,Yan等人又提出了挖掘频繁闭图集的CloseSpan算法,虽然它在边的扩展与结果集的剪枝中采用了一些优化方法以减少计算时间,但总体的时间复杂性依然为O(2n·2n).Huan和Wang在文献[9]中提出了另一种频繁模式挖掘算法FFSM,将图的描述巧妙的转化为标准邻接矩阵(canonical adjacent matrix,简称CAM).这样,FFSM不但将子图同构问题转化成了对矩阵的操作,也将图扩展过程巧妙的转化为矩阵的联接操作与矩阵的扩展操作.但是,由于其图扩展的过程通过矩阵的联接与扩展完成,所以扩展边的时间复杂性为O(m2·n·2n)?,图同构测试的时间复杂性为O(m2),总的时间复杂性降低至O(m4·n·2n).具有m个节点的完全图包含m(m?1)/2条边,因此,其时间复杂性转化为用频繁边数表示的情况为O(n3·2n).

在表1中,我们给出了上述3种算法时间复杂性的比较,其中,n表示边数,m表示节点数,第2列给出了这些挖掘算法对频繁图中边进行扩展时的时间复杂性,第3列给出了这些算法进行子图同构测试的时间复杂性.由于在频繁子图的挖掘过程中,每次对边进行扩展都需要进行同构测试,因此,总的时间复杂性是边扩展的复杂性与同构测试复杂性的乘积,在第4列中给出.

从表1中可以看出,在频繁子图挖掘算法中,两个对算法时间复杂性影响最大的问题是子图同构问题(子图同构问题已被证明是NP完全问题)和有效的图扩展方法.表1中的数据显示,以上3种算法对边的扩展过程均采

?算法本身是按先深搜索的方式对边进行扩展,其复杂性为O(2n).但由于在扩展过程中,使用了矩阵的联接操作与扩展操作形成新的CAM,使复杂性达到O(m2·n·2n).

李先通 等:一种高效频繁子图挖掘算法

2471

用先深搜索方式,但对子图同构测试的方式却不尽相同,FFSM 效率更高,它能回避图与图之间直接的同构测试,通过标准邻接矩阵的比较确定子图同构问题,达到相对较好的时间复杂性O (m 2).因此,无论提高扩展边的效率还是子图同构测试的效率,都会对降低整体算法的时间复杂性起到积极的作用.虽然近期也有部分挖掘技术研究成果[10?12],但这个问题仍然没有很好的解决.

Table 1 Complexity of graph mining algorithms

表1 图挖掘算法的时间复杂性分析

扩展边的复杂性

同构测试复杂性

总复杂性gSpan O (2n ) O (2n ) O (2n ·2n )CloseSpan O (2n ) O (2n ) O (2n ·2n )FFSM

O (m 2·n ·2n )

O (m 2)

O (n 3·2n )

本文提出了一种新的频繁子图挖掘算法GraphGen,基本思想是将图挖掘过程分为两步:第1步是生成频繁子树,对边的扩展采用深度优先的方法,复杂性为O (2n ),但由于挖掘结果是树,其同构测试时间复杂性为

???????

?n n O log 5.2[10]

.第2步是对第一步中生成的频繁子树进一步扩展以形成频繁图,边的扩展方式为广度优先,复杂性 为O (n 2),进行子图同构测试的时间复杂性为O (2n ),这部分总的时间复杂性为O (n 2·2n ).由于这两部分是顺序完成

的,因此,算法总体的时间复杂性为???

?

?????n n O n log 25.2.

本文第1节给出与频繁子图挖掘的相关术语及定义.第2节给出频繁子图挖掘算法(先给出图描述的标准化编码,然后给出图挖掘算法).第3节给出实验结果.第4节对全篇进行总结.

1 基本概念

在本文中,我们将问题集中于简单无向连通标号图.通过修改,本文提出的算法也适用于复杂无向连通标号图,即含有环或两节点间有多条边的情况.

标号图作为一种通用的数据结构,能用于复杂模式的模型化工作.我们在这部分给出标号图的定义,同时给出的还有子图同构与频繁子图支持度的定义.基于这些定义,我们能对图进行准确的数学描述.

定义1.1(标号图). 一个标号图是一个五元组,G ={V ,E ,ΣE ,ΣV ,L }.其中,V 代表图中节点的集合,E ?V ×V 代表图中边的集合.ΣV ,ΣE 分别代表节点标号的集合与边标号的集合.L 是标号函数,用于完成标号向节点和边的映射:V →ΣV 与E →ΣE .

定义1.2(图的同构). 图的同构是一个双射f :V (G )?V (G ′).对于图G ={V ,E ,ΣV ,ΣE ,L }与图G ′={V ′,E ′,ΣV ′,ΣE ′, L ′},若它们是同构的,则满足如下条件:

?u ∈V ,L (u )=L ′(f (u ))

?u ,v ∈V ,((u ,v )∈E )?((f (u ),f (v ))∈E ′),且 ?(u ,v )∈E ,L (u ,v )=L ′(f (u ),f (v )).

定义1.3(子图同构). 给定标号图G 与G ′,若G ′中存在子图G ″与图G 同构,则称G 与G ′是子图同构的,记为G ?G ′.

子图同构问题是NP 完全问题.如何减少或降低子图同构的计算开销,是图挖掘工作研究人员的主要研究内容之一.

定义1.4(支持度). 给定一个图的集合GD ,图G 的支持度记为SUP G ,计算方法为GD 中与G 存在子图同构的图G ′的个数与整个图集中图的个数的比值,表示如下:

|

||

}|{|GD G G GD G SUP G ′?∈′=.

一个图是否频繁,与该图在图集中的出现次数相关,同时也与预先定义的最小支持度阈值有关.设预先给定

2472 Journal of Software 软件学报 V ol.18, No.10, October 2007

的最小支持度阈值为min _sup ,则频繁图的定义如下:

定义1.5(频繁图与频繁树). 给定一个图集GD ,GD ={G i |i =0,1,…,n },且给定最小支持度阈值为min _sup ,我们称图G 是频繁的,当且仅当G 的支持度不小于最小支持度阈值,即SUP G ≥min _sup .相应地,当图G 是频繁的且其中无回路时,我们称G 为频繁树.

频繁子图挖掘问题是给定一个最小支持度阈值min _sup ,在图集GD 中找到所有支持度不小于min _sup 的子图.在以下章节中,使用大写字符表示集合,如“G ”,“E ”,“V ”等,而用小写字符表示元素,如“g ”,“e ”,“v ”等.

2 挖掘频繁子图

采用先深搜索的办法挖掘频繁子图,会在搜索的过程中形成一个树状的搜索空间(这个特点可以参照频繁项集中FP 树的定义),这棵树的根节点为空,由根至叶按边个数递增的顺序形成树,非根节点分别代表不同的频繁子图.整个挖掘过程是由根至叶的遍历过程.图1显示了这个树状的搜索空间

.

3-edge n -edge

...

Fig.1 Search space 图1 搜索空间

图的标准化编码是对图的一种形式化描述.将图与标准化编码进行一一对应,可有效的避免同构图的不同遍历顺序引起的重复候选集的计算开销.确定了图的标准化编码,我们就可以只计算具有标准化编码的遍历,降低算法的复杂性. 2.1 图的标准化编码

标号图的每一条边,都存在5个基本元素,即两个节点标识、两个节点标号和边标号,我们可直接使用该五元组对边进行描述,将边e =(v i ,v j )表示为(v i ,l i ,v j ,l j ,l e ),其中,v i ,v j 为节点标识,l i ,l j 为节点标号,l e 为边标号.例如图2(a)所示标号图,边(v 1,v 2)可表示为(v 1,B ,v 2,A ,b ),边(v 0,v 3)可表示为(v 0,A ,v 3,B ,c ).

节点标识之间存在一种线性顺序:若在图的遍历过程中先遍历v i ,后遍历v j .则v i 和v j 之间的顺序关系为v i ?v j .同样地,我们规定节点标号与边标号之间也存在一种序关系,即线性的字母序.由此,我们可定义边之间的线性关系.例如图2(a)中,我们可通过v 0?v 1来确定(v 0,v 1)(v ?1,v 2),但图2(a)与图2(b)中,边(v 0,v 1)中各项编码均相同,仅边的标号不同,我们可通过边的标号来确定其大小,由于a

2

3

2

3

(a) (b) Fig.2 Representation of labeled graph

图2 标号图的表示方法

定义2.1(边的线性顺序). 给定标号图的任意两条边e a =(a 1,a 2,a 3,a 4,a 5),e b =(b 1,b 2,b 3,b 4,b 5),其线性顺序由下

李先通等:一种高效频繁子图挖掘算法2473

列条件决定:

1) e a=e b,当且仅当a i=b i,i=1,2, (5)

2) e a?e b,当且仅当?k,1≤k≤5,使a j=b j (1≤j

3) e b?e a,其他情况.

例如,图2所示为同一个图的3种不同遍历结果.图2(a)中的边(v1,v3)a可描述为(v1,B,v3,B,a),图2(b)中的边(v1,v3)b可描述为(v1,B,v3,B,a).由于这两个五元组完全相等,因此,这两条边的顺序关系是相同的.然而,虽然图2(a)中的边(v0,v1)a=(v0,A,v1,B,a)与图2(b)中的边(v0,v1)b=(v0,A,v1,B,b)前4个元素具有相同的顺序关系,但第5个元素的顺序关系为a b,依照定义2.1,边的顺序关系为(v

?0,v1)a?(v0,v1)b.同理,图2(a)中的边(v0,v3)a=(v0,A,v3,B,c)与图2(b)中的边(v0,v3)b=(v0,A,v3,B,b)之间的大小关系为(v0,v3)b?(v0,v3)a,而图2(a)中的边(v2,v3)a=(v2,A,v3,B,b)与图2(b)中的边(v2,v3)b=(v2,A,v3,B,c)之间的大小关系为(v2,v3)a?(v2,v3)b.

同样地,我们可给出图的线性顺序定义

定义2.2(图的线性顺序). 给定两个标号图的DFS遍历编码g1={e11,e12,…,e1n},g2={e21,e22,…,e2m},其中,e ij表示图g i中DFS遍历第j条边的编码.图g1、图g2的线性顺序由下列条件决定:

1) g1=g2,当且仅当m=n,且e1i=e2i,其中,1≤i≤m;

2) g1?g2,当且仅当下列条件之一成立:

a) ?k,1≤k≤min(n,m),使e1j=e2j (1≤j

b) n

3) g2?g1,其他情况.

例如,表2的第2列~第4列分别对应图2中的3种遍历结果图2(a)~图2(c).通过定义2.1与定义2.2给出的线性顺序,我们得到g a?g b?g c.下面我们证明对任意图,其DFS编码值都存在最小值,且这个最小值是唯一的.

Table 2DFS coding of graphs

表2图的DFS编码

Edge 图2(a) 图2(b) 图2(c)

0 (v0,A,v1,B,a) (v0,A,v1,B,b)(v0,B,v1,B,a)

1 (v1,B,v2,A,b) (v1,B,v2,A,a)(v1,B,v2,A,a)

2 (v2,A,v3,B,b) (v2,A,v3,B,c)(v1,B,v3,A,b)

3 (v3,B,v1,B,a) (v3,B,v1,B,a)(v2,A,v0,B,c)

4 (v3,B,v0,A,c) (v3,B,v0,A,b)(v3,A,v0,B,b)

定理2.1. 图的最小DFS编码是唯一的.

证明:先证明其存在性.设图g为具有n条边的标号图,共有k种遍历方法,其编码的集合为G DFS={g1,g2,…,g k| g i={e i1,e i2,…,e in}(1≤i≤k)}.由定义2.2知,?g i,g j∈G,g i和g j之间均存在线性顺序关系.因此,将G中的编码逐个比较,必然能找到g′∈G,且其线性顺序具有最小值,所以图的最小DFS编码存在.

再证明其唯一性.设最小DFS编码不唯一.图g的不同遍历产生的DFS编码为G DFS={g1,g2,…,g k| g i={e i1,e i2,…,e in}(1≤i≤k)}.设g i与g j均为最小DFS编码,且g i≠g j.由定义2.2知,两个不同的DFS编码值,其相互关系仅有3种情况,若g i≠g j,则必有g i?g j或g j?g i之一成立.在不影响结果的前提下,不妨设g i?g j成立,这与题设g i与g j 均为最小DFS编码矛盾,而导致这种矛盾的原因是假定最小DFS编码不唯一.所以,最小DFS编码是唯一的.

综上所述,最小DFS编码存在,并且唯一. □定理2.1确定了图与最小DFS编码的一一对应关系.在进行图挖掘的过程中,由于同构图的遍历顺序不同,会形成不同的DFS编码.通过最小DFS编码与图的一一对应,我们在挖掘过程中可以放弃对其他DFS编码的继续操作而只考虑最小DFS编码,这样做既会保证得到完整的结果集,又可以避免扩展重复候选集所带来的额外计算开销.

接下来,我们从频繁子图的生成过程着手,进一步分析挖掘过程中树与图之间的关系.

定义2.3. 在图的扩展过程中,如果一条扩展边引入了一个新的节点,则称该扩展边为外边,由e o表示.若该扩展边未引入新的节点(扩展边的两个节点已存在于该图中),则称其为内边,用e w表示.

2474 Journal of Software软件学报 V ol.18, No.10, October 2007

图集中,节点与边的频率超过最小支持度阈值时,我们称其为频繁节点与频繁边.由此设定,当外边(内边)的频率不低于最小支持度阈值时,称其为频繁外边(频繁内边).

例如,图2(a)的遍历过程如表2第2列所示,其中,用粗实线描述的边表示扩展过程中的外边,而用虚线表示的边则为内边.因此,我们可以将这些边分别加入两个集合:一个集合是外边集,为E o={(v0,v1),(v1,v2),(v2,v3)},另一个集合为内边集E w={(v3,v1),(v3,v0)}.

定理2.2. 如果一个图仅由外边组成,那么它是一棵树(无回路).反之,如果一个图中至少含有一条内边,则它必含有回路.

证明:我们通过对边进行归纳证明外边形成树.

如果一个图g0仅含有一条边,显然,g0无回路,g0是一棵树.

设图g n由n条外边组成且无回路,我们考虑加入一条新的外边的情况.假设被加入的外边为e=(v i,l i,v j,l j,l e),并假定节点v j为新引入的节点,即v j?V(g n),e?E(g n),因此,节点v j与图g n之间仅有一条路e与v i连通.通过题设我们知道,在引入节点v j之前,图g n中不存在回路,即由节点v i起始的路径集合P k={p k|(p k是g n中的路径)∧(p k起始于v i)}(其中,k=1,…,(i?1),(i+1),…,(n+1))中无回路.到达v j的路径必经过v i,即P j={p j|p j=p k+e},由于v j与g n之间仅有一条路e,因此得出?p∈P j不是回路.所以,g n+1中无回路.

现在我们考虑图g中存在至少一条内边的情况.

设e=(v i,l i,v j,l j,l e)是内边,且图g在e加入之前由外边组成.由前面的证明知道,此时g是树,所以,它的所有节点都是连通的,因此,必然存在一条路径p起始于v i而终止于v j,记为p(i,j).e?E(g n)且e连通节点v i与v j.因此,图g∪e中有回路,且该回路为(e+p(i,j)). □在图挖掘过程中,影响计算效率的原因来自两个方面:一方面是子图同构测试;另一方面是边的扩展.通过定理2.2,我们可将图的挖掘过程分为两个步骤:第1步生成频繁子树.与图的同构测试相比,子树同构测试的时间复杂性更低;第2步由频繁子树进一步扩展为频繁子图,这时,频繁子树在扩展过程中不引入新的节点,边扩展的时间复杂性降低至O(n2).但是,将挖掘过程分为两步,我们需要面对的另一个问题是,在频繁子树向频繁子图扩展的过程中,能否生成完整的结果集.

定理2.3. 1) 一个图的先深搜索生成树的最小DFS编码是唯一的.

2) 生成树的最小DFS编码确定,并给定频繁内边集,扩展之后的图也是唯一的.

证明:1) 树是无回路的图.定理2.1保证了生成树的最小DFS编码不但存在,而且唯一.

2) 假设图g为最小DFS树t所扩展.令E′=E(g)?E(t)为给定的频繁内边集.同时,根据图中生成树的定义, ?v∈V(g)?v∈V(t),即生成树t包含图g的所有节点.因此,?e∈E′,e=(v i,l i,v j,l j,l e),都能在树t中找到对应的v i∈V(t), v j∈V(t),即边e的两个节点均在t中出现,并且,由于我们考虑的是简单图,任意两节点间存在的边数不会大于1,所以,此对应关系为一一对应.综上所述,DFS树确定,且后向边集确定,得到的图也是唯一的. □定理 2.3说明,最终结果集中的任一频繁子图都存在一棵频繁子树与之对应,在由树向图的扩展过程中,由于内边的逐条加入,会形成一个完整的搜索空间.

2.2 FTGen

作为频繁子树挖掘算法,FTGen(frequent subtree generation)的输入条件为图集GD,频繁子树t(程序开始运行的时候是频率最高且DFS编码最小的边),频繁边集E.频繁边集E可通过对图集GD的扫描与边的统计得到,同时,E中的边按频率的降序排列.算法的详细定义如下:

算法1. FTGen.

输入:图集GD,频繁子树t,频繁边集E;

输出:频繁子树集T.

(1) if t≠min(t) then return; /*检查t是否具有最小DFS编码*/

(2) E′←{e是频繁外边};

(3) for E′中的每条边

李先通 等:一种高效频繁子图挖掘算法 2475

(4) E ′←E ′?e ;

(5) if (t ?e )存在于图集中; (6) then t ←t ?e ;

(7) if (T 中无t 的同构子树) then T ←T ∪t ; (8) FTGen (GD ,t ,E ,T ); (9) endfor;

算法在第1行判断频繁子树是否为最小DFS 编码.若当前子树不是最小DFS 编码,则放弃操作,以避免对重复生成的子树做进一步扩展.在生成频繁子树之前,算法在第2行找到子树t 的所有频繁外边,这样,可以保证新边加入后,t 中依然无回路.算法的第4行到第8行,循环处理子树的每一条外边,第5行检验当前外边e 能否加入t 中(扩展后的子树出现在图集GD 中,符号“?”的意义为将外边e 加入子树t ),并将这样的边与子树联接生成新的子树.若无重复的子树生成,继续对t 扩展,直至频繁外边集为空或T 中存在t 的同构子树.同时,将生成的频繁子树在第7行中加入到频繁子树的集合中.

FTGen 的挖掘结果是图集GD 中出现的频繁子树,储存在集合T 中.频繁子树将被用于进一步对边扩展以形成图,同时,频繁子树作为图的一种,是最终挖掘结果的子集.

FTGen 主要的计算开销由两部分组成:一是子树同构的测试.虽然目前有很多关于子树同构测试的研究工 作

[13?17]

,但我们采用文献[13]中提供的方法,将时间复杂性控制在????

???

?n n O log 5.2;二是频繁外边的扩展,由于采用了先深搜索,这部分的时间复杂性为O (2n

),即算法总的时间复杂性为???

??????n n O n log 25.2.

同时,定理2.1与定理2.2保证了算法的正确性.定理2.1确定了剪枝的基础,即通过DFS 最小编码与图之间的一一对应,对不符合最小DFS 编码的中间结果直接删除而不影响最终结果.定理2.2确定了外边、内边的扩展顺序与树和图之间的关系.我们在算法的挖掘过程中只增加外边,从而确保生成结果是树. 2.3 频繁子图挖掘算法(GraphGen )

算法GraphGen 用于挖掘图集中的频繁子图,其挖掘过程是先生成频繁子树,再由频繁子树扩展为频繁子图.其中,频繁子树挖掘算法采用本文算法1描述的FTGen.由树向图扩展内边的特点是,随着边数的增加,节点数保持不变.根据这个特点,我们在GraphGen 中将边扩展的时间复杂性降低至O (n 2).下面给出算法GraphGen 的详细定义:

算法2. GraphGen.

输入:图集GD , 最小支持度阈值min _sup ; 输出:频繁子图集合FG .

(1) 扫描图集并找到图集GD 中所有频繁边; (2) 删除所有非频繁边; (3) E ←{GD 中所有频繁边};

(4) 将E 中的边按DFS 编码顺序和频率的降序进行排列; (5) T ←NULL ; /*T 为频繁子树集合*/

(6) t ←e 1; /*E 中的第一条边作FTGen 的初始值*/ (7) FTGen (D ,t ,E ,T );

(8) 将集合T 中的元素按节点数与DFS 编码顺序进行排序; (9) FG ←T ; (10) for T 中的每棵树 (11) g ←t ;

(12) E ′←{e 是频繁边,且e 是内边,并能在图集中找到(g ?e )};

2476 Journal of Software 软件学报 V ol.18, No.10, October 2007

(13) for E ′中的每条边 (14) E ′←E ′?e ; (15) g ←g ?e ;

(16) if g ≠min(g ) then break;

(17) if FG 中无g 的同构子图 then FG ←FG ∪g ; (18) endfor; (19) endfor; (20) return FG ;

GraphGen 分为3个部分,算法2给出了这个算法的细节.

算法在第1部分(第1行~第6行)对图集GD 进行预处理.作为图挖掘的基础,必须从图集中提取出必要的信息,如频繁边集、频繁节点集等.在这个部分中,GraphGen 扫描图集GD 并得到频繁边集,将频繁边集按频率递减与DFS 编码值递增的顺序进行排列,供算法进一步计算.

算法在第2部分(第7行)进行频繁子树的挖掘工作,具体的挖掘过程见2.2节.

算法的第3部分(第8行~第19行)是由树向图的扩展过程.针对每一棵频繁子树,从频繁边集中找出能与之联接的内边,逐一加入到该树,从而形成频繁子图.算法在第12行找到所有能与图g 联接的频繁内边,并将这些边在第13行~第17行的子循环中加入到图g 中.算法的执行结果为频繁子图集合FG .

与FTGen 相似,算法GraphGen 主体的时间复杂性也分为两部分:一部分是子图同构的时间复杂性.由于子图同构的测试是NP 完全问题,算法在第17行进行的图同构测试,其时间复杂性为O (2n );另一部分是扩展边的时间复杂性.由于我们仅向频繁图中加入内边,通过两层循环完成,因此,这部分时间复杂性为O (n 2).边的每一次扩展,都需要检验所生成的图是否与结果集的元素重复,因此,算法总的时间复杂性为O (2n ·n 2).

在本算法中,仅考虑在稳定的图集中进行频繁子图挖掘.因此,图集GD 及GD 中的频繁边集都是确定的.由定理2.3可知,GraphGen 的挖掘结果集是完整的.

由于算法1与算法2是顺序完成的,因此,算法的整体时间复杂性为???

?

?????n n O n log 25.2.

表3给出了FTGen 和GraphGen 与其他算法时间复杂性的比较值.可以看出,本算法的优点是将整体挖掘过程分为两个部分.在挖掘频繁子树的部分,我们的算法在子图同构的计算上节省了时间;而在由树向图扩展的过 程中,我们在扩展边的过程中节省了时间,使整体时间复杂性与其他算法相比提高了)log (n n O ?倍.

Table 3 Complexity of graph mining algorithms

表3 图挖掘算法的时间复杂性分析

扩展边的复杂性

同构测试复杂性

总复杂性 n n n n CloseSpan O (2n ) O (2n ) O (2n ·2n ) FFSM O (m 4·n ·2n )

O (m 2) O (n 3·2n ) FTGen O (2n ) ????????n n O log 5.2

?

???

?????n n O n log 25.2GraphGen

O (n 2)

O (2n )

O (n 2·2n )

2.4 算法的优化

算法2的第3部分,在边的扩展方式上较之前的算法进行了较大的改进,但仍然需要进行大量的子图同构验证(第17行).由于我们的算法是由频繁子树向图的扩展,因此对具有不同节点数的子树,不会产生相同的频繁子图.基于这个特点,我们可以对算法2进行相应调整,使其在生成频繁子图的过程中,对同构子图的检验次数降至最低.

算法3. 对GraphGen 同构测试部分的改进. (1) k ←0; /*k 用于存储树的节点数*/

李先通等:一种高效频繁子图挖掘算法2477

(2) for T中的每棵树t

(3) if k<(t中的节点数) then

(4) k←t的节点数;

(5) FG←FG∪G; /*G为临时频繁子图集合*/

(6) G←Φ;

(7) endif;

(8) g←t;

(9) E′←{e是频繁内边,并能在图集中找到(g?e)};

(10) for E′中的每条边

(11) g←g?e;

(12) if g≠min(g) then break;

(13) if G中无g的同构子图 then G←G∪g;

(14) endfor;

(15) endfor;

算法3是算法2中第10行~第19行循环部分的改进.

算法3在第3行加入了对频繁子树集合T中子树节点数的检验,并将具有相同节点数的频繁子图放入中间集G中.频繁子树集合T是按照节点数增加的顺序排列的.在生成频繁子图的过程中,如果子树的节点数相同,则直接在G中检验重复子图即可,如果子树的节点数在下一次循环中增加,则将G中频繁子图并入结果集FG 并置空,加入重新生成的频繁子图.通过上述办法,可最大限度的降低用于同构子图检验的时间.

3 实验结果与分析

实验的运行环境为单CPU PC机,CPU是主频为3.2G的Intel Pentium IV超线程处理器,内存为512M,硬盘为120G,操作系统是Windows XP Professional SP2 CN.实验分别采用模拟数据和真实数据.模拟数据来自Yan 等人提供的数据模拟器,而真实数据则采用DTP(developmental therapeutics program)提供的化合物集合.

实验从算法的执行效率与最终结果集尺寸两方面将GraphGen与gSpan和FFSM进行比较与分析.针对算法执行效率的分析,我们将分别改变支持度和频繁边集的大小来观察算法的运行结果,而且,也通过改变图集的规模对算法的效率进行考查.通过比较最终结果集大小,可以从另一个侧面证明算法的正确性.

3.1 模拟数据集上的实验结果与分析

模拟数据集由数据模拟器进行模拟,该模拟器由Yan等人提供,表4中列举了该数据模拟器使用到的参数.

Table 4Parameter of data generator

表4数据模拟器的可选参数

参数意义

D 生成图的总数

E 边的标号个数

i 频繁子图的平均尺寸

L 频繁子图种子个数,生成过程中会扩展或分割等

S 将频繁子图尽量多的放入每个生成图中,可互相覆盖

T 图的平均尺寸(边数)

V 节点的标号个数

s 用于控制随机情况

在进行数据模拟的时候,我们采用类似“D10kT30L200i11V4E4”的文件名来记录生成的数据,如D10kT30 L200i11V4E4表示生成图的总数为10 000个(D10k),图的平均尺寸为30条边(T30),频繁子图的种子个数为200个(L200),频繁子图的平均尺寸为11条边(i11),节点的标号个数为4个(V4),边的标号个数为4个(E4),其他生成条件按默认值进行.

2478 Journal of Software 软件学报 V ol.18, No.10, October 2007

图3中展示了对模拟数据D10kE40I5T20L200的试验结果.横坐标表示支持度阈值,图3(a)的纵坐标表示运行时间,单位为秒,图3(b)的纵坐标表示挖掘出频繁子图的个数.在图3(a)中我们看到,GraphGen 在运行时间上比FFSM 和gSpan 小得多,在支持度为1%和2%的时候,GraphGen 的效率较gSpan 提高了3~4倍.随着支持度的增加,3个算法的运行时间趋于一致,这是由于支持度增加后频繁子图数量迅速降低降造成的.当支持度超过10%以后,算法的运行时间降低的比较缓慢.图3(b)显示了挖掘算法得到的结果集的大小,从图中可以看出,这3个算法得到的结果集相等.为较好地显示数量与支持度的关系,这个图的纵坐标使用了对数坐标.

61051041031021011010

710 1 2 3 4 5 6 7 8 9 10

gSpan FFSM GraphGen

100

1 2 3 4 5 6 7 8 9 10

1000000T o t a l i d e n t i f i e d s u b g r a p h s

1000

10000

100000

GSpan/FFSM/GraphGen

R u n t i m e (s )

Support (%)

Support (%)

(a) (b)

Fig.3 Mining result of simulated data set

图3 对模拟数据的挖掘结果

在图4(a)中,我们通过变化所生成频繁子图的规模来对这3种算法进行比较.试验方法是保持支持度为2%不变,并通过改变数据集的模拟参数i 来控制频繁子图的规模,分别将其边数的平均值控制在5~9.如图所示,随着频繁子图平均规模的扩大,gSpan 与FFSM 的运行时间扩大的较快,而GraphGen 则相对平稳.图4(b)所示为模拟数据集D100kV30I5T20L200的挖掘结果,该实验使用了更大规模的数据集D (100 000个图),但对边的标号数量未做限制.如图所示,虽然图集的规模变的更大,但由于边的标号个数降低,导致频繁边集数量下降,使算法的总体运行时间也随之降低.同时,当支持度较小时,GraphGen 的效率依然高于gSpan 三至四倍左右.

R u n t i m e (s )

1 2 3 4 5 6 7 8 9 10

30

80

130

180

230

gSpan FFSM GraphGen

R u n t i m e (s )

Frequent graph size (i)

5 6 7 8 9

90

2904906908901090gSpan FFSM GraphGen

Support (%)

(a) 频繁边集变化结果 (b) D100kV30I5T20L200 (a) 频繁边集变化结果 (b) D100kV30I5T20L200

Fig.4 Mining result of simulated data set

图4 模拟数据挖掘结果

李先通 等:一种高效频繁子图挖掘算法 2479

3.2 真实数据集上的实验结果与分析

实验的真实数据采用由美国国家癌症研究院(NCI)公布的实验数据,数据可从以下网址获得: https://www.sodocs.net/doc/291212783.html,/docs/aids/aids_data.html.DTP 中的化合物可分为3个部分,分别是CA(confirmed active), CM(confirmed moderately)和CI(confirmed inactive).这个分类是这些化合物对HIV 病毒的作用,其中,CA 含有617种化合物,CM 含有1 195种化合物,而CI 中则含有42 038种化合物.我们的实验使用了CA 与CM 两类化合物,分别称为DTP CA 和DTP CM.DTP CA 中化合物节点数与边数的最大值分别是190和196.DTP CM 中化合物的最大节点数与边数分别为220个节点和234条边.

我们将试验结果的比较通过图5和图6给出.图5是使用DTP CA 的试验结果,左侧是gSpan,FFSM 和GraphGen 这3种算法运行时间与支持度阈值的关系曲线,右侧是3个算法结果集大小的比较.图6是使用DTP CM 的实验结果,与图5相同,左侧为3个算法运行时间与支持度阈值的关系曲线,右侧是3个算法结果集的大小.当支持度较高时运行时间相差较小,我们采用对数坐标进行描述,使数据曲线更加清晰.

1

R u n t i m e (s )

3 4 5 6 7 8 9

10100100010000gSpan FFSM GraphGen

T o t a l i d e n t i f i e d s u b g r a p h s

100000

3 4 5 6 7 8 9

GSpan/FFSM/GraphGen

10000

100

Support (%)

Support (%)

Fig.5 Mining result of DTP CA 图5 DTP CA 实验结果

Fig.6 Mining result of DTP CM 图6 DTP CM 实验结果

从实验结果中可以看出,当支持度为3%或4%的时候,GraphGen 的执行效率远高于其他两种算法,这与我们的理论分析和前一小节中模拟数据的实验结果相一致.随着支持度阈值的增加,3种算法的效率逐渐趋于一致,这是由于在支持度较高的情况下,从数据集中产生的频繁边集的数量也会迅速降低.在DTP CM 数据集中,支持度升高至10%的时候,算法产生的结果集接近支持度为3%时的1/400.

通过对比模拟数据与真实数据的实验结果还可发现,当边的数量上升时,算法的运行时间也急剧上升.虽然DTP CA 和DTP CM 的数据集规模均小于模拟数据的数据集,但运行时间却高于模拟数据,这是因为随着数据集平均边数的增加,图的复杂程度也相应的增加.同时,进行图同构测试的时间复杂性为指数形式,导致了运行时间的急剧上升.

4 结 论

本文提出了一种新的频繁子图挖掘算法GraphGen,与目前常用算法相比较,GraphGen 的优点在于将算法

3 4 5 6 7 8 9 10

gSpan

FFSM GraphGen

R u n t i m e (s )

1000101

10000T o t a l i d e n t i f i e d s u b g r a p h s

3 4 5 6 7 8 9 10

1000000100

10000100000

GSpan/FFSM/GraphGen

100Support (%)

Support (%)

2480 Journal of Software软件学报 V ol.18, No.10, October 2007 的整体效率提高了)

log

(n

n

O?倍,这种提高来自于两个方面:一方面,GraphGen将子图同构问题部分地转化为子树同构问题,将时间复杂性由指数形式转化为多项式形式;另一方面,GraphGen将图中的边分为两部分,这导致扩展边时的时间复杂性降低.这两个方面恰恰是频繁子图挖掘算法中计算复杂性最高的部分.通过不同数据的实验结果也证实了上述理论分析结果.

References:

[1] Borgelt C, Berhold MR. Mining molecular fragments: Finding relevant substructures of molecules. In :Proc. of the ICDM 2002.

2002.

[2] Holder LB, Cook DJ, Djoko S. Substructures discovery in the subdue system. In: Proc. of the AAAI’94 Workshop Knowledge

Discovery in Databases. 1994. 169?180.

[3] Inokuchi A, Washio T, Okada T, Motoda H. Applying algebraic mining method of graph substructures to mutageniesis data

analysis. In: Proc. of the PAKDD. 2000.

[4] Inokuchi A, Washio T, Okada T. An apriori-based algorithm for mining frequent substructures from graph data. In: Proc. of the

PKDD 2000, LNAI 1910. 2000. 13?23.

[5] Kuramochi M, Karypis G. Frequent subgraph discovery. In: Proc. of the ICDM 2001. 2001.

[6] Yan Y Han J. gSpan: Graph-Based substructure pattern mining. In: Proc. of the 2002 Int’l Conf. on Data Mining (ICDM 2002).

Maebashi, 2002.

[7] Washio T, Motoda H. State of the art of graph-based data mining. In: Proc. of the SIGKDD 2003.

[8] Yan X, Han J. CloseGraph: Mining closed frequent graph patterns. In: Proc. of the 9th ACM SIGKDD Int’l Conf. on Knowledge

Discovery and Data Mining (KDD2003). Washington, 2003.

[9] Han J, Wang W, Prins J. Efficient mining of frequent subgraphs in the presence of isomorphism. In: Proc. of the IEEE Int’l Conf.

on Data Mining (ICDM 2003). 2003.

[10] Jin R, Wang C, Polshakov D, Parthasarathy S, Agrawal G. Discovering frequent topological structures from graph datasets. In: Proc.

of the KDD 2005. Chicago, 2005. 606?611.

[11] Inokuchi A. Mining generalized substructures from a set of labeled graphs. In: Proc. of the IEEE Int’l Conf. on Data Mining (ICDM

2004), 0-7695-2142-8/04.

[12] Cohen M, Gudes E. Diagonally subgraphs pattern mining. In: Proc. of the DMKD 2004. Paris, 2004.

[13] Shamir R, Tsur D. Faster subtree isomorphism. In: Proc. of the IEEE’97, 0-8186-8037-7/97.

[14] Ueda N, Aoki-Kinoshita KF, Yamaguchi A, Akutsu T, Mamitsuka H. A probabilistic model for mining labeled ordered trees:

Capturing patterns in carbohydrate sugar chains. IEEE Trans. on Knowledge and Data Engineering, 2005,17(8):1051.

[15] Buss SR. Alogtime algorithms for tree isomorphism, comparison and canonization, In: Computational Logic and Proof Theory,

Proc. of the 5th G?del Colloquium’97, Lecture Notes in Computer Science #1289. Berlin: Springer-Verlag, 1997. 18?33.

[16] Yang R, Kalnis P, Tung AKH. Similarity evaluation on tree-structured data. In: Proc. of the SIGMOD 2005. Baltimore, 2005.

[17] Rückert U, Kramer S. Frequent free tree discovery in graph data. In: Symp. on Applied Computing archive, Proc. of the 2004 ACM

Symp. on Applied Computing. SESSION: Data Mining (DM). 2004. 564?570.

李先通(1973－),男,黑龙江哈尔滨人,博士生,主要研究领域为频繁模式挖掘.

高宏(1966－),女,博士,教授,博士生导师,主要研究领域为数据库,数据仓库,计算生物学

.

李建中(1950－),男,博士,教授,博士生导

师,CCF高级会员,主要研究领域为数据

库,并行计算.

数据挖掘领域的十大经典算法原理及应用

数据挖掘领域的十大经典算法原理及应用 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1.C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV 机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面

频繁项集挖掘的Apriori改进算法研究

１０００－５８６２（２０１１）０５－０４９８－０５ 频繁项集挖掘的Ａｐｒｉｏｒｉ改进算法研究 栗晓聪滕少华 广东工业大学计算机学院，广东广州５１０００６ 摘要：针对Ａｐｒｉｏｒｉ算法的不足，提出了一种新的优化算法—ＩＡｐｒｉｏｒｉ．该算法应用散列技术优化产生频繁－２项集，优化连接操作减少连接判断的次数，通过对候选项集编码来减少扫描数据库的次数，优化逻辑“与”运算减少不必要的“与”操作次数，缩短生成频繁项集的时间．ＩＡｐｒｉｏｒｉ算法仅需３次扫描数据库．研究结果表明，该算法具有快速、直观、节省内存等优点． Ａｐｒｉｏｒｉ算法；频繁项集；候选项集；ＩＡｐｒｉｏｒｉ算法 ＴＰ３１１Ａ ２０１１－０７－１２ 广东省自然科学基金（０６０２１４８４，　９１５１００９００１０００００７）和广州市越秀区科技计划（２００７－ＧＸ－０２３）资助项目． 滕少华（１９６２－），男，江西南昌人，教授，博士，主要从事协同工作、网络安全和数据挖掘方面的研究．

第５期

２０１１年

第５期

＠＠［１］王琳，滕少华，伍乃骐，等．基于协议分析的散列模式入侵检 测方法［Ｊ］．计算机工程与设计，２００６，２７（１）：　５３－５５．＠＠［２］颜跃进，李舟军，陈火旺，等．基于ＦＰ－Ｔｒｅｅ有效挖掘最大频 繁项集［Ｊ］．软件学报，２００５，１６（２）：　２１５－２２２． ＠＠［３］郭宇红，童云海，唐世渭，等．基于ＦＰ－Ｔｒｅｅ的反向频繁项集 挖掘［Ｊ］．软件学报，２００８，１９（２）：　３３８－３５０． ＠＠［４］　Ｈａｎ　Ｊｉａｗｅｉ，　Ｐｅｉ　Ｊｉａｎ，　Ｙｉｎ　Ｙｉｗｅｎ，　ｅｔ　ａｌ．　Ｍｉｎｉｎｇ　ｆｒｅｑｕｅｎｔ　ｍａｔｔｅｒｎｓ ｗｉｔｈｏｕｔ　ｃａｎｄｉｄａｔｅ　ｇｅｎｅｒａｔｉｏｎ　［Ｊ］．　Ｄａｔａ　Ｍｉｎｎｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒ，　２００４，　８（１）：　５３－８７． ＠＠［５］Ｊｉａｗｅｉ　Ｈａｎ，Ｍｉｃｈｅｌｉｎｅ　Ｋａｍｂｅｒ．数据挖掘概念与技术［Ｍ］．范 明，孟小峰，译．北京：机械工业出版社，２００７：１６７－１６１．＠＠［６］　Ｗｕ　Ｘｉｎｇｄｏｎｇ，　Ｖｉｐｉｎ　Ｋｕｍａｒ，　Ｒｏｓｓ　Ｑｕｉｎｌａｎ　Ｊ．　Ｔｏｐ　１０　ａｌｇｏｒｉｔｈｍｓ　 ｉｎ　ｄａｔａ　ｍｉｎｉｎｇ　［Ｊ］．　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，　２００８，１４（１）：　１－３７． ＠＠［７］陈耿，朱玉全，杨鹤标，等．关联规则挖掘中若干关键技术的 研究［Ｊ］．计算机研究与发展，２００５，４２（１０）：　１７８５－１７８９．＠＠［８］徐章艳，刘美玲，张师超，等．Ａｐｒｉｏｒｉ算法的三种优化方法［Ｊ］． 计算机工程与应用，２００４，４０（３６）：　１９０－１９３． ＠＠［９］傅慧，邹海．基于待与项集的频繁项集挖掘算法的研究［Ｊ］． 计算机工程与设计，２００９，３０（１）：　１２９－１３１． ＠＠［１０］徐健辉．生成频繁项集的逻辑“与”运算算法［Ｊ］．计算机应用， ２００４，２４（１１）：　８８－９０． ＠＠［１１］俞燕燕，李绍滋．基于散列的关联规则ＡｐｒｉｏｒｉＴｉｄ改进算法［Ｊ］． 计算机工程，２００８，３４（５）：　６０－６２． ＠＠［１２］柴华昕，王勇．Ａｐｒｉｏｒｉ挖掘频繁项集算法的改进［Ｊ］．计算机 工程与应用，２００７，４３（２４）：　１５８－１６１． Ｔｈｅ　Ｒｅｓｅａｒｃｈ　ｏｎ　Ｉｍｐｒｏｖｅｍｅｎｔ　ｏｆ　Ａｐｒｉｏｒｉ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ Ｍｉｎｉｎｇ　Ｆｒｅｑｕｅｎｔ　Ｉｔｅｍｓｅｔｓ　 ＬＩ　Ｘｉａｏ－ｃｏｎｇＴＥＮＧ　Ｓｈａｏ－ｈｕａ

一种高效频繁子图挖掘算法.2007,18(10)_2469-2480

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.sodocs.net/doc/291212783.html, Journal of Software , Vol.18, No.10, October 2007, pp.2469?2480 https://www.sodocs.net/doc/291212783.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/291212783.html,, https://www.sodocs.net/doc/291212783.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/291212783.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.四年级

流数据频繁模式挖掘算法汇总

频繁模式挖掘 常用的概念： 事务数据库： 时间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}

学习18大经典数据挖掘算法

学习18大经典数据挖掘算法 本文所有涉及到的数据挖掘代码的都放在了github上了。 地址链接: https://https://www.sodocs.net/doc/291212783.html,/linyiqun/DataMiningAlgorithm 大概花了将近2个月的时间，自己把18大数据挖掘的经典算法进行了学习并且进行了代码实现，涉及到了决策分类，聚类，链接挖掘，关联挖掘，模式挖掘等等方面。也算是对数据挖掘领域的小小入门了吧。下面就做个小小的总结，后面都是我自己相应算法的博文链接，希望能够帮助大家学习。 1.C4.5算法。C4.5算法与ID3算法一样，都是数学分类算法，C4.5算法是ID3算法的一个改进。ID3算法采用信息增益进行决策判断，而C4.5采用的是增益率。 详细介绍链接：https://www.sodocs.net/doc/291212783.html,/androidlushangderen/article/details/42395865 2.CART算法。CART算法的全称是分类回归树算法，他是一个二元分类，采用的是类似于熵的基尼指数作为分类决策，形成决策树后之后还要进行剪枝，我自己在实现整个算法的时候采用的是代价复杂度算法， 详细介绍链接：https://www.sodocs.net/doc/291212783.html,/androidlushangderen/article/details/42558235 3.KNN(K最近邻)算法。给定一些已经训练好的数据，输入一个新的测试数据点，计算包含于此测试数据点的最近的点的分类情况，哪个分类的类型占多数，则此测试点的分类与此相同，所以在这里,有的时候可以复制不同的分类点不同的权重。近的点的权重大点，远的点自然就小点。 详细介绍链接：https://www.sodocs.net/doc/291212783.html,/androidlushangderen/article/details/42613011 4.Naive Bayes(朴素贝叶斯)算法。朴素贝叶斯算法是贝叶斯算法里面一种比较简单的分类算法，用到了一个比较重要的贝叶斯定理，用一句简单的话概括就是条件概率的相互转换推导。 详细介绍链接：https://www.sodocs.net/doc/291212783.html,/androidlushangderen/article/details/42680161 5.SVM(支持向量机)算法。支持向量机算法是一种对线性和非线性数据进行分类的方法，非线性数据进行分类的时候可以通过核函数转为线性的情况再处理。其中的一个关键的步骤是搜索最大边缘超平面。 详细介绍链接：https://www.sodocs.net/doc/291212783.html,/androidlushangderen/article/details/42780439 6.EM(期望最大化)算法。期望最大化算法，可以拆分为2个算法，1个E-Step期望化步骤,和1个M-Step最大化步骤。他是一种算法框架，在每次计算结果之后，逼近统计模型参数的最大似然或最大后验估计。

频繁子图模式挖掘

数据挖掘与商务智能读书报告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、基于网格的聚类算法 主要思想：基于网格的聚类算法是一种基于网格的具有多分辨率的聚类方法。它首先将数据集的分布空间划分为若干个规则网格(如超矩形单元)或灵活的网格(如任意形状的多

数据挖掘十大待解决问题

数据挖掘领域10大挑战性问题与十大经典算法 2010-04-21 20:05:51| 分类：技术编程| 标签：|字号大中小订阅 作为一个数据挖掘工作者，点可以唔知呢。 数据挖掘领域10大挑战性问题： 1.Developing a Unifying Theory of Data Mining 2.Scaling Up for High Dimensional Data/High Speed Streams 3.Mining Sequence Data and Time Series Data 4.Mining Complex Knowledge from Complex Data 5.Data Mining in a Network Setting 6.Distributed Data Mining and Mining Multi-agent Data 7.Data Mining for Biological and Environmental Problems 8.Data-Mining-Process Related Problems 9.Security, Privacy and Data Integrity 10.Dealing with Non-static, Unbalanced and Cost-sensitive Data 数据挖掘十大经典算法 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm

十 大 经 典 排 序 算 法 总 结 超 详 细

数据挖掘十大经典算法，你都知道哪些？ 当前时代大数据炙手可热，数据挖掘也是人人有所耳闻，但是关于数据挖掘更具体的算法，外行人了解的就少之甚少了。 数据挖掘主要分为分类算法，聚类算法和关联规则三大类，这三类基本上涵盖了目前商业市场对算法的所有需求。而这三类里又包含许多经典算法。而今天，小编就给大家介绍下数据挖掘中最经典的十大算法，希望它对你有所帮助。 一、分类决策树算法C4.5 C4.5，是机器学习算法中的一种分类决策树算法，它是决策树(决策树，就是做决策的节点间的组织方式像一棵倒栽树)核心算法ID3的改进算法，C4.5相比于ID3改进的地方有： 1、用信息增益率选择属性 ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（shang），一种不纯度度量准则，也就是熵的变化值，而 C4.5用的是信息增益率。区别就在于一个是信息增益，一个是信息增益率。 2、在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致过拟。 3、能对非离散数据和不完整数据进行处理。 该算法适用于临床决策、生产制造、文档分析、生物信息学、空间数据建模等领域。 二、K平均算法

K平均算法（k-means algorithm）是一个聚类算法，把n个分类对象根据它们的属性分为k类（kn）。它与处理混合正态分布的最大期望算法相似，因为他们都试图找到数据中的自然聚类中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。 k-Means 算法常用于图片分割、归类商品和分析客户。 三、支持向量机算法 支持向量机(Support Vector Machine)算法，简记为SVM，是一种监督式学习的方法，广泛用于统计分类以及回归分析中。 SVM的主要思想可以概括为两点： (1)它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分； (2)它基于结构风险最小化理论之上，在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。 四、The Apriori algorithm Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段“频繁项集”思想的递推算法。其涉及到的关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支

数据挖掘实验三应用 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-项集

数据挖掘十大算法

数据挖掘十大算法 数据挖掘十大算法—K 近邻算法 k -近邻算法是基于实例的学习方法中最基本的，先介绍基于实例学习的相关概念。 一、基于实例的学习。 1、已知一系列的训练样例，很多学习方法为目标函数建立起明确的一般化描述；但与此不同，基于实例的学习方法只是简单地把训练样例存储起来。 从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。 2、基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上，很多技术只建立目标函数的局部逼近，将其应用于与新查询实例邻近的实例，而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂，但它可用不太复杂的局部逼近描述时，这样做有显著的优势。 3、基于实例方法的不足： （1）分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。所以，如何有效地索引训练样例，以减少查询时所需计算是一个重要的实践问题。（2）当从存储器中检索相似的训练样例时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。 二、k-近邻法基于实例的学习方法中最基本的是k -近邻算法。这个算法假定所有的实例对应于n 维欧氏空间?n 中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲，把任意的实例x 表示为下面的特征向量：其中a r (x ) 表示实例x 的第r 个属性值。那么两个实例x i 和x j 间的距离定义为d (x i , x j ) ，其中： 说明： 1、在最近邻学习中，目标函数值可以为离散值也可以为实值。 2、我们先考虑学习以下形式的离散目标函数。其中V 是有限集合 {v 1，... v s }。下表给出了逼近离散目标函数的k-近邻算法。 3、正如下表中所指出的，这个算法的返回值f' (x q ) 为对f (x q ) 的估计，它就是距离x q 最近的k 个训练样例中最普遍的f 值。 4、如果我们选择k =1，那么“1-近邻算法”

数据挖掘算法

数据挖掘的10大经典算法 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在 构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm

数据挖掘一些面试题总结

数据挖掘一些面试题总结（Data Mining） 摘录一段 企业面对海量数据应如何具体实施数据挖掘，使之转换成可行的结果/模型？ 首先进行数据的预处理，主要进行数据的清洗，数据清洗，处理空缺值，数据的集成，数据的变换和数据规约。 请列举您使用过的各种数据仓库工具软件（包括建模工具，ETL工具，前端展现工具，OLAP Server、数据库、数据挖掘工具）和熟悉程度。 ETL工具：Ascential DataStage ，IBM warehouse MANAGER、Informatica公司的PowerCenter、Cognos 公司的DecisionStream 市场上的主流数据仓库存储层软件有：SQL SERVER、SYBASE、ORACLE、DB2、TERADATA 请谈一下你对元数据管理在数据仓库中的运用的理解。 元数据能支持系统对数据的管理和维护，如关于数据项存储方法的元数据能支持系统以最有效的方式访问数据。具体来说,在数据仓库系统中，元数据机制主要支持以下五类系统管理功能： （１）描述哪些数据在数据仓库中； （２）定义要进入数据仓库中的数据和从数据仓库中产生的数据； （３）记录根据业务事件发生而随之进行的数据抽取工作时间安排； （４）记录并检测系统数据一致性的要求和执行情况； （５）衡量数据质量。 数据挖掘对聚类的数据要求是什么？ （1）可伸缩性 （2）处理不同类型属性的能力 （3）发现任意形状的聚类 （4）使输入参数的领域知识最小化 （5）处理噪声数据的能力 （6）对于输入顺序不敏感 （7）高维性 （8）基于约束的聚类 （9）可解释性和可利用性 简述Apriori算法的思想，谈谈该算法的应用领域并举例。 思想：其发现关联规则分两步，第一是通过迭代，检索出数据源中所有烦琐项集，即支持度不低于用户设定的阀值的项即集，第二是利用第一步中检索出的烦琐项集构造出满足用户最小信任度的规则，其中，第一步即挖掘出所有频繁项集是该算法的核心，也占整个算法工作量的大部分。 在商务、金融、保险等领域皆有应用。在建筑陶瓷行业中的交叉销售应用，主要采用了Apriori 算法 通过阅读该文挡，请同学们分析一下数据挖掘在电子商务领域的应用情况（请深入分析并给出实例，切忌泛泛而谈）？ 单选题 1. 某超市研究销售纪录数据后发现，买啤酒的人很大概率也会购买尿布，这种属于数据挖掘的哪类问题？(A) A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理

数据挖掘中十大经典算法

数据挖掘十大经典算法 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。 5. 最大期望(EM)算法 在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。 6. PageRank PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里?佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个