还剩60页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
北京交通大学毕业设计(论文)毕业设计(论文)中文题目微博舆情管理平台数据分析系统的设计与实现英文题目:MicroBlogPublicOpinionManagementPlatform:TheDesignandImplementationoftheDataAnalysisSystem中文摘要随着网络技术应用的普及和发展,舆情的传播方式和传播速度都发生了根本性变化网络舆情对人类的社会状态产生了全方位的影响,微博舆情则是网络舆情的重要组成部分,它的特点有直接性,突发性,偏差性,丰富性和互动性本文以微博消息为研究对象,研究了微博消息传播的特点与模型,通过对抓取数据的分析发现了微博传播的单向性,便捷性,背对脸等特点,还有微博意见领袖在微博传播中的重要作用,微博热点的产生规律根据对数据分析的结果提出了趋势分析的算法利用空间向量模型完成对微博内容的结构数据化,利用K-means算法完成对微博消息的聚类分析,找到所要分析的某类微博内容,进而在这类微博中找出微博消息意见领袖,提出微博意见领袖影响力评估算法,WeiboRank算法,并结合算法完成了微博消息预警模块的实现,初步实现了微博舆情管理平台的数据预警分析功能关键词微博舆情文本聚类趋势分析AbstractAlongwiththeuniversalapplicationandrapiddevelopmentofnetworktechnologytheapproachesthatthenet-mediatedpublicsentimentspreadhavebeenfundamentallychanged.Thenet-mediatedpublicsentimenthasexertedhugeinfluenceonthewaythatthesocietyoperates.Astheoneofthemostsignificantpartsofthenet-mediatedpublicsentimentthepublicsentimentwhichisproducedandspreadbythemicrobloghasseveralimportantcharacterssuchasdirectnessimmediacydeviationvariabilityinteractivity.TakingthemicroblogmessagesasourinvestigatingsubjectthispaperaimedtodoresearchonthecharacteristicsandmodelsofdeliveringmessagesbetweenmicroblogusersThroughtheanalysisofthecapturedatafoundunidirectionalmicro-blogcommunicationconveniencebackonthefaceandothercharacteristicsandraisedaneffectivealgorithmtosortthesekindsofmessages.UsingthespatialvectormodeltheK-meansalgorithmdidclusteranalysisonmicroblogmessagesandfoundouttheopinionleadersamongtremendousmessages.Thenaninfluentialestimationalgorithmofthemicroblogopinionleaderswasraised,WeiboRankalgorithm.Togetherwiththeestimationalgorithmwealsoachievedtheearlywarningpartandsomebasicdatawarninganalysisfunctionsonthewholemicroblog-mediatedpublicsentimentplatform.Keywords microblog-mediatedpublicsentimenttextclusteringtrendanalysis目录TOC\o1-3\h\z\u
一、概述
11.1课题背景与研究意义
11.
1.1课题背景
11.
1.2研究现状
31.
1.3研究意义
31.2论文结构4
二、微博消息传播模型
42.1微博消息传播的特点
42.2微博用户状态
62.3微博意见领袖
72.4微博传播模型9
三、微博舆情管理平台的设计与实现
123.1微博舆情管理平台的总体流程
123.2数据分析系统设计流程13
四、微博舆情管理平台的实现
144.1样本选取与数据来源
144.2微博数据转化
154.3微博文本聚类
174.
3.1文本聚类定义
174.
3.2机器学习
184.
3.3K-means算法
194.4微博意见领袖重要性评估
214.
4.1PageRank算法
214.
4.2WeiboRank算法
224.
4.3算法对比
234.5微博舆情预警模块
254.
5.1微博舆情预警
254.
5.2趋势分析模块
264.6趋势分析结果比较29
五、结论与展望
315.1系统不足
315.2未来展望
325.
2.1改进预期
325.
2.2新增功能
325.3结束语33参考文献34附录Ⅰ翻译原文35ClusterAnalysis:BasicConceptsandAlgorithms351Overview
401.
1.1WhatIsClusterAnalysis
401.
1.2DifferentTypesofClusterings
411.
1.3DifferentTypesofClusters
442.RoadMap47•K-means47•AgglomerativeHierarchicalClustering48•DBSCAN48附录Ⅱ中文翻译48聚类分析基本概念及算法481概述
511.
1.1什么是聚类分析?
511.
1.2不同类型的群集合
521.
1.3簇的不同类型
532.路线图56•K-means算法56•凝聚层次聚类56•DBSCAN
561、概述
1.1课题背景与研究意义
1.
1.1课题背景随着时代的进步,技术的发展和web
2.0时代的到来,网络舆情也呈现蓬勃发展的势头,截至2012年12月底,我国网民规模达
5.64亿,手机网民规模也已达到
4.20亿,我国微博用户规模为
3.09亿,较2011年底增长了5873万,网民中的微博用户比例较上年底提升了六个百分点,达到
54.7%相当一部分用户访问和发送微博的行为发生在手机终端上,截至2012年底手机微博用户规模达到
2.02亿,即高达
65.6%的微博用户使用手机终端访问微博微博,即微博客(MicroBlog)的简称,是一个基于用户关系信息分享、传播以及获取平台,用户可以通过WEB、WAP等各种客户端组建个人社区,以140字左右的文字更新信息,并实现即时分享美国埃文·威廉姆斯推出的twitter是最早的微博平台,也是目前最著名的平台2007年,中国第一家带有微博色彩的网站“饭否网”开张,到2009年新浪微博的开通,中国第一家推出微博的门户网站,微博正式进入中文上网主流人群视野2011年10月,中国微博用户总数达到
2.498亿,成世界第一大国微博成为网络舆情的一大组成部分舆情是“舆论情况”的简称,是指在一定的社会空间内,围绕中介性社会事件的发生、发展和变化,作为主体的民众对作为客体的社会管理者及其政治取向产生和持有的社会政治态度它是较多群众关于社会中各种现象、问题所表达的信念、态度、意见和情绪等等表现的总和对于舆情的内涵,国内的研究者们有着不同的认识有研究者指出“所谓‘舆情’,实际上就是大众密切关心的热门话题或反映了某些社会心理的观点与看法,其较高层次是‘思潮’,基本层次是‘情绪’大众传媒对此应该有足够的敏感,并以恰当的方式进行舆论引导,减少社会震荡”另有研究者认为“舆情即民意情况,涉及公众对社会生活中各个方面的问题尤其是热点问题的公开意见外露的部分或情绪反应既可能外露又可能不外露的部分”更多的学者倾向于如下认识“舆情是指在一定的社会空间内,围绕中介性社会事件的发生、发展和变化,民众对社会管理者产生和持有的社会政治态度如果把中间的一些定语省略掉,舆情就是民众的社会政治态度”这一定义将舆情界定为民众的社会政治态度,突出了民众与国家管理者之间的关系,抓住了舆情的核心,因此本文在以下的论述中,也采用这一定义任何一种技术的出现及发展,或多或少会对社会生活造成一定的冲击和影响网络从诞生的那一天起,就开始深刻地影响人们的生活、学习、思考、交流和娱乐的方式与此同时,现实生活与虚拟世界交互影响,呈现出一种你中有我、我中有你的局面以网络为平台,通过新闻、评论、发帖、回复等为载体表现出来的舆情,就是网络舆情以网络为载体的网络舆情,核心是单个或多个事件,是海量网民感情、态度、建议、观点的表达,互动与传播,以及后续的影响力的集合带有广大网民的主观性,未经媒体验证和包装,直接通过多种形式发布于互联网上舆情管理与监控,就是通过对互联网信息挖掘采集技术的整合,实现自动抓取互联网中的海量信息,可以利用一些算法自动对信息分类,主题分析,倾向分析等功能,形成图表或者简报结论,便于用户掌握舆情的本质是民众的社会政治态度,而在网络上,某种抽象的社会政治态度是需要以一些具体的形式反映出来的或者说,舆情在网络上要为人所知、激起网民共鸣、或者在网络上被传播,必然要借助于一定的载体在网络上,舆情的载体主要有新闻评论,论坛社区发帖、跟帖,博客,播客,微博等与传统舆情相比,网络舆情具有传播快速和实时互动的特点网络的出现使得地球村的梦想得以实现,一条消息可以在瞬间传遍世界相应的,某个舆情通过各大网站、论坛的转贴可以在极短时间内为大量人知晓,这在以前是难以想象的;在网络舆情体现最明显的论坛、社区、博客、微博等空间,每一个网民都可以实时地发表自己的观点,大家共同讨论或辩论,不同观点或立场的网民进行交锋,可以通过互动推动舆情的发展或深化,引起更多人的关注
1.
1.2研究现状随着网络技术的发展和时代的进步,网络舆情的重要性已经毋庸置疑,有关网络舆情管理与检测的研究也日趋成熟,有关网络舆情管理与监测的系统越来越多,微博舆情的分析平台也有出现,不过多数为政府和企业服务,只监控有可能爆发的负面信息和重大事件,不对普通用户开放,而有关微博消息的分析软件不但费用昂贵而且只是对信息的已传播轨迹进行呈现和分析,缺乏对微博消息未来走向的一个分析预测,也无对微博消息传播范围广度的分级
1.
1.3研究意义网络舆情反映了民情民意,在为国家管理者决策提供参考依据的同时也存在引发社会问题的风险,尤其是国内外敌对势力经常利用互联网,别有用心地煽动不良情绪或发动串联,以期影响我国社会稳定因此,研究如何发现互联网上的舆情、做出预警并在必要时采取合理的预控措施,成为摆在相关部门面前亟待解决的问题
1.2论文结构论文分为4章第一章概述介绍了我选择这个课题的背景,叙述了目前国内外关于微博舆情管理平台的研究现状,分析了微博舆情管理平台的重要意义第二章分析了微博消息传播的模型,研究了微博消息传播的特点,建立了微博消息传播的模型第三章概述了微博舆情管理平台的总体流程,详细讲解了数据分析系统的设计流程,讲述了分词模块,聚类模块及趋势分析模块的算法思想,基本原理第四章针对数据分析系统的局限性,提出了未来的改进方向
二、微博消息传播模型
2.1微博消息传播的特点微博舆情作为网络舆情重要组成部分,有着与网络舆情共同的特点,网络舆情的特点有以下几点直接性,突发性,偏差性,丰富性和互动性网民根据现实社会或者网络上发生的新闻可以在各种平台上直接发表自己的见解和意见,根据其他网民的见解进行交换观点,而网络的虚拟性也使虚假不良信息的发布变得容易和更具蛊惑性,容易成为热点这也对网络舆情的监管提出了要求而微博也有其自身独特的特点便捷性,原创性,背对脸随着智能手机的普及以及各种便捷移动电子设备的出现,各种微博移动终端使得微博消息的发表与接收变得非常便捷,使得网络舆情的直接性和突发性表现的更为突出而以新浪微博为例,其用户可以选择一个或多个的关注组别,例如娱乐,新闻,经济等,这就让用户可以更加便捷的了解自己需要的某些方面的信息微博的便捷性让网络舆情的消息爆发更加突然,在前不久的雅安地震中,震后3分钟即有第一条关于震区震后实情的微博消息出现,这与微博的便捷性是分不开的微博消息是由140字左右的短文本构成的,所以其原创性远大于例如BBS,论坛,博客等平台,可能表达的意思相同,但发出的微博却不一样,同样以雅安地震为例,“为雅安祈福”,“雅安平安”,“支援雅安”等消息出现在微博上,虽然是不同文本,但同样表达了对雅安地震灾情的关注和祝福,这种原创性大大丰富了微博的内容,也直接体现了网络舆情的偏差性与丰富性但也为微博舆情管理增加了难度,对微博内容的分类提出了更高的要求背对脸这种特性,则是很生动表明了微博与平常网络平台相比最大的特点,其传播消息的途径是单向的,被关注者发布消息无需理会关注者的反应,关注者关注着被关注者的消息,就类似一个人在玩电脑游戏,而他的粉丝就是站在他背后观看的人,观看者可以看到游戏的进度,但游戏者却不用理会观看者在做什么,这就是微博消息传播背对脸的特性根据微博典型的这3种特点,我们看出它与其他网络平台舆情传播的显著差别,而想要对微博舆情进行管理,必须很好的利用这三种特点
2.2微博用户状态在调研文献时,病毒在传播的时候会出现三种用户状态,感染态,免疫态,易感染态由于病毒传播与微博消息的相似性,假设一个用户发布一条消息后,他的粉丝用户都一定会看到这条消息,类比病毒传播的三种状态,将微博用户也分为三种状态,未知状态,转发状态,已知不传播状态未知状态就是不知道消息的状态,通常就是他所关注的人中没有传播这条消息;转发状态就是这个用户知道这条消息,并且对这条消息很感兴趣,转发了这条状态,就把这条消息通过他的粉丝继续传播了下去;已知不传播状态则是知道了这条消息,但是因为不感兴趣,没有转发这消息或发布相关的消息如图2-1所示,这是一个用户状态示意图,用户A发布了一条状态,B和C关注了A,所以知道了A发布的消息,B不感兴趣,忽略了这条消息,成为了已知不传播状态,这条消息的传播在B处中断,而C对这条消息很感兴趣,转发了这条消息,则成为转发状态,继续向C自己的粉丝传播这条消息,则D由不知道这条消息的未知状态变为了知道这条消息的已知不传播状态,而E关注了B,虽然被D关注,但根据微博背对脸的特性,E无法知道这条消息,一直处于未知状态在消息传播过程中,这三种状态是单向转变的,未知状态可以变成已知不传播状态,已知不传播状态可以变成转发状态,但不能反向转变,已知不传播状态可能在多次从不同用户得知同一消息后变得感兴趣从而转变为转发状态图2-1微博用户状态图
2.3微博意见领袖意见领袖这一说法起源于20世纪40年代初传播学关于媒介传播效果的研究,传播学者拉扎斯菲尔德在1940年美国大选的调查研究中发现,大部分选民的投票不依靠大众传媒,依靠的是身边的亲戚、朋友和团体的影响从而有了意见领袖这一概念,在人际传播网络中经常为他人提供信息、意见、评论,并对他人施加影响的“活跃分子”,是大众传播效果的形成过程的中介或过滤的环节而在微博消息传递过程中,人际传播网络化为微博用户传播网络,微博意见领袖在其中发挥着巨大作用【10】微博意见领袖通常有着数量庞大的粉丝群,通常用户有着几十或几百的粉丝,而微博领袖的粉丝数量则通常为上万甚至几十万上百万,成为微博平台上的明星,通过发布微博消息领导着他们的粉丝意见通过对收集到的数据的分析,从数据表明,基本上可以认为20%的意见领袖用户领导着80%的用户的意见,如图2-2,从一条转发量为561次的微博消息的前10名的数据可以看出,昵称为“思想焦距”“杜子健”“历史尘封档案”的3位用户是此次消息传播中最重要的3位意见领袖排名昵称粉丝用户类型时间二次转发1思想焦距1209767个人认证2013-3-915:03:003682杜子健324621个人认证2013-3-913:07:01513历史尘封档案538570微博达人2013-3-915:45:02404煮酒谈史214251微博达人2013-3-916:11:35375人性之美丽213917微博达人2013-3-915:06:26226长江直播47390微博达人2013-3-915:17:05187敌我媒体采访团275145个人认证2013-3-915:03:0698彭三金176135个人认证2013-3-915:03:0739笑着做教师11370个人认证2013-3-916:38:55310王周生7162个人认证2013-3-915:23:093图2-2微博消息影响力前10名不过转发量并不是判断意见领袖影响力的唯一标准,包括粉丝数,转发率以及活跃程度均是评估意见领袖影响程度的重要参考标准,通过对实验数据结果的总结,发现微博意见领袖有以下几个特点基本上所有的微博意见领袖均是新浪认证用户,图2-2也说明了这一观点,而且认证用户容易获得普通用户认可和接受,发布消息的真实性也比较可靠认证用户中有部分是在现实社会中有着一定影响力,微博则是其社会影响力在网络中的映射粉丝数量也不是必然要求,类似消息的二级传播原理,活跃且粉丝质量高的用户也会有相当大的影响力,这也是一些草根用户能够成为影响力大的意见领袖的原因草根用户积极参与用户间的互动,并且努力发布有价值的消息给粉丝,也可以获得较大的影响力也有部分用户从来不与粉丝互动,但其绝对粉丝数量较多,也可以获得较大影响力也有草根用户凭借实时发布极有价值信息发布获得较大影响力,随之而来的则是转发和粉丝数量激增总结上述特点可以得出评估用户影响力的标准粉丝数,转发率,历史转发率(该用户的活跃程度),是否认证用户具体重要性的评估算法将在
3.5节具体阐述
2.4微博传播模型由微博背对脸的特点可以知道微博消息传播的单向性,类似病毒的传播,病毒感染一台主机则这台主机进入感染态,而感染一台服务器,则访问这台服务器的所有主机都会了解这个病毒,或感染或免疫,微博中消息传播也是如此,普通用户相当于终端,而微博意见领袖则相当于服务器,区别在于,消息的接受是被动的,只要登录微博就能看到关注者的消息,而不用像用户一样需要登录服务器通过对抓取的微博数据的分析,发现20%的用户领导着80%的用户意见,而且越是在消息初期,微博意见领袖的作用就越大,意见领袖的加入会使消息有一个爆炸式的增长,而随着加入的意见领袖增加,消息传播增长趋势放缓,意见领袖的作用降低,当消息的传播广度到达一定范围后,意见领袖的影响力就趋近于零了图2-3是一条有关波士顿爆炸案的微博消息路径图的一部分,通过图2-3可以看出意见领袖在微博消息传播所占的重要作用,是传播路径上的重要节点,与消息传播的广度息息相关图2-3微博消息传播路径图通过对数据分析可以发现在消息的传播广度和初始微博意见领袖加入的多少有一定关系,当单位时间内意见领袖的影响力达到了一个阈值M后,可以认为在之后的一段时间内,此消息的传播范围会有一个明显的增长,关于M值会在
3.6详细介绍通过研究发现,消息成为热点中有以下3种规律,每一种都会在热点的成长曲线中出现对一个范围内的微博意见领袖进行监控,发现意见领袖对一条微博消息的转发比例达到10%时,可以认为此消息会有一个广泛的传播,会成为一个热点话题;通过对已知此消息但未转发的意见领袖的比例与已知此消息并转发的意见领袖所占比例的对比,可实现对未来的微博消息传播范围的判断;在单位时间内(设为1个小时)的消息传播量达到一个阈值M后,可以认为此消息传播进入爆发期,会出现较大增长,通过设置不同M值,可对未来的消息传播范围有一个大致的分级,不同级别表示预测此消息传播的最大广度从趋势分析角度来说,以上3种规律无论应用哪一种均可以对消息传播趋势做一个分析,采用多种规律对趋势分析精度的提升也是有限的,而对一种规律分析的足够透彻已经可以达到一个接受的趋势分析的准确度了
三、微博舆情管理平台的设计与实现
3.1微博舆情管理平台的总体流程微博舆情管理平台的三大模块如图3-1所示,分为微博信息数据获取模块,数据分析模块,分析结果呈现模块,本文主要研究的是数据分析模块图3-1微博舆情管理平台三大模块微博舆情管理平台的主要流程如下,首先输入要查询的微博消息的关键词或核心微博,然后利用网络爬虫来收集微博中的消息内容,包括微博内容,转发关系,博主ID,发布时间等然后进入中文分词模块,将微博内容分词后进入VSM,将微博内容的文本数据转化为计算机可以处理的结构化数据,将所有相关微博内容预处理后,进入K-means算法对微博内容进行分类,找到离关键词最近的那个类,认为这个类中的微博内容表达的是同一意思,并作为数据分析的主类,然后找出类中符合意见领袖标准的微博领袖逐一进行影响力评估,分析出各意见领袖的影响力指标,然后进入趋势分析预警模块,根据微博的走势代入趋势分析算法进行分析,得出结果将数据上传到管理平台,管理平台对数据进行处理将结果输出
3.2数据分析系统设计流程数据分析系统的主要流程如图3-2所示,获得关键词或核心微博后,从数据库中获取微博相关数据,将微博内容与微博ID挂钩,用中文分词系统将微博内容进行分词,然后在数据库中新建一表项,用于存储分词后的文本内容,继续以微博ID为区分,将分词后的文本放入K-means算法中进行迭代聚类,选出关键词或核心微博所在类为相关微博类,删除数据库中其他无关微博,进而筛选出符合微博意见领袖定义的用户,进入微博意见领袖影响力评估算法,分析出每个意见领袖的重要程度以小时为单位,计算单位时间内的微博内容传播广度,设定不同等级阈值M,存在超过M值的时间段即可分析预测出消息未来走势,进而将意见领袖重要性在前10名的用户数据反馈数据库,将用户按时间顺序进行排序存储到数据库交给管理平台进行结果反馈,这就是整个数据分析系统的主要流程图3-2微博舆情管理平台数据分析系统主要流程
四、微博舆情管理平台的实现
4.1样本选取与数据来源网络爬虫的主要功能是搜集Internet中的各种信息它利用网页中的超文本链接Hyperlink来访问网页,从一个事先制订好的URL列表开始,这个列表中的URL一般是从过去的访问记录里提取出来的,通常是一些比较流行的站点和新闻网页,利用HTTP等标准协议,通过URL从一个页面爬行到另一个页面,直到没有满足条件的新的URL产生为止
4.2微博数据转化向量空间模型(VectorSpaceModel,简称VSM),其主要思想是以向量空间中的向量运算来处理文本内容,并且使用空间上的相似性来描述语义的相似性,如图4-1所示此时,就可以通过计算向量间的相似性来度量文档间的相似性向量空间模型主要涉及以下两方面的工作1)构建向量表示文档、查询中的词项2)度量任意文档向量和查询向量的相似性以下则对该三方面的工作进行详细介绍1)构建向量表示文档中的词项对于文档集中的每一个不同的词项,在向量中只记录一个分量图4-1VSM主要思想如果词项出现,则在对应向量的分量处记1;如果词项未出现,则在对应的分量处记0经过向量化的文档,就可以在坐标系中表示,如图4-2所示图4-2VSM文档向量化表示示例然而,二值表示的方法并没有考虑一个词项在文档中出现的次数所以,扩展这种表示形式,将词项在文档中出现的频率作为向量中各个分量的值在图4-2中,如果文档D2中A出现了两次,则向量表示为20通过使用向量空间模型,文本数据被表示为计算机能够处理的结构化数据此时,通过比较两个向量的相似性就能解决两个文档之间的相似性问题2)度量任意文档向量和查询向量的相似性余弦距离经常被用在文本相似性比较中余弦结果为一个0到1的数,1表示向量一致,0则表示正交,符合相似性百分比的特性不同文档长度的归一化是通过计算向量内积与文档向量的长度的比值实现的,即前提是忽略文档向量长度的影响假设文档向量为di=di1di2⋯dit,查询向量为Q=wq1wq2⋯wqt余弦的计算公式经过VSM分类的文本文档,可以看做粗略的分类,不过不够精确,所以需要后续的文本聚类的精确分类来确定所需要的微博消息
4.3微博文本聚类
4.
3.1文本聚类定义所谓聚类,就是一个集群的集合聚类的目的是找到对象组,进一步目的是通过数据分析确定对数据分析有用的群体文本聚类就是从很多文档中把一些内容相似的文档聚为一类文本聚类的基础是著名的聚类假设聚为一类的文本相似性较大,而聚为不同类的文本相似性较小文本聚类是一种无监督的机器学习方法,不依赖于训练过程,并且不需要提前手动划分文本类别,因此具有一定的灵活性和较高的自动化处理能力目前,文本聚类已经成为对文本信息进行摘要、组织和导航的重要手段,受到了越来越多的关注一个文本表现为一个由文字和标点符号组成的字符串,由字或字符组成词,由词组成短语,进而形成句、段、节、章、篇的结构要使计算机能够高效地处理文本,就必须找到一种理想的形式化表示方法下面所介绍的文本聚类算法是在空间向量化模型的基础上实现的文本聚类算法有划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法本系统使用划分法进行文本聚类划分法对于一个有N个记录的数据集,将构造K个分组,每一个分组属于同一个聚类,KNK个分组所要满足的条件1)至少一个数据纪录属于一个分组2)每一个数据纪录属于且仅属于一个分组对于给定的K,算法首先给出一个初始的分组方法,通过迭代的方法来不断优化分组,每一次优化后的分组方案都会较前一次好这里提到的好的标准是对于同一个分组中的记录,越近越好;对于不同分组中的记录,越远越好【9】目前,常用的使用这个思想的算法有K-means算法、K-medoids算法,系统中使用的是K-means算法
4.
3.2机器学习机器学习MachineLearning是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能机器学习的研究是根据生理学、认知科学等对人类学习机理的了解,建立人类学习过程的计算模型或认识模型,发展各种学习理论和学习方法,研究通用的学习算法并进行理论上的分析,建立面向任务的具有特定应用的学习系统机器学习是研究如何使用机器来模拟人类学习活动的一门学科稍为严格的提法是机器学习是一门研究机器获取新知识和新技能,并识别现有知识的学问这里所说的“机器”,指的就是计算机机器学习按学习形式分类,可分为监督学习与非监督学习监督学习,即在机械学习过程中提供对错指示一般实在是数据组中包含最终结果(0,1)通过算法让机器自我减少误差这一类学习主要应用于分类和预测regressionclassify非监督学习又称归纳性学习(clustering)利用K方式Kmeans,建立中心(centriole),通过循环和递减运算iterationdescent来减小误差,达到分类的目的K-means文本聚类算法就是一种应用非监督的机器学习的划分法文本聚类算法
4.
3.3K-means算法K-means算法是属于划分类的聚类方法,它的基本原理如下1.用户输入想要划分的文本聚类输n2.随机选择n个文本作为聚类中心3.对其他文本计算到这n个聚类中心的距离,并把它分到距离最近的那个聚类里面4.重新计算聚类中心5.重复步骤3,4直到达到用户的设定条件为止【9】图4-3K-means算法流程图K-means算法的基本思想是先设置一个聚类数目n,系统随机选择n个文本作为初始的聚类中心,然后挨个比较每个文本与各个类中心的相似度,将它赋予给最相似的那个类中心所在的类然后重新计算选择每个类的中心进行不断循环迭代,直到目标函数收敛不再变化
4.4微博意见领袖重要性评估从前文中可以知道,微博意见领袖在微博消息传播中的重要性,而意见领袖本身也存在着影响力不同的问题,所以根据PageRank算法提出改进的WeiboRank算法来对意见领袖的重要性进行评估
4.
4.1PageRank算法著名的PageRank算法是衡量网络中节点重要程度的经典算法是Google排名运算法则(排名公式)的一部分,是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个网站的好坏的唯一标准在揉合了诸如Title标识和Keywords标识等所有其它因素之后,Google通过PageRank来调整结果,使那些更具“等级/重要性”的网页在搜索结果中的排名获得提升,从而提高搜索结果的相关性和质量基本思想如果网页T存在一个指向网页A的连接,则表明T的所有者认为A比较重要,从而把T的一部分重要性得分赋予A这个重要性得分值为PR(T)/CT其中PR(T)为T的PageRank值,CT为T的出链数,则A的PageRank值为一系列类似于T的页面重要性得分值的累加优点是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间不足人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性降低;另外,PageRank有很严重的对新网页的歧视PageRank的核心思想是每个节点的PR值根据反向链接的数量,均匀“流”向所有的关系节点每个节点的PR值为所有邻居好友对其贡献PR值的综合
4.
4.2WeiboRank算法微博中用户的传播影响力受到很多因素的影响,例如用户的跟随者数量、关注用户量、帐号是否有认证,以及微博本身的质量、新鲜度等同时与微博用户自身的活跃性、是否经常登录微博、发布和分享信息也有很大的关系通过借鉴PageRank算法的设计思想,综合考虑用户的传播意愿的互动程度,提出了WeiboRank算法来准确评估每个节点的传播影响力给定一个权重有向网络G=V,E,W,节点为V,边为E,边权为w,其中i和j节点间边权Wij表示节点i对节点j的影响力本研究中边权Wij采用历史转发比率Rtij来表示历史转发比率是指用户j曾经转发用户i的微博的次数与用户i总转发微博数的比率定义如下式中Rtc(i,j)是用户j曾经转载作者i的微博的次数显然,如果用户j过去经常转发i的微博,今后也很有可能转发SCi为用户i在监测时间段内所转发的所有微博数量式1是将用户历史转发状况进行归一化处理为了衡量邻居i对J的重要程度,本文提出节点间亲近率的概念亲近率定义为节点d对i的历史转发率和所有节点J转发过的用户节点的历史转发率之和的比值其物理上表征在节点j的所有邻居的互动关系中,节点i相对于j的重要程度亲近率Ci,j定义如下从亲近率定义中可以看出,其综合考虑了用户的传播意愿和与其他节点互动的程度在微博信息传播网络中,我们借鉴PageRank算法的核心思想,提出weiboRankwR算法来评估每个节点的信息影响力,定义如下式中,WRi是节点i的WeiboRank值,B是指向i的节点的集合,其中Ci,j是节点j的传播影响力分配给i的比例因子,这里采用上文定义的亲近率d是阻尼系数,可设定在0,1之间,本文中选取0.85将所有节点的WeiboRank初始值设为0.1,通过迭代到收敛为止,可以得到所有用户的WR值
4.
4.3算法对比为了对比WeiboRank算法对用户传播影响力的识别准确性,采用以下2种常用评估微博用户影响力的方式1被转发量Retweets该数量表示用户发布的信息被其他用户转发的信息量2粉丝数量Followers该数量表示微博中所有收听该用户的粉丝数量本文采用信息传播实际影响人次覆盖率P作为用户的传播能力的评测指标该数据是以用户的微博信息在区域内被真实传播的过程中所能影响到的人次的实测结果为依据,将每个微博用户所发出的所有微博的实测影响人数进行迭加获得的每个微博用户的真实传播影响力值得注意的是,如果用户i的某条微博在转发过程中多次传播到用户j,这种情况需要进行合并,只计1人次为了进一步对比和分析算法在真实影响人次这一评价指标下对用户影响力的识别准确程度,通过相关算法获得用户影响力的排名,然后通过对排名的意见领袖用户影响人次覆盖率进行对比,并与真实用户传播影响人次序列进行对比,考察各序列之间的相对关系,结果如图4-4所示图4-43种算法意见领袖累计覆盖率统计通过对图4-4中的数据分析发现,WeiboRank算法意见领袖用户对信息的累计人群覆盖率都高于其他算法,这充分说明该算法通过亲近率引入个体传播意愿和节点互动程度后,能够有效地逼近用户的真实信息传播能力同时我们发现WeiboRank算法和用户的followers两个序列的传播影响人次覆盖率比较相近,这说明如果在不太要求精确性的情况下,用户粉丝数量基本上能够反映用户的传播影响力而用户retweets的序列转发信息量作为用户的传播影响力的评价指标是效果最差的转发量大的用户并不一定意味着其影响力也大从图中可以看出前20%的用户的用户影响力覆盖了80%的用户传播影响人次,符合人们日常认识中的20/80分布规律
4.5微博舆情预警模块
4.
5.1微博舆情预警预警的概念源于对重大自然灾害征兆的研究目前关于天气、自然状况的预警系统已经在社会生活中发挥着显著的作用究其原因,自然现象内外部影响因素之间的因果关系相对确定,而且这些现象都经历了长期的观察测量,有了较好的量化基础,因而可以方便地进行预警预警,究其实质是一种特殊的预测,因为预测是预警的基础和条件,预警是选择实施预案的前提和准备预警体现动态的认知,预案体现静态的防范微博舆情预警,就是发现对微博舆情出现、发展和消亡具有重要影响的因素,并连续不间断地动态监测、度量、及采集它们的信息,根据预警体系内容,运用综合分析技术,对当前微博舆情做出评价分析并预测其发展趋势,及时做出等级预报的活动网络舆情预警等级的设定在综合考虑国际惯例、我国相关机构管理规定及微博舆情发展趋势的前提下,微博舆情的预警等级被划分为轻警情Ⅳ级,非常态、中度警情Ⅲ级,警示级、重警情Ⅱ级,危险级和特重警情I级,极度危险级四个等级,并依次采用蓝色、黄色、橙色和红色来加以表示蓝色级IV级出现舆情微博用户对该舆情关注度低,传播速度慢,舆情影响局限在较小范围内,没有成为当日热点的可能;黄色级Ⅲ级出现舆情微博用户对该舆情关注度较高,传播速度中等,舆情影响局限在一定范围内,有一定可能成为当日热点;橙色级Ⅱ级出现舆情微博用户对该舆情关注度高,传播速度快,影响扩散到了很大范围,舆情有可能成为多日热点;红色级I级出现舆情微博用户对该舆情关注度极高,传播速度非常快,影响扩大到了整个社会,舆情必定成为热点并且持续一段时间
4.
5.2趋势分析模块对曾经成为过热点的微博消息的传播特点进行整理后,得出两种热点传播模型,一种是传统媒体在微博建立的用户的传播方式,一种是微博达人的消息传播模式,图4-5就是两种方式的转发量时间曲线图,例子选择则是媒体模式选择的是南方周末“一名中国公民在波士顿爆炸案中遇难”的消息传播,微博达人模式选择的是“国学大师刘文典说过的一句话”,图4-6和图4-7选择的是传播量时间曲线图,其中南方周末的微博消息在一天的时间内的转发量为997,传播用户量接近500万,其中南方周末本身的粉丝数量就占了近450万,转发率非常低,但是传播范围广,依然是热点,而微博达人模式则不一样,转发量为724,最终传播用户量接近10万,在一定范围内也成为了热点,而它的传播时间图就和起点很高的南方周末的图形很不一样,有着较高的转发率,虽然广度不及南方周末,但也成为过热点话题从两者的传播图形中可以看出,转发率并不能成为热点评估的标准两种模式中,有一共同点则是都曾经出现过短时间内的传播量激增,然后成为热点,根据这一特性设计了趋势分析模块,从最早的意见领袖开始,每出现一个意见领袖,提取这一意见领袖后一小时的意见领袖的传播广度,设定不同的M值(一小时内微博传播量),根据以往数据可以得出,M值在5000以下为蓝色级基本无威胁,在10000到50000为黄色级,需要注意,有很大概率成为热点,而50000以上则肯定成为热点,但持续时间还未能有效的分级,也就是还不能对橙色和红色级进行有效分级,但已能区分热点与否当M值在5000到10000时,成为热点的概率经过统计在50%左右,而如果M值在5000到10000之间出现的次数能达到两次,则成为热点的概率能大大提高,大概能达到80%左右,所以若M值在5000到10000之间时,统计M值的次数,若只出现一次,则为蓝色级,若出现两次或以上,为黄色级而若10000以上也出现两次或以上,则分为橙色级,也就是很可能成为多日热点图4-5转发量时间曲线图图4-6微博达人模式图图4-7媒体模式传播图
4.6趋势分析结果比较利用趋势分析模块对微博消息进行分析,对分析结果与最终消息走势进行对比,结果如图4-8所示,总共测试了15组微博消息,媒体模式10组句子和微博达人模式5组前10组为媒体传播模式的微博消息,其中“江苏盐城政府单位吃喝27万”,“南京一邮局被强拆”,“埃及浮雕刻有‘丁锦昊到此一游’”,“人民日报海外版房地产商哭穷属卖萌装天真”,“郑州暴雨”,这5条微博成为热点,其余没有成为热点,趋势分析模块没有预测出“江苏政府单位吃喝”,“人民日报海外版房地产商哭穷属卖萌装天真”这两条热点;误测了“李克强发表讲话”,“人民日报农村孩子为何不愿跃‘龙门’”为热点,准确率只有60%在微博达人模式中,“营养餐食物变质,营养缩水,问题不断”这条热点没有预测出,但其他热点均成功预测并且没有误报热点,准确率为80%微博题目热点预警结果消息最终走势结果对比李克强将在波茨坦会议旧址发表讲话黄色级蓝色级错误江苏盐城政府单位吃喝27万黄色级蓝色级错误南京一邮局被强拆橙色级橙色级正确李克强无论多忙都要抽时间读书蓝色级蓝色级正确埃及浮雕刻有“丁锦昊到此一游”橙色级红色级正确人民日报农村孩子为何不愿跃“龙门”黄色级蓝色级错误人民日报海外版房地产商哭穷属卖萌装天真蓝色级黄色级错误郑州暴雨黄色级黄色级正确江苏男子坐冤狱8年获补偿金
2.9万元蓝色级蓝色级正确营养餐食物变质,营养缩水,问题不断蓝色级黄色级错误陈佩斯关于网络舆论的评论黄色级黄色级正确王石爱国主义与民族主义黄色级黄色级正确银河SOHO环境监测蓝色级蓝色级正确小学生作文《停车》蓝色级蓝色级正确Esports海涛G1联赛IG负于LGD黄色级黄色级正确图4-8分析结果分析图根据与真实走向的对比,可以发现在微博达人模式中,趋势分析预警成为热点的结果的准确率在80%左右,即使没有成为当日热点也是关注比较靠前的话题而媒体模式中的准确率就比较差强人意了,只有60%左右,根据实验结果发现媒体本身拥有众多粉丝数,所以发表的消息虽然成为热点的可能性非常大,但也总有40%的新闻只是新闻,传播面广而没有成为热点,所以对媒体模式的更准确预警分析有待改进初步设想对媒体认证的意见领袖传播的微博消息加上一个转发率的对比,但尚未从已知数据中发现热点与转发率的明显关系
五、结论与展望
5.1系统不足尽管微博舆情监控技术日趋成熟,但是微博舆情本身的特点及复杂性使得微博舆情信息的处理不能像普通文本信息的处理那样进行微博舆情信息与普通文本的最大区别在于它的扩散性和不可控性,信息内容非常动态由于时间和精力有限,这个系统尚未做到尽善尽美,主要还存在以下几个方面问题
1.信息的实时动态监测对微博信息的实时获取,是趋势分析的关键,由于新浪API的限制,导致对微博消息的抓取有一定限制,在抓取数据时会有一定时间的延迟,在数据挖掘方面有待改进而且从系统功能方面,首先实现的是对指定微博内容的热点趋势分析,而没有实现从实时所有微博信息中发现热点,网络抓取技术这方面有待改进
2.语义分析技术汉语语义的丰富性与复杂性导致中文分词与语义分析的困难,许多适用英文语义分析的算法无法用于中文语义,由于中文语义分析需要建立自然语料库,这方面需要的工作量过大,时间和精力不足,所以在这方面只有一些理论研究,没有实现而如果实现了中文语义分析,充分解析微博句子或词语,对于敏感话题识别和微博舆情趋势分析将会有重要意义
3.趋势分析准确率从
3.8的结果分析中发现,对于媒体传播模式的微博消息的预警准确率基带提高,需要加入文本倾向性分析和转发率等因素来提高分析准确率
5.2未来展望
5.
2.1改进预期由于技术限制,对一些传播特别广的全国范围性的消息热点的监测没能实现,希望能对挖掘算法进行改进,完成对这种热点的特点分析和模型建立通过更多的数据抓取来改进微博意见领袖影响力算法进而完成对趋势分析模块的改进,对趋势分析模块的初步改进设想是将微博传播趋势分析进行分类,微博达人模式适用现行模块,媒体模块则需要重新设定参数,进行修改,同时在趋势分析模块中加入文本倾向性分析,也就是语义分析模块来提高微博分析的准确性,并且实现对热点的热度分级
5.
2.2新增功能文本倾向性分析模块传统的舆情分析和调查主要采用静态的手段,如通过调查问卷,电话和面谈,国内外都有不少专业的调查公司和院所参与调查问题和场景的设计工作而网络舆情分析系统是让计算机去动态的收集数据,对其进行自动分析形成舆情分析结果网络舆情分析系统所涉及的领域众多,不过各个子领域的一些相关技术是可以互相参考和借鉴的如美国专利局编号为4930077的专利提出了通过文本分析来预测舆情的方法加州大学伯克利分校社会科学计算实验室的SDA项目,主要针对网页数据进行自动分析;国内的方正智思是北大方正技术研究院挟多年积累的中文信息处理的技术,研发推出的一个中文智能信息挖掘与知识管理的软件开发包与服务系统这些成型系统一般由数据收集、数据预处理和数据分析等模块组成对现有各种主题分类相关技术进行研究,分类列出了这些技术中对文本倾向性分类仍然适用的方式和方法,并总结了其中面临的主要技术瓶颈;通过列举文本倾向性分类处理对象的特点规律,总结了在构建倾向性分类器时需要着重考虑的问题和因素针对目前倾向性语义资源匮乏的现状,收集和整理了当前主要的基础语义资源,分析了在构建语义资源时需要考虑的因素,提出了用于倾向性分类的语义资源的构建方法并实际构建了一部领域极性词典通过加入语义分析模块,可以极大提高预警的准确率,实现对媒体模式微博消息的预警
5.3结束语随着网络在全球范围内的飞速发展,网络已经逐渐发展成反映社会舆情的主要载体,微博舆情也成了网络舆情的重要组成部分微博舆情管理平台在民意调查,舆情监控和消息获取等方面均有很大价值针对目前舆情管理平台的研究现状,本文重在研究其中数据分析系统的内容,有以下贡献整合中文分词系统与空间向量模型及K-means算法,实现了对微博数据的转化及聚类,给出了微博意见领袖的评估算法及对微博消息的预警等功能初步实现了微博舆情管理平台的功能参考文献
[1]张洋何楚杰段俊文等.微博舆情热点分析系统设计研究[J].信息网络安全20129:60-64
[2]王艺.重大突发公共事件的微博舆情监测与引导初探[J].贵州民族学院学报:哲学社会科学版20115:148-151
[3]杨涛.智能信息处理技术在互联网舆情分析中的应用[D].同济大学2008
[4]张超.文本倾向性分析在舆情监控系统中的应用研究[D][D].北京:北京邮电大学
2008.
[5]唐晓波宋承伟.基于复杂网络的微博舆情分析[J].情报学报20123111:1153-
1162.
[6]王晶朱珂汪斌强.基于信息数据分析的微博研究综述[J].计算机应用20121232:
7.
[7]莫溢刘盛华刘悦等.一种相关话题微博信息的筛选规则学习算法[J].中文信息学报2012265:1-
6.
[8]谭俊武.面向网络舆情分析的文本倾向性分类技术的研究与实现[D][D].国防科学技术大学
2009.
[9]陆浩.网络舆情监测研究与原型实现[D][D].北京:北京邮电大学
2009.
[10]肖宇许炜商召玺.微博用户区域影响力识别算法及分析[J].计算机科学2012399:38-
42.
[11]杨春霞胡丹婷胡森.微博病毒传播模型研究[J].ComputerEngineering
20123815.
[12]李雯静许鑫陈正权.网络舆情指标体系设计与分析[J].情报科学2009277:986-
991.
[13]滕达.基于趋势分析的网络舆情监控系统TANCMS的研究与实现[D].国防科学技术大学
2008.
[14]LarsenBAoneC.Fastandeffectivetextminingusinglinear-timedocumentclustering[C]//ProceedingsofthefifthACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.ACM1999:16-
22.
[15]KumarVTanPNSteinbachM.Clusteranalysis:basicconceptsandalgorithms[J].Introductiontodatamining2006:487-
586.
[16]PageLBrinSMotwaniRetal.ThePageRankcitationranking:bringingordertotheweb[J].
1999.附录Ⅰ翻译原文ClusterAnalysis:BasicConceptsandAlgorithmsClusteranalysisdividesdataintogroupsclustersthataremeaningfulusefulorboth.Ifmeaningfulgroupsarethegoalthentheclustersshouldcapturethenaturalstructureofthedata.Insomecaseshoweverclusteranalysisisonlyausefulstartingpointforotherpurposessuchasdatasummarization.Whetherforunderstandingorutilityclusteranalysishaslongplayedanimportantroleinawidevarietyoffields:psychologyandothersocialsciencesbiologystatisticspatternrecognitioninformationretrievalmachinelearninganddatamining.Therehavebeenmanyapplicationsofclusteranalysistopracticalproblems.Weprovidesomespecificexamplesorganizedbywhetherthepurposeoftheclusteringisunderstandingorutility.ClusteringforUnderstandingClassesorconceptuallymeaningfulgroupsofobjectsthatsharecommoncharacteristicsplayanimportantroleinhowpeopleanalyzeanddescribetheworld.Indeedhumanbeingsareskilledatdividingobjectsintogroupsclusteringandassigningparticularobjectstothesegroupsclassification.Forexampleevenrelativelyyoungchildrencanquicklylabeltheobjectsinaphotographasbuildingsvehiclespeopleanimalsplantsetc.Inthecontextofunderstandingdataclustersarepotentialclassesandclusteranalysisisthestudyoftechniquesforautomaticallyfindingclasses.Thefollowingaresomeexamples:Biology.Biologistshavespentmanyyearscreatingataxonomyhierarchicalclassificationofalllivingthings:kingdomphylumclassorderfamilygenusandspecies.Thusitisperhapsnotsurprisingthatmuchoftheearlyworkinclusteranalysissoughttocreateadisciplineofmathematicaltaxonomythatcouldautomaticallyfindsuchclassificationstructures.Morerecentlybiologistshaveappliedclusteringtoanalyzethelargeamountsofgeneticinformationthatarenowavailable.Forexampleclusteringhasbeenusedtofindgroupsofgenesthathavesimilarfunctions.•InformationRetrieval.TheWorldWideWebconsistsofbillionsofWebpagesandtheresultsofaquerytoasearchenginecanreturnthousandsofpages.Clusteringcanbeusedtogroupthesesearchresultsintoasmallnumberofclusterseachofwhichcapturesaparticularaspectofthequery.Forinstanceaqueryof“movie”mightreturnWebpagesgroupedintocategoriessuchasreviewstrailersstarsandtheaters.Eachcategoryclustercanbebrokenintosubcategoriessub-clustersproducingahierarchicalstructurethatfurtherassistsauser’sexplorationofthequeryresults.•Climate.UnderstandingtheEarth’sclimaterequiresfindingpatternsintheatmosphereandocean.Tothatendclusteranalysishasbeenappliedtofindpatternsintheatmosphericpressureofpolarregionsandareasoftheoceanthathaveasignificantimpactonlandclimate.•PsychologyandMedicine.Anillnessorconditionfrequentlyhasanumberofvariationsandclusteranalysiscanbeusedtoidentifythesedifferentsubcategories.Forexampleclusteringhasbeenusedtoidentifydifferenttypesofdepression.Clusteranalysiscanalsobeusedtodetectpatternsinthespatialortemporaldistributionofadisease.•Business.Businessescollectlargeamountsofinformationoncurrentandpotentialcustomers.Clusteringcanbeusedtosegmentcustomersintoasmallnumberofgroupsforadditionalanalysisandmarketingactivities.ClusteringforUtility Clusteranalysisprovidesanabstractionfromindividualdataobjectstotheclustersinwhichthosedataobjectsreside.Additionallysomeclusteringtechniquescharacterizeeachclusterintermsofaclusterprototype;i.e.adataobjectthatisrepresentativeoftheotherobjectsinthecluster.Theseclusterprototypescanbeusedasthebasisforanumberofdataanalysisordataprocessingtechniques.Thereforeinthecontextofutilityclusteranalysisisthestudyoftechniquesforfindingthemostrepresentativeclusterprototypes.•Summarization.ManydataanalysistechniquessuchasregressionorPCAhaveatimeorspacecomplexityofOm2orhigherwheremisthenumberofobjectsandthusarenotpracticalforlargedatasets.Howeverinsteadofapplyingthealgorithmtotheentiredatasetitcanbeappliedtoareduceddatasetconsistingonlyofclusterprototypes.Dependingonthetypeofanalysisthenumberofprototypesandtheaccuracywithwhichtheprototypesrepresentthedatatheresultscanbecomparabletothosethatwouldhavebeenobtainedifallthedatacouldhavebeenused.•Compression.Clusterprototypescanalsobeusedfordatacompres-sion.Inparticularatableiscreatedthatconsistsoftheprototypesforeachcluster;i.e.eachprototypeisassignedanintegervaluethatisitspositionindexinthetable.Eachobjectisrepresentedbytheindexoftheprototypeassociatedwithitscluster.Thistypeofcompressionisknownasvectorquantizationandisoftenappliedtoimagesoundandvideodatawhere1manyofthedataobjectsarehighlysimilartooneanother2somelossofinformationisacceptableand3asubstantialreductioninthedatasizeisdesired•EffcientlyFindingNearestNeighbors.Findingnearestneighborscanrequirecomputingthepairwisedistancebetweenallpoints.Oftenclustersandtheirclusterprototypescanbefoundmuchmoreeffciently.Ifobjectsarerelativelyclosetotheprototypeoftheirclusterthenwecanusetheprototypestoreducethenumberofdistancecomputationsthatarenecessarytofindthenearestneighborsofanobject.Intuitivelyiftwoclusterprototypesarefarapartthentheobjectsinthecorrespondingclusterscannotbenearestneighborsofeachother.Consequentlytofindanobject’snearestneighborsitisonlynecessarytocomputethedistancetoobjectsinnearbyclusterswherethenearnessoftwoclustersismeasuredbythedistancebetweentheirprototypes.Thischapterprovidesanintroductiontoclusteranalysis.Webeginwithahigh-leveloverviewofclusteringincludingadiscussionofthevariousap-proachestodividingobjectsintosetsofclustersandthedifferenttypesofclusters.Wethendescribethreespecificclusteringtechniquesthatrepresentbroadcategoriesofalgorithmsandillustrateavarietyofconcepts:K-meansagglomerativehierarchicalclusteringandDBSCAN.Thefinalsectionofthischapterisdevotedtoclustervalidity—methodsforevaluatingthegoodnessoftheclustersproducedbyaclusteringalgorithm.MoreadvancedclusteringconceptsandalgorithmswillbediscussedinChapter
9.Wheneverpossiblewediscussthestrengthsandweaknessesofdifferentschemes.Inadditionthebibliographicnotesprovidereferencestorelevantbooksandpapersthatexploreclusteranalysisingreaterdepth.1OverviewBeforediscussingspecificclusteringtechniquesweprovidesomenecessarybackground.Firstwefurtherdefineclusteranalysisillustratingwhyitisdiffcultandexplainingitsrelationshiptoothertechniquesthatgroupdata.Thenweexploretwoimportanttopics:1differentwaystogroupasetofobjectsintoasetofclustersand2typesofclusters.
1.
1.1WhatIsClusterAnalysisClusteranalysisgroupsdataobjectsbasedonlyoninformationfoundinthedatathatdescribestheobjectsandtheirrelationships.Thegoalisthattheobjectswithinagroupbesimilarorrelatedtooneanotheranddifferentfromorunrelatedtotheobjectsinothergroups.Thegreaterthesimilarityorhomogeneitywithinagroupandthegreaterthedifferencebetweengroupsthebetterormoredistincttheclustering.Clusteranalysisisrelatedtoothertechniquesthatareusedtodividedataobjectsintogroups.Forinstanceclusteringcanberegardedasaformofclassificationinthatitcreatesalabelingofobjectswithclassclusterlabels.Howeveritderivestheselabelsonlyfromthedata.IncontrastclassificationnthesenseofChapter4issupervisedclassification;i.e.newunlabeledobjectsareassignedaclasslabelusingamodeldevelopedfromobjectswithknownclasslabels.Forthisreasonclusteranalysisissometimesreferredtoasunsupervisedclassification.Whenthetermclassificationisusedwithoutanyqualificationwithindataminingittypicallyreferstosupervisedclassification.Alsowhilethetermssegmentationandpartitioningaresometimesusedassynonymsforclusteringthesetermsarefrequentlyusedforapproachesoutsidethetraditionalboundsofclusteranalysis.Forexamplethetermpartitioningisoftenusedinconnectionwithtechniquesthatdividegraphsintosubgraphsandthatarenotstronglyconnectedtoclustering.Segmentationoftenreferstothedivisionofdataintogroupsusingsimpletechniques;e.g.animagecanbesplitintosegmentsbasedonlyonpixelintensityandcolororpeoplecanbedividedintogroupsbasedontheirincome.Nonethelesssomeworkingraphpartitioningandinimageandmarketsegmentationisrelatedtoclusteranalysis.
1.
1.2DifferentTypesofClusteringsAnentirecollectionofclustersiscommonlyreferredtoasaclusteringandinthissectionwedistinguishvarioustypesofclusterings:hierarchicalnestedversuspartitionalunnestedexclusiveversusoverlappingversusfuzzyandcompleteversuspartial.HierarchicalversusPartitionalThemostcommonlydiscusseddistinc-tionamongdifferenttypesofclusteringsiswhetherthesetofclustersisnestedorunnestedorinmoretraditionalterminologyhierarchicalorpartitional.Apartitionalclusteringissimplyadivisionofthesetofdataobjectsintonon-overlappingsubsetsclusterssuchthateachdataobjectisinexactlyonesubset.Ifwepermitclusterstohavesubclustersthenweobtainahierarchicalclusteringwhichisasetofnestedclustersthatareorganizedasatree.Eachnodeclusterinthetreeexceptfortheleafnodesistheunionofitschildrensubclustersandtherootofthetreeistheclustercontainingalltheobjects.Oftenbutnotalwaystheleavesofthetreearesingletonclustersofindividualdataobjects.IfweallowclusterstobenestedthenoneinterpretationofFigure
8.1aisthatithastwosubclustersFigure
8.1beachofwhichinturnhasthreesubclustersFigure
8.1d.TheclustersshowninFigures
8.1a–dwhentakeninthatorderalsoformahierarchicalnestedclusteringwithrespectively124and6clustersoneachlevel.Finallynotethatahierarchicalclusteringcanbeviewedasasequenceofpartitionalclusteringsandapartitionalclusteringcanbeobtainedbytakinganymemberofthatsequence;i.e.bycuttingthehierarchicaltreeataparticularlevel.ExclusiveversusOverlappingversusFuzzyTheclusteringsshowninFigure
8.1areallexclusiveastheyassigneachobjecttoasinglecluster.Therearemanysituationsinwhichapointcouldreasonablybeplacedinmorethanoneclusterandthesesituationsarebetteraddressedbynon-exclusiveclustering.Inthemostgeneralsenseanoverlappingornon-exclusiveclusteringisusedtoreflectthefactthatanobjectcansimultaneouslybelongtomorethanonegroupclass.Forinstanceapersonatauniversitycanbebothanenrolledstudentandanemployeeoftheuniversity.Anon-exclusiveclusteringisalsooftenusedwhenforexampleanobjectis“between”twoormoreclustersandcouldreasonablybeassignedtoanyoftheseclusters.ImagineapointhalfwaybetweentwooftheclustersofFigure
8.
1.Ratherthanmakeasomewhatarbitraryassignmentoftheobjecttoasingleclusteritisplacedinallofthe“equallygood”clusters.Inafuzzyclusteringeveryobjectbelongstoeveryclusterwithamembershipweightthatisbetween0absolutelydoesn’tbelongand1absolutelybelongs.Inotherwordsclustersaretreatedasfuzzysets.Mathematicallyafuzzysetisoneinwhichanobjectbelongstoanysetwithaweightthatisbetween0and
1.Infuzzyclusteringweoftenimposetheadditionalconstraintthatthesumoftheweightsforeachobjectmustequal
1.Similarlyprobabilisticclusteringtechniquescomputetheprobabilitywithwhicheachpointbelongstoeachclusterandtheseprobabilitiesmustalsosumto
1.Becausethemembershipweightsorprobabilitiesforanyobjectsumto1afuzzyorprobabilisticclusteringdoesnotaddresstruemulticlasssituationssuchasthecaseofastudentemployeewhereanobjectbelongstomultipleclasses.Insteadtheseapproachesaremostappropriateforavoidingthearbitrarinessofassigninganobjecttoonlyoneclusterwhenitmaybeclosetoseveral.Inpracticeafuzzyorprobabilisticclusteringisoftenconvertedtoanexclusiveclusteringbyassigningeachobjecttotheclusterinwhichitsmembershipweightorprobabilityishighest.CompleteversusPartialAcompleteclusteringassignseveryobjecttoaclusterwhereasapartialclusteringdoesnot.Themotivationforapartialclusteringisthatsomeobjectsinadatasetmaynotbelongtowell-definedgroups.Manytimesobjectsinthedatasetmayrepresentnoiseoutliersor“uninterestingbackground.”Forexamplesomenewspaperstoriesmayshareacommonthemesuchasglobalwarmingwhileotherstoriesaremoregenericorone-of-a-kind.Thustofindtheimportanttopicsinlastmonth’sstorieswemaywanttosearchonlyforclustersofdocumentsthataretightlyrelatedbyacommontheme.Inothercasesacompleteclusteringoftheobjectsisdesired.Forexampleanapplicationthatusesclusteringtoorganizedocumentsforbrowsingneedstoguaranteethatalldocumentscanbebrowsed.
1.
1.3DifferentTypesofClustersClusteringaimstofindusefulgroupsofobjectsclusterswhereusefulnessisdefinedbythegoalsofthedataanalysis.Notsurprisinglythereareseveraldifferentnotionsofaclusterthatproveusefulinpractice.Inordertovisuallyillustratethedifferencesamongthesetypesofclustersweusetwo-dimensionalpointsasshowninFigure
8.2asourdataobjects.Westresshoweverthatthetypesofclustersdescribedhereareequallyvalidforotherkindsofdata.Well-SeparatedAclusterisasetofobjectsinwhicheachobjectiscloserormoresimilartoeveryotherobjectintheclusterthantoanyobjectnotinthecluster.Sometimesathresholdisusedtospecifythatalltheobjectsinaclustermustbesufficientlycloseorsimilartooneanother.Thisidealisticdefinitionofaclusterissatisfiedonlywhenthedatacontainsnaturalclustersthatarequitefarfromeachother.Figure
8.2agivesanexampleofwell-separatedclustersthatconsistsoftwogroupsofpointsinatwo-dimensionalspace.Thedistancebetweenanytwopointsindifferentgroupsislargerthanhedistancebetweenanytwopointswithinagroup.Well-separatedclustersdonotneedtobeglobularbutcanhaveanyshape.Prototype-BasedAclusterisasetofobjectsinwhicheachobjectisclosermoresimilartotheprototypethatdefinestheclusterthantotheprototypeofanyothercluster.Fordatawithcontinuousattributestheprototypeofaclusterisoftenacentroidi.e.theaveragemeanofallthepointsinthecluster.Whenacentroidisnotmeaningfulsuchaswhenthedatahascategoricalattributestheprototypeisoftenamedoidi.e.themostrepresentativepointofacluster.Formanytypesofdatatheprototypecanberegardedasthemostcentralpointandinsuchinstanceswecommonlyrefertoprototype-basedclustersascenter-basedclusters.Notsurprisinglysuchclusterstendtobeglobular.Figure
8.2bshowsanexampleofcenter-basedclusters.Graph-BasedIfthedataisrepresentedasagraphwherethenodesareobjectsandthelinksrepresentconnectionsamongobjectsseeSection
2.
1.2thenaclustercanbedefinedasaconnectedcomponent;i.e.agroupofobjectsthatareconnectedtooneanotherbutthathavenoconnectiontoobjectsoutsidethegroup.Animportantexampleofgraph-basedclustersarecontiguity-basedclusterswheretwoobjectsareconnectedonlyiftheyarewithinaspecifieddistanceofeachother.Thisimpliesthateachobjectinacontiguity-basedclusterisclosertosomeotherobjectintheclusterthantoanypointinadifferentcluster.Figure
8.2cshowsanexampleofsuchclustersfortwo-dimensionalpoints.ThisdefinitionofaclusterisusefulwhenclustersareirregularorintertwinedbutcanhavetroublewhennoiseispresentsinceasillustratedbythetwosphericalclustersofFigure
8.2casmallbridgeofpointscanmergetwodistinctclusters.Othertypesofgraph-basedclustersarealsopossible.OnesuchapproachSection
8.
3.2definesaclusterasaclique;i.e.asetofnodesinagraphthatarecompletelyconnectedtoeachother.Specificallyifweaddconnectionsbetweenobjectsintheorderoftheirdistancefromoneanotheraclusterisformedwhenasetofobjectsformsaclique.Likeprototype-basedclusterssuchclusterstendtobeglobular.Density-BasedAclusterisadenseregionofobjectsthatissurroundedbyaregionoflowdensity.Figure
8.2dshowssomedensity-basedclustersfordatacreatedbyaddingnoisetothedataofFigure
8.2c.ThetwocircularclustersarenotmergedasinFigure
8.2cbecausethebridgebetweenthemfadesintothenoise.LikewisethecurvethatispresentinFigure
8.2calsofadesintothenoiseanddoesnotformaclusterinFigure
8.2d.Adensity-baseddefinitionofaclusterisoftenemployedwhentheclustersareirregularorintertwinedandwhennoiseandoutliersarepresent.Bycontrastacontiguity-baseddefinitionofaclusterwouldnotworkwellforthedataofFigure
8.2dsincethenoisewouldtendtoformbridgesbetweenclusters.Shared-PropertyConceptualClustersMoregenerallywecandefineaclusterasasetofobjectsthatsharesomeproperty.Thisdefinitionencompassesallthepreviousdefinitionsofacluster;e.g.objectsinacenter-basedclustersharethepropertythattheyareallclosesttothesamecentroidormedoid.Howevertheshared-propertyapproachalsoincludesnewtypesofclusters.ConsidertheclustersshowninFigure
8.2e.Atriangularareaclusterisadjacenttoarectangularoneandtherearetwointertwinedcirclesclusters.Inbothcasesaclusteringalgorithmwouldneedaveryspecificconceptofaclustertosuccessfullydetecttheseclusters.Theprocessoffind-ingsuchclustersiscalledconceptualclustering.Howevertoosophisticatedanotionofaclusterwouldtakeusintotheareaofpatternrecognitionandthusweonlyconsidersimplertypesofclustersinthisbook.
2.RoadMapInthischapterweusethefollowingthreesimplebutimportanttechniquestointroducemanyoftheconceptsinvolvedinclusteranalysis.•K-meansThisisaprototype-basedpartitionalclusteringtechniquethatattemptstofindauser-specifiednumberofclustersKwhicharerepresentedbytheircentroids.•AgglomerativeHierarchicalClusteringThisclusteringapproachreferstoacollectionofcloselyrelatedclusteringtechniquesthatproduceahierarchicalclusteringbystartingwitheachpointasasingletonclusterandthenrepeatedlymergingthetwoclosestclustersuntilasingleall-encompassingclusterremains.Someofthesetechniqueshaveanaturalinterpretationintermsofgraph-basedclusteringwhileothershaveaninterpretationintermsofaprototype-basedapproach.•DBSCANThisisadensity-basedclusteringalgorithmthatproducesapartitionalclusteringinwhichthenumberofclustersisautomaticallydeterminedbythealgorithm.Pointsinlow-densityregionsareclassifiedasnoiseandomitted;thusDBSCANdoesnotproduceacompletelustering.附录Ⅱ中文翻译聚类分析基本概念及算法聚类分析将数据分为有意义的,有用的,或两者兼而有之的组(集群)如果目标群体是有意义的,那么集群应该捕获数据的自然结构但是在某些情况下,聚类分析只是一个用于其他目的有用的起点,如数据汇总无论是理解或效用,聚类分析,长久以来在各个领域扮演重要角色心理学等社会科学,生物学,统计,模式识别,信息检索,机器学习和数据采集聚类分析已经被应用到许多实际问题中我们按照聚类的目的是了解或者实用而提供了一些具体的例子聚类理解类对象或概念上是有意义的群体,有着共同的特点,在人们如何分析和说明事物上有重要的作用事实上,人类善于将对象和特定对象分成组(集群)并且将它们分类例如,即使是相对较小的儿童也可以快速识别出照片中的建筑物,车辆,人物,动物,植物等拍摄对象在数据理解方面方面,集群是潜在的类,而聚类分析就是自动将集群分类的技术以下是一些例子•生物学生物学家们花了很多年创造了万物分类(分层分类)领域、语系、类、秩序、科、属和种因此,这也许并不奇怪,在群集分析的早期多是试图建立一个数学学科分类,可以自动找到这样的分类结构最近,生物学家已经将聚类应用到遗传信息处理放面例如,集群已被用于寻找具有类似的功能基因组•信息检索万维网有数十亿的网页,一个搜索引擎的查询结果可以返回数千页集群可以用来将这些搜索结果归为具有相同点的一大类例如,一个“电影”的查询可能会返回到诸如评论,预告片,明星和剧院类别分组的网页每个类别(集群)可以分成子类别(子集),产生一个层次结构,进一步帮助用户在查询结果•气候了解地球的气候需要找到模式分析大气和海洋为此,聚类分析已被应用到寻找到对陆地上气候有重大影响的极地地区和海洋地区的大气压力•心理学和医学疾病或健康有很多的变数,聚类分析可以用来识别这些不同的子类别例如,集群已被用于识别不同类型的抑郁症聚类分析也可用于检测一种疾病空间和时间分布格局•业务企业收集当前和潜在客户大量信息集群可以用来把客户分组以便进行额外的分析和营销活动聚类效用聚类分析提供了一条从单个数据对象抽象到集群中此外,一些集群技术根据一定的规则描述各集群的特点,也就是说,一个数据对象,它是在集群中的其他对象的代表这些集束原型可以用来作为分析的数据或数据处理一些技术基础因此,在公用事业方面,聚类分析是寻找最有代表性的集群原型研究方法•综述许多数据分析技术,如回归或PCA,都为O(M2)或更高(其中m是物体的数量),因此,不适合大数据集然而,虽然算法不适用于整个数据集,它可以应用到减少簇原型组成的数据集依据分析类型、原型的数量、准确度的不同,结果可以媲美那些将已获得的所有数据•压缩集群原型也可用于数据压缩特别是,一个表被创建为每个集群的原型组成,也就是说,每个原型分配一个整数值,是其在表中的位置(索引)每个对象的代表是与其相关的原型群集索引这种压缩类型被称为矢量量化,并经常用于图像,声音和视频数据,其中
(1)数据对象很多都是彼此非常相似,
(2)一些信息丢失是可以接受的,
(3)数据规模大幅减少是理想•有效发现最近邻居最近的邻居发现可以要求计算所有点之间的成对的距离通常集群与集群原型可以更有效的找到如果对象比较接近其集群原型,然后我们可以使用原型,以减少其寻找对象的近邻距离计算数量直观上,如果两个集群原型是相距甚远,那么在相应的簇对象不会是邻居因此,要找到一个对象的近邻,只需要计算距离本章提供了一个聚类分析的介绍我们首先介绍聚类,包括各种的分为簇集对象和不同类型的集群的分类方法然后,我们描述了三个具体的聚类算法技术,代表了两大类,并说明一个概念品种有K-均值,凝聚层次聚类,DBSCAN算法本章最后一节是专门聚类有效性,评估方法由一个聚类算法产生的集群善良更先进的集群概念和算法将在第9章讨论,我们尽可能的讨论了不同方案的长处和弱点此外,书目说明提供参考相关的书籍和论文,更深入的探讨聚类分析1概述在具体讨论什么事聚类技术时,我们提供一些必要的背景首先,我们进一步确定聚类分析,说明和解释其难点以及和其他集群方法的关系然后探索两个重要议题
(1)将不同的事物组合成类,
(2)类型的集群
1.
1.1什么是聚类分析?聚类分析组数据对象仅仅基于MATLAB环境中,描述对象和它们之间的关系我们的目标是,找出在一组类似(或相关)彼此和(或无关的)在其他各组对象的不同越大组内和更大的群体之间的差异,更好或更明显的聚类相似性(相关性)另外,在分割和分配的条款是作为同义词集群,这些条款是经常使用的聚类分析之外的传统界限的方法例如,分为子图和并不强烈连接到群集的连接通常指的是分割成组的数据用简单的技术分工,例如,图像可分为基于像素的强度和颜色只分部分裂,人群可可依据收入进行分类
1.
1.2不同类型的群集合整个集群的一个集合通常称为聚类,并在本节中,我们区分不同类型的群集合层次(嵌套)与分割式(非嵌套),独有的与重叠与模糊划分的层次与最经常讨论的距离之间的群集合是不同类型的,簇集嵌套或非嵌套,或在更传统的术语,分层或划分的A集群是一个简单的数据对象设置成不重叠的子集(集群),使得每个数据对象的完全是分工的如果我们允许集群有子群,然后我们得到了一个层次聚类,这是该组织为一树嵌套簇集树中的每个节点(群)(除叶节点)是它的子联盟,树的根是群集包含所有的.但并非总是如此,树上的叶子是对象的个人资料单身集群如果我们允许集群嵌套,然后图
8.1解释
(一)是,它有两个子群(图
8.1(b)项),其中每个有三个子群(图
8.1(d)段)在图
8.1所示的集群(A至D),当在这规律,也形成了分层(嵌套)分别一,二,四,六各层次集群最后,注意分层聚类可作为划分的群集合的序列和划分聚类效果,可采取任何成员的序列叠与模糊控制在图
8.1所示的群集合都是排他性的,因为他们给每个对象都是一个单独的群其中一点可以合理地在多个群集设了很多情况在最一般的意义上,重叠或不重叠是用来反映一个事实,即一个对象可以同时属于多个组(类)例如,在一所大学的人既可以是已登记的学生也可以是大学雇员除非非重叠群也使用,一个对象是“与”两个或多个群集,可以合理地分配到其中任何群.假想图
8.1之间的集群有点半,不是使一个对象有点武断分配到一个集群,它是摆在了“一样好”集群所有在一个模糊聚类,每个对象属于每一个成员的体重是介于0(绝对不属于)和1群集换句话说,集群被视为模糊集(数学,模糊集在其中任何一个对象属于0和1之间的权重)模糊聚类,我们经常施加额外的约束,即对每个对象的权重之和必须等于1)同样,概率聚类技术的概率计算每个点属于每个集群,还必须总结这些概率为1因为成员权或任何对象之和为1,概率聚类没有解决真正的多用户情况下,如一个学生的雇员,其中一个对象属于多个类的情况相反,这些方法是最合适的避免在分配一个对象只有一个群集的随意性可能接近时数或概率的模糊聚类经常转换为非重叠群,每个对象分配到集群中,其成员的重量或概率最高整的聚类与偏每个对象分配到集群,而不是一个局部聚类对于一个局部聚类的动机是,在一个数据集的某些对象可能不属于明确界定的群体很多时候,在数据集对象可能代表噪音,孤立点,或“无趣的背景”例如,一些报纸报道,可能都有一个共同的主题,如全球变暖一类因此,为了找到在上个月的故事中的重要议题,我们可能要搜索的文件是由一个共同的主题紧密相关的集群在其他情况下,需求完整的对象聚类.例如,一个应用程序,使用聚类组织文档进行检索需要保证所有的文件可以浏览
1.
1.3簇的不同类型聚类的目的是找到对象(组),其中的用处是通过数据分析确定的目标有用的群体毫不奇怪,有几种不同的群集的概念在实践中证明是有益的为了直观地说明这些类型的集群中的差异,我们使用二维点,如图
8.2所示,由于我们的数据对象,我们强调,但是,这里描述的集群类型同样为其他类型的数据无效分隔集群是一组对象,其中每个对象是密切(或更多类似)集群中的每个对象比其他任何对象群集有时,一个阈值用来指定集群中的所有对象都必须充分接近(或类似)彼此这种理想的集群技术信息研究所的定义,只有当数据满足包含从很远的自然相互集群图
8.2(a)给出了一个良好的分离集群的两个例子,在一个两维空间点群组成任意两点之间的距离是不同的群体大于他任意两点间的距离保持在一组井分隔群集不须球状,但可以有任意形状基于原型的集群是一组对象,其中每个对象是密切(更多类似)的原型定义,而不是任何其他群集原型群集对于连续属性的数据,集群的原型往往是重心,即所有在集群点的平均值(平均)当质心是没有意义的,例如,当数据类别属性,原型往往是最有代表性的集群对于许多类型的数据,该原型可以被看作是最核心的一点,在这种情况下,我们通常所说的中心的集群原型为基础的集群毫不奇怪,这种集群往往是球状图
8.2(b)显示了一个中心为基础的集群的例子基于图的数据是,如果作为一个图,其中的节点对象和对象之间的联系表示连接(参见第
2.
1.2节),然后一组可以作为一个连接组件中定义的代表,也就是说,对象的组彼此相连,但不会对本集团以外对象的连接一种基于图的集群重要的例子是连续性的群集,其中只有两个对象,如果它们连接在一个相互指定距离之内这意味着,每一个连续性的群集对象是接近到群集中的其他一些对象比任何一个不同的聚点图
8.2(c)给出了两维点,如簇的例子这群集的定义是有用的当集群不规则或交织在一起,但可以有麻烦时,噪音存在,因为由两个图
8.2(c)项的积分可以合并两个不同的簇群小桥球形说明的图形为基础的集群其他类型也是可能的其中一种办法(第
8.
3.2)定义为一个集团群集,也就是说,一组节点在一个完全相互连接图特别是,如果我们加入了对象之间的距离为彼此连接,形成一个群集,当一个对象的形式设置一个集团像原型为基础的集群,这种集群往往是球状基于密度的群集是一组环绕低密度区域对象的密集区图
8.2(d)显示一定密度的数据为基础,加入噪声的数据图
8.2
(三)创建群集集群的两个圆形不合并,如图
8.2(c)项,因为它们之间的桥梁进入噪音消失同样地,存在的曲线图
8.2(c)又消失的噪音之中,并不构成群集在图
8.2(d)项集群的一个基于密度的定义时,往往采用集群不规则或交织,在噪声和离群点都存在相比之下,集群的一个连续性的定义都不能很好的工作数据,图
8.2(d)由于噪声往往会形成集群之间的桥梁共享属性(概念集群)更普遍,我们可以定义为一个共享对象的一些属性设置群集这个定义包括所有以前的群集的定义,在一个中心的群集共享,例如,对象的属性,它们都是相同的质心然而,共享属性的方法还包括集群研究的新类型考虑图
8.2所示的群集
(五)一个三角区(集群)毗邻长方形之一,有两个交织在一起的圆圈(集群)在这两种情况下,聚类算法将需要集群的一个非常具体的概念,成功地检测到这些集群对查找安泰这种集群的过程称为概念聚类然而,过于复杂的集群的一个概念,会考虑在模式识别领域的我们,所以我们只考虑在这本书集群简单的类型
2.路线图在这一章中,我们使用以下三个简单的,但聚类分析所涉及的许多重要概念•K-means算法这是一个以原型为基础,试图找到一个均值的聚类技术•凝聚层次聚类此分群方式是指一组密切相关的聚类技术,开始时各自作为一个单身聚点,然后反复,直到一个单一的合并两个最接近的集群的层次聚类集合,全方位的集群仍然存在这些方法在一些有基于图形的聚类方面自然解释,而其他人在一个原型为基础的方法方面作出解释•DBSCAN这是一个基于密度的聚类算法,划分聚类,在其中的簇数量为自动,由算法确定但低密度区的点容易被忽略,因此DBSCAN不是一种完整的聚类方法PAGE1。