⼤数据分析之分类算法 数据分析之决策树ID3算法 什么是分类算法? 分类算法跟之前的聚类都是让不同对象个体划分到不同的组中的。但是分类不同之处在于类别在运算之前就已经是确定的。 分类是根据训练数据集合,结合某种分类算法,⽐如这篇讲的ID3算法来⽣成最终的分类规则,这样当提供⼀个对象的时候我们可以根据它 们的特征将其划分到某个分组中。 决策树ID3算法是分类中的经典算法,决策树的每⼀层节点依照某⼀确定程度⽐较⾼的属性向下分⼦节点,每个⼦节点在根据其他确定程度 相对较⾼的属性进⾏划分,直到 ⽣成⼀个能完美分类训练样例的决策树或者满⾜某个分类终⽌条件为⽌。 术语定义: ⾃信息量:设信源X发出a的概率p(a),在收到符号a之前,收信者对a的不确定性定义为a的⾃信息量I(a)=-logp(a)。 信息熵:⾃信息量只能反映符号的不确定性,⽽信息熵⽤来度量整个信源整体的不确定性,定义为:H(X)= 求和(p(ai) I(ai)) 条件熵:设信源为X,收信者收到信息Y,⽤条件熵H(X"Y)来描述收信者收到Y后X的不确定性的估计。 平均互信息量:⽤平均互信息量来表⽰信息Y所能提供的关于X的信息量的⼤⼩。 互信息量I(X"Y)=H(X)-H(X"Y) 下边的ID3算法就是⽤到了每⼀个属性对分类的信息增益⼤⼩来决定属性所在的层次,信息增益越⼤,则越 应该先作为分类依据。 ID3算法步骤 a.对当前例⼦集合,计算属性的信息增益; b.选择信息增益最⼤的属性Ai(关于信息增益后⾯会有详细叙述) c.把在Ai处取值相同的例⼦归于同于⼦集,Ai取⼏个值就得⼏个⼦集 d.对依次对每种取值情况下的⼦集,递归调⽤建树算法,即返回a, e.若⼦集只含有单个属性,则分⽀为叶⼦节点,判断其属性值并标上相应的符号,然后返回调⽤处,或者树达到规定的深度,或者⼦集所有 元素都属于⼀个分类都结束。 举例分析 世界杯期间我和同学⼀起去吃了⼏回⼤排档,对那种边凑热闹边看球的氛围感觉很不错,但虽然每个夏天我都会凑⼏回这种热闹,但肯定并 不是所有⼈都喜欢凑这种热闹的,⽽应⽤决策树算法则能有效发现哪些⼈愿意去,哪些⼈偶尔会去,哪些⼈从不愿意去; 变量如表1所⽰,⾃变量为年龄、职业、性别;因变量为结果(吃⼤排档的频率)。 年龄A 职业B 性别C 结果 20-30 学⽣ 男 偶尔 30-40 ⼯⼈ 男 经常 40-50 教师 ⼥ 从不 20-30 ⼯⼈ ⼥ 偶尔 60-70 教师 男 从不 40-50 ⼯⼈ ⼥ 从不 30-40 教师 男 偶尔 20-30 学⽣ ⼥ 从不 20以下 学⽣ 男 偶尔 20以下 ⼯⼈ ⼥ 偶尔 20-30 ⼯⼈ 男 经常 20以下 学⽣ 男 偶尔 20-30 教师 男 偶尔 60-70 教师 ⼥ 从不 30-40 ⼯⼈ ⼥ 偶尔 60-70 ⼯⼈ 男 从不 计算过程: 1、⾸先计算结果选项出现的频率: 表2 结果频率表 从不p1 经常p2 偶尔p3 0.375 0.125 0.5 2、计算因变量的期望信息: E(结果)=-(p1*log2(p1)+p2*log2(p2)+p3*log2(p3) ) =-(0.375*log2(0.375)+0.125*log2(0.125)+0.5*log2(0.5) ) =1.406 注:这⾥Pi对应上⾯的频率 3、计算⾃变量的期望信息(以年龄A为例): E(A)= count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )) 3.1公式说明: Count(Aj):年龄A第j个选项个数; j是下⾯表3五个选项任⼀ 表3 年龄记录数量表 选项 20-30 20以下 30-40 40-50 60-70 数量 5 3 3 2 3 Count(A):年龄总记录数 p1j =count(A1j)/count(Aj) :年龄A第j个选项在结果中选择了"从不"的个数占年龄A第j个选项个数的⽐例; p2j =count(A2j)/count(Aj) :年龄A第j个选项在结果中选择了"偶尔"的个数占年龄A第j个选项个数的⽐例; p3j =count(A3j)/count(Aj) :年龄A第j个选项在结果中选择了"经常"的个数占年龄A第j个选项个数的⽐例; 3.2公式分析 在决策树中⾃变量是否显著影响因变量的判定标准由⾃变量选项的不同能否导致因变量结果的不同决定,举例来说如果⽼年⼈都从不去⼤排 档,中年⼈都经常去,⽽少年都偶尔去,那么年龄因素肯定是决定是否吃⼤排档的主要因素; 按照假设,即不同年龄段会对结果产⽣确定的影响,以表3年龄在20以下的3个⼈为例,假设他们都在结果中选择了"偶尔"选项,此时: p2j =count(A2j)/count(Aj)=1, p1j =co
2024-02-20 10:50:40 149KB 文档资料
1
如果你认为你是一名真正优秀的程序员……读Knuth的《计算机程序设计艺术》,如果你能读懂整套书的话,请给我发一份你的简历。 ―― Bill Gates 《计算机程序设计艺术》重译自Donald E. Knuth(汉名高德纳)的三卷著作:"The Art of Computer Programming: 1. Fundamental Algorithms; 2. Seminumerical Algorithms; 3. Sorting and Searching";三卷中文名为《基本算法》、《半数值算法》及《排序与查找》。本书内容博大精深,作者因为三卷书获得美国计算机协会1974年图灵奖(该奖被国际公认为计算机科学领域的最高奖项)。
2024-01-25 14:04:46 18.45MB 程序设计
1
首先分析粮食仓库选址的原则和影响因素等,研究建立了粮库选址模型;进而考虑带障碍约束条件,采用量子粒子群优化的空间聚类分析方法,解决了粮库选址问题;最后,以河南省粮库选址为实例进行了模型验证。实验表明,使用量子粒子群优化方法提高了粮库选址的科学性,为科学合理地进行粮库建设与布局提供了决策依据。
2023-12-11 22:36:49 280KB
1
π_4-CQPSK信号的频偏估计算法.pdf
2023-12-10 11:26:00 915KB
1
计算机程序设计艺术_第1卷_基本算法.pdf
2023-12-07 09:52:40 10.95MB 计算机程序设计艺术
1
在高信噪比处理域构造新的用于调制识别的高阶统计量幅值特征,与传统特征相比保留了更多的分类信息,适合干扰较大多种调制模式并存的环境。基于联合特征向量有效提高了识别性能,用窗口平滑抑制截获信号中的噪声,对识别器输入特征向量样本规范化以提高处理速度。分别基于欧氏距离分类方法和改进算法的神经网络识别器进行仿真实验,证明了采用联合特征向量和优化方法在低信噪比干扰更大的信道条件下能区分更多的调制类型(MASK、MPSK、MFSK、MQAM),且平均调制识别率提高200%,算法效率也得到明显提高。
2023-11-23 17:52:34 237KB
1
针对用BaumWelch算法训练隐马尔可夫模型用于序列比对算法的搜索空间有限性容易陷入局部最优点的缺陷,提出一种用量子粒子群优化算法训练隐马尔可夫模型的生物多序列比对新方法。该方法克服了BaumWelch算法在收敛性能上的缺陷,在整个可行解空间中进行搜索。从BaliBASE数据库中选取测试例子进行数值实验,实验结果表明,所提算法优于BaumWelch算法,对标准例子进行的实验证明了算法的有效性。
2023-11-23 17:18:25 315KB
1
为了提高语音情感识别系统的识别准确率,在传统支持向量机(SVM)方法的基础上,提出了一种基于主成分分析法(PCA)的多级SVM情感分类算法。首先将容易区分的情感分开,针对混淆度大且不能再利用多级分类策略直接进行区分的情感,采用PCA进行特征降维,然后逐级地判断出输入语音所属的情感类型。与传统基于SVM分类算法的语音情感识别相比,本方法可将七种情感的平均识别率提高5.05%,并且特征维度可降低58.3%,从而证明了所提出方法的正确性与有效性。
2023-11-05 16:01:02 891KB
1
在单芯片多核系统中,NoC已成为主流片上通信架构。有效的任务调度是挖掘计算并行性的重要方法。在经典静态列表调度基础上,针对HEFT算法中节点排序会得出较多的优先级相同节点的问题,提出一种节点二次排序的调度方法。在边的调度上应用了ALAP原则,改进算法有效提高了调度效果。实验表明,新方法对bl、blcomp、blio等节点优先权算法得出的任务列表均有良好的调度效果,适应性较好;对于2D Mesh同构NoC架构,改进算法对三种节点优先权算法有1.15倍的平均加速比,最大可有1.27倍加速比。
1
针对传统NoC容错算法中容错粒度过粗造成资源浪费的问题, 提出了一种细粒度的自适应容错路由算法, 对带有部分故障的节点重新利用。算法将各种故障映射为一种功能故障模型, 结合新提出的路由端口优先级策略和嵌入的奇偶转向模型, 实现数据包的无死锁容错路由。实验表明, 随着负载和故障数目的增加, 该算法具有更优越的容错性能, 证明了算法的有效性。
2023-10-23 22:18:41 1.29MB 片上网络(NoC) 容错 故障模型 优先级
1