《Mahout算法解析与案例实战》一一3.3 Mean Shift算法

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
简介:

本节书摘来自华章计算机《Mahout算法解析与案例实战》一书中的第3章,第3.3节,作者:樊 哲,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.3 Mean Shift算法

3.3.1 Mean Shift算法简介
Mean Shift算法,中文可以翻译为均值偏移或均值漂移,最早是由Fukunaga在1975年发表的《The Estimation of the Gradient of a Density Function, with Application in Pattern Recognition》中被提出来,这是一篇关于概率密度梯度函数的论文。Mean Shift最开始的意思是偏移的均值向量,它是一种无参的估计方法,沿着概率梯度上升方向寻找分布的峰值。通俗地讲,它是一个这样的迭代过程:先计算出当前点的偏移均值,移动该点到其偏移均值,然后以此为新的起点,继续移动,直到满足一定的条件结束。
Mean Shift算法的特性之一是该算法不需要提供一个要聚类的数目(K-Means聚类算法是需要的),而且该算法还能根据数据的特征发现任意形状的聚类簇(这点和Canopy算法不同,Canopy算法发现的是圆形簇)。该算法首先为每个数据创建一个固定半径的窗口,循环遍历每个窗口,通过一个本地的密度函数计算一个均值漂移向量(这个向量是指向最大增长速度的方向)。然后每个窗口根据计算出来的均值漂移向量移动到一个新的位置,并且开始新的循环。循环退出的条件是当通过本地密度函数计算出来的向量变到很小的时候,满足一个阈值就退出。
3.3.2 Mahout中Mean Shift算法实现原理
在Mahout中,Mean Shift算法是通过修改Canopy聚类算法得到的。该算法在Mahout 中的实现思路如下。
在讲解算法前,首先需要了解下面的参数设定:该算法使用距离阈值T1作为每个窗口的固定半径,使用距离阈值T2来决定两个canopy什么时候合并为一个(即当两个canopy的距离小于T2的时候就把它们合并)。每个canopy包含一个或者多个被限制在某个范围的点(这些点使用整数id来表示)。下面是算法的具体步骤。
1)算法在初始时为每个输入样本数据点创建一个canopy。
2)针对每一个canopy,把输入与当前canopy的距离小于距离阈值T1的归为当前canopy(比如,一共有三条记录,如果它们彼此的距离都小于T1,那么以第一条记录为canopy的点有两个,分别是记录2和记录3;以第二条记录为canopy的点也有两个,分别是记录1和记录3;以第三条记录为canopy的点也有两个,分别是记录1和记录2)。每一个canopy计算它的均值漂移向量,计算方法:使用每个canopy包含的点的全部维度相加除以包含点的数目就得到了一个新的canopy中心向量,即均值漂移向量。这个中心向量的权重通过它包含的点的数目来表示。
3)针对步骤2中新的canopy计算它们之间的距离,当距离小于阈值T2时就把它们归为一个canopy,同时相应的属性也叠加。
4)算法结束的条件:当每一个canopy的前后两次的差值都满足小于一个给定的阈值delta时,该算法结束。
5)算法结束后,剩下的canopy的数目就是聚类的数目。
该算法的流程图如图3?14所示。image

这里的mapper和reducer的操作其实是一样的,而driver主要是进行循环的触发和退出循环条件的判断,在图3?15中可以详细地看出该算法的Mapper、Reducer和Driver的主要工作。
mapper主要的工作是根据T1和T2阈值把canopy进行归类、合并,然后使用新的中心向量来更新每个canopy,输出到reducer;reducer根据map的输出进行与map同样的操作,然后返回到driver;driver根据reducer的结果进行判断,看阈值是否小于delta(当然循环的次数也是一个条件),然后根据该结果确定退出或继续循环。
image

图3?15 Mean Shift算法mapper、reducer和driver工作流
3.3.3 Mahout的Mean Shift算法实战
1.输入数据
下载数据,这里使用的数据同样是第2章中的控制图数据,包含600个样本数据,每个样本数据有60个属性列,这些数据可以分为6个类。上传到HDFS的文件如图3?4所示,这里上传到/user/test/input/synthetic_control.data中。
2.参数意义
Mean Shift算法在Mahout中的使用方式如下:

usage: meanshift [Generic Options] [Job-Specific Options]

其中[]包含的两个参数是可选的。
Generic Options参数选项和Canopy算法一样,这里不再介绍,可直接参考相关内容。
Job-Specific Options参数选项包含如下:
--input (-i ) input:任务的输入文件选项,必选。
--output (-o) output:任务的输出文件的选项,必选。
-- convergenceDelta (-cd) convergenceDelta:判断退出循环的阈值,默认是0.5,可选。
-- maxIter (-x) maxIter:最大的循环次数,必选。
--overwrite (-ow):如果出现,则对输出路径进行重写,可选。
--inputIsCanopies (-ic) inputIsCanopies:如果出现,则说明输入已经被转换为Mean-ShiftCanopies了,可选。
--distanceMeasure (-dm) distanceMeasure:距离计算的类名称,默认为Square-Euclidean,即欧氏距离平方,可选。
--kernelProfile (-kp) kernelProfile:内部计算方法类,默认是TriangularKernelProfile。
--t1 (-t1) t1:T1阈值,可选。
--t2 (-t2) t2:T2阈值,可选。
--clustering (-cl):如果出现,则对数据进行分类,可选。
--method (-xm) method:选择使用的计算方式,单机或集群,默认为集群,可选。
--outlierThreshold (-outlierThreshold) outlierThreshold:异常值阈值,可选。
--help (-h):打印此参数帮助信息,可选。
--tempDir tempDir:临时文件所存放的地方,可选。
--startPhase startPhase:开始要运行算法的阶段,可选。
--endPhase endPhase:最后要运行算法的阶段,可选。
关于inputIsCanopies参数的设置:当输入的样本数据已经转换为MeanShiftCanopies时,就不需要设置参数,否则就需要设置,然后就是在程序中执行一个InputDriver任务,这个任务就是把输入转换为MeanShiftCanopies的,且要求输入中的维度是按照空格来间隔的(一个或多个空格)。
3.运行
通过前面两个小节的内容,相信读者已经知道了如何上传数据,这里不再赘述。在正式运行该算法的调用命令之前,首先要对输入数据进行转换。进入Hadoop安装目录,执行如下命令:

./hadoop jar ../../mahout-d-0.7/mahout-examples-0.7-job.jar org.apache.mahout.clustering.conversion.meanshift.InputDriver -i /user/test/input/synthetic_control.data -o /user/test/input/real_input

上面的命令运行完成后,直接运行下面的命令:

./mahout meanshift -i /user/test/input/real_input/ -/user/test/output -ic true -cd 0.5 -x 10 -dm org.apache.mahout.common.distance.EuclideanDistanceMeasure -kp org.apache.mahout.common.kernel.TriangularKernelProfile -t1 47.6 -t2 1 -cl
由

于输入已经进行了转换,因此上面的命令设置-ic参数为true。
4.结果分析
首先查看转换后的输入数据,可以在HDFS文件系统上查看/user/test/input/real_input/part-m-00000文件,如图3?16所示。
image

图3?16 Mean Shift算法输入转换数据
由图3?16可以看出,输入已经转换为序列文件,同时输入数据的value已经被转换为ClusterWritable类型了。
截取在终端运行该算法的信息来进行分析(由于信息太多,因此只截取部分重要信息),如图3?17所示。

image
image

图3?17 (续)
由上面的结果可以看出,循环的主体运行了三次就达到了阈值,即退出了循环。每次循环的map和reduce输出的canopy个数见表3?2。
image

可以看到,程序运行到最后剩下了7个聚类中心向量,但是,由图2-5可以知道,原始数据应该是有6个类别的,这说明该算法的某些参数设置不合理。
3.3.4 Mean Shift算法小结
本节通过对Mean Shift算法的介绍,让读者了解了Mahout实现该算法的思路,使读者对该算法有一个整体的认知,同时给出了一个该算法实战演示,方便读者运行该算法来计算数据。从实战中也可以看出,该算法对于演示使用的数据效果不是很好,这也从另外一个方面说明了算法其实和参数设置也是有很大关系的。参数设置合理,就会得到比较好的结果,否则,得到的结果将会不太理想。

相关文章
|
3月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
56 0
|
3月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
65 3
|
7天前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
1月前
|
机器学习/深度学习 人工智能 算法
深入解析图神经网络:Graph Transformer的算法基础与工程实践
Graph Transformer是一种结合了Transformer自注意力机制与图神经网络(GNNs)特点的神经网络模型,专为处理图结构数据而设计。它通过改进的数据表示方法、自注意力机制、拉普拉斯位置编码、消息传递与聚合机制等核心技术,实现了对图中节点间关系信息的高效处理及长程依赖关系的捕捉,显著提升了图相关任务的性能。本文详细解析了Graph Transformer的技术原理、实现细节及应用场景,并通过图书推荐系统的实例,展示了其在实际问题解决中的强大能力。
165 30
|
10天前
|
存储 监控 算法
企业内网监控系统中基于哈希表的 C# 算法解析
在企业内网监控系统中,哈希表作为一种高效的数据结构,能够快速处理大量网络连接和用户操作记录,确保网络安全与效率。通过C#代码示例展示了如何使用哈希表存储和管理用户的登录时间、访问IP及操作行为等信息,实现快速的查找、插入和删除操作。哈希表的应用显著提升了系统的实时性和准确性,尽管存在哈希冲突等问题,但通过合理设计哈希函数和冲突解决策略,可以确保系统稳定运行,为企业提供有力的安全保障。
|
1月前
|
存储 算法
深入解析PID控制算法:从理论到实践的完整指南
前言 大家好,今天我们介绍一下经典控制理论中的PID控制算法,并着重讲解该算法的编码实现,为实现后续的倒立摆样例内容做准备。 众所周知,掌握了 PID ,就相当于进入了控制工程的大门,也能为更高阶的控制理论学习打下基础。 在很多的自动化控制领域。都会遇到PID控制算法,这种算法具有很好的控制模式,可以让系统具有很好的鲁棒性。 基本介绍 PID 深入理解 (1)闭环控制系统:讲解 PID 之前,我们先解释什么是闭环控制系统。简单说就是一个有输入有输出的系统,输入能影响输出。一般情况下,人们也称输出为反馈,因此也叫闭环反馈控制系统。比如恒温水池,输入就是加热功率,输出就是水温度;比如冷库,
309 15
|
3月前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
2月前
|
算法 Linux 定位技术
Linux内核中的进程调度算法解析####
【10月更文挑战第29天】 本文深入剖析了Linux操作系统的心脏——内核中至关重要的组成部分之一,即进程调度机制。不同于传统的摘要概述,我们将通过一段引人入胜的故事线来揭开进程调度算法的神秘面纱,展现其背后的精妙设计与复杂逻辑,让读者仿佛跟随一位虚拟的“进程侦探”,一步步探索Linux如何高效、公平地管理众多进程,确保系统资源的最优分配与利用。 ####
76 4
|
2月前
|
缓存 负载均衡 算法
Linux内核中的进程调度算法解析####
本文深入探讨了Linux操作系统核心组件之一——进程调度器,着重分析了其采用的CFS(完全公平调度器)算法。不同于传统摘要对研究背景、方法、结果和结论的概述,本文摘要将直接揭示CFS算法的核心优势及其在现代多核处理器环境下如何实现高效、公平的资源分配,同时简要提及该算法如何优化系统响应时间和吞吐量,为读者快速构建对Linux进程调度机制的认知框架。 ####
|
3月前
|
存储 算法 搜索推荐
这些算法在实际应用中有哪些具体案例呢
【10月更文挑战第19天】这些算法在实际应用中有哪些具体案例呢
68 1

推荐镜像

更多