首页 人力资源Apriori算法分析和改进,基于Markov异常检测模型

人力资源Apriori算法分析和改进,基于Markov异常检测模型

举报
开通vip

人力资源Apriori算法分析和改进,基于Markov异常检测模型人力资源Apriori算法分析和改进,基于Markov异常检测模型 Apriori算法分析和改进 一 Apriori算法介绍 1.1 Apriori 算法思想 Apriori 算法的基本思想是:首先找出事务中所有的频集,这些频集出现的频繁性需要大于或等于预先设定的最小支持度。随后由频集产生强关联规则, 这些规则必须大于最小支持度和最小可信度。为了生成所有频集,使用了递推的方法。 1.2 Apriori 算法步骤 1.制定最小支持度及最小置信度。 2.对数据集所有事务进行扫描,对每个项出现的次数计数,删除那些...

人力资源Apriori算法分析和改进,基于Markov异常检测模型
人力资源Apriori算法分析和改进,基于Markov异常检测模型 Apriori算法分析和改进 一 Apriori算法介绍 1.1 Apriori 算法思想 Apriori 算法的基本思想是:首先找出事务中所有的频集,这些频集出现的频繁性需要大于或等于预先设定的最小支持度。随后由频集产生强关联 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf , 这些规则必须大于最小支持度和最小可信度。为了生成所有频集,使用了递推的方法。 1.2 Apriori 算法步骤 1.制定最小支持度及最小置信度。 2.对数据集所有事务进行扫描,对每个项出现的次数计数,删除那些出现计数值小于阈值的项集,这样就得到 L1频繁项集; 3.利用频繁 1-项集合的结合,产生候选 2-项集合 C2(Candi,date2-itemset)。 4.对 C2中每个候选项集的支持计数,确定频繁项集 2-项集的集合 L2,并利用这些频繁 2-项集合 L2的结合,产生候选 3-项集合 C3。 5.重复扫描数据库产生更高层次的频繁项集合,再结合产生下一级候选项集,直到穷尽数据集中的所有频繁项集。 Apriori 算法描述如下: (1) C1={candidate1-itemsets}; (2) L1={c?C1|c.count?minsupport}; (3) For(k=2,Lk-1?Φ,k++)//直到不能再生成最大项目集为止 (4) Ck=sc_candidate(Lk-1);//生成含 k 个元素的侯选项目集 (5) for all transactions t?D//办理处理 (6) Ct=count_support (Ck,t);//包含在事务 t 中的侯选项目集 (7) for all candidates c?Ct (8) c.count=c.count+1; (9)next (10) Lk={c?Ck|c.count?minsupport}; (11) next (12) resultset=resultset?Lk 其中,D 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示数据库,minsupport 表示给定的最小支持度,re,sultset 表示所有最大项目集。 1.3 Apriori 算法的不足 在Apriori 算法中候选项集是逐层产生, 而产生此层的频集, 必须要扫描整个数据库一次, 然后再结合频集产生下一层级的候选项集合, 直到频集无法结合产生候选项集。Apriori 算法一定要等到扫描完整个数据库后才做结合, 因为在扫描的过程中, 有些候选项集在若干的区段中的支持度已大于等于使用者制定的最小支持度, 因此在扫描这些若干个区段后, 便可以找出频集, 并直接结合产生下一个层级的候选物项集。基于上述原因,Apriori算法可能会存在下述问题。 (1) 所挖掘的规则存在大量冗余。 (2) 因计算项过多而造成执行能缓慢, 主要的原因在于频繁项集合产生过多的候 选项集, 尤其是候选22项集的情况最为严重。 二 Apriori 算法的典型改进及其比较 2.1 FIS-ES 算法 FIS-ES 算法对传统集合操作进行了扩展,提出了基于扩展集合操作的最大频繁项集生成法 FIS-ES,算法通过从数据库中检测是否有符合最小支持度 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 的频繁项, 并删除该频繁项的真子集,循环操作直到读完数据库中的 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 为止。该算法通过只保留最大的频繁项集,从而压缩了搜索空间、提高了数据挖掘的效率。 2.2 基于 PCL 模型的频繁项集求解算法 从近几年频繁项集挖掘算法的研究趋势来看, 为了提高算法的效率,提出了一系列的混合搜索策略和高效剪枝策略。在基于 Apriori 算法性质基础上,胡学钢等在《基于剪枝概念格模型的频繁项集表示及挖掘》一文提出了基于 PCL 模型的频繁项集求解算法,改善了频集挖掘算法的时空性能。 2.3 FP-DFS 算法 在文献中作者以 FP-tree 为基本数据结构, 首先通过新的搜索策略和剪枝策略, 将事务数据库 D 压缩为内存中的 FP-tree,然后按照相反次序逐个处理项集中的项目,每次迭代得到以某个项目开头的所有频繁项集。从而提高算法的搜索效率,减少了对内存的占用,算法的空间复杂性低。 2.4 使用概率的方法求候选频繁项集的 Apriori 改进算法 针对 Apriori 算法存在的可能产生大量的候选集的缺点,该算法通过使用概率的方法估算任意数据项集同时出现的概率来求候选频繁项集。首先创建数组来记录各个属性项独立出现的概率,设定最小概率,得到 m 个多个频繁 1 项集,由 m 个频繁1 项集的独立出现概率, 估算出任意两个属性项同时出现的概率,得到候选频繁 2 项集,通过迭代,由候选频繁数据项集的支持度求出频繁项集。 2.5 基于事务地址索引表来约简事务的 Apriori 优化算法 针对 Apriori 算法需要重复地扫描数据库的缺陷,基于事务地址索引表来约简事务的 Apriori 优化算法提出使用一个有效约简事务数据库中事务的策略对算法进行优化。该算法中给出了一个有效约简事务的方法, 就是通过创建事务地址索引表缩小了对事务数据库记录的搜索范围,实现了分区域的快速定位,从而减少解空间,优化了候选集的计数过程,一定程度上提高了Apriori 算法的执行效率, 但是该算法还是需要对事务数据库多次扫描。 2.6 适用于数字资源访问日志数据库的关联规则挖掘改进算法 文献提出了一种适用于数字资源访问日志数据库的关联规则挖掘改进算法,通过事务压缩和项目压缩相结合,生成候选项目集的同时, 剔除事务数据库中不支持频繁项集的事务及事务中的项目, 在每条事务压缩后通过联接产生候选项目集及计算支持度,候选项目集采用关键字识别,省去了 Apriori 算法中的剪枝和字符串模式匹配步骤,提高了产生频繁模式集的速度。但是该算法存在应用范围较窄的缺陷。 2.7 S_Apriori 算法 S_Apriori 算法在 Apriori 算法的基础上作了改进,采用新的数据结构, 使得只需要扫描一次数据库和连接时无须重复判断即可快速找到更高阶的频繁项目 集,算法的效率也得到了提高。 总之,国内外众多学者从不同的角度提出了各种优化算法,尽管这些算法各具优点且挖掘的性能和效率均明显高于传统的算法,但总的来说,各自还是有些缺点,算法仍较复杂。 FIS-ES 算法与 Apriori 算法的不同之处就在于 FIS-ES 只需扫描一次数据库,而 Apriori 算法的每一次频繁项集的产生都需要扫描一次数据库。所以该算法比 Apriori 算法具有更快的挖掘速度、更少的空间占用等优点,但也存在一些不足:算法的时间和空间占用随项目长度的增加呈指数增长, 这种情况在最小支持度较大时表现得尤为突出;事务数据量比较大时,对内存的要求会比较高。基于 PCL 模型的频繁项集求解算法应用过程中构造剪枝概念格需要花费一定时间, 另外基于概念格及其分布式关联规则挖掘算法及其在实际应用需要进行大量的研究,尤其是分布式概念的关联规则挖掘算法等都需要进一步深入研究解决。 通过使用概率的方法估算任意数据项集同时出现的概率来求候选频繁项集的方法,该算法与 Apriori 算法比较产生的候选项集大小和扫描数据库次数都有了改进, 将关联规则挖掘的运行速度提高了一个数量级,这种算法非常适合挖掘数据库大、长模式的关联规则, 但是算法中参数 a、b 的设定需要额外的时间,同时算法采用概率估算求候选频繁项集,如果参数设定不合适, 有可能会遗漏一些用户感兴趣的关联规则。FP-DFS 算法、基于事务地址索引表来约简事务的 但也存在应Apriori 优化算法等其他算法与 Apriori 算法比较提高了搜索效率,用范围较窄等问题。 基于Markov异常检测模型 一引言 入侵检测系统,作为对常规安全措施如用户 (IDSIntrusionDetectionSystem)(认证、信息加密和安全产品如防火墙的补充,已被越来越多的人所认识。入侵)() 检测系统从检测技术上可分为特征检测、统计分析和专家系统三种技术。Marko过程模型作为一种统计分析技术在语音识别、信息抽取和一些分类领域得到成v 功应用,但将其应用于网络安全中的异常检测,研究得并不多。 异常检测是事先定义一组系统”正常”情况的数值,如利用率、内存利CPU用率、文件校验和等这些数据可以人为定义,也可以通过观察系统利用统计的( 办法 鲁班奖评选办法下载鲁班奖评选办法下载鲁班奖评选办法下载企业年金办法下载企业年金办法下载 得出,然后将系统运行时的数值与定义的”正常”情况比较,得出是否有) 被攻击的迹象。异常检测的困难在于如何定义所谓的“正常”情况,它需要对系统安全有足够的背景知识。如何在领域知识匮乏的情况下,识别系统的异常行为,对于异常检测的实际应用有着十分重要的意义。 下面介绍从单步、多步链和基于多步链的序列预测三个方面,MarkovMarkov 较为全面地研究了链模型在异常检测上的应用。Markov 二链模型应用于异常检测 Markov 链是随机过程的特殊情况它是状态和时间参数都离散的 MarkovMarkov,M 过程随机序列在任一时刻可以处在状态θ„θ且它在时刻arkov.Xu,t,1,,T,m+k所处的状态的概率只与它在时刻的状态有关而与它在时刻以前所处状态,m,m 无关则称为链实际中链的每一状态对应于一个可以观测到,XuMarkov.,Markov 的物理事件所有状态之间的转移用状态转移概率矩阵表示状态转移概率矩阵和,. 状态的初始概率分布二者结合可完整描链,Markov. 大部分攻击过程都包含了一系列前后相关的行为其特征与正常系统过程有 , 着明显的 差别链模型在异常检测中的应用就是利用这种差别使用链建立,Markov,Markov正常系统 行为的统计模型并以此来检测系统行为的异常状态对应于每种类型的系统事,. 件用状态, 转移矩阵来表示状态间的变化当一个事件发生时如果状态转移矩阵确认该转移,, 的概率较 小则可能是异常事件. 建立链模型2.1Markov 首先通过统计方法计算一步转移概率矩阵元素表示系统在时刻处于 ,P,Pijt状态在i, 时刻处于状态的概率计算公式为t+1j,: Pij= Nij/Ni (1) 其中表示系统调用和系统调用相邻出现的次数表示系统调用出现的,Nijij;Nii次数. 此外设系统的初始状态概率矢量ππ„π其中,= (1,,n),, ππθ ?? i= P(i=i) =NiN,1in (2) 其中表示系统调用出现的次数表示总的系统调用数显然有?π?并,Nii;N.:0i1且?πii=1 另外单步链模型存在两条基本假设,Markov: 时刻系统状态的概率分布只与时刻的状态有关与时刻以前的状态 1)t+1t,t无关. 从时刻到时刻的转移概率与的值无关这两条假设对系统调用序列并2)tt+1t. 不严格 成立要考虑某一状态的前几个状态对该状态的影响例如在序列„,.,(S1,S2,,St-1,中不仅对有影响此前的若干系统调用也可能影响到为此要计算多St),St-1St,St.步的状态转移概率由多步转移概率的性质×可以使用.MarkovP(t+s)=P(t)P(s),一步转移概率矩阵来计算得到多步的转移概率矩阵. 链分析检测数据2.2Markov 滑动窗口序列 2.2.1 首先利用滑动窗口对长的序列进行分割形成小的序列集合窗口分割一般有时,. 间窗分 割和数量窗分割两种时间窗分割是用一定长度的时间间隔譬如划分序列.(2 s).本方法是以一定长度的系统调用序列为基本单位使用数量窗来分割序列例如,.,对系统调用序列„„使用长为的滑动窗口划分可得(S1,S2,,St,St+1,,St+s),t,s+个长为的序列集合„„„„„1t:(S1,S2,,St);(S2,S3,,St+1)(Ss+1,Ss+2,,St+s); 分析方法2.2.2 在建立了正常系统调用行为的链模型之后利用该模型对待检测的序Markov, 列进行分 析分析的方法有以下几种,: 单步链计算序列支持度(1)Markov. 对长度为的系统调用序列„计算正常系统模式对其支持度 t(S1,S2,,St),:P(S „π×ׄ×若此支持度小于某一阈值则此序1,S2,,St)=S1PS1S2PSt-1St.(3),列为异常序列否则为正常序列并统计所有异常序列所,, 占的比率. 多步方法(2)Markov. 由于单步链存在的前提假设在实际应用中不能严格成立为此采用多Markov,步的 链分析方法对长度为的系统调用序列„计算在正常系统模Markov.t(S1,S2,,St),式下下一系统调用出现的概率„这里取序列„St+1P(St+1S1,,St).(S1,S2,,St)中所有时刻的状态??到的转移概率的加权平均值计算公式为Si(1it)St+1,: tt P(St,1S1,?,St) ,WiPSiSt,1/Wi,,,,i1i1 其中是时刻系统调用为时刻系统调用为的概率由 :PSiSt+1iSi,t+1St+1,t 步状态转移概率矩阵得到是状态到的转移概率权值体现的是与+1-i.WiSiSt+1, 距离为的对的影响距离越小影响越大所以随着增加权值St+1t+1-iSiSt+1,,i,变大本文取??若此概率小于某一给定的阈值则认为该序列是一,Wi= i2(1it).,异常序列否则为正常,. 基于多步链的序列预测3)Markov 利用正常系统模式的长度为的系统调用序列„来预测待测序列 t(S1,S2,,St) t的下一系统调用具体方法是使取得最大值的做为St+1.St+1t+1WiPSiSt,1,,i1 时刻的状态估计即???.:St+1=argmax1itiWiPSiSt+1 若实际序列中与预测值相同则记为正常否则为异常同样对所有的序 St+1,,.列进行预测亦可发现用正常系统模式对正常系统行为进行预测其序列不正常比,,例要远小于对异常行为序列的预测所得的不正常比例.
本文档为【人力资源Apriori算法分析和改进,基于Markov异常检测模型】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_180829
暂无简介~
格式:doc
大小:23KB
软件:Word
页数:0
分类:企业经营
上传时间:2018-02-19
浏览量:18