贾志远21551063第三次读书报告.docx
- 文档编号:17423620
- 上传时间:2023-07-25
- 格式:DOCX
- 页数:11
- 大小:34.54KB
贾志远21551063第三次读书报告.docx
《贾志远21551063第三次读书报告.docx》由会员分享,可在线阅读,更多相关《贾志远21551063第三次读书报告.docx(11页珍藏版)》请在冰点文库上搜索。
贾志远21551063第三次读书报告
硕士研究生读书报告
题目图聚类研究
作者姓名贾志远
作者学号21551063
指导教师贝毅君
学科专业大数据1502
所在学院软件学院
提交日期二○一五年十二月
ResearchonGraphClustering
ADissertationSubmittedto
ZhejiangUniversity
inpartialfulfillmentoftherequirementsfor
thedegreeof
MasterofEngineering
MajorSubject:
SoftwareEngineering
Advisor:
BeiYijun
By
JiaZhiyuan
ZhejiangUniversity,P.R.China
2015
摘要
本文主要是对图聚类算法进行研究,首先介绍了聚类的定义,之后对图聚类进行了简单的解释以及将会使用哪些算法来进行图聚类,然后对图聚类中的一些专业词汇进行了解释说明,最后对划分聚类算法、层次聚类算法、密度聚类算法、网格聚类算法及模型聚类算法进行了详细讲解,同时在图聚类中会用到的一些聚类算法,例如:
Mafkov聚类、谱聚类以及基于密度的聚类进行了描述,对算法的过程进行了详细阐述。
关键词:
图聚类,聚类算法,Mafkov聚类,谱聚类
Abstract
Thispaperismainlystudythegraphclusteringalgorithm.Firstly,thepaperintroducesthedefinitionofclustering,afterthat,thegraphclusteringisexplainedsimplyandwhatalgorithmwillbeused.Thensomeprofessionalwordsrelatedtothegraphclusteringareexplained.Finallythepaperwillexplainthepartitionclusteringalgorithm,thehierarchicalclusteringalgorithm,thedensitybasedclusteringalgorithm,thegridclusteringalgorithmandtheclusteringalgorithmindetail.Atthesametime,itwillusesomekindsofclusteringalgorithmsinthegraphclustering,suchasMafkovclustering,spectralclusteringanddensitybasedclustering,theywillbedescribedsimplyandtheprocessofthesealgorithmsaredescribedindetail.
Keywords:
graphclustering,clusteralgorithms,Mafkovclustering,spectralclustering
1引言
聚类是一个将数据集划分成若干簇或类的过程,使得同一类内的数据对象具有较高的相似度,而不同类之间的数据对象具有较低的相似度[1]。
现有的聚类算法大致分为:
划分聚类算法、层次聚类算法、密度聚类算法、网格聚类算法及模型聚类算法等。
在聚类分析中,一种非常重要的特征模式聚类的变体就是图聚类,它是一项极富挑战性的课题。
所谓图聚类是指把图中相对连接紧密的结点及其相关的边分组形成一个可以用一个抽象结点表示的子图。
子图内各结点具有较高的相似性,而子图之间各结点的相似性较低[5]。
图聚类有很多不同的方式,其中具代表性的有:
Mafkov聚类[2、5]、谱聚类[3]以及基于密度的聚类[4]等。
其中Markov聚类的核心思想是基于模拟随机流(使用图的转移概率矩阵)进行图聚类;谱聚类是通过优化图的最小分割来进行图聚类,其中这个优化问题可以通过解一个图矩阵的特征值特征向量的方法实现;而基于密度的聚类是通过衡量一个点周围邻居的密度来进行图聚类,该算法不仅可以对图聚类,还可以识别出中心桥梁点和异常点。
2相关基本概念
这一部分主要是讲述概念性的东西,为之后的图聚类分析的名词进行概念描述。
2.1图
一个图通常表示为G=(V,E,w)。
其中V是顶点的集合,E是边的集合,w:
E->R是一个边权重函数,把一条边映射成一个实数域上的权重。
如果一个图是无权图,那么每条边的权就是l[5]。
2.2图聚类
图聚类问题是把一个图G=(V,E,w)划分为k个不相交的子图G1=(V,E,w),(i=1,2,……,k)。
2.3相异度
两个对象之间的相异度是这两个对象差异程度的数值化度量,对象越相似,它们的相异度就越低。
而计算对象之间的距离是经常采用的求相异度的方法。
常用的距离算法有曼哈坦距离和欧几里得距离[1]。
2.4聚类分析
聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法,同时也是数据挖掘的一个重要算法。
聚类分析是由若干模式组成的,通常,模式是一个度量的向量,或者是多维空间中的一个点。
聚类分析以相似性为基础,在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。
2.5Markov链(马氏链)
考察一个随机过程,若己知现在t的状态X(t),那么将来的状态X(t+n)取值(或取某些状态)的概率与过去状态X(s)(s 具有这种马尔可夫性的过程称为马尔可夫过程[6]。 对于马尔可夫过程的状态取值为可列无限集或有限集时,通常称为马尔可夫链,简称马氏链。 这一点可适用于随机变量的判别,作为随机变量和非随机变量的主要区别。 3现有聚类的五种算法 前面引言中提到了聚类算法的五种划分,这五种划分中的一些算法在一定程度上都会在图聚类中使用到,下面就对这五种划分进行讲解和分析。 第一种是划分聚类算法。 划分法(partitioningmethods),给定一个有N个元组或者纪录的数据集,将其进行分类,构造K个分组,每一个分组就代表一个聚类, 。 而且这K个分组满足下列条件: (1)每一个分组至少包含一个数据纪录; (2)每一个数据纪录属于且仅属于一个分组(注意: 这个要求在某些模糊聚类算法中可以放宽)。 对于给定的K,算法首先给出一个初始的分组方法,以后通过反复迭代的方法改变分组,使得每一次改进之后的分组方案都较前一次好,而所谓好的标准就是: 同一分组中的记录越近越好,而不同分组中的纪录越远越好。 大部分划分方法是基于距离的。 给定要构建的分区数k,划分方法首先创建一个初始化划分。 然后,它采用一种迭代的重定位技术,通过把对象从一个组移动到另一个组来进行划分。 一个好的划分的一般准备是: 同一个簇中的对象尽可能相互接近或相关,而不同的簇中的对象尽可能远离或不同。 还有许多评判划分质量的其他准则。 传统的划分方法可以扩展到子空间聚类,而不是搜索整个数据空间。 当存在很多属性并且数据稀疏时,这是有用的。 为了达到全局最优,基于划分的聚类可能需要穷举所有可能的划分,计算量极大。 实际上,大多数应用都采用了流行的启发式方法,如k-均值和k-中心算法,渐近的提高聚类质量,逼近局部最优解。 这些启发式聚类方法很适合发现中小规模的数据库中小规模的数据库中的球状簇。 为了发现具有复杂形状的簇和对超大型数据集进行聚类,需要进一步扩展基于划分的方法。 使用这个基本思想的算法有: K-MEANS算法、K-MEDOIDS算法、CLARANS算法。 第二种是层次聚类算法。 层次法(hierarchicalmethods),这种方法对给定的数据集进行层次似的分解,直到某种条件满足为止。 具体又可分为“自底向上”和“自顶向下”两种方案。 例如,在“自底向上”方案中,初始时每一个数据纪录都组成一个单独的组,在接下来的迭代中,它把那些相互邻近的组合并成一个组,直到所有的记录组成一个分组或者某个条件满足为止。 层次聚类方法可以是基于距离的或基于密度或连通性的。 层次聚类方法的一些扩展也考虑了子空间聚类。 层次方法的缺陷在于,一旦一个步骤(合并或分裂)完成,它就不能被撤销。 这个严格规定是有用的,因为不用担心不同选择的组合数目,它将产生较小的计算开销。 然而这种技术不能更正错误的决定。 已经提出了一些提高层次聚类质量的方法。 代表算法有: BIRCH算法、CURE算法、CHAMELEON算法等。 第三种是密度聚类算法。 基于密度的方法(density-basedmethods),基于密度的方法与其它方法的一个根本区别是: 它不是基于各种各样的距离的,而是基于密度的。 这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。 这个方法的指导思想就是,只要一个区域中的点的密度大过某个阈值,就把它加到与之相近的聚类中去。 对于簇中每个对象,在给定的半径ε的邻域中至少要包含最小数数目(MinPts)个对象。 这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点,可发现任意形状的聚类,且对噪声数据不敏感。 代表算法有: DBSCAN算法、OPTICS算法、DENCLUE算法等。 第四种是网格聚类算法。 基于网格的方法(grid-basedmethods),这种方法首先将数据空间划分成为有限个单元(cell)的网格结构,所有的处理都是以单个的单元为对象的。 这么处理的一个突出的优点就是处理速度很快,通常这是与目标数据库中记录的个数无关的,它只与把数据空间分为多少个单元有关。 代表算法有: STING算法、CLIQUE算法、WAVE-CLUSTER算法。 第五种是模型聚类算法。 基于模型的方法(model-basedmethods),基于模型的方法给每一个聚类假定一个模型,然后去寻找能够很好的满足这个模型的数据集。 这样一个模型可能是数据点在空间中的密度分布函数或者其它。 它的一个潜在的假定就是: 目标数据集是由一系列的概率分布所决定的。 通常有两种尝试方向: 统计的方案和神经网络的方案。 4图聚类算法 第一种Mafkov聚类算法。 马尔可夫算法是使用类似形式文法的规则在符号串上操作的字符串重写系统。 马尔可夫算法被证明是图灵完全的,这意味着它们适合作为一般的计算模型,并可以用它的简单概念表示任何数学表达式。 算法步骤: 自顶向下依次检查规则,看是否能在符号串中找到任何在箭头左边的字符串。 如果没有找到,停止执行算法。 如果找到一个或多个,把符号串中的最左匹配的文字替换为在第一个相应规则的箭头右边的字符串。 如果应用的规则是终止规则,则停止执行算法。 返回步骤1并继续。 举个例子来说: 规则是: "A"->"apple" "B"->"bag" "S"->"shop" "T"->"the" "theshop"->"mybrother" "从不使用的"->"终止规则" 符号串是: "IboughtaBofAsfromTS." 执行步骤: 如果算法应用于上述例子,符号串将被以如下方式变更。 "IboughtabagofAsfromTS." "IboughtabagofapplesfromTS." "IboughtabagofapplesfromtheS." "Iboughtabagofapplesfromtheshop." "Iboughtabagofapplesfrommybrother." 算法接着就终止了。 第二种谱聚类算法。 谱聚类算法是建立在谱图理论基础上的,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。 该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量,然后选择合适的特征向量聚类不同的数据点。 谱聚类算法最初用于计算机视觉、VLSI设计等领域,它成为了国际上机器学习领域的研究热点。 谱聚类算法建立在图论中的谱图理论基础上,其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类算法,对数据聚类具有很好的应用前景。 算法步骤: 谱聚类算法将数据集中的每个对象看作是图的顶点V,将顶点间的相似度量化作为相应顶点连接边E的权值,这样就得到一个基于相似度的无向加权图G(V,E),于是聚类问题就可以转化为图的划分问题。 基于图论的最优划分准则就是使划分成的子图内部相似度最大,子图之间的相似度最小。 虽然根据不同的准则函数及谱映射方法,谱聚类算法有着不同的具体实现方法,但是这些实现方法都可以归纳为下面三个主要步骤: 1)构建表示对象集的相似度矩阵W; 2)通过计算相似度矩阵或拉普拉斯矩阵的前k个特征值与特征向量,构建特征向量空间; 3)利用K-means或其它经典聚类算法对特征向量空间中的特征向量进行聚类。 上面的步骤只是谱聚类算法的一个总体框架,由于划分准则、相似度矩阵计算方法等因素的差别,具体的算法实现同样会有所差别,但其本质依然是图划分问题的连续放松形式。 K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。 K-means算法以欧式距离作为相似度测度,它是求对应某一初始聚类中心向量V最优分类,使得评价指标J最小。 算法采用误差平方和准则函数作为聚类准则函数。 K-means算法过程: 1)从N个文档随机选取K个文档作为质心; 2)对剩余的每个文档测量其到每个质心的距离,并把它归到最近的质心的类; 3)重新计算已经得到的各个类的质心; 4)迭代2~3步直至新的质心与原质心相等或小于指定阈值,算法结束。 具体如下: 输入: k,data[n]; (1)选择k个初始中心点,例如c[0]=data[0],…c[k-1]=data[k-1]; (2)对于data[0]….data[n],分别与c[0]…c[k-1]比较,假定与c[i]差值最少,就标记为i; (3)对于所有标记为i点,重新计算c[i]={所有标记为i的data[j]之和}/标记为i的个数; (4)重复 (2)(3),直到所有c[i]值的变化小于给定阈值。 第三种基于密度的聚类。 基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类,无需预先设定簇的数量,因此特别适合对于未知内容的数据集进行聚类。 DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)一个比较有代表性的基于密度的聚类算法。 与层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在有“噪声”的空间数据库中发现任意形状的聚类。 DBSCAN所用到的基本术语: 对象的ε-邻域: 给定对象在半径ε内的区域; 核心对象: 如果一个对象的ε-邻域至少包含最小数目MinPts个对象,则称该对象为核心对象; 直接密度可达: 给定一个对象集合D,如果p是在q的ε-邻域内,而q是一个核心对象,我们说对象p从对象q出发是直接密度可达的; 密度可达的: 如果存在一个对象链p1,p2,…,pn,p1=q,pn=p,对pi∈D,(1<=i<=n),pi+1是从pi关于ε和MitPts直接密度可达的,则对象p是从对象q关于ε和MinPts密度可达的; 密度相连的: 如果对象集合D中存在一个对象o,使得对象p和q是从o关于ε和MinPts密度可达的,那么对象p和q是关于ε和MinPts密度相连的; 噪声: 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。 不包含在任何簇中的对象被认为是“噪声”; 边界点: 边界点不是核心点,但落在某个核心点的邻域内; 噪声就是那些既不是边界点也不是核心点的对象。 DBSCAN算法根据以上的定义在数据库中发现簇和噪声。 簇可等价于集合D中,这个簇核心对象密度可达的所有对象的集合。 DBSCAN通过检查数据集中每个对象的ε-邻域来寻找聚类。 如果一个点p的ε-邻域包含多于MinPts个对象,则创建一个p作为核心对象的新簇C。 然后,DBSCAN从C中寻找未被处理对象q的ε-邻域,如果q的ε-邻域包含多MinPts个对象,则还未包含在C中的q的邻点被加入到簇中,并且这些点的ε-邻域将在下一步中进行检测。 这个过程反复执行,当没有新的点可以被添加到任何簇时,该过程结束。 具体如下: DBSCAN算法描述: 输入: 包含n个对象的数据库,半径ε,最少数目MinPts。 输出: 所有生成的簇,达到密度要求。 1.REPEAT 2.从数据库中抽取一个未处理过的点; 3.IF抽出的点是核心点THEN找出所有从该点密度可达的对象,形成一个簇; 4.ELSE抽出的点是边缘点(非核心对象),跳出本次循环,寻找下一点; 5.UNTIL所有点都被处理。 5总结 本次读书报告学会了很多不同的图聚类处理算法,通过不同的算法,会对图聚类进行不同的处理,其中了解最多的是K-means算法和DBSCAN算法,通过这两个算法,了解到图聚类处理的不同流程,加深了我对图聚类的理解,便于以后对图聚类进行优化,同时也加深了我对机器学习的认知,让我了解到了机器学习更深层次的部分。 参考文献 [1]MarkWMaier,DavidEmery,RichHilliard.Softwarearchitecture: IntroducingIEEEstandard1471[J].Computer,2001,34(4). [2]ZHAOPeng,MUXiaodong,YIZhaoxiang.ResearchonSoftwareFaultDiagnosisinSoftware-intensiveEquipment[J].ComputerEngineering,2008(3): 231-254. [3]MattTelles,YuanHsieh.程序调试思想与实践[M].邓劲生等译.北京.中国水利水电出版社,2002. [4]RTI(ResearchTriangleInstitute).Softwarebugscost[OL].RTLStudyFunds.USA.2002.http: //www.rti.org. [5]J.M.Kleinberg,E.Tardos,Approximationalgorithmsforclassificationproblemswithpairwiserelationships: MetriclabelingandMarkovrandomfields,JournaloftheACM49(5)(2002)14–23. [6]SatuElisaSchaeffer.Graphclustering[J].ComputerScienceReview,2007: 27-64.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贾志远 21551063 第三次 读书 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)