下载文档原格式
邮局订阅号：82-946120元/年技术创新软件时空《PLC 技术应用200例》您的论文得到两院院士关注K-means 算法的改进及应用Improvement and Application of k-means Algorithm(上海大学)王刚勇周维民WANG Gang-yong ZHOU Wei-min摘要:针对k-means 算法在聚类过程中受初始聚类中心影响很大的问题,本文提出了一种优化初始聚类中心的方法。
此方法通过计算聚类中心与其他各个点之间的距离,依次找到最佳的一组初始聚类中心组合。
实验表明改进后的k-means 算法提高了检测率,降低了误检率,产生了质量较高的聚类结果。
关键词:K-means 算法;中心对象;聚类中图分类号:TP393.08文献标识码:AAbstract:In allusion to the problem of k-means algorithm that is greatly affected by the initial clustering center,a new method is proposed to optimize the initial clustering center.The method calculating the distance between the clustering center and other points will find the best clustering center combination.Experiments on the web-log show that the improved k-means algorithm can improve the detection rate,reduce error rate,and produce a high clustering result.Key words:K-means algorithm;Center object;Clustering文章编号:1008-0570(2012)10-0431-021引言随着计算机技术的不断发展,网络已经遍布于世界的各个领域和角落,随着而出的信息安全问题显得尤为重要。
分析Technology AnalysisI G I T C W 技术136DIGITCW2021.021 决策树分类算法1.1 C 4.5分类算法的简介及分析C4.5分类算法在我国是应用相对较早的分类算法之一，并且应用非常广泛，所以为了确保其能够满足在对规模相对较大的数据集进行处理的过程中有更好的实用性能，对C4.5分类算法也进行了相应的改进。
C4.5分类算法是假如设一个训练集为T ，在对这个训练集建造相应的决策树的过程中，则可以根据In-formation Gain 值选择合理的分裂节点，并且根据分裂节点的具体属性和标准，可以将训练集分为多个子级，然后分别用不同的字母代替，每一个字母中所含有的元组的类别一致。
而分裂节点就成为了整个决策树的叶子节点，因而将会停止再进行分裂过程，对于不满足训练集中要求条件的其他子集来说，仍然需要按照以上方法继续进行分裂，直到子集所有的元组都属于一个类别，停止分裂流程。
决策树分类算法与统计方法和神经网络分类算法相比较具备以下优点：首先，通过决策树分类算法进行分类，出现的分类规则相对较容易理解，并且在决策树中由于每一个分支都对应不同的分类规则，所以在最终进行分类的过程中，能够说出一个更加便于了解的规则集。
其次，在使用决策树分类算法对数据挖掘中的数据进行相应的分类过程中，与其他分类方法相比，速率更快，效率更高。
最后，决策树分类算法还具有较高的准确度，从而确保在分类的过程中能够提高工作效率和工作质量。
决策树分类算法与其他分类算法相比，虽然具备很多优点，但是也存在一定的缺点，其缺点主要体现在以下几个方面：首先，在进行决策树的构造过程中，由于需要对数据集进行多次的排序和扫描，因此导致在实际工作过程中工作量相对较大，从而可能会使分类算法出现较低能效的问题。
其次，在使用C4.5进行数据集分类的过程中，由于只是用于驻留于内存的数据集进行使用，所以当出现规模相对较大或者不在内存的程序及数据即时无法进行运行和使用，因此，C4.5决策树分类算法具备一定的局限性。
expected improvement 算法摘要：1.预期改进算法（Expected Improvement）简介2.预期改进算法的应用领域3.预期改进算法的优点与局限性正文：1.预期改进算法（Expected Improvement）简介预期改进算法（Expected Improvement，简称EI）是一种启发式搜索算法，主要应用于组合优化问题，例如旅行商问题（Traveling Salesman Problem，TSP）、车辆路径问题（Vehicle Routing Problem，VRP）等。
该算法的目标是在搜索过程中，每次迭代都尝试寻找能使解质量提高的解，以此来加速收敛过程。
2.预期改进算法的应用领域预期改进算法在很多组合优化问题中都有广泛应用，特别是那些NP 难问题。
例如：（1）旅行商问题：在给定城市之间距离的情况下，寻找一个最短路径，使得从一个城市出发，经过所有其他城市后，最终回到出发城市。
（2）车辆路径问题：在给定客户位置、需求量、车辆载重及行驶时间等因素的情况下，寻找一种车辆分配方案，使得总行驶里程最短或总运输成本最低。
（3）装箱问题：给定一组物品和箱子的尺寸，寻找一种最优的装箱方案，使得所有物品都能被装入箱子，且箱子的总容量最小。
3.预期改进算法的优点与局限性预期改进算法的优点主要表现在以下几个方面：（1）具有较好的启发性，能够在搜索过程中找到改善解的质量，加速收敛；（2）适用于多种组合优化问题，具有一定的通用性；（3）算法简单易懂，实现较为容易。
然而，预期改进算法也存在一些局限性：（1）在搜索过程中，可能会陷入局部最优解，导致算法收敛速度降低；（2）算法的收敛性与问题的特性有关，对于某些问题，算法可能表现不佳；（3）算法需要设置一些参数，如搜索深度、启发式因子等，参数设置不当可能影响算法性能。
总之，预期改进算法是一种具有启发性的搜索算法，适用于多种组合优化问题。
数据挖掘十大经典算法数据挖掘是通过分析大量数据来发现隐藏的模式和关联，提供商业决策支持的过程。
在数据挖掘中，算法起着至关重要的作用，因为它们能够帮助我们从数据中提取有用的信息。
以下是十大经典的数据挖掘算法：1.决策树算法：决策树是一种基于分层选择的预测模型，它使用树状图的结构来表示决策规则。
决策树算法适用于分类和回归问题，并且可以解释性强。
常用的决策树算法有ID3、C4.5和CART。
2.朴素贝叶斯算法：朴素贝叶斯是一种基于概率的分类算法，它假设特征之间是相互独立的。
朴素贝叶斯算法简单有效，适用于大规模数据集和高维数据。
3.支持向量机（SVM）算法：SVM是一种针对分类和回归问题的监督学习算法，它通过构建一个最优的超平面来实现分类。
SVM在处理非线性问题时使用核函数进行转换，具有较强的泛化能力。
4.K近邻算法：K近邻是一种基于实例的分类算法，它通过找到与目标实例最接近的K个邻居来确定目标实例的类别。
K近邻算法简单易懂，但对于大规模数据集的计算成本较高。
5.聚类算法：聚类是一种无监督学习算法，它将相似的实例聚集在一起形成簇。
常用的聚类算法有K均值聚类、层次聚类和DBSCAN等。
6.主成分分析（PCA）算法：PCA是一种常用的降维算法，它通过线性变换将原始数据转换为具有更少维度的新数据。
PCA能够保留原始数据的大部分信息，并且可以降低计算的复杂性。
7. 关联规则算法：关联规则用于发现项集之间的关联关系，常用于市场篮子分析和推荐系统。
Apriori算法是一个经典的关联规则算法。
8.神经网络算法：神经网络是一种模仿人脑神经元通信方式的机器学习算法，它能够学习和适应数据。
神经网络适用于各种问题的处理，但对于参数选择和计算量较大。
9.随机森林算法：随机森林是一种基于决策树的集成学习算法，它通过建立多个决策树来提高预测的准确性。
随机森林具有较强的鲁棒性和泛化能力。
10.改进的遗传算法：遗传算法是一种模拟生物进化过程的优化算法，在数据挖掘中常用于最优解。
第29卷第5期2008年10月华 北 水 利 水 电 学 院 学 报Journa l of Nort h China Institut e of W ate r Conservancy and Hydroe l ec tric Powe rVol 129No 15Oct .2008收稿日期6作者简介侯 兵(—),男,河南商丘人,助教,硕士,主要从事概率统计和数据挖掘方面的研究文章编号:1002-5634(2008)05-0061-04关联规则挖掘中改进的增量式更新算法侯 兵1,程伟丽1,李 霞2(1.华北水利水电学院,河南郑州450011;2.河南财经学院统计学系,河南郑州450002)摘 要:增量式更新算法能充分利用已挖掘出的知识来提高挖掘效率,是数据挖掘高效算法中的一个主要方向.分析了典型的关联规则增量式更新算法波折法F UP 算法的不足,提出了一种改进的关联规则增量式更新算法,新算法极大地降低了存储空间和挖掘时间需求,从而提高了整个关联规则挖掘的效率.关键词:数据挖掘;关联规则;算法中图分类号:TP311.13 文献标识码:A1 FUP 算法1.1 F UP 算法的基本思想在众多的增量式更新算法中,D W Cheung 等提出的F UP (Fast UPdating A lgorithm )算法[1],是Ap ri 2ori 算法[2]的改进,是最典型、最有效和最实用的算法之一,绝大部分关联规则更新算法的基本思想与其一致,由于交易数据库中的数据是不断增加的,必然引起关联规则发生变化,如果采用Ap ri ori 算法对更新后的数据库进行挖掘,由于数据库规模越来越大,则挖掘效率会越来越低,F U P 算法是为解决这个问题提出的.设原有交易数据库中的数据集记为D (也称为旧数据集),新增加数据集记为d (也称为新数据集),则当前事务数据库为(D +d ).假设已经采用Apriori 算法获得数据集D 的频繁项目集是L (D ),则F UP 算法的基本思想[1]为:1.利用Apri ori 算法生成新事务数据集d 的频繁项目集L (d ),比较L (d )和L (D ),找出相同部分放入当前事务数据库(D +d )的频繁项目集中.2.对于t ∈(L (D )-L (d ))的频繁项目集,如果t ∈L (D )且t |L (d ),则扫描d 得到t 在d 中的支持度support d ,再根据D 中已经求得的支持度sup 2port D ,求出t 在(D +d )中的支持度support D+d=support d d +support DDd +D如果support D +d >m in_sup,则把t 放入当前事务数据库(D +d)的频繁项目集中,否则t 不属于频繁项目集.3.对于t ∈(L (d )-L (D ))的频繁项目集合,如果t ∈L (d )且t |L (D ),则扫描D 得到t 在D 中的支持度support D ,再根据d 中已经求得的支持度sup 2port d ,利用式(1)求出t 在(D +d )中的支持度sup 2port D+d,如果support D +d >m in_sup,则把t 放入当前事务数据库(D +d )的频繁项目集中,否则t 不属于频繁项目集.1.2 FUP 算法的不足该类算法的不足有:①算法必须耗费大量时间处理规模巨大的候选项目集;②算法需多次重复扫描数据库与候选项目集进行模式匹配,代价很大;③算法对新增项目不敏感[3-4].2 现有算法对新项目集的敏感性 在旧数据集D 的基础上增加新数据集d 后,现有算法在计算各个项目集的支持度时都是以整个交易数据库的总交易数作为基数计算的,即新项目(ne wite m )的支持度为:support ({ne wite m })=新项目出现的次数D +d,因为D>>d ,所以:2008-02-0:1978.新项目出现的次数D+d <<新项目出现的次数d,也就是说有可能新项目虽然在新数据集d中频繁出现且有可能产生新的关联规则,但是在整个交易数据库中却作为非频繁项目集出现,如果采用现有的关联规则挖掘算法,则发现不了新的、潜在的关联规则.3 敏感度为了衡量关联规则挖掘算法对新增项目的敏感性,首先分析新增项目的概念.如果新增加的项目在新的数据集d中的(k-1)项目集仍然为非频繁项目集,那么新增加的项目对发现频繁项目集的结果没有影响,所以只有那些新增加的支持度大于或等于最小支持度的项目是要讨论的对象.定义1[7] 设交易数据库中在旧的数据集D的基础上,增加了新数据集d,若d中的1个项目ne2 witem满足Supportd ({ne wite m})-SupportD({ne wite m})≥ m in_sup则称项目ne w ite m为新项目.其中support D({ne2 witem})为1-项目集{ne wite m}在旧数据集D中的支持度,supportd({ne wite m})为1-项目集{ne2 witem}在新数据集d中的支持度[7].定义2 在关联规则挖掘算法所得到的频繁项目集中,如果{ne wite m}∈L1(D+d),那么就称该关联规则挖掘算法对新项目ne wite m是敏感的,也就是说该关联规则挖掘算法对新项目ne w ite m具有敏感度,否则不具有敏感度,其中,L1(D+d)是整个数据库的频繁1-项目集[8].4 改进算法数据挖掘频繁地访问数据库成为数据挖掘效率的瓶颈,关联规则挖掘情况也是如此.如果每次都对整个数据库运行挖掘算法,那么挖掘的效率会变得非常低.在增加新的数据后,如果充分利用以前挖掘到的知识,可大大提高挖掘的效率.根据实际应用需求,关联规则的更新问题可以分为以下几种情况:①事务数据库不变,最小支持度发生变化时,关联规则的高效更新问题;②最小支持度不变,一个事务数据集d1添加到事务数据库D中去时生成最新事务数据库(D∪d1)中的关联规则的问题;③最小支持度不变,从事务数据库D中删除一个事务数据集(∈D)后高效生成事务数据库(D)中的关联规则的问题这3种情况是关联规则更新问题的基础和核心笔者结合第2种情况提出了一种改进的关联规则增量式更新算法,该算法根据以前发现的频繁项目集和交易数据库中新增的数据动态地更新原来发现的频繁项目集,从空间上来说,可以不需要存储以前的数据集,从而节省了内存,从时间上来说,只考虑原来得到的频繁项目集,不需扫描交易数据库总的数据集,所以发现频繁项目集的时间大大节省,从而提高了整个关联规则挖掘的效率,并且具有很好的合理性.4.1 改进算法的基本思想引入了参数c(1≤c≤∞),在旧数据集中发现频繁项目集的过程中,保留那些支持度大于或等于m in_sup/c的频繁项目集,每次数据库中增加新的数据集时,只考虑以前产生的支持度大于或等于m in_sup/c的频繁项目集和当前增加的数据集.由于数据库的规模在不断增大,而项目的增加却相对稳定,扫描支持度大于或等于m in_sup/c的频繁项目集的时间比扫描整个旧数据集的时间要短,这样就大大提高了发现频繁项目集的效率.假设已经采用Ap ri ori算法获得数据集D的支持度大于或等于m in_sup/c的频繁项目集是L(D),那么在增加新的数据集d后的算法的基本思想:1.根据新数据集d和L(D)得到支持度大于或等于m in_sup/c的频繁项目集L(d),然后把L(d)加入到support D+d≥m in_sup c的频繁项目集L3(D +d)中.对于项目集t,若t∈L(D),则supportt= [count t(D)+c ount t(d)]/[c ount t(D+d)],如果supportt≥m in_sup/c,则把项目集t加入到频繁项目集L3(D+d)中.2.扫描新数据集d,用Ap riori算法计算新数据集d中的支持度大于或等于m in_sup/c的频繁项目集L(d).在这一步骤中support的计算方法为sup2 port t=count t(d)/d.3.对于项目集i,若i∈L(d)且i|L3(D+d),则把i加入到L3(D+d)中.4.利用Ap ri ori算法在得到的支持度大于或等于m in_sup/c的频繁项目集L3(D+d)中找出支持度大于或等于m in_sup的频繁项目集,即L(D+d).在上述过程中,c的取值越大,那么m in_sup/c 就越小,旧数据集中得到的支持度大于或等于m in_ sup/c的频繁项目集就保留得越多,也就是说旧数据集的权重越大;否则反之.特别地,当c=1时,也就是说对增加新数据后的数据集发现频繁项目集的时候,可以完全不考虑旧数据集中支持度小于_的所有项目集26 华 北 水 利 水 电 学 院 学 报 2008年10月d 2d 2-d2..m in sup/c.4.2 改进算法的执行过程和实例41211 执行过程定义函数Ap riori (D ,m in_sup),此函数的作用为:输入参数c(1≤c ≤∞),交易数据库中原有数据集D (旧数据集)和新增加的数据集d (新数据集),支持度阈值m in_sup /c ;输出(D +d )中的频繁项目集L (D +d).用改进的算法描述如下:11Apri ori (D ,m in_sup /c );21Apri ori (D +d ,m in_sup /c );31For each transacti ons t d ∈L (D );41I f t d ∈L (D +d );51support d (t )=support D +d(t);61L (D +d )={t dsupport d (t )≥m in_sup}41212 实 例设最小支持度为0.4,c =2,则m in _sup /c =0.2,为了方便描述,以下把交易数据集按产生时间的先后分为旧数据集D 和新数据集d .执行过程如图1所示.图1 改进的增量式更新算法的执行过程5 改进算法性能分析5.1 改进算法对新项目的敏感性分析在改进的算法中,对于增加新的数据集d 后,如果数据集d 中的项目集在D 中不满足支持度大于或等于m in_sup 的频繁项目集,则以项目集在d 中出现次数/d 作为支持度.显然对于支持度大于或等于m in_sup 的1-项目集有{ne w ite m }∈L 1(D +d ),也就是说改进算法对新项目ne wite m 是敏感的,其中L 1(D +d )是整个数据库的频繁1-项目集.增量式更新算法和改进算法的频繁1-项目集的比较结果见表1.从图中可以看出,在增量式更新算法中,项目集{D }是非频繁项目集,而在改进的算法中{D }是频繁项目集由以上的比较可以知道改进的算法对新项目D 是敏感的,而增量式更新算法对新项目D不敏感.表1 增量式更新算法和改进算法的频繁1-项目集的比较增量式更新算法L (D +d)改进算法L3(D +d )项集支持度计数项集支持度计数A 10/16A 10/16B 11/16B 11/16C7/16C 7/16D4/165.2 改进算法的性能分析为了进一步验证改进算法的性能,在运行W in 2X 的333上实现了改进算法并进行了测试,软件开发环境为V ++在实验数据库中,采用的是密集型数据库和,并且36第29卷第5期侯 兵等: 关联规则挖掘中改进的增量式更新算法 2.dow s P P 7isua l C .m ushroom connect把它们作为数据集(D +d ),D 和d 的记录数的比例是10∶1.具体参数见表2.表2 测试数据集参数数据集事务记录数总项数事务中项最大长度m us hroo m 812412023connec t6755712043 图2和图3为在不同的数据库和不同的支持度下改进算法与经典的F UP 算法挖掘时间的比较.当最小支持度阈值减小时,产生的频繁项目集数量增多;当支持度阈值减小时改进算法的运行时间曲线增长平缓得多,说明其计算性能相对稳定.6 结 语笔者所提出的改进算法能较好地发现数据库新的关联规则,在规则挖掘过程中显示了良好的空间和时间性能,并具有较高的敏感性.参 考 文 献[1]D W Cheng,J Han,V T Ng,et al .M aintenance of discov 2e red a ss ocia ti on rules in la rge da tabase [C ]//An I ncrem en 2tal Updating Techni que [C ]//The 12thInt .conf .on DataEnginee ring,New Orleans,Louisi ana,1996.[2]李天瑞.数据库中的关联规则及挖掘算法研究[D ].成都:西南交通大学,2001.[3]S O lafss on .I ntr oduction t o o pe ra ti ons re s ea rch and datam ining[J ].Co mputers &Operati ons R esearch,2006,33(11):3067-3069.[4]F Be rzal,I B lanco,D S ánchez,et al .A definiti on for fuzzyapproxi ma te dependence s [J ].Fuzzy Sets and System s .2005,149(1):105-129.[5]J Han .Da ta M ining :Concep ts and Technique s[M ].Mo rganKauf m ann Publishers (高等教育出版社,影印版),2001.[6]J TA nthony Lee,W L in,C Wang .M i ning ass oc iati on ruleswit h multi -di mensional constraints[J ].Journal of Syst em s and Soft wa re,2006,79(1):79-92.[7]E Cohen,M Da t a r,S Fuji wa ra,e t al .Findi ng InterestingA ss ociati ons without Support P runing [C ]//In Proc .Int .Conf .on Da t a Engi neering (I CDE 2000),2000:489-499.[8]S Pauray M ,Tsai,Chen C.M ining interesting a ss ocia ti onrules fr om custo me r databa ses and trans ac tion databases [J ].Infor m ati on System s,2004,29(8):685-696.Im pr oved I ncr em en t Up 2to 2da te A lgor ithm i n Assoc i a t i on Rule M i n i ngHOU B ing 1,CHEN W ei 2li 1,L I Xia 2(1.North China Institute of Wa ter Conservancy and Hydroelectri c Po wer,Zheng zhou 450011,Chi na;21Depa rt m ent of Statistics,Henan Uni ve rsit y of Finance and Econo m ics,Zhengzhou 450002,China )Ab stra ct:T he inc rement u p 2t o 2date alg orit hm can make full use of the m i ning kn owledge t o i mprove effic iency .The defic iencies of c las 2sic ass ociati on rule inc rement up 2to 2date a l gorith m F UP a re ana l yzed,and an i mp roved a lg orith m is p r ovided .The new a lg orith m grea tly reduces t he st orage cap ac ity and m ini ng ti me,and i mprove s m i ning efficiency of t he whole ass oc iati on rule .Key wor ds:da ta m i ning ;a ss ociati on rule;a lg orith m46 华 北 水 利 水 电 学 院 学 报 2008年10月。
