最小ID算法（通用8篇）
最小ID算法 篇1
摘要：同线多跳自组网既能解决现有同线通信方式的不足, 又具有广泛的应用前景。在对同线多跳自组网进行深入研究的基础上, 针对网络同步问题提出了一种新的基于最小ID的同步算法。经仿真分析验证, 这种算法能较好地满足要求。
关键词：同线多跳自组网,时隙同步,同步算法
1 同线多跳自组网概述
针对在同一对电话线路上实行快速多用户多路分布式组网的通信需求和现有同线通信方式的不足, 笔者在现有的“同线电话”基础上, 通过借鉴当今先进的Ad Hoc网的理念与技术, 提出同线Ad Hoc网即同线多跳自组网概念, 以此来实现同线通信设备的跨越式发展。
IETF和IEEE都采用了“Ad Hoc网络”一词来描述特殊的自组织对等式的多跳移动通信网络。根据无线Ad Hoc网的概念和有线同线通信也具有“一发相邻多收”的特性, 同线Ad Hoc网或同线多跳自组网可定义为:通过在同一对电话线路上分布式跨接终端, 利用自动中继转发技术, 构成同线远距离、自组织、对等式的多跳有线通信网络。按照这一定义, 现有的同线通信方式可划为“同线单跳自组网”范畴, 这与同线多跳自组网是有本质区别的。
无论是单跳还是多跳同线自组网, 从物理形态上看, 它们基本的拓扑结构, 都可归为在同一对线路上分布式跨接数十个节点的“总线式”结构, 如图1所示。具体应用时, 同一对线路还可使用线路分支器进行线路多分支组网, 这样每个分支线路又可跨接多个节点。此时, 物理拓扑结构可等效为具有公共节点的多分支“总线式”结构。另外, 图1中的某些节点还可作为网关节点, 这样可用于与其他通信网系互联互通。同线多跳自组网通常由有线信道、节点和配套设备等3部分组成。
2 时隙同步算法
为吸取FDMA和TDMA两者的优点, 本方案采用了FD-MA与TDMA混合的多载波时分多址接入方式 (MC-TDMA) , 即在频分的基础上再采用TDMA方式, 从而有效克服了这两种接入方式的不足, 很好地适应了同线多跳自组网的需要。经综合权衡, 同线多跳自组网的多频道TDMA时频结构如图2所示。其中, 每个频道的7个时隙, T0时隙作为突发控制与分组信道, T1-T6时隙作为可3个时分双工的电路业务信道;帧周期为40ms, 即声码话20ms帧周期的两倍。
在TDMA中, 保持各节点的时隙相互同步是保证TDMA接入性能的关键。在单跳分布式网中, 通过对任何一个节点的分组接收或载波监听, 可方便地实现各节点的时隙相互同步和网中N个节点的时隙确定性安排。而在多跳分布式网中, 多跳结构使得其实现就没那么简单。虽然, 可以利用GPS或者通过互同步、准同步、有中心控制等其他方式来解决多跳情况下的时隙同步问题, 但是它们毕竟有一定的限制和不便。为此, 我们提出了一种简便实用可靠的最小ID号时隙同步方式。
通常情况下, 通过入网申请和自组织算法可使网络中每个节点分配一个不同的ID号, 且较先入网的节点可分配到较小的ID号, 如N个节点可依入网顺序分别分配ID为1、2、3、…、N。最小ID号时隙同步算法的基本思想是, 各站点均参照一个当前网络中最小ID号的节点作为同步基准节点即临时时间中心站, 采用逐跳逐级散布的方式, 通告时间标准, 以确定T0复帧的时隙位置, 进而完成全网TDMA时隙的对齐。
2.1 基于最小ID的网络同步准则
在同线网络中, 各站点均参照一个临时时间中心站, 采用逐级散布的方式, 通告时间标准, 确定T0复帧的时隙位置, 进而完成全网TDMA时隙的对齐。由于临时基准中心站在网内具有最小的ID号, 本时间同步方式可称为基于最小ID的网络同步。
网内各站点均具有相同的处理逻辑, 本同步准则可表示如下:
(1) 本准则适用于已成功入网的站点, 对于尚未入网的站点, 需首先通过入网过程获取有效的ID号后, 方可参与网络同步过程。
(2) 各站点均遵循相同的判断规则, 在自行维护的Tmin和Tmax两个周期时间间隔内, 至少发送一次网络同步消息。Tmin为站点判定网络时间尚未同步时的最小消息发送间隔;Tmax为站点判定网络时间已同步时的最大消息发送间隔, 通常需小于三分之一的最大时钟稳定度校正周期。
(3) 各站点始终保持时间标准的概念, 即T0复帧的起始位置。时间标准在借助时间源 (即临时时间中心站) 发布后, 时间标准由遵循同一标准的站点共同维护。此后, 时间源信息在消息中的传播, 仅提供了对时间标准判定的辅助信息, 在临时中心站失效后, 可由网内另一最小ID号站点接替。
(4) 各站点以大分组突发序列的方式, 在本站点的T0复帧时隙发送网络同步消息, 在它站点的T0时隙接收网络同步消息。
(5) 在消息发送时间尚未到来时, 站点在唤醒机制的触发下, 接收公共控制消息, 且仅对网络同步消息和可能的网络同步事件作出处理。
(6) 在每次站点对应的T0复帧时隙到来时, 检查Tmin或Tmax规定的随机发送时刻是否到来, 若需要发送, 则转发站点保存的时间源信息, 同时设定自身的时间级别, 重新启动Tmin或Tmax定时器;若无需发送, 则处理其他控制消息, 或继续保持沉默。
2.2 ID号的申请与释放准则
ID号是站点在网络中的临时身份标识, 在每次入网过程中动态获取, 以此ID号即可对应到站点在T0复帧时隙中的准确位置, 规避网内各站点控制信息的冲突。
网络同步消息中包含了一个32比特的位图, 用于指示当前ID号的分配情况, 由临时时间中心点负责维护。下面分别描述ID号的申请准则和ID号的释放准则。
2.2.1 ID号的申请准则
ID号的申请准则描述如下:
(1) 本准则适用于初次开机站点, 或在多网合并时, 需要加入另一时间标准网络的站点 (业务中止、状态清零) ;
(2) 站点在入网前, 必须确认网络处于稳定状态 (即网内有活跃用户, 且全网遵循相同的时间标准、拓扑状态稳定、临时时间中心站激活) , 或者网络处于初始状态 (网内没有任何活跃用户) ;
(3) 对于处于稳定状态的网络, 站点锁定住网络的时间标准和拓扑状态, 利用任一空闲ID的T0复帧时隙 (为避免申请时隙与已分配时隙中信息的冲突, 可指定最大时隙为公共接入时隙) , 使用入网请求消息, 向临时时间中心站发起ID获取申请 (通过指向中心站的最短路由转发或直达) , 中心站提取一空闲ID, 使用入网确认消息, 向临时中心站发送确认, 同时更新网络时间同步消息中的ID分配表, 启动或维持Tmin定时器。站点只有在收到确认后, 方能占用该时隙工作, 否则退避等待;
(4) 对于处于初始状态的网络, 站点直接将自身确定为临时时间中心站, 占用较低的ID号, 发送网络同步消息, 同时启动Tmin定时器, 开始接受其他站点的入网申请。随后, 若检测到多种时间标准的存在, 直接按网络合并的方式处理。
2.2.2 ID号的释放准则
ID号的释放准则描述如下:
(1) 本准则适用于已入网站点的主动释放和站点突然离开时的被动释放;
(2) 对于主动释放的站点, 站点在离开网络前, 向自身当前所属时间标准的中心站, 发送退网请求 (可选择不同路径或同一路径发送3次) , 而后自行离开。中心站接收请求后, 释放ID分配表的相应ID, 启动Tmin定时, 通过网络定时消息通告网内其他节点;
(3) 对于被动释放的站点, 中心站通过对拓扑更新消息中相关参数的判断 (3次Tmax时间内未收到该站点的拓扑更新) , 直接释放ID分配表的相应ID, 启动Tmin定时, 通过网络定时消息通告网内其他节点。
3 网络同步性能分析
对于同线多跳自组网的网络性能验证, 笔者使用OPNET来建模。典型的网络拓扑为放置32个终端节点在一条总线上, 由于固定节点的位置是不能改变的, 我们可将各终端节点的位置设为一个随机变量, 服从均匀分布, 也就是说各站随机分布在总线的任意位置上, 更符合真实的网络拓扑。只要改变随机变量的取值范围, 就可以更改总线的长度, 便于多次不同的仿真。再按此模型建立多个场景, 每个场景结构都是一致的, 不同之处在于用户数量的不同, 如24个, 12个等。另外, 设置一个配置节点, 用来进行初始化配置, 如设定节点的随机位置, 确定总线长度等。
3.1 全网时隙校正时间
为方便见, 这里我们先讨论全网已同步到一个时间标准后, 为校正各站点时钟偏移而进行的一次时隙校正的动作。
设定32个站点在30公里范围内随机均匀分布, Tmax定时器为40s (假设3次发送时, 仅有1次成功, 仍可校正120s内的时钟抖动) , Tmin定时器设置为5s。
当临时时间中心站位于网络的最边缘时, 时间基准信息的散布需要最大的跳数, 此时会经历最大的时隙校正时间, 而临时时间中心站位于网络的中央时, 时间基准可较快散布。改变仿真随机数种子 (站点分布情况的改变) , 获得的全网时隙校正时间特性如下图3所示。
如图所示, 时间校正时间在3秒以内波动, 此时, 各随机数种子对应的中心站位置分别为 (100, 9.0) , (200, 21.7) , (300, 14.0) , (400, 28.5) , (500, 7.0) , (600, 2.7) , (700, 5.0) 。可见, 当中心站在距离总线中央位置较近时, 时隙校正时间较小, 而中心站靠近两端时, 时隙校正时间则更长。与分析结果基本相同。
3.2 初始全网时隙同步时间
这里我们讨论全网开设时的各站点时隙同步时间。该时间与站点开机的顺序和同线的距离密切相关, 当距离过远且站点同时开机时, 将出现多个时间中心的竞争。
仿真预置条件为, 设定32个站点在30KM范围内随机均匀分布, Tmax定时器为40s, Tmin定时器为5s, 设定32个站点同时开机。
改变仿真随机数种子 (站点分布情况的改变) , 获得的初始全网时隙同步时间特性如下图4所示。
图中数据表明, 初始全网时隙同步时间在60～90s之间, 远大于30KM内的时标转发时间, 其原因是各站点开机后, 必须首先侦听30s的时间, 以及中心站的竞争时间, 在中心站确认后, 各站点在向其获取动态ID号时, 全网时隙已同步, 但必须在获取有效的ID号后, 网络方能确认时间同步完成。
3.3 两网控制时隙对齐时的同步时间
仿真预置条件为:设定32个站点在30KM范围内随机分布, 在线路中央 (15KM) 处完成线路对接, 原有两个子网内各有一个活跃的时间中心站, 且网络处于稳定状态, Tmax定时器为40s, Tmin定时器为5s。
改变仿真随机数种子 (站点分布情况的改变) , 获得的初始全网时隙同步时间特性如下图5所示。
图中数据表明, 全网时隙同步时间在15～45s之间, 两网能够较快实现合并。影响这个时间的原因主要有二:
一是, 两网内的站点数量大小。若较少的站点向另一网络入网, 则可快速达到同步, 若需要入网的站点数量多, 显然达到同步的时间将要增长。
二是, 两网的时间基准错开多少。若两网时间基准基本一致, 那么控制消息的冲突将影响感知另一网络的速度, 导致入网时间消耗;而时间基准完全错开时, 由于网络同步消息在非T0时隙出现, 使得网络中各站点均能够快速感知到两个时间标准的存在, 加快了网络同步信息的发送频度, 则达到全网时隙同步的时间更快。
4 结束语
同线多跳自组网, 是针对当前同线通信系统存在的问题, 通过借鉴当今先进的无线多跳自组网理念与技术而创新提出的新概念网络, 本文对同线多跳自组网进行了深入的研究, 提出了网络同步的一种算法, 并进行了分析与仿真, 初步判断能够较好地满足系统的要求。
参考文献
[1]郑少仁.Ad Hoc网络技术[M].北京:人民邮电出版社, 2005.
[2]钟晓峰.基于时分系统的无线自组织网络同步算法[J].清华大学学报, 2005 (1) .
最小ID算法 篇2
(青海师范大学数学系，青海 810000)
摘要：本文讲述了几种求解最小生成树的算法(Kruskal算法、Prim算法、破圈法和DNA算法)，重点介绍了一种求解最小生成树问题的DNA 算法，进而比较这几种算法的优缺点以及介绍最小生成树的几个实际应用。
关键字：最小生成树 Kruskal算法 Prim算法 破圈法 DNA 算法
Several algorithm of solving minimum spanning tree and its application Xiangnan-kong
(Mathematics Department of Qinghai Normal University, Qinghai 810000) Abstract: This paper describes several algorithm of solving minimum spanning tree(Kruskal algorithm、Prim algorithm、Broken circle method and DNA algorithm), and focuses on discussing the DNA algorithm. Then it compares the advantages and disadvantages of several algorithms and introduces several practical applications of the minimum spanning tree . Keyword: Minimum spanning tree;Kruskal algorithm;Prim algorithm; Broken circle method ;DNA algorithm.
1 引言
最小生成树是网络最优化中一个重要的图论问题，它在交通网、电力网、电话网、管道网等设计中均有广泛的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。
求图的最小生成树有两种常见的算法，一种是Kruskal(克鲁斯卡尔)算法，另一种是Prim(普里姆)算法。这两个算法的基本思想均是基于避圈法，而从相反的角度，破圈法也可构造最小生成树算法。
本文讲述Kruskal算法、Prim算法和破圈法的同时，也着重介绍了一种求解最小生成树问题的DNA 算法。
2 有关最小生成树的理论基础
2.1 有关最小生成树的概念
2.1.1 定义一(图)
一个图G定义为一个偶对(V,E),记作G=(V,E)，其中
(1)
(2) V是一个集合，其中的元素称为顶点; E是无序积VDV中的一个子集合，其元素称为边;
2.1.2 定义二(树)：不含圈的连通图称为树。
2.1.3 定义三(生成树)：如果T是G的一个生成子图而且又是一棵树，则称T是图G的一棵生成树。
2.1.4 定义四(最小树)：设T?是赋权图G的一颗生成树，若对G的任意生成树T都有l T?
2.2 有关最小生成树的定理
2.2.1 定理一(最小树充要条件)
设T是G的一棵生成树，则下列条件都是T为最小树的充要条件
(1) 对任意连枝e′∈GT,有l (e′)=maxe∈CT(e′){(l(e))}
(2) 对图G中任意圈C,存在e′∈CT，有l (e′)=maxe∈C{l(e)}
(3)对任意树枝e∈T,有l (e)=mine∈ST(e){(l(e′))}
(4)对G的任意割集S，在T∩S中存在一条边e，l(e)=mine′∈S
2.2.2 定理二(唯一最小树充要条件)
设T?是G的一棵生成树，则下列条件都是T?是G的唯一最小树的充要条件是下列两个条件中的任一个成立：
(1)对任意e∈GT?，e是CT?(e)的唯一权最大的边。
(2)对任意e?∈T?，e?是ST?(e?)的唯一权最小的边。
3 Kruskal(克鲁斯卡尔)算法
3.1 Kruskal算法介绍
Kruskal算法是1956年首次提出的求最小生成树的算法。后来Edmonds把这个算法称为贪心算法。其基本思路是从G的m条边中选取n-1条权尽量小的边，并且使得不构成回路，从而构成一个最小树。下面我们就来叙述这个算法.
第1步 开始把图的边按权的大小由小到大地排列起来，即将图的边排序为a1,a2,…,am,使W a1 ≤W a2 ≤?≤W am 置S=?，i=0,j=1.
第2步 若|S|= i=n?1,则停止。这时G [S]=T即为所求;否则，转向第3步。
第3步 若G [S? aj ]不构成回路，则置e i+1=aj,S=S?{e i+1}, i?i+1,j：=j+1,转向第2步;否则，置j：=j+1，转向第2步。
MST-KRUSKAL(G,w)
T(e){l(e′)}
1 A→?
2 for each vertex ?∈V G
3 do Make-Set(v)
4 sort the edge of E into nondecreasing order by weight w
5 for each edge μ,? ∈E,taken in nondecreasing order by weight 6 do if Find-Set(u)≠Find-Set(v)
7 then A←A∪ u,v
8 Union(u,v)
9 retuen A
3.2 Kruskal算法的复杂性
首先在第1步中把边按权的大小由小到大地排列起来，这约需mqlog2m次比较;其次第2步最多循环n次;在第3步中判断G [S? aj ]是否构成回路，判定加边后是否构成回路总共约需m次比较，而加边后点的重新标号最多需n(n-1)次比较。所以总的计算量为mqlog2m+n+m+ n(n-1)~O n2log2n 由定理一(1)易见上述算法的正确性。
3.3 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图2所示
图1
图2
4 Prim(普里姆)算法
4.1 Prim算法介绍
Prim算法的基本思想：首先，选择带权最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止。下面我们来介绍这个算法：
设G是n+1个顶点的连通的赋权图。
第1步 取T0为n+1个顶点的空图，T0有n+1个分支(即孤立点)，没有圈。
i，则E(Vi× V i)是一个断第2步 把Ti的n+1-i个分支分成两个子集Vi和V
集。
i)中权最小的边，令T i+1=T i+e i+1,显然，第3步 取e i+1为断集E(Vi× V
T i+1没有圈且分支数为 n+1 ? i+1 =n?i.
第4步 当i=n?1时算法停止，Tn中已有n条边，构成G的一棵生成树，当i≠n?1时，令e′= i+1返回第2步。
MST-PRIM(G,w,r)
1 for each u∈V G
2 do key[u] ←∞
3 π[μ]←NIL
4 key[r] ←0
5 Q ←V G
6 while Q≠?
7 do u ←Extract?Min Q
8 for each v∈Adj u
9 do if v∈Q and w(u,v)< key[v]
10 then π v ←u
11 key[v] ←w(u,v)
4.2 Prim算法的复杂性
下面简单分析一下Prim算法的复杂性。第一次执行第2步是n-2次比较，第二次为n-3次比较，第三次是n-4比较，?，因此总的比较为2 n?2 (n?
1)次。在执行第3步时，第一次是n-2次比较，第二次n-3次比较，?，因此总的比较为(n-2)(n-1)次。由此算法的总计算量约为O n2 .
1
4.3 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图3所示
图3
5 破圈法
5.1 破圈法介绍
该算法的理论依据是存在性定理：连通图至少有一棵生成树。如果我们给的连通图G 中没有回路，那么G 本身就是一棵生成树，若G 中只有一个回路，则删去G 的回路上的一条边(不删除结点)，则产生的图仍是连通的，且没有回路，则得到的子图就是图G 的一棵生成树，若G 的回路不止一个，只要删去每一个回路上的一条边，直到G 的子图是连通没有回路且与图G 有一样的结点集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样(即删去的边不一样)所以可得到不同的生成树，但是在求最小生成树的时候，为了保证求得的生成树的树权W(T)最小，那么在删去回路上的边的时候，总是在保证图仍连通的前提下删去权值较大的边。尽量保留权值较小的边。这就是所谓的破圈法。破圈法就是在带权图的回路中找出权值最大的边，将该边去掉，重复这个过程，直到图连通且没有圈为止，保留下来的边组成的图即为最小生成树。破圈法的`复杂程度为O n3 .
5.2 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图4所示
最小ID算法 篇3
虽然ID3决策树算法已经得到了广泛应用, 但是该算法还存在一些缺陷和可以改进的方面。通过对ID3决策树算法建立决策树的过程中所存在的多值偏向问题的分析和探索, 提出了一种基于信息增益和样本结构相似度共同作用的属性判断指标, 通过改进指标来修正多值偏向给ID3决策树算法的准确性带来的影响。其实现过程对于在继续改进和丰富ID3决策树算法的判断指标和提高决策的准确性具有一定的现实价值和参考价值。
1 ID3决策树算法的不足
ID3决策树算法选用当前层次信息增益最大的属性来作为节点进行分支判断, 而每次信息增益的计算很大程度上会受到多值偏向性问题的影响, 即取值较多的属性有优先选取的倾向。这就难以判断得到的测试属性究竟是因为本身比较重要还是由于属性取值较多的缘故而被算法作为节点属性而选择的。
如果数据集中的不同属性间关系较为复杂, 属性间联系的强弱关系又没有明确的判断方法时, 信息增益的计算将很大程度上受到样本数据集中取值较多的属性的影响, 从而无法确实的反映客观的分类情况。由此可以得知, 在属性的关系复杂且重要度不确定的情况下构建的ID3决策树存在忽视重要的非多值属性的趋势。为提高分类预测的准确性, 针对ID3 决策树算法引入样本结构相似度模型对原算法的多值偏向性问题进行改进。
2 SS_ID3决策树算法简介
在样本数据集和实际数据集中一般情况下都存在一个共同的分类属性, 该属性具有若干个不同的属性值, 所有的数据元组都将指向这个分类属性中的各个属性值。从样本数据集中列的角度来看, 由于数据元组各个属性中属性值的随机性使得这些数据结构具有很大的不同, 从而使得每个属性列在表面上看起来往往是杂乱无章的。通过经验判断可以看出其中有一部分属性间没有很明确的联系, 但还是有一些属性间确实具有很明显或者很直接的关联关系。因为ID3决策树算法只是通过划分前后信息量之间的差值大小 (即信息增益) 为分类依据, 并没有考虑到描述属性和分类属性间的联系关系, 所以, 提出了一种改进的ID3决策树算法——SS_ID3决策树算法。
SS_ID3算法将描述属性和分类属性间的关联关系引入到了属性选择的步骤中与信息增益联合使用, 这样的处理能够帮助一些与分类属性在结构上相似或联系比较紧密的属性能够在描述属性选择的过程中得到更多的砝码, 从而能够在一定程度上减少或克服一些联系较紧密的描述属性由于属性值偏少而造成信息熵的减少不足导致的在选择中被忽略的问题, 同时还兼顾信息增益较大的属性, 使得这些属性不被样本结构相似度所掩盖。引入的样本结构相似度模型是一个用来度量样本数据集中的描述属性的属性值与分类属性的属性值之间的空间结构重叠性的数值指标, 样本结构相似度越大说明该描述属性的分类样本数在物理上越趋近于分类属性, 反之则越不同。计算主要用到的数值包括: (1) 总的样本数据元组数; (2) 分类属性的属性值; (3) 描述属性的每个属性值; (4) 结构相似矩阵。通过相应的计算得到的数值作为一个加权因子参与到描述属性的选择过程中来完成对ID3决策树算法的改进。
3 属性结构相似矩阵
计算样本结构相似度需要在样本数据集上建立一个数据模型——结构相似矩阵, 用来描述某个描述属性与分类属性间的分布情况, 即每个描述属性的属性值分别在所有分类属性值下出现的次数, 并获取其中重叠次数最多的数值。结构相似矩阵模型将为每个描述属性建立一个矩阵用来提供相应的计算样本结构相似度的参数, 并刻画了属性值在样本数据集中的结构分布情况。
3.1 结构相似矩阵的描述
在分类属性的取值空间R=[r1, r2, …, ry]上不同元组的属性值都有其各自不同的位置和数量, 可以根据属性值的位置得出一个向量V=[v1, v2, v3, …, vn], 其中v1至vn为样本数据集的所有元组所对应的分类属性的所有取值。同样每个描述属性都有一个向量与V对应。将每个描述属性向量分别与分类属性的向量合并成一个二维向量, 通过对这个二维向量进行处理就可以得到每个描述属性相对于分类属性的结构相似矩阵。
3.2 结构相似矩阵的数学定义
设存在一个训练样本数据集S, S中包括s个数据元组;存在数据项B为训练样本集S的一个描述属性, 属性B的取值空间为B={B1, B2, …, Bn}, 属性A在样本数据集中的结构为
undefined
;存在数据项C训练样本集S的分类属性, 具有m个不同值, 用来定义m个不同的类, 属性C的取值空间为C={C1, C2, …, Cm}, 对C按照样本数的多少从大到小进行排序得到整理后新的C′={C′1, C′2, …, C′m}。属性C′在样本数据集中的结构为
undefined
。由该描述属性和分类属性的值所构成的数据结构为:
undefined
。以描述属性B的取值为行, 分类属性C的取值为列, 可以通过UV得到一个n行m列的矩阵A, 按照Bj的顺序定位矩阵A的行顺序, 按照C′i的顺序定位矩阵A的列顺序, 并记矩阵A中的aij为UV中v的取值为C′i时且u的取值为Bj时数据元组的样本数量, 直到将UV中的所有数据自上而下进行遍历, 统计样本数后就得到了描述属性B相对于分类属性C的结构相似矩阵A。
undefined
4 样本结构相似度
通过对该矩阵中的数值进行提取和计算就可以得到该描述属性相对于分类属性的样本结构相似度。简单地来说样本结构相似度是一种通过计算得到的用以判断在样本数据集中指定描述属性的结构相似情况与分类属性的数据分布在不复用数据的情况下相吻合的程度。可见样本结构相似度是一种运用单个描述属性的结构相似矩阵通过计算得到该描述属性与分类属性在结构上的相似度的方法。
4.1 样本结构相似度的计算公式
样本结构相似度的数学定义如下:设存在样本数据集S, S中包含样本数据元组个数为s, 其中包含描述属性B其取值空间为B=[B1, B2 , …, Bn]和分类属性C其取值空间为C=[C1, C2 , …, Cm], B的取值个数为n, C的取值个数为m, 可以得到一个行数为n和列数为m的矩阵DT, 其中的矩阵元素为a[x], [y], 根据如下计算公式可以得到该描述属性相对于分类属性的样本结构相似度Fb (DT) 。
undefined[Max (a[], [j]) ]}, k=[1, 2, …, n]
其中公式Maxk (a[], [j]) 为获得结构相似矩阵DT的第j列的最大值, 而Adrx[Max (a[], [j]) ]是用来得到第j列的最大值所在的行数, k为记录结构相似矩阵DT各个行号得到的数据集, k=k-Adrx[Max (a[], [j]) ]就是将已取得当前列最大值的一行从之后的计算中剔除掉以保证该数据不被复用从而去除二义性和不确定性。
4.2 样本结构相似度的应用
由于样本结构相似度是一种用来修正信息增益在选择属性时产生的多值偏向问题的权值, 所以在ID3决策树算法的运作过程中需要将其加入到节点选择和判断的标准中, 即将样本结构相似度和信息增益相结合以得到进行了结构相似修正后的新的判断数值, 然后再对新数值进行比较来选择用来划分数据集的当前属性。使用相同的样本数据, 见表1, 分别进行ID3决策树和SS_ID3决策树的构建, 通过构建出来的决策属来进行比较。
由于根节点、各内部节点和叶节点的选择参数发生了变化后, SS_ID3算法和ID3算法所构建的决策树存在着明显的不同, 如图1所示。改进后的规则描述由原有的5条增加为8条, 这样就能够对数据的分类更加细致, 有助于提高决策树分类的准确性。
5 结论
通过决策树结构来看, SS_ID3决策树算法对取值数较多的属性并不敏感。SS_ID3算法使得决策树的结构更加平衡, 判断路径更加丰富, 对数据的分类更加细致, 有助于提高决策树分类的准确性。通过比较可以得到一些SS_ID3决策树算法的优点:一是在一定程度上解决了仅使用信息增益作为判断标准而造成的多值偏向问题。二是决策树的结构更加均衡。三是提高了结构相似度较高但取值不多的属性的权重, 使得决策树分类更加科学。四是对数据集的分类会更加细致, 有助于提高分类的准确率。
参考文献
[1]Joong-Hee Lee, Jong-Hyouk Lee, Seon-Gyoung Sohn, et al.Effective Value of Decision Tree with KDD 99 Intru-sion Detection Datasets for Intrusion Detection System[J].2008 (2) :17-20.
[2]Dunham M.Data Mining:Introductory and AdvancedTop ics[M].Upper Saddle River, NJ:Pearson Educa-tion, 2003.
[3]陆秋, 程小辉.基于属性相似度的决策树算法[J].计算机工程, 2009 (3) .
[4]鲁为, 王枞.决策树算法的优化与比较[J].计算机工程, 2007.
[5]房祥飞, 刘希玉.决策树在数据挖掘中的新进展和发展前景[J].信息技术与信息化.
[6]梁循.数据挖掘算法与应用[M].北京:北京大学出版社.
[7]段玉春, 晓艳, 孙玉强.一种改进的ID3决策树算法[J].南阳师范学院学报, 2006 (5) .
[8]唐松华, 姚耀文.数据挖掘中决策树算法的探讨[J].计算机应用研究, 2002 (8)
决策树分类算法-ID3的改进 篇4
近年来, 数据分类技术已被广泛、有效地应用于科学实验、案件侦破等领域, 引起了工业界和学术界的普遍关注。其中基于决策树的分类模型方法由于结构简单、效率高等优点被人们广泛使用。决策树方法起源于概念学习系统, 国际上最早最有影响的决策树方法是Quinlan提出的ID3算法, 在该算法中, 引入了熵的概念, 利用分割前后的熵来计算信息增益。在树的生长过程中, 在每次对记录集分割时均选择信息增益最大的属性进行分叉, 直到一个节点的记录的类别相同或者结点的记录数目小于给定的值没有属性供选择使用为止, 最后生成一棵树。
2 ID3算法
设训练实例集为X, 将其分为n类, 记为C={X1, X2……Xn}, 设第i类训练实例的个数是XÁ实例集X中的训练实例个数为。若记一个实例属于第i类的概率为P (Xi) , 则有:
此时决策树对划分C的不确定程度为H (X, C) , 可简记为H (X) ,
选择测试属性A进行测试, 设A具有性质a1, a2…, an, 在A=ai的情况下, 第i类的实例个数为|Xij|, A=aj的实例个数为|Xj|, 则有:
设Yj为A=aj时的实例集, 此时决策树对分类的不确定程度就是训练实例集对属性A的条件熵,
当选择测试属性A后, 分出每个A=aj时节点Xj对分类信息的信息熵为
属性A对于分类提供的信息量, 即属性的信息增益A为I (A)
显然, 式 (5) 的值越小则式 (6) 的值越大, 说明选择测试属性对于分类提供的信息越大, 选择之后对分类的不确定程度越小, ID3算法即采取I (A) 作为测试属性的选取标准, 分割训练实例集最终生成一棵决策树。
3 算法改进
传统的ID3算法偏向于选择取值较多但实际中并不总是最优的属性作为测试属性, 针对它的这一缺点, 本文引入用户兴趣度:给定0≤s≤1, s称为用户对不确定知识的兴趣度, 通常指关于某一事务的先验知识, 具体到决策树学习中则是指在决策树训练过程中, 除了用于生成和修改决策树的实例集之外, 还包括所有影响决策树规则生成和选择的因素。
改进的ID3算法是针对规则生成方法即属性选择标准算法进行了改进。通过对式 (5) 中加权和增加用户兴趣度, 加强了属性的标注, 降低非重要属性的标注, 最终使决策树减少了对取值较多的属性的依赖性。
利用用户兴趣度把 (5) 修改为:
相应式 (6) 变为:
改进ID3算法就是把式 (7) 和式 (8) 作为测试属性的选择标准来构造决策树。
4 算法举例
表1给出了影响夏天天气舒适度的几个相关指标的数据集合, 下面以该样本数据集为训练集, 分别采用ID3算法及其改进算法构造决策树, 对数据进行分类。
用ID3算法对样本训练集进行分类, 可得决策树, 如图1所示。
根据图1可以得到分类规则, 见表2。
由表2可以看到, 穿衣指数能在一定程度上反映天气的舒适程度, 但并不能成为决定天气舒适与否的客观条件。下面, 用改进算法对表1的样本数据集重新生成决策树, 通过测试指定穿衣指数属性的用户兴趣度s=0.3, 其它属性的用户兴趣度为0。
由表1可知, 初始时刻正例类实例个数为9, 反例类实例个数为11, 所以开始时熵值为:
选择穿衣指数作为测试属性, 该属性的信息熵为
类似可得H (X|温度) =0.9661;H (X|湿度) =0.9328;F (X|风力) =0.9880。比较可知:H (X|湿度)
由图2可得到新的分类规则, 用表3表示。
比较以上两种决策树算法的规则提取, 可以发现改进算法与ID3算法所生成的决策树有很大区别, 得到的分类规则也有较大不同。改进算法降低了穿衣指数对天气舒适影响的重要性, 相应地提高了湿度、温度、风力属性在分类中的重要性, 这显然与实际情况较相符, 达到了预期目的。
结束语
ID3是决策树生成算法中最早最经典的算法, 本文具体分析了ID3算法中存在的问题, 并对其进行了改进。从而提高了建立决策树的速度, 通过对实际例子的应用, 实验证明改进后算法是有效的。
参考文献
[1]史忠植.高级人工智能[M].北京:科学出版社, 2006.[1]史忠植.高级人工智能[M].北京:科学出版社, 2006.
[2]朱明.数据挖掘[M].合肥:中国科学技术大学出版社, 2002.[2]朱明.数据挖掘[M].合肥:中国科学技术大学出版社, 2002.
[3]郭景峰, 米浦波, 刘国华.决策树算法的并行性研究[J].计算机工程, 2002, 28 (8) .[3]郭景峰, 米浦波, 刘国华.决策树算法的并行性研究[J].计算机工程, 2002, 28 (8) .
[4]刘小虎, 李生.决策树的优化算法[J].软件学报, 1989, 9 (10) .[4]刘小虎, 李生.决策树的优化算法[J].软件学报, 1989, 9 (10) .
[5]杨明, 张载鸿.决策树学习算法ID3的研究.[J].微机发展, 2002 (5) .[5]杨明, 张载鸿.决策树学习算法ID3的研究.[J].微机发展, 2002 (5) .
最小ID算法 篇5
随着物联网的蓬勃发展,RFID技术在很多行业被广泛地应用[1,2,3]。RFID技术利用无线射频方式在阅读器和应答器(标签)之间进行非接触双向数据传输来达到目标识别与数据交换的目的[4,5,6,7]。然而,阅读器和应答器之间的无线通信信道是共享的,当多个标签同时响应一个阅读器时,造成阅读器不能识别标签,产生标签碰撞。“防碰撞算法”就是解决碰撞的一种有效算法[8]。
现有的防碰撞算法主要分为概率性防碰撞算法和确定性防碰撞算法。概率性防碰撞算法有“ALOHA算法”,湖南大学尹君、何怡刚等在ALOHA算法的基础上,提出一种基于分组动态帧时隙的防碰撞算法,将时隙利用率提高80%以上[9]。确定性防碰撞算法有“二进制树搜索算法”、“IPA算法”(Identification Prediction Algorithm)等,东华大学樊文静、张姗姗等提出一种基于后退式二进制搜索算法的改进算法IRBS[10]。西南交通大学李世煜、冯全源提出了分层深度搜索树型RFID 防碰撞算法[11]。然而,当标签数量庞大时,概率性算法吞吐率低,算法性能急剧下降;确定性算法虽然可以保证标签全部被识别,但花费时间较长。
本文在跳跃式动态树形防碰撞算法(JDS)的基础上,提出一种基于减少ID冗余位和动态传输数据思想的RIPA算法(精简IPA算法),通过大量的仿真实验,从阅读器问询和标签应答过程进行比较与分析,证明RIPA算法取得更优的性能。
1 相关原理
1.1 JDS算法
JDS[6]算法的搜索过程是当标签发生碰撞时,阅读器采取向前搜索策略,直至遇到一个可以识别的标签为止;同时再采取后退方式,返回上一碰撞节点,继续搜索直至识别完阅读器工作区域的所有标签。主要步骤如下:(1) 阅读器发送Request(Null,N)命令(N为标签ID长度),要求区域内所有标签应答;(2) 检测有无碰撞发生,若有把最高碰撞位置0,高于该位的数值不变,可得IDN-1-x的值(x为碰撞最高位的下标),由此得到下一次查询命令所需的参数;(3) 若无碰撞,则识别单个标签,处理完后回跳到父节点,得到下一次查询命令所需的参数;(4) 重复进行请求与检测过程,直到执行Request(Null,N)命令无碰撞发生时结束。JDS算法充分利用了返回式搜索和动态二进制搜索的优点,采用向前向后搜索,提高了系统性能。
1.2 IPA算法
IPA算法[12,13]引入了Ncb、Nc、N1和Nr四个量并结合查询树QT(Query-Tree)算法实现对RFID标签的识别。其本质是利用标签ID中“1”的个数来预测标签ID。该算法将标签ID分为计数域和位域,计数域为位域中“1”的个数,如图1所示。阅读器向标签发送的REQUESET命令中以计数域为前缀,接收到命令的标签与自身的计数域比较,若相同则回应。
在IPA算法中,阅读器要存储的信息有计数域Ncb(即标签“1”比特的个数),碰撞比特数Nc,被识别的“1”比特的个数N1,未被识别的“1”比特的个数Nr。容易知道,未识别的“1”个数Nr=Ncb-N1,阅读器分析Nr的值来判断标签能否被识别,有以下几种情况:
(1) Nr=0:标签ID中所有比特均被识别,数据没有碰撞。这种情况下Ncb、Nc、N1、Nr的值无需计算,标签可以直接被识别。
(2) Nr =1:标签ID中未识别的“1”比特数为1,根据标签的唯一性,每个标签ID的碰撞位Nc中必然有且只有一个“1”,而其余位均为“0”。可能的情况有Nc个,因此阅读器可以同时识别Nc个标签。
(3) Nr=Nc-1: 标签ID中未识别的“0”比特数为1,每个标签ID的碰撞位Nc中必然有且只有一个“0”,而其余位均为“1”。可能的情况有Nc个,因此阅读器可识别Nc个标签。
(4) 当Nr不满足以上三种情况, 说明阅读器仍然没有足够的信息可以识别标签, 采取QT算法进行识别。
2 RIPA算法
2.1 RIPA算法思想
(1) 当只有一个标签进行应答的情况下,即无碰撞发生,可以直接识别标签,无需计算Ncb、Nc、N1和Nr四个值。
(2) 采用JDS算法取代QT算法,在搜索标签的过程中,不仅可以避免重复的搜索路径,而且采用动态传输阅读器与标签之间数据的方法降低通信量。
(3) 阅读器和电子标签之间每次发送的都是整个序列号的信息,含有大量冗余信息,精简IPA算法通过减少寻呼中信息冗余位,从而降低传输时延和能耗。
2.2 RIPA算法相关指令
为了实际实现该算法,需要一组能由电子标签处理的指令。
锁定指令—REQUEST(UID,m):UID代表阅读器在第一次寻呼之后,根据译码结果所得到的下一次寻呼的序列号。UID的取值约定为:阅读器在判断出数据发生碰撞的准确比特位置之后,把碰撞位置“1”,未碰撞位置“0”,并将未碰撞位中“1”的个数计入到标记位中,组成新的锁定寻呼指令的序列号。阅读器在发送这个寻呼指令之后,电子标签的响应为:自己ID中的数据位与接收到阅读器发出的序列号进行比较,将阅读器发出的UID位中值为“1”所对应的比特位进行锁定,并把自己的计数位与序列号的计数位相减,得到新的计数位值,在之后的防碰撞处理中,参与数据发送和比较的仅仅是这几个被锁定的比特位及其计数位。
激活指令—ACTIVE:处于准备状态的标签接收到此指令后,比较自己新的计数位是否与count-bits相等,如果是则响应,否则继续处于准备状态。本文采用REQUEST(count-bits)来实现ACTIVE指令的功能。
被选择(序列号)指令—SELECT(UID):具有相同序列号的标签将以此作为执行读写命令的切入开关,即选择这个标签。具有其他序列号的电子标签只对REQUEST命令应答。
读写数据指令—READ-DATA:选中的标签将数据发送给阅读器,与阅读器进行读写通信。
进入静默状态指令—UNSELECT:取消一个事先选中的标签,标签进入无声状态,不应答REQUEST命令。
2.3 RIPA算法工作流程
RIPA精简IPA算法的防碰撞处理流程如图2所示。
以标签的ID长度为8位,阅读器作用范围内有5个标签为例,如表1所示。
具体流程如下:
(1) 对区域内5个标签发送指令REQUEST(11111111),所有ID值小于或等于(11111111)的标签对此命令作出应答, 所有应答标签将自己的ID 码反馈回去。
(2) 阅读器检测收到的信号,若没有信号,表示阅读器周围没有标签,转到步骤(1),否则转到步骤(3)。
(3) 阅读器对所有电子标签作出的应答信号进行译码,根据译码结果判断是否有碰撞发生,5个标签出现碰撞,可解码为XXX10XX1,转到步骤(4)。
(4) 阅读器根据步骤(3)中的译码结果判断碰撞发生的比特位,将其置“1”,未发生碰撞的比特位置“0”,并将未发生碰撞的比特位中“1”的个数记录,可得下次指令为(11100110,010)。阅读器发送REQUEST(11100110,010)指令,5个标签分别将自己ID的D1 、D2 、D5 、D6 、D7 三位锁定,并将各自的计数位减去010,即标签的新ID为011 10101、010 10010、011 01011、010 11000、000 00000。
(5) 阅读器发送REQUEST(0),则计数位与0相等的标签对此命令作出应答,标签5响应,无碰撞发生,无需进行Ncb、Nc、N1和Nr四个值的计算,可直接识别标签。再发送UNSELECT命令,使标签进入无声状态,不再响应阅读器发出的指令。
(6) 阅读器发送指令REQUEST(1),无标签应答。
(7) 阅读器发送指令REQUEST(2),标签2和标签4响应,阅读器检测到碰撞为“1X0X0”,此时统计Ncb=2、Nc=2、N1=1、Nr=1,所以可以直接识别出两个标签(标签2:10010,标签4:11000),进一步处理后,使标签进入无声状态,不再响应阅读器发出的指令。
(8) 阅读器发送指令REQUEST(3),标签1和标签3响应,阅读器检测到碰撞为“XXXX1”,统计Ncb=3、Nc=4、N1=1、Nr=2,此时阅读器没有足够的信息识别标签。于是采用JDS算法,阅读器根据碰撞数据,知道最高位为D5,将最高位置0,发送指令REQUEST(0,5)。收到指令REQUEST(0,5)后,标签3响应,无碰撞发生,识别标签3。
(9) 因为采用了JDS算法,阅读采用回跳策略,发送REQUEST(1,5)指令,标签1响应,无碰撞,识别标签1,发送UNSELECT命令,使标签进入无声状态,不再响应阅读器发出的指令。
(10) 所有电子标签均被识别,精简IPA算法识别过程结束。
2.4 RIPA算法特点分析
本文所提出的RIPA算法主要有以下几个特点:
(1) 精简ID。阅读器在发送命令后,对所有标签作出的应答信号进行译码,根据译码结果判断是否有碰撞发生。若有碰撞发生,阅读器将这几个碰撞的比特位置“1”,未发生碰撞的比特位置“0”,并将未发生碰撞的比特位中“1”的个数记录为m。接着阅读器发送REQUEST(UID,m)指令,标签在接到此命令之后将UID与自己的ID进行比较,将发生碰撞的比特位锁定,计数位记录减去m值的数值。在标签识别之前,将所有标签不相同的信息进行锁定,后期的识别过程只针对这些发生碰撞的信息进行,大大减少通信冗余,达到精简ID的目的。
(2) 压缩统计处理过程。阅读器发送REQUEST(count-bits),则计数位与count-bits值相等的标签对此命令作出应答,将自己锁定位发送给阅读器,阅读器判断是否有碰撞发生。如果没有碰撞发生,则直接获得该标签的ID号,无需对标签ID的Ncb、Nc、N1、Nr进行统计处理。当阅读器范围内只有一个标签应答时,传统IPA算法会先对标签进行计算处理后在识别标签,降低了阅读速率。
(3) 跳跃式动态树搜索。阅读器在通过统计计算后,仍然无法识别标签时,采用跳跃式动态树搜索,即将碰撞发生的最高位X置“0”,高于该位的值不变,低于该位的值舍去,直至顺利读取某个标签为止。处理完后采取回跳策略,返回到上一次发生碰撞的节点,识别此节点的另外一个分枝,这样不断重复操作,直到将标签全部识别。跳跃式动态树搜索避免了路径的重复,提高了识别速率。
3 RIPA算法仿真及分析
随机选取8位标签ID,对JDS、IPA和RIPA三种算法进行仿真,其中,RIPA为本文提出的精简IPA(Reduced_IPA,简称RIPA)。按照每个算法流程编写C程序,以选择随机或者有序的标签ID,仿真标签的识别过程。分别统计了阅读器问询和标签应答的总次数和总比特数,结果如图3、图4、图5和图6所示。
精简IPA算法在阅读器问询过程和标签应答过程中都明显优于JDS算法和IPA算法,随着标签数量的增多,精简IPA算法优势越加明显,如表2和表3所示。
可见,随着标签数量的增多,JDS算法阅读器问询和标签应答的总次数和总比特数呈直线上升,因为JDS算法只是对冗余的传输数据进行处理,减少了数据传输量,而识别过程没有任何的优化。IPA算法虽然大大降低了阅读器问询的总次数和总比特数,但却大大增加了标签应答的总比特数,这是由于IPA算法在一次问询的过程中,可能同时识别多个标签,从而大大减少了阅读器问询量,这是其优势所在;但IPA算法额外增加了计数位,这些比特位不属于标签的实际信息,在标签应答时,都全部返回阅读器,造成大量的信息传输。而且随着标签ID长度的增加,这种无用的信息传输量也将增大。
为了进一步验证RIPA算法的性能,我们又进行了随机和有序的16位的标签ID的识别仿真实验。
如图7、图8、图9和图10所示为仿真实验结果,RIPA算法识别有序标签ID的性能远高于识别随机标签的性能。这是由于有序标签中非碰撞位较多,将非碰撞位省去,可以减少大量冗余,并加快了识别速率。这个特点非常适用于大量识别同类物品的场合。如在仓储过程中,可以给不同商品添加商品代码,在识别同类商品的过程中,不但不影响阅读速率,还可以迅速发觉是否有非同类商品混杂的问题。
4 结 语
针对传统的标签数量庞大场合下存在的碰撞问题,本文首先研究了IPA算法的编码方式和基本原理,在分析IPA算法不足的基础上,引入了JDS算法,提出了RIPA算法。并通过实验证明了本算法相较于其他算法在阅读器问询次数、比特数和标签应答次数、比特数等方面具有较高的优越性,较大幅度改进了RFID标签的识别精度,提高了RFID系统多标签同时识别的性能。
决策树ID3算法的一种改进 篇6
ID3算法由Quinlan于1979年提出。其基本思想是:在对训练集进行分类时, 以信息熵为度量, 用于决策树节点的属性选择, 每次优先选取信息量最多的属性对数据进行划分, 以构造一颗熵值下降最快的决策树, 每个叶子节点对应的实例集中的实例属于同一类。
设样本数据集T有s个样本, 每个样本都有u个评估属性kA, m个类别。评估属性划分T成v个子集, 其中jT中包含sj样本, 属于第iC类的样本数为sij (i=1, 2, ...m) 。则有:子集Tj的信息熵:
属性Ak的信息熵为:信息增益为:Gain (Ak) =I (T) -E (Ak)
2 ID3算法的优点和不足
优点:运用信息论知识选择属性, 理论清晰;容易生成IF-THEN语句;对于离散型样本数据处理功能强;ID3自顶向下搜索, 节省系统资源, 计算时间与样本大小。
不足:ID3算法在选择分类属性时往往选择了取值较多的属性;ID3算法只能处理离散型数据, 若分析必须先进行离散化;用ID3算法创建决策树时必须知道所有内部节点。
3 ID3算法的改进
定理1:若函数f (x) 在[a, b]上连续, 在 (a, b) 内有一阶、二阶导数, 并且
在 (a, b) 上, 若f' (x) <0, 则f (x) 在[a, b]上是凸函数;
性质:若f (x) 在区间I上是凸函数,
λ1, λ2, ..., λn>0, 则有:λ1f (x 1) +...+λnf (x n) ≤f (λ1 x1+...+λn xn)
3.1 算法改进的实现
pi表示数据属于类Ci的概率, 在 (0, 1) 上任取p1, p2有p1+p2=1, p1-p2=△p→0, 因为log2 p函数在 (0, 1]上连续, 由定理1可知log2 p函数在其连续区间上是凸函数。
由凸函数性质计算得:
假设样本数据集T有s个样本, u个评估属性m个类别属性。评估属性kA划T成v个子集Tj含sj样本, 第iC类的样本数为sij。所以子集的信息熵为:
属性的信息熵是:信息增益为:Gain (Ak) =I (T) -E (Ak)
3.2 改进算法的应用
表一为某公司调查的顾客数据统计表.通过数据挖掘旨在回答“谁在买电脑”这一问题。
第1步:决策属性的信息熵
第2步:计算条件属性的熵
1) 年龄分三组:老、中、青。青年384人, 正例128人, 反例256人;中年256人, 正例256人, 反例0人;老年252人, 正例125, 反例127人。
老年:I (125, 127) =0.9157所以, E (年龄) =0.6877;G (年龄) =0.9537-0.6877=0.2660;
2) E (收入) =0.9361 G (收入信息增益) =0.9537-0.9361=0.0176;
3) E (学生) =0.7811 G (年龄信息增益) =0.9537-0.7811=0.1726;
4) E (信誉) =0.9048 G (信誉信息增益) =0.9537-0.9048=0.0453。
第3步:计算选择节点。由上可知“年龄”具有最高的信息增益, 选择“年龄”为测试属性。
第4步:递归建树算法, 分别对各个子集分析, 计算选择分支的测试属性。
1) 年龄=“青年”的子集有:选择学生为测试属性对子集进行再划分;
2) 对于年龄=“中年”, 数据都属于同一类, 自然形成树叶;
ID3算法在构件库中的应用 篇7
随着计算机技术的快速发展, 各行业中积累了大量数据, 如何在这些数据资源的背后找出大量隐藏的知识信息, 已成为各商业领域广泛关注的问题。基于这种背景, 数据挖掘技术应运而生。数据挖掘技术主要有决策树方法、神经网络方法、统计学方法、粗糙方法和可视化技术等[1], 这些数据挖掘技术从不同角度对大量历史数据进行知识挖掘。由于常用于分类和预测的决策树方法具有速度快、精度高、生成模型简单等优点, 在诸多的数据挖掘方法和技术中, 其受到了许多理论研究者的广泛关注[2]。
目前, 国际上最早具影响力的决策树方法是J.Ross.Quinlan等人于1986年提出的ID3算法。ID3算法的优点是:理论基础清晰、分类原理简单、学习能力强、适用于处理大规模的学习问题, 因此, ID3算法一直是数据挖掘领域中的一个极好典范[3]。由于国内研究人员对ID3算法的研究主要是算法的改进, 而对该算法的具体应用不多, 对构件库中的应用研究更少, 本文的工作弥补了这方面的不足。
2 ID3算法简介
ID3算法是数据挖掘技术中广为人知的一个重要算法, 它是决策树构造方法中用于分类预测的最为常用的具体实现方法, 其理论基础是由C.E.Shannon建立的信息论[4]。ID3算法将信息论中的信息增益作为选取最优属性的标准。
3 ID3算法在构件库中应用
3.1 构件样本数据集合的准备工作
要对大量数据进行数据挖掘和知识发现, 数据集成在数据挖掘流程中是非常重要的一个步骤。将ID3算法用于构件库中之前, 所需的集成数据需通过数据集成过程来完成。根据上海构件库中的构件信息, 建立模拟构件库, 其中包括用户对构件的反馈信息表和构件基本信息[5]。对于反馈信息表来说, 构件的很多复用用户对构件的各种评价信息是构件库管理者后期收集得到的, 因此保存的是构建管理者或复用者较为关注的构件属性, 而构件基本信息中的记录原本就保存在构件库中, 较为容易提取。参照上海构件库, 这里分别给出如表1和表2所示的用户反馈信息表和构件基本信息表。
对以上两个构件数据表进行集成处理, 初步整合成为构件模拟数据集, 然后对模拟数据集中的数据进行选取、预处理、转换、消除冗余和重复数据等一系列构件数据准备工作, 再通过将连续值进行离散化、筛选对数据挖掘有用的属性等操作, 最终得到如表3所示构件样本数据集合。
3.2 ID3算法的执行
本文采用C语言实现ID3优化算法, 并将集成处理后的构件样本数据集合作为ID3算法执行时的训练集。样本数据集合中包含的决策属性和分类属性等详细信息如表4所示。
利用ID3算法实现构件库分类和预测实例中, 计算每个决策属性的信息增益是实现ID3算法的关键步骤。执行ID3算法, 生成一棵如图1所示的决策树。
4 结语
本文通过ID3算法与构件库管理系统结合, 将决策树算法应用于构件库当中, 从生成的决策树中提取大量构件基本信息背后的知识规则, 进而可以辅助构件复用者方便准确快捷地做出理想复用决策。构件复用者平时所关注的影响构件复用的各种因素与通过ID3算法所提取的构件背后的信息相一致, 进而体现了决策树分类方法中ID3算法在构件库应用中的实用性和有效性。
摘要：随着人们对数据挖掘理论知识的不断研究和探讨, 数据挖掘技术和应用领域日趋成熟和广泛。在数据挖掘技术中, 决策树方法是用于分类和预测的重要方法之一。本文对决策树构造方法中最为常用的ID3算法进行分析和研究, 并将ID3算法在构件库中进行应用, 证明了决策树分类方法在构件库领域中的应用前景。
关键词：数据挖掘,ID3,构件库
参考文献
[1]杨会志.数据挖掘技术的主要方法及其发展方向[J].河北科技大学学报, 2000, 21 (3) :77-80.
[2]朱绍文, 胡宏银, 王泉德, 等.决策树采掘技术及发展趋势[J].计算机工程, 2000, 10, 26 (10) :1-3.
[3]朱玉全, 杨鹤标, 孙蕾.数据挖掘技术[M].南京:东南大学出版社, 2006, 11.
[4]陈文伟, 黄金才.数据仓库与数据挖掘[M].北京:人民邮电出版社, 2004, 1.
最小ID算法 篇8
数据挖掘主要是从大规模数据库的数据中抽取有效的、隐含的、以前未知的、有潜在实用价值的信息。数据挖掘的关键是在训练数据中发现事实,以测试数据作为检验和修正理论的依据,把知识应用到数据中[1]。其中决策树算法是数据挖掘中的一种重要算法,在分类预测方面得到了广泛的应用[2,3,4],它的目的是根据某个新记录的属性,将其分派到预先定义好的若干类中的一个,并为其添加一个字段以标识该记录的类别。决策树算法沿用的是传统的机器学习算法,处理大数据量数据时,存在三点不足:①基于主存,处理的数据量较小;②算法通常需要将数据以文件形式提供,在进行数据挖掘前需要进行数据转换工作;③面对大量数据,没有充分利用数据库技术所具有的对数据操作的优势,文献[5]对该问题进行了研究。本文在深入研究ID3算法的基础上,结合结构化查询语言SQL具有强大的分组、统计功能,提出一种基于SQL语句的ID3改进算法,通过SQL语句直接对保存在数据库中的数据表进行分组查询,计算测试属性的条件熵,并采用C++面向对象语言实现,充分利用了SQL语句的高效性和C++语言的灵活性,高效地实现了大量数据的分类,工程实践中易于实现。
1 基本概念
决策树学习是以样本为基础的归纳学习方法,表现形式类似树结构,在决策树的内部结点进行属性值测试,并根据属性值判断由该结点引出的分支,在决策树的叶结点得到结论。ID3 是Quinlan于1979年提出的著名的决策树算法。ID3算法的基本策略如下:
(1) 树以代表整个训练样本、全部条件属性作为测试属性集的单个结点开始。
(2) 如果样本都在同一个类,则该结点成为树叶,并用该类标号。
(3)否则,计算每个测试属性的信息增益,选取信息增益最大的属性将样本分类。该属性成为该结点创建分支的判定属性。
(4)对判定属性的每个已知值,创建当前结点的子结点,并根据属性值划分样本,同时将父结点的测试属性集移去判定属性,作为各子结点的测试属性集。
(5)算法使用同样的过程,递归地形成每个结点的子结点。
(6)递归生成子结点仅当下列条件之一成立时停止:①当前结点的所有样本属于同一类;②测试属性集为空,使用多数表决的方法将该结点转换为叶结点;③分支在某一个属性值上没有样本,使用多数表决的方法创建一个叶结点。
2 基于SQL语句的ID3算法的实现方法
2.1 数据结构设计
该算法实现涉及两个问题:①树表示方法,②结点表示方法。树采用孩子兄弟表示法存储,设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。结点包含测试属性集,样本子集、第一个孩子结点、右兄弟结点,若是叶子,还有类别。其中测试属性集合是在父结点的该属性值基础上与当前判定属性的差集,采用C++ STL中的vector容器存储;样本子集是样本数据表中记录的子集,是将当前结点至根结点所经结点构成的属性名=属性值带入SQL 1 中L参数的查询结果。
2.2 条件熵计算方法
class表示分类属性,计算结点N的测试属性集中某属性c的条件熵tjs:
将数据表中满足N.where 的记录行,按照属性c和分类属性class进行分组统计,即SQL为“select c,class,count(*) from 数据表 where N.where group by c,class order by c,class”,查询结果存入二维数组 r[m][n],m为属性c的取值个数,n为分类属性class取值个数,数组r的每行元素的和存入一维数组s[m]中。计算过程如下:
2.3 递归函数BuildChildNode
基于数据库查询的决策树算法,继承了原ID3算法思路,通过2.2的方法计算测试属性的条件熵。在子树生成过程中,可以采用深度优先和广度优先生成子树的方法实现。递归函数BuildChildNode如下:
输入:存储了测试属性集、记录行筛选条件(无)的根结点pNode。
输出:以pNode为根结点孩子兄弟表示法存储的决策树。
算法描述:
3 算法应用
文献[6]给出了一个可能带有噪音的数据集合。它有四个条件属性:outlook,temperature,humidity,windy。被分成两类,p与n,分别为正例与反例。采用本文提出的算法对该数据集合构造决策树。数据见表1.
决策树构造过程:
①定义决策树的根结点,并初始化。
Node root;
root.attrs={outlook,temperature,humidity,windy}
root.where=NULL;
设参数K表示待测试属性,class表示分类属性,tb_PlayTennis为保存数据集的数据库表名,L为记录筛选条件。三个常用SQL语句如下:
select K,class,count(*) from tb_PlayTennis where L group by K,class order by K,class (SQL 2)
当L为NULL时,SQL 1转变为:
select K,class,count(*) from tb_PlayTennis group by K,class order by K,class (SQL 3)
select * from tb_PlayTennis (SQL 4)
②以root为参数调用递归函数BuildChildNode,即BuildChildNode(& root),
(1) 此时root.where为NULL,将Outlook带入SQL 3中的参数K,将查询结果见表2。
根据2.2的算法,计算得出:H(class,Outlook)=0.552 8
同理,将Temperature、Humidity、Windy分别带入SQL 3中的参数K,依次得出:
H(class,Temperature)=0.917 2,
H(class,Humidity)=0.918 3,
H(class,Windy)=1.00。
②选取Outlook作为分支属性,各个子节点的测试属性集为{temperature,humidity,windy},根据其三个取值sunny、overcast、rain开始生成子节点,按照深度优先的策略构造决策树,
(1)首先生成实例集为将Outlook=' sunny '代入SQL 4中参数L所形成的记录集对应的子结点N2,由于N2的所有记录的class属性值为p,所以标记N2为叶结点,并从递归算法中返回;
(2)同理,当outlook='overcast' 时生成结点N3,各测试属性的条件熵为:
H(class,temperature)=0.444 4,
H(class,humidity)=0.000 0,
H(class,windy)=0.972 8。
选取属性humidity作为分支属性,根据其两个属性值high、normal生成子结点,首先生成实例集为outlook='overcast' and humidity='high'对应的子结点N4,此时class属性值全部为n,从递归函数中返回,然后生成实例集为 outlook='overcast' and humidity='normal' 对应的子结点N5,此时class属性值全部为p,从递归函数中返回;
(3)当outlook='rain' 时,同理生成其子树。这里不再一步一步求解,结果见图1。
4 总结
本文首先介绍了决策树算法的基本概念,针对ID3算法在处理大数据时存在的不足,通过引入数据库查询语句,给出了条件熵计算方法。进而提出ID3算法的一种新的实现方法。并在递归算法中给出了深度优先和广度优先建树方案,解决了ID3算法与数据库继承性差的问题。最后通过实例分析,证明了该算法的正确性。
摘要：ID3算法沿用的是机器学习算法,与数据库集成性差。提出一种基于SQL语句的ID3改进算法。通过SQL语句直接对保存在数据库中的数据表进行分组查询,计算测试属性的条件熵,并给出深度优先和广度优先生成子树的递归算法。实验证明,改进的ID3算法充分利用了SQL的高效性和C++语言的灵活性,降低了算法实现难度,高效实现大量数据的分类。
关键词：ID3,决策树,信息熵,SQL语句
参考文献
[1]李雄飞,李军.数据挖掘与知识发现.北京:高等教育出版社,2003:2—3
[2]王英,刘维亭.决策树算法在电网报警信息处理中的应用.科学技术与工程,2011;11(30):7375—7378
[3]宋晖,张良均.C4.5决策树法在空气质量评价中的应用.科学技术与工程,2011;11(20):4848—4850
[4]丁胜祥,董增川,张莉.基于决策树算法的洪水预报模型.水力发电,2011;37(7):8—12
[5]杨一展,李小平,段霞霞.一种基于数据库查询的改进的决策树算法.计算机工程与应用,2008;44(15):148—150