`
lovnet
  • 浏览: 6670895 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

数据挖掘和知识发现的技术、方法及应用

阅读更多

数据挖掘和知识发现的技术、方法及应用

一幅凝固的油画

Keywords:

data miningKnowledge discovery in databasesDMKDDCRISPDMInternet

概念

基于Internet的全球信息系统的发展使我们拥有了前所未有的丰富数据。大量信息在给人们带来方便的同时也带来了一大堆问题:第一是信息过量,难以消化;第二是信息真假难以辨识;第三是信息安全难以保证;第四是信息形式不一致,难以统一处理。数据丰富、知识贫乏已经成为一个典型问题。Data Mining数据挖掘)的目的就是有效地从海量数据中提取出需要的答案,实现“数据-〉信息-〉知识-〉价值”的转变过程。

Data Mining数据挖掘)是指用非平凡的方法从海量的数据中抽取出潜在的、有价值的知识(模型或规则)的过程。该术语还有其他一些同义词:数据库中的知识发现Knowledge discovery in databases)、信息抽取(Information extraction)、信息发现(Information discovery)、智能数据分析(Intelligent data analysis)、探索式数据分析(exploratory data analysis)、信息收获(information harvesting)、数据考古(data archeology)等。

数据挖掘的发展历程大致如下:

1989 IJCAI会议: 数据库中的知识发现讨论专题

–Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley, 1991)

•1991-1994 KDD讨论专题

–Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)

•1995-1998 KDD国际会议 (KDD’95-98)

–Journal of Data Mining and Knowledge Discovery (1997)

•1998 ACM SIGKDD, SIGKDD’1999-2002 会议,以及SIGKDD Explorations

数据挖掘方面更多的国际会议

–PAKDD, PKDD, SIAM-Data Mining, (IEEE) ICDM, DaWaK, SPIE-DM, etc.

Data Mining数据挖掘是数据库研究、开发和应用最活跃的一个分支,是多学科的交叉领域,它涉及数据库技术、人工智能、机器学习、神经网络、数学、统计学、模式识别、知识库系统、知识获取、信息提取、高性能计算、并行计算、数据可视化等多方面知识。

数据挖掘技术从一开始就是面向应用的,它不仅是面向特定数据库的简单检索查询调用,而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理,以指导实际问题的求解,企图发现事件间的相互关联,甚至利用已有的数据对未来的活动进行预测。例如加拿大BC省电话公司要求加拿大SimonFraser大学KDD研究组,根据其拥有十多年的客户数据,总结、分析并提出新的电话收费和管理办法,制定既有利于公司又有利于客户的优惠政策。这样一来,就把人们对数据的应用,从低层次的末端查询操作,提高到为各级经营决策者提供决策支持。这种需求驱动力,比数据库查询更为强大。同时,这里所说的数据挖掘,不是要求发现放之四海而皆准的真理,也不是要去发现崭新的自然科学定理和纯数学公式,更不是什么机器定理证明。所有发现的知识都是相对的,是有特定前提和约束条件、面向特定领域的,同时还要能够易于被用户理解,最好能用自然语言表达发现结果。因此数据挖掘的研究成果是很讲求实际的。

技术

Data Mining数据挖掘)主要任务有数据汇总、概念描述、分类、聚类、相关性分析、偏差分析、建模等。具体技术包括:

统计分析(statistical analysis

常见的统计方法有回归分析(多元回归、自回归等)、判别分析(贝叶斯分析、费歇尔判别、非参数判别等)、聚类分析(系统聚类、动态聚类等)和探索性分析(主元分析法、相关分析法等)。其处理过程可以分为三个阶段:搜集数据、分析数据和进行推理。

决策树(decision tree

决策树是一棵树,树的根节点是整个数据集合空间,每个分节点是对一个单一变量的测试,该测试将数据集合空间分割成两个或更多块。每个叶节点是属于单一类别的记录。首先,通过训练集生成决策树,再通过测试集对决策树进行修剪。决策树的功能是预言一个新的记录属于哪一类。

决策树分为分类树和回归树两种,分类树对离散变量做决策树,回归树对连续变量做决策树。

通过递归分割的过程来构建决策树:1 寻找初始分裂,整个训练集作为产生决策树的集合,训练集每个记录必须是已经分好类的。决定哪个属性(Field)域作为目前最好的分类指标。一般的做法是穷尽所有的属性域,对每个属性域分裂的好坏做出量化,计算出最好的一个分裂。量化的标准是计算每个分裂的多样性(diversity)指标GINI指标。2 树增长到一棵完整的树,重复第一步,直至每个叶节点内的记录都属于同一类。3 数据的修剪,去掉一些可能是噪音或者异常的数据。

基本算法(贪心算法)为:自上而下分而治之的方法,开始时,所有的数据都在根节点;属性都是种类字段 (如果是连续的,将其离散化);所有记录用所选属性递归的进行分割;属性的选择是基于一个启发式规则或者一个统计的度量 (, information gain)。停止分割的条件:一个节点上的数据都是属于同一个类别;没有属性可以再用于对数据进行分割。

伪代码(Building Tree)为:

Procedure BuildTree(S){

用数据集S初始化根节点R

用根结点R初始化队列Q

While Q is not Empty do {

取出队列Q中的第一个节点N

if N 不纯 (Pure) {

for 每一个属性 A

估计该节点在A上的信息增益

选出最佳的属性,将N分裂为N1N2

}

}

}

属性选择的统计度量为:信息增益——Information gain (ID3/C4.5),所有属性假设都是种类字段,经过修改之后可以适用于数值字段;基尼指数——Gini index (IBM IntelligentMiner),能够适用于种类和数值字段。

关联规则(correlation rules

规则反映了数据项中某些属性或数据集中某些数据项之间的统计相关性,其一般形式为:<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 9pt; HEIGHT: 17.25pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image001.wmz"></imagedata></shape>X1Xn<shape id="_x0000_i1026" style="WIDTH: 15pt; HEIGHT: 12pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image003.wmz"></imagedata></shape>Y[C,S],表示由X1Xn可以预测Y,其中可信度为C,支持度为S

I={i1, i2,…, im}是二进制文字的集合,其中的元素称为项(item)。记D为交易(transaction)T的集合,这里交易T是项的集合,并且TÍI 。对应每一个交易有唯一的标识,如交易号,记作TID。设X是一个I中项的集合,如果XÍT,那么称交易T包含X

一个关联规则是形如XÞY的蕴涵式,这里XÌI, YÌI,并且XÇY=F。规则XÞY在交易数据库D中的支持度support)是交易集中包含XY的交易数与所有交易数之比,记为support(XÞY),即

support(XÞY)=|{T:XÈYÍTTÎD}|/|D|

规则XÞY在交易集中的可信度confidence)是指包含XY的交易数与包含X的交易数之比,记为confidence(XÞY),即

confidence(XÞY)=|{T: XÈYÍTTÎD}|/|{T:XÍTTÎD}|

给定一个交易集D,挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度(minsupp)和最小可信度(minconf)的关联规则。

基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的,它显示了这些变量之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将其进行动态的分割,或者直接对原始的数据进行处理,当然数值型关联规则中也可以包含种类变量。基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同的层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考虑。基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。在单维的关联规则中,我们只涉及到数据的一个维,如用户购买的物品;而在多维的关联规则中,要处理的数据将会涉及多个维。

Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题,其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化,如引入随机采样、并行的思想等,以提高算法挖掘规则的效率;提出各种变体,如泛化的关联规则、周期关联规则等,对关联规则的应用进行推广。

Agrawal等在1993年设计了一个基本算法,提出了挖掘关联规则的一个重要方法 — 这是一个基于两阶段频集思想的方法,将关联规则挖掘算法的设计可以分解为两个子问题:

1) 找到所有支持度大于最小支持度的项集(Itemset),这些项集称为频集(Frequent Itemset)。

2) 使用第1步找到的频集产生期望的规则。

这里的第2步相对简单一点。如给定了一个频集Y=I1I2...Ikk³2IjI,产生只包含集合{I1I2...Ik}中的项的所有规则(最多k),其中每一条规则的右部只有一项,(即形如[Y-Ii]ÞIi"1£i£k)。一旦这些规则被生成,那么只有那些大于用户给定的最小可信度的规则才被留下来。对于规则右部含两个以上项的规则,在其以后的工作中进行了研究。为了生成所有频集,使用了递推的方法。其核心思想如下:

L1 = {large 1-itemsets};

for (k=2; Lk-1¹F; k++)

{

Ck=apriori-gen(Lk-1); //新的候选集

for all transactions tÎD

{

Ct=subset(Ck,t); //事务t中包含的候选集

for( all candidates cÎ Ct )

c.count++;

}

Lk={cÎ Ck |c.count³minsup}

}

Answer=ÈkLk;

首先产生频繁1-项集L1,然后是频繁2-项集L2,直到有某个r值使得Lr为空,这时算法停止。这里在第k次循环中,过程先产生候选k-项集的集合CkCk中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集,最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk,这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库,即如果频集最多包含10个项,那么就需要扫描交易数据库10遍,这需要很大的I/O负载。

Agrawal等引入了修剪技术(Pruning)来减小候选集Ck的大小,由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质:一个项集是频集当且仅当它的所有子集都是频集。那么,如果Ck中某个候选项集有一个(k-1)-子集不属于Lk-1,则这个项集可以被修剪掉不再被考虑,这个修剪过程可以降低计算所有的候选集的支持度的代价。

基于Apriori的频集方法即使进行了优化,但是Apriori方法一些固有的缺陷还是无法克服:1) 可能产生大量的候选集。当长度为1的频集有10000个的时候,长度为2的候选集个数将会超过<chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="10" unitname="m" w:st="on"><span lang="EN-US">10M</span></chmetcnv>。还有就是如果要生成一个很长的规则的时候,要产生的中间元素也是巨大量的。2) 无法对稀有信息进行分析。由于频集使用了参数minsup,所以就无法对小于minsup的事件进行分析;而如果将minsup设成一个很低的值,那么算法的效率就成了一个很难处理的问题。以下两种方法,分别用于解决以上两个问题。

解决问题1的一种方法采用了一种FP-growth的方法。他们采用了分而治之的策略:在经过了第一次的扫描之后,把数据库中的频集压缩进一棵频繁模式树(FP-tree),同时依然保留其中的关联信息。随后我们再将FP-tree分化成一些条件库,每个库和一个长度为1的频集相关。然后再对这些条件库分别进行挖掘。当原始数据量很大的时候,也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明,FP-growth对不同长度的规则都有很好的适应性,同时在效率上较之Apriori算法有巨大的提高。

第二个问题是基于这个的一个想法:apriori算法得出的关系都是频繁出现的,但是在实际的应用中,我们可能需要寻找一些高度相关的元素,即使这些元素不是频繁出现的。在apriori算法中,起决定作用的是支持度,而我们现在将把可信度放在第一位,挖掘一些具有非常高可信度的规则。对于这个问题的一个解决方法的整个算法基本上分成三个步骤:计算特征、生成候选集、过滤候选集。在三个步骤中,关键的地方就是在计算特征时Hash方法的使用。在考虑方法的时候,有几个衡量好坏的指数:时空效率、错误率和遗漏率。基本的方法有两类:Min_Hashing(MH)Locality_Sensitive_Hashing(LSH)Min_Hashing的基本想法是:将一条记录中的头k个为1的字段的位置作为一个Hash函数。Locality_Sentitive_Hashing的基本想法是:将整个数据库用一种基于概率的方法进行分类,使得相似的列在一起的可能性更大,不相似的列在一起的可能性较小。对这两个方法比较一下发现,MH的遗漏率为零,错误率可以由k严格控制,但是时空效率相对的较差。LSH的遗漏率和错误率是无法同时降低的,但是它的时空效率却相对的好很多。所以应该视具体的情况而定。最后的实验数据也说明这种方法的确能产生一些有用的规则。

基于范例的推理(case-based reasoning

范例推理是直接使用过去的经验或解法来求解给定的问题。范例通常是一种已经遇到过并且有解法的具体问题。当给定一个特定问题时,范例推理就检索范例库,寻找相似的范例。如果存在相似的范例,其解法就可以用来求解新问题。而且该新问题被加入进范例库,已备将来搜索使用。

模糊集(fuzzy set

模糊集是表示和处理不确定性数据的重要方法,它不仅可以处理不完全数据、噪声或不精确数据,还可以用于开发数据的不确定性模型,能够提供比传统方法更灵巧、更平滑的性能。

粗糙集(rough set

粗糙集是相对较新的一种数学工具,用于处理含糊性和不确定性,在数据挖掘中可以发挥重要作用。粗糙集是由集合的下近似、上近似来定义的。下近似中的每一个成员都是该集合的确定成员,而不是上近似中的成员则肯定不是该集合的成员。粗糙集的上近似是下近似和边界区的并。边界区的成员可能是该集合的成员,但不是确定的成员。可以认为粗糙集是具有三值隶属函数的模糊集,它常与关联规则、分类和聚类方法结合使用,一般不单用。

贝叶斯信念网络(Bayesian belief network

贝叶斯信念网络是概率分布的图表示,它是一种有向无环图,结点表示属性变量,边表示属性变量之间的概率依赖关系。和每个结点相关的是条件概率分布,用于描述该结点和其父结点之间的关系。

定义1:给定一个随机变量集<shape id="_x0000_i1027" style="WIDTH: 12pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75" o:bullet="t"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image005.wmz"></imagedata></shape> ={<shape id="_x0000_i1028" style="WIDTH: 57.75pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image007.wmz"></imagedata></shape>},其中<shape id="_x0000_i1029" style="WIDTH: 15.75pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image009.wmz"></imagedata></shape>是一个<shape id="_x0000_i1030" style="WIDTH: 12.75pt; HEIGHT: 11.25pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image011.wmz"></imagedata></shape>维向量。贝叶斯信念网络了说明<shape id="_x0000_i1031" style="WIDTH: 12pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image013.wmz"></imagedata></shape>上的一条联合条件概率分布。贝叶斯信念网络定义如下:

<shape id="_x0000_i1032" style="WIDTH: 60pt; HEIGHT: 15.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image014.wmz"></imagedata></shape>

第一部分<shape id="_x0000_i1033" style="WIDTH: 12.75pt; HEIGHT: 14.25pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image016.wmz"></imagedata></shape>是一个有向无环图,其顶点对应于有限集<shape id="_x0000_i1034" style="WIDTH: 12pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image018.wmz"></imagedata></shape>中的随机变量<shape id="_x0000_i1035" style="WIDTH: 57.75pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image007.wmz"></imagedata></shape>。其弧代表一个函数依赖关系。如果有一条弧由变量<shape id="_x0000_i1036" style="WIDTH: 11.25pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image019.wmz"></imagedata></shape><shape id="_x0000_i1037" style="WIDTH: 14.25pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image021.wmz"></imagedata></shape>,则<shape id="_x0000_i1038" style="WIDTH: 11.25pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image019.wmz"></imagedata></shape><shape id="_x0000_i1039" style="WIDTH: 14.25pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image021.wmz"></imagedata></shape>的双亲或者直接前驱,而<shape id="_x0000_i1040" style="WIDTH: 14.25pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image021.wmz"></imagedata></shape>则是<shape id="_x0000_i1041" style="WIDTH: 11.25pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image019.wmz"></imagedata></shape>的后继。一旦给定其双亲,图中的每个变量独立于图中该节点的非后继。在图<shape id="_x0000_i1042" style="WIDTH: 12.75pt; HEIGHT: 14.25pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image016.wmz"></imagedata></shape><shape id="_x0000_i1043" style="WIDTH: 15.75pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image023.wmz"></imagedata></shape>的所有双亲变量用集合<shape id="_x0000_i1044" style="WIDTH: 39pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image024.wmz"></imagedata></shape>

第二部分<shape id="_x0000_i1058" style="WIDTH: 9.75pt; HEIGHT: 14.25pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image026.wmz"></imagedata></shape>代表用于量化网络的一组参数。对于每一个<shape id="_x0000_i1059" style="WIDTH: 15.75pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image028.wmz"></imagedata></shape><shape id="_x0000_i1060" style="WIDTH: 39pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image029.wmz"></imagedata></shape>的取值<shape id="_x0000_i1061" style="WIDTH: 15.75pt; HEIGHT: 20.25pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image031.wmz"></imagedata></shape>,存在如下一个参数:<shape id="_x0000_i1045" style="WIDTH: 122.25pt; HEIGHT: 21.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image033.wmz"></imagedata></shape>,它指明了在给定在<shape id="_x0000_i1046" style="WIDTH: 39pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image029.wmz"></imagedata></shape>发生的情况下<shape id="_x0000_i1047" style="WIDTH: 15.75pt; HEIGHT: 20.25pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image031.wmz"></imagedata></shape>事件发生的条件概率。因此实际上一个贝叶斯信念网络给定了变量集合<shape id="_x0000_i1048" style="WIDTH: 12pt; HEIGHT: 12.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image035.wmz"></imagedata></shape>上的联合条件概率分布:

<shape id="_x0000_i1049" style="WIDTH: 188.25pt; HEIGHT: 33.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image036.wmz"></imagedata></shape>

贝页斯网络构造算法可以表示如下:给定一组训练样本<shape id="_x0000_i1050" style="WIDTH: 83.25pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image038.wmz"></imagedata></shape><shape id="_x0000_i1051" style="WIDTH: 12pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image040.wmz"></imagedata></shape><shape id="_x0000_i1052" style="WIDTH: 15.75pt; HEIGHT: 18pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image009.wmz"></imagedata></shape>的实例,寻找一个最匹配该样本的贝叶斯信念网络。常用的学习算法通常是引入一个评估函数<shape id="_x0000_i1053" style="WIDTH: 42.75pt; HEIGHT: 15.75pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///C:%5CDOCUME~1%5CRoger%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image042.wmz"></imagedata></shape>,使用该函数来评估每一个可能的网络结构与样本之间的契合度,并从所有这些可能的网络结构中寻找一个最优解。常用的评价函数有贝叶斯权矩阵(Bayesian Score Metric)及最小描述长度函数(Minimal Description Length)

支持向量机(support vector machine

支持向量机(SVM)建立在计算学习理论的结构风险最小化原则之上。其主要思想是针对两类分类问题,在高维空间中寻找一个超平面作为两类的分割,以保证最小的分类错误率。它的一个重要优点是可以处理线性不可分的情形。

隐马尔科夫模型(Hidden Markov model

马尔科夫过程是描述系统的一种方法,由俄国有机化学家马尔科夫于1870年提出,其组成有:系统状态、系统初始状态概率和状态之间转移的概率。隐马尔科夫模型包括:模型中状态数、模型中的输出符号数、模型中的状态集、状态转移的概率分布和初始状态分布等。隐马尔科夫模型有三个基本问题:识别问题(给定一个输出序列和模型,模型可能创建的序列的概率是什么?)、序列问题(给定一个输出序列和模型,什么最可能的状态序列可以创建输出序列?)和训练问题(给定一个输出序列和拓扑结构,怎样调整模型参数,包括状态转移和输出的概率分布,使得模型创建的输出序列具有最大概率?)。

神经网络(neural network

神经网络(Nerual Net)指由大量神经元互连而成的网络,有点象服务器互连而成的国际互连网(Internet).人脑有1000亿个神经元,每个神经元平均与10000个其他神经元互连,这就构成了人类智慧的直接物质基础。

神经元的工作机制:神经元由细胞体,树突(输入端),轴突(输出端)组成。神经元有两种工作状态:兴奋和抑制。每个神经元到另一个神经元的连接权(后者对前者输出的反应程度)是可以接受外界刺激而改变的,这构成了学习机能的基础。

人工神经网络的工作原理:人工神经网络首先要以一定的学习准则进行学习,然后才能工作。现以人工神经网络对手写“A”“B”两个字母的识别为例进行说明,规定当“A”输入网络时,应该输出“1”,而当输入为“B”时,输出为“0”。所以网络学习的准则应该是:如果网络作出错误的的判决,则通过网络的学习,应使得网络减少下次犯同样错误的可能性。首先,给网络的各连接权值赋予(01)区间内的随机值,将“A”所对应的图象模式输入给网络,网络将输入模式加权求和、与门限比较、再进行非线性运算,得到网络的输出。在此情况下,网络输出为“1”“0”的概率各为50%,也就是说是完全随机的。这时如果输出为“1”(结果正确),则使连接权值增大,以便使网络再次遇到“A”模式输入时,仍然能作出正确的判断。如果输出为“0”(即结果错误),则把网络连接权值朝着减小综合输入加权值的方向调整,其目的在于使网络下次再遇到“A”模式输入时,减小犯同样错误的可能性。如此操作调整,当给网络轮番输入若干个手写字母“A”“B”后,经过网络按以上学习方法进行若干次学习后,网络判断的正确率将大大提高。这说明网络对这两个模式的学习已经获得了成功,它已将这两个模式分布地记忆在网络的各个连接权值上。当网络再次遇到其中任何一个模式时,能够作出迅速、准确的判断和识别。一般说来,网络中所含的神经元个数越多,则它能记忆、识别的模式也就越多。

神经网络模型的特点是:利用大量的简单计算单元(神经元)连成网络,从而实现大规模并行计算;分布式存储,信息存在整个网中,用权值体现出来,有联想能力,可以从一个不完整的信息恢复出完整信息;自组织、自学习。其工作机理是通过学习来改变神经元之间的连接强度。人工神经网络的基本结构可以分为:递归网络和前馈网络

常用神经网络模型有Hopfield NetHarmming NetCarpenter/Grossberg 分类器、单层感知网、多层感知网、Kohonen的自组织特性图和反向传播(BP)网络。

多层感知网络(误差逆传播神经网络):在1986年以RumelhartMcCelland为首的科学家出版的《Parallel Distributed Processing》一书中,完整地提出了误差逆传播学习算法,并被广泛接受。多层感知网络是一种具有三层或三层以上的阶层型神经网络。典型的多层感知网络是三层、前馈的阶层网络,即:输入层I、隐含层(也称中间层)J、输出层K。相邻层之间的各神经元实现全连接,即下一层的每一个神经元与上一层的每个神经元都实现全连接,而且每层各神经元之间无连接。

竞争型(KOHONEN)神经网络:它是基于人的视网膜及大脑皮层对剌激的反应而引出的。神经生物学的研究结果表明:生物视网膜中,有许多特定的细胞,对特定的图形(输入模式)比较敏感,并使得大脑皮层中的特定细胞产生大的兴奋,而其相邻的神经细胞的兴奋程度被抑制。对于某一个输入模式,通过竞争在输出层中只激活一个相应的输出神经元。许多输入模式,在输出层中将激活许多个神经元,从而形成一个反映输入数据的特征图形。竞争型神经网络是一种以无教师方式进行网络训练的网络。它通过自身训练,自动对输入模式进行分类。竞争型神经网络及其学习规则与其它类型的神经网络和学习规则相比,有其自己的鲜明特点。在网络结构上,它既不象阶层型神经网络那样各层神经元之间只有单向连接,也不象全连接型网络那样在网络结构上没有明显的层次界限。它一般是由输入层(模拟视网膜神经元)和竞争层(模拟大脑皮层神经元,也叫输出层)构成的两层网络。两层之间的各神经元实现双向全连接,而且网络中没有隐含层,如图5。有时竞争层各神经元之间还存在横向连接。竞争型神经网络的基本思想是网络竞争层各神经元竞争对输入模式的响应机会,最后仅有一个神经元成为竞争的胜者,并且只将与获胜神经元有关的各连接权值进行修正,使之朝着更有利于它竞争的方向调整。神经网络工作时,对于某一输入模式,网络中与该模式最相近的学习输入模式相对应的竞争层神经元将有最大的输出值,即以竞争层获胜神经元来表示分类结果。这是通过竞争得以实现的,实际上也就是网络回忆联想的过程。

1986年美国物理学家J.J.Hopfield陆续发表几篇论文,提出了Hopfield神经网络。他利用非线性动力学系统理论中的能量函数方法研究反馈人工神经网络的稳定性,并利用此方法建立求解优化计算问题的系统方程式。基本的EN-U

分享到:
评论

相关推荐

    数据挖掘 与 知识发现

    掘的概念、数据挖掘对象、知识发现过程、研究方法以及相关研究领域和应用范围。作为知识发现的数据预处理工作,简要叙述了数据清理、数据约简、数据概念等级分层、多维数据模型等内容。书中较详细地介绍了粗糙级、...

    数据挖掘在各行业的应用论文

    知识发现和数据挖掘的研究.caj 数据仓库与数据挖掘技术浅谈.caj 用户访问模式数据挖掘的模型与算法研究.caj 数据仓库的建设与数据挖掘技术浅析.caj 分类特征规则的数据挖掘技术.caj 数据挖掘技术的主要方法及其发展...

    数据挖掘论文合集-242篇(part2)

    知识发现和数据挖掘的研究.caj 神经网络专家系统及其数据挖掘技术的探讨.caj 神经网络分类器的特征提取和优选.pdf 神经网络在数据挖掘中的应用研究.caj 神经网络数据挖掘方法中的数据准备问题.kdh 空间数据挖掘技术....

    数据挖掘概念与技术第三版英文原版ppt

     《数据挖掘:概念与技术(原书第3版)》是数据挖掘和知识发现领域内的所有教师、研究人员、开发人员和用户都必读的参考书,是一本适用于数据分析、数据挖掘和知识发现课程的优秀教材,可以用做高年级本科生或者...

    空间数据挖掘技术应用

    从这些海量数据中提取出隐含的信息和知识已成为人们研究的热点。空间数据挖掘就是为了解决这一科学问题而 提出的。该文在回顾已有空间数据挖掘规则的基础上,指出了空间数据挖掘过程中存在的主要问题,进而探讨了未 ...

    数据挖掘论文合集-242篇(part3)

    知识发现和数据挖掘的研究.caj 神经网络专家系统及其数据挖掘技术的探讨.caj 神经网络分类器的特征提取和优选.pdf 神经网络在数据挖掘中的应用研究.caj 神经网络数据挖掘方法中的数据准备问题.kdh 空间数据挖掘技术....

    数据挖掘论文合集-242篇(part1)

    知识发现和数据挖掘的研究.caj 神经网络专家系统及其数据挖掘技术的探讨.caj 神经网络分类器的特征提取和优选.pdf 神经网络在数据挖掘中的应用研究.caj 神经网络数据挖掘方法中的数据准备问题.kdh 空间数据挖掘技术....

    数据挖掘技术在软件知识库中的应用研究.pdf

    数据挖掘技术在软件知识库中的应用研究.pdf

    数据挖掘技术论述与介绍

    数据挖掘综合了各个学科技术,有很多的功能如:分类、聚类、预测、关联规则和序列模式的发现,应用数据挖掘技术是为了实现以下三种目的: 。发现知识:知识发现的目标是从数据库存储的数据中发现隐藏的关系、模式和...

    数据挖掘技术入门基础理论课程 共91页.ppt

    如何才能从中提取有价值的知识,进一步提高信息的利用率,由此引发了一个新的研究方向:基于数据库的知识发现(Knowledge Discovery in Database)及相应的数据挖掘(Data Mining)理论和技术的研究。 为什么数据...

    数据仓库与数据挖掘技术

    第8章介绍常用的知识发现技术及数据挖掘方法,主要包括依赖性分析、聚类分析、基于神经网络的数据挖掘方法、基于遗传算法的数据挖掘方法及基于粗糙集的数据挖掘方法;第9章介绍SQL Server 2000数据挖掘技术。, 本书...

    数据挖掘基础知识——技术、架构、发展

    本书将介绍数据挖掘与数据库知识发现的基本知识,以及从大量有噪声、不完整、甚至是不一致数据集合中,挖掘出有意义的模式知识所涉及的概念与技术方法。 本文将从数据管理技术演化角度,介绍数据挖掘的由来。以及...

    完整版数据仓库与数据挖掘全套课程课件 共117页.ppt

    第十二讲 数据挖掘工具及应用 数据库(DB)与数据仓库(DW),大数据处理(Big Data)与数据挖掘技术是当代数据处理的最新技术。这几项技术的结合开创了决策支持系统(DSS)发展的新方向。建立DW是科学决策的前提。...

    数据挖掘技术在Web 中的应用

    因此,将数据挖掘技术应用于Web 中,能够使人们快 速准确地从基于Web 的信息中获取自己所需的信息,这对于提高Web 信息服务水平和用户的忠诚度有重要意义。基于Apriori 算法的Web 日志挖掘技术正是数据挖掘应用于Web...

    数据挖掘:概念与技术(中文第三版)

    本书是数据挖掘和知识发现领域内的所有教师、研究人员、开发人员和用户都必读的参考书,是一本适用于数据分析、数据挖掘和知识发现课程的优秀教材,可以用做高年级本科生或者一年级研究生的数据挖掘导论教材。

    数据挖掘概念与技术

     《数据挖掘:概念与技术(原书第3版)》是数据挖掘和知识发现领域内的所有教师、研究人员、开发人员和用户都必读的参考书,是一本适用于数据分析、数据挖掘和知识发现课程的优秀教材,可以用做高年级本科生或者...

    数据挖掘(PDF)数据挖掘作为一个新兴的多学科交叉应用领域,正在各行各业的决策支持活动

    本书将介绍数据挖掘( )与数据库知识发现 )的基本知识,以及从大量有噪声、不完整、 至是不一致数据集合中,挖掘出有意义的模式知识所涉及的概念与技术方法。 本章将从数据...

    基于数据挖掘的数据库技术在转子故障知识发现中的应用方法研究.pdf

    基于数据挖掘的数据库技术在转子故障知识发现中的应用方法研究.pdf

Global site tag (gtag.js) - Google Analytics