簇算法

⑴ 八：聚类算法K-means（20191223-29)

学习内容：无监督聚类算法K-Means

k-means：模型原理、收敛过程、超参数的选择

聚类分析是在数据中发现数据对象之间的关系，将数据进行分组，组内的相似性越大，组间的差别越大，则聚类效果越好。

不同的簇类型： 聚类旨在发现有用的对象簇，在现实中我们用到很多的簇的类型，使用不同的簇类型划分数据的结果是不同的。

基于原型的： 簇是对象的集合，其中每个对象到定义该簇的 原型 的距离比其他簇的原型距离更近，如(b)所示的原型即为中心点，在一个簇中的数据到其中心点比到另一个簇的中心点更近。这是一种常见的 基于中心的簇 ，最常用的K-Means就是这样的一种簇类型。 这样的簇趋向于球形。

基于密度的 ：簇是对象的密度区域，(d)所示的是基于密度的簇，当簇不规则或相互盘绕，并且有早上和离群点事，常常使用基于密度的簇定义。

关于更多的簇介绍参考《数据挖掘导论》。

基本的聚类分析算法

     1. K均值： 基于原型的、划分的距离技术，它试图发现用户指定个数(K)的簇。

     2. 凝聚的层次距离： 思想是开始时，每个点都作为一个单点簇，然后，重复的合并两个最靠近的簇，直到尝试单个、包含所有点的簇。

     3. DBSCAN: 一种基于密度的划分距离的算法，簇的个数有算法自动的确定，低密度中的点被视为噪声而忽略，因此其不产生完全聚类。

不同的距离量度会对距离的结果产生影响，常见的距离量度如下所示：

优点：易于实现 

缺点：可能收敛于局部最小值，在大规模数据收敛慢

算法思想：

选择K个点作为初始质心 

repeat

    将每个点指派到最近的质心，形成K个簇 

    重新计算每个簇的质心  

until 簇不发生变化或达到最大迭代次数

这里的“重新计算每个簇的质心”，是根据目标函数来计算的，因此在开始时要考虑 距离度量和目标函数。

考虑欧几里得距离的数据，使用 误差平方和（Sum of the Squared Error,SSE） 作为聚类的目标函数，两次运行K均值产生的两个不同的簇集，使用SSE最小的那个。

k表示k个聚类中心，ci表示第几个中心，dist表示的是欧几里得距离。 

这里有一个问题就是为什么，我们更新质心是让所有的点的平均值，这里就是SSE所决定的。

k均值算法非常简单且使用广泛，但是其有主要的两个缺陷：

1. K值需要预先给定 ，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后找出Cost Function最小时所对应的K值，这个值往往能较好的描述有多少个簇类。

2. K-Means算法对初始选取的聚类中心点是敏感的 ，不同的随机种子点得到的聚类结果完全不同

3. K均值算法并不是很所有的数据类型。 它不能处理非球形簇、不同尺寸和不同密度的簇，银冠指定足够大的簇的个数是他通常可以发现纯子簇。

4. 对离群点的数据进行聚类时，K均值也有问题 ，这种情况下，离群点检测和删除有很大的帮助。

下面对初始质心的选择进行讨论：

当初始质心是随机的进行初始化的时候，K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕，可能只能得到局部的最优解，而无法得到全局的最优解。

多次运行，每次使用一组不同的随机初始质心，然后选择一个具有最小的SSE的簇集。该策略非常的简单，但是效果可能不是很好，这取决于数据集合寻找的簇的个数。

关于更多，参考《数据挖掘导论》

为了克服K-Means算法收敛于局部最小值的问题，提出了一种 二分K-均值(bisecting K-means)

将所有的点看成是一个簇

当簇小于数目k时

    对于每一个簇

        计算总误差

        在给定的簇上进行K-均值聚类,k值为2        计算将该簇划分成两个簇后总误差

    选择是的误差最小的那个簇进行划分

在原始的K-means算法中，每一次的划分所有的样本都要参与运算，如果数据量非常大的话，这个时间是非常高的，因此有了一种分批处理的改进算法。

使用Mini Batch（分批处理）的方法对数据点之间的距离进行计算。

Mini Batch的好处：不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。n 由于计算样本量少，所以会相应的减少运行时间n 但另一方面抽样也必然会带来准确度的下降。

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集成为一个“簇”。通过这样的划分，每个簇可能对应于一些潜在的概念（也就是类别）；需说明的是，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇对应的概念语义由使用者来把握和命名。

聚类是无监督的学习算法，分类是有监督的学习算法。所谓有监督就是有已知标签的训练集（也就是说提前知道训练集里的数据属于哪个类别），机器学习算法在训练集上学习到相应的参数，构建模型，然后应用到测试集上。而聚类算法是没有标签的，聚类的时候，需要实现的目标只是把相似的东西聚到一起。

聚类的目的是把相似的样本聚到一起，而将不相似的样本分开，类似于“物以类聚”，很直观的想法是同一个簇中的相似度要尽可能高，而簇与簇之间的相似度要尽可能的低。

性能度量大概可分为两类： 一是外部指标， 二是内部指标 。

外部指标：将聚类结果和某个“参考模型”进行比较。

内部指标：不利用任何参考模型，直接考察聚类结果。

对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大

初学者会很容易就把K-Means和KNN搞混，其实两者的差别还是很大的。

K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。

当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。

优点：

简单， 易于理解和实现 ；收敛快，一般仅需5-10次迭代即可，高效

缺点：

    1，对K值得选取把握不同对结果有很大的不同

    2，对于初始点的选取敏感，不同的随机初始点得到的聚类结果可能完全不同

    3，对于不是凸的数据集比较难收敛

    4，对噪点过于敏感，因为算法是根据基于均值的

    5，结果不一定是全局最优，只能保证局部最优

    6，对球形簇的分组效果较好，对非球型簇、不同尺寸、不同密度的簇分组效果不好。

K-means算法简单理解，易于实现（局部最优），却会有对初始点、噪声点敏感等问题；还容易和监督学习的分类算法KNN混淆。

参考阅读：

1.《 深入理解K-Means聚类算法 》

2.《 K-Means 》

⑵ 关于随机生成节点，想在ns2里模拟分簇网络，但实现分簇算法觉得挺麻烦的，就想模拟下已经分好簇的网络 。

这个很好弄啊，可以在tcl里面实现也可以在C++里面实现，用random就行。NS2里面通过TCL机制和C++协同工作，入门有点晕，具体问题可以给我发邮件[email protected]

⑶ 无线传感器网络通信协议的目录

第1章 无线传感器网络概述
1.1 引言
1.2 无线传感器网络介绍
1.2.1 无线传感器网络体系结构
1.2.2 无线传感器网络的特点和关键技术
1.2.3 无线传感器网络的应用
1.3 无线传感器网络路由算法
1.3.1 无线传感器网络路由算法研究的主要思路
1.3.2 无线传感器网络路由算法的分类
1.3.3 无线传感器网络QoS路由算法研究的基本思想
1.3.4 无线传感器网络QoS路由算法研究的分类
1.3.5 平面路由的主流算法
1.3.6 分簇路由的主流算法
1.4 ZigBee技术
1.4.1 ZigBee技术的特点
1.4.2 ZigBee协议框架
1.4.3 ZigBee的网络拓扑结构
1.5 无线传感器安全研究
1.5.1 无线传感器网络的安全需求
1.5.2 无线传感器网络安全的研究进展
1.5.3 无线传感器网络安全的研究方向
1.6 水下传感器网络
1.7 无线传感器网络定位
1.7.1 存在的问题
1.7.2 性能评价
1.7.3 基于测距的定位方法
1.7.4 非测距定位算法
1.7.5 移动节点定位
第2章 无线传感器网络的分布式能量有效非均匀成簇算法
2.1 引言
2.2 相关研究工作
2.2.1 单跳成簇算法
2.2.2 多跳成簇算法
2.3 DEEUC成簇路由算法
2.3.1 网络模型
2.3.2 DEEUC成簇算法
2.3.3 候选簇头的产生
2.3.4 估计平均能量
2.3.5 最终簇头的产生
2.3.6 平衡簇头区节点能量
2.3.7 算法分析
2.4 仿真和分析
2.5 结论及下一步工作
参考文献
第3章 无线传感器网络分簇多跳能量均衡路由算法
3.1 无线传输能量模型
3.2 无线传感器网络路由策略研究
3.2.1 平面路由
3.2.2 单跳分簇路由算法研究
3.2.3 多跳层次路由算法研究
3.3 LEACH-L算法
3.3.1 LEACH-L的改进思路
3.3.2 LEACH-L算法模型
3.3.3 LEACH-L描述
3.4 LEACH-L的分析
3.5 实验仿真
3.5.1 评价参数
3.5.2 仿真环境
3.5.3 仿真结果
3.6 总结及未来的工作
3.6.1 总结
3.6.2 未来的工作
参考文献
第4章 基于生成树的无线传感器网络分簇通信协议
4.1 引言
4.2 无线传输能量模型
4.3 基于时间延迟机制的分簇算法（CHTD）
4.3.1 CHTD的改进思路
4.3.2 CHTD簇头的产生
4.3.3 CHTD簇头数目的确定
4.3.4 CHTD最优簇半径
4.3.5 CHTD描述
4.3.6 CHTD的特性
4.4 CHTD簇数据传输研究
4.4.1 引言
4.4.2 改进的CHTD算法（CHTD-M）
4.4.3 CHTD-M的分析
4.5 仿真分析
4.5.1 生命周期
4.5.2 接收数据包量
4.5.3 能量消耗
4.5.4 负载均衡
4.6 总结及未来的工作
4.6.1 总结
4.6.2 未来的工作
参考文献
第5章 基于自适应蚁群系统的传感器网络QoS路由算法
5.1 引言
5.2 蚁群算法
5.3 APAS算法的信息素自适应机制
5.4 APAS算法的挥发系数自适应机制
5.5 APAS算法的QoS改进参数
5.6 APAS算法的信息素分发机制
5.7 APAS算法的定向广播机制
5.8 仿真实验及结果分析
5.8.1 仿真环境
5.8.2 仿真结果及分析
5.9 总结及未来的工作
5.9.1 总结
5.9.2 未来的工作
参考文献
第6章 无线传感器网络簇头选择算法
6.1 引言
6.2 LEACH NEW算法
6.2.1 网络模型
6.2.2 LEACH NEW簇头选择机制
6.2.3 簇的生成
6.2.4 簇头间多跳路径的建立
6.3 仿真实现
6.4 结论及未来的工作
参考文献
第7章 水下无线传感网络中基于向量的低延迟转发协议
7.1 引言
7.2 相关工作
7.3 网络模型
7.3.1 问题的数学描述
7.3.2 网络模型
7.4 基于向量的低延迟转发协议
7.4.1 基于向量转发协议的分析
7.4.2 基于向量的低延迟转发算法
7.5 仿真实验
7.5.1 仿真环境
7.5.2 仿真分析
7.6 总结
参考文献
第8章 无线传感器网络数据融合算法研究
8.1 引言
8.2 节能路由算法
8.2.1 平面式路由算法
8.2.2 层状式路由算法
8.3 数据融合模型
8.3.1 数据融合系统
8.3.2 LEACH簇头选择算法
8.3.3 簇内融合路径
8.3.4 环境设定和能耗公式
8.4 数据融合仿真
8.4.1 仿真分析
8.4.2 仿真结果分析
8.5 结论
参考文献
第9章 无线传感器网络相关技术
9.1 超宽带技术
9.1.1 系统结构的实现比较简单
9.1.2 空间传输容量大
9.1.3 多径分辨能力强
9.1.4 安全性高
9.1.5 定位精确
9.2 物联网技术
9.2.1 物联网原理
9.2.2 物联网的背景与前景
9.3 云计算技术
9.3.1 SaaS软件即服务
9.3.2 公用/效用计算
9.3.3 云计算领域的Web服务
9.4 认知无线电技术
9.4.1 传统的Ad-hoc方式中无线传感器网络的不足
9.4.2 在ZigBee无线传感器网络中的应用
参考文献
第10章 无线传感器网络应用
10.1 军事应用
10.2 农业应用
10.3 环保监测
10.4 建筑应用
10.5 医疗监护
10.6 工业应用
10.6.1 工业安全
10.6.2 先进制造
10.6.3 交通控制管理
10.6.4 仓储物流管理
10.7 空间、海洋探索
10.8 智能家居应用

⑷ 高分求助ns关于分簇算法源代码

祝愿你成功

⑸ 聚类算法

1. 概述

K-means聚类算法也称k均值聚类算法，是集简单和经典于一身的基于距离的聚类算法。它采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为类簇是由距离靠近的对象组成的，因此把得到 紧凑且独立的簇作为最终目标。

2. 算法核心思想

K-means聚类算法是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

3. 算法实现步骤

1、首先确定一个k值，即我们希望将数据集经过聚类得到k个集合。

2、从数据集中随机选择k个数据点作为质心。

3、对数据集中每一个点，计算其与每一个质心的距离（如欧式距离），离哪个质心近，就划分到那个质心所属的集合。

4、把所有数据归好集合后，一共有k个集合。然后重新计算每个集合的质心。

5、如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），我们可以认为聚类已经达到期望的结果，算法终止。

6、如果新质心和原质心距离变化很大，需要迭代3~5步骤。

4. 算法步骤图解

上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。

K-means术语：

簇：所有数据的点集合，簇中的对象是相似的。

质心：簇中所有点的中心（计算所有点的中心而来）

5. K-means算法优缺点

优点：

1、原理比较简单，实现也是很容易，收敛速度快。

2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。

3、主要需要调参的参数仅仅是簇数k。

缺点：

1、K值需要预先给定，很多情况下K值的估计是非常困难的。

2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。

3、对噪音和异常点比较的敏感。用来检测异常值。

4、采用迭代方法，可能只能得到局部的最优解，而无法得到全局的最优解。

⑹ 什么叫做网络的分簇

你在网络上发送一个东西，就是以簇为单位传送过去的

⑺ 聚类算法有哪些分类

聚类算法的分类有：

1、划分法

划分法(partitioning methods)，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K小于N。而且这K个分组满足下列条件：

（1） 每一个分组至少包含一个数据纪录；

（2）每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；

2、层次法

层次法(hierarchical methods)，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。

例如，在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满足为止。

3、密度算法

基于密度的方法(density-based methods)，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。

4、图论聚类法

图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。因此，每一个最小处理单元数据之间都会有一个度量表达，这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源，因而其主要优点是易于处理局部数据的特性。

5、网格算法

基于网格的方法(grid-based methods)，这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。

代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

6、模型算法

基于模型的方法(model-based methods)，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。

通常有两种尝试方向：统计的方案和神经网络的方案。

(7)簇算法扩展阅读：

聚类算法的要求：

1、可伸缩性

许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能会导致有偏的结果。

我们需要具有高度可伸缩性的聚类算法。

2、不同属性

许多算法被设计用来聚类数值类型的数据。但是，应用可能要求聚类其他类型的数据，如二元类型(binary)，分类/标称类型（categorical/nominal），序数型（ordinal）数据，或者这些数据类型的混合。

3、任意形状

许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。

4、领域最小化

许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担，也使得聚类的质量难以控制。

5、处理“噪声”

绝大多数现实中的数据库都包含了孤立点，缺失，或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。

6、记录顺序

一些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合，当以不同的顺序交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。