模糊决策树算法FID3

Q

A

用户

今天发布什么呢？？？

HHY

今天讲决策树算法哦，不同于清晰决策树，利用了模糊逻辑的模糊决策树算法哦！

模糊隶属度

(a)三角形隶属度函数

(b)高斯隶属度函数

(c)梯形隶属度函数

（1）三角形模糊隶属度函数

（2）高斯模糊隶属度函数

（3）梯形模糊隶属度函数

（4）Sigmoid模糊隶属度函数

存在很多的隶属度函数，可以提供我们选择，我们可以根据不同的实际情况选择不同的隶属度函数，FID3算法中，由用户为每个特征提供隶属度函数，这是在算法执行之前需要处理的 ，可以归结为数据预处理阶段。

我们举个例子说明，我们假设有一个特征是age，然后我们可以把数字映射到不同的模糊区间，并且某一个年龄数字对于不同的区间有不同的隶属度。

模糊决策树

模糊决策树就是将特征应用了隶属度函数然后应用到决策树算法中，当然也存在区别：

什么区别呢？

清晰决策树一个实例属于一个叶子节点，但是模糊决策树中，一个实例可能会被划分多到多个叶子节点中，只要隶属度不为0就会分到到相应的分支知道叶子节点。

模糊决策树是传统清晰决策树的推广。模糊决策树是一种近似推理的技术，其有效地将决策树和模糊表示相结合。在学习模糊决策树算法时需要先对模糊决策树的一些基本定义进行充分地了解学习。它将模糊理论应用于训练与匹配过程中，结合了决策树的可理解性和模糊集合的表示能力用来处理模糊性和不确定性信息，使决策树拥有更好的健壮性，提高了决策树的可理解性，并使决策树归纳算法的扩展能力增强，具有代表的模糊决策树算法：Umano提出的Fuzzy ID3算法、Yuan和Shaw提出的Min-Ambiguity算法。

模糊决策树的归纳过程可以分为以下步骤

：

（1）数据预处理；

（2）归纳建立决策树；

（3）把得到的决策树转换成一组模糊规则；

（4）把得到的模糊规则用于分类。

模糊决策树同传统的决策树构造算法类似，模糊决策树也是采用从上而下的构造方法。

其中研究领域的几个关键部分包含：

（1）模糊决策树中的属性选择标准。传统决策树中选择测试属性的最常用的方法就是选择具有最大信息增益的属性作为决策树中的测试属性,而在模糊决策树中，很多基于该方法的改进和提高都得到了很好的研究；

（2）模糊决策树归纳过程。归纳过程是模糊决策树中一个很重要的部分，并且它和传统的决策树方法有所不同；

（3）模糊决策树停止增长的判断条件。传统决策树中一般所有的属性在当前路径上都得到了使用或者当前结点上样本属于同一分类的时候就停止增长。在模糊决策树算法中，由于引进了模糊理论导致每个样本属于不同的模糊集合，每个样本可能会被分发到不同的叶子节点中去，是的树的增长更加的复杂，在每个节点需要考虑更多的样本实例，但是比传统的清晰决策树具有更好的精度。为了高校地解决模糊决策树的树节点过多以及何时停止树的增长的问题，研究领域的学者提出了很多解决办法。

模糊决策树是通过把决策树以及模糊理论相结合而产生的算法，它具有二者的优点，同时也会有新的缺点。

但是总体来讲，模糊决策树的优点一般表现在如下几个方面：

（1）它具有和传统的决策树一样的构建的自上而下的过程，只是用到了模糊集。对于模糊决策树而言，在构造某个节点上某个属性也许不存在满足的分支，那么该属性会被模糊化进入多个分支，而不像传统的决策树一样，只允许一条数据进入一个分支；

（2）模糊集合和近似推理可以处理噪声、非一致和非完全的数据，它比清晰决策树更加的精确；

（3）模糊决策树使用了模糊隶属度函数，可以处理连续型和离散性数据。

同时模糊决策树也会存在一些缺点如下：

（1）模糊决策树与清晰决策树不同，因为每个样本隶属于不同的模糊集，因此可能会分发到不同的叶子节点，从而增加了计算的负担，占用内存较多，虽然牺牲了资源，但是保持了树的结构同时获得了更高的精度；

（2）模糊决策树不会像组合学习方法或者重抽样方法等那样具有突破性，因为它只是将决策树相关技术与模糊理论进行了结合。

传统的批处理模糊决策树算法如Fuzzy ID3算法，用户需要自定义每一个属性的隶属度函数和模糊集，通过引入模糊集方法取得了更高的准确率。数据预处理阶段会进行大量的工作，因此不适合数据流挖掘算法，需要引入最优隶属度函数进行数据模糊化。模糊决策树较传统决策树而言是一种软分类方法，其算法流程跟普通决策树构建过程类似，不同的是对每个属性值进行了模糊化，得到每个属性值对应的模糊隶属，进而通过模糊隶属度的和代替每个子集中每一类的出现频率，进行相关的信息增益等模糊熵的计算。

模糊信息增益

模糊信息增益只是在信息增益的公式上面稍微做了一些改变。

只是把之前的频率p换成了相关隶属度的东西,

信息增益中p()代表的是在某一个集合中，属于某一个类的样本占该集合样本总数的比例，在模糊决策树中，将其替换为属于某一类的样本的隶属度的和占该集合总样本隶属度和的比例，其中s代表了集合s隶属度的和。ck代表某一类。

FID3

上面图形为模糊决策树模型，其中边上的标识代表了每个样本从root到叶子节点时候的隶属度的值，β12代表第二个叶子节点属于第一类的隶属度值。计算公式如下：

实例属于每个类的隶属度值如下公式，μpathl代表实例到达l叶子节点经过的路径的隶属度的乘积

最终实例属于哪一个类取使得这个值最大的类