数据挖掘算法论文
数据挖掘算法论文:基于决策树的数据挖掘算法研究
摘要：决策树（Decision Tree）曾在很长的时间里是非常流行的人工智能技术，随着数据挖掘技术的发展，决策树作为一个构建决策系统的强有力的技术在数据挖掘和数据分析过程中起到了非常重要的作用。决策树在数据挖掘中主要用于分类、预测以及数据的预处理等。
关键词：决策树；数据挖掘；Apriori算法
一、决策树数据挖掘基本概念
数据分类是数据挖掘中的一个重要问题，是一种有效的KDD分析方法。数据分类通过分析训练集中的数据，建立分类模型，然后利用这个分类模型，把数据库中的数据项映射到给定类别中。
图1.决策树生成过程Decision tree formation process
决策树分为分类树和回归树两种，分类树针对离散数据集生成决策树，回归树则针对连续变量生成决策树。决策树生成过程如图1所示。
决策树是一个类似于流程图的树结构，决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。
如图2所示，给出了一个决策树的示意描述样例。该决策树给了一个用于学生成绩分析的模型。利用它可以分析学生成绩受什么因素影响，以及会影响到与学生成绩相关的那些属性。决策树的中间结点通常用矩形表示，而叶子结点常用椭圆表示。
图2.决策树示意描述Decision tree motioned description
二、决策树算法
由于Apriori算法存在必须耗费大量时间处理规模巨大的候选项目集和必须多次扫描数据库对候选项目集进行匹配筛选的固有缺陷，针对这些缺陷Han等人提出了一种基于FP-Tree的关联规则算法FP-Growth算法。FP-Growth算法用一种压缩的数据结构（FP-Tree）可存储关联规则挖掘所需的全部数据信息，通过对源数据的两次扫描，将数据信息存到这种结构里，避开了产生候选项集的步骤，极大地减少了数据交换和频繁匹配的开销，这就是无候选项集产生算法（Frequent Patterns Growth，FP-Growth）。
（一）FP-Growth算法原理与相关概念。FP-Growth算法通过如下三方面的改进与创新，脱离了必须产生候选项集的传统方式，开辟了关联规则挖掘的新思路。
1.它构造了一种新颖的、紧凑的数据结构FP-Tree。它是一种扩展的前缀树结构，存储了关于频繁模式数量的重要信息。树中只包含长度为1的频繁项作为叶节点，并且那些频度高的节点更靠近树的根节点，因此，频度高的项比那些频度低的项有更多的机会共享同一个节点。
2.开发了基于FP-Tree的模式片断成长算法，它从长度为1的频繁模式开始，只检查它的条件模式基构建它的条件模式树，并且在这个树上递归地执行挖掘。模式的成长通过联合条件模式树新产生的后缀模式实现。由于事务处理中的频繁项都对应着频繁树中的路径进行编码，模式的成长确保了结果的完整性。因此，FP-Tree算法不像Apriori类算法那样需要产生再测试。挖掘的主要操作是计算累加值和调整前缀树，这种花费通常要远远小于Apriori类算法中的候选项集的产生和模式匹配操作。
3.挖掘过程中采用的搜索技术是基于分区的，通过分割再解决的方法，而FP-Tree的结构包括一个标识成“null”的根、一个由频繁项组成的头表和一组项的前缀子树组成了根的子孙。树中的每个节点包括3个域：项名（itemname）、计数（count）和节点链接（node-link）。其中，项名记录了节点所代表的项；计数记录了树中到达这个节点的路径所代表的事务处理的数目；节点链接指向树中下一个同名节点，如果没有同名节点则指向空。头表中的每条记录包含两个域：项名和节点链接的头。节点链接的头指向树中第一个同名的节点。
（二）FP-Growth算法描述。与Apriori算法的不同，FP-Growth算法中频繁项集的生成分为两步进行，第一步是构造FP-Tree，第二步在第一步的基础上对产生的FP-Tree进行挖掘以构造频繁项集。
FP-Growth方法将发现长频繁模式的问题转换成递归地发现一些短模式，然后与后缀连接。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。当数据库很大时，构造基于内存的FP一树是不现实的。一种有趣的替换是首先将数据库划分成投影数据库的集合，然后在每个投影数据库上构造FP一树并挖掘它。该过程可以递归地用于投影数据库，如果它的FP-Tree还不能放进内存。对FP-Tree方法的性能研究表明：对于挖掘长的和短的频繁模式，它都是有效的和规模化的，并且大约比Apriori算法快一个数量级。它也比树-投影算法快。树-投影算法递归地将数据库投影为投影数据库树。
FP-Growth算法开辟了有效挖掘频繁模式的新途径。然而，它的时间和空间效率还不足够高，仍需进一步改进。
数据挖掘算法论文:数据挖掘中聚类算法比较及在武警网络中的应用研究
摘 要：聚类算法是数据挖掘的核心技术,根据评价聚类算法优劣的几个标准,对数据挖掘中常用聚类算法做了比较分析,根据各自特点,加以改进,并应用于武警部队数据挖掘项目中。通过运用改进型Kmeans算法,取得了较好的挖掘结果,为进一步信息的智能化检索、信息的过滤、分拣提供依据。
关键词：数据挖掘;代表点聚类算法;基于密度的聚类算法;Kmeans聚类算法;指挥自动化
1 引 言
数据挖掘的历史虽然较短,但从20世纪90年代以来,他的发展速度很快,是多学科综合的产物。虽然目前还没有一个完整的定义,但这里认为：数据挖掘就是从海量的数据中挖掘出可能有潜在价值的信息的技术。这些信息是可能有潜在价值的,支持决策,可以有效利用指挥自动化网,为进一步研究寻找突破口。
数据挖掘综合了各个学科技术,其任务一般可分为2类：描述和预测。描述性挖掘任务刻划数据库中数据的一般特性。预测性挖掘任务在当前数据上进行推断,以进行预测\[1\]。主要功能有分类和预测、聚类分析、关联规则和序列模式的发现、偏差的检测等。
把数据库中的对象分类是数据挖掘的基本操作,根据最大化类内的相似性、最小化类间的相似性的原则进行聚类或分组,从而使属于同一类的个体间距离尽可能小,而不同类个体间距离尽可能大,为了找到效率高、通用性强的聚类方法人们从不同角度提出近百种聚类方法,典型的有Kmeans方法、Kmedoids方法、CLARANS方法,BIRCH方法等,这些算法适用于特定的问题及用户。
聚类算法一般分为分割和分层2种。分割聚类算法通过优化评价函数把数据集分割为K个部分,他需要K作为输人参数。典型的分割聚类算法有Kmeans算法：Kmedoids算法、CLARANS算法。分层聚类由不同层次的分割聚类组成,层次之间的分割具有嵌套的关系。他不需要输入参数,这是他优于分割聚类算法的一个明显的优点,其缺点是终止条件必须具体指定。典型的分层聚类算法有BIRCH算法、DBSCAN算法和CURE算法等。根据评价聚类算法优劣的几个标准\[2\],对常用的聚类算法进行比较分析。
(1) 是否适用于大数据量,算法的效率是否满足大数据量高复杂性的要求;
(2) 是否能应付不同的数据类型,能否处理符号属性;
(3) 是否能发现不同类型的聚类;
(4) 是否能应付噪声数据或异常数据;
(5) 是否对数据的输入顺序不敏感。
2 数据挖掘常用聚类算法比较分析
2.1 BIRCH算法
BIRCH算法即平衡迭代削减聚类法,其核心是用一个聚类特征3元组表示一个簇的有关信息,从而使一簇点的表示可用对应的聚类特征,而不必用具体的一组点来表示。他通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法的聚类特征树是一个具有2个参数分枝因子B和类直径T的高度平衡树。分枝因子规定了树的每个节点子女的最多个数,而类直径体现了对一类点的直径大小的限制即这些点在多大范围内可以聚为一类,非叶子结点为他的子女的最大关键字,可以根据这些关键字进行插人索引,他总结了其子女的信息。
聚类特征树可以动态构造,因此不要求所有数据读人内存,而可以在外存上逐个读人。新的数据项总是插人到树中与该数据距离最近的叶子中。如果插人后使得该叶子的直径大于类直径T,则把该叶子节点分裂。其他叶子结点也需要检查是否超过分枝因子来判断其分裂与否,直至该数据插入到叶子中,并且满足不超过类直径,而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改变类直径修改特征树大小,控制其占内存容量。
BIRCH算法通过一次扫描就可以进行较好的聚类,由此可见,该算法适合于大数据量。BIRCH算法只适用于类的分布呈凸形及球形的情况,并且由于BIRCH算法需提供正确的聚类个数和簇直径限制,对不可视的高维数据不可行。
2.2 CURE算法
CURE算法即使用代表点的聚类方法。该算法先把每个数据点看成一类,然后合并距离最近的类直至类个数为所要求的个数为止。CURE算法将传统对类的表示方法进行改进,回避用所有点或用中心和半径来表示一个类；而是从每一个类中抽取固定数量、分布较好的点作为描述此类的代表点,并将这些点乘以一个适当的收缩因子,使他们更靠近类的中心点。将一个类用代表点表示,使得类的外延可以向非球形的形状扩展,从而可调整类的形状以表达那些非球形的类。另外,收缩因子的使用减小嗓音对聚类的影响。CURE算法采用随机抽样与分割相结合的办法提高算法的空间和时间效率,并且在算法中用堆和Kd树结构来提高算法效率。
2.3 DBSCAN算法
DBSCAN算法即基于密度的聚类算法。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是：对于一个类中的每个对象,在其给定半径的领域中包含的对象不能少于某一给定的最小数目。在DBSCAN算法中,发现一个类的过程是基于这样的事实：一个类能够被其中的任意一个核心对象所确定。为了发现一个类,DBSCAN先从对象集D中找到任意对象P,并查找D中关于关径Eps和最小对象数Minpts的从P密度可达的所有对象。如果P是核心对象,即半径为Eps的P的邻域中包含的对象不少于Minpts,则根据算法,可以找到一个关于参数Eps和Minpts的类。如果P是一个边界点,则半径为Eps的P邻域包含的对象少于Minpts,P被暂时标注为噪声点。然后,DBSCAN处理D中的下一个对象。
数据挖掘算法论文:数据挖掘算法研究
摘 要：数据挖掘技术是一个不断发现知识的过程。阐述了目前三种流行的数据挖掘算法的理论模型及算法思想，并从算法时间复杂度、依赖条件和误差估计等方面进行了比较分析，说明了不同算法的优势和不足。指出了不同算法的应用前景，提出了一种将不同算法结合以减少误差率，提高算法效率的思路。
关键词：数据挖掘； 关联规则； 分类算法； 聚类算法
数据挖掘是指从海量的数据库中抽取隐含的、具有潜在使用价值信息的过程。它是一种面向应用的技术，不仅针对特定数据库进行简单搜索查询，且对数据进行微观、中观乃至宏观的统计、分析、综合和推理，进而发现潜在的知识。
数据挖掘的目的是发现知识，而知识发现的过程需要特定数据模型的支持，这使得数据挖掘算法成为研究的关键点。本文研究3种经典的数据挖掘算法，即关联规则挖掘算法、分类算法和聚类算法，并对它们进行了比较分析，指出了各算法的应用前景。
1 关联规则挖掘算法
关联规则是通过用户给定支持度和置信度来寻找规则的过程［1］。基本思想包含2个过程：
（1） 发现最大频繁项目集。
通过用户给定的支持度，寻找数据集中支持度大于或等于给定支持度的所有项目集，即频繁项目集，再从频繁项目集中选出所有不被其他项目包含的频繁项目集，即最大频繁项目集。
（2） 生成关联规则。
通过用户给定的置信度，在发现最大频繁的项目集中生成置信度大于或等于给定置信度的关联规则。
思想中支持度是数据集D中包含项目集i1的事务在数据集D上的百分比，公式如下：
ИИSupporti1=|{t∈D&i1t}|/|D|（1）И
式中：t是数据集D上的一个事务。
置信度是指包含i1和i2的事务数与包含i1的事务数的支持度比值，公式如下：
ИИConfidencei1i2=Supporti1∪i2/Supporti1（2）И
式中：i1∩i2=0。
2 分类算法
分类是根据数据集的特点构造一个分类器，利用该分类器将数据集中的数据映射到给定类别中某一类的过程。主要分类算法有k-最邻近算法、决策树分类算法和贝叶斯分类算法。
2.1 k-最邻近算法
k-最邻近算法（kNN）是一种基于距离的分类算法，距离越近，相似性越大，距离越远，相似性越小［2］。算法的基本思想是为：计算每个分类样本到待分类元组的距离，即计算相似度，选取与待分类数据相似度最大的k个数据，将待分类元组划分到这k个数据分类属性最集中的类别中。
2.2 决策树算法
决策树算法采用自上而下的方法递归构造决策树，分两个步骤：决策树生成和决策树剪枝。典型的决策树算法有ID3算法、C4.5算法等［3］。
2.2.1 决策树生成算法
决策树生成算法采用信息增益来选择能使样本最好分类的属性，信息增益的计算如下：
有n个消息，概率分布为p=(p1,p2，…，pn)，则该样本SУ钠谕信息为：
ИI(S)=I(p)=－∑n1pilog2 pi （3）И
对于给定的样本si∈S，其样本总数为Si，根据类别属性值将si划分为m个子集，每个子集中所包含的样本数分别为sij(1≤j≤m)，其概率分布为p=(Si1/Si,Si2/Si，…，Sim/Si)。根据公式得样本si的期望信息为I(si)=I(p)。
样本集SУ撵匚：
ИE(S)=－∑m1(Si1+Si2+…+Sim)I(si)S（4）И
样本S的信息增益为：
ИG(S)=I(S)－E(S)（5）И
算法的基本思想：
（1） 以代表训练样本的单个结点开始建树。
（2） 如果样本S都属于同一个分类，则将该结点作为叶子结点。
（3） 否则，利用公式计算各个属性的信息增益，比较计算所得的信息增益值，选取信息增益最大的属性作为根结点。
（4） 递归划分选取的根结点，直到下面3个条件之一满足时结束： 给定结点的所有样本属于同一分类；没有多余的属性可以用来进一步划分样本，此时采用多数表决法来创建叶节点；分支属性样本为空。
2.2.2 决策树剪枝算法
理想的决策树分为3种：叶结点数最少；叶子结点深度最小；叶结点数最少，且叶子结点的深度最小［4］。在决策树生成算法中没有考虑噪声等影响的因素，因此可能出现过度拟合现象，使分类预测性能降低，导致生成的决策树不尽理想。为了避免过度拟合，提出了决策树剪枝算法，该方法有预先剪枝和后剪枝2种。预先剪枝指在生成决策树的同时，决定是继续划分还是停止划分。预先剪枝的最大缺点是可能使树的生长过早停止，导致生成的决策树不完整，因此应用较少。后剪枝是一种先拟合后化简的方法，首先采用决策树生成算法对训练样本生成决策树，然后从树的叶子结点开始逐步向根的方向进行剪枝，具体的剪枝算法在本文不予以讨论。
2.3 贝叶斯分类
贝叶斯分类以贝叶斯定理为基础［5］，贝叶斯定理是：H为某种假定，P(H)为先验概率，P(X|H)为H成立条件下X的概率，则后验概率P(H|X)为：
ИP(H|X)=P(X|H)P(X) （6）И
贝叶斯分类的原理是通过某对象的先验概率，利用贝叶斯定理计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。
算法的基本思想：
（1） 根据训练样本计算分类属性的先验概率P(ci)。
（2） 计算待分类数据每个非分类属性的条件概率P(x|ci)。
（3） 由于各非分类属性可视为条件独立，故P(x|ci)=∏n1(xk|ci)。
（4） 利用式（6）计算ci的后验概率。
因为P(x)和P(ci)是常数，所以P(x|ci)最大，则后验概率最大，故将待分类数据划分到P(x|ci)最大的ci所在类别中。
3 聚类方法
聚类就是将数据对象分成多个簇，簇内有较高的相似性，而簇间差异很大。典型的聚类分析方法有划分方法和层次方法。
3.1 划分方法
划分方法依据数据点在几何空间的距离来判断个体间的相似度，距离越近就越相似，就越容易划分为一类。划分的原则是在同一个簇中的对象间有较高的相似性，而不同簇间差异很大。
3.1.1 k-平均算法
k-平均算法（k-means）是一种以簇内对象的均值为中心点的划分方法［6］。算法用欧氏距离来表示点到簇的距离：
Иd(x,y)=∑k1(xi－yi)2 （7）И
算法的准则函数定义为：
ИE=∑k1∑x∈ci|x－xi| （8）И
算法基本思想：
（1） 随机地选取k个对象，每个对象代表一个簇的初始中心。
（2） 根据式（7）计算剩余对象到中心点的欧氏距离，将每个对象赋给与其欧氏距离最小的簇，即最相似的簇。
（3） 重新选取每个簇的中心点，即重新计算簇内各点的平均值。
（4） 计算平方误差和E，循环(1)，(2)，(3)直到准则函数E变化不明显为止。
3.1.2 PAM算法
PAM算法是一种以簇中位置最中心的对象为中心点的划分方法［7］。中心点被称为代表对象，其他对象被称为非代表对象。算法基本思想：
（1） 随机地选取k个对象，每个对象代表一个簇的初始中心点。
（2） 根据中心点计算每个非中心点y到中心点x的绝对距离|y－x|，将每个对象赋给与其绝对距离最小的簇，即最相似的簇。
（3） 选择一个未被选过的中心点oi及oi所在簇中的一个未被选过的非中心点oh，计算oh代替oi的总代价Tcih，并记录在S中。
（4） 如果S中有小于0的记录，则找出S最小，记录的非中心点，并用该非中心点代替被选择的中心点，重新组建k个划分的簇。
（5） 如果S中所有的记录都大于等于0，则不再划分新的簇。
总代价为：Tcih=∑n1cjhi 。 其中n为所有节点数；cjhi表示oj在oi被oh代替后所产生的代价。每一个oi被oh代替后，对于非中心点oj，有四种情况需要考虑(如┩1~图4所示)。
（1）oj当前在oi所在簇内，但oh代替oi后，oj被划分到了中心点om所在的簇。此时cjhi=d(j,m)－d(j,i)。
（2） oj当前在oi所在簇内，但oh代替oi后，oj被重新划分到了中心点oh所在簇，此时cjhi=d(j,h)－d(j,i)。
（3） oj当前在中心点om所在簇内，但oh代替oi后，oj被重新划分到了中心点oh所在簇，此时cjhi=d(j,h)－d(j,m)。
（4） oj当前在中心点om所在簇内，但oh代替oi后，oj仍在中心点om所在簇，此时cjhi=0。
图中实线为oh代替oi前oj的所属关系，虚线为代替后oj的所属关系。
3.2 层次方法
层次方法是根据某种给定的条件对数据集进行层次的分解，有凝聚和分裂2种方式［8］。
凝聚采用自底向上的策略，先将每个对象作为独立的簇，然后合并各个簇，满足用户指定的终止条件时停止。凝聚方法有AGNES算法等。
分裂采用自顶向下的分类策略，先将所有对象作为一个簇，然后将该簇细分为越来越小的簇，满足用户指定的终止条件时停止。分裂方法有DIANA算法等。
3.2.1 AGNES算法
AGNES算法采用对象间的欧氏距离作为评价2个簇间距离的标准［9］。算法基本思想：
（1） 将每个对象作为独立的初始簇。
（2） 将欧氏距离最小的2个对象所在簇进行合并，组成一个新的簇。
（3） 达到用户指定的簇的数目时终止。
3.2.2 DIANA算法
DIANA算法以簇的直径和平均相异度为划分层次的标准［10］。其中，簇的直径是指簇中任意两对象间的最大欧氏距离，平均相异度指平均距离：
ИИdavg(Ci,Cj)=∑x∈Ci∑x∈Cj|x-y|/(ninj)И
式中：ni是Cj中包含属性的个数;nj是Cj中包含属性的个数。算法基本思想：
（1） 将所有对象作为一个整体划分到同一个簇。
（2） 在所有簇中挑选出簇直径最大的簇，并在该簇中选取一个与其他点平均相异度最大的点作为一个新簇，然后选取原簇中到新簇距离小于等于到原簇距离的点放入新簇中。
（3） 循环(2)直到满足用户指定簇的数目为止。
4 几种算法的比较
关联规则方法主要用于对事物数据库进行数据挖掘，在商业领域使用得相对频繁一些。分类和聚类方法则用于对关系数据库进行数据挖掘，通过分析有属性描述的数据库元组来构造模型。
在实际应用过程中，不同方法有不同的优点和缺点。下面对本文提出几种算法的时间复杂度、使用范围、依赖条件、误差估计进行比较，如表1所示。
表1 几种算法比较
算法时间复杂度使用范围依赖条件误差估计
ApraoriO|Ck||Lk－1|k2小数据集最小支持度较小
kNNO(n)小数据集最临近数目小
决策树O(n×n)数据完整性较高的数据类别属性较大且与评估函数有关
贝叶斯分类O(n×m)完全独立数据和函数依赖数据先验概率较小
k-平均O(n×k×t)簇密集数据且簇平均值可计算簇的数目k较大且与孤立点的数目有关
PAMO(k×s×s+k(n－k))小数据集簇的数目k小
AGNESO(n×n)n较小的数据簇的数目k较小
DIANAO(n×n)n较小的数据簇的数目k较小
从表1可以看出，不同算法在不同应用上有各自的优缺点。如kNN算法时间复杂度最小，然而仅限于小数据集，对于数据集较大的情况，则可选用决策树和贝叶斯分类；k-平均算法对簇密集型数据有很高的效率。在实际应用中可以根据需要将几种算法结合，以达到更高的效率。
5 结 语
数据挖掘使信息处理技术从简单的数据存储转入更为高级的知识发现阶段，它正以一种全新的理念改变着人类信息管理方式。本文分析了3种数据挖掘算法的基本思想，并对不同算法进行了比较，指出了各算法的优缺点及使用范围，并展望了各算法对不同特征数据集的应用前景。
数据挖掘算法论文:基于粗糙集和遗传算法的数据挖掘方法
摘要：运用粗糙集和遗传算法的理论，为大型的数据挖掘提供了一种新的方法。首先通过粗糙集理论对数据进行预处理，然后对属性简约，最后通过遗传算法进行规则提取，寻找最优解。
关键词：粗糙集；遗传算法；数据挖掘；知识发现
数据挖掘[1]又称知识发现，是从大量的、不完全的、有躁声的、模糊的实际数据中，提取隐含在其中的、人们事先不知道的、但又很有用的知识和信息的过程。它的一般步骤如下：提出问题->数据准备->数据整理->建立模型->评价和解释。它是数据库研究、开发和应用最活跃的一个分支，是多学科的交叉领域，涉及数据库技术、人工智能、机器学习、神经网络、数学、统计学、模式识别、知识库系统、知识获取、信息提取、高性能计算、并行计算、数据可视化等多方面的知识。
1 粗糙集与遗传算法的基本概念
粗糙集(Rough Set, RS)[2]作为一种全新的数学概念,为处理具有不完整、不一致及不确定性特征的信息提供了新的有效工具,它的主要特点之一是无须提供问题所需处理的数据集合之外的任何先验信息。相对于许多其他处理不确定知识的方法来说更具客观性,并且和其他分析方法有机结合,进一步增强对不确定问题的处理能力。
定义1：信息系统S可表示为S=(U,A,V,f),其中U是对象的非空有限集合,称为论域;A是属性的非空有限集合;V=∪a∈AVa,Va是属性A的值域,f:U×AV是一个信息函数,他为每个对象的每个属性赋予一个信息值。
如果属性集A可以分为条件属性集C和决策属性集D ,即C∪D = A ,C∩D =Ф,则该信息系统称为决策系统或决策表,其中D 一般只含有一个属性。
定义2：在知识表达系统S 中,对于一属性集P∈A,对象x,y∈U,二元等价关系IND(P) ={(x,y)∈U×U | 所有的a∈P, f(x,a)=f(y,a)}称为S 的不可分辨关系。不可分辨关系是一个等价关系,通过一个不可分辨关系,可以得到一个决策系统的划分。
定义3：给定信息系统S=(U,A),B∈A ,对B中的属性a,如果IND(B)≠IND(B-{a}),则说属性a是必要的(Indispensable),否则称a是不必要的(Dispensable)。
遗传算法( Genetic Algorithm, GA)[3]起源于对生物系统进行的计算机模拟研究，是模拟生物在环境中的遗传和进化过程而形成的一种自适应优化概率搜索算法。它的流程主要模仿的 是生物遗传进化过程中的选择、交叉和变异操作，从而完成对问题最优解的自适应搜索过程。流程主要包括染色体编码、产生初始群体、计算适应度、进化操作等几大部分。
遗传算法的搜索过程是从一群初始节点开始搜索,而不是从单一的初始点开始搜索,这种机制意味着搜索过程可以有效地跳出局部极值点。既可以完成极值点领域内解的求精,也可以在整个问题空间实施探索,得到问题全局最优解的概率大大提高。
2 粗糙集与遗传算法在数据挖掘中的应用
粗糙集算法与遗传算法结合,能有效地提高挖掘效果,具有实际应用的可行性。其基本思想是：首先通过粗糙集对信息表中的数据缺损进行处理；然后对于信息表中的数据，根据已定义的可辩识距阵，通过属性简约算法进行属性简约和知识发现；最后对知识发现的规则通过遗传算法进行优化，找出最主要的规则。主要包括以下几个方面：
2.1 数据预处理
数据预处理用于对原始数据的采样、收集、整理，对于不同途径获取来的数据不一定能够得到有效的信息，所以数据的预处理是非常必要的。包括连续属性的离散化和不完备数据的填补，由于粗糙集只能处理离散的数据，所以还必须对连续的数据离散化，而属性离散化的关键在于选取合适的断点对条件属性进行划分[4]，如可采用基于属性重要性的离散化算法。由于数据采集的不完整性，使数据库中很大一部分数据都存在缺失，因此对输入的数据必须进行必要的处理如采用均值法、频率统计法等对数据进行补齐。
2.2 属性简约
粗糙集处理决策表时，数据约简是核心内容，一般是约去过剩的条件属性，用最少的属性区分不同的决策，提供同样多的信息，使决策表的决策属性和条件属性的依赖关系不发生变化。简约后的属性集称为属性的约简集，约简集通常不唯一，找到一个信息表中的约简集不是在一个多项式时间里能够解决的问题，求最小约简集（含属性个数最少的约简集）同样是一个困难的问题，实际上它是一个NP-hard问题，因此根据已定义的可辩识距阵，有如下的属性简约算法：
① 计算属性表的可辩识距阵。
② 对于可辩识距阵中的所有取值为非空集合的元素Cij建立相应的析取逻辑表达式。
③ 将所有析取逻辑表达式进行合取运算，得到一个合取范式。
④ 将合取范式转换为析取范式形式。
⑤ 输出属性约简结果，其中析取范式中的每个合取项对应一个属性约简的结果，每个合取项中所包含的属性组成的约简后的条件属性集合。
2.3 决策规则提取
经过第二步属性简约后，属性个数减少了，但是得出的规则数量依然可能过多，不利于得到用户最想要，最重要的规则，因此我们会更希望关心具有较多共同特性的规则，必须把简约后生成的规则集里那些具有大量共同特征的规则再次提取出来，面对这种优化问题，遗传算法是个强有力的工具。其步骤是编码产生原始种群，计算个体适应度，选择个体，交叉，变异操作，然后一代一代进化最后找出最优解。
（1）编码，是进行遗传算法的重要步骤，编码方案的选取很大程度上决定于问题的性质和要求，同时也决定了对随后的遗传算子的设计。如可以将数据离散化后的属性值定义在2的n次方之间[5]，采用二进制编码方法对每个数字编码，像属性值3用编码表示就是0011；
（2）产生初始种群。随机选取一些个体作为初始种群；
（3）确定评价函数。数据挖掘的目的是挖掘出具有最多相同特征的规则，因此评价函数的选取时应当把能够匹配简约表中最多的属性的规则评价为最优规则；
（4）遗传操作。交叉操作是将规则编码的某几位互相置换，变异操作是将规则编码的某些二进制位按位取反。这样通过规则集中任意的两两组合会形成新的规则集。然后经过每个规则的评价函数确定当前的最优规则，这样经历数代遗传之后就可得到相对最优的规则。
3 公司录取情况数据挖掘应用实例
下面用一个实例来说明本文使用的数据挖掘方法。某公司每年都会收到大量的求职信息表，并从中雇用一定数量的员工，对于员工的雇用，公司以往都是通过面试及给领导的感觉来雇用的，因此公司希望能够从以前的录用中找出一个大体的评判标准以便于以后录用时作为参考，由于以往几年累计求职的员工太多，情况比较复杂，因此公司希望这个标准能够简单明了。通过本文提出的方法，可以很好的解决该公司的需求，以下以该公司求职人员的原始求职表中的一部分作为演示，“?”代表求职表中该属性没有写明情况，如表1所示：
按属性简约的算法，通过决策表的可辩识距阵，我们可以得到算法第3步后的合取范式为：
F(d,e,f,a)=(e∨a)∧(d∨e∨a) ∧(d∨e) ∧(e∨f∨a) ∧(d∨e∨f) ∧(d∨e∨a) ∧(d∨e∨a) ∧(d∨e∨a) ∧(d∨a) ∧(e) ∧(e∨a) ∧(d∨e∨f∨a) ∧(d∨e∨f) ∧(d∨e∨f∨a) ∧(d∨e∨f) ∧(d∨e∨a)
其中每一个析取项对应于可辩识距阵中的一个元素，d，e，f，a分别对应属性学历、经验、法语、仪表，按算法第4步简化后可以得到F(d,e,f,a)=(e∧a) ∨(e∧d)。由此可见，在原始决策表给出的这部分信息中与决策有关的是d，e，a。
通过粗糙集的属性约简，可以得到以往公司录用时真正看重的一些属性，通过这些属性，再用遗传算法找出其中最主要的规则。例如约简表中某一行在学历、经验、仪表上的值为201，则编码就是10,00,01。随机选取8个个体作为初始种群，评价函数以能够匹配约简表中最多行属性的规则成为当代的最优规则。
算法定义为一个8元组：
SGA=（C，E，P0，M，Ф，Г，Ψ，T）
C表示对个体采用二进制编码；E表示个体适应度评价函数f(x)；P0表示初始种群随机选取的8个规则；Ф表示采用赌按比例选择算子；Г表示中间位单点交叉算子；Ψ表示基本位变异算子；T表示执行20代上述遗传算法后停止。
最后得到最佳个体00,01,01，即学历MBA，经验水平一般，仪表良好的评判标准，凡在此标准附近或高于此标准的，可以考虑录用。
4 结语
在数据挖掘中应用粗糙集和遗传算法，粗糙集可以解决数据不精确、不完整的问题，并进行属性简约，遗传算法可以从大量规则中提取出最优的规则，提高了分析系统的效率。本文将粗糙集和遗传算法在数据挖掘中相结合，给出实例说明该方法的可行性。在今后的研究中还将继续结合其他的方法进行研究，提高对知识的发现能力。
数据挖掘算法论文:数据挖掘分类算法研究与探讨
摘要：数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力将会不停地促进它的发展。随着数据库应用的不断深化，数据库的规模急剧膨胀，数据挖掘已成为当今研究的热点，每年都有新的数据挖掘方法和模型问世，特别是其中的分类问题，引起了越来越多的关注。
关键词：数据挖掘；分类；算法
随着计算机技术特别是数据库技术的迅猛发展，以及人类活动范围的扩展、生活节奏的加快，人们能以更快速更容易更廉价的方式获取和存储数据，这就使得数据及其信息量以指数方式增长。面对这些极度膨胀的数据，人们受到“信息爆炸”和“数据过剩”(Data Glut)的巨大压力。这些海量数据如果不能有效利用起来，将只会成为“数据垃圾”。对人类社会进步起到巨大作用的是知识。 数据挖掘就是从大量数据中发现潜在规律、提取有用知识的方法和技术[1]。数据挖掘包含的内容很多，其中很重要的一个方面是分类规则挖掘。
分类技术在很多领域都有应用，例如可以通过客户分类构造一个分类模型来对银行贷款进行风险评估；当前的市场营销中很重要的一个特点是强调客户细分。客户类别分析的功能也在于此，采用数据挖掘中的分类技术，可以将客户分成不同的类别，比如呼叫中心设计时可以分为：呼叫频繁的客户、偶然大量呼叫的客户、稳定呼叫的客户、其他，帮助呼叫中心寻找出这些不同种类客户之间的特征，这样的分类模型可以让用户了解不同行为类别客户的分布特征；其他分类应用如文献检索和搜索引擎中的自动文本分类技术；安全领域有基于分类技术的入侵检测等等。机器学习、专家系统、统计学和神经网络等领域的研究人员已经提出了许多具体的分类预测方法。下面对几种主要的分类方法作简要的研究与探讨：
1 基于判定树的归纳分类
判定树是一个类似流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根节点。由判定树可以很容易得到“IF-THEN”形式的分类规则。方法是沿着由根节点到树叶节点的路径，路径上的每个属性-值对形成“IF”部分的一个合取项，树叶节点包含类预测，形成“THEN”部分。一条路径创建一个规则。判定树归纳的基本算法是贪心算法。
算法描述如下：判定树归纳分类[2]是一种从训练样本集中推理出判定树表示形式的分类规则的方法。它采用自顶向下的递归方式，判定树的最顶节点是根结点，树的内部结点表示在一个属性上的测试，从该结点向下的每个分支代表一个测试输出，在树的叶结点得到分类预测。从根到叶结点的一条路径就对应着一条合取规则，整棵判定树就对应着一组析取表达式规则。判定树的优点在于它的直观性和易理解性，判定树方法不仅能做出分类和预测，而且它的生成过程、分类、预测以及从判定树所提取的分类规则都具有很强的可理解性。
算法策略如下：①判定树以代表训练样本的单个节点开始；②如果样本都在同一个类，则该节点成为树叶，并用该类标记；③否则，基于启发式或统计式策略选择能够最好地将样本分类的属性，将样本分类；④对测试属性的每个已知的值，创建一个分枝，并以此为根据划分样本；⑤使用同样的过程，递归地形成每个划分上的样本判定树。
停止划分的条件：给定节点的所有样本属于同一类：没有剩余属性可以用来进一步划分样本，此时使用多数表决(用训练集中的多数所在的类标记它)；没有样本剩余。
2 KNN法(K-Nearest Neighbor)
KNN(K Nearest Neighbors)算法[3]又叫K最临近方法，总体来说KNN算法是相对比较容易理解的算法之一，假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类，KNN就是计算每个样本数据到待分类数据的距离，取和待分类数据最近的K各样本数据，那么这个K个样本数据中哪个类别的样本数据占多数，则待分类数据就属于该类别。
KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种Reverse KNN法，能降低KNN算法的计算复杂度，提高分类的效率。
该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
3 VSM法
VSM法即向量空间模型(Vector Space Model)法，由Salton等人于60年代末提出。这是最早也是最出名的信息检索方面的数学模型。其基本思想是将文档表示为加权的特征向量：D=D(T1,W1;T2,W2;…;Tn,Wn)，然后通过计算文本相似度的方法来确定待分样本的类别。当文本被表示为空间向量模型的时候，文本的相似度就可以借助特征向量之间的内积来表示。
在实际应用中，VSM法一般事先依据语料库中的训练样本和分类体系建立类别向量空间。当需要对一篇待分样本进行分类的时候，只需要计算待分样本和每一个类别向量的相似度即内积，然后选取相似度最大的类别作为该待分样本所对应的类别。
由于VSM法中需要事先计算类别的空间向量，而该空间向量的建立又很大程度的依赖于该类别向量中所包含的特征项。根据研究发现，类别中所包含的非零特征项越多，其包含的每个特征项对于类别的表达能力越弱。因此，VSM法相对其他分类方法而言，更适合于专业文献的分类。
4 Bayes法
Bayes法是一种在已知先验概率与类条件概率的情况下的模式分类方法，待分样本的分类结果取决于各类域中样本的全体。
设训练样本集分为M类，记为C={c1,…,ci,…cM}，每类的先验概率为P(ci)，i=1,2,…,M。当样本集非常大时，可以认为P(ci)=ci类样本数/总样本数。对于一个待分样本X，其归于cj类的类条件概率是P(X/ci)，则根据Bayes定理，可得到cj类的后验概率P(ci/X)：
P(ci/x)=P(x/ci)・P(ci)/P(x) （1）
若 P(ci/X)=MaxjP(cj/X)，i=1,2,…,M，j=1,2,…,M，则有x∈ci（2）
（2）式是最大后验概率判决准则，将（1）式代入（2）式，则有：
若P(x/ci)P(ci)=Maxj[P(x/cj)P(cj)]，i=1,2,…,M,j=1,2,…,M，则x∈ci，这就是常用到的Bayes分类判决准则。经过长期的研究，Bayes分类方法在理论上论证得比较充分，在应用上也是非常广泛的。
Bayes方法的薄弱环节在于实际情况下，类别总体的概率分布和各类样本的概率分布函数(或密度函数)常常是不知道的。为了获得它们，就要求样本足够大。另外，Bayes法要求表达文本的主题词相互独立，这样的条件在实际文本中一般很难满足，因此该方法往往在效果上难以达到理论上的最大值。
5 神经网络
人工神经网络的研究至今已有60多年的历史。1943年，心理学家McCulloch和数学家Pitts合作，提出了形式神经元的数学模型，即MP模型[4]，从此，神经网络引起了许多科学家的兴趣。但随着对感知机为代表的神经网络的功能和局限性的深入分析等原因，使神经网络的研究陷入低潮。但是仍有一些学者坚持研究，并取得了一些成果，出现了Grossberg的ART模型和Kohonen的SOM模型。1982年，通过引入能量函数的概念，Hopfied研究了网络的动力学性质，并用电子线路设计出相应的网络，进而掀起了神经网络新的研究高潮。1986年，Rumellhart和McCllel-land等提出了PDP理论，尤其是发展了多层前向网络的BP算法，成为迄今应用最普遍的学习算法。
神经网络可解决目前数据挖掘存在几个方面的问题：
1) 数据的量度和维度，面对大量复杂、非线性、时序性与噪音普遍存在的数据；
2) 数据分析的目标具有多样性，使其在表述和处理上都涉及到领域知识；
3) 在复杂目标下，对海量数据集的分析，目前还没有现成的且满足可计算条件的一般性理论的方法。然而，神经网络在对噪声数据的高承受能力以及对未经训练的数据分类模式的能力方面有很大优势。因此设计出基于神经网络的数据挖掘方法，并将其用于真实世界问题，是可行且也是必要的。
人工神经网络可用于数据挖掘的分类、聚类、特征挖掘、预测和模式识别等方面，因此，人工神经网络在数据挖掘中占有举足轻重的作用。
总之，数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力将会不停地促进它的发展。每年都有新的数据挖掘方法和模型问世，人们对它的研究正日益广泛和深入。尽管如此，数据挖掘技术仍然面临着许多问题和挑战：如数据挖掘方法的效率亟待提高，尤其是超大规模数据集中数据挖掘的效率；开发适应多数据类型、容噪的挖掘方法，以解决异质数据集的数据挖掘问题；动态数据和知识的数据挖掘；网络与分布式环境下的数据挖掘等；另外，近年来多媒体数据库发展很快，面向多媒体数据库的挖掘技术和软件今后将成为研究开发的热点。
数据挖掘算法论文:数据挖掘技术及算法综述
摘要:数据挖掘是目前非常热门的一门交叉学科,涉及到很多学科的研究领域。文中对数据挖掘的概念、实施步骤及各种算法进行了比较详细的归纳,并且对数据挖掘技术将来的研究方向也进行了预测。
关键词:数据挖掘;聚类算法;关联规则;决策树;遗传算法
1 引言
数据挖掘是一个多学科的交叉领域,这些学科包括数据库技术、机器学习、统计学、模式识别、信息检索、神经网络、基于知识的系统、人工智能、高性能计算和数据可视化等[1]。目前,对于数据挖掘方面的研究已经取得了很大的进展,开发出了许多新的数据挖掘算法、系统和应用。本文将先对数据挖掘的概念及实施步骤进行说明,然后将分类归纳数据挖掘中的各种常见算法,最后对数据挖掘目前的研究方向进行预测。
2 数据挖掘的概念及流程
2.1 数据挖掘的概念
简单地说,数据挖掘就是从大量的数据中“挖掘”知识,即从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道、但又是潜在有用的信息和知识的过程。它是一种决策支持过程,可以从企业数据库的大量数据中,挖掘出潜在的模式,预测客户的行为,帮助企业的决策者做出正确的判断,从而减少投资的风险,获得更大的利润。
2.2 数据挖掘的流程
一般来讲,数据挖掘的整个过程由五个步骤组成:
1) 数据挖掘的最后结果是不可预测的,但是要探索的问题应该是有预见的,为了数据挖掘而进行数据挖掘,是不可取的。因此,清晰地定义出业务问题,认清数据挖掘的目的是数据挖掘的第一步,也是很重要的一步。
2) 数据准备[2],数据准备又可以分成数据选择,数据预处理,数据转化三个步骤。数据选择,是从大量与业务对象有关的数据中选择出适合进行数据挖掘的数据;数据预处理,包括进行数据清洗,数据推测,数据转换等。数据清洗,指的是清除掉一些明显的噪声数据,提高数据的质量;数据推测,是因为在前面两步中,也许会出现数据不全的情形,所以进行适当的推算,补齐所需的数据;数据转换,是将数据转换成一个分析模型,这个分析模型是针对数据挖掘算法建立的,建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键;数据转化,则是在做完前面的步骤以后,适当的缩减即将进行分析的数据库规模,以上这些工作会直接影响到数据挖掘时的效率和准确性,同样很重要。
3) 数据挖掘,这是整个数据挖掘过程中最重要的一步,即使用适当的数据挖掘算法对刚才处理出的数据进行分析,进而得到可能的模式模型。根据不同数据的特点以及用户不同的需求,对同样的任务,可以选用不同的算法,目前常见的算法包括聚类算法、关联分析、分类算法、遗传算法等。
4) 结果评价,通过上述步骤得到的模式模型,并不一定是真实有效的,甚至可能会是和实际情况完全相反的,所以还需要对得到的结果进行评价。这一步使用的方法包括用数据代入进行验证,也可以根据常规的经验进行一些判断,一般由数据挖掘具体操作而定。如果没有得到合适的模式模型,就需要重新选择数据,甚至需要选用其他的数据挖掘算法,因此,数据挖掘的过程往往都是一个不断反复的过程。
5) 知识同化,完成上述步骤后,如果得到了可以接受的模式模型,就需要进一步把得出的模型形象化,运用到所需的信息系统中去。
3 数据挖掘的常见算法
数据挖掘常用的分析方法包括聚类算法(Cluster Algorithm)、关联规则(Association Rules)、决策树算法(Decision Tree Algorithm)、遗传算法(Genetic Algorithm)等。
3.1 聚类算法
聚类是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度的相似,而不同类中的数据最大程度的不同。常见的聚类算法主要包括层次聚类算法(Hierarchical Clustering Method)、分割聚类算法 (Partitioning Clustering Method)、基于密度的方法(Density-Based Methods)、基于网格的方法(Grid-Based Methods)等[3]。
1) 层次聚类算法,是通过将给定的数据集组织成若干组数据,并形成一个相应的树状图,进行层次式的分解,直到某种条件满足为止,具体又可分为“自底向上”和“自顶向下”两种算法[4]。这两种算法的思路正好相反,前者是将每个对象都作为一个原子聚类,再进行聚合,最后得到相应的结果,而后者是将所有对象看成一个聚类,再进行分解。CURE算法、CHAMELEON算法、BIRCH算法等是比较常用的层次聚类算法。
2) 分割聚类算法,是先将数据集分成k个分组,每一个分组就代表一个聚类,然后从这k个初始分组开始,然后通过反复迭代的方法改变分组,使得每一次改进之后的分组方案都较前一次好,最终使同一分组中的记录越来越近,不同分组中的记录原来越远,从而得到最优解。使用这一思想的主要算法有K-means算法、K-medoids算法、CLARANS算法等。
3) 基于密度的方法与其它方法的最要区别在于:它不基于各种距离,而是从数据对象的分布密度出发,将密度足够大的相邻区域连接起来,从而可以发现具有任意形状的聚类,并能有效处理异常数据,它的代表算法有DBSCAN算法、OPTICS算法、DENCLUE算法等。
4) 基于网格的方法则是从对数据空间划分的角度出发,利用属性空间的多维网格数据结构,将数据空间划分为有限空间的单元,以构成一个可以进行聚类分析的网格结构。该方法的主要特点是处理时间与数据对象的数目无关,但与每维空间划分的单元数相关,而且,这种方法还与数据的输入顺序无关,可以处理任意类型的数据,但是聚类的质量和准确性降低了,它的代表算法有STING算法[5]和CLIQUE算法等。
3.2 关联规则
关联规则是数据挖掘研究的重要内容,它描述了数据库中一组对象与另一组对象之间存在的某种关联关系。从大量商业记录中挖掘有趣的关联关系,有助于许多商务决策的制定,如分类设计、交叉购物等。关联规则是形如A=>B的蕴涵式,表示形式如pen=>ruler [支持度=20%,置信度=60%],支持度和置信度分别反映规则的有用性和确定性,这条规则就意味着所有的顾客中有20%的人同时购买了钢笔和直尺,而买了钢笔的顾客的60%也买了直尺。在关联规则中,所有支持度大于最小支持度的项集称为频繁项集,简称频集。如果一条关联规则同时满足最小支持度阈值和最小置信度阈值,就认为它是有趣的,并称为强关联规则。
关联规则挖掘一般分为两步:1) 找出所有频繁项集,即满足最小支持度的项集;2) 从频繁项集中产生强关联规则。最为著名的关联规则挖掘算法就是R.Agrawal和R.Srikant于1994年提出的挖掘布尔关联规则中频繁项集的原创性算法Apriori。它使用一种称作逐层搜索的迭代方法,k项集用于探索(k+1)项集。首先,通过扫描数据库,累积每个项的计数,并收集满足最小支持度的项,找出频繁1项集的集合。该集合记作L1。然后,L1用于找频繁2项集的集合L2,L2用于找L3,如此下去,直到不能找到频繁k项集。找每个Lk需要一次数据库全扫描。
但是,Apriori算法也有其不足之处:1) 可能产生大量的候选集;2) 生成每个Lk都需要重复扫描数据库。后来,陆续出现了一系列Apriori算法的改进算法,以及其他的关联规则挖掘算法,比如RIApriori算法、Apriori-improve算法、FP-growth算法等,这大大提高了关联规则挖掘的速度和准确性,也推动了关联规则挖掘理论的进一步发展。
3.3 决策树算法
决策树是一种类似于流程图的树结构,每个内部节点(非树叶节点)表示在一个属性上测试,每个分支代表一个测试输出,而每个树叶节点(或终节点)存放一个类标号。决策树算法主要围绕决策树的两个阶段展开:第一阶段,决策树的构建,通过递归的算法将训练集生成一棵决策树;第二阶段,由测试数据检验生成的决策树,消除由于统计噪声或数据波动对决策树的影响,来达到净化树的目的,得到一棵正确的决策树。常见的决策树算法主要有ID3算法[6]、C4.5算法、CART算法、SPRINT算法等。
3.4 遗传算法
遗传算法是基于进化理论,并采用遗传结合,遗传变异,自然选择等设计方法的一种进化计算算法的优化算法。进化计算算法的基础是生物进化,随着时间的流逝,进化出更好的或更适应的个体。在数据挖掘中,遗传算法可以用于评估聚类、关联规则等算法的适合度。在应用遗传算法解决问题时,最困难的一步应该是怎样将问题建模成一组个体的集合,然后在计算中,首先假设一个初始模型,然后对其反复进行杂交技术和变异技术的算法,最后用适应度函数确定初始集合中应该保留的那个最优个体。这个算法的优点在于容易并行化,但是对问题进行建模很困难,杂交变异过程以及适应度函数也很难确定。
4 结束语
随着数据量的积累和数据库种类的多样化,数据挖掘的应用前景非常的广阔,从上面对各种常见算法的归纳可以看出,每种算法都有局限性,很难采用单一的方法解决相应的问题,因此,多方法融合将成为数据挖掘未来的发展趋势。
数据挖掘算法论文:遗传算法与网络数据挖掘
摘要:计算机网络发展迅速,网络数据挖掘已经成为一个重要的研究领域。网络数据分布范围广,数据量大,结构多样,时间跨度高。如何对这些海量数据进行高效查询成为研究人员关注的问题。遗传算法在搜索的过程中采用群体搜索方式,有利于得到最优查询结果。在数据查询、查询优化和分布式数据挖掘等方面使用遗传算法,能够从不同角度大大提高查询效果。
关键词:网络数据挖掘;遗传算法;查询优化
随着万维网使用越来越广泛,网络数据挖掘已成为一个重要的科学研究领域,得到越来越多的科研人员的重视。设计算法从已有信息中发掘新知识,根据用户情况定制信息,学习用户行为是网络数据挖掘所面临的主要问题。
在网络工具中结合使用人工智能可消除网络检索中的人为因素。在客户端和服务器端分别安装智能系统,使计算机通过Internet在Web服务器上进行高效的知识发掘。通过网络服务器检索知识已经引起机器学习、人工智能等领域学者的普遍注意。然而,网络数据数量大、分布地域广泛、类型差异大,要开发一个智能工具对这样的数据进行检索难度很大。
网络挖掘技术在智能网络的发展中发挥着重要的作用。网络数据具有多样性、分布广泛等特点,按照现有的算法对网络数据进行搜索具有相当局限性。与其他传统的优化算法相比,遗传算法在搜索的过程中采用群体搜索方式,有利于达到全局最优。遗传算法可采用和进化出更优的复合目标函数,以便在动态而负责的网络环境中实现高效的数据检索和知识预测。A.Broder等人将网络看作是一个由无数网页组成的集合S,这些网页构成邻接关系,使用适应性函数f实现对这些网页的评估[1]。
f:SR+
搜索引擎通过f函数的最优值输出搜索结果。通过激活基于遗传算法的应用来使这网络关联的搜索更加高效。在本文第二节中主要对网络数据挖掘进行讨论,第三节介绍在网络数据挖掘中使用遗传算法的案例。
1 网络数据挖掘
1.1 网络数据的特点
S. Chakrabarti.指出网络数据挖掘即是指在万维网中应用数据挖掘技术来提取人们感兴趣的模式和知识[2]。网络数据挖掘由于网络的自身特点已经成为一个独立而重要的研究方向。对于网络数据的特点可做以下归纳:未经分类,海量,分布性广泛,多种媒体类型并存,半结构化,时间跨度大,维度高。
本文用图1表示网络。
在图1中,结点表示网页,有向边表示超链接,这些超链接包含了重要的信息,有助于实现信息的高效检索。例如,在图1中,许多结点的链接都指向A结点,这就表明,结点A所代表的页面很可能是某些领域的权威[3]。通常情况下,一个网站被描述成若干网页的集合,在这个集合中,每个成员包含的对其他成员的连接数远多于外部网页。
按照网络数据挖掘的深度层次,可以将网络数据挖掘归为以下几类:
1)基于内容的数据挖掘:这种数据挖掘方式首先会对页面中涉及的内容进行归纳总结,生成摘要。而页面的内容种类很多,诸如文本、图片、HTML代码到图和表等,根据这些内容对网页进行分类,然后设计相应的算法对这些网页进行检索。对搜索结果进行数据挖掘同样是网络内容挖掘的一个组成部分。其中包括了对结果进行总结,将他们按照层次、标题和摘要中的短语对文档进行归类,以及对多个搜索引擎的搜索结果进行合成和重组。最后将对数据进行元数据挖掘。在信息检索、文本挖掘、图像挖掘和自然语言处理等方面的应用都属于这些类型。
2)基于网络信息结构的数据挖掘:这种挖掘方式涉及到通过万维网中文档之间的超链接来提取知识,这一做法往往能够发现诸多网页中某方面主题的权威页面。结构挖掘方面的重要应用包括了查找重要的页面、关联页面和主页,识别重要的模式和它们之间的相互关系。然而,网页的信息不单单来自于这个页面本身所含的内容,还来自于其相邻的页面。在这里同时使用基于内容的挖掘和基于结构的挖掘可以达到效果互补的目的。
3)基于网络数据用途的挖掘:此类数据挖掘从本质上说是对数据用途的挖掘。以网站为例进行说明:在客户端,通过用户的浏览历史记录来搜集数据;在服务器端,通过请求日志搜集数据。通过这样的数据挖掘,可以发现用户访问页面的类型,访问的时间和访问持续的时间,以及这个页面被引用的次数。此类信息有助于实现对页面的整理,最终实现高效快速的信息检索。在商业领域中使用这一技术可以实现客户价值评估、产品潜力发掘、客户行为预测等。
1.2 网络数据挖掘的组成和方法
Etzioni. O.提出可将网络数据挖掘的过程分成信息检索、信息提取、知识集成和分析四个部分[4]。图2对网络数据挖掘的四个组成部分进行说明:
图2
信息检索(Information Retrieval,IR):信息检索是自动对网络中相关联的文档进行搜索,其过程主要包括对文档的表示、索引和搜索。
信息提取(Information Extraction,IE):信息提取是在文档被检索之后,自动从中提取知识,这一过程主要实现对文档中主要字段的语义进行识别。
信息集成(Generation):这一过程对已有的文档进行归纳,得到概要知识。在这里将使用分类、规则关联等模式识别和机器学习的技术来提取信息。例如,将一个网站的主页和其他页面区分开就是一个集成工作。
数据分析(Analysis):这一阶段将对信息集成阶段所生成的模式进行解释说明。数据分析是一个数据驱动的问题,必须在数据充足的前提下才可能提取有用的信息。
1.3 网络数据挖掘面临的挑战与局限性
由于网络数据本身的特身,网络数据挖掘面临如下问题:1)由于网络数据的匿名性和人为破坏而造成了数据的不可靠。2)存在噪声。3)网络数据是动态的,且存在时间短暂。3)网络数据缺乏结构化处理,且类型各异。4)语义存在二义性。5)数据高度冗余。使用我们现有的工具和算法难以应付如此复杂的网络数据。在下一节中提出在查询中使用遗传算法实现对网络数据的搜索和数据挖掘的优化。
2 在网络数据挖掘中使用遗传算法
遗传算法和相关技术在网络数据挖掘领域的应用包括信息查询检索、查询优化、文档表示和分布式数据挖掘等[5],本文就信息查询和查询优化方面对遗传算法的应用进行阐述。
2.1 查询和检索
Marghny等人将遗传算法用于元数据搜寻[6],使用这一方法对标准搜索引擎的搜索结果以一种优化方式进行组合,生成更令用户感兴趣的页面,在文献[6]中对适配函数进行如下定义:
(a) 链接质量函数
n表示用户输入的关键字的个数,#Ki表示在链接L中关键字Ki出现的次数。
(b) 页面质量函数
m表示每个页面中总的链接数。
(c) 平均质量函数
Fmax(P)和Fmin(P)分别表示采用遗传算法后页面质量函数的最大值和最小值。Fmax(P)的最大值是m*n,而Fmin(P)的最小值是0.
研究人员分别使用Yahoo,Google,AltaVista和MSN这四个搜索引擎针对不同的主题下载了300个页面。在杂交点之后对选中的页面交换双亲的链接,以实现杂交。
2.2 查询优化
查询优化使用一种基于适度回馈机制的技术。使用回馈的目的是通过使用相关和无关文档集合来修改用户的查询,使用户的查询结果更接近于目标文档。将之前的查询得到的关键字添加到当前查询中,同时将早期文档中不相关的关键字删除,通过这种办法可以检索到更多的关联度更大的结果。
遗传算法在查询优化上能够发挥很大的作用。Z. Z. Nick和P. Themis.通过长期监控用户的浏览习惯创建用户模型[7]。使用遗传算法对用户查询进行修改,在这里文档和查询被表示成向量。每个个体被表示成查询向量,用染色体表示关键字的权重或者关键字出现或未出现的频率。M. Boughanem等人研制了一种新的查询优化技术,在这一技术中,通过使用遗传算法生成多个查询,对文档的不同区域进行搜索,最终得到最优查询结果[8]。
Leroy等人在文献[9]中解释了在对上下文进行动态查询时使用基于遗传算法的优化策略有助于提高偶然用户的查询效率。由于偶然用户在Internet上进行查询的时候只使用少数的关键字,这样得到的查询结果很少而且相当不精确。但是,大多数用户在查询时使用相同的搜索引擎,在某一主题的查询方面,可总结大多数用户的查询行为,从中提取有价值的信息,从而对偶然用户的查询要求能够进行更高效的处理。在遗传编程的实现上,每个染色体被设计成一个查询,它有五个位,每个位由一个适当的关键字填充。在计算染色体适应度时,将查询编码发送给查询引擎,查询引擎将返回十条最主要的文档。
3 小结
为了充分发挥网络的潜能,让网络查询更加智能化,需要对查询进行改进。在网络数据挖掘及其相关领域的研究在查询优化方面发挥着十分重要的作用。网络数据挖掘是一个快速发展的领域,在这个领域,研究人员提出各种方法对计算方法进行改进。在该文中,阐述了网络数据挖掘过程、组成、特点以及网络数据挖掘所面临的挑战。详细讨论了使用遗传算法对网络数据挖掘中不同问题的解决方法。
虽然使用遗传算法对网络数据进行挖掘很有发展潜力,但是目前这方面的应用和相关文献还比较有限,为研究人员的进一步研究留下很大的空间。
数据挖掘算法论文:电子商务中数据挖掘的基本算法与应用分析
摘要：数据挖掘技术是近些年来发展起来的一门新技术，通过该技术，人们可以发现数据后面潜藏的有价值的信息。数据挖掘已经成为解决当前企业信息系统中所面临的“数据爆炸”状况的最有效的方法，这也为决策者进行各种商业决策提供了科学的理论支持。该文将对数据挖掘的含义与基本算法进行阐述和分析，并对数据挖掘在电子商务中的具体应用进行分析探讨。
关键词：电子商务；数据挖掘；基本算法；应用分析
近些年来，基于电子计算机性能的不断提高、计算成本的不断下降以及数据管理技术的成功运用，企业商务往来的电子信息化程度也越来越高。与此同时，这也造成了大量的数据积累，形成了了“数据丰富而知识贫乏”的现象，这使得信息决策者难以从海量的数据中提取出具有信息价值的知识，数据挖掘技术的运用很好的解决了这个问题。
1 数据挖掘的含义
数据挖掘（Data Mining）可以定义为从大量的、不完全的、模糊的或者是随机的实际应用数据中，提取隐含的、同时又有潜在价值的知识与信息的过程。
数据挖掘可以扩展为以下几层含义：首先，数据源必须具备包含大量的、真实的数据的特点，数据源可以是不同数据仓库或者文件等；其次，在数据挖掘中发掘出的知识要可运用并且同时容易被理解。也就说，数据挖掘的本质目的在于寻找有用的知识，但是该知识需要被人们理解和接受；最后，数据挖掘通常是针对某一特定问题而进行的分析，往往不可能发掘出通用的知识，这些知识信息一般都具有相应的针对性，只有在特写的范围中才能够应用。
广义的角度来说，在数据挖掘中的知识是指具有一定规则的模式或者概念等，而信息与数据则是知识的理论源泉。也就是说对知识的发掘就是是从数据中挖掘出相应的规则与模式的过程，故而称之为数据挖掘。在数据挖掘中，数据源可以是多样的也可以是单一的，可以是分布式形态的，也可以是结构化形态的。
2 电子商务中数据挖掘的体系结构
当前电子商务是数据挖掘技术应用比较广泛的应用，这主要是归功于电子商务能够比较容易地满足数据挖掘所必需的因素，这些因素包括丰富的数据语言、可以自动收集可靠的数据并可将数据挖掘的结果转化为商务行为。然而，要想充分发挥数据挖掘技术在电子商务应用中的效率，数据挖掘技术需要将事务处理阶段的数据转存到相应的数据仓库中，并且要与电子商务行为有机结合起来。本文将电子商务中数据挖掘的体系结构概括3个主要部分，即商务数据定义、分析处理和顾客相互作用和。流程图如图1所示。
3 电子商务中数据挖掘的基本方法
3.1 路径分析
这种方法可以被用于确定在一个Web站点中最频繁访问的路径，其它一些与之有关路径的信息也可以通过路径分析得出。比如当70%的用户端在访问/company/product2的时候，从/company开始,而后经过company/news,/company/products/company/productl；80%的访问这个站点的顾客是从/company/products而开始的；65%的客户在浏览少于4个页面后便离开了。可以知道，第1条规则在/company/roduct2页面上有具有有用的信息，但是由于客户对站点进行的是迁回绕行方式的访问，因而这个有用信息并不十分明显。第2条规则则说明了客户访问站点通常不是从主页开始的，而是由/company/products开始的，假如这个页面上包含许多产品的目录类型的信息，将是一个不错的想法。第3条规则表明客户在网站上停留的时间。进过路径分析后，发现客户在该网站上浏览情况往往不超过4个页面时，就可以将相对重要的商品信息置于这些页面中，从而可以改进页面网站的结构设计。
3.2 关联规则分析
关联分析的最终目的是挖掘隐藏在数据间的相互关系，在电子商务中进行关联规则分析也就是找到客户对网站上不同文件之间访问的相互联系。在进行Web数据挖掘后，可以构建出关联关系模型，我们可以依据该模型更好地组织站点，从而减少用户过滤信息的负担。
3.3 序列模式分析
序列模式分析的重点在于分析不同数据之间的前后或者因果关系，也就是说在时间有序的事务集合中，去发现具有关联的内部事务模式。发现序列模式有助于电子商务的组织者对客户的访问模式进行预测，从而为客户提供个性化的服务，网站的管理人员可以依据浏览模式对访问者进行分类，而在页面上只展示出对应的访问链接。当访问者浏览到某一页面的时候，管理人员可以检查他的浏览所符合的序列模式，并且在比较显眼的位置进行“访问该页面的人员一般接着访问”的若干页面。
3.4 分类分析法
分类分析法的输入集通常是一组记录集合或者几种标记，这种分析法首先为每一个记录赋予一个相应的标记，也就是按标记分类记录，而后对这些标定的记录进检查，从而描述出这些记录的特征。在电子商务中通过应用数据挖掘，可以对不同消费群体进行分类，从而便于对某一类客户进行有针对性的商务活动。
3.5 聚类分析法
聚类分析法有别于分类规则法，其输入集合一般是一组未标定的记录，这也就是说该输入记录并没有进行任何分类。这种方法的目的是依据一定的规则，对记录集合进行合理划分，并且利用显式或者隐式的方法对不同的类别进行描述。当前已开发出许多聚类分析的工具，在电子商务中，通过对具有相似浏览行为的客户进行聚类，可以使管理员更多地了解客户信息，从而为其提供更适合、更满意的服务。
4 电子商务中数据挖掘的应用分析
本文将数据挖掘在电子商务中的典型应用概括为以下几个方面：
4.1 发现潜在客户
在对Web的客户访问信息进行数据挖掘中，可以利用分类技术在Internet上发现未来潜在的客户。对于电子商务从业者来说，得到这些潜在客户一般市场策略是，首先对现已存在的访问者进行分类，通常分为3种，即:“no customer”、“visitor once”、“visitor regular”。通过Web上的分类发现，管理人员可以识别出新客户和已经分类的老客户的一些具有共性的描述，这有助于对该新客户进行正确的分类。而后，依据其分类来判断这个新客户是否属于潜在的客户群体，从而决定是否要需要将这个新客户作为未来潜在的客户来对待。在确定客户的类型以后，管理人员就可以动态展示相应的Web页面，而Web页面的具体内容主要取决于客户与销售商提供的产品以及服务之间的关联规则。
4.2 驻留客户
现代电子商务平台使得传统客户与销售商之间的空间距离已经不存在了，在网络电子平台上，每一个客户来都有选择不同销售产品的权利，如何使这些客户在销售商自己的销售站点上驻留比较长的时间、使其对该网页产品产生更火的兴趣，对每一个销售商来说都是一个挑战。为客户在相应的网站上驻留更长的时间，就需要了解客户的浏览行为，掌握客户的兴趣与不同需求所，从而对页面内容进行动态调整，以此来满足客户的需求。对客户访问信息进行数据挖掘，就可以掌握客户的浏览行为，从而获取客户的兴趣及需求。在网络电子商务平台中的一个典型的序列，就代表了客户以页面的形式在该站点上导航的行为，运用数据挖掘中的序列模式分析技术，可以知道道客户的实际需求，从而为客户提供一些特有的商品信推广信息，从而使客户能保持对访问站点的兴趣。
4.3 对站点改进的设计
网络站点上页面内容的安排与连接，就像超市物品在货架上的摆设一样，需要将支持度与信任度较高的关联物品摆放在一起，从而有助于销售。通过Web上的关联规则分析，可以针对不同的客户对站点的结构进行动态调整，并进行相应的改进设计，从而使与客户访问有关联的文件之间的连接更为直接，这也有助于客户更容易地访问到预想的页面。当电子商务网站具有这样的便利性的时候，便可以给客户留下很好的印象，这也就增加了客户下次访问的机率。
4.4 对客户进行聚类
在电子商务中，应用数据挖掘进行客户聚类是一个十分重要的内容，通过对具有相似浏览行为的客户进行分组，可以分析出组中客户的共同特征与共性信息，从而可以帮电子商务的组织者更加客观地了解自己的客户，这也最后有利于组织者为客户提供更加适合、更加面向客户的服务。
5 结束语
数据挖掘尽管只有十多年的发展历史，但是在电子商务中却展示出了非常广阔的应用前景。本文比较详细地阐述了电子商务中数据挖掘的体系结构、应用方法以及比较典型的应用，期望通过本文的分析与探讨，可以为今后数据挖掘技术在电子商务中的广泛应用提供积极的借鉴参考。
数据挖掘算法论文:数据挖掘中关联规则算法的研究
摘要：数据挖掘是一个新兴的领域，在短短几年内得到了迅速的发展。关联规则算法是数据挖掘技术中最活跃的算法之一。该文从关联规则算法的原理入手，对关联规则的各种算法进行了深入研究，并总结得出了强关联规则生成的步骤方法。
关键词：数据挖掘；关联规则算法；强关联规则
随着数据库技术的发展、改进及相关技术、产品的广泛应用，数据库中存储的数据量日益膨胀。此时，许多人都曾提出疑问：在海量的数据之间是否隐藏着许多具有决策意义的有价值的信息？如果这种信息真的存在，那么把这些信息挖掘出来并应用于现实生活，将会为决策者和管理者提供指导，提高工作效率和工作精度。
数据挖掘(Data- Mining)就是从众多的、有噪声的、不完全的、模糊的、随机的大量数据中，提取隐含在其中人们事先不知道但又是潜在有用的信息和知识的过程[1]。
关联规则算法是一种在海量数据中找出隐藏的关联规则的方法。它是数据挖掘中最为活跃的算法之一。
1 关联规则算法的原理
1.1 背景
关联规则算法早期应用于“购物篮分析”。通过使用关联规则算法来对客户的事务执行购物蓝分析，可以知道哪些产品比较热销，以及一个特定的产品与另一个产品一起被购买的可能性是多大。如，在数据挖掘应用中最典型的例子“啤酒与尿布”，就是销售商们通过大量的客户购买信息，挖掘出的一条关联规则。即，在购买尿布的用户中，有很大比例的人还同时购买了啤酒。知道了这条规则，商家就可以采取行动，改变产品的布局来增加销售和管理库存。现在，关联规则挖掘不仅在零售业，在其它领域也得到了广泛应用。
关联规则常常用一个蕴涵式来表示。如“啤酒=>尿布”。
1.2 基本概念
1.2.1 项集（Itemset）
项集也叫项目集合，是由一组项组成。其中每个项都是一个属性值。通常设I＝{i1,i2，…im}为一个项目集，而事务数据库D={t1,t2，…tm}是由一系列事务组成，而每个事务ti（i=1,2,…,n）都对应I上的一个子集。在购物篮分析中，项集中包含的是一组由用户购买的产品，如｛啤酒，尿布，香槟｝。这个项集包含了3个属性值，大小为3。
1.2.2 支持度（Support）
支持度是指一个项集在全部事务中出现的频率。项集｛牛奶，面包｝的支持度就是在全部事务数据中，既购买了面包又购买了牛奶的顾客出现的频率。若项集｛牛奶，面包｝的支持度为0.05，则表明在全部顾客中，只有5%的顾客同时购买了这两样。
最小支持度是事先由用户确定的一个数值。一般来说，用户只关心那些出现频率比最小支持度高或与之相等的项集。因此，该数据可以用来对项集进行筛选。
1.2.3 置信度(Confidence)
置信度是关联规则的属性。关联规则“牛奶=>面包”的置信度是使用｛牛奶｝的支持度除项集｛牛奶，面包｝的支持度来计算的。简单解释就是，在全部事务数据中，购买牛奶的顾客中有多大比例的人还同时购买了面包。
它是按以下方式来定义的：
Confidence{A=>B}=Support{A,B}/Support{A}
最小置信度也是在运行算法之前由用户事先指定的一个数值。该数据表明用户只对那些置信度等于或大于最小置信度的规则感兴趣，即那些拥有较高概率的规则。该数据可以用来筛选出有效的关联规则。
1.2.4 频繁项目集（Frequent Itemsets）
挖掘频繁项目集是进行关联规则算法的核心内容。所有满足用户指定的最小支持度的项目集，即大于或等于最小支持度的I的非空子集，就称为频繁项目集，简称为频繁项集。即上面提到的用户感兴趣的项集。
1.2.5 强关联规则(Strong Association Rule)
D在I上同时满足最小支持度和最小置信度，即在满足支持度不小于最小支持度的每一个频繁项集中，置信度大于等于最小置信度的关联规则。即上面提到的用户感兴趣的规则。这个规则也叫强关联规则。
1.2.6 相关度（Importance）
相关度是关联规则中另外一个重要的概念。在一些文献中相关度也被称为兴趣度分数或者增益（lift）[2]。
相关度的公式可以定义如下。
Importance({A,B})=confidence(A,B)/(confidence(A)*confidence(B))
如果Importance＝1,则A和B是独立的项。在购物篮分析中，它表示产品A的购买和产品B的购买是两个独立的事件。如果Importance1，则A和B是正相关的。这表示如果一个客户购买了A，则他也可能购买B。
2 关联规则挖掘的一般过程
通过以上对关联规则挖掘算法的简单介绍，可以了解到，关联规则挖掘就是通过用户指定的最小支持度，在全部事务数据库中挖掘出满足支持度不小于最小支持度的频繁项目集，再通过用户指定的最小置信度，在全部频繁项目集中挖掘出那些置信度不小于最小置信度的强关联规则。关联规则挖掘过程由这两部分共同组成。
在这两部分中，关联规则挖掘是否成功主要取决于第一部分，即挖掘频繁项目集。
3 频繁项目集的生成算法
挖掘频繁项目集是使用关联规则算法的核心部分。自关联规则挖掘问题提出后，相应的如何快速高效地生成频繁项目集这个核心问题的算法就不断的被人研究，并不断发现、使用。这些算法大多都是通过利用频繁项集的特性DD即如果一个项目集是频繁的，那么它的所有子集也都是频繁的DD来进行操作的。
Apriori算法[5]在关联规则挖掘领域中有很大的影响力，应用极为广泛。它的命名源于算法使用了频繁项集性质的先验知识。Apriori算法是通过迭代即反复扫描数据项的方式来产生频繁项集的。它的具体思路是：在第一次迭代时，先产生包含所有数据项的大小为1的候选集，计算出它们的支持度，选择那些支持度大于等于最小支持度的候选集作为第一次迭代时的频繁项目集。此时，所有频繁项目集的大小都为1，被淘汰的项目集被标记为非频繁子集。接着进行第二次迭代，在第二次迭代的第一步中，将所有成对出现的项集都作为大小为2的候选集，第二步，利用频繁项集的性质：频繁项集的子集也都是频繁的，假若某个项目集的一个子集不是频繁的，那这个项目集必然不是频繁项集，将刚才产生的候选集中包含有非频繁子集的删去。第三步再计算所有候选集的支持度，将支持度满足最小支持度的候选集做为第二次迭代产生的大小为2的频繁项目集。如此通过i次迭代，就可以产生出大小为i的频繁项集。
Apriori算法是通过项目集元素数目不断增长的方式来逐步完成频繁项目集发现的。每增长一次项目数，Apriori算法就至少需要扫描事务数据库一次，假如频繁项目集的项目数很大，会造成计算机巨大的I/O负载。并且，因为Apriori算法在每一次迭代时，都将成对出现的项集依次组成新的候选集，因此，可能会产生庞大的候选集。这对计算机运行速度也将是一种挑战。
因此，逐渐又产生了Apriori算法的改进方法。
如基于数据分割方法的Partition方法。Apriori算法在每一次迭代时只能将项目数增加1,每次产生的候选集也并不都是有效的，无形中降低了算法的效率。而Partition算法是一种基于对数据集进行划分的挖掘算法，它的思路是：先将事务数据库划分为几个逻辑上互相独立的区域。在每个区中，利用挖掘算法挖掘出它们各自的频繁项目集。然后将这些频繁项目集合成一个候选集。最后，计算出候选集的支持度，挖掘出符合不小于最小支持度的最终的频繁项目集。Partition方法在第一次划分时扫描一次数据集，在最后求候选集支持度时再一次扫描数据集，全程只扫描二次数据集，大大减少了I/O操作。Partition算法因为是分别求每个区的频繁项集，因此可分别同时对各区进行操作，大大提高了算法的效率。
还有与Apriori算法类似的DHP算法[3]。DHP算法也是从Lk-1中生成侯选集Ck。但DHP算法在每次迭代计算候选集的支持度时，会建立并维护一张Hash表。在下一次迭代时，根据Hash表来选择加入的数据项，而不是像Apriori算法那样将所有数据项先全部选上之后，再删去那些非频繁子集。通过对Hash表的操作，DHP算法可以大大减小侯选集的规模，从而提高算法的计算效率。
随着数据库容量的逐步增大，为适应新形势，新的算法不断出现。2000年，Han等人提出了一个不用产生候选集，可以直接将数据压缩成频繁模式树的方法，被称为FP-tree算法[4]。
4 强关联规则的生成
利用Apriori算法或其它类似的算法挖掘出所有频繁项集之后，下一步的工作就是生成强关联规则。这可以在频繁项目集中逐一测试非空子集的支持度，从而挖掘出所有可以生成的规则。也可以直接测试用户想要挖掘的规则是否成立。假如用户打算挖掘出这样的规则｛A，B，C｝=>D，那么，第一步，先来检验｛A,B,C,D｝和｛A,B,C｝是否都是频繁项集。如果是，接着第二步，利用关联规则置信度的公式Confidence{A=>B}=support{A,B}/support{A}，计算出规则｛A，B，C｝=>D的置信度的值。若此值大于等于最小置信度，那么规则｛A，B，C｝=>D成立，是强关联规则。反之，不成立。
5 结论
关联规则挖掘就是要挖掘出强关联规则。强关联规则的生成取决于频繁项目集，而频繁项目集的挖掘算法正是关联规则算法的核心所在。因此，深入研究关联规则算法，并根据实际情况在应用中选取最合适的算法对强关联规则的生成非常重要。
数据挖掘算法论文:一种改进的基于密度的离群数据挖掘算法
摘要：利用基于密度的离群数据挖掘算法离群数据不在非离群数据指定的邻域内的特点，改进了原有的离群数据挖掘算法：首先判断数据是否在某个非离群数据指定的邻域内，如果不在，再判断其邻域内数据的个数。通过对二维空间数据测试表明，改进的算法能够快速有效地挖掘出数据集中的离群数据，速度上数倍于原来的算法。
关键词：数据挖掘；离群数据；基于密度
0引言
数据挖掘是从大量的数据中发现正确的、新颖的、潜在有用并能够被理解的知识的过程。现有的数据挖掘研究大多集中在发现适用于大部分数据的常规模式。但在一些应用中，如电信和信用卡欺骗、药物研究、气象预报、电子商务、贷款审批、客户分类、金融领域、网络入侵检测等领域有关例外情况的信息比常规模式更有价值。目前在数据挖掘中，对偏离常规模式的数据即离群数据的研究正得到越来越多的重视。
目前还没有关于离群数据的统一的定义，这里采用Hawkins1980年给出的定义：离群数据是在数据集中与众不同的数据，使人怀疑这些数据并非产生于非随机偏差，而是产生于完全不同的机制。离群数据的来源有两类：错误的数据，如录入错误、测量错误等；数据真实性质的反映，如一个公司的总裁的薪金远大于该公司一个普通员工的薪金等。所谓的离群数据挖掘指给定一个有n个数据点或数据对象的集合及预期的离群数据数目n′，发现与剩余数据相比显著相异的、离群的或不一致的前n′个对象的过程[1]。
早期的统计分析领域的基于统计的离群数据挖掘其前提是待处理数据的分布特征是预先知道的（如正态分布、泊松分布等），这种方法需要知道数据的分布及分布的参数等；郑斌祥等人[2]基于第k个最近邻居的离群挖掘方法只针对时序数据，而且运算性能也不甚理想；基于偏离的离群数据检测方法是知道数据特性选取合适的相异函数，但序列离群数据在概念上仍然有一定的缺陷，遗漏了不少的离群数据，因而没有得到普遍的认可；基于规则的分类离群数据挖掘方法只适合于要求错误数据少，分组粒度细的挖掘；基于距离的方法比较接近Hawkins对离群数据本质的定义，它通过实验确定合适的基准值和距离范围，难以处理分类数据和周期性时态数据；基于密度的离群数据挖掘（DensityBased Outlier Mining，DBOM）的观点比基于距离的离群数据挖掘的观点更贴近Hawkins对离群数据本质的定义，因此能够检测出基于距离离群数据挖掘算法所不能识别的一类离群数据，即局部离群数据，而局部离群数据抛弃了以前所有的离群数据定义中非此即彼的绝对离群数据概念，更加符合现实生活中的应用。另外还有基于相似系数的方法、基于聚类的小波变换聚类的方法、高维空间聚类的方法等。本文首先描述了DBOM算法，而后对其进行了改进。
1基于密度的离群数据挖掘
1.1DBOM算法的基本概念
定义1以数据对象o为圆（球）心，半径ε内的区域称为o的ε―邻域。
定义2若数据对象C的ε―邻域内含有数据对象数目不少于Minpts个，则称C为核心对象，能产生核心对象的ε是有意义的。其中，Minpts是一个可以人为设定的自然数。
定义3D是数据对象集合，p∈D，C∈D。对于给定的一个自然数Minpts，若C是核心对象，p在C的ε―邻域内，则称p是从C出发关于ε和Minpts直接密度可达。
定义4D是数据对象集合，p∈D，p的ε―邻域内数据对象集合称为p的ε擦谟蚣，记为Pε―set。
定义5D是数据对象集合，o∈D，对于任意一个核心数据对象C∈D，从C出发，都不能关于ε和Minpts直接密度可达并且|oε―set|≤Minpts，则称o为关于ε和Minpts的基于密度的离群数据对象。
定义6D是数据对象集合，p∈D，若p的ε擦谟蚰诤有对象数目为零，则称p是数据集D中关于ε邻域的孤立点。
1.2DBOM算法的描述
基于密度的离群数据挖掘算法可以发现任意形状的数据布局中的离群数据，它的基本思想是：对于数据集中的每一个离群数据对象，不能包含在任何一个给定半径和该半径邻域内包含指定数据对象数目的核心对象的邻域内。基于密度的离群数据挖掘为了发现所有的离群数据，需要对每个数据进行处理。DBOM首先从数据集D中任意找一数据对象p，并查找出D中p的关于半径ε邻域内包含所有的邻域对象，若p的ε邻域内某一个数据对象的ε邻域内包含Minpts或多于Minpts个数据对象，则p不是离群数据；反之，若p的ε邻域内所有数据对象的ε邻域内包含的数据对象个数都少于Minpts，或者p的ε邻域内没有数据对象即p是数据集D中关于ε邻域的孤立点，则p是离群数据。接着处理数据集中的下一个数据，直至数据集中的所有数据都被处理完。相应的算法描述如下：
2改进的基于密度的离群数据挖掘IDBOM
上述的基于密度的离群数据挖掘算法能够较好地挖掘出数据集中的离群数据，该算法的平均执行时间复杂度为O（n2）（n为数据集中包含的数据对象数目）。它主要是通过对数据集中每个数据对象进行判断，如果它的邻域内某一个数据对象是一个核心对象，即它包含在某一个核心对象的邻域内，该数据对象就不是离群数据，否则是离群数据。从离群数据的特征来看，离群数据往往是比较稀疏的、在数据集中所占比例比较小的数据因此，上述算法对每个数据及其邻域内的数据进行相关判断，显然效率就比较低下。
定理1如果一个数据对象是核心对象，那么该数据的邻域内的数据都不是离群数据。
证明假设存在一个数据集D，C为D中关于ε和Minpts的核心数据对象，Cε―set为C的ε―邻域集，那么对Cε―set中的任意一个数据对象p，都有d（C，p）≤ε，即从核心数据对象C出发，可以直接密度到达数据对象p，由定义5可知，数据对象p不是离群数据对象。
定理2某个数据对象是离群数据是其ε―邻域内数据对象的个数少于Minpts个的充分条件。
证明设存在一个数据集D，o为D中关于ε和Minpts的离群数据对象，oε―set为o的ε―邻域集，由定义5可知，｜oε―set｜≤Minpts；假设在数据集的边缘存在一个数据对象q∈｜qεset｜≤Minpts, C为数据集中一个核心数据对象，且有q∈Cε―set，根据定义5可知q不是离群数据对象。
基于上述定理，我们不对数据集中每个数据对象的邻域内判断是否存在一个核心数据对象，而是只判断邻域内数据对象个数少于Minpts个的数据对象的邻域内是否存在核心数据对象。如果某一个数据对象p是核心数据对象则将其及其邻域内的数据对象打上暂不运算的标签及非离群数据的标签；反之按下述方式处理其邻域内的数据对象：若p的邻域和某个核心数据对象C的邻域数据对象交集不为空，那么判断这些交集中的数据对象是否存在核心数据对象，若存在则p不是离群数据。如果和任何核心数据对象的ε擦谟蚪患为空或交集内不含核心数据对象则p就是离群数据对象。改进的算法描述如下：
3算法测试
这里对基于密度的离群数据挖掘算法进行了测试，算法是用Matlab实现的，实验的环境是一台P4 2.93G、内存1GB的计算机，通过对网络中心的某数据集进行测试，在ε＝50和Minpts＝3的条件下，共挖掘出3个离群数据，经过检测，其中两个离群点是由病毒造成的网络不正常，另外一个是由于一个实验室进行网络对拷发送广播报文引起的网络堵塞造成的。其中优化后的算法的运算时间是优化前的三分之一。在运算的过程中发现，ε和Minpts取值不同，挖掘出的离群数据的个数也可能不同，这说明了基于密度的离群数据挖掘算法对输入参数有一定的敏感性。
