数据挖掘算法综述（共8篇）
数据挖掘算法综述 篇1
1 数据挖掘的主要研究内容
数据挖掘的任务是发现隐藏在数据中的模式,可以发现的模式分为两大类:描述型模式和预测型模式[2]。描述型模式是对当前数据中存在的事实做规范描述,刻画当前数据的一般特性;而预测型模式则是以时间为关键参数,对于时间序列型数据,根据其历史和当前的值预测未来的值。
关联模式是反映一个事件和其他事件之间依赖或关联的知识,其目的是为了生成部分数据的概要,寻找数据子集之间关联关系与数据之间的派生关系,即在同一事件中出现的不同项之间的相关性。如果两项或多项属性之间存在关联,那么就可以依据已知的属性值预测某一项的属性值。关联规则的挖掘可分为两步,首先是通过迭代识别所有的频繁项目集,然后再从频繁项目集中构造可信度不低于用户设定的最低值的规则。识别和挖掘所有频繁项目集是关联规则挖掘算法的核心,也是计算量最大的部分[3]。
关联规则中最典型的是购物篮分析,在关联规则的分析中有助于发现交易数据库中不同商品之间的联系,找出顾客购买的行为模式。
分类就是通过构造一个分类函数,把具有某些特征的数据项划分到某个给定的类别上。分类由模型创建和模型使用两步组成,模型创建是指通过对训练数据集的学习来建立分类模型;模型使用是指使用分类模型对测试数据和新的数据进行分类。训练数据集中的数据带有类标号,通过训练集的训练,使得使用分类函数可以把标号未知的数据正确的分类到其相应的标号中[4]。
聚类就是将数据项分组成多个类或簇,类之间的数据差别应尽可能大,类内的数据差别应尽可能小,即为“最小化类间的相似性,最大化类内的相似性”原则。与分类模式不同的是,聚类中要划分的类别是未知的,是一种不依赖于预先定义的类和带类标号的训练数据集的非监督学习,无需背景知识,其中类的数量由系统按照某种性能指标自动确定。聚类分析作为数据挖掘中的一个模块,既可以作为一个单独的工具以发现数据库中数据分布的一些深入的信息,概括出每一类的特点,又可以把注意力放在某一个特定的类上以作进一步的分析,还可以作为数据挖掘算法中其他分析算法的一个预处理步骤。
2 关联分析算法
常用的经典频繁项集挖掘算法有下面几种[5]。
2.1 Apriori算法
在关联分析中经典算法是R.Agrawal等人提出的Apriori算法,这是一种很有影响力的挖掘关联规则频繁项集的算法,探查逐级挖掘Apriori性质:频繁项集的所有非空子集都必须是频繁的。根据频繁k-项集,形成频繁(k+1)-项集候选,并扫描数据库1次,完成第k次迭代(k>1),找出完整的频繁(k+1)-项集Lk+1。
Apriori算法是最早用于解决关联规则问题的算法,也是目前数据挖掘领域里应用最广泛的算法之一。该算法的优点是简单易懂并且能够有效地产生所有关联规则,在频繁项目不多时表现出了明显优势;但是,当最小支持度低时,该算法会生成大量的候选频繁项集,可能会遇到组合爆炸的问题,另外,在判定每个候选项集支持度的时候,Apriori算法需要反复多次的遍历事务数据库,导致系统的输入输出代价过高。
2.2 Apriori-Tid算法
为了提高Apriori算法的有效性,目前已经提出了许多Apriori变形,旨在提高原算法的效率,Apriori-Tid算法就是一种Apriori变形算法。
Apriori-Tid算法仅在第1次扫描时用事务数据库D计算候选频繁项集的支持度,其它各次扫描用其上一次扫描生成的候选事务数据库D'来计算候选频繁项集的支持度。该做法可以减少对数据库的扫描次数,在一定情况下能迅速削减候选频繁项集。虽然Apriori-Tid算法进行了改进,但是仍然无法克服Apriori算法的固有缺陷,仍然存在下面的问题:可能产生大量的候选集;可能需要重复扫描数据库,通过模式匹配检查一个很大的候选集;无法对稀有信息进行分析。
3 分类算法
常用的分类算法有下面的几种[6]。
3.1 决策树方法
决策树是一种以实例为基础的归纳学习算法,在其树型结构中,每个结点表示对一个属性值的测试,其分支表示测试的结果,而树的叶结点表示类别,从决策树的根结点到叶结点的一条路径对应着一条合取规则,整个决策树对应着一组析取表达式规则。
决策树算法中最著名的是ID3和C4.5两个算法。ID3算法用信息论的知识作为基础,来计算具有最大信息增益的属性字段,然后建立一个决策树结点,再根据该属性字段的不同取值来建立分支。该方法描述简单且分类速度快,但是只对较小的数据集有效,而且抗噪性差。C4.5算法在继承ID3算法的优点的基础上对其进行了改进,用信息增益率代替信息增益来选择属性,同时在树的构造过程中对树进行剪枝避免了过拟合问题,还能够处理属性值缺少的样本,提高了抗噪能力。C4.5算法产生的分类规则仍然易于理解,准确率较高,但是在构造树的过程中,对数据集进行多次的顺序扫描和排序,导致算法的效率降低,而且C4.5仍然不适合大训练集数据。
3.2 人工神经网络
人工神经网络是多个神经元按一定规则连接构成的网络系统,通过模拟人类大脑的结构和功能完成对外部输入信息的动态响应,并将获取的知识存储在网络单元之间的连接权系数中,使网络具有很强的容错性和鲁棒性。
反向传播算法是人工神经网络中采用最多的训练方法。该算法通过对训练样本集的学习,将每次的处理结果与该样本已知类别进行比较,用所得的误差帮助完成学习,并且对每个训练样本动态的修改权值从而让网络的输出值与实际的类别的均方差最小。
神经网络的优点就是并行分布处理能力强,分类的准确度高,对噪声数据有较强的鲁棒性和容错能力,具备联想记忆的功能等。但是该方法获取的模式隐含在网络结构中,导致分类结果较难理解,网络的训练时间较长,不适于大数据量的学习。
3.3 贝叶斯分类
贝叶斯分类以统计学中的贝叶斯定理为理论基础,通过贝叶斯定理得到的后验概率来预测类成员关系的可能性,是一种具有最小错误率的概率分类方法。在计算过程中,如果假设所有变量都是条件独立的,则可以使用朴素贝叶斯分类方法,但所有变量都是条件独立的情况非常少。贝叶斯网络可以综合先验信息和样本信息,减少了定义全联合概率分布的概率数目,又避免了朴素贝叶斯分类器要求所有变量都是条件独立的不足,成为近年的主要研究方向。
4 结束语
数据挖掘是当今计算机学领域研究的一个主要热门课题,在各个领域都有广泛的应用,数据挖掘的算法对数据挖掘技术的实现起到关键的作用,也直接影响到能否把数据挖掘应用到具体的实践中。本文综合研究了数据挖掘的各种算法的优劣,为算法的改进和创新提供了基础。
参考文献
[1]王光宏,蒋平.数据挖掘综述[J].上海.同济大学学报,2004,32(2):246-252.
[2]Fayyad U.Knowledge Discovery and Data Mining towards a U-inifying Framework.KDD'96Proc.2nd Intl.Conf.on Knowled-ge Discovery&Data Mining,1996.
[3]邹志文,朱金伟.数据挖掘算法研究与综述[J].北京.计算机工程与设计,2005,26(9):2304-2307.
[4]韩家炜.数据挖掘:概念与技术[M].北京:机械工业出版社,2001.
[5]R.Agrawal,T.Imielinski,A.N.Swamy.Mining association rules between sets of items in large databases[A].Proceedings of1993ACM SIGMOD International Conference on Managem-ent of Data,Washington D.C.USA,1993:207-216.
[6]胡可云.数据挖掘理论与应用[M].北京:清华大学出版社,2008.
聚类算法研究综述 篇2
关键词：数据挖掘；聚类分析；聚类算法
中图分类号：TP301. 6 文献标识码：A文章编号：1009-3044(2007)12-21500-02
The Research of Clustering Algorithms
XIANG Bing-bing1, QIAN Guang-chao2
(1.School of Mathematics and Computational Science, Anhui University, Hefei, Anhui Province 230039, China；2. School of Computer Science and Technology ,Anhui University, Hefei, Anhui Province 230039, China)
Abstract：Clustering is an important technique in data mining. It’s used to discover the data distribution and concealed patterns. The paper elucidate the basic principle of the clustering algorithms and sum up the contemporary research of the clustering algorithms. It also analyze a few representative clustering algorithms and compare their differences，advantages and disadvantages. At last，the paper indicate the development trend of clustering integrating the application demand.
Key word:Data mining； Clustering Analysis；Clustering Algorithms
1 引言
数据挖掘是指从从大量无序的数据中提取隐含的、有效的、可理解的、对决策有潜在价值的知识和规则，为用户提供问题求解层次的决策支持能力。数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神經网络算法等等。聚类算法是一种有效的非监督机器学习算法，是数据挖掘中的一个非常重要的研究课题。当人们使用数据挖掘工具对数据中的模型和关系进行辨识的时候，通常第一个步骤就是聚类，其目的就是将集中的数据人为地划分成若干类, 使簇内相似度尽可能大、簇间相似度尽可能小，以揭示这些数据分布的真实情况。但任何聚类算法都对数据集本身有一定的预先假设，根据文献[1]的理论，如果数据集本身的分布并不符合预先的假设，则算法的结果将毫无意义。因此，面对特定的应用问题，如何选择合适的聚类算法是聚类分析研究中的一个重要课题。本文比较了数据挖掘中现有聚类算法的性能，分析了它们各自的优缺点，并指出了其今后的发展趋势。
2 聚类算法分类研究
聚类的目的是把大量数据点的集合分成若干类，使得每个类中的数据之间最大程度地相似，而不同类中的数据最大程度地不同。通常聚类算法可以分为层次聚类、分割聚类、密度型聚类、网格型聚类和其他聚类等几种。
2.1 层次聚类
层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类，它又可以分为两类，即自底向上的聚合层次聚类和自顶向下的分裂层次聚类。聚结型算法采用自底向上的策略， 首先把每个对象单独作为一个聚类， 然后根据一定的规则合并成为越来越大的聚类， 直到最后所有的对象都归入到一个聚类中。大多数层次聚类算法都属于聚结型算法， 它们之间的区别在于类间相似度的定义不同。与聚结型算法相反， 分裂型算法采用自顶向下的方法，它先将所有的对象都看成一个聚类，然后将其不断分解直至每个对象都独自归入一个聚类。一般情况下不使用分裂型方法， 因为在较高的层次很难进行正确的拆分。纯粹的层次聚类算法的缺点在于一旦进行合并或分裂之后， 就无法再进行调整。现在的一些研究侧重于层次聚类算法与循环的重新分配方法的结合。
主要的层次聚类算法有BIRCH， CURE， ROCK， CHAMELEON， AMOEBA，COBWEB， Clustering with Random Walks 算法等。CURE算法[2]不用单个中心或对象来代表一个聚类，而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类，这样就可以识别具有复杂形状和不同大小的聚类，从而能很好地过滤孤立点。ROCK算法[3]是对CURE的改进，除了具有CURE算法的一些优良特性之外，它还适用于类别属性的数据。CHAMELEON算法[4]是Karypis等人于1999年提出来的，它在聚合聚类的过程中利用了动态建模的技术。
2.2 分割聚类
分割聚类算法是另外一种重要的聚类方法。它先将数据点集分为k个划分，每个划分作为一个聚类，然后从这k个初始划分开始，通过重复的控制策略，使某个准则最优化，而每个聚类由其质心来代表( k- means 算法) ， 或者由该聚类中最靠近中心的一个对象来代表( k- medoids 算法)，以达到最终的结果。分割聚类算法收敛速度快，缺点在于它倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k 可以合理地估计， 并且初始中心的选择和噪声会对聚类结果产生很大影响。这类方法又可分为基于密度的聚类、基于网格的聚类等。
很多算法中都使用距离来描述数据之间的相似性，但是，对于非凸数据集，只用距离来描述是不够的。对于这种情况，要用密度来取代相似性，这就是基于密度的聚类算法。基于密度的算法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可以发现任意形状的类。此类算法除了可以发现任意形状的类，还能够有效去除噪声。
基于网格的聚类算法，把空间量化为有限个单元( 即长方体或超长方体) ，然后对量化后的空间进行聚类。此类算法具有很快的处理速度。缺点是只能发现边界是水平或垂直的聚类，而不能检测到斜边界。此类算法具有很快的处理速度。时间复杂度一般由网格单元的数目决定， 而与数据集的大小无关。此外，聚类的精度取决于网格单元的大小。此类算法不适用于高维情况，因为网格单元的数目随着维数的增加而呈指数增长。所有基于网格的聚类算法都存在下列问题：一是如何选择合适的单元大小和数目；二是怎样对每个单元中对象的信息进行汇总。
主要的分割聚类算法有k - means， EM， k - medoids， CLARA， CLARANS 等。常见的k -medoids 算法有PAM算法、CLARA 算法、CLARANS 算法。
2.3 其他聚类
主要有：基于约束的聚类算法、机器学习中的聚类算法、用于高维数据的聚类算法等。
基于约束的聚类算法，其约束可以是对个体对象的约束，也可以是对聚类参数的约束，它们均来自相关领域的经验知识。该方法的一个重要应用在于对存在障碍数据的二维空间数据进行聚类。COD (Clustering with Obstructed Distance) [ 5]就是处理这类问题的典型算法，其主要思想是用两点之间的障碍距离取代了一般的欧氏距离来计算其间的最小距离。
机器学习中的聚类算法是指与机器学习相关、采用了某些机器学习理论的聚类方法，它主要包括人工神经网络方法以及基于进化理论的方法。如自组织特征映射( SOM) 网络是利用人工神经网络进行聚类的较早尝试，它也是向量量化方法的典型代表之一。在基于进化理论的聚类方法中，模拟退火的应用较为广泛， SNICC算法[ 6 ]就是其中之一。遗传算法也可以用于聚类处理，它主要通过选择、交叉和变异这三种遗传算子的运算以不断优化可选方案从而得到最终的聚类结果。
高维数据聚类是目前多媒体数据挖掘领域面临的重大挑战之一，除了降维这一最直接的方法之外，对高维数据的聚类处理还包括子空间聚类以及联合聚类技术等。子空间聚类算法，认为在高维数据集中，聚类往往不是存在于整个空间中，而是存在于某些子空间中。它们针对高维空间数据，寻找子空间中的聚类。主要子空间聚類算法有CLIQUE，PROCLUS 等。
3 典型聚类算法性能比较
3.1 CLARANS 算法
CLARANS通过利用多次不同抽样改进了CLARA算法，是一种k-中心点聚类方法。它首先随机选择一个点作为当前点，然后随机检查它周围不超过参数Maxeighbar个的一些邻接点。假如找到一个比它更好的邻接点，则把它移入该邻接点，否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须预先调入内存，并且需多次扫描数据集，其时空复杂度都相当大，虽通过引入R*—树结构对其性能进行改善，但构造和维护代价太大。该算法对脏数据和异常数据不敏感，但对数据输入顺序异常敏感，且只能处理凸形或球形边界聚类，效率较高。
3.2 BIRCH 算法
BIRCH是一个综合性的层次聚类方法，它利用层次方法的平衡迭代进行归约和聚类。其核心是用一个聚类特征三元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法具有对象数目的线性易伸缩性，及良好的聚类质量。一次扫描就可以进行较好的聚类，其计算复杂度为O( n)。BIRCH 算法只适用于类的分布呈凸形及球形的情况，对不可视的高维数据则是不可行的。
3.3 DBSCAN 算法
DBSCAN是基于密度的聚类算法，可以将足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是：对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目。DBSCAN算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时，就必须有大量内存支持，I/O 消耗也非常大。其时间复杂度为O(nlogn)，聚类过程的大部分时间用在区域查询操作上。DBSCAN算法能够发现空间数据库中任意形状的密度连通集；在给定合适的参数条件下，能很好地处理噪声点；对用户领域知识要求较少；对数据的输入顺序不太敏感；适用于大型数据库。但DBSCAN算法要求事先指定领域和阈值，具体使用的参数依赖于应用的目的。
3.4 STING 算法
STING 是一种格的多分辨率聚类技术。它将空间区域划分为矩形单元，针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。STING扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O (n) ，其中n是对象的数目。在层次结构建立后，查询处理时间是O ( g)，g是最低层风格单元的数目，通常远远小于n。
STING 是独立于查询的，有利于并行处理和增量更新且效率较高。但由于STING 采用了一个多分辨率的方法来进行聚类分析，聚类的质量取决于网格结构的最低层粒度。如果数据粒度比较细，处理的代价会明显增加。并且，STING 在构建一个父单元时没有考虑子单元和其相邻单元之间的关系，因此，尽管该技术处理速度快，但可能降低簇的质量和精确性。
4 结论和展望
聚类分析是数据挖掘中一种非常有用的技术，它可作为特征和分类算法的预处理步骤，也可将聚类结果用于进一步关联分析，还可以作为一个独立的工具来获得数据分布的情况。聚类算法的研究具有广泛的应用前景，其今后的发展也面临着越来越多的挑战。首先是聚类算法的选择，建议使用者根据实际情况(例如发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率)来选择合适的聚类算法。其次，对于特征数据本身所具备的高维性、复杂性、动态性以及容易达到大规模的特性，聚类算法的设计还应该更多地考虑融合不同的聚类思想形成新的聚类算法，从而综合利用不同聚类算法的优点。
参考文献：
[1]R O Duda，P E Hart，D G Stork. Pattern Classification ( 2nd Edition) [M]. New York: Wiley， 2001. 4542458.
[2]Guha S， Rastogi R，Shim K. CURE: An Efficient Clustering Algorithm for Large Databases[C]. Seattle: Proceedings of the ACM SIGMOD Conference，1998. 73-84.
[3]Guha S，Rastogi R，Shim K. ROCK: A Robust Clustering Algorithm for Categorical Attributes[C]. Sydney: Proceedings of the 15 th ICDE，1999. 512-521.
[4]Karypis G，Han E-H，Kumar V. CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling[J]. IEEE Computer，1999，32 (8) : 68-75.
[5]Tung A K H，Hou J，Han J. Spatial Clustering in the Presence of Obstacles[C]. Heidelberg: Proceedings of the 17 th ICDE，2001. 359-367.
数据挖掘中聚类算法综述 篇3
将物理或抽象对象的集合分组成为有类似的对象组成的多个类的过程被称为聚类[1]。由聚类所形成的这些簇是一组数据对象的集合, 处在同一个簇中的对象之间具有着较高的相似性, 不同簇中的对象则相异。在许多应该用中, 可以将一个簇中的对象当成是一个整体来对待。
现有的聚类技术大致可以分为如下几类:划分方法 (partitioning method) , 层次方法 (hierachical method) , 基于密度的方法 (density-based method) , 基于网格的方法 (grid-based method) 和基于模型的方法 (model-based method) 。论文将介绍聚类分析的基本概念、聚类算法的典型要求以及各类聚类技术中的典型算法。
2、聚类分析的基本概念
2.1 聚类的定义
聚类可以定义如下[2]:在数据空间A中, 数据集X由许多数据点 (或数据对象) 组成, 数据点xi= (xi1, …, xid) ∈A, xi的每个属性 (或特征、或维度) xij既可以是数值型, 也可以是枚举型。数据集X相当于是以这N×d矩阵。假设数据集X中有N个对象xi (i=1, …, N) 。聚类的最终目的就是把数据集X划分为k个分割Cm (m=1, …, k) , 也有可能有些对象不属于任何一个分割, 这些对象就是噪声Cn。所有这些分割的并集就是数据集X, 并且这些分割之间没有交集, 即
这些Cm就是聚类。
2.2 评价聚类算法的几个标准
聚类分析是数据挖掘中一个重要的技术, 它的潜在应用提出了各自特殊的要求。一般来说, 一个好的聚类算法应当满足:
1.可伸缩性:聚类算法应该适合处理不同规模的数据集;2.处理不同类型属性的能力:现有的大量算法都针对单一类型的数据, 对于混合型数据的处理方法仍旧是一个重要的方向。3.发现任意形状的簇:基于距离的相似性度量手段往往只能发现球状聚类, 因此提出能发现数据集中任意形状的簇也是衡量聚类算法的一个重要标准。4.用于决定输入参数的领域知识最小化:数据挖掘在实际应用中往往与专业相联系, 输入参数的确定一直是个难题。一个好的算法的参数要尽可能与领域知识无关。5.处理噪声数据的能力:绝大多数真实世界中的数据集都包含孤立点、缺失值甚至错误的数据。包括k-平均在内的许多算法都对噪声数据较为敏感, 在这类数据上可能产生较低质量的聚类结果。6.对于输入对象的顺序不敏感:有些算法对不的数据输入顺序可能产生不同的结果, 使得算法具有较差的稳定性, 研究对于输入数据对象的顺序不敏感的聚类算法具有重要的意义。7.高维性:现有的许多聚类算法擅长处理低维的数据, 由于高维特征空间中数据固有的稀疏性, 传统的距离度量方式逐渐失效, 这给聚类算法在很大程度上带来了困难。开发针对高维数据集的聚类算法是很有必要的。8.基于约束的聚类:现实世界中的应用可能需要在各种约束条件下进行聚类, 要找到即满足给定约束条件, 又具有良好聚类结果的数据分组是一项具有挑战性的任务。9.可解释性和可用性:数据挖掘的目标是找到可解释的、可理解的和可用的模式。因此, 需要给聚类结果以特定的语义解释, 以便和具体的应用相联系。
3、主要聚类算法
目前在文献中存在大量的聚类算法。算法的选择由数据类型、聚类目的和应用决定。在本节中, 我们将介绍每一类聚类方法及它们的代表算法。
3.1 划分方法
给定一个含有n个对象的数据集, 以及要生成的簇的数目k。划分方法的任务就是首先将数据构建成k个划分, 然后采用一种迭代的重定位技术, 将对象在不同的划分间移动, 直至满足一定的准则, 一个好的划分的一般准则是:在同一个簇的对象尽可能"相似", 不同簇中的对象则"相异"。在划分方法中, 最经典的就是k-平均[3]和k-中心算法。很多算法都是由这两个算法改进而来的。
k平均算法只有在平均值被定义的情况下才能使用, 因此算法容易受到孤立点的影响, k中心算采用簇中最中心的位置作为代表点而不是采用对象的平均值。因此, 与k平均算法相比, 当存在噪声和孤立点数据时, k-中心算法要较k-平均健壮, k-中心没有k-平均算法那样容易受到极端数据的影响。在时间复杂度上, k-平均算法的时间复杂度为O (nkt) , 而k-中心的大约为O (n2) , 后者的执行代价要高得多。此外, 这两种方法都要求用户指定聚类数目k。
3.2 基于层次的方法
一个层次的聚类方法对给定的数据对象集合进行层次的分解, 将数据对象组成一棵聚类树。根据层次的分解自底向上还是自顶向下, 层次的方法可以分为凝聚的和分裂的[4]。凝聚的方法也称为自底向上的方法, 开始时每个对象都被看成是一个单独的一个簇, 然后逐步的合并相近的对象或簇形成越来越大的簇, 直到所有的对象都在一个簇中, 或者达到某个终止条件。分裂的方法, 也称为自顶向下的方法, 它与凝聚层次聚类恰好相反, 初始时将所有的对象置于一个簇中, 然后逐渐细分为更小的簇, 直到最终每个对象都在单独的一个簇中, 或者达到某个终止条件。无论是凝聚的方法还是分裂的方法, 在一个合并或分裂动作被执行后, 就不能被改变, 这样有可能会影响聚类的质量。
层次聚类算法因实现简单而广受欢迎, 但是在实际操作中经常会遇到合并或分裂点选择的问题。由于分裂和合并操作是不可逆的, 下一步的处理都是在新的生成簇上进行的, 所以选择这些分裂或合并点是非常关键的。在层次聚类中, 任何已作的处理都不能被撤销, 簇之间的对象也是不能交换的。任一步的处理如不得当, 都会可能导致聚类质量的降低。此外, 这类算法在合并、分裂的时候要检测和估算大量的对象和簇, 因而伸缩性较差。为了改进层次聚类算法的聚类质量, 新的研究从层次聚类与其他聚类技术结合入手, 形成多阶段的聚类。比较常见的方法有四种:BIRCH、CURE、ROCK和Chameleon[5]。
3.3 基于密度的方法
从目前已有的大量文献来看, 绝大多数的划分聚类方法在进行聚类的时候都是以距离作为相似性的度量的手段。通常情况下这样的方法只适用于发现球状聚类, 对发现任意形状的聚类则显得不足。随之久提出了基于密度的另一类聚类方法。这类方法从对象分布区域的密度着手, 对于给定类中的数据点, 如果在给定范围的区域中, 对象或数据点的密度超过某一阈值就继续聚类。这样通过连接密度较大区域, 就能形成不同形状的聚类, 而且还可以消除孤立点和噪声对聚类质量的影响。自这类算法中, 最具代表性的是DBSCAN算法、OPTICS算法和DEN-CLUE[6]算法。
这种聚类算法能够在带有"噪声"的信息系统中发现任何形状的聚类, 并且具有对数据输入顺序不敏感的优点。
基于密度的聚类涉及到的一系列定义。我们先对这些定义进行说明:
·ε-邻域:给定对象半径ε内的区域称为该对象的ε-邻域。
·核心对象:如果一个对象的ε-邻域至少包含最小数目Min Pts个对象, 则称该对象为核心对象。
·直接密度可达:给定一个对象集合D, 如果p是在q的ε-邻域内, 而q是一个核心对象, 我们说对象p从对象q出发是直接密度可达的。
·密度可达:如果存在一个对象链pl, p2, …, pn, p1=q, pn=p, 对pi∈D, (1≤i≤n) , pi+1是从pi关于ε和Min Pts密度可达的, 则对象p是从对象q关于ε和Min Pts密度可达的。
·密度相连:如果对象集合D中存在一个对象O。, 使得对象p和q是从O关于ε和Min Pts密度可达的, 那么对象p和q是关于ε和Min Pts密度相连的。
密度可达是直接密度可达的传递闭包, 是可传递的, 但不满足对称性, 只有核心对象之间才是密度可达的。一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合, 不包含在任何簇中的对象被认为是噪声点。
3.4 基于网格的方法
基于网格的聚类方法将数据空间划成有限数量的单个单元格, 这些单元格组成了一个网格结构。所有的聚类操作都在这个网格结构上进行。这类方法的主要优点就是它的处理速度很快, 其处理时间独立于数据对象的数目, 仅依赖于量化空间中每一维的单元数目;聚类的精度取决于单元格的大小。这类算法也有着其缺点, 它只能发现边界是水平或垂直的簇, 而不能检测到斜边界。此外, 在处理高维数据时, 网格单元的数目会随着属性维数的增长而成指数增长。
一般来说, 所有基于网格的聚类算法几乎都存在下列问题: (1) 是如何选择合适的单元大小和数目, 单元数目太少时, 精度就会很低, 而单元数目太多时算法的复杂度就会变大; (2) 是如何对每个单元中对象的信息进行汇总。
常见的基于网格的方法有:STING, 它利用存储在网格单元中的统计信息;Wave Cluster[7], 它用一种小波变换的方法来聚类;CLIQUE, 它是在高维数据空间中基于网格和密度的聚类方法。
3.5 基于模型的方法
基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。该方法为每个簇都假定一个模型, 然后寻找数据对给定模型的最佳拟合。这样的方法都是假定数据是根据潜在的概率分布生成的。在这类算法中, 聚类的数目也根据统计数字自动决定, 噪声和孤立点也是通过统计数字来分析。基于模型的聚类方法主要有两类:统计学方法和神经网络方法。
2.5.1统计学方法
从统计学的观点看, 聚类分析是通过数据建模简化数据的一种方法。概念聚类就是其中的一种, 概念聚类的绝大多数方法都采用了统计学的途径, 在决定概念或聚类时, 使用概率度量。它将数据分成多组, 对一组未标记的数据对象产生一个分类模式, 并对每个分类模式给出其特征描述, 即每组对象代表了一个概念或类。在这里, 聚类质量不再只是单个对象的函数, 而是加入了如导出的概念描述的简单性和一般性等因素。
COBWEB是一种典型的简单增量概念聚类[8]算法, 它用分类属性-值对这一结构来描述输入的对象, 以一个分类树的形式创建层次聚类。与判定树不同, 分类树种的每个节点都对应一个概念, 包含该概念的一个概率描述, 概述被分在该节点下的对象。概率描述包括概念的概率和形如P (Ai=Vij|Ck) 的条件概率, 这里Ai=Vij是属性值-对, Ck是概念类。在分类树的某个层次上的兄弟节点形成了一个划分。为了用分类树对一个对象进行分类, 采用了一个部分匹配函数来沿着最佳匹配点的路径在树中向下移动。
2.5.2神经网络方法
神经网络以其分布式存储、并行协同处理以及自学习等特性被用于聚类分析领域。神经网络方法将每个簇都描述为一个标本, 标本作为聚类的原型不一定对应一个特定的数据实例或对象。在进行聚类时, 新的对象通过与标本的比较而被分配到到最相似的簇, 簇中的对象的属性可以根据标本的属性来预测。在聚类分析中经常被用到的神经网络的方法有三个:Kohonen自组织神经网络[9]、竞争神经网络以及自组织共振神经网络等。这些法都涉及有竞争的神经单元。
竞争学习 (Competitive learning) 采用了若干个单元的层次结构, 它们以一种"胜者全取"的方式对系统当前处理的对象进行竞争。在一个簇中获胜的单元成为活跃的, 而其他单元是不活跃的。各层之间的连接是激发式的, 即在某个给定层次中的单元可以接收来自低一层次所有单元的输入。在一层中活动单元的布局代表了高一层的输入模式。在某个给定层次中, 一个簇中的单元彼此竞争, 对低一层的输出模式做出反应。一个层次内的联系式抑制式的, 以便在任何簇中只有一个单元是活跃的。获胜的单元修正它与簇中其他单元连接上的权重, 以便未来它能够对与当前对象相似或一样的对象做出较强的反应。如果我们将权重看作定义的一个标本, 那么新的对象被分配给具有最近标本的簇。结果簇的数目和每个簇中单元的数目是输入参数。
在聚类过程结束时, 每个簇可以被看作一个新的"特征", 它检测对象的某些规律性。这样产生的结果簇可以被看作一个底层特征向高层特征的映射。神经网络聚类方法与实际的大脑处理有很强的理论联系。由于较长的处理时间和数据的复杂性, 需要进行进一步的研究来使它适用于大型数据库。
4、总结与展望
将指定的数据集分成不同的簇, 簇内的对象彼此相似, 簇间的对象相异的过程就称为聚类。它属于一种无指导的学习, 即没有预先指定类别。聚类的质量是由相异度来评估的, 相似度是根据描述对象的属性值来计算的, 通常是采用距离来度量的。聚类分析来源于很多研究领域, 包括数据挖掘, 统计学, 生物学, 以及机器学习等。其应用也是相当广泛, 如市场或客户分割, 模式识别, 生物学研究, 空间数据分析, Web文档分类。它可以被当成是单独的数据挖掘工具, 也常常作为其它数据处理方法的数据预处理工具。
从已有的大量文献来看, 数据挖掘中的相关算法主要是基于数字数据或者文本数据。在实际应用中的数据既包含数字数据也包含文本数据, 是混合数据。虽然提取的数据经过相关处理后可以将数字数据和文本数据归并到一类, 但是在处理精度上会受到影响。因此研究能有效处理混合型数据的算法是一个极其重要的方向。传统方法往往采用单一的算法对数据进行处理, 基于一种算法的数据处理虽然其算法复杂度相对较低, 但最大的缺陷就是数据处理精度无法得到更精确的保证[27], 研究多个算法的融合技术也是有着很重要的意义。
摘要：聚类分析是一种基本的数据分析方法, 它在数据挖掘, 统计学, 空间数据库技术, 人工智能, 生物学研究, 机器学习, 模式识别等领域都得到了广泛的应用。论文总结了各类聚类算法的研究现状, 分析它们的优缺点, 并指出了其发展趋势。
关键词：数据挖掘,聚类方法,数据处理
参考文献
[1].Jiawei Han, Micheline Kamber.Data Mining Concepts and Techniques[M].beiing:China Machine Press, 2001:223
[2].杨小兵.聚类分析中若干关键技术的研究[D].杭州:浙江大学, 2005.
[3].JainA K, DubesR C.Algorithm for clustering data[M].Prentice-Hall, 1988
[4].W.H.E Day and H.Edelsbrunner.Efficient algorithms for agglomerativehierarchical clustering methods[J].J.Classification, 1984, 1:7-24
[5].GeorgeK, HanEui Hong, VIPinK.Chameleon:Hierarchicalclusteringusin-ynamiemodeling[J].ComPuter, 1999, 32 (8) :68-75.
[6].A.H inneburg and D.A.Keim.An efficient approach to clustering inlarge multimedia databases with noise[C].In Porc.1998 Int.Conf.Knowl-edge Discovery and Data Mining (KDD'98) , New York, NY, 1998:58-65
[7].G.Sheikholeslami, S.Chatterjee, and A.Zhang.WaeCluster:A multi-resolution clustering approach for very large spatial databases[C].In Proc.1998 Int.Conf.Very Large Databases (VLDB'98) , New York, 1998:428-439
[8].J.W.Shavlik and T.G.Dietterich.Readings in Machine Learning[Z].Morgan Kaufmann, 1990.
[9].Kohonen T.Self-OrganizingMaps[M].Springer Series in InformationSciences, 2001.30.
数据挖掘算法综述 篇4
本文主要着重于数据分类分析的训练阶段,同时根据目前数据分类技术的情况,可以把数据分类技术分为决策树类、Bayes类、基于关联规则类以及利用数据库技术类等几类算法进行叙述。
1 决策树分类算法
在决策树分类算法中比较典型,提出时间也比较早的非C4.5算法莫属,但是随着计算机技术和信息技术的发展,C4.5算法已经满足不了越来越复杂的数据分类算法,因此为是适应大规模数据集的处理,C4.5在发展过程中又不断演变,在发展过程中又出现了多种基于C4.5算法的新技术,其中比较常用也比较典型的有SPRINT和SLIQ算法。
1.1 C4.5算法
1.1.1算法简介
由于C4.5算法比较抽象,为了简洁明了的对C4.5算法进行准确的描述,本文以集合为载体对C4.5算法进行描述。我们假设一个全集T,在对T构造决策树时,根据Information Gain值选择作为分裂结点的属性及标准,可以把集合T分成n个子集。并规定Ti表示集合T的第i个子集,若子集内的元素具有某一相同的特性,则该结点就成为决策树的叶子结点而停止分裂。对于剩下的子集,重复上述步骤,直至所有的元素都被集合在相应的类别中。
1.1.2算法分析
相比传统的数据分类算法如统计方法、神经网络方法相比较,决策树分类算法有许多明显的优点。比如,决策树分类算法的数据分类规则简单明了,比较容易理解,在实际操作中不易出错。
尽管决策树数据分类算法有着诸多优点,但是决策树数据分类算法也有诸多缺点。由于决策树对数据的分析过程决定了,在数据分类过程中,特别是在构造树的过程中,不可避免的需要对数据进行多次顺序扫描和排序,这势必会导致整个数据分析过程变得缓慢。同时由于C4.5的特点,使得C4.5算法的适用范围也有限,只适合于能够驻留于内存的数据集使用,当训练集大得无法在内存容纳时程序无法运行。
1.2 SLIQ沿算法
所谓的SLIQ算法实际是基于C4.5算法演变而来,对C4.5算法进行了多处改进,同时在数据分类分析过程中采用了预排序和广度优先两种技术。接下来,下文将对预排序技术和广度优先技术进行简单的介绍。
1.2.1算法描述
(1)预排序
在前文中讲到,在进行大量数据分类分析时,需要对每一个数据的特性进行分析,并按照相应的规则对每个数据分析,由于数据量比较大,使得数据的分析排序过程比较慢,造成了数据分类过程效率低下,为了解决上述问题,便引入了预排序的技术,以便能够消除在决策树的每个结点对数据集进行排序的需要。所谓预排序,就是以数据的共同特点为依据,从而快速对数据进行排序。
(2)广度优先策略
由于C4.5算法的特点,决策树的结构是按照深度优先策略完成的,所以在数据分类分析过程中必须对每一个关键节点进行分析,效率极其低下。但是采用广度优先策略技术之后,仅仅需要对每一层只需对每个属性列表扫描一次,就可以为当前决策树中每个叶子结点找到最优分裂标准。
(3)SLIQ算法分析
SLIQ算法基于C4.5算法技术在很多方面进行了完善,并且也采用了与排序技术和广度优先策略技术,使得SLIQ算法技术在一定程度上具有良好的记录个数和属性个数增长的可扩展性。但是在实际数据分类过程中,仍然存在下述问题需要解决:又在数据分析过程中,数据全部暂时存放于内存中,与此同时数据特性列表的长度和数据训练集的长度一样,上述情况使得SLIQ算法实际可以处理数据集的大小收到了一定程度上的限制。同时由于采用了预排序技术,使得SLIQ算法不可能达到随记录数目增长的线性可扩展性。
1.3 SPRINT算法
正如前文所讲,又在SLIQ算法中,所有的数据都储存在内存中,使得SLIQ算法处理数据集的大小有限,为了解决上述问题,SPRINT算法便应运而生。为了尽可能的避免大量需要处理的数据存储在内存中,SPRINT算法对决策树算法的数据分析结构做出了相应的改变,特别是删除了SLIQ算法中需要存储在内存中的数据类别列表,取而代之的是把数据类列表融合到每个数据数的属性列表中,采用这种方法的好处是,在进行大量数据分析时,在遍历每个属性列表寻找当前结点的最优分裂标准时,可以避免反复的数据分析。数据的相关属性分别存放属于各个结点的记录,使得数据的分类分析变得比较简单。但是SPRIT算法也不是万能的,其使用范围受到了限制,对于非分裂属性的属性列表进行分裂就显得不适用,使得这种算法的拓展性不够强。
2 Bayes分类算法
Bayes分类算法是目前数据分类算法中比较重要的一类数据分类算法,与概率统计学知识有着密不可分的关系,由于贝叶斯定理的特点,使得该算法在对数据的特性进行分析的过程中,需要做出相应的假设性前提,而在实际的数据分类分析过程中,这种前提性假设往往过于理想化,在实际情况中并不成立,使得数据分类准确性就会下降。基于上述原因,TAN算法便应运而生。
2.1 TAN算法
TAN算法的提出是为了降低NB中任意属性之间独立的假设。TAB算法在NB网络结构中的结构示意图如1所示。
上述示意图中的每一个顶点代表一个随机变量,每一边表示每个随机变量之间特有的关系。其中虚线表示NB所需的边,而实线代表是新增的边。
3 基于关联规则的分类算法
3.1 CBA 算法描述
所谓的CBA分类数据算法与关联规则密不可为,通常而言,在该种算法中同样需要数据构造分类器,在构造CBA算法中的数据构造器是需要如下两个步骤,首先发现所有的右部为类别的类别关联规则,通常称为CAR。其次是从第一个步骤中的CAR中,选择合适的数据集。
3.2算法分析
在CBA算法中主要用到的是Apriori算法技术,通过Apriori算法技术可以使不易发现的数据关联规则显现出来。通常而言,为了确保该算法在对数据进行分类时不发生漏缺情况,需要把最小支持度取值为0,但是这样又使得该算法不能充分发挥其优化作用,最终使得该算法运行效率低下。
4 基于数据库技术的分类算法
基于数据库技术的分类算法是数据分类算法技术的发展方向,该算法首先是由研究数据库的人员发现并提出的,虽然基于数据库技术的分类算法已经出现很长时间,但是在实际数据分类算法的应用中,并没有用到与数据库相关的技术。之所以出现上述问题是由于数据挖掘应用很难与数据库系统集成,为了解决上述问题, MIND和GAC-RDB算法应运而生。
4.1 MIND 算法
4.1.1算法描述
MIND算法在构造数据分类器时与决策树算法相似,数据分析的过程也与SLIQ有相同之处。但是MIND在数据分类算法中采用了与数据库相关的UDF方法和SQL语句。
4.1.2算法分析
决策树分类算法在分析数据时需要对每个节点的数据特性进行分析,既费时又费力,但是在MIND算法中,上述过程主要通过UDF实现。使得分类算法易于与数据库系统集成。但是MIND算法并不能直接利用数据库的查询功能,同时该算法的维护也比较复杂。
4.2 GAR-RDB算法
4.2.1算法描述
GAR-RDB算法充分利用了关系数据库系统提供的聚集运算功能,在数据分析过程中主要用到的是SQL语句。通过对数据集的属性进行分析从而选择一个最好的分裂属性,并进行相应的排序。
4.2.2算法分析
该算法与其他方法相比分类准确迅速,执行速度有较大提高,同时可拓展性也比较好,也可以充分利用数据库提供的查询功能,从而避免对数据集重复地进行扫描,也不需要对训练集转换成交易型数据库格式。但是该种算法在自动地确定参数的取值等方面还需要改进。
5 结束语
数据挖掘算法综述 篇5
随着信息科技与互联网的高速发展,各个应用领域的信息量都呈现了爆炸性的增长趋势。因此,不同应用领域各自关注的实体对象之间的关系也变得愈加庞大和复杂。在这些复杂关系的背后,往往蕴含着巨大的科学价值和商业价值。由此,吸引了诸多领域的研究者都开始专注于实体对象之间关系的研究,如计算生物学领域中,蛋白质和酶之间所发生的复杂的交互、调控与代谢关系的研究;社会学领域中,对不同社交网络中人与人之间交际关系的研究;商业领域中,对金融网络和货币流通网络中商业关系的研究;以及互联网搜索领域中,不同网页之间超链接关系的研究。在这些领域中,如果采用传统的关系数据库来管理数据对象之间的这些错综复杂的关系,会用到巨量且昂贵的连接操作。因此,利用传统的关系数据库来研究复杂的结构化数据并不具备现实可行性。“图”作为离散数学和计算机科学中基本的数据结构,可以有效地表示存在多种关联的数据以及内部具有一般性结构的数据。图中,每个顶点代表现实世界中的实体对象;两个不同顶点之间则可能会存在一条或多条边,由其代表不同实体之间存在的某种关系。针对这种形式的结构化的数据,研究者们将其称作“图数据”。
近年来,图数据已广泛地用于刻画现实世界中各类实体间的复杂关系。例如,传感器网络中的节点拓扑结构图;互联网领域中的页面超链接关系图;计算生物学中的蛋白质交互和基因调控网络;社交网络中(如新浪微博、微信等)用户之间交互关系图及～Email～通信关系图;物流学领域中的交通网络、物流网络等等。这些例子清楚地表示,图数据现已无处不在,因此,对图数据进行管理则成为一个迫切重要的问题。由于图数据具有的重大科学意义和巨大社会价值,数据领域内的顶级学术会议SIGMOD、VLDB、ICDE、KDD以及重要学术会议CIKM、EDBT、ICDM等均设有与图数据管理有关的研讨议程。
然而,在现实世界中,实体对象间的关系却每时每刻都在发生着变化。以社交网络为例,根据Facebook网站2010年的Yearbook报告,仅仅2010一年间,其用户就从3.37亿人增至5.85亿人,平均每秒新增7.9位用户,同时,平均每分钟,会发生47 553个好友关系的建立或解除。2011年,Google+在上线后的两周时间内,增长了1 000万的用户。同年,Twitter～平均每天都活跃着2亿的用户,并且发生着超过16亿次的交互。这些数据无不在显示与说明,现实世界中实体对象间的关系都无时无刻地经历着变化。因此,描述实体对象的图数据的结构和内容往往不是固定不变的,而是会随着时间的推移发生各种演绎与进化的。
动态图,又称为演绎图(evolving graph),是指会随时间而发生变化的图模型或者图数据。动态图可以根据其变化的形式分为两类:
(1) 图中拓扑结构关系发生变化;
(2) 图中顶点和边所代表数据对象内容、或者图中某一特定对象的评价方式发生变化。
由此,可将这两种情况分别简称为图的结构变化和图的内容变化。在第一种情况中, 图中的顶点和边会随着时间发生插入和删除,从而导致图的结构发生变化。在第二种情况下,顶点或者边上的权值会随着时间发生数值上的改变,或者对图中某一特定对象的评价方式会随着时间变化。比如,对图中每条路径,存在一个评分函数随时给出该路径的得分。对一组固定的起点和终点,评分函数不同,其评分最优路径也就不同。因此,当评分函数随时间发生变化时,同一对起点和终点间的评分最优路径也会随着时间发生相应的变化。
动态图数据在现实生活中的广泛存在,比如:在蛋白质交互网络中,各类蛋白质分子的相互作用有着队列顺序,这使得整个蛋白质交互过程要随着时间而顺序进行;在社会关系网络中,各类人群和各类团体之间的相互关系也会随着时间发生变化;在交通网络中,通过每条公路的时间和费用因交通堵塞的发生均会随着时间发生变化。因此,对动态图数据的管理就有着重要的实践研究意义,主要体现为:在计算生物学领域中,研究基因组结构和功能的协同进化关系;在社会学领域中,通过从动态图数据挖掘知识,发现各类社会团体之间关系的演变规律和原因;在交通网络中,通过交通网络拓扑结构的变化,研究网络中某区域变化对全局网络的影响等等。
尽管如此,传统静态图数据上各类问题的解决算法却无法应用于动态图数据上各类问题的高效解决,主要有以下几个原因:第一,传统的静态图模型无法描述图数据随时间发生演绎与进化的情况;第二,传统的静态图模型上的各类问题的定义在动态图数据模型上不再适用;第三,图数据的动态性使得各类问题的计算复杂性大大增加,原有静态图上的各类方法将无法有效地解决这些问题。此外,现有的动态数据管理的研究主要集中于数据流和传统关系数据的动态维护,但却无法处理结构复杂的图数据。因此,必须提出更为优质的方法能够随着时间变化高效地维护图结构,并且能够实时返回用户所需要的结果或者从动态图数据中挖掘得到更加实用的知识。
2 动态图上的查询与挖掘算法的研究工作
相比传统静态图数据上的研究,动态图数据上的研究工作才刚刚起步。但在较近的几年,越来越多的成果开始在动态图数据管理研究方面得以展现。在本节中,将对动态图上的相关工作进行简单的介绍,包括基于结构变化的动态图上的研究工作和基于内容变化的动态图上的研究工作。
2.1 基于结构变化的动态图上的研究工作
过去几年间,研究者们对拓扑结构关系变化的动态图相关研究开展了大量效果卓著的工作。这些工作主要集中在以下三个方面:
(1) 图上经典问题在动态图上的研究;
(2) 动态图上子图模式的研究;
(3) 动态图上变化探测相关问题的研究。
现在,将在下面几个专题中对这三方面工作进行分别的讨论剖析。
2.1.1 图上经典问题在动态图上的研究
图上经典问题主要包括:最短路径问题、可达性查询问题、最小生成树问题和连通分支问题等等。目前,已经见到很多的工作对这些问题进行了研究并取得了颇丰的研究成果。但在动态图上,这些问题则变得更加复杂。下面,将对动态图上重要的图经典问题的相关工作分别加以介绍。
(1)动态图上最短路径问题的研究
最短路径查询是图上一个基础性的查询问题,其应用十分广泛。当图的拓扑结构关系随时间发生变化时,两点间的最短路径也会发生相应的变化。动态图上最短路径问题相关工作主要表现在:当图的拓扑结构发生变化,即顶点和边发生插入和删除时,如何维护指定的顶点之间的最短路径;以及当图的拓扑结构发生变化,如何为任意图中两个顶点实时并迅速地找到两者之间的最短路径。其中,某些工作要求动态图必须满足一定的性质,如:文献[1,2]研究了平面图 (planar graph) 上的最短路径维护问题,文献[3]和文献[4]研究了非加权图上最短路径的维护问题等等。近几年来,研究者们相继提出一些新方法,但这些方法均未对图性质做任何要求[5,6,7,8,9,10,11]。下面,即将对其中标志性的工作进行讨论与分析。
文献[5]给出一个全局动态的算法FMN来计算动态图上的单源最短路径问题,全局动态 (fully dynamic) 是指图中的顶点和边允许发生删除与插入。与全局动态对应的是衰减动态 (decremental dynamic),却只是允许图中发生顶点和边的删除操作。给定一个顶点s,该工作的目标是维护顶点s到图中所有其他顶点的最短距离和最短路径。在研究中,构建了一棵以s为根的最短路径树T,当图中顶点和边发生插入和删除时,算法就对最短路径树T进行相应的更新。同时,又定义了边上“层次”的概念。文献[5]表明每次更新T需要O(klogn)的平均时间,其中,n为图中顶点个数,k为图中边的最大层次数。此外,文献[5]也表明,完成最短距离查询和最短路径查询分别需要O(1)和O(L)的时间,这里,L表示最短路径上边的数量。尽管FMN 算法回答查询的时间很短,但是却需要维护复杂的最短路径树结构,这就使得其算法效率并不高超。如文献[6]中所示,动态算法SWSF-FP 在很多情况下都要优于FMN 算法。
文献[6]中给出了一个全局动态算法SWSF-FP 来维护动态图上的最短路径,该工作要解决的是和文献[5]中相同的问题。SWSF-FP 算法的主要思想是:为图中每个顶点维护一个值rhs(v),该值记录了起点s到顶点v的最短距离。当图中发生边的增加和减少时,算法逐步地更新受到这条变化边影响的顶点上的rhs(v)取值。SWSF-FP算法的缺点是需要频繁地计算rhs(v),这将导致较高的时间开销。文献[7]中对SWSF-F算法进行了改进,并提出一个基于Dijkstra的算法的更新最短路径树,使得SWSF-FP算法可以用于具有多重边的动态图上。
文献[8]中提出了一个为图序列中每一个快照计算两点间最短路径的基本框架FVF。该文献假定在图的动态演绎过程中,会有一些历史信息得到保存。该文献中,动态图序列根据其相似性可划分为若干个图快照的集合。FVF方法为每一个集合保存一个并集图和一个交集图,通过并集图和交集图上保留的两点间的最短路径信息,可以快速回答每个图快照中两点间的最短路径。FVF的方法也存在着不足,其缺点是:通过并集图和交集图上的信息,只能找到图快照上一部分顶点对间的最短路径。当并集图和交集图上的信息不能帮助回答某一对顶点间的最短路径时,FVF 需要调用静态图上的最短路径算法为该图快照上的这一对顶点计算彼此之间的最短路径。
此外,文献[9]中首次给出了计算动态图中所有顶点对之间最短路径的全局动态算法。文献[10]中则给出了一个改进的算法用于维护动态图中所有顶点对的最短路径。
(2)动态图上最小生成树问题的研究
文献[11]中给出了一个全局动态的算法来维护动态图上的最小生成树,该方法利用了图分解理论将图划分成一组连通图的集合。当图中的边发生动态更新时(插入或者删除),只有集合中的一部分连通图会受到影响。因此,算法将这部分连通图在最小生成树上的对应部分更新即可。文献[11]证明了:对每一次边的更新,算法维护最小生成树的时间复杂度均为O(m1/2) ,其中,m表示图中边的数量。特别地,当动态图是一个平面图时,算法的时间复杂度还可进一步降低为O((log m)2)。
文献[12] 采用Sparsification技术对文献[11] 中的工作进行了改进,使得对每次边的更新,维护最小生成树的时间复杂度能够降至O(n1/2)。文献[12] 表明,当只允许图中的边进行插入更新操作时,可以利用Sleator-Tarja 动态树来维护动态图的最小生成树。此时,对每一次边的更新,算法均需要O(log n)的时间完成最小生成树的更新。当只允许图中的边进行删除更新操作时,文献[12]表明,并不存在全局动态的算法能比O(log n)更快。进一步地,文献[13]给出了一个最坏情况下时间复杂度为O(log n)的全局动态算法,当动态图中的边每次发生更新时(插入或者删除),该算法用于维护最小生成树的平摊时间即为O(n1/3 log n) ,而回答最小生成树的查询却只需要O(1)的时间。
(3)动态图上k连通分支问题的研究
文献[14]首次研究了动态图上连通分支(k = 1)的动态维护问题,其中给出一个时间复杂度为O(q+|V ||E|) 的算法,可以实时回答所要查询的q个顶点是否在同一连通分支中。然而,该工作只能对k=1的连通分支进行动态维护,且只能允许动态图中发生边的删除。
文献[15]首次提出了一个部分动态算法用于维护2-顶点连通分支。该研究假设动态图中只会发生顶点和边的插入更新操作。文中对Sleator-Tarja动态树结构进行了改进,使其可以适用于文中给出的递归算法。文献[15]表明:对每一次顶点或边的更新,其维护连通分支的时间复杂度为O(nlog n+m),空间复杂度为O(n)。即便如此,该工作提出的算法也不是全局动态算法,即其仅能处理动态图中只发生顶点或边插入更新操作的情况。
文献[16] 中研究了并行环境下动态图上对k=2和k=3的k连通分支的维护问题,并给出一系列的理论结果。文献[17]中提出一个抽象化模型用于描述图的连通结构,该模型能够有效地反应动态图中连通结构的变化,并能回答图中任意两个顶点是否属于同一个5-连通分支。文献[17]中的方法仍然不是全局动态的,即仅能解决图中边只发送插入更新的情况。
目前,在动态图上,关于图经典问题的研究工作主要集中在最短路径维护,最小生成树维护和k-连通分支维护等问题方面。这些工作只是讨论了动态图上对某些特殊性质进行动态维护的复杂度,以及给出一些理论结果,却不曾关注图中“何时”并且“何处”发生了显著的变化。
2.1.2 动态图上子图模式挖掘的研究
子图模式挖掘是图挖掘中一类十分重要的问题。针对静态图上的子图模式挖掘已经开展了大量深入的研究工作并取得了不俗的研究成果。然而,动态图上的子图模式挖掘问题的研究却只是刚刚开始。目前,动态图上关于子图模式的研究主要集中两方面:动态图上频繁子图模式挖掘和动态图上紧密子图挖掘。
动态图上的频繁子图模式挖掘是指在一个图的演绎过程中(或者演绎图序列中)找到具有相同变化过程的子图。目前关于动态图上的频繁子图模式挖掘已经取得了一定的进展,其研究目的都是从动态演绎图序列中找到一组子图序列,使得其满足:
(1) 这些子图在动态图序列中的出现是频繁的;
(2) 这些子图的图序列随时间变化的情况保持一致。
文献[18]将图中每一个顶点上或者每一条边上的一次变化称为一次“原子操作”,图序列中任意两个连续子图之间的变化可用一系列的原子操作来表达。文中定义了原子操作表达的文法规则,因此,对动态图上频繁子图模式的挖掘等价于在原子操作序列上的频繁项集的挖掘问题。文献[18]提出了名为GTRACE 方法来计算序列中具有相同操作顺序的原子操作序列,并将其转化为动态图上的频繁子图模式。
文献[19]提出一种基于约束的挖掘算法来计算动态图上具有相同进化模式的频繁子图,其目的是根据用户给出的两种约束参数:紧密度参数和频繁度参数,在动态图序列中找到足够紧密并且足够频繁的具有相同变化模式的子图。文献[20]提出了在动态图序列中寻找一种新的模式,即图中的某几部分区域会以一定相关的方式发生进化。文献[21]研究了如何在动态图集合中挖掘频繁子图模式。在该问题中,动态图集合是指一些图的集合,集合中的每一张图均会随时间发生变化。文献[21]的目的是在这些动态图集合中找到一组具有相同演变模式的频繁子图。该问题与图数据库中频繁子图模式挖掘的问题相类似。文献[21]对现有静态图数据库中的频繁子图模式挖掘算法进行了改进,使其可以适用于动态图集合上的频繁子图模式挖掘问题。文献[22]研究了在动态图序列中挖掘具有相同变化模式的频繁树结构的问题。文献[23]中考虑了如何在多项式时间内计算得到周期性或者近似周期性的子图变化模式。文献[24,25]则研究了如何在社会网络的进化过程中找到满足一定进化规律的团体组织(community) 。
2.1.3 动态图上变化探测相关问题的研究
文献[26]和文献[27]利用熵等信息论方法,适当分割图流,并在每一个流片段中发现相对高度互连的结点社团(community)。文献[26]提出了一种动态张量分析的方法,将图的动态演变抽象为一个较小核心张量流和其对应图的映射矩阵。GraphScope方法[27]用于在大规模的动态演变图上发现联系紧密的社团(community),并探测这些社团发生显著变化的时间。文献[28,29]提出了三种不同的代价函数,如最大公共子图,来检测图数据流在何时发生了显著改变。文献[30]提出了在图数据流中计算图与图之间距离的优化方法。该文定义了图与图之间距离的概念,并设计了一个算法,仅需要有限的内存开销,即能以任意顺序处理图数据流中发生变化的边。这些方法都提出了各自的目标函数来定义动态图数据发生显著变化的概念,但这些代价函数都是落定于动态图整体来进行考虑的。而在现实世界中,计算动态图序列中所有子图的代价函数值却是不切实际的,因此这些方法都不能发现并确定动态图中的哪一子部分发生了显著变化。
2.2 基于内容变化的动态图上的研究工作
基于内容变化的动态图是指:图上顶点和边上的权值会随着时间发生变化。目前,关于内容变化的动态图方面的探讨主要集中于时间依赖图上最短路径的研究。时间依赖图上边的代价权值被刻画为一个会随着时间的变化而变动的函数。目前,关于时间依赖图上的最短路径查询问题(TDSP)的研究工作已经获得了长足的进步。然而,这些工作主要解决了最短旅行时间问题,即在时间依赖图模型上找到一条起点到终点的路径,使得该路径的时间代价总和最小。相应工作主要分为两类,一类是基于离散的时间模型,另一类则基于连续的时间模型。文献[31,32,33]研究了离散时间模型下的时间依赖最短路径查询。文献[33]将出发时间区间平滑地离散为多个时间点,并依据这这些时间点将图中顶点和边复制多次。因此,时间依赖图就转化为一个规模增大的静态图。文献[31]给出方法如何在这个静态图上完成最短路径查询。只是这一基于离散时间模型的方法并不能回答连续时间模型下的最短路径查询问题。文献[32]中,图上每一条边均被赋予一组聚集属性,该聚集属性表示了这条边在不同时刻呈现的状态。文献[34,35,36,37,38]研究了连续时间模型下的最短路径查询问题。文献[34]提出了一种基于Bellman-Ford算法思想的求解方法。对图中任意顶点,该方法迭代计算到达该顶点的最早时刻,并利用这些中间结果,最终计算可得到达终点的最早时刻。最后,根据该时刻找到旅行时间最短的结果路径。文献[35]提出了道路网中的速度流模型,该模型下,图中每条边的通过速度可以用一个分段线性的函数表示。该文提出一个基于Dijkstra算法思想的方法计算速度流模型下的最快路径查询问题。文献[36]则给出了一种基于A*算法的扩展算法。该算法的主要思想是用一个优先队列维护所有待扩展的路径。对任意一个顶点,起点到这个顶点的最早到达时间函数就维护在优先队列中,该算法通过该顶点到终点的欧氏距离和网络中的最大速度,实现从顶点到终点的时间预估。算法根据预估时间弹出队列元素,并找到起点到终点的最短旅行时间路径。文献[37]介绍了如何应用数据挖掘的方法找到各种条件下描述道路通过速度的模型。文献[38]是目前最有效的解决TDSP问题的方法。该方法采用两阶段搜索策略。第一阶段,用优先队列更新图中所有顶点最早到达的时间函数,并最终计算出终点的最早到达时间函数。第二阶段,根据终点的最早到达时间函数找到旅行时间最小的路径。文献[39]研究了时间依赖图下,具有时间限制的代价最优路径的查询问题,并给出了一个有效的两阶段算法计算时间限制下的代价最优路径。
3 结束语
动态图作为现实世界中广泛存在的结构化数据,已经引起人们越来越多的关注。对动态图数据管理方面的研究,具有十分重要的学术意义和广阔的应用前景。本文总结了动态图数据上查询与挖掘算法的主要工作,并对未来的研究方向进行了简要的分析,希望能够借此推动国内对动态图数据开展更系统且深入的研究。
摘要：近年来,图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系。然而,在现实世界中,描述实体对象的图数据的结构和内容往往不是固定不变的,而是会随着时间的推移发生演绎与进化。目前,越来越多的研究者开始关注动态图数据方面的研究问题,也涌现除了很多优秀的研究工作。总结了近年来动态图上查询算法与挖掘算法方面的基础性研究工作,讨论了现有的工作和动态图研究的发展方向。
数据挖掘算法综述 篇6
近年来,随着电子商务和社会经济的发展,人们的生活习惯有了较大变化,越来越多的企业通过电子商务进行交易、结算等商务活动,在网上进行消费、投资活动的人群也逐年增多,人们的日常活动,包括食品、衣物、旅行、票务预订、教育等活动都可以通过网络得到满足,电子商务越来越紧密的和消费者结合。截至2014年6月,中国电子商务交易额超过5.8万亿元,互联网用户超6.7亿,网购用户数量超过3.1亿人。但是虽然每天都有数以亿计的消费者在网络中进行购物活动,但网络中亦有数以万计的商家在网络中从事商业活动,对于每一个商家而言,如何对市场进行划分,精准的进行产品、市场进行定位,抓住老客户,发现新客户,在众多的商家中脱颖而出成为摆在每个商家面前的问题。[1]
2005年,菲利普·科特勒提出了精准营销的概念,并首次提出了基于互联网的精准营销理论,他认为:“日新月异的科技使一些公司勇于从传统的大众传媒沟通方式转移到更加有针对性目标市场的互动模式,以此来不断提高沟通的效果和效率。”随着技术的不断发展,数据挖掘成为网络中精准营销的重要抓手,消费者在网络中购物、浏览网页等活动中留下了大量的交易数据、Web数据等信息,这些数据中隐藏着巨大的商业价值,对其进行研究和挖掘,具有重要意义,消费者可以获得更满意的购物体验,商家可以获得更公平的流量分配,电子商务平台也可以因提供精准营销服务而获得更多商家入驻和获得新的赢利点,以及更多消费者的关注。
2 精准营销和数据挖掘相关理论研究
精准营销是指在恰当的时间,提供恰当的产品,用恰当的方式,送到恰当的顾客手中,恰当到一定程度,称之为精准,这是国内学者对精准营销的描述。在实际研究中,也有学者认为精准营销是通过定量和定性相结合的方法对目标市场的不同消费者进行细致分析,根据他们不同的消费心理和行为特征,采用有针对性的现代技术、方法和指向明确的策略,实现对目标市场不同消费者群体强有效性、高投资汇报的营销沟通。其特征主要体现在目标对象的选择性、沟通策略的有效性、沟通行为的经济性、沟通结果的可衡量性和精准程度的动态性五个方面,其所包含的理论包括顾客让渡价值理论、市场细分理论和4C理论,精准营销实施的策略和途径包括邮件、呼叫中心、短信等基于数据库的精准营销方法,门户网站广告、关键词搜索等基于互联网的营销方法和借助拥有共同客户群商家的基于第三方渠道营销方法三种,精准营销是对经典营销的延伸和发展,其主要集中在挖掘客户、客户沟通、信息传播和增值服务等方面。
数据挖掘从广义上来讲又称数据库中的知识发现,是从数据库中大量数据中发现隐含的、未知的有价值信息的过程。[2]数据挖掘是目前数据库和人工智能领域研究的热点问题,目前已广泛应用到各个领域和行业,包括商业领域中产品生产、市场营销、客户关系管理等,金融领域中投融资评估、股票交易等;物流领域的路线规划、天气预测等;教育领域的高中生管理、毕业生就业分析有情。数据挖掘需要的原始数据可以是结构化的数据,也可以是半结构化的数据,如图形、图像、文本等数据;也可以是网络中异构数据,在数据挖掘中采用的算法包括分类分析、回归分析、聚类分析、Web页挖掘、预警分析等,它们模拟人们的归纳、演绎等思维逻辑,从不同的角度对数据进行挖掘,满足客户细分、客户行为预测、特征发现、风险预警等方面的信息需求。
3 用于电子商务平台精准营销的数据挖掘需求分析
当消费者在电子商务网站上有了浏览、购买、评价行为后,该用户就成网站的价值客户,其相关数据被电子商务网站和商家的数据库所记录,电子商务数据分为前端行为数据和后端商业数据两类,前端行为数据包括浏览量、访问量、点击量及搜索关键词等用户行为数据;后端商业数据包括交易信息、购买商品、支付金额、购买数量等信息。对这些数据进行分析可以帮助商家了解用户行为习惯、客户群细分、发现高价值客户、维持客户关系、发掘潜在客户等,总的来说,可以将其需求划分为以下三个方面:
3.1 客户前端行为习惯
客户行为习惯的分析主要源自对前端行为数据的分析,其分析的关键即对用户的转化流程的分析,用户转化流程主要包括浏览过程、购买流程、注册流程、互动流程等,其目的是使用户心情愉悦的进行操作,并较快地找到想要的结果,从而达成交易。客户行为习惯分析包括两个内容:一是分析特定用户群在网页上流转的规律和特点,发现频繁访问的路径模式,提炼出该用户群体的主流路径和浏览特征,对网页优化和改版、对用户下一个浏览页面进行预测;二是对搜索关键词进行分析,在对大量用户检索行为分析的基础上,得出最有效的关键词组合,优化广告发布页面的相关性,提高转化率。[3]
3.2 客户后端购买行为分析
电子商务客户后端购买行为在精准营销方面的需求主要有目标客户特征分析、客户分类、保留和延长客户生命周期和利润贡献、商品智能推荐等,其目的主要是通过挑选指标变量进行数据挖掘,以便运营团队提供精细化、个性化运营和服务,从而实现特定营销目的。
3.2.1 目标客户特征分析
目标客户特征分析是精准化营销的第一步,因为在精准营销之前,第一步就是要找准目标客户和受众,特别是当企业刚推出新产品的时候,产品运营团队尤其需要一个对目标客户特征的初步描述,这个时候需要依据产品设计初衷、产品定位及运营团队初步的理想化的猜测,从历史数据中挖掘出目标客户典型特征;在该产品试运营之后,再根据收集到的用户资料对目标客户特征进行修正。
3.2.2 客户分类
客户分类主要是精准要求的必然要求,目的是针对不同客户群体采用不同的营销方式,从而提高运营团队的运营效率和付费转化率,在实际操作中主要是通过分析数据库中的交易数据,按照各个客户指标(如自然属性、交易额、价值度等)对客户进行分类,确定各类客户行为模式,运营团队据此采取相应营销措施实现企业利润最大化。
3.2.3 保留和延长客户生命周期和利润贡献
当客户在商家购买东西后,商家就会有需求来保留和延长客户生命周期和利润贡献,为实现这个需求商家一般会有两种策略,一是保留客户,通常是建立客户流失预警模型提前锁定有价值的客户,对其进行客户关怀;二是通过交叉消费等手段,让客户消费更多商品和服务,挖掘客户利润,这都依赖于数据挖掘的实施。
3.2.4 商品智能推荐
在电子商务网站中,经常需要针对不同的客户进行商品推荐,缩减客户搜索成本,提高客户体验,提高网站流量的转化率,提高营收。根据商品推荐的对象来分,可以分为面向浏览用户的推荐和面向登录用户的推荐两种,面向浏览用户的推荐往往是常规推荐,其指的是符合常规商品关联逻辑的一些推荐,面向登录用户的推荐往往是个性化推荐,是指基于购买行为间关联性归纳出的商品推荐。
3.3 指标异常检测
孤立点和异常值是与整体数据行为特征不一致的数据,孤立点和异常值在数据挖掘中通常表现为分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等,对这些偏差进行检测很有意义,在电子商务数据挖掘的一些业务中其能反映出外界市场变化的客观反应,如当网站PV减少的时候需要对搜索来源、直接访问量、搜索关键词等进行分析,及时发现市场变化,做出相应调整。
4 用于电子商务平台精准营销的数据挖掘算法研究
目前在电子商务平台精准营销中应用的数据挖掘算法基本覆盖了数据挖掘算法中的聚类算法、分类和预测算法、关联规则算法这三个类别,本文对其概念、使用范围和算法进行了综述和分析。[4]
4.1 聚类算法
聚类分析是精准营销中比较基础和比较重要的算法之一,聚类算法可以实现针对目标群体的多指标群体划分,这些分类往往是精准营销的基础和核心,只有正确地进行分类,精准营销的业务需求才能有效地开展,其业务场景主要如下:一是目标客户群的分类;二是不同产品的价值组合(交叉销售);三是孤立点、异常值的探测和发现。该算法可以分为划分方法、层次方法、基于密度的方法和基于网格的方法及数据来源。
4.2 分类和预测算法
分类和预测是数据分析的两种形式,主要用来抽取能够描述重要数据集合或预测未来数据趋势,分类算法主要用来预测数据对象的离散类别,预测方法用于预测数据对象的连续取值。分类算法主要应用的业务范围包括:一是按照既定的标签或目的对客户进行分类以便寻找不同种类用户的特征;二是利用分类算法得出的反常实例揭示异常现象,常用算法包括决策树、KNN法、SVM法、VSM法、贝叶斯法、神经网络等,预测算法主要应用的业务范围是预测客户访问行为、商品销售小预测等,算法主要包括线性回归、多元回归、非线性回归等。
4.3 关联规则算法
关联分析,关联规则算法主要是发现(下转P20)(上接P16)不同项之间的相关性,利用关联规则可以发现存在在数据库中的可被发现的两个或多个变量取值之间存在的规律性。在电子商务精准营销中,其业务场景主要如下:一是发现访问页面之间的关联规则;二是找出客户可能会感兴趣的商品推荐;三是商品智能推荐。关联规则算法在精准营销中应用较为广泛的是Apriori算法、协同过滤算法等。
5 结论
随着电子商务和数据挖掘技术的继续发展,用户的需求会越来越丰富,精准营销理论也会随之愈加深化,国内外学者对电子商务平台中精准营销的业务理解和分析思路也会更加精确和成熟,满足精准营销需求的数据挖掘的研究算法也会更加灵活,在应用中对业务提升的效果也将愈加显著。
参考文献
[1]李维胜,蒋绪军.电子商务精准营销对策研究[J].开发研究,2013(2):46-49+96.
[2]刘金勇.Web数据挖掘在电子商务中的研究应用[J].网络安全技术与应用,2013(9):25-26.
[3]谭恒松.中小企业移动电子商务精准营销策略研究[J].中国商贸,2013(28):87-88.
数据挖掘算法综述 篇7
作为互联网上最为核心的通信协议之一, TCP协议最早于1974年由Vinton Cerf和Robert Kahn共同提出。最初, TCP协议设计的主要目的是如何在异构的主机之间可靠地传输数据, 因此主要包括基于窗口的流量控制, 丢包恢复等功能。上个世纪80年代, 由于互联网用户和流量的激增, 互联网经历了多次严重的拥塞崩溃事件。为了解决这一问题, 上世纪80年代后期, Van Jacobson等人首次把拥塞控制应用到TCP协议当中, 从而极大地改善了Internet上端到端连接的性能和稳定性, 保证了整个互联网的稳定运行[1]。TCP是目前互联网中使用最广泛的传输协议。非常多的应用, 如FTP, Web, Email等, 都采用了TCP协议。根据2009年11月份的最新统计, 互联网总字节数的90%和总报文数的87%均使用TCP协议进行传输[2]。
随着互联网的飞速发展, 各种新技术被应用到互联网中, 如多路由技术, 并行处理技术, 链路层重传技术等。这些技术在提升互联网性能的同时, 也导致了传输层乱序数据包的出现。大量的研究表明, 乱序数据包会使位于传输层的TCP协议性能大幅下降。国内外众多学者已经提出了各种不同的方法来提高TCP协议在面临乱序数据包时的性能。
本文首先分析了乱序数据包造成TCP性能下降的主要原因, 然后讨论了各国学者所提出的不同解决方案;在此基础上给出了在面临乱序数据包时, 提高TCP协议性能的几个研究方向。
2 乱序数据包对TCP协议的影响
TCP协议拥塞控制的基本原理是:当网络发生拥塞时, 发送端应减小发送速率。实际上, 位于通信连接末端的TCP拥塞控制算法无法了解网络中究竟是否真的发生了拥塞, 只能根据接收端收到的信息推测网络状态。因此设定了一个假设前提, 即分组丢失意味网络拥塞。即使这样, TCP协议还是无法确切了解是否真的发生了分组丢失事件, 只能根据确认指示推测分组是否丢失。现行的TCP协议可以通过两种方式来判定数据包的丢失[3]。
(1) 重传定时器超时。
(2) 接收端收到一定数量的重复应答 (通常为3个) 。
TCP通过数据包的序列号来保证数据包的正确, 按序交付。假设序列号为的数据包丢失, 接收端每收到一个序列号大于的数据包都会认为这是一个乱序数据包, 在数据包被正确接收之前, 每收到一个这样的数据包, 都将产生一个对于的重复应答。如果发送端收到一定数量的重复应答, 将认为该数据包丢失, 并由此推测网络发生了拥塞。此时, 重传丢失的数据包, 并将拥塞窗口减半。
这种丢包判定方式有效的前提是:网络结构稳定, 同属一个连接的所有数据包按照同一路径到达接收端, 并且中间路由采用先到先服务和FIFO的原则。在以上条件成立的情况下, 数据包的到达遵循“先发先到”的原则。数据包如果没有按序到达则意味着丢失。然而, 这种丢包判定方式容易受到网络中持续的乱序数据包的影响。
乱序数据包是一种数据包到达顺序与发送顺序不一致的网络现象。许多针对网络中数据包的乱序问题的观察、测量和本质研究指出:数据包的乱序并不是网络的病态行为, 而是作为一种普遍现象伴随着网络一直存在。统计显示约有0.1%-2%的数据包会经历乱序事件[4]。
乱序数据包的出现会给TCP协议带来很大影响: (1) 不必要的传输层重传, 浪费带宽; (2) 拥塞窗口不必要的减小, 降低网络利用率。
3 现有的解决方案分析
针对乱序数据包对于传输层TCP协议的影响, 众多学者提出了不同的解决方案, 主要包括以下三种。
3.1 增大触发快速重传的门限值
一些学者指出, 将触发快速重传的门限值 (dupthresh) 固定为3, 会使得TCP协议对于乱序数据包的容忍程度太低, 容易诱发不必要的重传。因此提出改变dupthresh的取值[5]。目前主要有三种dupthresh设定算法:
(1) 当乱序数据包出现时, 通过固定参数K增大dupthresh的取值。
该算法的主要思路是:当乱序数据包出现时, 将快速重传门限值dupthresh增大为dupthresh+K。为此, 需要在接收端检测乱序数据包事件。检测过程如下:如果数据包在dupthresh之后到达, 即, 已经被判定为丢失的数据包到达接收端, 则认为这是一个乱序数据包事件。此时, 将dupthresh增大为dupthresh+K。此后, 将按照新的dupthresh进行丢包判断。
这种方法的优点是实现简单, 缺点也很明显, 接收端可能需要多个周期, 才能将dupthresh设定为合理值。这个收敛过程和整个算法的性能依赖于K的选择。
(2) 将dupthresh动态设定为当前值与乱序数据包长度和的一半。
该算法的主要思路是:当接收端检测到数据包缺失时, 开始记录乱序到达的数据包数量, 称为乱序数据包长度, 记为L, 直到缺失的数据包到达。此时, 将快速重传的门限值dupthresh修改为 (dupthresh+L) /2。
这种方法的优点是, 它能够较第一种算法更为迅速地使dupthresh根据网络状态收敛于理想值。缺点在于一个偶然的较大的乱序数据包长度可能造成dupthresh过大, 影响TCP协议的性能。
(3) 根据乱序数据包长度, 利用指数加权移动平均算法设定dupthresh。
为了克服上述两种算法的缺陷, Leung等人在文献[6]中提出利用指数加权移动平均算法 (EWMA:Exponentially Weighted Moving Average) 动态设定dupthresh。同第二种设定算法一样, 当接收端检测到数据包缺失时, 开始记录乱序数据包的长度L, 直到缺失的数据包到达。此时, 根据以下公式, 计算平均乱序数据包长度:
其中, α为EWMA因子, 通常取1/3, x为乘性因子, 通常取4。
随后, 将dupthresh设定为平均乱序数据包长度avg。这种算法的优点在于dupthresh可以根据网络状态动态更新, 并且, 避免了第二种算法中单个过大的乱序数据包长度对dupthresh造成的过大影响。缺点在于接收端需要增加统计变量, 并且随时更新乱序数据包长度也会对接收端的性能造成一定影响。
3.2 Eifel算法
R.Ludwig和R.Katz提出使用Eifel算法来减少由乱序数据包引发的伪超时与伪重传对TCP协议的影响[7]。Eife的原理如图1所示, 发送端在T1时刻发送报文S时, 将时间戳插入TCP头部。在T2时刻, 发送端检测到S丢失, 重传S, 并执行拥塞控制算法。重传的S与原始发送的S相比, 包含不同的时间戳T2。当接收端收到原始的S后, 发送应答时, 包含原始S的发送时间T1。当此应答到达发送端时, 发送端发现此应答包含的时间信息T1小于存储与Retransmit TS变量中的T2, 由此判断此重传为假重传。当检测到假重传时, 发送端会将拥塞窗口和慢启动门限值恢复到错误重传前的值, 然后如同没有发生错误重传一样继续发送数据分组。
Eiefl算法的优点在于能够在很短的时间内检测出假重传, 从而避免了后续不必要的重传和拥塞回退机制。Eiefl算法还可以解决分组乱序、分组重复等问题。Eifel算法的缺陷在于, Eifel算法必须使用TCP协议的数据段参数来进行错误重传判断, 并且Eifel算法仅仅是在检测到伪重传时避免了拥塞窗口的减小, 并不能减少伪重传的数据包数量, 因此不能减少伪重传对带宽的消耗。
3.3 DSACK机制
重复选择确认机制 (DSACK) 通过扩展TCP协议的SACK选项来克服乱序数据包的影响[8]。
DSACK算法的原理如图2所示, 发送端发送S1-S4数据包。由于网络原因造成S1数据包乱序, 它在S4数据包之后到达接收端。因此S2, S3, S4数据包均会产生对S1的重复应答。在收到这3个重复应答后, 发送端将重传S1。当重传的S1到达接收端后, 会产生一个对于S5的重复应答, 同时SACK信息会指明此重复应答是由S1引起的。当此应答到达发送端后, 发送端就可以判断出刚才对于S1的重传是假重传。
DSACK算法要求发送端维护检测到分组丢失时的拥塞窗口和慢启动门限值等信息, 发送端根据DSACK信息检测到假重传时, 将拥塞窗口和慢启动门限值恢复到错误重传前的值。虽然没有增加分组的开销, 但是它无法解决网络中的分组重复和ACK丢失等问题。如果包含DSACK信息的应答丢失, 则接收端无法进行恢复。并且, 由于DSACK信息在丢失恢复结束后才到达发送端, 因此发送端在丢失恢复阶段无法检测到假重传。
4 结束语
本文总结了目前国内外学者提出的几种典型的TCP协议乱序数据包处理算法, 并对这些算法进行了详细的分析和比较。综上所述, 该领域仍存在着一些亟待解决的问题, 未来的研究可以考虑从以下方面展开:
(1) 充分利用TCP数据包头部的闲置字段, 描述链接及网络状态, 接收端可以利用这些状态参数, 判断缺失的数据包是否是由于网络拥塞导致。
(2) 设计更加合理的快速重传门限值设定算法, 使其能够以较快的速度收敛于真实网络状态, 同时算法应尽量减轻接收端的计算量和存储空间开销。
(3) 利用接收端已知参数, 如往返时延, 重传超时时间等, 在不增加接收端开销的基础上, 判断乱序数据包的出现。
参考文献
[1]Nagle J.RFC896:Congestion control in IP/TCP Internet works.Internet Engineering Task Force, 1984.
[2]Internet2NetFlow:Weekly reports.http://netflow.internet2.edu/weekly/.2009, 11.
[3]Allman M, Paxson V, Stevens W.RFC2581:TCP Congestion Control.Internet Engineering Task Force, 1999.
[4]Bennett J C R, Partridge C, Shectman N.Packet Reordering is Not Pathological Network Behavior[J].IEEE/ACM Transactions on Networking, 1999, 7 (6) :789-798.
[5]Chaudhary R, Jacob L.Corruption and Reordering Robust TCP-Friendly Rate Contro l[J].Computer Communications, 2005, 28:97-107.
[6]Leung K C, Ma C.Enhancing TCP Performance to Persistent Packet Reordering[J].Journal of Communication and Networks, 2005, 7 (3) :385-393.
[7]Ludwig R, Katz R.The Eifel Algorithm:Making TCP Robust Against Spurious Retransmissions[J].Computer Communication Review, 2000, 30 (1) :30-36.
蝙蝠算法应用综述 篇8
关键词：蝙蝠算法,仿生原理,改进的蝙蝠算法,算法应用
1 蝙蝠算法概述
蝙蝠算法模拟蝙蝠通过回声定位捕食猎物行为[1]实现搜索问题的最优解,其模拟回声定位方式为:将每只蝙蝠个体视为当前可行域内的一个解,每个解对应一个由所优化问题确定的适应值,每只蝙蝠通过调整脉冲波长、音量、脉冲发射率3项参数来追随当前最优蝙蝠,使得整个种群在问题求解空间中产生从无序到有序的深化,获取最优解。
2 蝙蝠算法应用
自BA提出以来,已有不少学者将其应用于优化问题,包括简单函数优化、生产调度、分类类别、模式识别等,相对于PSO、GA以及HS等,BA具有更大潜能。本文从基本BA和改进的BA两方面来阐述BA的应用。
2.1 BA基本应用
为了对燃气轮机发电系统进行性能优化和状态监测,Tamiru[2]将蝙蝠算法应用于燃气轮机发电系统模型中。首先使用蝙蝠算法和局部线性模型树算法对模糊系统进行训练,然后利用该系统捕捉燃气轮机发电系统的能量损失分布及变化情况,与局部线性模型树算法进行训练结果对比,证明蝙蝠算法和局部线性模型树算法结合的有效性;Nakamura[3]使用BA解决拓扑优化问题中的弹簧问题和减速器问题,实验测试结果表明蝙蝠算法得到的解优于目前为止所有文献的最优解;Nakamura[4]首次将BA强大的搜索能力和快速查找能力结合,实验测试结果表明蝙蝠算法的解优于目前为止所有文献的最优解;Bora[5]将BA应用于求解无刷直流齿轮电机问题[6],与SQP、GA、GA&SQP、ACO、PSO的对比实验结果表明BA可行;Fister[7]引入BA对运动员运动过程数据进行处理,给教练提供智能体育训练计划,与DE、PSO、DET进行对比实验证实BA的可行性;Yang[8]使用BA求解3个基准工程约束优化问题,实验结果表明BA的求解结果优于目前最优解。Taher[9]应用蝙蝠算法求解机组负荷经济调度问题,与PSO的对比实验表明BA的可行性与有效性。
2.2 改进的BA
基本BA存在易陷入局部最优导致早熟收敛问题,不少学者对基本蝙蝠算法进行相应改进以获取更好的解。
2.2.1 基准测试函数求解
Tsai[10]重新定义了蝙蝠的运动方式和随机游走过程,和基本BA进行对比测试,结果表明了该算法的有效性;Guanghui Liu[11]提出了多普勒效应蝙蝠算法,给出发现猎物、靠近猎物、捕食猎物时蝙蝠声波频率变化公式,通过和PSO、基本BA结果对比,证明了该算法的有效性和快速性;刘长平[12]对BA迭代过程中产生的较优解进行混沌优化,较差解用新的解予以替换,与PSO、BA求解结果对比,表明BA是解决工程应用中复杂函数优化问题的一种有效方法;谢健[13]将Levy飞行作用于蝙蝠位置的更新公式中,通过和基本BA求解结果对比,表明该BA的有效性和可行性;黄光球[14]把基本蝙蝠的回声定位方式改进为追随、自主、避险或从众行为运动,通过和基本BA、改进自组织迁移算法的求解结果进行对比,表明该算法具有较强的全局收敛性;肖辉辉[15]对BA迭代过程中产生的解进行变异、交叉、选择操作,得到新的解,和基本BA仿真结果对比,表明该BA能够增强算法的全局寻优能力。通过这两种BA求解非线性方程组问题,验证了BA的可行性和有效性,扩展了蝙蝠算法的应用范围;李枝勇[16]用量子旋转门和非门分别实现搜索和变异;高珊[17]使用小生境技术把蝙蝠划分为若干类,每个类内部通过共享适应度函数和排挤机制提高种群多样性。通过与PSO、GA、CS对比,表明改进的BA能够有效避免了局部最优,提高了全局寻优能力。
2.2.2 规划问题求解
李枝勇[18]为了求解多目标0-1规划问题,重新定义了蝙蝠位置和速度的更新公式,将约束条件转化到目标函数,把问题转化成无约束形式,通过和元胞蚁群算法、枚举法进行对比实验,证明了蝙蝠算法在解决多目标0-1规划问题上的有效性和优越性;李国成[19]在评估蝙蝠个体过程中嵌入交叉熵操作来更新蝙蝠位置,通过和HS、GA求解绝对值方程结果进行对比,表明该算法具有较强的全局搜索能力和稳定性;Taher和Farhad[20]使用自适应启发式蝙蝠算法解决机组组合优化问题,通过和GA、DP-SO、HPSO、SFLA对10~100个单元的集成系统问题和38个单元、不间断调度的集成系统问题求解结果对比,证明了该算法的有效性和快速性。
2.2.3 模式识别问题求解
Behnam[21]提出了多普勒效应蝙蝠算法。算法中加入多普勒效应特性,靠近猎物时声波频率增大,远离时声波频率减小,以此调节搜索过程中蝙蝠的声波频率,通过和ACO、PSO检测钓鱼网站的正确率和错误率进行对比,表明该算法稳定可行;为了提高BA的求解精度,Chen[22]根据蝙蝠和猎物速度方向的不同给出不同的声波频率更新公式,通过对燃气涡轮发电机进行故障检测和诊断,对比实际故障数据和该算法预测数据的偏差,证明了该算法的准确性。
3 研究展望
综上,蝙蝠算法未来研究方向如下:
(1)参数的敏感性研究。对不同的变量比如α、γ值的改变对算法收敛速度和结果的影响进行分析,在总结各参数变化对结果影响的基础上,设计出更好、更稳定、更快速求解问题的BA算法。
(2)BA与局部启发式算法相结合。利用BA自适应的随机搜索性,探索潜在的最优空间。局部启发式算法能对BA的搜索空间进行深入搜索,两相结合能在提高收敛速度和寻求全局最优之间找到一个平衡点,从而跳出局部最优解,提高求解精度。