Search trees：实例--二叉搜索树
什么是二叉搜索树
二叉搜索树(Binary Search Tree)是一棵有序的二叉树，所以我们也可以称它为二叉排序树（不知道二叉树的童鞋，先看看二叉树：传送门）。
具有以下性质的二叉树我们称之为二叉搜索树：若它的左子树不为空，那么左子树上的所有值均小于它的根节点；若它的右子树不为空，那么右子树上所有值均大于它的根节点。它的左子树和右子树分别也为二叉搜索树。
2、二叉搜索树的结构
二叉搜索树能够高效的进行一下操作：①插入一个数值②查询是否包含某个数值③删除某个数值
根据实现的不同，还可以实现其他各种操作，这是一种使用性很高的数据结构。我们来看一个例子：
这就是二叉搜索树的存储结构，所有的节点，都满足左子树上的比自己小，而右子树上的所有节点比自己大。二叉搜索树因为其有序性，所以它能够高效的管理数的集合
(1)查询
我们查找是否存在17：
<1>根节点是7，因为小于17，所以去右子树查找
<2>走到节点12，还是小于17，所以继续往右子树找
<3>走到节点17，此时找到17。
(2)插入
我们使用查找的方式进行插入，以数字6为例，如图所示：
(3)删除
删除操作相对之前的其他两种操作，就略显复杂一些。一般来说我们可以分为三种情况：
<1>需要删除的节点没有左儿子，那么就把右儿子提上去
<2>需要删除的节点的左儿子没有右儿子，那么就把左儿子提上去
<3>不满足上述的两种情况的话，就把左子树中最大的节点放到要删除的节点上。
3、二叉搜索树的复杂度
无论我们执行哪一个操作，其所花的时间都和树的高度成正比。我们不难得知，二叉搜索树的平均复杂度为O(log n)。
4、二叉搜索树的实现
通过上述的了解，我们大致已经知道二叉搜索树的工作原理。所以现在我们就来简单的实现二叉搜索树基本的增删查的功能，代码如下：
[cpp]view plain copy
1.//表示节点的结构体
2.struct node{
3.int val;
4.node*lch,*rch;
5.};
6.//插入整数x
7.node*insert(node*p,int x){
8.if(p==NULL){
9.node*newNode=new node;
10.newNode->val=x;
11.newNode->lch=newNode->rch=NULL;
12.p=newNode;
13.}else{
14.if(x
15.else p->rch=insert(p->rch,x);
16.}
17.return p;
18.}
19.//查找整数x
20.bool find(node*p,int x){
21.if(p==NULL)return false;
22.else if(p->val==x)return true;
23.else if(p->val>x)return find(p->lch,x);
24.else return find(p->rch,x);
25.}
26.//删除整数x
27.node*remove(node*p,int x){
28.if(p==NULL)return NULL;
29.else if(x
30.else if(x>p->val)p->rch=remove(p->rch,x);
31.//情况<1>
32.else if(p->lch==NULL){
33.node*q=p->rch;
34.delete p;
35.return q;
36.}
37.//情况<2>
38.else if(p->lch->rch==NULL){
39.node*q=p->lch;
40.q->rch=p->rch;
41.delete p;
42.return q;
43.}
44.//情况<3>
45.else{
46.node*q;
47.for(q=p->lch;q->rch->rch!=NULL;q=q->rch);
48.node*r=q->rch;
49.q->rch=r->lch;
50.r->lch=p->lch;
51.r->rch=p->rch;
52.delete p;
53.return r;
54.}
55.return p;
56.}
Heaps；实例--斐波那契堆
斐波纳契堆（Fibonacci Heap）于1984年由Michael L.Fredman与Robert E.Tarjan 提出，1987年公开发表，名字来源于运行时分析所使用的斐波那契数。
斐波那契堆同二项堆（Binomial Heap）一样，也是一种可合并堆（Mergeable Heap）。与二项堆一样，斐波那契堆是由一组最小堆有序树构成，但堆中的树并不一定是二项树。与二项堆中树都是有序的不同，斐波那契堆中的树都是有根而无序的。
特点：不涉及删除元素的操作有O(1)的平摊时间。Extract-Min和Delete的数目和其它相比较小时效率更佳。关键思想在于尽量延迟对堆的维护
稠密图每次Decrease－key只要O(1)的平摊时间，和二项堆的O(lgn)相比是巨大的改进。
斐波那契堆的结构较二项堆更松散。因此对结构的维护可以到方便时再做。
斐波那契堆中的树是有根而无序的。每个节点包含一个指向其父节点的指针p[x]，以及一个指向其任一子女的指针child[x]（指向子女双链表）。
每个孩子有left[x]和right[x]。（意义：在O(1)的时间内去掉一个节点，或者在O(1)的时间内合并双链表。）其它域：degree[x]存储子女个数。mark[x]指示自从x上一次成为另一节点的子女以来，它是否失掉一个孩子。
一个给定的斐波那契堆可以通过一个指向其含有最小关键字树的指针来访问。
斐波那契堆的关键思想在于尽量延迟对堆的维护。创建一个新的斐波那契堆：
MAKE_Fib_Heap有O(1)的代价。
插入一个节点：分三步进行：1，为新的节点置p，child，left，right，mark等域。时间消耗：O(1)。2，将包含x的根表和根表H连接。时间消耗：O(1)。3，在O(1)的时间内调整指向该堆的指针min[x]时间消耗：O(1)。以节点数表示势。势的增加为1，实际代价为O(1)。所以平摊代价为O(1)。
寻找最小节点：min[x]指向的节点即为最小节点。因为势没有变化，所以这个操作的平摊代价为O(1)。
合并两个斐波那契堆：分为3步：1。合并根表2。设置新的min[h]3。重置n[x]。
抽取最小节点：这是最复杂的工作。被延迟的对根表的调整工作最终由这个操作进行。1。去掉最小值，将其每个孩子都加入根表。2。将相同度数树的合并。
调整根表的步骤1。在根表中找出两个具有相同度数的根x和y，且key[x]《key[y]2。将y与x连接。将y从根表里去掉，成为x一个孩子，并增加degree[x]。
减小一个节点的权1。若此减小不影响堆序，不作调整。2。若影响堆序，则从堆中删除该节点，将其加入根表。并检查其父亲的mark位。
若为false，则停止，并将其置为true。若为true，则删除其父亲，继续递归向上执行。直到一个
节点mark域为false或该节点为根节点为止。
删除一个节点：1。将该节点权调整至最小2。抽取最小值。
证明最大度数界：证明删除或extract－min的平摊时间为O（lgn)。引理1：设x为斐波那契堆中任一节点，并假设degree[x]=k。设y1，y2，。。。yk表示按与x链接的次序排列的x的子女，从最早的到最迟的，则对i=2,3,...,k，有degree[y1]>=0且
degree[yi]>=i-2证明：显然degree[y1]》=0对i>=2，注意到y1被链接到x上时，y1，y2，。。yi－1都是x的子女，故我们必有degree[x]>=i-1又仅当degree[x]=degree[yi]时，才将yi链接到x上。故此时必有degree[yi>=i-1，在此之后，节点yi至多失去一个孩子，因为失去两个就被切断了。所以degree[yi]>=i-2
引理2：对所有的整数k>=0，Fk+2=1+sum（Fi）[0<=i<=k]，F为斐波那契数。用数学归纳法证明。并可证明不等式Fk+2>=G^k，其中G为黄金分割率。
(1+5^0.5)/2=1.161803...
引理3：设x为斐波那契堆中任一节点，并设k=degree[x]，那么，size(x)>=Fk+2>=G^k。
推论：在一个包含n个节点的斐波那契堆中节点的最大度数为O(lgn)。
对于斐波那契堆上的各种可合并操作，关键思想是尽可能久地将工作推后。例如，当向斐波那契堆中插入新结点或合并两个斐波那契堆时，并不去合并树，而是将这个工作留给EXTRACT-MIN操作
Spatial data partitioning trees：实例--Burkhard-Keller树
BK树或者称为Burkhard-Keller树，是一种基于树的数据结构，被设计于快速查找近似字符串匹配，比方说拼写检查器，或模糊查找，当搜索”aeek”时能返回”seek”和”peek”。为何BK-Trees这么酷，因为除了穷举搜索，没有其他显而易见的解决方法，并且它能以简单和优雅的方法大幅度提升搜索速度。。
在定义BK树之前，我们需要预先定义一些操作。为了索引和搜索字典，我们需要一种比较字符串的方法。编辑距离（Levenshtein Distance）是一种标准的方法，它用来表示经过插入、删除和替换操作从一个字符串转换到另外一个字符串的最小操作步数。其它字符串函数也同样可接受（比如将调换作为原子操作），只要能满足以下一些条件。
除了字符串匹配、查找回文串、查找重复子串等经典问题以外，日常生活中我们还会遇到其它一些怪异的字符串问题。比如，有时我们需要知道给定的两个字符串“有多像”，换句话说两个字符串的相似度是多少。1965年，俄国科学家Vladimir Levenshtein给字符
串相似度做出了一个明确的定义叫做Levenshtein距离，我们通常叫它“编辑距离”。字符串A到B的编辑距离是指，只用插入、删除和替换三种操作，最少需要多少步可以把A变成B。例如，从FAME到GATE需要两步（两次替换），从GAME到ACM则需要三步（删除G和E 再添加C）。Levenshtein给出了编辑距离的一般求法，就是大家都非常熟悉的经典动态规划问题。
在自然语言处理中，这个概念非常重要，例如我们可以根据这个定义开发出一套半自动的校对系统：查找出一篇文章里所有不在字典里的单词，然后对于每个单词，列出字典里与它的Levenshtein距离小于某个数n的单词，让用户选择正确的那一个。n通常取到2或者3，或者更好地，取该单词长度的1/4等等。这个想法倒不错，但算法的效率成了新的难题：查字典好办，建一个Trie树即可；但怎样才能快速在字典里找出最相近的单词呢？这个问题难就难在，Levenshtein的定义可以是单词任意位置上的操作，似乎不遍历字典是不可能完成的。现在很多软件都有拼写检查的功能，提出更正建议的速度是很快的。它们到底是怎么做的呢？1973年，Burkhard和Keller提出的BK树有效地解决了这个问题。这个数据结构强就强在，它初步解决了一个看似不可能的问题，而其原理非常简单。
首先，我们观察Levenshtein距离的性质。令d(x,y)表示字符串x到y的Levenshtein 距离，那么显然：
1.d(x,y)=0当且仅当x=y（Levenshtein距离为0<==>字符串相等）
2.d(x,y)=d(y,x)（从x变到y的最少步数就是从y变到x的最少步数）
3.d(x,y)+d(y,z)>=d(x,z)（从x变到z所需的步数不会超过x先变成y再变成z 的步数）
最后这一个性质叫做三角形不等式。就好像一个三角形一样，两边之和必然大于第三边。给某个集合内的元素定义一个二元的“距离函数”，如果这个距离函数同时满足上面说的三个性质，我们就称它为“度量空间”。我们的三维空间就是一个典型的度量空间，它的距离函数就是点对的直线距离。度量空间还有很多，比如Manhattan距离，图论中的最短路，当然还有这里提到的Levenshtein距离。就好像并查集对所有等价关系都适用一样，BK树可以用于任何一个度量空间。
建树的过程有些类似于Trie。首先我们随便找一个单词作为根（比如GAME）。以后插入一个单词时首先计算单词与根的Levenshtein距离：如果这个距离值是该节点处头一次出现，建立一个新的儿子节点；否则沿着对应的边递归下去。例如，我们插入单词FAME，它与GAME的距离为1，于是新建一个儿子，连一条标号为1的边；下一次插入GAIN，算得它与GAME的距离为2，于是放在编号为2的边下。再下次我们插入GATE，它与GAME距离为1，于是沿着那条编号为1的边下去，递归地插入到FAME所在子树；GATE与FAME的距离为2，于是把GATE放在FAME节点下，边的编号为2。
查询操作异常方便。如果我们需要返回与错误单词距离不超过n的单词，这个错误单词与树根所对应的单词距离为d，那么接下来我们只需要递归地考虑编号在d-n到d+n范围内的边所连接的子树。由于n通常很小，因此每次与某个节点进行比较时都可以排除很多子树。
举个例子，假如我们输入一个GAIE，程序发现它不在字典中。现在，我们想返回字典中所有与GAIE距离为1的单词。我们首先将GAIE与树根进行比较，得到的距离d=1。由于Levenshtein距离满足三角形不等式，因此现在所有离GAME距离超过2的单词全部可以排除了。比如，以AIM为根的子树到GAME的距离都是3，而GAME和GAIE之间的距离是1，那么AIM及其子树到GAIE的距离至少都是2。于是，现在程序只需要沿着标号范围在1-1到1+1里的边继续走下去。我们继续计算GAIE和FAME的距离，发现它为2，于是继续沿标号在1和3之间的边前进。遍历结束后回到GAME的第二个节点，发现GAIE和GAIN距离为1，输出GAIN并继续沿编号为1或2的边递归下去（那条编号为4的边连接的子树又被排除掉了）……
实践表明，一次查询所遍历的节点不会超过所有节点的5%到8%，两次查询则一般不会17-25%，效率远远超过暴力枚举。适当进行缓存，减小Levenshtein距离常数n可以使算法效率更高。
Tries；实例--散列
Hash表数据结构常识：
一、哈希表基于数组。
二、缺点：基于数组的，数组创建后难以扩展。某些哈希表被基本填满时，性能下降得非常严重。
三、没有一种简便得方法可以以任何一种顺序遍历表中数据项。
四、如果不需要有序遍历数据，并且可以提前预测数据量的大小，那么哈希表在速度和易用性方面是无与伦比的。
*若结构中存在和关键字K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个事先建立的表为散列表。
*对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称碰撞。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。
*若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
性质
所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但并不能绝对肯定二者一定相等。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域，比如固定长度的比特串。在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。
常用HASH函数
·直接取余法：f(x):=x mod maxM;maxM一般是不太接近2^t的一个质数。
·乘法取整法：f(x):=trunc((x/maxX)*maxlongit)mod maxM，主要用于实数。
·平方取中法：f(x):=(x*x div1000)mod1000000);平方后取中间的，每位包含信息比较多。
构造方法
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。
（详细构造方法可以参考hash函数中的【哈希表的构造方法】）
1．直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key)=a·key+b，其中a和b为常数（这种散列函数叫做自身函数）
2．数字分析法
3．平方取中法
4．折叠法
5．随机数法
6．除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key)=key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
处理冲突方法
1．开放寻址法；Hi=(H(key)+di)MOD m,i=1,2,…，k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
1)．di=1,2,3,…，m-1，称线性探测再散列；
2)．di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)称二次探测再散列；
3)．di=伪随机数序列，称伪随机探测再散列。
2．再散列法：Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
3．链地址法(拉链法)
4．建立一个公共溢出区
查找性能分析
散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：
1．散列函数是否均匀；
2.处理冲突的方法；
3．散列表的装填因子。
散列表的装填因子定义为：α=填入表中的元素个数/散列表的长度
α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。
散列(Hash)同顺序、链式和索引存储结构一样，是存储线性表的又一种方法。散列存储的基本思想是：以线性表中的每个元素的关键字key为自变量，通过一种函数H(key)计算出函数值，把这个函数值解释为一块连续存储空间的单元地址(即下标)，将该元素存储到这个单元中。散列存储中使用的函数H(key)称为散列函数或哈希函数,它实现关键字到存储地址的映射(或称转换)，H(key)的值称为散列地址或哈希地址；使用的数组空间是线性表进行散列存储的地址空间，所以被称之为散列表或哈希表。当在散列表上进行查找时，首先根据给定的关键字key，用与散列存储时使用的同一散列函数H(key)计算出散列地址，然后按此地址从散列表中取对应的元素。
例如，有个线性表A=(31,62,74,36,49,77)，其中每个整数可以是元素本身，也可以仅是元素的关键字，为了散列存储该线性表，假设选取的散列函数为：
H(key)=key%m
即用元素的关键字key整除m，取其余数作为存储该元素的散列地址，m一般取小于或等于散列表长的最大素数，在这里取m=11，表长也为11，因此可得到每个元素的的散列地
址：
H(31)=31%11=9；H(62)=62%11=7；
H(74)=74%11=8；H(36)=36%11=3；
H(49)=49%11=5；H(77)=77%11=0；
如果根据散列地址把上述元素存储到散列表HT[m]中，则存储结构为：
散列的基本概念
从散列表中查找元素与插入元素一样简单，如从HT中查找关键字为36的元素时，只要利用上述散列函数H(key)计算出key=36时的散列地址3，则从下标为3的单元中取出该元素即可。
在上面的散列表上插入时根据元素的关键字计算出的散列地址，其对应的存储单元都是空闲的，没有出现该单元已被其它元素占的情况。在实际应用中这种理想的情况是很少见的，例如，要在上面的散列表中插入一个关键字为19的元素时，计算出其散列地址为8，而8号单元已被关键字为74的元素所占用，通常我们把这种现象称为冲突。具相同散列地址的关键字称为同义词。因此，在设计散列函数时，要尽量减少或没有冲突存在，但少量的冲突往往是不可避免的。这样就存在如何解决冲突的问题。冲突的频度除了与散列函数H相关外，还与散列表的填满程度相关。因此，如何尽量避免冲突和冲突发生后如何解决冲突就成了散列存储的两个关键问题。
构造散列函数的目标是使散列地址尽可能均匀分布在散列空间上，同时使计算尽可能简单。构造散列函数的方法很多，常用的构造散列函数的方法有如下几种。
1．直接地址法
直接地址法是以关键字key本身或关键字加上某个常量C作为散列地址的方法。对应的散列函数H(key)为：
H(key)＝key＋c
在使用时，为了使散列地址与存储空间吻合，可以调整c。这种方法计算简单，并且没有冲突。它适合于关键字的分布基本连续的情况，若关键字分布不连续，空号较多，将会造成较的空间浪费。
2．数字分析法
数字分析法是假设有一组关键字，每个关键字由n位数字组成，如k1，k2…kn。数字选择法是从中提取数字分布比较均匀的若干位作为散列地址。
例如，有一组有6位数字组成的关键字，如下表左边一列表示：
关键字散列地址(0..99)
散列的基本概念
分析这一组关键字会发现，第1、3、5和6位数字分布不均匀，第1位数字全是9或8，第3位基本上都是2，第5、6两位上也都基本上是5和6，故这4位不可取。而第2、4两位数字分布比较均匀，因此可取关键字中第2、4两位的组合作为散列地址，如上表的右边一列所示。
3．除余数法
除余数法是选择一个适当的p（p≤散列表长m）去除关键字k，所得余数作为散列地址的方法。对应的散列函数H（k）为：
H(k)＝k％p
其中p最好选取小于或等于表长m的最大素数。如表长为20，那么p选19，若表长为25，则p可选23，…。表长m与模p的关系可按下表对应：
m=8，16，32，64，128，256，512，1024，…
p=7，13，31，61，127，251，503，1019，…
这是一种最简单，也是最常用的一种散列函数构造方法。在上一节中我们已经使用过。
4.平方取中法
平方取中法是取关键字平方的中间几位作为散列地址的方法，因为一个乘积的中间几位和乘数的每一位都相关，故由此产生的散列地址较为均匀，具体取多少位视实际情况而定。例如有一组关键字集合(0100,0110,0111,1001,1010,1110),平方之后得到新的数据集合(0010000,0012100,0012321,1002001,1020100,123210),那么，若表长为1000，则可取其中第3、4和5位作为对应的散列地址为(100，121，123，020，201，321)。
(5)折叠法
折叠法是首先把关键字分割成位数相同的几段（最后一段的位数可少一些），段的位数取决于散列地址的位数，由实际情况而定，然后将它们的叠加和（舍去最高进位）作为散列地址的方法。
折叠法又分移位叠加和边界叠加。移位叠加是将各段的最低位对齐，然后相加；边界叠加则是将两个相邻的段沿边界来回折叠,然后对齐相加。
例如，关键字k=98123658,散列地址为3位，则将关键字从左到右每三位一段进行划分，得到的三个段为981、236和58，叠加后值为1275，取低3位275作为关键字98123658的元素的散列地址；如若用边界叠加，即为981、632和58叠加后其值为1671，取低3位得671作为散列地址。
散列法构造表可通过散列函数的选取来减少冲突，但冲突一般不可避免，为此，需要有解决冲突的方法，常用的解决冲突的方法有两大类，即开放定址法和链地址法。
1．开放定址法
开放定址法又分为线性探插法、二次探查法和双重散列法。开放定址法解决冲突的基本思想是：使用某种方法在散列表中形成一个探查序列，沿着次序列逐个单元进行查找，直到
找到一个空闲的单元时将新结点存入其中。假设散列表空间为T[0..m-1]，散列函数H(key)，开放定址法的一般形式为：hi=(H(key)+di)%m0≤i≤m-1
其中di为增量序列，m为散列表长。h0=H(key)为初始探查地址(假d0=0),后续的探查地址依次是h1,h2,…,hm-1。
(1)线性探查法
线性探查法的基本思想是：将散列表T[0..m-1]看成一个循环向量，若初始探查的地址为d(即H(key)=d)，那么，后续探查地址的序列为：d+1,d+2，…，m-1,0,1,…,d-1。也就是说，探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1],…,T[m-1]，此后又循环到T[0],T[1],…,T[d-1]。分两种情况分析，一种运算是插入：若当前探查单元为空，则将关键字key写入空单元，若不空则继续后序地址探查，直到遇到空单元插入关键字，若探查到T[d-1]时仍未发现空单元，则插入失败（表满）；另一种运算是查找，若当前探查单元关键字值等于key,则表示查找成功，若不等于，则继续后序地址探查，若遇到单元关键字值等于key时，查找成功，若探查T[d-1]时仍未发现关键字值等于key,则查找失败。
(2)二次探查法
二次探查法的探查序列是:hi=(H(key)+i2)%m0≤i≤m-1
即探查序列为：d=H(key),d+12,d+22,…,等。也就是说，探查从地址d开始，先探查T[d],然后在依次探查T[d+12],T[d+22],…。
(3)双重散列法
双重散列法是几种方法中最好的方法，它的探查序列为：
hi=(H(key)+i*H1(key))%m0≤i≤m-1
即探查序列为：d=H(key),(d+1*H1(key))%m，(d+2*H1(key))%m，…，等。
【例9.4】设散列函数为h(key)=key%11；散列地址表空间为0~10，对关键字序列{27，13，55，32，18，49，24，38，43}，利用线性探测法解决冲突，构造散列表。
解：首先根据散列函数计算散列地址：
h(27)=5；h(13)=2；
h(55)=0；h(32)=10；
h(18)=7；h(49)=5；
h(24)=2；h(38)=5；
h(43)=10；
(散列表各元素查找比较次数标注在结点的上方或下方)
根据散列函数计算得到的散列地址可知，关键字27、13、55、32、18插入的地址均为开放地址，将它们直接插入到T[5],T[2],T[0],T[10],T[7]中。当插入关键字49时，散列地址5已被同义词27占用，因此探查h1=(5+1)%11=6，此地址为开放地址，因此可将49插入到T[6]中；当插入关键字24时，其散列地址2已被同义词13占用，故探测地址
h1=(2+1)%11=3,此地址为开放地址，因此可将24插入到T[3]中；当关键字38插入时，散列地址5已被同义词27占用，探查h1=(5+1)%11=6,也被同义词49占用，再探查
h2=(5+2)=7，地址7已被非同义词占用，因此需要再探查h3=(5+3)%11=8，此地址为开放
地址，因此可将38插入到T[8]中；当插入关键字43时，计算得到散列地址10已被关键字32占用，需要探查h1=(10+1)%11=0,此地址已被占用，探查h2=(10+1)%11=1为开放地址，因此可将43插入到T[1]中；由此构造的散列表如图9.13所示。
散列的基本概念
2.拉链法（链地址法）
当存储结构是链表时，多采用拉链法，用拉链法处理冲突的办法是：把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0..m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针。
例如，按上面例9.4所给的关键字序列，用拉链法构造散列表如图９.14所示。
散列的基本概念
用拉链法处理冲突，虽然比开放定址法多占用一些存储空间用做链接指针，但它可以减少在插入和查找过程中同关键字平均比较次数(平均查找长度)，这是因为，在拉链法中待比较的结点都是同义词结点，而在开放定址法中，待比较的结点不仅包含有同义词结点，而且包含有非同义词结点，往往非同义词结点比同义词结点还要多。
如前面介绍的例9.4中，用线性探测法构造散列表的过程，我们知道，对前5个关键字的查找，每一个仅需要比较一次，对关键字49和24的查找，则需要比较2次，对关键字38的查找则需要比较4次，而对43的查找则需要比较3次。因此，对用线性探测法构造的散列表的平均查找长度为：
ASL=(1×5＋2×2＋3×1＋4×1)/9≈1.78
而用拉链法构造的散列表上查找成功的平均查找长度为：
ASL=(1×5+2×3+3×1)/9≈1.55
显然，开放定址法处理冲突的的平均查找长度要高于拉链法处理冲突的平均查找长度。但它们都比前面介绍的其它查找方法的平均查找长度要短。
南京师范大学 硕士学位论文 基于决策树的分类方法研究 姓名：戴南 申请学位级别：硕士 专业：计算数学（计算机应用方向） 指导教师：朱玉龙 2003.5.1
摘要 厂 ｛数掘挖掘，又称数据库中的知识发现，是指从大型数据库或数据仓库中提取 具有潜在应用价值的知识或模式。模式按其作用可分为两类：描述型模式和预测型模式。分类模式是一种重要的预测型模式。挖掘分娄模式的方法有多种，如决 策树方法、贝叶斯网络、遗传算法、基于关联的分类方法、羊Ｈ糙集和ｋ一最临近方、／ 法等等。，／驴 Ｉ 本文研究如何用决策树方法进行分类模式挖掘。文中详细阐述了几种极具代表性的决策树算法：包括使用信息熵原理分割样本集的ＩＤ３算法；可以处理连续属性和属性值空缺样本的Ｃ４．５算法；依据ＧＩＮＩ系数寻找最佳分割并生成二叉决策树的ＣＡＲＴ算法；将树剪枝融入到建树过程中的ＰＵＢＬＩＣ算法：在决策树生成过程中加入人工智能和人为干预的基于人机交互的决策树生成方法；以及突破主存容量限制，具有良好的伸缩性和并行性的ＳＩ，ｌＱ和ＳＰＲＩＮＴ算法。对这些算法的特点作了详细的分析和比较，指出了它们各自的优势和不足。文中对分布式环境下的决策树分类方法进行了描述，提出了分布式ＩＤ３算法。该算法在传统的ＩＤ３算法的基础上引进了新的数掘结构：属性按类别分稚表，使得算法具有可伸缩性和并行性。最后着重介绍了作者独立完成的一个决策树分类器。它使用的核心算法为可伸缩的ＩＤ３算法，分类器使用ＭｉｃｒｏｓｏｆｔＶｉｓｕａｌｃ＋＋６．０开发。实验结果表明作者开发的分类器可以有效地生成决策树，建树时间随样本集个数呈线性增长，具有可伸缩性。。 ，，荡囊 关键字：数据挖掘１分类规则，决策树，分布式数据挖掘
C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习：给定一个数据集，其中的每一个元组都能用一组属性值来描述，每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习，找到一个从属性值到类别的映射关系，并且这个映射能用于对新的类别未知的实体进行分类。 C4.5由J.Ross Quinlan在ID3的基础上提出的。ID3算法用来构造决策树。决策树是一种类似流程图的树结构，其中每个内部节点（非树叶节点）表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点存放一个类标号。一旦建立好了决策树，对于一个未给定类标号的元组，跟踪一条有根节点到叶节点的路径，该叶节点就存放着该元组的预测。决策树的优势在于不需要任何领域知识或参数设置，适合于探测性的知识发现。 从ID3算法中衍生出了C4.5和CART两种算法，这两种算法在数据挖掘中都非常重要。下图就是一棵典型的C4.5算法对数据集产生的决策树。 数据集如图1所示，它表示的是天气情况与去不去打高尔夫球之间的关系。
图1 数据集 图2 在数据集上通过C4.5生成的决策树 算法描述
C4.5并不一个算法，而是一组算法—C4.5，非剪枝C4.5和C4.5规则。下图中的算法将给出C4.5的基本工作流程： 图3 C4.5算法流程 我们可能有疑问，一个元组本身有很多属性，我们怎么知道首先要对哪个属性进行判断，接下来要对哪个属性进行判断？换句话说，在图2中，我们怎么知道第一个要测试的属性是Outlook，而不是Windy？其实，能回答这些问题的一个概念就是属性选择度量。 属性选择度量 属性选择度量又称分裂规则，因为它们决定给定节点上的元组如何分裂。属性选择度量提供了每个属性描述给定训练元组的秩评定，具有最好度量得分的属性被选作给定元组的分裂属性。目前比较流行的属性选择度量有--信息增益、增益率和Gini指标。
3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”，
基于分类回归树的个人信用评价模型 孟昭睿 （中国建设银行股份有限公司河南总审计室，河南郑州450003） 摘要：分类回归树作为一种基于统计理论、计算机实现的非参数识别技术，在个人信用评估领域有着良好的应用前景。文章主要探讨如何利用分类回归树建立个人信用评价模型。实证结果表明：该模型对个人信用评价可取得较好的效果。 关键词：分类回归树；信用评价；决策树 中图分类号：TP311文献标识码:A 文章编号:1006-8937（2009）02-0076-02 On the individual credit evaluation mode based on the assoeted recursive tree MENG Zhao-rui (Henan General Accounting Office,China Construction Bank Corporation,Zhengzhou,Henan 450003,China ) Abstract ：The classified return tree takes one kind the non-parameter recognition technology which based on the statistical theory,the computer realizes,has the good application prospect in individual credit appraisal domain.How does the article mainly discuss establishes individual credit status model using the classified return tree.The real diagnosis result indicated:This model may make the good progress to individual credit status.Keywords ：assoeted recursive tree;credit evaluation;decision tree 1引言随着金融的全球化趋势和银行业竞争的加剧，如何有 效地控制和防范商业银行的信贷风险正在受到越来越广泛的重视。如何在扩大信贷规模的同时准确分析客户的信用风险状况，确立合理的个人信贷标准是银行进行市场竞争的有力武器。目前，国内商业银行过去制定的个人消费信贷评价体系大多是基于专家或信贷员的经验，主观地设定各指标评分和权重。根据内部调查，许多银行反映其个人信用评估部分指标的设置和权重分配不合理，不能很好地判别申请客户的信用状态。建立科学有效的信用评价模型，对促进个人消费信贷业的发展，降低银行个人信贷风险无疑有着十分重要的作用。 2分类回归树原理 作为一种自动预测方法的分类回归树CART 不仅可以同时利用连续特征和离散特征来进行训练，并且也可以模拟非线性的关系。利用分类回归树可以自动探测出高度复杂数据的潜在结构，重要模式和关系。探测出的知识又可用来构造精确和可靠的预测模型，应用于分类客户、保险诈骗和信用风险管理。从技术上来讲，CART 技术可称为二元回归分解技术。CART 是一种有监督学习算法，即用户在使用他进行预测之前，首先需要提供一个训练样本集对CART 进行构建和评估，然后才能使用。 2.1构建分类树 构建分类树T max ，的过程，即为树的每个节点选择拆分规 则的过程。具体过程如下：所有的数据样本都属于树根节点t ，寻找第一个拆分规则即选择整棵树根节点的分支条件时，首先从第一个预测变量开始扫描，计算并记录样本数据中该变量的每一个取值或每两个相邻数据的中值作为拆分阀值时节点的不纯度函数下降值，然后扫描第二个预测变量，同样计算并记录该变量的各个不纯度函数下降值，直至扫描完最后一个预测变量，计算并记录完所有的拆分阀值对应的不纯度下降值。最后找出不纯度函数下降值最大时所对应的拆分变量和拆分阀值，将其定义为树根节点的拆分变量和拆分阀值。此时，已经将整个样本数据集分成两个子集，对于每一个子集，重复上述寻找树根节点拆分规则的扫描过程，寻找每个子集所属子树的根节点的拆分规则。 假设为寻找左子树的根节点t L 的拆分规则，也是从第一个预测变量开始扫描，计算并记录属于左子树的样本数据集中该变量的每一个取值或每两个相邻数据的中值作为拆分阀值时节点的不纯度函数下降值，直至扫描完最后一个预测变量，并找出使节点t L 不纯度函数下降值最大时所对应的拆分变量和拆分阀值，将其定义为左子树根节点的拆分变量和拆分阀值。同理寻找右子树的根节点拆分规则，则每棵子树又被拆分成两棵更小的子树。 整棵树的建立过程就是一个寻找更小子树根节点的拆分规则的过程。当节点满足以下条件之一时停止拆分操作。其一，节点很小：分支后的叶节点的样本数小于给定的值N min (一般Nmin=5， 有时为1)。其二，纯节点：分支后的叶节点中的样本属于同一个类。其三，空属性向量集：无属性向量 收稿日期：2008-12-28 作者简介：孟昭睿（1970），女，中国建设银行股份有限公司河南总审计 室，中级会计师中级经济师. 第28卷第2期V ol.28No.2 企业技术开发 TECHNOLOGICAL DEVELOPMENT OF ENTERPRISE 2009年2月Feb.2009
1 分类的概念及分类器的评判 分类是数据挖掘中的一个重要课题。分类的目的是学会一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。 分类可描述如下：输入数据，或称训练集（training set）是一条条记录组成的。每一条记录包含若干条属性（attribute），组成一个特征向量。训练集的每条记录还有一个特定的类标签（类标签）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：(v1,v2,…,…vn:c)。在这里vi表示字段值，c表示类别。 分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型。这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意是预测，而不能肯定。我们也可以由此对数据中的每一个类有更好的理解。也就是说：我们获得了对这个类的知识。 对分类器的好坏有三种评价或比较尺度： 预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法是10番分层交叉验证法。 计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。 模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越受欢迎；例如，采用规则表示的分类器构造法就更有用。 分类技术有很多，如决策树、贝叶斯网络、神经网络、遗传算法、关联规则等。本文重点是详细讨论决策树中相关算法。
决策树(ID3 C4.5 CART)原理+推导+代码 文章目录简介初识决策树特征选择信息增益信息增益比ID3C4.5决策树剪枝CART 分类与回归树简述：回归树的生成分类树的生成CART剪枝优缺点决策树ID3、C4.5算法CART分类与回归树适用场景代码决策树模型，自己总结了很久，也认为比较全面了。现在分享一下自己总结的东西。 这里面我只捡精炼的说，基本上都是干货，然后能用人话说的，我也不会疯狂排列数学公式。 初识决策树 决策树其实是用于分类的方法，尤其是二分类就是是非题，不过当然不限于二分，然后CART可以应用于分类和回归。其中对于回归的处理让我很是佩服。 树形结构模型，可以理解为if-else集合。 三个步骤 特征选择 生成决策树 节点和有向边组成。 结点包括内节点（一个特征和属性）叶子节点（一个类） 先看一下模型图 每个有向边都是一条规则，节点出度规则是完备的。 算法基本流程
根据训练集生成决策树。 根据测试集剪枝。 特征选择 特征选择我们有一个潜意识里的认识，就是希望选取对于分类有帮助的特征。 那么这里采用信息增益的指标来判断。 什么是信息增益？ 信息增益 什么是熵 用来度量随机变量的不确定性的，熵越大，不确定性越高。 所以我们得到了信息增益的算法： 根据上述方法我们可以得到一个属性的排序。 信息增益比 根据上面的公式其实是更有益于选择那些属性值多的属性，这是需要改进的，所以我们增加一个分母。 得到信息增益比的定义： 知道了我们如何选择特征了，接下来就是生成决策树的算法了，一共有两种，先介绍一下ID3。 简单来说就是根据信息增益从大到小进行排序来选择结点。 算法简述： 从根节点开始，选择信息增益最大的属性来划分children结点。 然后选择每个孩子结点来作为根节点，再根据信息增益选择下一个属
如何运用决策树进行分类分析 前面我们讲到了聚类分析的基本方法，这次我们来讲讲分类分析的方法。 所谓分类分析，就是基于响应，找出更好区分响应的识别模式。分类分析的方法很多，一般而言，当你的响应为分类变量时，我们就可以使用各种机器学习的方法来进行分类的模式识别工作，而决策树就是一类最为常见的机器学习的分类算法。 决策树，顾名思义，是基于树结构来进行决策的，它采用自顶向下的贪婪算法，在每个结点选择分类的效果最好的属性对样本进行分类，然后继续这一过程，直到这棵树能准确地分类训练样本或所有的属性都已被使用过。 建造好决策树以后，我们就可以使用决策树对新的事例进行分类。我们以一个生活小案例来说什么是决策树。例如，当一位女士来决定是否同男士进行约会的时候，她面临的问题是“什么样的男士是适合我的，是我值得花时间去见面再进行深入了解的？” 这个时候，我们找到了一些女生约会对象的相关属性信息，例如，年龄、长相、收入等等，然后通过构建决策树，层层分析，最终得到女士愿意去近一步约会的男士的标准。 图：利用决策树确定约会对象的条件
接下来，我们来看看这个决策的过程什么样的。 那么，问题来了，怎样才能产生一棵关于确定约会对象的决策树呢？在构造决策树的过程中，我们希望决策树的每一个分支结点所包含的样本尽可能属于同一类别，即结点的”纯度”（Purity ）越来越高。 信息熵（Information Entropy ）是我们度量样本集合纯度的最常见指标，假定当前样本集合中第K 类样本所占的比例为P k ，则该样本集合的信息熵为： Ent (D )=?∑p k |y| k=1 log 2p k 有了这个结点的信息熵，我们接下来就要在这个结点上对决策树进行裁剪。当我们选择了某一个属性对该结点，使用该属性将这个结点分成了2类，此时裁剪出来的样本集为D 1和D 2， 然后我们根据样本数量的大小，对这两个裁剪点赋予权重|D 1||D|?，|D 2||D|?，最后我们就 可以得出在这个结点裁剪这个属性所获得的信息增益（Information Gain ） Gain(D ，a)=Ent (D )?∑|D V ||D |2 v=1Ent(D V ) 在一个结点的裁剪过程中，出现信息增益最大的属性就是最佳的裁剪点，因为在这个属性上，我们获得了最大的信息增益，即信息纯度提升的最大。 其实，决策树不仅可以帮助我们提高生活的质量，更可以提高产品的质量。 例如，我们下表是一组产品最终是否被质检接受的数据，这组数据共有90个样本量，数据的响应量为接受或拒绝，则|y|=2。在我们还没有对数据进行裁剪时，结点包含全部的样本量，其中接受占比为p 1= 7690，拒绝占比为p 2=1490，此时，该结点的信息熵为： Ent (D )=?∑p k |y|k=1log 2p k =-（7690log 27690+1490log 21490）=0.6235
基于专家知识的决策树分类 概述 基于知识的决策树分类是基于遥感影像数据及其他空间数据，通过专家经验总结、简单的数学统计和归纳方法等，获得分类规则并进行遥感分类。分类规则易于理解，分类过程也符合人的认知过程，最大的特点是利用的多源数据。 如图1所示，影像+DEM就能区分缓坡和陡坡的植被信息，如果添加其他数据，如区域图、道路图土地利用图等，就能进一步划分出那些是自然生长的植被，那些是公园植被。 图1.JPG 图1 专家知识决策树分类器说明图 专家知识决策树分类的步骤大体上可分为四步：知识（规则）定义、规则输入、决策树运行和分类后处理。 1.知识（规则）定义 规则的定义是讲知识用数学语言表达的过程，可以通过一些算法获取，也可以通过经验总结获得。 2.规则输入
将分类规则录入分类器中，不同的平台有着不同规则录入界面。 3.决策树运行 运行分类器或者是算法程序。 4.分类后处理 这步骤与监督/非监督分类的分类后处理类似。 知识（规则）定义 分类规则获取的途径比较灵活，如从经验中获得，坡度小于20度，就认为是缓坡，等等。也可以从样本中利用算法来获取，这里要讲述的就是C4.5算法。 利用C4.5算法获取规则可分为以下几个步骤： （1）多元文件的的构建：遥感数据经过几何校正、辐射校正处理后，进行波段运算，得到一些植被指数，连同影像一起输入空间数据库；其他空间数据经过矢量化、格式转换、地理配准，组成一个或多个多波段文件。 （2）提取样本，构建样本库：在遥感图像处理软件或者GIS软件支持下，选取合适的图层，采用计算机自动选点、人工解译影像选点等方法采集样本。 （3）分类规则挖掘与评价：在样本库的基础上采用适当的数据挖掘方法挖掘分类规则，后基于评价样本集对分类规则进行评价，并对分类规则做出适当的调整和筛选。这里就是C4.5算法。 4.5算法的基本思路基于信息熵来“修枝剪叶”，基本思路如下： 从树的根节点处的所有训练样本D0开始，离散化连续条件属性。计算增益比率，取GainRatio（C0）的最大值作为划分点V0，将样本分为两个部分D11和D12。对属性C0的每一个值产生一个分支，分支属性值的相应样本子集被移到新生成的子节点上，如果得到的样本都属于同一个类，那么直接得到叶子结点。相应地将此方法应用于每个子节点上，直到节点的所有样本都分区到某个类中。到达决策树的叶节点的每条路径表示一条分类规则，利用叶列表及指向父结点的指针就可以生成规则表。
科技论坛 0 引言 图像识别技术，要运用目前流行的机器学习算法，而目前流行的机器学习算法就有十几种，比如支持向量机、神经网络、决策树。机器学习是人工智能发展的重要一部分，它涉及的学科很多，应用也相当广泛，它通过分析、研究、设计让计算机学习知识，从而提高完善自身的性能。但是神经网络学习的速度较慢，传统的支持向量机则不能解决分类多的问题。 本文针对鸢尾花的特征类别少以及种类少的特点，采用决策树算法对课题进行展开，对比与其他人利用支持向量机、神经元网络模型来进行研究，该系统具有模型简单、便于理解、计算方便、消耗资源少的优点。 1 决策树模型和学习 本文采用决策树算法对鸢尾花进行分类，先建立决策树的模型并进行学习训练，在决策树的训练过程中采用是信息论的知识进行特征选择，对选定的特征采用分支的处理，然后再对分支过后的数据集如此反复的递归生成决策树，在一颗决策树生成完后对决策树进行剪枝，以减小决策树的拟合度，来达到一个对鸢尾花较高的分类准确率。 要对鸢尾花进行分类首先需要大量的鸢尾花数据集作为本文的实验数据，本文采用的数据集是来自加州大学欧文分校UCI数据库中的鸢尾花数据集。该数据集中鸢尾花的属性有四个，分别是花萼长度、花萼宽度、花瓣长度和花瓣宽度，鸢尾花的类别则有三种，分别是Iris Setosa，Iris Versicolour，Iris Virginica，用简写Se、Ve和Vi表示这三种花，具体数据如图1所示。 ■1.1 信息论 美贝尔电话研究所的数学家香农是信息论的创始人，1948年香农发表了《通讯的数学理论》,成为信息论诞生的标志。信息论的诞生对信息技术革命以及科学技术的发展起到重要作用。信息论中有两个概念信息增益及信息增益率，都是用于衡量原始数据集在按照某一属性特征分裂之后整体信息量的变化值。这样，本文就可以通过这种指标寻找出最优的划分属性，数据集在经过划分之后，节点的“纯度”越来越高，这里的纯度值得是花朵的类别，当某一节点中花朵全为一类时，该节点已经达到最纯状态，无需再进行划分， 反之继续划分。 图1 鸢尾花数据集 1.1.1 信息熵 信息熵用于描述信源的不确定性。即发生每个事件都有不确定性，为了使不确定性降低，我们需要引入一些相关的信息进行学习，引入信息越多，那么得到的准确率越高，信息熵越高，信源越不稳定。例如一束鸢尾花，它可能是Se,可能是Vi，也有可能是Ve，我们利用数据库中的各种鸢尾花的花瓣长度、花瓣宽度、花萼长度和花萼宽度来预测鸢尾花的类别，引入的鸢尾花种类越多，信息熵就越高。 样本集合D的信息熵Ent(D)以下面的公式进行计算，其中集合里第k类样本所占的比例是k p，k的取值范围是从1到y，y值得是总共有y类样本，通过式（1）可以计算得到原始样本集的信息熵。 ()21 Ent D y k k k p log p = =?∑(1) 1.1.2 信息增益 信息增益即在一个条件下，信源不确定性减少的程度。信息增益用于度量节点的纯度。信息增益对可取值数目较多的属性有所偏好。在鸢尾花数据集的D集合中，属性a取到某一取值情况的概率乘该取值情况的信息熵得到的值记为v D，其中V指的是该属性a可以取值的个数，则属性a 的信息增益为： ()()() 1 Gain D,a Ent D V v v v D Ent D D = =?∑(2) 基于决策树的鸢尾花分类 徐彧铧 （浙江省衢州第二中学，浙江衢州，324000） 摘要：针对传统手工分类的不足，满足不了人们对图片分类的需求，本文利用机器学习算法中的决策树算法进行研究。通过模型简单、便于理解、计算方便、消耗资源少的决策树算法模型，并利用现成的数据库，运用图像识别技术对鸢尾花进行分类，以求方便简单快速地识别出不同类别的鸢尾花。在此过程中，学习到图像识别的一些基本分类操作，为我们实现更复杂的模型提供了帮助。 关键词：决策树信息论特征选择；C4.5算法；CART算法 www ele169 com | 99
决策树分类算法 决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。 1．决策树的组成 决策树的基本组成部分有：决策节点、分支和叶，树中每个内部节点表示一个属性上的测试，每个叶节点代表一个类。图1就是一棵典型的决策树。 图1 决策树 决策树的每个节点的子节点的个数与决策树所使用的算法有关。例如，CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。 下面介绍一个具体的构造决策树的过程，该方法
是以信息论原理为基础，利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的一个节点，然后再根据字段的不同取值建立树的分支，在每个分支中重复建立树的下层节点和分支。 ID3算法的特点就是在对当前例子集中对象进行分类时，利用求最大熵的方法，找出例子集中信息量（熵）最大的对象属性，用该属性实现对节点的划分，从而构成一棵判定树。 首先，假设训练集C 中含有P 类对象的数量为p ，N 类对象的数量为n ，则利用判定树分类训练集中的对象后，任何对象属于类P 的概率为p/(p+n)，属于类N 的概率为n/(p+n)。 当用判定树进行分类时，作为消息源“P ”或“N ”有关的判定树，产生这些消息所需的期望信息为： n p n log n p n n p p log n p p )n ,p (I 22++-++- = 如果判定树根的属性A 具有m 个值｛A 1, A 2, …, A m ｝，它将训练集C 划分成｛C 1, C 2, …, C m ｝，其中A i 包括C 中属性A 的值为A i 的那些对象。设C i 包括p i 个类P 对象和n i 个类N 对象，子树C i 所需的期望信息是I(p i , n i )。以属性A 作为树根所要求的期望信息可以通过加权平均得到
决策树分类 决策树（Decision Tree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internal node）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（leaf）代表某个类（class）或者类的分布（class distribution），最上面的结点是根结点。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。 构造决策树是采用自上而下的递归构造方法。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为(a = b)的逻辑判断，其中a 是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。 使用决策树进行分类分为两步： 第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。 第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。 问题的关键是建立一棵决策树。这个过程通常分为两个阶段： (1) 建树（Tree Building）：决策树建树算法见下，可以看得出，这是一个递归的过程，最终将得到一棵树。 (2) 剪枝（Tree Pruning）：剪枝是目的是降低由于训练集存在噪声而产生的起伏。 决策树方法的评价。 优点 与其他分类算法相比决策树有如下优点： (1) 速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。 (2) 准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。 缺点 一般决策树的劣势： (1) 缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在Irvine机器学习知识库中，最大可以允许的数据集仅仅为700KB，2000条记录。而现代的数据仓库动辄存储几个G-Bytes的海量数据。用以前的方法是显然不行的。
1.1.1. 分类回归树 分类回归树(Classification and regression trees,CART)是决策树的一种，它是基于吉尼(Gini)指标(并且是最简化的吉尼指标)的方法。 在OpenCV 下函数icvCreateCARTStageClassifier 实现层强分类器的构建，而它又调用了icvCreateCARTHaarClassifier 、icvInitCARTHaarClassifier 、icvEvalCARTHaarClassifier 实现了弱检测器的分类回归树的初始化、构建、赋值。 以下是简化了的算法描述：其中C 代表当前样本集，当前候选属性集用T 表示。 (1)新建一个根节点root (2)为root 分配类别(有人脸还是没有) (3)如果T 都属于同一类别(都是正样本或者反样本)或者C 中只剩下一个样本则返回root 为叶节点，为其分配属性。 (4)对任何一个T 中属性执行该属性上的划分，计算此划分的分类不纯度 (吉尼不纯度) (5)root 的测试属性是T 中最小GINI 系数的属性 (6)划分C 得到C1 C2子集 (7)对于节点C1重复(1)-(6) (8)对于节点C2重复(1)-(6) 至于CART 的修剪、评估等算法就不给出了。CART 的修剪的算法是分类错误算法。如果想深入了解CART 树，则阅读上节给出的参考书目。 1.1. 2. 弱分类器方法 弱分类器的种类很多，但OpenCV 使用的是效果最好的决策树分类器。关于分类器的介绍在第一章已经讨论过了，如果要有更深入理解可以看一些数据挖掘的图书后，再看看OpenCV 下的cvhaartraining.cpp 文件。这里特别提下弱分类器的阈值的寻找方法。 阈值寻找算法定义在icvFindStumpThreshold_##suffix 函数里面，它是通过一个宏被定义的。至于为什么通过这种方式定义，可以参考文献。[i] 函数icvFindStumpThreshold_##suffix 输入参数介绍：wk 是第k 个样本的权重，yk 是第k 个样本是正样本还是反样本，如果是正样本则为+1，反样本则为-1，lerror 、rerror 是要求的最低误差，lerror=rerror=3.402823466e+38F(超大的数值)，left 、right 是输出的误差。threshold 是阈值，found 为是否找到阈值，初始是0。 For i=1:num(对每个排序后的样本) (1)∑==i k k w wl 1 ，∑+==num i k k w wr 1 (2)k i k k y w wyl *1∑== ， k num i k k y w wyr *1∑+== (3)curleft=wyl/wl ， curright=wyr/wr (4)如果curlerror+currerror 分类与回归树 ———一种适用于临床研究的统计分析方法 赵一鸣 （北京大学第三医院临床流行病学研究中心，北京100083） ［关键词］临床研究；分类法；回归分析，统计学［摘 要］介绍分类与回归树（class ification and re g ress ion trees ，CART ） 的发展历史、结构、组成和特点。CART 包括分类树和回归树两部分，分类树的结果变量是分类变量，回归树的结果变量是连续变量。CART 是一种树型结构， 由树结和连线组成，在末端的树结又称为终止结。CART 可分析同质性较差的数据，采用替代变量的方法解决缺失数据问题，不要求数据的分布，可同时利用各种类型的数据。CART 的树型结构与临床思维十分接近，有利于CART 在临床研究中的应用。CART 可用于临床研究数据分析，其应用范围有待于不断扩展。［中图分类号］R4［文献标识码］B ［文章编号］1671-167X （2001）06-0562-04 C lassification and re g ression trees （a statistical m et hod suitable f or cli nical researches ） ZHAO y i-M i n g （C enter f or C li n ical E p i de m io lo g ical R esearch ，P eki n g U n ivers it y T h ird H os p ital ，B e i j i n g 100083，Ch i na ） KEY W ORD S C lassification ；R e g ression anal y sis ；C li nical research ；S tatistics ；A nal y sis SUMM ARY T o i ntroduce classification and re g ression trees （CART ）.T he develo p m ent ，struct ure ，m ai n ele m ents and f eat ures o f CART w ere i ntroduced.CART w as struct ured b y t w o p arts ，classifica-tion tree and re g ression tree.C lassification tree used nom i nal variable as outcom e ，and re g ression tree used conti nuous variable as outcom e.T ree struct ure w as t he f eat ure o f CART ，and it w as m ade u p o f tree notes and li nes.T he ter m i nal tree notes w ere na m ed end notes.CART w as suitable f or non-hom o-g eneous data anal y sis ， usi n g surro g ate to re p lace m issi n g data ，suitable f or an y distri buted data ，and all ki nd o f variables.T he tree struct ure o f CART w as ver y li ke cli nical t hou g ht w a y and suitable to ex p lai n results f or cli nical p ur p ose.CARTis a ne w statistical m et hod suitable f or cli nical data anal y sis.T he a pp lied ran g e o f CARTi n cli nical researches needs to be ex p anded. ［J pekin g UniO （~ealt h S ci ），2001，33：562-565］ 1970年， 美国4位统计学家分析了当时各种统计分析方法存在的缺陷，提出一种既可以包容这些统计分析方法优点，又能克服其缺陷的新的统计分析方法 分类与回归树 （class ification and re g ress ion trees ，CART ） 。至1984年CART 的理论模型研究基本完善［1］，但其计算量非常大，在当时的微机上难以运行。直至1995年，出现了在486微机上运行的CART 统计分析软件，使其能够用于临床研究数据的统计分析。CART 的免费限时试用版软件可以从以下网站下载：htt p ：／／www.salf ord-s y ste m https://www.doczj.com/doc/2418762470.html, ／de m o.ht m l 。现将作者对CART 的认识和应用体会简介如下。1 分类与回归树的结构与组成 CART 由分类树（class ification tree ）和回归树（re g ress ion tree ） 两部分组成。分类树用于结果变量是分类变量的数据分析，回归树则用于结果变量是连续变量的数据分析。CART 是一种树型分析方法（图1、2），其结构类似一棵倒置的树，由主干和许多分支组成。在树中有许多节点，用椭圆形框和长方形框表示，称为树结（tree node ），其中长方形框又称为终止结（end node ）。每一个树结中有一些数字，为分析结果，在椭圆形框下方标有判别条件，树结间用实线连接。2 分类与回归树的特点及其在临床研究数据分析中的价值目前诊断疾病主要依据疾病的临床表型，以此为依据诊断患某种疾病的一组患者，其内部同质性（hom o g eneous ）有时较差，例如不同肺癌患者肿瘤的病理类型各异，组织学来源不同，生物学特征及其表型存在多样性，对治疗的反应和临床转归不同。这类数据采用单因素分析或多元线性回归、L o g istic 回归等归一化模型处理往往效果不理想， 因为这些?265?北京大学学报（医学版） J OURNAL OF PEK I NG UN I VERS I Ty （HEALTH SC I ENCES ）V o l .33N o.6 D ec .2001 论贝叶斯分类、决策树分类、感知器分类挖掘算法的优势与劣势 摘要本文介绍了在数据挖掘中数据分类的几个主要分类方法，包括：贝叶斯分类、决策树分类、感知器分类，及其各自的优势与劣势。并对于分类问题中出现的高维效应，介绍了两种通用的解决办法。 关键词数据分类贝叶斯分类决策树分类感知器分类 引言 数据分类是指按照分析对象的属性、特征，建立不同的组类来描述事物。数据分类是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。分类技术解决问题的关键是构造分类器。 一．数据分类 数据分类一般是两个步骤的过程： 第1步：建立一个模型，描述给定的数据类集或概念集（简称训练集）。通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有指导的学习。如果训练样本的类标号是未知的，则称为无指导的学习（聚类）。学习模型可用分类规则、决策树和数学公式的形式给出。 第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。 常用的分类规则挖掘方法 分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有以下几种方法，不同的方法适用于不同特点的数据：1．贝叶斯方法 2．决策树方法 3．人工神经网络方法 4．约略集方法 5．遗传算法 分类方法的评估标准： 准确率：模型正确预测新数据类标号的能力。 速度：产生和使用模型花费的时间。 健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。 伸缩性：对于给定的大量数据，有效地构造模型的能力。 可解释性：学习模型提供的理解和观察的层次。 影响一个分类器错误率的因素 (1) 训练集的记录数量。生成器要利用训练集进行学习，因而训练集越大，分类器也就越可靠。然而，训练集越大，生成器构造分类器的时间也就越长。错误率改善情况随训练集规模的增大而降低。 (2) 属性的数目。更多的属性数目对于生成器而言意味着要计算更多的组合，使得生成器难度增大，需要的时间也更长。有时随机的关系会将生成器引入歧途，结果可能构造出不够准确的分类器（这在技术上被称为过分拟合）。因此，如果我们通过常识可以确认某个属性与目标无关，则将它从训练集中移走。 (3) 属性中的信息。有时生成器不能从属性中获取足够的信息来正确、低错误率地预测标签（如试图根据某人眼睛的颜色来决定他的收入）。加入其他的属性（如职业、每周工作小时数和年龄），可以降低错误率。 (4) 待预测记录的分布。如果待预测记录来自不同于训练集中记录的分布，那么错误率有可能很高。比如如果你从包含家用轿车数据的训练集中构造出分类器，那么试图用它来对包含许多运动用车辆的记录进行分类可能没多大用途，因为数据属性值的分布可能是有很大差别的。 评估方法 有两种方法可以用于对分类器的错误率进行评估，它们都假定待预测记录和训练集取自同样的样本分布。 (1) 保留方法(Holdout)：记录集中的一部分（通常是2/3）作为训练集，保留剩余的部分用作测试集。生成器使用2/3 的数据来构造分类器，然后使用这个分类器来对测试集进行分类，得出的错误率就是评估错误率。 虽然这种方法速度快，但由于仅使用2/3 的数据来构造分类器，因此它没有充分利用所有的数据来进行学习。如果使用所有的数据，那么可能构造出更精确的分类器。 (2) 交叉纠错方法(Cross validation)：数据集被分成k 个没有交叉数据的子集，所有子集的大小大致相同。生成器训练和测试共k 次；每一次，生成器使用去除一个子集的剩余数据作为训练集，然后在被去除的子集上进行测试。把所有 分类决策树 原理 决策树（Decision Tree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，对未知的数据进行分类。如何预测, 先看看下面的数据表格： 上表根据历史数据，记录已有的用户是否可以偿还债务，以及相关的信息。通过该数据，构建的决策树如下： 如新来一个用户：无房产，单身，年收入55K，那么根据上面的决策树，可以预测他无法偿还债务（蓝色虚线路径）。从上面的决策树，还可以知道是否拥有房产可以很大的决定用户是否可以偿还债务，对借贷业务具有指导意义。 决策树构建的基本步骤如下： 1. 开始所有记录看作一个节点 2. 遍历每个变量的每一种分割方式，找到最好的分割点 3. 分割成两个节点N1和N2 4. 对N1和N2分别继续执行2-3步，直到每个节点足够“纯”为止 构建决策树的变量可以有两种： 1）连续型：如前例中的“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。 2）分类型：如前例中的“婚姻情况”，使用“=”来分割。 如何评估分割点的好坏？如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。比如上面的例子，“拥有房产”，可以将记录分成了两类，“是”的节点全部都可以偿还债务，非常“纯”；“否”的节点，可以偿还贷款和无法偿还贷款的人都有，不是很“纯”，但是两个节点加起来的纯度之和与原始节点的纯度之差最大，所以按照这种方法分割。构建决策树采用贪心算法，只考虑当前纯度差最大的情况作为分割点。 纯度计算 前面讲到，决策树是根据“纯度”来构建的，如何量化纯度呢？这里介绍三种纯度计算方法。如果记录被分为n类，每一类的比例P(i)=第i类的数目/总数目。还是拿上面的例子，10个数据中可以偿还债务的记录比例为P(1) = 7/10 = 0.7，无法偿还的为 P(2) = 3/10 = 0.3，N = 2。 Gini不纯度： 熵（Entropy）： 错误率： 上面的三个公式均是值越大，表示越“不纯”，越小表示越“纯”。三种公式只需要取一种即可，对最终分类准确率的影响并不大，一般使用熵公式。 纯度差，也称为信息增益（Information Gain），公式如下： 其中，I代表不纯度（也就是上面三个公式的任意一种），K代表分割的节点数，一般K = 2。vj表示子节点中的记录数目。上面公式实际上就是当前节点的不纯度减去子节点不纯度的加权平均数，权重由子节点记录数与当前节点记录数的比例决定。 停止条件 决策树的构建过程是一个递归的过程，所以需要确定停止条件，否则过程将不会结束。一种最直观的方式是当每个子节点只有一种类型的记录时停止，但是这样往往会使得树的节点过多，导致过度拟合（Overfitting）。另一种可行的方法是当前节点中的记录数低于一个最小的阀值，那么就停止分割，将max(P(i))对应的分类作为当前叶节点的分类。分类与回归树——一种适用于临床研究的统计分析方法
论贝叶斯分类、决策树分类、感知器分类挖掘算法的优势与劣势
分类决策树
相关主题
文本预览