数据仓库算法总结

1、数据库房算法数据库房算法总结事务办理环境不适合DSS应用的原由:事务办理和分析办理的性能特征不一样数据集成问题历史数据问题数据的综合问题数据库房数据的四个基本特色:数据库房的数据是面向主题的数据库房的数据是集成的数据库房的数据是不行更新的数据库房的数据是随时间不停变化数据库房定义：数据库房是在企业管理和决策中面向主题的、集成的、与时间相关的(时变的)、不行更正的（非易失的）数据会集，用于支持管理决策。支持度若D中的事务包含包含A和B的元组数AB的支持度为AB(即A和B两者)的百分比为s，则称关系规则s。即：support(A元组总数B)=P(AB)可信度/置信度若D中包含A的事务同时也包含B的

2、百分比为c，则称关系规则AB的置信度/可信度为c。即：confidence(AB)=P(B|A)=support(AB)/support(A)屡次项集项集的出现频率是包含项集的事物数，简称项集的频率。项集满足最小支持度阈值minsup：假如项集的出现频率大于或等于minsup与D中事物总数的乘积。满足最小支持阈值的项集就称为屡次项集(或大项集)。屡次k项集的会集记为Lk。定理（Apriori性质）屡次项集的全部非空子集都一定也是屡次的。任何非屡次项集的超级必定也是非屡次的Apriori算法详尽做法：关于所研究的事务数据库D，第一找出屡次1-项集的会集，记为L1；再用L1找屡次2-项集的会集L2

3、；再用L2找L3这样下去，直到不可以找到屡次k-项集为止。找每个Lk需要一次数据库扫描。如何实现用Lk-1找Lk.连接步：为找Lk，经过Lk-1与Lk-1连接产生候选k-项集的会集。该候选项集的会集记作Ck，执行1数据库房算法Lk-1与Lk-1的连接：假如他们前(k-2)个项相同，则可连接。剪枝步：任何非屡次的(k-1)项集都不行能是屡次k-项集的子集。所以，进行剪枝。1：该例基于某商店的事务DB。DB中有9个事务，Apriori假设事务中的项按字典次序存放。（1）在算法的第一次迭代，每个项都是候选1-项集的会集C1的成员。算法简单地扫描全部的事务，对每个项的出现次数计数。扫描D,对每个候选计

4、数2）设最小支持计数为2，可以确立屡次1-项集的会集L1。它由拥有最小支持度的候选1-项集构成。比较候选支持度计数与最小支持度计数3）为发现屡次2-项集的会集L2，算法使用L1L1产生候选2-项会会集C2。由L1产生候选C2（4）扫描D中事务，计算C2中每个候选项集的支持计数。扫描D,对每个候选计数2数据库房算法（5）确立屡次2-项集的会集L2，它由拥有最小支持度的C2中的候选2-项集构成。比较候选支持度计数与最小支持度计数6）候选3-项集的会集C3的产生以下：连接：C3=L2L2=I1,I2，I1,I3，I1,I5，I2,I3，I2,I4，I2,I5I1,I2，I1,I3，I1,I5，I2,

5、I3，I2,I4，I2,I5=I1,I2,I3，I1,I2,I5，I1,I3,I5，I2,I3,I4，I2,I3,I5，I2,I4,I5利用Apriori性质剪枝：屡次项集的全部子集一定是屡次的。存在候选项集，判断其子集能否屡次。I1,I2,I3的2-项子集是I1,I2，I1,I3和I2,I3,它们都是L2的元素。所以保留I1,I2,I3。I1,I2,I5的2-项子集是I1,I2，I1,I5和I2,I5,它们都是L2的元素。所以保留I1,I2,I5。I1,I3,I5的2-项子集是I1,I3，I1,I5和I3,I5,I3,I5不是L2的元素，因此不是屡次的，C3中删除I1,I3,I5。I2,I3

6、,I4的2-项子集是I2,I3，I2,I4和I3,I4,此中I3,I4不是L2的元素，因此不是屡次的，由C3中删除I2,I3,I4。I2,I3,I5的2-项子集是I2,I3，I2,I5和I3,I5,此中I3,I5不是L2的元素，因此不是屡次的，由C3中删除I2,I3,I5。I2,I4,I5的2-项子集是I2,I4，I2,I5和I4,I5,此中I4,I5不是L2的元素，因此不是屡次的，由C3中删除I2,I4,I5。这样，剪枝后C3=I1,I2,I3，I1,I2,I5。（7）扫描D中事务，以确立L3，它由拥有最小支持度的C3中的候选3-项集构成。由L2产生候选C3扫描D,对每个候选计数8）算法使用

7、L3L3产生候选4-项集的会集C4。尽管连接产生结果I1,I2,I3,I5,这个项集被剪去，因为它的子集I2,I3,I5不是屡次的。则C4=空集,所以算法停止，找出了全部的屡次项集。3数据库房算法关系规则的生成：依据上边介绍的关系规则发掘的两个步骤，在获取了全部屡次项目集后，可以依据下边的步骤生成关系规则：关于每一个屡次项目集l，生成其全部的非空子集；关于l的每一个非空子集X，计算Conference(X)，若Confidence(X)minconfidence，则“X(l-X)”建立。因为规则由屡次项集产生，每个规则都自动满足最小支持度。2：基于例1的结果，假设数据包含屡次项集l=I1，I2

8、，I5。可以由l产生哪些关系规则？L（L)的非空子集有I1，I2、I1，I5、I2，I5、I1、I2I5关系规则以下：I1I2I5,confidence2450%I1I5I2,confidence22100%I2I5I1,confidence22100%I1I2I5,confidence2633%I2I1I5,confidence2729%I5I1I2,confidence22100%假如最小置信度阈值为70%，那么只有第2、3、6个规则可以作为最后的输出，因为只有这些是产生的强规则。序列关系规则采集到的数据中常常存在某种次序关系，平常是基于时间的先后次序。关于鉴别动向系统的重要特色，或展望特

9、定事件的将来发生，序列信息将是很有价值的。对象时间戳事件A11，2，4A22，3A35B11，2B22，3，4C11，2C22，3，4C32，4，5D12D23，4D34，5每一行记录与一个特定的对象相关系的一些事件在给准时刻的出现。时间戳不是一个详尽的时间，而是一个象征性的时间，表示时间上的先后次序。将与对象A相关的全部事件准时间戳增序摆列就获取对象A的一个序列(sequence)。数据序列(datasequence)是指与单个数据对象相关系的事件的有序列表。如表中显示的数据集包含四个数据序列，对象A，B，C，D各一个。4数据库房算法设D是包含一个或多个数据序列的数据集序列s的支持度是包含s

10、的全部数据序列所占的比率。假如序列s的支持度大于或等于用户给定的最小支持度阈值(minsup)，则称s是一个屡次序列。以前面给定的包含4个数据序列的数据集为例，序列的支持度等于75%。假设minsup=50%，则最少出此刻2个数据序列中的任何序列都是序列模式：minsup=50%序列模式的例子：s=75%，除D外s=75%，除D外序列合并规则序列S1和序列S2合并，仅当从S1中去掉第一个事件后获取的子序列与从S2中去掉最后一个事件后获取的子序列相同，结果候选是序列S1和序列S2的最后一个事件连接，S2的最后一个事件可以作为最后一个事件合并到S1的最后一个元素中，也可以作为一个不一样的元素，这取

11、决于以下条件：假如S2的最后两个事件属于相同的元素，则S2的最后一个事件在合并后的序列中是S1的最后一个元素的一部分假如S2的最后两个事件属于不一样的元素，则S2的最后一个事件在合并后的序列中成为连接到S1的尾部的单独元素序列关系算法的连接和剪枝步骤的例子（此中，每个是指一个元素，1，2，3，4，5是指事件）屡次3序列产生候选4序列候选4序列剪枝关于给定的序列s，t，形如st的表达式就是序列关系规则。序列关系规则st的置信度是支持序列s和t的数据序列数与仅支持s的数据序列数之比。比方，的置信度为：s()/s()=15数据库房算法只凭支持度和可信度阈值未必总能找到符合实质的或有意义的规则,应该在

12、关系规则XY的置信度超出某个特定的胸襟标准时，定义它为有意义。在此引入Lift值（增益）：Lift(XY)=P(Y|X)/P(Y)=P(XY)/P(X)*P(Y)Lift=1，前项和后项经验独立Lift1，表示前项和后项是正相关的，说明X与Y实质同时发生的概率大于X与Y独立刻同时发生的随机概率Lift1，表示前项和后项是负相关的基于划分的聚类方法、1k-means算法(k-均匀或k-均值)第一将全部对象随机分配到k个非空的簇中。计算每个簇的均匀值，并用该均匀值代表相应的簇。依据每个对象与各个簇中心的距离，分配给近来的簇。而后转第二步，重新计算每个簇的均匀值。这个过程不停重复直到满足某个准则函数

13、才停止。例3样本数据依据所给的数据经过对其实行k-means(设n=8，k=2)，其主要序号属性1属性2执行步骤：第一次迭代：假设随机选择的两个对象，如序号1和序号3111看作初始点，分别找到离两点近来的对象，并产生两个簇1，2212和3，4，5，6，7，8。312关于产生的簇分别计算均匀值，获取均匀值点。422关于1，2，均匀值点为（1.5，1）；543关于3，4，5，6，7，8，均匀值点为（3.5，3）。653第二次迭代：经过均匀值调整对象的所在的簇，重新聚类，即744将全部点按离均匀值点（1.5，1）、（3.5，3）近来的原则重新854分配。获取两个新的簇：1，2，3，4和5，6，7，8

14、。重新计算簇均匀值点，获取新的均匀值点为（1.5，1.5）和（4.5，3.5）。第三次迭代：将全部点按离均匀值点（1.5，1.5）和（4.5，3.5）近来的原则重新分配，调整对象，簇依旧为1，2，3，4和5，6，7，8，发现没有出现重新分配，并且准则函数收敛，程序结束。迭代次数均匀值均匀值产生的新簇新均匀值新均匀值（簇1）（簇2）（簇1）（簇2）1（1，1）（1，2）1，2，3，4，5，6，7，8（1.5，1）（3.5，3）2（1.5，1）（3.5，3）1，2，3，4，5，6，7，8（1.5，1.5）（4.5，3.5）3（1.5，1.5）（4.5，3.5）1，2，3，4，5，6，7，8（1.5

15、，1.5）（4.5，3.5）请思虑：关于相同的样本数据，若随机选择的两个初始点为序号4和7，结果与前面会相同吗？有何结论?6数据库房算法2、K-中心点算法1.为每个簇随机选择一个代表对象(中心点)；2.节余的对象依据其与代表对象的距离分配给与其近来的一个簇；3.屡次地用非代表对象来替代代表对象，以提升聚类的质量，直至找到最适合的中心点。例4假如空间中的五个点A、如图1所示，各点之间的距离关系如表1所示，依据所给的数据对其运转PAM算法实现划分聚类（设k=2）。样本点间距离以下表所示:样本点ABCDEA01223B10243C2A2DBC220153D24103E33530E第一步建立阶段：假如

16、从5个对象中随机抽取的2此中心点为A，B,则样本被划分为A、C、D和B、E。第二步交换阶段：假设中心点A、B分别被非中心点C、D、E替代，依据PAM算法需要计算以下代价TCAC、TCAD、TCAE、TCBC、TCBD、TCBE。以TCAC为例说明计算过程：a)当A被C替代今后，A不再是一此中心点，因为A离B比A离C近，A被分配到B中心点代表的簇，CAAC=d(A,B)-d(A,A)=1。B是一此中心点，当A被C替代今后，B不受影响，CBAC=0。C原来属于A中心点所在的簇，当A被C替代今后，C是新中心点，符合PAM算法代价函数的第二种状况CCAC=d(C,C)-d(C,A)=0-2=-2。d)

17、D原来属于A中心点所在的簇，当A被C替代今后，离D近来的中心点是C，依据PAM算法代价函数的第二种状况CDAC=d(D,C)-d(D,A)=1-2=-1。e)E原来属于B中心点所在的簇，当A被C替代今后，离E近来的中心依旧是B，依据PAM算法代价函数的第三种状况CEAC=0。所以，TCAC=CAAC+CBAC+CBAC+CDAC+CEAC=1+0-2-1+0=-2。请计算代价TCAD、TCAE、TCBC、TCBD、TCBE。在上述代价计算达成后，采纳一个最小的代价，明显有多种替代可以选择，选择第一个最小代价的替代（也就是C替代A），依据图（a）所示，样本点被划分为B、A、E和C、D两个簇。图（

18、b）和图（c）分别表示了D替代A，E替代A的状况和相应的代价CCCAAA211111DDDBBB333EEE(a)C替代A,TCAC=-2(b)D替代A,TCAD=-2(c)E替代A,TCAE=-1图替代中心点A图（a）、（b）、（c）分别表示了用C、D、E替代B的状况和相应的代价。7数据库房算法CC2CAA11A1D1D1D2BBB33EEE（a）C替代B,TCBC=-2(b)D替代B,TCBD=-2(c)E替代B,TCBE=-2图替代中心点B经过上述计算，已经达成了PAM算法的第一次迭代。在下一迭代中，将用其余的非中心点A、D、E替代中心点B、C，找出拥有最小代价的替代。向来重复上述过程，

19、直到代价不再减小为止。层次聚类方法1、AGNES算法例5将以下数据聚为两个簇第1步：依据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为1，合并后1，2点合并为一个簇。第2步：对前一次合并后的簇计算簇间距离，找出距离近来的两个簇进行合并，合并后3，点成为一簇。3步：重复第2步的工作，5，6点成为一簇。4步：重复第2步的工作，7，8点成为一簇。5步：合并1，2，3，4成为一个包含四个点的簇。第6步：合并5，6，7，8，因为合并后簇的数量达到了用户输入的停止条件，程序结束。序号属性1属性2111步骤近来的簇距离近来的两个簇合并后的新簇212111，21，2，3，4，5，6

20、，7，8321213，41，2，3，4，5，6，7，8422315，61，2，3，4，5，6，7，8534417，81，2，3，4，5，6，7，8635511，2，3，41，2，3，4，5，6，7，8744615，6，7，81，2，3，4，5，6，7，8结束8458数据库房算法2、DIANA算法（典型的分裂聚类方法）两种测度方法：簇的直径：在一个簇中的任意两个数据点的距离中的最大值。均匀相异度（均匀距离）：1davg(Ci,Cj)xCiyCjxy例6ninj将以下数据聚为两个簇序号属性1属性2第1步，找到拥有最大直径的簇，对簇中的每个点计算均匀相异度（假设采纳是欧式距离）。1112123214

21、225341的均匀距离：(1+1+1.414+3.6+4.24+4.47+5)/7=2.96近似地：2的均匀距离为2.526；3的均匀距离为2.68；4的均匀距离为2.18；5的均匀距离为2.18；6的均匀距离为2.68；7的均匀距离为2.526；6358的均匀距离为2.96。744挑出均匀相异度最大的点1放到splintergroup中，节余点在old845party中。第2步，在oldparty里找出到近来的splintergroup中的点的距离不大于到oldparty中近来的点的距离的点，将该点放入splintergroup中，该点是2。第3步，重复第2步，splintergroup中放

22、入点3。第4步，重复第2步，splintergroup中放入点4。第5步，没有在oldparty中的点放入了splintergroup中且达到停止条件（k=2），程序停止。假如没有到停止条件，应该从分裂好的簇中选一个直径最大的簇连续分裂。步骤拥有最大直径的簇splintergroupOldparty11，2，3，4，5，6，7，812，3，4，5，6，7，821，2，3，4，5，6，7，81，23，4，5，6，7，831，2，3，4，5，6，7，81，2，34，5，6，7，841，2，3，4，5，6，7，81，2，3，45，6，7，851，2，3，4，5，6，7，81，2，3，45，6，7，8

23、停止3、BIRCH(1996)4、CURE算法密度聚类1、DBSCAN9数据库房算法关于一个类中的每个对象，在其给定半径的领域中包含的对象不可以少于某一给定的最小数量定义1对象的-临域（Eps近邻）：给定对象在半径内的地域。定义2核心对象：假如一个对象的-临域最少包含最小数量MinPts个对象，则称该对象为核心对象。比方，在图中，=1cm，MinPts=5，q是一个核心对象。定义3直接密度可达：给定一个对象会集D，假如p是在q的-邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。比方，在图中，=1cm，MinPts=5，q是一个核心对象，对象p从对象q出发是直接密度可达的。

24、图直接密度可达图密度可达图密度相连图噪声定义4密度可达的：假如存在一个对象链p1，p2，pn，p1=q，pn=p，对piD，（1=i=n），pi+1是从pi关于和MitPts直接密度可达的，则对象p是从对象q关于和MinPts密度可达的。比方，在图中，=1cm，MinPts=5，q是一个核心对象，p1是从q关于和MitPts直接密度可达，p是从p1关于和MitPts直接密度可达，则对象p从对象q关于和MinPts密度可达的（间接密度可达）。定义5密度相连的：假如对象会集D中存在一个对象o，使得对象p和q是从o关于和MinPts密度可达的，那么对象p和q是关于和MinPts密度相连的。定义6噪声

25、:一个基于密度的簇是基于密度可达性的最大的密度相连对象的会集。不包含在任何簇中的对象被以为是“噪声”。7下边给出一个样本领务数据库（见左表），对它实行DBSCAN算法。依据所给的数据经过对其进行DBSCAN算法，以下为算法的步骤（设n=12，用户输入=1，MinPts=4）样本领务数据库DBSCAN算法执行过程表示聚出的类为1，3，4，5，9，10，12，2，6，7，8，11可达10数据库房算法算法执行过程：第1步，在数据库中选择一点1，因为在以它为圆心的，以1为半径的圆内包含2个点（小于4），所以它不是核心点，选择下一个点。第2步，在数据库中选择一点2，因为在以它为圆心的，以1为半径的圆内包

26、含2个点，所以它不是核心点，选择下一个点。第3步，在数据库中选择一点3，因为在以它为圆心的，以1为半径的圆内包含3个点，所以它不是核心点，选择下一个点。第4步，在数据库中选择一点4，因为在以它为圆心的，以1为半径的圆内包含5个点，所以它是核心点，找寻从它出发可达的点（直接可达4个，间接可达2个），聚出的新类1，3，4，5，9，10，12，选择下一个点。第5步，在数据库中选择一点5，已经在簇1中，选择下一个点。第6步，在数据库中选择一点6，因为在以它为圆心的，以1为半径的圆内包含3个点，所以它不是核心点，选择下一个点。第7步，在数据库中选择一点7，因为在以它为圆心的，以1为半径的圆内包含5个点，

27、因此它是核心点，找寻从它出发可达的点，聚出的新类2，6，7，8，11，选择下一个点。8步，在数据库中选择一点8，已经在簇2中，选择下一个点。9步，在数据库中选择一点9，已经在簇1中，选择下一个点。10步，在数据库中选择一点10，已经在簇1中，选择下一个点。11步，在数据库中选择一点11，已经在簇2中，选择下一个点。12步，选择12点，已经在簇1中，因为这已经是最后一点全部点都已办理，程序停止。网格聚类1、STING算法是一种基于网格的多分辨率聚类技术，它将空间地域划分为矩形单元。针对不一样级其余分辨率，平常存在多个级其余矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单

28、元。高层单元的统计参数可以很简单的从基层单元的计算获取。这些参数包含属性没关的参数count、属性相关的参数m（均匀值）、s(标准偏差)、min(最小值)、max(最大值)以及该单元中属性值依据的分布种类。模型聚类K近来邻居算法（KNN）经过计算每个训练数据到待分类元组的距离，取和待分类元组距离近来的K个训练数据，K个数据中哪个类其余训练数据占多数，则待分类元组就属于哪个种类。11数据库房算法7“身高”用于计算距离，K=5，对分类。姓名性别身高(米)种类Kristina女1.6矮Jim男2高Maggie女1.9中等Martha女1.88中等Stephanie女1.7矮Bob男1.85中等Kat

29、hy女1.6矮Dave男1.7矮Worth男2.2高Steven男2.1高Debbie女1.8中等Todd男1.95中等Kim女1.9中等Amy女1.8中等Wynette女1.75中等1.取前K=5个记录：N=、和。2.对第6个记录d=，获取N=、和。3.对第7个记录d=，获取N=、和。4.对第8个记录d=，获取N=、和。对第9和10个记录,没变化。5，对第11个记录d=，获取N=、和。对第12到14个记录,没变化。6.对第15个记录d=，获取N=、和。7.最后输出元组是：、和。此中，四个属于矮个、一个属于中等。最后KNN方法以为Pat为矮个。请问：若K=5，的身高应该属于那各种类？ID3算法

30、生成决策树信息增益信息增益是指划分前后进行正确展望所需的信息量之差。即原始切割的熵与划分今后各切割的熵累加获取的总熵之间的差。选择属性的方法：选择拥有最大信息增益（熵减少的程度最大）的属性作为当前节点的测试属性信息增益的计算设S是有s个训练样本数据的会集，类标号属性拥有m个不一样值，定义m个不一样类Ci（i=1,2,m），si是类Ci中的样本数，则对一个给定的训练样安分类所需要的希望信息为：mIs1,s2,smpilog2pii1此中pi是任意样本属于Ci的概率，可用si/s来预计12数据库房算法设属性A拥有v个不一样值a1,a2,av，则可用属性A将S划分为v个子集S1,S2,Sv，Sj中包

31、含的样本在属性A上拥有值aj。假如选择A作为测试属性，则这些子集对应于由包含会集S的结点生长出来的分枝。设sij是子集Sj中类Ci的样本数，则依据A划分成子集的熵为：vs1jsmjI(s1j,E(A),smj)j1s此中s1jsmjs为第j个子集的权，等于子集（A值为aj）中的样本数除以S中的样本数。关于给定的子集Sj，它的信息I(s1j,s2j,smj)可用下式计算mI(s1j,s2j,smj)pijlog2(pij)i1Sijpij|是Sj中的样本属于类Ci的概率|Sj由A划分的信息增益为：Gain(A)=I(s1,s2,sm)-E(A)8一个商场顾客数据库（训练样本会集）样本会集的种类属

32、性为：“buy_computer”，该属性有两个不同取值，即yes,no，所以就有两个不一样的种类(m=2)。设C1对应类别yes，C2对应种类no。种类C1包含9个样本，种类C2包含5个样本。为了计算每个属性的信息增益，第一利用公式计算出全部（对一个给定样本进行分类所需要）的信息，详尽计算过程以下：接着需要计算每个属性的（信息）熵。假设先隶属性“age”开始，依据属性“age”每个取13数据库房算法值在yes种类和no种类中的分布，就可以计算出每个分布所对应的信息。而后利用公式计算出若依据属性“age对”样本会集进行划分，所获取对一个数据对象进行分类而需要的信息熵为：由此获取利用属性“age

33、对”样本会集进行划分所获取的信息增益为：近似可得Gain(income)=0.029，Gain(student)=0.151，Gain(credit_rating)=0.048。明显选择属性“age所”获取的信息增益最大，所以被作为测试属性用于产生当前分支结点。这个新产生的结点被标志为“age；”同时依据属性“age的”三个不一样取值，产生三个不一样的分支，当前的样本会集被划分为三个子集，以以下图。C4.5算法信息增益比率：是在信息增益看法基础上发展起来的，一个属性的信息增益比率用下边的公式给出：Gain(A)GainRatio(A)SplitI(A)v此中SplitI(A)pjlog2(pj

34、)j114数据库房算法假如以属性A的值为基准对样本进行切割的化，SplitI(A)就是前面熵的看法。C4.5办理连续值的属性：依据属性的值，对数据集排序；用不一样的阈值将数据集动向的进行划分；当输出改变时确立一个阈值；取两个实质值中的中点作为一个阈值；取两个划分，全部样本都在这两个划分中；获取全部可能的阈值、增益及增益比；在每一个属性会变成取两个取值，即小于阈值或大于等于阈值。简单地说，针对属性有连续数值的状况，则在训练集中可以按升序方式摆列。假如属性A共有n种取值，则对每个取值vj（j=1，2，n），将全部的记录进行划分：一部分小于vj；另一部分则大于或等于vj。针对每个vj计算划分对应的增

35、益比率，选择增益率最大的划分来对属性A进行失散化。91）第一对Humidity进行属性离样本数据散化，针对上边的训练会集，经过检测每个划分而确立最好的OutlookTemperatureHumidityWindPlayTennis划分在75处，则这个属性的范SunnyHot85falseNo围就变成(75)。SunnyHot90trueNo2）计算目标属性PlayTennis分OvercastHot78falseYes类的希望信息：RainMild96falseYesI(s1,s2)I(9,5)RainCool80falseYes9955RainCool70trueNo14log21414lo

36、g214OvercastCool65trueYesSunnyMild95falseNo0.940SunnyCool70falseYes3）计算每个属性的GainRatio：RainMild80falseYes0.246SunnyMild70trueYesGainRatio(Outlook)；1.5770.156OvercastMild90trueYesGainRatio；OvercastHot75falseYes(windy)0.049GainRatio；(Temperature)0.0248GainRatio(Humidity)0.04834）采纳最大的GainRatio，依据Outlook

37、的取值，获取三个分支。5）再扩展各分枝节点，获取最后的决策树。贝叶斯定理设X是类标号未知的数据样本。设H为某种假设，如数据样本X属于某特定的类C。关于分类问题，我们希望确立P(H|X)，即给定观察数据样本X，假设H建立的概率。15数据库房算法贝叶斯定理给出了以下计算P(H|X)的简单有效的方法:P(X|H)P(H)P(H|X)P(X)P(H):是先验概率，或称H的先验概率。P(X):样本数据被观察的概率。P(X|H)代表假设H建立的状况下，观察到X的概率。P(H|X)是后验概率，或称条件X下H的后验概率。后验概率P(H|X)比先验概率P(H)基于更多的信息。P(H)是独立于X的。朴素贝叶斯分类

38、朴素贝叶斯分类就是假设一个属性值对给定类的影响独立于其余属性的值。这一假设称作类条件独立。做此假设是为了简化所需计算，并在此意义下称为“朴素的”。朴素贝叶斯分类的工作过程以下：(1)每个数据样本用一个n维特色向量X=x1,x2,xn表示，分别描述对n个属性A1，A2，An样本的n个胸襟。(2)假设有m个类C1，C2，Cm，给定一个未知的数据样本X（即没有类标号），分类器将展望X属于拥有最高后验概率（条件X下）的类。也就是说，朴素贝叶斯分类将未知的样安分配给类Ci（1im）当且仅当P(Ci|X)P(Cj|X)，对任意的j=1，2，m，ji。这样，最大化P(Ci|X)。其P(Ci|X)最大的类Ci

39、称为最大后验假设。(3)依据贝叶斯定理：P(X|Ci)P(Ci)P(Ci|X)P(X)因为P(X)关于全部类为常数，只需要P(X|Ci)*P(Ci)最大即可。假如Ci类的先验概率未知，则平常假设这些类是等概率的，即P(C1)=P(C2)=P(Cm)，所以问题就变换为对P(X|Ci)的最大化（P(X|Ci)常被称为给定Ci时数据X的似然度，而使P(X|Ci)最大的假设Ci称为最大似然假设）。不然，需要最大化P(X|Ci)*P(Ci)。注意，类的先验概率可以用P(Ci)=si/s计算，此中si是类Ci中的训练样本数，而s是训练样本总数。(4)给定拥有好多属性的数据集，计算P(X|Ci)的开支可能特

40、别大。为降低计算P(X|Ci)的开销，可以做类条件独立的朴素假设。给定样本的类标号，假设属性值互相条件独立，即在属性间，不存在依赖关系。这样nP(X|Ci)P(xk|Ci)k1此中概率P(x1|Ci)，P(x2|Ci)，P(xn|Ci)可以由训练样本估值。假如Ak是失散属性，则P(xk|Ci)=sik/si，此中sik是在属性Ak上拥有值xk的类Ci的训练样本数，而si是Ci中的训练样本数。假如Ak是连续值属性，常用的办理方法有两种：一是对其失散化，而后依据失散值办理；另一种假设这一属性遵从某一分布，平常假设该属性遵从高斯分布。对未知样本X分类，也就是对每个类Ci，计算P(X|Ci)*P(Ci

41、)。样本X被指派到类Ci，当且仅当P(Ci|X)P(Cj|X)，1jm，ji，换言之，X被指派到其P(X|Ci)*P(Ci)最大的类。16数据库房算法例10样本数据希望分类的未知样本为:X=（age=”=30”，income=”medium”，student=”yes”，credit_rating=”）fair”思路:计算每一个类的P(Ci|X)=P(X|Ci)P(Ci)/P(X),Ci代表任意一个类，X代表需要判断的盘问条件设C1对应于类buys_computer=”yes，”C2对应于类buys_computer=”no”。(1)需要最大化P(X|Ci)*P(Ci)，i=1，2。每个类的先

42、验概率P(Ci)可以依据训练样本计算：P(buys_computer=”yes”)=9/14=0，.643P(buys_computer=”no”)=5/14=0.357。为计算P(X|Ci)，i=1，2，计算下边的条件概率：P(age=30|buys_computer=”yes”)=2/9=0，.222P(age=30”|buys_computer=”no”)=3/5=0，.600P(income=”medium”|buys_computer=”yes”)=4/9=0，.444P(income=”medium”|buys_computer=”no”)=2/5=0，.400P(student=

43、”yes”|buys_computer=”yes”)=6/9=0，.677P(student=”yes”|buys_computer=”no”)=1/5=0，.200P(credit_rating=”fair”|buys_computer=”yes”，)=6/9=0.667P(credit_rating=”fair”|buys_computer=”no”。)=2/5=0.400假设条件独立性，使用以上概率，获取：P(X|buys_computer=”yes”)=02*0.22.444*0.667*0.667=0.044，P(X|buys_computer=”no”)=0.600*0.400*0

44、.200*0.400=0，.019P(X|buys_computer=”yes”)*P(buys_computer=”yes”)=0.044*0.643=0.028，P(X|buys_computer=”no”)*P(buys_computer=”no”)=0.019*0.357=0.007。故关于样本X，朴素贝叶斯分类展望buys_computer=”yes。”17数据库房算法神经网络输入层：节点的数据与训练样本的非种类属性数量对应，平常一个连续属性对应一个输入层单元，一个p值失散属性对应p个输入层单元；输出层：节点的数据与训练样本的种类数量对应；隐蔽层：层数及隐蔽层节点的数量当前还没有理论

45、指导，凭经验采纳。1、向前流传输入：给定隐蔽层或输出层的单元j(j的输入来自前一层的输出)。到单元j的净输入：IjwijOijij是单元j的偏置Wij是前一层单元iOi是前一层单元到单元j的连接权重i的输出隐蔽层和输出层的每个单元接受一个净输入，而后利用激活函数对它进行计算。给定单元j的净输入Ij，则单元j的输出为：1Oj1eIj2、向后流传偏差计算偏差经过更新权和偏置以反响网络展望偏差，后向流传偏差。关于输出层单元j，偏差Errj用下式计算：ErrjOj(1Oj)(TjOj)此中Oj是单元j的实质输出，而Tj是j基于给定训练样本的已知类标号的真切输出，Oj(1-Oj)是log的微分函数。为计算隐蔽层单元j的偏差，考虑下一层中连接j的单元的偏差加权和。隐蔽层单元j的误差是：ErrjOj(1Oj)