分类聚类

2024-10-09

分类聚类（精选7篇）

分类聚类篇1

1、引言

图像分类是根据图像信息中所反映的不同特征将不同类别的目标区分开来的一种图像处理方法。目前提出的图像分类方法各自基于不同的图像模型, 它们利用不同的图像特性进行分类, 有各自的适用范围和优缺点。常见的图像分类方法可以分为监督分类和非监督分类。

监督分类和非监督分类的根本区别在于是否利用训练数据来获取先验的类别知识。监督分类根据训练数据集提供的样本选择特征参数, 建立判别函数, 对待分类点进行分类。因此, 监督分类依赖于选定的训练数据。相比之下, 非监督分类不需要更多的先验知识, 它根据图像色彩的数据特性进行分类。因此, 非监督分类方法简单且具有较高的精度。本文主要对三种非监督分类方法进行对比分析和有效性验证。

2、非监督聚类分析方法

2.1 K-means方法

K-means以K为参数, 把n个对象分为K个簇, 使得同簇内的对象具有较高的相似度, 簇间对象的相似度较低。当结果簇是密集的, 簇与簇间区别明显时, 算法效果较好。但由于K-means要求用户必须事先给出K值, 而K值的选定又很难, 这就使得算法的使用受到限制;同时, K-means不适合发现非凸面形状的簇和大小差别很大的簇, 并且对于“噪声”和孤立点数据很敏感, 少量的该类数据能够对平均值产生极大的影响, 导致聚类结果不好。

2.2 层次聚类方法

层次聚类方法对给定的数据集进行层次的分解, 直到某种条件满足为止。分为凝聚的和分裂两种方法。层次聚类与K-means有两点不同:层次聚类采用逐个样本修正法或者成批样本修正法计算样本均值;层次聚类通过调整样本所属类别完成样本的聚类, 也可以自动地进行类别的“合并”和“分裂”, 从而得到比较合理的聚类结果。

2.3 基于密度和自适应密度可达聚类方法

算法描述:

输入:数据对象, coefR、σ

输出:簇的数目, 每个簇的对象和簇中心点, 孤立点或噪声

方法:

(1) 计算对象集的相异度矩阵、对象密度, 构造候选数据对象链表;

(4) 在候选数据对象链表中寻找密度吸引点 (密度最大点) ODensityMaxi, 作为簇Ci的中心点;

(5) 将自适应密度可达范围内的数据对象划分到簇Ci中, 即存放到Ci的数据链表中, 同时从候选数据对象链表中删除已划分的对象) ;

(7) until候选数据对象链表为空;

(8) 将簇所包含数据对象数目小于给定阈值的簇划分到孤立点数据链表中;

(9) 输出最终聚类结果。

3、实验结果分析

实验利用MATLAB 7.0得到真彩色BMP图像的R、G、B像素栅格矩阵, 然后利用聚类方法将图像按照R、G、B值的相似性聚类, 进而将图像内容分类成不同的色彩区域。本文从大量实验数据中选取了一幅典型的图像进行分析。

对图1 (a) 所示原始图像分别利用CADD、K-means和层次聚类进行聚类, 图像下方C1、C2、C3和C4表示簇和对应颜色。从图1 (b) 中看出CADD的聚类结果良好, 结果簇C1、C2、C3和C4很好的反映出原始图像不同的色彩区域, 并且聚类结果的噪声点集反映出了原始图像色彩内容变化过渡像素的存在。从图1 (c) 中看出K-means的聚类结果不好, C3和C4的分类效果还可以, 但C1和C2没能分辨出来。从图1 (d) 中看出层次聚类的聚类结果也不好, C3和C4、C1和C2都没有很好的分辨出来。

实验结果说明, 图像内容色差变化较大且聚类簇的数目选择正确, K-means和层次聚类才能取得较好效果。但现实中的图像色彩变化是比较复杂的, 图像内容分类数目的确定很困难。

综上所述, CADD与K-means和层次聚类相比具有较高聚类精度和分辨率;CADD克服了传统单纯划分或层次算法需要人为指定最终聚类数目、不能很好的聚类复杂形状簇的缺点和基于密度的算法不能处理变密度簇的不足;CADD能够划分出变密度的簇和噪声点 (孤立点) ;CADD利用像素点的平均抽样提高了算法的效率。

4、结语

图像的分类是图像处理领域重要的研究课题之一, 在许多领域中都有广泛的应用, 对它的理论研究有很重要的意义, 而且聚类分析方法已成为数字图像分类的重要方法。研究结果表明, 通过对聚类算法的改进研究能够提高算法对图像分类的有效性。

参考文献

[1]孟海东, 郝永宽, 王淑琳[J].计算机与现代化, 2009, 10.

[2]宋宇辰, 宋飞燕, 孟海东.基于密度复杂簇聚类算法研究与实现[J].计算机工程与应用, 2007, 43 (35) :1622165.

基于层次聚类的分类挖掘篇2

关键词：数据挖掘,聚类,分类

0 引言

随着信息技术迅速发展,数据库应用的范围不断扩大,从中可获取的数据量越来越大,数据的种类也日益繁多。而从已存在的大规模的、带有“噪声”的数据中提取出隐含其中,人民感兴趣的有用信息和知识,成为信息技术产业界需解决的一个问题。所以数据挖掘的出现也就成了信息技术自然进化的结果。其源于诸如数据库系统、数据可视频化、数据仓库、机器学习、信息提取、统计和高性能计算。其它有贡献的领域包括神经网络、空间数据分析、模式识别、信号处理、图象数据库和一些应用领域,也包括经济、商务和生物信息学。数据挖掘功能包括发现概念/类描述、分类、预测、关联规则、聚类、偏差分析、趋势分析和类似性分析。

1 相关知识

1.1 数据挖掘

数据挖掘是知识发现的一个步骤,是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取出有效的、新颖的、人们事先不知道的,但潜在有用的信息和知识的过程。它的核心技术是机器学习、人工智能、统计等,但是一个数据挖掘(Data Mining)系统并不是多项技术的简单组合,而是一个完整的体系,包括数据采集、预处理、数据分析、数据挖掘、结果表述与可视化等。

1.2 聚类分析

聚类分析是将物理或抽象的数据集划分为由类似对象组成的多个类的过程,使得位于同一类中的对象有高度的相似性,而不同组中的数据对象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定的。通常就是利用(各对象间)距离来进行表示的。许多领域,包括数据挖掘、统计学和机器学习都有聚类研究和应用。聚类算法各式各样,主要有划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法。

1.3 分类规则

分类规则挖掘则是通过对训练样本数据集的学习构造分类规则的过程,是数据挖掘、知识发现的一个重要方面。分类规则挖掘的实质是希望得到高准确性、有趣的和易于理解的分类规则。目前常用的分类规则挖掘方法有决策树方法、统计方法、神经网络方法、粗糙集方法和遗传算法等。

通过构造一个分类函数,把具有某些特征的数据划分到某个给定的类别上即可获得分类规则模型。数据分类由创建模型和评估使用模型两步组成,创建模型是通过对训练数据集的总结学习来建立分类模型;评估使用模型是先用已建立的分类模型对预测数据进行分类看其准确率是否在可接受范围,然后对新的数据进行分类。训练数据集中的数据带有类标号,通过训练集的训练,使得使用分类函数可以把标号未知的数据正确的分类到其相应的标号中。

2 基于层次聚类的分类挖掘算法

在聚类中,目标数据的有关类的信息预先是未知的,需要利用某种度量来将所有的数据对象划分到相应的簇中。分类与聚类不同,在分类模型中,需要存在一些样本数据,且这些数据的类标号是已知的,分类的目的是从训练样本集行类标识。

对数据进行分类,首先要得到训练数据集,可以通过聚类来得到这个数据集合。本文利用层次聚类的方法进行聚类以得到分类所需要的训练数据集,并用决策树的分类方法来进行分类。

(1)从源数据对象中随机采样获得包含s个对象的集合S;

(2)将采样集合S划分为p个部分,每个划分部分大小为s/p;

(3)将各划分部分聚类成s/pq个局部聚类,其中q>1;

(4)对局部聚类进行聚类,落在每个新获得的聚类中的代表性点,则根据收缩因子α,“收缩”或移向聚类的中心。这些点将要用于描绘出聚类簇的边界形状;

(5)重复第(4)步;

(6)为聚类结束后的类分配类标号(1,2...),作为进行分类的训练数据集;

(7)用决策树的方法进行归纳分类;

(8)若样本属于同一个类别,则将该结点设成叶结点,并用该类标记;

(9)否则,选择具有最大信息增益的属性来选择合适的分支属性,以便使得样本集划分为几个子集,这些分支属性即为各个结点所对应的测试属性;

(10)一个测试属性的每个已知值对应将被创建的一个分枝和一个被划分的子集;

(11)对于上边的各个处理过程,递归地形成每个划分上的样本决策(子)树.一旦一个属性出现在某一个结点上,它就不被再考虑出现在该结点的子树结点中;

(12)当递归划分步骤符合以下任意的一条件时停止:

(1)给定结点的所有样本同属于一个类别;

(2)若样本集没有剩余属性被进一步划分,则将当前结点转换成叶结点,并用当前结点所含样本集中类别个数最多的类标记它;

(3)若测试属性的分枝上没有样本,则创建一个叶结点,并用当前结点所含样本中集中类别个数最多的类标记它;

(13)由此产生分类规则,得到一个分类器。

利用通过上述方法获得的分类器可对需要预测的大量的数据进行分类,以得到人们感兴趣的结果。

3 结束语

数据挖掘是信息技术领域研究的一个热门课题,涉及到多学科多领域的研究内容。不同领域的研究者都研究发现了各种不同的数据挖掘的方法和技术对数据进行挖掘和应用。本文建立了用层次聚类的方法对数据进行分类的模型,为数据挖掘的发展提供了基础。

参考文献

[1]韩家炜,堪博著,范明,孟小峰译.数据挖掘—概念与技术[M].北京:机械工业出版社.2007.

[2]朱明.数据挖掘[M].中国科学技术大学出版社.2002.

[3]赵少卡.基于大型数据库的数据挖掘[J].福建电脑.2007.

[4]段录平,周丽娟,王宇.基于神经网络的数据挖掘研究[J].控制理论与应用.2007.

基于聚类的加速k-近邻分类方法篇3

近年来,大数据处理［1，2］已成为各领域研究的一个热点问题之一,许多成熟的数据处理方法如神经网络NN( Neural Net- work)［3］、决策树DT( Decision Tree)［4］、支持向量机SVM( Sup- port Vector Machine )［5］、k-近邻方法［6］等被广泛研究并应用。在这些分类方法中,k-近邻k-NN( k-Nearest Neighbor) 分类是一种最为经典且使用广泛的数据分类方法［7，8］。但是,传统k-NN分类方法存在多方面的困难,如近邻参数k的选择困难、距离度量形式局限、分类速度较慢、不能有效处理高维、非平衡等复杂数据分类问题。

目前,已经提出了多种改进的k-NN分类方法,如针对近邻参数的选择困难问题,采用启发式的搜索策略从参数取值空间中搜索得到更加合理的近邻参数来取代人为指定的参数值,典型的方法如VDM［9］及基于相似度支持度的k-NN参数优化算法［10］等; 针对传统k-NN分类方法不能高效处理高维数据的问题,通过充分利用K-NN分类的简单有效性及李群结构的复杂数据表示和距离计算能力,提出一种多协方差李-KNN分类方法［11］,解决了高维数据分类问题; 针对传统k-NN方法分类速度慢,无法高效处理大规模数据的分类问题,目前已经提出了利用向量方差和逼近系数来进行k-NN搜索的方法［12］以加速k-NN分类方法的学习过程,或基于随机采样的方式［13］,首先提取种子点,然后根据种子点进行加速的k-NN分类; 此外,许多研究者通过改变距离度量函数、学习样本权重、学习特征权重等方法对距离度量进行了改进,提高了k-NN分类方法处理非平衡分类问题的性能［14，15］。

但是,由于k-NN方法是基于实例学习的方法,即根据训练样本构造分类器,对于每个待分类样本,均需要计算其与训练集中每个训练样本的相似度,才能得到其近邻样本集,得到其标签。假设训练样本集规模为l,向量空间模型特征维度为d,测试样本集规模为t ,则k-NN方法的时间复杂度为O( tld) ,为保证分类的泛化性能,在采用k-NN方法处理实际分类问题时,需要训练集规模足够大,因此k-NN方法的时间复杂度往往较高, 无法处理大规模数据的分类问题。

针对传统k-NN分类方法时间复杂度高,无法进行高效分类的问题,本文提出一种基于聚类的加速k-NN( C_k-NN) 分类方法。该方法首先对训练样本集进行聚类,得到每个类的聚类中心,并将与聚类中心相似度最高的训练样本构成新的具有代表性的训练集。然后针对每个测试样本,选择新的训练样本集中的与其相似度最高的k个样本,以得到该测试样本的模式类别。

1 k-NN分类方法

k-NN分类方法通过选择与未标记样本相似度最高的k个样本构成近邻样本集,然后取近邻样本中类别最多的标签作为该未标记样本的标签,如此循环往复,直到所有未标记样本均得到相应标签为止。

假设训练集为Tr = { X,Y} = { ( xi,yi}li = 1且xi∈ Rd,其中X为训练样本集,Y为训练样本集标签,测试集为TE = { TX,TY} = { ( txj,tyj}jt= 1,其中TX为测试样本集,TY为测试样本集标签, k-NN分类参数为k 。传统k-NN分类方法的目标即根据与测试样本集TX中测试样本txj相似度最高的k个训练样本来得到测试样本txj的类别标签ty'j。k-NN分类方法针对每个测试样本txj,从训练样本集X中选择与测试样本txj相似度最高的k个训练样本k_Set = { xq}kq = 1,其中,任一训练样本xi与测试样本txj的相似度定义如下:

式中,xip表示训练样本xi的第p个分量,txjp表示测试样本txj的第p个分量。假设离散目标函数为f: Rd→ Y,即建立训练样本空间Rd与标签域Y之间的对应关系,如f( xi) = yi,然后采用式( 2) 对测试样本txj打标签。

其中,δ 函数如下:

即可得到测试样本txj的预测标签ty'j,针对测试样本集TX中的每个测试样本循环往复,得到测试样本集TX中每个测试样本的预测标签,并将其与测试样本的真实标签比对,以衡量分类器的泛化性能。

由于传统k-NN分类方法时间复杂度较高,特别地,当训练集规模l较大时,无法建立高性能的分类器。针对这一问题,本文提出一种基于聚类的加速k-NN分类方法,首先对训练样本集进行聚类,得到每个类的聚类中心,并提取与聚类中心最相似的训练样本构成新的训练集,以减小测试集寻找k近邻样本时的搜索规模,提高模型的学习效率,使其能够对大规模数据进行高效分类。

2基于聚类的加速k-NN分类算法

在处理实际问题时,经常会遇到大规模数据的分类问题,传统k-NN分类方法由于其对每个测试样本的标签预测过程均需要对整个训练样本空间的全局搜索,因此当训练样本集规模较大时,无法进行有效的分类。为解决该问题,本文首先对整个训练样本集进行聚类,计算每个聚类的类中心,并选择与类中心相似度最高的训练样本构成新的训练样本集,然后再执行k-NN分类过程。由于基于聚类的加速k-NN分类算法压缩了实际参与的训练样本集的规模,因此其寻找每个测试样本的k个近邻样本的搜索空间变小,搜索速度快,提高了整个k-NN分类算法的执行效率,可对大规模数据集进行高效分类。

具体地,基于聚类的加速k-NN分类算法执行过程如下。

算法1基于聚类的加速k-NN分类算法

初始化: 假设训练集为Tr = { X,Y} = { ( xi,yi}li = 1且xi∈ Rd,其中X为训练样本集,Y为训练样本集标签,测试集为TE = { TX,TY} = { ( txj,tyj}jt= 1,其中TX为测试样本集,TY为测试样本集标签,k-近邻分类参数为k,聚类参数为c 。

Step1: 对训练样本集X进行初始聚类,得到初始聚类划分结果X → { Xp}cp = 1,具体过程如下:

Step1. 1: 从训练样本集X中随机选择c个样本构造初始中心集C = { cr}rc= 1;

Step1. 2: 计算训练样本集X中每个训练样本xi与所有不同类心cr之间的相似度S( xi,cr) :

分别将每个xi归入与其相似度最高的类中心所属的类别;

Step1. 3: 根据式( 5) 更新每个类的中心cr,得到新的类中心集合C :

式中,crp为第r个类心的第p个分量,xrqp表示第r类中第q个样本的第p个分量,nr为第r类中训练样本个数。

Step1. 4: 观测更新前后的聚类中心集合C是否一致,若不一致,则返回Step1. 2继续执行,直到更新前后的聚类中心一致为止,得到聚类划分结果X → { Xp}cp = 1;

Step2: 计算训练样本集X中与聚类中心集C中每个聚类中心相似度最高的训练样本,构成新的训练样本集合X',并结合其样本标签构造新的训练集Tr' = { X',Y'} = { ( x'i,y'i) }ic= 1;

Step3: 针对测试样本集TX中的测试样本txj,根据式( 1) 计算新的训练样本集X' 中每个训练样本x'i与测试样本txj的相似度S( x'i,txj) ;

Step4: 选择相似度最高的前k个训练样本,以得到测试样本txj的预测标签ty'i:

Step5: 针对测试样本集TX中的每个测试样本循环往复执行Step3 - Step4,得到测试样本集TX中每个测试样本的预测标签,构成预测标签集合TY',并将其与测试样本的真实标签集TY比对,以衡量分类器的性能;

Step6: 算法结束,输出分类器的分类精度。

3实验结果及分析

为验证本文提出的基于聚类的加速k-NN分类方法( C_k-NN) 的性能,本文将其与标准k-NN分类方法( k-NN) 、基于近邻参数优化的k-NN分类方法Ok-NN( Nearest Neighbor Optimiza- tion k-NN Classification method)［10］和基于随机采样的加速k-NN分类方法进行了对比RSk-NN( Random Sampling k-NN Classifica- tion Method)［13］。本文的实验在一台PC机( 2. 66 GHz CPU, 2 GB内存) 上进行测试,实验平台是Matlab2008a。实验采用的数据集［16］见表1。

实验中本文提出的C_k-NN优化分类方法的初始聚类参数c分别取20、40、60、80和100进行实验,基于随机采样的加速k- NN分类优化算法中的采样参数与本文方法的聚类参数设置值一致,而k-NN方法中的近邻参数k分别取10、15和20进行测试。图1 - 图5分别为在近邻参数10下三种方法的比较结果。由于数据集Flare_solar规模较大,标准k-NN分类法方法无法在有效时间内进行高效分类,因此没有得到标准k-NN方法在该数据集上的实验结果值。

由于标准k-NN方法无法在Flare_solar上有效训练,因此没有得到其测试精度,且由于基于近邻参数优化的k-NN分类方法( Ok-NN) 与标准k-NN方法不受参数设置影响,因此其测试精度是一条水平直线。从图中可以看出,除数据集Flare_solar外,在其他数据集上,本文提出的基于聚类的加速k- NN分类方法( C_k-NN) 的测试精度与标准k-NN方法的测试精度最为接近,Ok-NN分类方法则略次于本文提出的C_k-NN方法,而RSk_NN分类方法效果较差,特别地,在数据集German和Titanic上几乎是失效的。其次,从图中可以看出,随着聚类个数参数的增加,C_k-NN方法的测试精度基本呈现相对稳定的增长趋势,这是由于随着聚类个数增加,所得到的实际训练样本集规模增大,包含的分类信息较多,能够进行有效分类。

在取得最优参数值时( 即图中C_k-NN与RSk-NN在不同参数下的最大值) ,三种改进的k-NN分类方法与标准k-NN方法的最小测试精度差值见表2。

从表2中可以看出,与标准k-NN方法相比,本文提出的C_ k-NN分类方法测试精度下降较小,测试精度的差值均在1% 以内; 而其他两种优化方法与标准k-NN分类方法相比,则测试精度有较大程度的损失,特别地,在数据集German上,精度损失很大。这是由于数据集German本身维度较高,分布较为复杂,采用基于近邻参数优化和基于随机采样的方法尽管能够压缩训练样本规模,提高分类效率,但其抽取的样本含有的信息量较小,损失了大量重要的训练样本信息,因此测试精度低,泛化性能差。

表3为近邻参数取10时,四种方法在个数据集上的训练时间比较,其中标准k-NN方法在数据集Flare_solar上无法在有效时间内训练。

从表3中可以看出,与标准k-NN分类方法相比,本文提出的C_k-NN在学习效率方面有了明显地提高,特别对于规模较大的数据集,训练速度提高了成百上千倍,且随着聚类个数参数的增大,实际训练样本集规模增大,因此训练时间增加。但是, Ok-NN方法尽管通过参数优化的方式提高了分类问题学习过程的效率,但其仅仅是通过优化参数的方式进行了加速,没有从本质上改变算法的复杂度,训练效率提高的幅度仍然不够高,对于大规模数据集依旧无法高效得到分类结果。而RSk-NN方法的学习效率很高,甚至在多数数据集上都超过了本文提出的C_ k-NN分类方法,但其测试精度太低,且随着参数变化模型的测试精度值有较大波动,分类器的性能很差。

在其他近邻参数下的实验结果也表明,本文提出的C_k-NN分类方法在保持较高测试精度的同时大幅度提高了模型的学习效率,得到了优秀的实验结果。

综上可知,本文提出的基于聚类的加速k-NN分类方法不仅有效压缩了训练样本规模,在大幅度提高了方法训练效率的同时能够提取重要的训练样本信息,压缩不重要的训练样本信息,使得模型保持较高的泛化性能,可用来解决大规模样本的分类问题。

4结语

基于聚类分析的图模型文档分类篇4

文档分类是一个复杂的过程,包括文档预处理、文档表示、分类算法设计、性能评估等主要步骤,文档分类的主要任务有文档的形式化表示以及在此基础上的分类算法设计。目前,一系列分类算法被应用于文档分类,如KNN(K-Nearest Neighbor)、支持向量机(SVM)、决策树、贝叶斯分类算法(Bayes)以及神经网络方法,都取得了较为理想的分类效果。然而,在如此众多的方法中,它们大都是基于向量空间模型。VSM对模型中的特征词进行权重估计过程中不考虑特征词之间的相关性,直接用特征词作为维度构建文档向量,降低了文档向量对文档概念表达的准确性以及对不同类型文档的区分能力[1]。为了取得更好的文档分类效果,本文尝试对文档表示模型进行探索性的研究。另外,为了将文档表示成合适的模型,还必须完成文档的特征降维。文档特征向量的高维性是文档分类的难点之一, 文档特征降维是文档分类面临的主要问题。特征聚类是文档特征降维的一种非常有效的方法。文献[2]首次提出特征分布聚类,根据特征在不同文档中的分布情况对特征进行聚类。文献[3]最早将基于信息瓶颈特征聚类的方法应用在文档分类领域,取得了等同甚至优于其它方法的结果。文献[4]使用K-means、密度聚类方法对特征项进行聚合,取得了较好的特征选择效果,提高了文档分类的效率。文献[5]根据特征间的相似度,对特征进行聚类,在每个簇中选择一个特征代表整个簇,大大减小了特征集的冗余性。本文在基于特征项相关性的前提下,从特征项对于文档类别分布的角度考虑,提出了一种新的特征聚类算法同时实现特征降维和分类器增强。

1特征聚合理论

文档类属判定与文档特征选取的数量和质量相关,若选取特征的数量过大,文档向量的维数太高,则计算开销过大,并且许多特征项对类别归属所能提供的信息很少;而大量减少特征词数量又会丢失许多重要的分类信息。因此,将文档表示成向量后,文档相似度计算常常不能体现特征项之间的内在联系,特征项“各自用力”,不能确切体现文档间的相似程度。

1.1基于相关信息的特征项选择

文献[6]对文档频率(DF)、χ2统计量(CHI)、信息增益(IG)、互信息(MI)等常用的特征选择函数进行了研究,发现IG与CHI的性能最好,类别区分性因子(如IG、CHI)在选择的特征数超过某阈值后,性能基本保持不变,具有非常好的抗噪音能力。其中χ2统计是更加有效的方法,它不仅可以去除冗余信息,而且还可以取得更好的性能。

χ2统计量(CHI)体现了特征与特征之间的相关信息及特征与文档类别之间的相互关联程度。A表示包含特征t且属于类别c的文档频数;B为包含t但是不属于类别c的文档频数;C表示属于类别c但是不包含t的文档频数;D表示既不属于c也不包含t的文档频数;N表示语料中文档总数。特征t与某类别c的CHI如式(1)所示:

$x^{2} (t, c) = \frac{Ν (A D - B C)^{2}}{(A + B) (C + D) (B + D) (C + D)}$ (1)

考虑到N、A+C、B+D均是常数,我们只关心特征词对某个类别的χ2值的大小顺序,而不关心具体的值,故实际计算的时候可以简化为式(2):

$x^{2} (t, c) = \frac{(A D - B C)^{2}}{(A + B) (C + D)}$ (2)

χ2统计值用来衡量特征t和类别c之间的统计相关性。其值越高,特征和类别之间的独立性越小,相关性越强,特征对该类别的贡献越大。特征词的χ2统计值比较了特征项对一个类别的贡献和对其他类别的贡献,利用χ2统计计算特征t和类别c之间的相关性,确定该特征t是否可以代表这个类别。由于χ2统计值很好地体现了特征和类别之间的相关性,因而CHI方法在特征选择中得到了广泛的应用。

1.2特征项聚类

CHI方法在特征选择中效果很好,但在目前的分类算法中,CHI值并没有得到充分的利用。在特征选择过程中,我们计算了每一个特征与所有类别之间的χ2统计量,但是由于对CHI的取值通常只是特征和所有类别的χ2平均值或者最大值,丢弃了很多信息,而在特征选择后CHI值也没有得以利用。如果在分类过程中充分利用特征的CHI值,就有可能得到更好的分类结果。

由于语言表达形式的多样性,能表达同一概念,体现一个类别特点的特征词往往有多个。另外,词与词之间往往存在较强的语义关联。单单依靠特征词的重复而产生的频率信息缺乏统计价值,容易被噪音所淹没。特征项过高的维度通常使得基于距离的相似性度量不再那么有效,而且容易引起较大的计算误差[7]。因此,如果将特征项映射到概念级,将有助于加强同一类别文档的聚合能力。

定义1 当文档被简单地看成是它所含有词或短语组成的集合时,这些词称为项,即文档可以表示为特征项的集合d(tl,t2,…,tn),(1<=k<=n),其中tk代表特征项。

定义2 在文档集合中可以把tl,t2,…,tn看成n维空间的坐标系,每个t得到c(cl,c2,…,cj)个CHI值,表示为χ2 (t,i),(1<=i<=j)。根据tk在c个类别的CHI分布值采用相关算法对相似度进行聚类, 得到m维特征聚类簇。

在大样本条件下,具有相似CHI分布的特征项对文档分类具有相似的贡献。因而我们对CHI分布相似的特征项进行聚类。虽然对分类贡献相同的特征项具有不同的权值,但对分类贡献相近的特征应归属于同一个新特征簇,这个新特征簇包含多个或一个特征词条。

每个特征词t都能得到c(类别总数)个CHI值,每个词都可得到一条对分类的贡献分布曲线,如图1所示。可认为那些有相同分布曲线的特征词是相互关联的,对分类有相同的贡献。因此,我们可以将分类贡献分布相同的词聚合为一个簇,从而最终得到m个不同的分布簇,使用单个簇作为文档向量的一维[8]。

传统的文档特征选择方法通过某种评价函数分别计算单个特征对类别的区分能力,由于没有考虑特征间的关联性,这些方法选择的特征集往往存在着冗余。通过对CHI分布相似的特征项聚类后,类别区分能力强且语义相关的特征被聚集成一组,聚类后的新特征簇具有比较直观的实际意义;包含原始特征空间较多的信息,使得在新特征空间上的统计信息更加可靠;对特征间的冗余性进行裁减,消减特征空间的维数,从而减少分类模型的训练时间与模型规模。

1.3基于类别分布的特征聚类算法

基于类别的统计语言模型是解决统计模型数据稀疏问题的重要方法。目前我们很难找到一种比较成熟且运算量适中、收敛效果好的特征聚类算法。传统的聚类方法以训练语料的困惑度为指导,聚类结果语义信息不明显[9]。

K-means是常用的聚类方法,有较高的执行效率,簇与簇之间有明显区别时,聚类效果较好。但对初值敏感,当存在非凸面形状或差别很大的簇时,聚类精度较低。而凝聚层次聚类的突出优点是它比较符合数据的特性,能够生成比较规整的簇集合,聚类结果不依赖元素的初始排列或输入次序,与聚类过程的先后次序无关,聚类结果比较稳定,有较好的聚类质量,准确度较高。但计算开销较大,对异常数据比较脆弱,容易出现大类现象,不适合大量文件的集合。因而,本文将K-means算法和凝聚层次算法结合起来对特征进行聚类,即能使两种算法的缺点得到部分克服,又能充分发挥两种算法的优势。这种基于K-means和层次聚类的混合算法既能降低聚类时间,在一定程度上又得到较好的聚类结果[10]。

总结起来,可以将该算法步骤表示如下:

1) 应用特征提取理论选取N个特征词条。这N个特征词条满足条件:按照从大到小取前N个相应的特征项的CHI值Zj>阈值θ,由此得出词条具有N个初等模式。阈值θ的选取应根据CHI值的大小,由经验选取。

2) 统计每个初等模式的χ2值。设有C个类别,则每个初等模式都可达到C个χ2值。对每个初等模式的C个χ2值进行统计,可以得到各个初等模式对分类贡献的分布曲线。将各个初等模式对分类贡献的分布曲线标准化。公式如式(3)所示:

BZj = χj2/A (3)

其中BZj表示某一初等模式标准化后的统计值;χj2表示此初等模式的实际统计值;A表示由统计意义上得出的阈值[11]。公式如式(4)所示:

$\frac{Ρ}{C \times Ν} > λ$ (4)

其中P表示小于A的χ2值的个数;C为类别个数;N为初等模式的个数;λ可以取60%、70%、80%、90%等值。

3) 利用K-means算法在整体数据集上进行聚类。由于特征数据集合规模太大,先利用K-means算法在整体数据集上进行聚类。将聚类输出作为下一次聚类的输入,反复进行多次,从而消除初始值对聚类结果的影响,此方法在一定程度上能够将较大或呈延伸状的簇分成若干个小类。

4) 使用K-means方法所产生的类来约束凝聚层次法的凝聚空间,整合可以合并的小类。在层次聚类中,通过在每一步选择相似度最大的来进行聚类。当相近分布的特征聚为一个类别时,由于其在各个类别的频率分布较为接近,聚合后的特征模式分布不会有很大的变化,因而平均信息量(熵)的变化较小。不同类别的特征混合时(即错误的分类),聚合后的特征分布将显著变化,分布更加趋向均匀,使平均信息量增大较大。

聚类和特征选择是相互加强的。一方面,良好的聚类结果将提供良好的类标签,为每个类别选择更好的特征;另一方面,较好的特征选择方法将有助于提高集群性能,提供较好的类标签[12]。我们通过聚类,将相近的特征词映射到了相同的概念簇上,降低了文档向量的维度,即将n个特征项聚合为m个簇,认为每个簇中的所有特征项具有同一个特征属性。约简后的特征加强了特征之间的语义联系,降低了特征的维度。约简后的算法在速度上和性能上都有所提高。本算法的计算复杂度为O(m(n/m)2log(n/m)+m2logm),其中m是约束类的数目。

2图模型文档向量表示

传统的文档分类和聚类算法主要采用向量空间模型(VSM)进行文档表示,向量空间模型将文档表示成一个向量,向量的每一维表示一个特征。根据特征对文档内容表达的重要性每个特征可以获得一个权重,文档每一维特征的权重用TF-IDF[13]公式计算。

在几乎所有真实的文档集中,某一属性在一个类别中的分布与在其它类别中的分布相差甚远,同一属性在不同类别中的重要性(或称相关性)也是不同的。所以,仅仅使用TF-IDF权重公式并不足够,它不能表示出每个属性在特定类别中的重要性大小,而只是从全局的角度衡量了每个属性对于所有类别的区分能力,对某些特定类重要性高的属性不能体现其在这些类中的代表作用,重要性低的属性亦可能极大程度地降低算法的性能。文献[14]针对这个问题,引入信息论中信息增益的概念,提出一种对TF-IDF的改进方法TF-IDF-IG文档表示方法。改进后的方法兼顾了词语在文档集合中的分布情况以及词语在文档集合中的比例分布情况,能较好地表现文档的内容。但无论是TF-IDF还是TF-IDF-IG方法,特征选择及权重计算都是基于频度这个因素考虑的,这样会掩盖一些重要的特征。

图模型是近年来的一个研究热点,它可以形象地描述事物之间的相互联系且便于理解。该方法克服了传统向量空间模型文档表示中词和词之间相互独立、忽略上下文的缺陷。在文档图的表示中,将文档提取的特征项作为表示文档图中的结点,特征词条之间的关系构成文档图中的边,用边上的权值表示相关联的两个特征项之间的共现程度。用图模型表示文档可以反映特征项之间的共现程度以及特征项之间的关联。两个特征经常共同出现在文档的同一个窗口单元(如一句话、一个自然段、一篇文档等),则认为这两个特征在意义上是相互关联的。文档分类的要求是找到类别特征,主要考虑的是特征和类之间的关系,特征和特征之间的关系实际上是由特征和类别之间的关系引申而来。而且一般情况下,一篇文档阐述一个主题,关于同一个主题的特征在一篇文档中同时出现的几率比较高,因此在文档分类应用中,我们选择整篇文档作为窗口单元构造图模型会更加有效。即对每一篇文档构造一个词与词的共现概率矩阵。这里的共现词可以是习惯搭配关系的词对,也可以是属于同一词类的词对,或者是在同一话题中经常出现的词对[15]。它们共现的频率越高,两个特征词的权值也就越大,特征的权值如式 (5)所示:

$W_{i j} = W (t_{i j}, d) = \frac{t f (t_{i j}, d) \times \log_{2} (\frac{Ν}{Ν_{t i j}} + a) \times Ι G_{i j}}{\sqrt{\sum_{t_{i j} \in d} [t f (t_{i j}, d) \times \log_{2} (\frac{Ν}{Ν_{t i j}} + a) \times Ι G_{i j}]^{2}}}$ (5)

其中:W(tij,d)为共现的特征词tij在文档d中的权重;tf(tij,d)为特征词条i和特征词条j在某一窗口单元内的共现频率;IGij为共现的两个特征词条i、j的互信息值;N为文档训练集合的数目;Ntij为文档集合中含有特征词i、j的文档数量;a是一个常量(一般取0.01);log2(N/Ntij+a)为共现的两个特征词条i、j的逆文档频率函数。式(5)权重计算综合了词语位置、词语关系和词语频率等信息,挖掘了隐含的或潜在的关联特征,更加充分地表达文档的语义信息,与人的思维习惯相符,比传统的相互独立的词更有意义。

3文档分类方法

现有的文档分类方法主要有KNN、支持向量机、决策树、线性最小二乘法估计(LLSF)、贝叶斯分类算法以及神经网络等。其中,KNN分类方法是一种稳定而有效的文档分类算法,在现有文档分类方法中应用得比较广泛。它是一种基于实例的文档分类算法,其原理是对于某一给定的测试文档d,在训练文档集中通过相似度找到与之最相似的k个训练文档。根据这k个训练文档的类别来判断待分类文档的类别值。相似度的判定可以使用欧氏距离或向量间余弦夹角来度量。而最相似的k个训练文档按其与测试文档d的相似度高低对类别值加权,将文档分到权重最大的那个类别中从而预测测试文档d的类别值。

文档分类除对文档进行表示外,还必须对文档进行相似度度量。不同的相似度度量方法会出现不同的分类结果。一个文档中的所有特征,构成了文档的整个语义,特征之间的相互关联和共现,对于文档相似度来说是很有意义的[16]。针对传统KNN不涉及向量中各特征间的关系,使得距离计算不精确的不足,提出了一种改进KNN方法,它主要考虑到文档间不同特征项的属性关联与共现对相似度的作用,用两文档之间的匹配系数调整相似度,如式(6)所示:

$S i m_{n} = (α + \frac{n}{| d_{x} |} + \frac{n}{| d_{i} |})^{n - 1} \times S i m (d_{x}, d_{i})$ (6)

其中:n是文档向量dx与di共现的特征项的个数;α为常量,其值反映关联与共现的重要度,该值有一个优选范围;|dx|、|di|是文档d中的特征词总数。

本文结合χ2统计量和特征聚类降维方法对特征空间进行降维处理,每篇文档根据聚类后的特征分布模式构造成一个m维的向量;采用图模型表示关联文档特征,建立文档分类样本空间,用图模型TF-IDF-IG权重式(5)计算特征词的权重并将属于同一模式的所有特征词的权重相加,其和作为m维向量中一维的权重;利用式(6)计算测试文档dx与训练集中所有文档的相似度;对计算出的相似度排序,选出K个最大值,作为dx的最近邻;根据K个最近邻判断dx所属类别,按照式(7)计算每类的权重P,将待分类样本归属为权重最大的类别。

$Ρ (d_{x}, c_{j}) = \sum_{i}^{Κ} s i m_{n} \times y (d_{x}, c_{j})$ (7)

其中:dx表示测试文档;simn为dx与di之间相似度;d1…di…dn为训练集合中与dx相似度最大的k个文档向量,y(dx,cj)为类别属性函数,即如果dx属于类别cj,那么函数值为1,否则为0。

4实验设计

搜狗实验室的互联网语料链接关系库(SOGOU-T)提供了一个大规模互联网语料链接关系对应表,用于验证各种链接关系分析算法的有效性和可行性。实验里我们选择语料关系库中的五大类(C000008财经,C000010 IT,C000013健康,C000014体育,C000024军事)中 5000篇短文用作训练样本,随机抽取1000篇用作测试样本实现文档分类。

训练步骤如下:1) 采用中科院分词工具ICTCLAS对选择的5000篇短文进行预处理。这些短文经过分词处理,统计得到33028个特征词条;2) 对样本语料进行进一步处理,先去除文档频率小于5的词,然后使用开方检验(CHI)算法进行计算,选择出10000多个特征词条;3) 统计出这些特征分别在五个类中的分布值,当λ=80%时统计表明A值应取100,CHI特征提取后选出7465个特征词条;4) 利用基于类别分布的特征聚类算法将7465个(对分类作用相同的词聚合成一个簇)词条聚合成1000个簇,聚类后的部分特征词如表1所示;5) 对语料库中的文档建立图模型,构建求相似度的统一向量模型;6) 最后应用KNN算法对将要分类的文档进行分类,相似度中α=1时优化效果最好,文档d中的特征词总数|dx|、|di|取值为30,KNN中的K=25时,分类效果较好。

我们对这7465个特征词进行了大量的实验,由于没法进行召回率的测试,因此对词汇聚类进行评价的最简单指标是准确率。分别采用K-means和凝聚层次聚类方法将其分为2000、1500、1000、800、700个簇,发现凝聚层次聚类容易出现大类的情况,最大的类有上千维,K-means也存在初值确定的问题。用本文的聚类分析方法得出总词数准确率。特征词聚类维数和准确度的关系如图2所示。

本文采用评估文档分类的主要三个指标:查准率P、查全率R和测试值F1。

$Ρ = \frac{分类的正确文本数}{实际分类的文本数} \times 100 %$

$R = \frac{分类的正确文本数}{应有的文本数} \times 100 %$

$F 1 = \frac{Ρ \times R \times 2}{Ρ + R} \times 100 %$

为了比较在同样的分类语料条件下不同分类方法的分类效果,我们用KNN方法分别对基于图模型的特征向量和基于聚类分析的图模型特征向量进行了分类测试。分类结果如表2和表3所示。

5结语

本文通过χ2统计和特征聚类对特征项个数进行了两次压缩,提出的特征聚类方法选择具有相同分布模式的多个(一组)特征词代替传统算法中单个词来表示向量一维。图模型文档表示方法引入了语义因素在一定程度上解决了关联特征维的提取和向量空间维数高的问题,使得语法语义上具有相同特征的词构成概念簇。特征约简后的文档向量对概念表达更加完善,文档区分度更加显著。实验证明,本文算法对提高分类的精度和速度具有重要的意义。

摘要：针对传统向量空间模型中的特征项孤立处理问题,首先通过χ2统计和特征聚类相结合的模式实现特征降维,然后使用图模型来建立词和词之间相互关联信息,最后运用KNN方法进行文档分类测试。该算法提高了稀有词对分类的贡献,强化了关联词的分类效果,并降低了文档向量的维数。实验证明,该算法提高了分类的准确率和召回率。

分类聚类篇5

1 入侵检测系统

入侵检测系统(Intrusion Detection System,IDS)是软件与硬件相结合的系统,它进行主动的安全防御,对系统和网络的状态进行监视,分析一些关键点的信息,发现外部攻击者的非法入侵行迹和系统内部用户的不合理使用。目前,按照检测方法的不同,可以分为异常检测(Anomaly Detection)与误用检测(Misuse Detection)。异常检测是总结用户正常情况下的操作特征和对资源的使用情况,将其提取为正常模式存储在知识库中,然后将待检查的行为与其比较,如偏差超过设定的阈值,说明出现了异常。误用检测是总结入侵攻击行为模式存储于特征库,然后用匹配的方法将待检测数据与特征库中的模式匹配,若有匹配的模式出现,则说明有入侵。前者可检测出各种攻击,包含从未出现的攻击,但是误报率高。后者虽有高的检测准确率,但漏报率较高,对识别新出现的攻击有欠缺。另外,按数据源不同,入侵检测系统分为基于主机的IDS,基于网络的IDS和混合型IDS。基于主机的IDS的数据来自本地主机的系统日志与审计数据;基于网络的IDS的数据来源于网段中的数据包;混合型IDS是将前两者相结合的检测系统。

2 IDS引入数据挖掘技术

一个好的入侵检测系统应该具有自适应性,准确性和可扩展性。但是常用的IDS的入侵检测规则是通过人工学习补充建立的,安全领域人员了解系统漏洞问题和网络上已经出现的攻击手段,经过学习总结,将其放入特征库,这样特征库的建立完善主要是依赖人的参与。但是,由于现在计算机网络的复杂性,网络攻击情况的多变性,还有网络安全人员对攻击的把握可能不完全准确,会导致IDS检测准确率的有限性。另外,网络数据流量非常大,建立一个完整的特征库要求安全人员的不断学习升级,这对IDS检测的准确性带来影响。将数据挖掘技术应用于入侵检测系统能有效地解决这些问题。

数据挖掘[1](DM,Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在的有用信息和知识的过程。它与人工智能、数理统计、并行计算、数据库等多学科交叉。数据挖掘的方法主要有关联分析、聚类分析、分类分析和序列模式等。本文的自适应入侵检测模型主要用到聚类分析和分类分析。

聚类分析:聚类是将一个数据集分成多个类的过程。聚类分析是一种没有训练数据集用来学习的无指导的学习,以一定的相似性度量方法将数据记录分成多个类,使得经过聚类后,同一个类中的数据有较高的相似度,不同类的数据没有相似性或相似性很低。在进行入侵检测时,一般认为那些包含着大量数据的聚类是正常行为特征的聚类,而包含数据较少的聚类是异常的,因为在实际网络中90%以上的流量都是正常的[2]。常用的聚类算法是K-均值聚类[3]。

分类分析:根据要分析的数据集的一些特征,发现某些数据的共同特性,将数据分成不同的类,得出类别的概念描述或分类规则,当新的数据需要检验时,根据分类规则,将其分到相应的类,常用的分类算法[1]有ID3、C4.5、CART等。

3 引入数据挖掘技术后的自适应入侵检测模型

数据挖掘技术用于入侵检测系统后,入侵检测系统可以自主的进行学习,从而将特征库中的规则不断自我完善,这样的入侵检测系统具有自适应性和可扩展性,检测的准确性也会得到提高。本文的入侵检测模型所用到的规则库不只是包含正常的模式或异常的模式,而是将两者结合起来,运用一定数据挖掘算法判断待检测数据为正常或异常的模型。

该入侵检测模型如图1,分为以下几个模块:

1)数据采集:负责对用户、系统、网络数据流等信息进行收集;

2)自适应模型:积累模式,用一定的数据挖掘算法产生的模式规则库(包含正常和异常);

3)入侵检测:将数据采集器采集到的待检测的数据进行分析,判断是否有异常发生;

4)入侵响应:当检测到异常时,采用一定措施进行响应的处理。

该自适应模型产生和补充完善算法如下,基础是K-均值聚类和决策树算法,将这两种算法进行结合、改进,形成该自适应模型的模式规则库产生与完善的算法。

算法:

1)在原始的网络环境中收集网络数据(包含正常的和异常的数据)

2)选择其中K条数据作为初始质心

3)repeat

4)将每条数据指派到最近的质心,使之形成K个簇

5)重新计算每个簇的质心(质心是簇中数据的均值)

6)until质心不发生变化

REPEAT

7)将聚好的类分配类标号(1,2...K),作为下面进行分类的训练数据集

8)用决策树进行归纳分类,产生分类规则

9)按产生的规则,对一条新的待检测的网络数据(data_x)进行分类(属于某个簇),判断该待检测数据为正常或异常

10)repeat重新计算每个簇的质心(加入了data_x,重新计算)

11)将每条网络数据指派到最近的质心,形成K个簇

12)until质心不发生变化

该算法中,通过该自适应入侵检测模型,正常模式和异常模式规则库会不断完善,因为每条检测过后的数据,不论其为正常或异常,它都会作为一种对判断标准的补充加入到规则库,完善自适应入侵检测模型中的规则库,这样对后来待检测数据的判断也会更加精准。同时,该模型对判断异常数据的不同类型也有一定的区分能力,因为在K个聚类中,异常的聚类中的数据虽然较少,但也会分散在1-N(N

4 结束语

由于传统的防火墙技术本身的缺陷和不足,使得保护计算机网络安全的入侵检测技术越来越为人所重视。为了克服传统入侵检测系统的局限性,将数据挖掘技术引入到入侵检测系统是一个好的选择,能有效提高入侵检测系统的自适应性和检测准确性。该文将聚类算法与分类算法相结合引入入侵检测模型,提出了一种基于聚类的分类分析自适应入侵检测模型。

参考文献

[1]邵峰晶,于忠清.数据挖掘原理与算法[M].北京:中国水利水电出版社,2003,2:132-151.

[2]Ertoz L,Eilertson E,Lazarevic A,Tan P,Dokas P,Srivastava J,Kumar V.Detection and summarization of novel network attacks using data mining.Technical Report[R].University of Minnesota.2003.

分类聚类篇6

关键词：朴素贝叶斯分类器,k-均值聚类,数据挖掘

1 引言

数据挖掘[1]是从大型数据集中将隐含在其中的、人们事先不知道的、对决策有用的知识获取的完整过程。分类是数据挖掘和机器学习中一个重要的研究课题, 它旨在生成一个分类函数或分类模型, 由该模型把数据库中的数据项映射到某一给定类别中, 从而实现对数据的分类。朴素贝叶斯分类器[2] (naive Bayesian classifiers) 是以概率密度函数为基础, 描述分类系统中条件属性和分类属性之间的映射关系。贝叶斯分类器的优点是出错率较小, 但实际上在使用过程中主要存在两个方面的限制:一是先验概率定义困难;二是类别条件独立问题:即独立性假设经常是不满足的。并且独立性假设在一定程度上限制了朴素贝叶斯分类器的适用性, 当处理的数据维数较多, 且数据量较大时, 朴素贝叶斯分类器的效率是偏低的, 且其准确率也有待提高。

针对上述限制, 提出结合k-均值聚类与贝叶斯方法进行分类知识挖掘的解决方案和实现方法。该方法先在数据预处理过程中采用k-均值算法, 得到相互独立的核心属性, 后进行贝叶斯方法的分类知识挖掘。由于k-均值聚类理论的引入, 改善了贝叶斯方法中属性独立性的限制, 提高了分类的准确率。并且由于k-均值算法的引入, 扩大了朴素贝叶斯分类器的应用领域。

2 k-均值聚类算法

2.1 聚类分析

聚类是一个将数据集划分为若干组或类的过程, 并使得同一个组内的数据对象具有较高的相似度;而不同组中的数据对象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定的。为了实现属性聚类, 通常将一块数据区域A描述成一张表, 在表中有n个对象, 主要是用来存放所有n个对象彼此之间所形成的差异。有矩阵

其中d (i, j) 表示对象i和j对象之间的差异 (或不相似程度) 。通常d (i, j) 为一个非负数;当对象i和j对象非常相似或彼此“接近”时, 该数值接近0;该数值越大, 就表示对象i和对象j越不相似。由于d (i, j) =d (j, i) 且d (i, i) =0, 因此就有上式所示矩阵。

2.2 k-均值算法

k-均值算法以要生成的簇的数目k为输入参数, 把n个对象划分成k个组 (k≤n) , 每个组表示一个簇。首先, 随机地选择k个对象作为初始聚类中心, 而对于所剩下其它对象, 则根据它们与这些聚类中心的相似度 (距离) , 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类;然后再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) ;不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数, 具体定义如下:

其中E为数据库中所有对象的均方差之和;p为代表对象的空间中的一个点;mi为聚类Ci的均值。

k-均值算法试图找到使平方误差准则函数最小的簇。当潜在的簇形状是凸面的, 簇与簇之间区别较明显, 且簇大小相近时, 其聚类结果较理想。该算法复杂度为O (nkt) , 其中n为所有对象的数目, k为簇数, t是迭代的次数, 通常k<<n, t<<n。因此, 对处理大数据集合, 该算法非常高效, 伸缩性好。

3 朴素贝叶斯分类器

每个数据样本均是由为一个n维特征向量, X={x1, x2, …, xn}来描述其n个属性 (A1, A2, …, An) 的具体取值;假设共有m个不同类别, C1, C2, …, Cm。给定一个未知类别的数据样本X, 分类器在已知X情况下, 预测X属于事后概率最大的那个类别。也就是说, 朴素贝叶斯分类器将未知类别的样本X归属到类别Ci, 当且仅当:P (Ci|X) >P (Cj|X) , 对于1≤j≤m, j≠i。根据贝叶斯定理:

根据此方法, 对一个未知类别的样本X, 可以先分别计算出X属于每一个类别Ci的概率P (X|Ci) P (Ci) , 然后选择其中概率最大的类别作为其类别。即朴素贝叶斯分类模型为

4 基于均值的朴素贝叶斯分类算法

基于k-均值算法的朴素贝叶斯分类技术就是利用k-均值算法来研究各列属性之间存在的隐含的依赖关系, 将列属性值进行融合, 达到数据预处理目的, 最后再基于朴素贝叶斯方法进行分类。其处理步骤如下:

1.数据预处理:

(1) 随机地选择k个对象作为初始聚类中心, 而对于所剩下其它对象, 则根据它们与这些聚类中心的相似度 (距离) , 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类

(2) 再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) ;

(3) 不断重复 (1) 、 (2) 直到标准测度函数

通过满足方差最小标准的k个聚类, 将其中相关系数较大的属性合并成一个综合属性。这样随后进行的贝叶斯分类中的各个属性间就能尽可能达到属性独立。

2.基于朴素贝叶斯分类算法进行分类挖掘

通过k-均值算法, 改善了条件属性独立性的限制, 符合朴素贝叶斯分类器的要求。由此可得到改进后的基于k-均值的朴素贝叶斯分类算法:先根据互不相关的核心属性集, 求取类的先验概率P (Ci) ;再由类条件独立的假定, 计算;最后通过上述分类器计算式, 得出分类结果。

5 实验结果及分析

本文中使用NBC表示朴素贝叶斯分类器, KMBC表示基于k-均值算法的朴素贝叶斯分类器。为了测试算法KMBC的效果, 选用了UCI机器学习数据库中的7个典型数据库实例, 数据集的基本信息见表1。实验在WINDOWS XP, J2SDK的平台下完成, 首先补齐决策表, 离散化处理, 在测试过程中同样采用交叉验证法;最后将得到的两种结果进行比较, 结果见表1.

由实验过程及实验结果分析发现, 实验所用的数据实例中, KMBC的分类准确率优于NBC。在算法运行时间上, KMBC略高于NBC, 两者之间运行时间的差别并不明显。

6 结束语

针对朴素贝叶斯分类器的条件独立性假设的限制, 本文提出了一种基于k-均值的朴素贝叶斯算法, 先利用k-均值算法对数据进行预处理, 通过属性合并改善条件属性间的依赖性, 找到一组最近似独立的属性结果, 以符合朴素分类器的算法要求。实验结果表明, 改进后的算法可以达到更精确的分类效果。并且当数据量很大, 而各维属性之间又存在隐含关系是, 改进后的算法是处理这些问题行之有效的方法。

参考文献

[1]han j w.数据挖掘概念与技术[M].北京:机械工业出版社, 2001

分类聚类篇7

近年来, 国内外学者对工程项目物流管理的研究主要有对物流过程的组织结构、物流成本效益分析和物流系统运行过程三方面的研究[1]。但在物资分类管理中还存在很多问题, 如大型工程项目在管理工程物资时眉毛胡子一把抓, 缺乏科学有效的管理方法, 不能实现良好的资源配置;本文通过建立大型工程项目物资分类指标体系, 对钢材, 混凝土等十四种主要工程物资采用模糊聚类法分类, 识别对物流管理影响大的关键物资和对物流管理影响小的次要物资并据此配置资源, 根据物资物流特点量体裁衣, 探索大型工程项目的物流管理方法, 为促进大型工程项目物流工作高效完成提供借鉴[2]。

1 大型工程主要物资的分类指标体系

1.1 大型工程物资分类指标体系的建立

大型工程项目的物流管理是指围绕大型工程项目的物资采购、运输、装卸、储存、现场搬运、生产加工、回收、废弃处理等具有综合型复杂内容的全过程物流组织[3], 物资类型主要有结构材料, 装饰材料, 专用材料, 周转材料, 构配件, 施工机械等[4]。大型工程项目物流的主要特点是物流流量大, 涉及高新技术和先进设备的探索性使用, 存在特殊物流单元—超限物资[5]和施工区域呈线性分布等[6]。本文依据影响工程项目物流管理的主要因素, 以科学性与实用性, 整体性与层次性, 通用性与可比性为原则建立大型工程项目的物资分类指标体系, 如图1所示。

1.2 指标权重赋值

采用G1法[7]依据15份专家所填权重调查表确定各指标权重, 权重确定过程如下:

1) 确定序关系。对于评价指标集{x1, x2, …, xm}专家对指标集中的指标进行重要性排序得出序关系:x1*>x2*>…>x*12>x*13。

2) 给出xk*-1与xk*相对重要程度的判断。

专家关于评价指标xk*-1与xk*的重要性程度之比ωk*-1/ωk*的理性判断为:

3) 通过相对重要程度调查表确定rk值, rk赋值表如表1所示。

4) 权重系数ωm*的计算:

5) 指标权重的确定:

取上述指标权重平均值, 得出各指标的最终权重值 (见表2) 。

2 大型工程主要物资的模糊聚类

2.1 模糊聚类简介

按确定的标准对客观事物进行分类的数学方法称为聚类分析, 它是数量统计中多元分析的一个分支, 是一种硬划分, 把每个待辨识的对象严格的划分到某个类中, 具有非此即彼的性质[9]。在大型工程物资分类中往往没有明显的分类界限, 模糊聚类分析的基本思想就是用相似性尺度来衡量事物之间的亲疏程度, 并以此为分类, 因此用模糊理论来进行的聚类分析会更符合客观实际。

2.2大型工程主要物资的模糊聚类过程

1) 原始矩阵的建立。

a.通过发放调查问卷统计分数, 计算各类物资各项分类指标综合得分。

b.指标预处理:将指标分为“成本型”指标和“效益型”指标, “成本型”指标是指指标取值越小越好的分类指标, “效益型”指标是指指标取值越大越好的指标[10]。文中将不可替代性、作用影响程度、需求量、生产周期、生产难度、使用覆盖周期、价格、缺货成本、运输成本、订购成本、储存成本划分为“成本型”指标, 此类指标取值越小越好。将市场流通量、有效使用期划分为“效益型”指标, 此类指标取值越大越好, 据此对指标进行预处理。

成本型指标计算公式:

效益型指标计算公式:

其中, xij为第i种物资的第j个指标的预处理结果;aij为第i种物资的第j个指标未经预处理的综合得分。amaxj, aminj分别代表第j个指标的最大值和最小值。

c.xij计算完成后乘以各指标的权重ωj, 得出原始数据X。

2) 模糊相似矩阵的建立。

对于待分类的工程物资X= (x1, x2, …, xn) 首先要鉴别元素xi与xj的相似程度, 用相似系数rij表示, 区间为[0, 1], 采用欧几里得距离法计算相似系数rij:

由此得到模糊相似矩阵:

3) 模糊等价矩阵的建立。

根据计算所得的模糊相似矩阵R, 不一定具有传递性, 还需要将R改造成具有传递性的模糊等价矩阵R*。用二次方法求R的传递闭包t (R) =R8, t (R) 就是所求的模糊等价矩阵R*。

4) 模糊聚类。

a.将λ取若干不同值 (0≤λ≤1) , 得若干λ截集, 得出物资分类。X1:木材, X2:混凝土, X3:水泥, X4:钢材, X5:砖石砌块, X6:玻璃陶瓷, X7:防水材料, X8:保温材料, X9:建筑门窗, X10:管材, X11:周转材料, X12:通用机械, X13:超限物资, X14:设备配件。

物资分类表见表3。

b.动态模糊聚类图见图2。

c.确定分类。

当λ=0.171 5时, 大型工程主要物资分为八类, 第一类物资包括混凝土, 超限物资, 水泥, 砖石砌块, 钢材, 周转材料, 保温材料, 此类物资在大型工程的物流工作中起着关键影响作用, 以物资在物流管理中的重要性、稀缺性、时效性、成本为依据识别此类物资为关键物资;第二类物资是玻璃陶瓷, 第三类物资是木材, 第四类物资是建筑门窗, 第五类物资是防水材料, 第六类物资是设备配件, 第七类物资是通用机械, 第八类物资是管材, 此七类物资在大型工程的物流工作中影响作用一般, 以物资在物流管理中的重要性、稀缺性、时效性、成本为依据来识别此七类物资为一般物资。

3 大型工程主要物资模糊聚类结果分析

3.1 各类物资物流特点

1) 关键物资。

混凝土, 超限物资, 水泥, 砖石砌块, 钢材, 周转材料和保温材料, 此类物资在大型工程物流管理中的重要性、稀缺性、时效性、物资成本四方面的特点突出。钢材和混凝土广泛应用于大型工程的建筑结构中, 钢材和混凝土共同组成的承重体系是影响建筑结构安全最关键的因素, 其他材料难以替代二者的特殊工程性质, 一旦缺货会使得施工进度瘫痪, 酿成巨大损失, 故在工程物流中钢材和混凝土十分重要。超限物资作为特殊物流单元往往超长超宽或超高超重, 如非标准化的特殊大型设备, 其生产周期长、生产难度大、市场流通量小, 具有一定稀缺性, 在工程建设中需求量少但拥有其他设备无法替代的专业功能, 在整个工程中起关键作用。超限物资的生产地往往距离工程建设地点较远, 运输路线长、难度大、成本高、影响因素多。水泥的运输和储存不能受潮且储存时间不宜过长, 一般情况下自出厂日期起, 超过三个月视为过期, 使用时必须重新检验, 故在工程物流中必须注意水泥的储存环境和时效性管理。砖石砌块和保温材料在施工物资中体积较大, 运输储存过程中需要合理的规划和管理, 在有限的施工场地, 砖石砌块的合理堆放可以避免因现场作业空间狭小和场地交通阻塞造成的施工不便。保温材料的运输不同于其他物资采用重量计算方式, 保温材料往往采用体积计算方式, 因此运输成本较高。周转材料相比其他施工物资, 多出一个逆向物流环节, 只有妥善的现场物流管理和逆向物流管理才能使周转材料在周转中充分发挥其使用价值, 降低工程成本。

2) 一般物资。

包括玻璃陶瓷, 木材, 建筑门窗, 防水材料, 设备配件, 通用机械, 管材, 此类物资在工程物流中市场流通量大, 不可替代性较小, 作用影响程度中等, 生产难度较小, 运输成本、订购成本、储存成本、缺货成本普遍比较小, 其物流管理对整个工程的影响程度偏小。

3.2 大型工程物流管理建议

1) 关键物资与一般物资的物流分类管理。

关键物资中钢材和超限物资等物资的采购需要与优秀的供应商保持长期的战略合作关系, 在降低订购成本的同时保证物资的供应质量, 采购前制定详细的采购计划精确所需物资的数量、规格、型号, 避免出现二次加工、材料退换、材料大量剩余或库存补充频繁等现象, 造成不必要的浪费。水泥的超期和受潮严重影响其材料性质, 应根据施工进度制定采购计划, 避免过早和过量的采购。砖石砌块, 应避免一次性的大批量采购, 尽量选择小批量的频繁采购方式, 在满足工程建设所需的前提下将砖石砌块对施工现场空间占用降至最低。关键物资的现场管理需注意水泥的储存应避免受潮和淋雨, 管理人员应密切关注水泥的存储情况并及时向采购人员反映以配合水泥采购计划的制定, 保证水泥在有效期内充分发挥其功能作用。砖石砌块在有限的施工场地中占用了大量的空间, 易引起施工现场交通阻塞和现场混乱等问题, 造成施工不便, 故施工人员在砖石砌块进场前应做好施工现场规划, 合理布局砖石砌块堆放位置, 使施工现场整洁, 交通流畅的同时方便砌筑工程的取材。钢材在进场前应做好质量、规格、数量的验收工作, 验收后的保管工作主要是为了避免钢材锈蚀和丢失现象。

一般物资种类多, 数量大, 易产生较多管理费用, 故主要以管理成本最小化为目的。基于一般物资可替代性较强, 市场流通量大, 供应商竞争激烈等特点, 采购时主要考虑成本因素。较低的缺货成本允许偶尔缺货, 故应将库存量压到最低水平, 以减少对资金和空间的占用, 降低成本。与供应商及第三方物流建立一般合作交易关系, 降低采购成本。现场物流中, 在保证物资质量的前提下设置合理的储存条件, 避免材料的丢失和破坏, 配合工程的正常施工。

2) 合理利用有效社会资源。

超限物资的运输往往涉及诸多专业难题, 相对于自行运输, 企业可充分利用有效社会资源将任务委托于富有经验和专业性较强的第三方物流, 有效降低物流成本和物流风险的同时集中资源发展核心竞争力。在保证材料供应品质的基础上充分利用当地资源, 就近选择供应商以降低成本, 带动当地经济发展。

3) 制定物流绩效评价机制。

大型工程项目的物流工作需要建立合理的绩效考核来评价物流工作的管理水平, 通过绩效考核寻找物流工作中效率低下的管理环节, 分析导致管理效率低下的主要原因, 针对主要原因进行改造, 不断完善物流管理体系。

4 结语

本文对钢材, 混凝土等十四种大型工程主要施工物资, 凭借分类指标体系运用模糊聚类法进行分类, 在数量庞大种类繁多的大型工程物资中识别对工程影响较大的关键物资和对工程影响较小的一般物资, 并据此对有限的资源进行合理的配置, 集中资源严格控制对工程物流影响较大的关键物资, 降低物流风险, 去繁从简轻巧管理对工程物流影响较小的次要物资降低物流成本, 探索与各类物资物流特性相适应的管理方法实施分类管理, 配合工程质量、成本、进度管理, 使得大型工程项目的物流工作在最短时间, 最低成本和最小风险的情况下顺利完成, 在大型工程的物流管理研究方面具有一定的前瞻性和借鉴性。本文在指标体系的建立和分类对象的选择上具有一定的局限性, 且基于物资分类所提出的管理方法需进一步研究, 提出更科学高效的大型工程物流分类管理方法。

摘要：依据影响工程项目物流管理的主要因素建立分类指标体系且对指标权重赋值, 运用模糊聚类法对钢材、混凝土等大型工程主要施工物资进行分类, 识别对物流管理影响大的关键物资和对物流管理影响小的次要物资, 最后提出了大型工程物流管理建议。

关键词：大型工程,物流管理,模糊聚类

参考文献

[1]吕雪峰.建筑业物流管理关键环节优化研究[D].哈尔滨:哈尔滨工业大学, 2007.

[2]都基娜.浅谈施工企业的物流成本管理[J].物流科技, 2008, 30 (12) :106-107.

[3]郑晓云, 王瑛.施工项目物流成本控制分析[J].低温建筑技术, 2005 (4) :117-118.

[4]马!.加强建筑施工过程中建筑材料管理的具体策略分析[J].科技与企业, 2014 (20) :52.

[5]陈思.大型土木工程项目物流运作管理研究[D].成都:西南交通大学硕士学位论文, 2007.

[6]刘玉明, 王耀球.大型工程建设项目的供应物流模式选择研究[J].物流技术, 2007, 26 (2) :76-78.

[7]乔洪波.应急物资需求分类及需求量研究[D].北京:北京交通大学硕士学位论文, 2009.

[8]张永领.基于模糊聚类的应急物资分类储备研究[J].灾害学, 2012, 27 (1) :130-134.

[9]刘合香.模糊数学理论及其应用[M].北京:科学出版社, 2012.