最新推荐系统聚类的方法word版本 11页.docx
《最新推荐系统聚类的方法word版本 11页.docx》由会员分享,可在线阅读,更多相关《最新推荐系统聚类的方法word版本 11页.docx(9页珍藏版)》请在冰点文库上搜索。
最新推荐系统聚类的方法word版本11页
本文部分内容来自网络整理,本司不为其真实性负责,如有异议或侵权请及时联系,本司将立即删除!
==本文为word格式,下载后可方便编辑和修改!
==
系统聚类的方法
篇一:
聚类分析方法小结
聚类分析方法小结
简单点说:
分类是将一片文章或文本自动识别出来,按照先验的类别进行匹配,确定。
聚类就是将一组的文章或文本信息进行相似性的比较,将比较相似的文章或文本信息归为同一组的技术。
分类和聚类都是将相似对象归类的过程。
区别是,分类是事先定义好类别,类别数不变。
分类器需要由人工标注的分类训练语料训练得到,属于有指导学习范畴。
聚类则没有事先预定的类别,类别数不确定。
聚类不需要人工标注和预先训练分类器,类别在聚类过程中自动生成。
分类适合类别或分类体系已经确定的场合,比如按照国图分类法分类图书;聚类则适合不存在分类体系、类别数不确定的场合,一般作为某些应用的前端,比如多文档文摘、搜索引擎结果后聚类(元搜索)等。
分类(classification)是找出描述并区分数据类或概念的模型(或函数),以便能够使用模型预测类标记未知的对象类。
分类技术在数据挖掘中是一项重要任务,目前商业上应用最多。
分类的目的是学会一个分类函数或分类模型(也常常称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个类中。
要构造分类器,需要有一个训练样本数据集作为输入。
训练集由一组数据库记录或元组构成,每个元组是一个由有关字段(又称属性或特征)值组成的特征向量,此外,训练样本还有一个类别标记。
一个具体样本的形式可表示为:
(v1,v2,...,vn;c);其中vi表示字段值,c表示类别。
分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。
不同的分类器有不同的特点。
有三种分类器评价或比较尺度:
1)预测准确度;
2)计算复杂度;3)模型描述的简洁度。
预测准确度是用得最多的一种比较尺度,特别是对于预测型分类任务。
计算复杂度依赖于具体的实现细节和硬件环境,在数据挖掘中,由于操作对象是巨量的数据,因此空间和时间的复杂度问题将是非常重要的一个环节。
对于描述型的分类任务,模型描述越简洁越受欢迎。
另外要注意的是,分类的效果一般和数据的特点有关,有的数据噪声大,有的有空缺值,有的分布稀疏,有的字段或属性间相关性强,有的属性是离散的而有的是连续值或混合式的。
目前普遍认为不存在某种方法能适合于各种特点的数据
聚类(clustering)是指根据“物以类聚”原理,将本身没有类别的样本聚集成不同的组,这样的一组数据对象的集合叫做簇,并且对每一个这样的簇进行描述的过程。
它的目的是使得属于同一个簇的样本之间应该彼此相似,而不同簇的样本应该足够不相似。
与分类规则不同,进行聚类前并不知道将要划分成几个组和什么样的组,也不知道根据哪些空间区分规则来定义组。
其目的旨在发现空间实体的属性间的函数关系,挖掘的知识用以属性名为变量的数学方程来表示。
聚类技术正在蓬勃发展,涉及范围包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等领域,聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。
常见的聚类算法包括:
K-均值聚类算法、K-中心点聚类算法、CLARANS、BIRCH、CLIQUE、DBSCAN等。
1.含义
根据事物本身的特性研究个体分类的方法,是研究事物分类的基本方法。
其是为了某种目的做的工作,并非真实存在所分的类。
2.原则
同一类中的个体相似性大,不同类中的个体差异很大。
3.分类
(1)按聚类对象分:
样品聚类:
对观测量聚类,对反映被观测对象特征的各个变量值进行分类。
目的是判断研究对象的属类。
变量聚类:
根据所研究的问题选择反映事物某些特点的部分变量来研究事物的某方面。
目的是找出彼此独立的有代表性的变量,以便在用少量有代表性变量代替众多变量时,损失信息很少。
(2)按聚类过程分:
分解方法:
首先把所有个体认为一大类,然后根据距离最近或性质相似逐层分解,直到每个个体自成小类为止。
凝聚方法:
首先把每个个体认为一小类,然后根据距离最近或性质相似逐步合并,直到所有个体一个大类为止。
4.3.2内容过程
1.数据准备
这里运用聚类分析方法对我国部分东西部地区的经济发展进行综合评价。
2.方法选择
按分析Analyze—聚类C(来自:
WwW.:
系统聚类的方法)lassify—分层聚类HierachicalClassify的顺序展开如图4.10所示对话框。
从左侧原始变量备选框中指定参与分析变量送入右侧变
量Variable(s)框中。
在聚类栏Classify选择聚类类型—观测量聚类Cases或变量聚类Variable,若做观测量聚类,还需指定一个标识变量送到样本标签框LabelCasesby中。
在输出显示栏系统默认选择统计量和图形。
单击方法选择Method功能按钮,展开对话框。
(1)聚类方法ClusterMethod:
定义、计算两项之间距离或相似性的方法。
组间连接:
合并两类后使所有对应两项之间的平均距离最小。
组内连接:
合并后使类中所有项之间的平均距离(平方)最小。
最近邻法:
用两类之间最近点间的距离代表两类间的距离。
最远邻法:
用两类之间最远点间的距离代表两类间的距离。
重心聚类:
以计算所有各项均值间距离的方法计算两类间距离。
中位数法:
以各类中的中位数为类中心。
最小方差:
以类间方差最小为聚类原则。
(2)测度方法Measure:
测度距离或相似性的算法。
方法一般与定义方法对应一致。
聚类方法不同,测度算法相应不同,聚类结果会有区别。
若方法与算法不一致,则输出警告提示,结果不能成立。
测度方法有计算连续变量的距离、离散变量的不相似性、二值变量的距离或不相似性。
连续变量距离计算方法有:
欧氏距离:
(∑(Xi-Yi)2)1/2,即两项间的差是每个变量值差的平方和再平方根,目的是计算其间的整体距离即不相似性。
距离平方:
∑(Xi-Yi)2,目的是减少误差。
相似测度:
∑(XiYi)2/((∑Xi2)(∑Yi2)),即两项间的相似性是向量间的余弦,值域-1—1,用0值表示相互垂直。
皮氏相关:
∑(ZXiZYi)2/(n-1),即两项间的相似性是向量间的线性相关性,范围-1—1,0值表明非线性相关。
切氏距离:
Max|Xi-Yi|,即两项间的距离是变量间最大差值的绝对值。
布氏距离:
∑|Xi-Yi|,两项间的距离是每个变量值之差的绝对值总和。
明氏距离:
(∑|Xi-Yi|p)1/p。
自定距离:
(∑|Xi-Yi|p)1/r。
若r=p,则为明氏距离。
(3)数据转换TransformValues:
为消除量纲不同的影响。
若参与分析的变量量纲一致,则不需标准化转换。
但不同的标准化会导致不同的聚类结果,因此选择方法注意与变量分布相对应。
标准化到Z分数:
变量均值为0、标准差为1,(每个值-均值)/标准差。
标准化到某范围:
范围-1—1,每个值/范围。
标准化到某一值:
最大值为1,每个值/最大值。
标准化到某范围:
范围0—1,(每个值-最小值)/范围。
标准化到某一值:
均值的一个范围,每个值/均值。
标准化到标准差:
单位标准差,每个值/标准差。
(4)测度转换TransformMeasure:
已计算相似性或不相似性,则不需转换。
距离取绝对值:
距离顺序颠倒:
相似性值与不相似性值互变。
使距离标准化:
(距离-最小值)/范围。
3.输出选择
(1)统计量
在主对话框单击Statistics出现对话框。
篇二:
聚类分析原理及步骤
聚类分析原理及步骤——将未知数据按相似程度分类到不同的类或簇的过程1》传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。
采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中,如SPSS、SAS等。
典型应用
1》动植物分类和对基因进行分类2》在网上进行文档归类来修复信息
3》帮助电子商务的用户了解自己的客户,向客户提供更合适的服务
主要步骤
1》数据预处理——选择数量,类型和特征的标度((依据特征选择和抽取)特征选择选择重要的特征,特征抽取把输入的特征转化为一个新的显著特征,它们经常被用来获取一个合适的特征集来为避免“维数灾”进行聚类)和将孤立点移出数据(孤立点是不依附于一般数据行为或模型的数据)2》为衡量数据点间的相似度定义一个距离函数——既然相类似性是定义一个类的基础,那么不同数据之间在同一个特征空间相似度的衡量对于聚类步骤是很重要的,由于特征类型和特征标度的多样性,距离度量必须谨慎,它经常依赖于应用,例如,通常通过定义在特征空间的距离度量来评估不同对象的相异性,很多距离度都应用在一些不同的领域一个简单的距离度量,如Euclidean距离,经常被用作反映不同数据间的相异性,一些有关相
似性的度量,例如PMC和SMC,能够被用来特征化不同数据的概
念相似性,在图像聚类上,子图图像的误差更正能够被用来衡量两
个图形的相似性
3》聚类或分组——将数据对象分到不同的类中【划分方法(划分方法一般从初始划分和最优化一个聚类标准开始,Crisp
Clustering和FuzzyClusterin是划分方法的两个主要技术,CrispClustering,它的每一个数据都属于单独的类;FuzzyClustering,它的
每个数据可能在任何一个类中)和层次方法(基于某个标准产生一
个嵌套的划分系列,它可以度量不同类之间的相似性或一个类的可分
离性用来合并和分裂类)是聚类分析的两个主要方法,另外还有基于
密度的聚类,基于模型的聚类,基于网格的聚类】
4》评估输出——评估聚类结果的质量(它是通过一个类有效索引来
评价,,一般来说,几何性质,包括类间的分离和类内部的耦合,一般
都用来评价聚类结果的质量,类有效索引在决定类的数目时经常扮演
了一个重要角色,类有效索引的最佳值被期望从真实的类数目中获取,
一个通常的决定类数目的方法是选择一个特定的类有效索引的最佳
值,这个索引能否真实的得出类的数目是判断该索引是否有效的标准,
很多已经存在的标准对于相互分离的类数据集合都能得出很好的结
果,但是对于复杂的数据集,却通常行不通,例如,对于交叠类的集
合。
)
聚类分析的主要计算方法原理及步骤
划分法
1》将数据集分割成K个组(每个组至少包
含一个数据且每一个数据纪录属于且
仅属于一个分组),每个组成为一类
2》通过反复迭代的方法改变分组,使得每
一次改进之后的分组方案都较前一次
好(标准就是:
同一分组中的记录越近
越好,而不同分组中的纪录越远越好,
使用这个基本思想的算法有:
K-MEANS算法、K-MEDOIDS算法、
CLARANS算法)
层次法
1》“自底向上”方案——将每个数据单独作为一组,通过反复迭代的方法,把那些相互邻近的组合并成一个组,直到所有的记录组成一个分组或者某个条件满足为止,代表算法有:
BIRCH算法、CURE算法、CHAMELEON算法等2》“自顶向下”方案
主要算法原理及步骤
K-MEANS算法
k-means算法接受输入量k;然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足:
同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。
聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。
k-means算法的工作过程说明如下:
1》从n个数据对象任意选择k个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;
2》计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始
收敛为止。
一般都采用均方差作为标准测度函数.
k个聚类具有以下特点:
各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。
K-MEDOIDS算法
K-MEANS有其缺点:
产生类的大小相差不会很大,对于脏数据很敏感。
改进的算法:
k—medoids方法:
选取一个对象叫做mediod来代替上面的中心的作用,这样的一个medoid就标识了这个类。
步骤:
(1)、任意选取K个对象作为medoids(O1,O2,…Oi…Ok)。
以下是循环的:
(2)、将余下的对象分到各个类中去(根据与medoid最相近的原则);(3)、对于每个类(Oi)中,顺序选取一个Or,计算用Or代替Oi后的消耗—E(Or)。
选择E最小的那个Or来代替Oi。
这样K个medoids就改变了,
下面就再转到2。
(4)、这样循环直到K个medoids固定下来。
这
种算法对于脏数据和异常数据不敏感,但计算量显然要比K均值要大,一般只适合小数据量
Clara算法
K-medoids算法不适合于大数据量的计算,Clara算法的思想就是用实际数据的抽样来代替整个数据,然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids。
Clara算法从实际数据中抽取多个采样,在每个采样上都用K-medoids算法得到相应的(O1,O2…Oi…Ok),然后在这当中选取E最小的一个作为最终的结果。
Clarans算法
Clara算法的效率取决于采样的大小,一般不太可能得到最佳的结果
在Clara算法的基础上,又提出了Clarans的算法,与Clara算法不同的是:
在Clara算法寻找最佳的medoids的过程中,采样都是不变的。
而Clarans算法在每一次循环的过程中所采用的采样都是不一样的。
与上次课所讲的寻找最佳medoids的过程不同的是,必须人为地来限定循环的次数
篇三:
基于聚类的推荐算法
曲靖师范学院
本科生毕业论文
论文题目:
一种基于项目聚类的推荐算法
作者、学号:
何芸娜201X112142
学院、年级:
数学与信息科学学院201X级
学科、专业:
数学信息与计算科学
指导教师:
刘永财
完成日期:
201X年5月27日
曲靖师范学院教务处
一种基于项目聚类的推荐算法
摘要
推荐系统是帮助用户评估他没有发现的内容,从而克服信息超载的一种有效工具.对于推荐系统的研究,既有重大的社会意义,又有重大的经济价值.推荐系统早在上世纪九十年代就已经被提出并进行了广泛的研究.
在现代信息爆炸的年代,用户在网上留下的评分数据成了一个很大的数据库.本文介绍了一种基于项目聚类的协同过滤推荐算法及比较简单实用的聚类分析算法—k-means算法,利用该推荐算法合理开发并利用这些资源.主要通过k-means算法求出根据项目相似性度量,从而对项目进行聚类.
文中介绍的推荐算法,其核心目的在于解决数据稀疏性优势的基础上,使用聚类分析技术对原始信息进行处理,通过简单实用的k-means聚类算法将用户的行为模型转化为兴趣模型从而实现了更精准的推荐.
关键词:
推荐系统;聚类分析;相似性度量;k-means算法
Basedontheprojectclusteringrecommendationalgorithm
Abstract:
Recommendationsystemistohelpusersassessthecontenthedidnotfoundaneffectivetooltoovercometheinformationoverload.Recommendationsystemforthestudyofbothmajorsocialsignificance,butalsoofgreateconomicvalue.Recommendationsystemearlyinthelastcenturyninetyyearshasbeenproposedandcarriedoutextensiveresearch.
Inthemoderneraofinformationexplosion,leavingthescoreintheonlineuserdataintoalargedatabase.Thispaperdescribesaproject-basedclusteringcollaborativefilteringalgorithmisrelativelysimpleandpracticalclusteringalgorithm-k-meansalgorithm,usingtherecommendedalgorithmdevelopmentandrationaluseoftheseresources.mainlydeterminedbyk-meansalgorithmbasedonprojectsimilaritymeasure,sotheprojectcluster.
Thisarticledescribestherecommendationalgorithm,itscorepurposeistosolvethedatasparsity-basedadvantages,theuseofclusteranalysistechniquestoprocesstheoriginalinformationthroughsimpleandpracticalk-meansclusteringalgorithmtomodelthebehavioroftheuserinterestmodelthustransformedintotoachieveamoreaccuraterecommendations.
Keyword:
recommendationsystemclusteringanalysis
similaritymeasurementk-meansarithmetic
目录
1引言.........................................................1
2聚类分析.....................................................3
3基于项目聚类的推荐算法.......................................5
3.1ISODATA算法...............................................5
3.2k-means聚类算法...........................................6
3.3k-means聚类算法的算法步骤.................................7
3.4k-means算法和ISODATA算法.................................8
3.5简单推荐过程的实现.........................................9
4k-means聚类算法的实现......................................10
4.1k-means聚类算法模型建立..................................10
4.2k-means聚类算法的性能分析................................11
4.3MovieLens电影评分数据集..................................12
4.4k-means聚类算法实验过程及结果............................13
总结.........................................................16
参考文献......................................................17
致谢.........................................................18
附录..........................................................19
1引言
文献[1]“互联网信息环境中信息超载问题研究”中介绍了计算机及互联网的飞速发展而使得人类从信息贫乏时代进入了信息超载时代.在这个信息爆炸[1]的时代,无论对于作为信息消费者的用户和信息生产者的媒体与商家都受到了海量信息带来的新挑战.
一方面,普通用户很难从海量信息中发现自己感兴趣的部分;另一方面,对于媒体和商家来说,海量的信息成为网络中的“暗信息”无法产生价值,而这些“暗信息”中或许存在着大量用户感兴趣的项目[2],如何利用这些信息提供给用户良好的服务来增加用户粘性也是一个很重要的事情.文献[2]中介绍了一种基于项目聚类的推荐算法,利用k-means算法挖掘这些海量的信息.从中开发这些海量信息的隐藏价值.
作为当前解决信息超载问题的最有效工具之一,搜索引擎以一定的策略在互联网中搜集与发现信息,同时完成对信息的提取、组织和理解等处理,从而为用户提供检索服务,起到信息导航的目的[3].搜索引擎提供的信息导航服务目前已经成为互联网上非常重要的网络服务,搜索引擎也已经成为计算机工业界和学术界广泛研究的对象.但是,随着互联网技术与需求的不断发展,搜索引擎技术不可避免的显露出一些不足之处:
首先,现有的搜索引擎工具只能为用户找到已知的信息或已知关键字的信息,而不能帮助用户找到其未知但有意义或有兴趣的信息.有些潜在的携带用户偏好等信息如果无法用文字准确描述则无法通过搜索引擎得到,例如对电影的不同偏好或者对服装首饰搭配的审美特点都不容易使用明确的文字进行描述.另外,现有搜索引擎呈献给用户的是“千人一面”的分类体系和网页内容,信息结果的排列方式也是仅仅按照关键字的相关度进行排序,这往往无法满足用户的个性化需求.
文献[3]“搜索引擎及网络信息资源的分类组织”一文中介绍了几种常用的搜索引擎,从搜索引擎算法的原理到实现介绍了搜索引擎的功能,分析了搜索引擎的优点和带来的便捷之处,同时也分析了搜索功能的局限性和不足之处.
个性化推荐技术的出现从一定程度上解决了现有搜索引擎所面临的两个问题.推荐系统帮助用户评估他从未看过的产品,这些产品既包括书、电影、CD、网
1