《数据挖掘》读书笔记4章
第四章 算法：基本方法
4.1 推断基本规则
选择一个属性作为最简单的分类规则，称为“1规则”（1-true），简称1R。
| 对于每个属性 对于这个属性的每个属性值，建立如下的一条规则： 计算每个类别出现的频率； 找出出现最频繁的类别； 建立规则，将这个类别赋予这个属性值； 计算规则的误差率； 选择误差率最小的规则 |
对于残缺值，采样作为另一个属性值的方法。对于1R算法，当一个属性存在大量的可能值时，过度拟合就很可能发生，需要对属性值适当处理。
4.2 统计建模
对所有属性，让它们对决策做出同等重要、彼此独立的贡献。这样的方法其理论基础是朴素贝叶斯方法。
对于训练集中某个属性值没有联合每一个类值一起出现，会出现某个条件概率为0，那么朴素贝叶斯法会出错。解决方法是运用拉普拉斯估计器（对每一项分子上加 ， ，分母加上 ）。
使用贝叶斯方法的一个优势是：处理残缺值不是难题，只需要省略这个属性即可。贝叶斯方法处理名词性属性时，只需要简单地统计频率，而处理数值值时，一般将它们假设成拥有“正态”或者“高斯”分布（更好的技术是采用“核密度估计”），计算均值与方差用于对新例计算在该属性上的概率。
朴素贝叶斯典型的应用就是运用于文档分类。
4.3 分治法：创建决策树
创建决策树是用递归方式选择依据哪个属性进行划分，问题是划分属性的顺序如何决定，采用信息量来度量属性选择的优劣。某属性划分所得的信息量越小（信息增益越大），效果越好。信息量计算公式为： 。递归划分的停止条件为当数据不能被进一步分裂时。最佳情况是，每个叶子节点都是纯的，即所属类别一致。
用信息量来衡量的缺陷在于：倾向于选择高度分支数量的属性，而这些属性往往对预测作用很小。因此，提出增益率的概念：只考虑属性分裂数据集后所产生子节点的数量和规模，而忽略类别的信息（ ）。用增益率可能补偿过度，造成倾向于选择某个属性的原因仅仅是因为这个属性的内在信息值比其他属性小的多。解决办法是：得到最大增益率的属性，并且该属性的信息增益至少等于所有属性的信息增益的平均值。
4.4 覆盖算法：建立规则
覆盖方法：依次取出每个类，寻找一个方法能覆盖所有属于这个类别的实例，同时能剔除不属于这个类别的实例。覆盖法的自身特性决定了它将产生一个规则集而不是一个决策树。覆盖法只关注于一次集中处理一个类别。
典型的方法是PRISM法，它只建立正确或者“完美”的规则，它利用正确率来衡量规则的成功率。其伪代码如下：
| 对于每个类别C 将实例集初始化为E 当E含有类别C的实例时 创建规则R，规则左边为空条件，预测类别为C 循环工作，直到R完美（或者没有属性可使用了） 对于每个在规则R中还未包含的属性A和属性值v 考虑添加条件A=v到规则R的左边 选择A和v，使正确率p/t最大化（最大覆盖量打破平局） 将A=v添加到规则R中 将规则R所覆盖的实例从E中删除 |
这样方法产生的是顺序独立的规则，缺点是可能出现模糊事件（多种分类或者压根没有分类），这时的解决方法是选择实例最多的分类。
4.5 挖掘关联规则
由于同时考虑覆盖量和正确率的不可行，这里只考虑高覆盖率，目的寻找能够达到预定最小覆盖量的属性-值（项）配对的组合。因此，有单项集、二项集、三项集等概念，其中只关注那些达到最小覆盖量的项集。（技术实现运用到散列表存储项集）
获得规定覆盖量的项集之后，就要分别将项集转换成至少拥有指定最小正确率的规则或规则集。每个项集都可以产生一条或者多条规则（归纳法），每条规则都对应了一个正确率，达到指定最小正确率的规则保留，这样所有项集产生的并且满足要求的规则就是挖掘出的关联规则。
4.6 线性模型
决策树和规则主要处理名词性属性，对于数值属性，除了可以先处理成离散的名词性属性再运用上述方法，还可以运用其他方法。
4.6.1 数值预测：线性回归
当所有属性和结论都是数值型时，线性回归是一种自然会考虑的技术。主导思想是加权线性和： ，其中 是实例的结果， 是该实例的某个属性值， 是权重。权重的确定是依据所有实例以及评价标准最小均方差。
4.6.2 线性分类：逻辑回归（Logistic回归）
用线性回归法可以方便用于含有数值属性的分类问题，技巧是对每一个类执行一个回归，使属于该类的训练实例的输出结果为1，而不属于输出0，得到该类的一个线性表达式，然后对一个未知类的测试例，计算每个线性表达式的值并选择最大的。这种方法称为多反馈线性回归。但是它存在缺陷从属关系函数产生的不是概率值，因为从属关系值有可能落在0带1的范围以外。而Logostic回归可以解决这个问题。
原始目标变量为 ，其范围为[0,1]，将 转化为 。对于后者，使用线性回归 来近似，可以得到：
线性回归中使用均方差来衡量匹配程度，这里运用模型的对数似然：
应该选择使得对数似然最大化的权值 。
可以使用类似多反馈线性回归方法将Logostic回归推广到多类问题，并且通常使用的是成对分类法。
4.6.3 使用感知器的线性分类
对于分类问题，没必要非要计算出概率值，感知器学习算法的思想是：学习超平面将属于不同类别的实例分开。只有确实存在可分超平面时，该算法才能迭代终止。感知器是神经网络的前辈。
4.6.4 使用Winnow的线性分类
对于二值分类问题，除了使用感知器，还能使用Winnow算法，算法结构很类似，当出现错分时，更新权值。不同之处在于：感知器是用加减权值方法，而Winnow是用乘预先给定的数（其倒数）更新权值。Winnow的缺陷在于权值必须为正，而平衡Winnow则解决了这个缺陷。
4.7 基于实例的学习
使用距离函数判定一个与测试例最相似的训练实例，那么该实例的结果就是测视例的结果。因此问题的中心转化为：距离函数的设定以及最近邻的寻找。当然也可以扩展为寻找k近邻节点来进行判定。
对于最近邻寻找算法，使用kD树或者更好的球树数据结构（可另外深究）。
4.8 聚类
有多种聚类算法，在此主要介绍基于距离的K-means算法（已经理解）。
由于K-means算法需要反复计算节点之间距离，可以利用一些近似法大大提高计算速度。寻找最近聚类中心可以运用寻找最近邻的方法。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！