聚类属于无监督学习。
聚类的算法有很多种，其可分为基于划分、层次、密度、网格及模型的聚类方法。
根据数据集的不同，需要采用不同的聚类算法和策略。
1. 选择聚类算法，所面临的常见问题又哪些？
1） 不同形状的数据集。不同形状的数据集，也需要采取不同的度量策略，或者不同的聚类算法。
2）不同的数据次序。相同数据集，但数据输入次序不同，也会造成聚类的结果的不同。
3）噪声。不同的算法，对噪声的敏感程度不同。
2. 在高维的欧式空间，什么是“维数灾难”？
在高维下，所有点对的距离都差不多（如欧式距离），或者是几乎任意两个向量都是正交（利用夹角进行进行度量），这样聚类就很困难。
3. 常见的聚类算法的策略有哪些？
1）层次或凝聚式聚类。采取合并的方式，将邻近点或簇合并成一个大簇。
2）点分配。每次遍历数据集，将数据分配到一个暂时适合的簇中，然后不断更新。
4. 层次聚类算法的复杂度是多少？
每次合并，都需计算出两个点对之间的距离，复杂度是O(n^2), 后续步骤的开销，分布正比与O((n-1)^2), O((n-2)^2)...，这样求和算下来，算法复杂度是O(n^3).
算法优化：采用优先队列/最小堆来优化计算。优先队列的构建，第一步需要计算出每两个点的距离，这个开销是O(N^2). 一般情况下，N个元素，单纯的优先队列的构建开销为O（N），若是N^2个距离值，则建堆的开销是O(N^2)。
第二步，合并，合并需要一个删除、计算和重新插入的过程。因为合并一个簇对，就需要更新N个元素，开销为O(N*logN)。总的开销为O((N^2) * logN).
所以，总的算法复杂度为O((N^2) * logN).
5. 欧式空间与非欧式空间下，常见的簇之间的距离度量有哪些？
欧式空间：
1）两个簇之间的质心之间的距离最小
2）两个簇中所有点之间的最短距离
3）两个簇之间所有点对的平均距离
4）将具有最小半径的两个簇进行合并， 簇的半径：簇内的点到质心的最大距离
5）将具有最小直径的两个簇进行合并，簇的直径：簇内任意两点间的最大距离
非欧式空间，簇的中心点定义，该点距离其他点的距离最近，如何计算？
1）该点到簇中其他所有点的距离之和（求和），1-范数
2）该点到簇中其他点的最大距离（最大值），无穷-范数
3）该点到簇中其他点的平方和（平方和），2-范数
6. k-means算法，k均值算法
点分配式的聚类算法。一般用于球形或凸集的数据集。
算法步骤如下：
1）初始化k个选择点作为最初的k个簇的中心
2）计算每个点分别到k个簇的中心，并将点分配到其距离最近的簇中
3）由分配的点集，分别更新每个簇的中心，然后回到2，继续算法，直到簇的中心变化小于某个阈值
7. k-means算法的两个问题？
1）初始化选择点；常用的方式是尽量选择距离比较远的点（方法：依次计算出与已确定的点的距离，并选择距离最大的点），或者首先采取层次聚类的方式找出k个簇
2）如何选取k值；k值选取不当，会导致的问题？当k的数目低于真实的簇的数目时，平均直径或其他分散度指标会快速上升
可以采用多次聚类，然后比较的方式。多次聚类，一般是采用1, 2, 4, 8...数列的方式，然后找到一个指标在v/2, v时，获取较好的效果，然后再使用二分法，在[v/2, v]之间找到最佳的k值。
8. CURE算法
使用场景：
任何形状的簇，如S形、环形等等，不需要满足正态分布，欧式空间，可以用于内存不足的情况
特征：
簇的表示不是采用质心，而是用一些代表点的集合来表示。
算法步骤：
1）初始化。抽取样本数据在内存中进行聚类，方法可以采用层次聚类的方式，形成簇之后，从每个簇中再选取一部分点作为簇的代表点，并且每个簇的代表点之间的距离尽量远。对每个代表点向质心移动一段距离，距离的计算方法：点的位置到簇中心的距离乘以一个固定的比例，如20%。
2）对簇进行合并。当两个簇的代表点之间足够近，那么就合并这两个簇，直到没有更足够接近的簇。
3）点分配。对所有点进行分配，即将点分配给与代表点最近的簇。
9. GRGPF算法
场景：
非欧式空间，可用于内存不足的情况（对数据抽样）
特征：
同时使用了层次聚类和点分配的的思想。
如何表示簇？
数据特征：簇包含点的数目，簇中心点，离中心点最近的一些点集和最远的一些点集，ROWSUM(p)即点p到簇中其他店的距离平方和。靠近中心的点集便于修改中心点的位置，而远离中心的点便于对簇进行合并。
簇的组织：类似B-树结构。首先，抽取样本点，然后做层次聚类，就形成了树T的结构。然后，从树T中选取一系列簇，即是GRGPF算法的初始簇。然后将T中具有相同祖先的簇聚合，表示书中的内部节点。
点的分配：对簇进行初始化之后，将每个点插入到距离最近的那个簇。
具体处理的细节更为复杂，如果对B-树比较了解，应该有帮助。
10. 流聚类，如何对最近m个点进行聚类？
N个点组成的滑动窗口模型，类似DGIM算法中统计1的个数。
1）首先，划分桶，桶的大小是2的次幂，每一级桶的个数最多是b个。
2）其次，对每个桶内的数据进行聚类，如采用层次聚类的方法。
3）当有新数据来临，需要新建桶，或者合并桶，这个类似于GDIM，但除了合并，还需要合并簇，当流内聚类的模型变化不是很快的时候，可以采取直接质心合并的方式。
4）查询应答：对最近的m个点进行聚类，当m不在桶的分界线上时，可以采用近似的方式求解，只需求出 包含m个点的最少桶 的结果
插入排序：
对于小型的排序任务速度很快，它是稳定的，只需要O(1)的额外空间，基于比较和交换的次数为O(n^2)。
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <queue>
using namespace std;
int x[8]={55,41,59,26,53,58,97,93};
int main()
{
//ifstream fin;
//fin.open("data1.txt");
for(int i=1;i<8;i++)
for(int j=i;j>0 && x[j]<x[j-1];j-- )
{
int t=x[j];
x[j]=x[j-1];
x[j-1]=t;
}
for(int i=0;i<8;i++)cout<<x[i]<<" ";
cout<<endl;
return 0;
}
快速排序：
如果n很大，快速排序的O(n*logn)的运行时间就很关键了，在结合随机划分和双向划分后，对于任意的n元输入数组，快排的期望运行时间正比于 n logn。
下面代码的版本是基于第一个元素进行划分，对于随机输入的数据这是没有问题的，但是对于某些常见输入，比如数组已基本有序，那么最坏情况下需要
O(n^2)的时间，这时候，我们可以才用随机划分元素的方法，可以改善性能，通过把第一个元素和后面所有元素中的一个随机项交换来实现这一点：
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <queue>
using namespace std;
int x[8]={55,41,59,26,53,58,97,93};
void qsort1(int l,int u)
{
if(l>=u)return;
int m=l;
for(int i=l+1;i<=u;i++)
{
if(x[i]<x[l]){
m++;
int t=x[m];
x[m]=x[i];
x[i]=t;
}
}
int t=x[l];
x[l]=x[m];
x[m]=t;
qsort1(l,m-1);
qsort1(m+1,u);
}
int main()
{
qsort1(0,7);
for(int i=0;i<8;i++)cout<<x[i]<<" ";
cout<<endl;
return 0;
}
顺便说一下：C库函数qsort非常简单相对较快，但是它比我们自己写的快排慢，仅仅是因为其通用而灵活的接口对每次比较都使用函数调用，C++库函数sort具有最简单的
接口：我们通过调用sort(x,x+n)来对数组x排序，实现也很高效。
Openvswitch之Qos rate-limiting原理
OVS的qosrate-limiting功能是采用令牌桶（Token-Bucket）机制进行的。这里的“令牌桶”是指网络设备的内部存储池，而“令牌”则是指以给定速率填充令牌桶的虚拟信息包。
一 令牌桶算法原理
在令牌桶处理包的行为方面，RFC中定义了两种令牌桶算法——单速率三色标记算法和双速率三色标记算法，其评估结果都是为包打上红、黄、绿三色标记。QoS会根据包的颜色，设置包的丢弃优先级，其中单速率三色标记比较关心包尺寸的突发，而双速率三色标记则关注速率上的突发，两种算法都可工作于色盲模式和非色盲模式。下面分别介绍这两种算法原理。
1.单速率三色标记算法原理
这里首先要理解“单速率”是什么意思，那就是算法中的两个令牌桶有同样的承诺信息速率（CIR），也就是具有相同平均访问速率。这两个令牌桶分别是正常使用的令牌桶（C桶）和超出令牌桶容量的突发令牌桶（E桶），可以理解为两个水桶，一个是正常使用的水桶，另一个是用来当正常使用的水桶满后装多余的水的水桶。
单速率三色标记算法关注的是数据包的突发尺寸，数据包的色标记评估依据以下3个参数：承诺信息速率(CommittedInformationRate，CIR)、承诺突发尺寸（CommittedBurstSize，CBS）和超额突发尺寸（ExcessBurstSize，EBS）。CIR是指向令牌桶中填充令牌的平均速率，即允许的通信流平均速度；CBS是指每次突发所允许的最大的流量尺寸，也相当于允许的最大取令牌的速率，等于桶的容量（最大时就是一个包就可以全部领取桶中的全部令牌）。EBS是指每次突发允许超出CBS的最大流量尺寸。CBS和EBS的单位都是bit（位）。
单速率三色机制采用双桶结构：C桶和E桶（之所以用这两个字母来表示，为的就是与前面说的CBS和EBS两种速率的头个字母一致，便于描述），且两个令牌桶的CIR一样。C令牌桶中任何未用的令牌都被放入E令牌桶中，用做以后临时超过CIR的突发流量的令牌；另外，当C令牌桶满时，超出的令牌也都会放在E令牌桶中。
Tc和Te分别表示C令牌桶和E令牌桶中的令牌数，也就是桶中当前的容量（单位也为bit），两桶的总容量分别为CBS和EBS，也就是对应前面介绍的承诺突发尺寸和超额突发尺寸，最初它们都是满的，即Tc和Te初始值分别等于CBS和EBS。正常情况下，不会使用第二个令牌桶（也就是E桶），而是把任何CBS（也就是C桶）中未使用的令牌都放入E桶中，只有当C令牌桶满后，后面来的令牌才放到E令牌桶中，为可能出现的突发数据提供信用令牌（也就是经过允许的令牌）。
在这种单速率三色标记算法中，两个令牌桶中令牌的添加是按照相同的CIR速率进行的。即每隔1/CIR时间添加一个令牌。添加的顺序是先添加C桶再添加E桶，当两个令牌桶中的令牌都满时，再产生的令牌就会被丢弃。至于在发送数据包时，令牌的使用IEEE又定义了三种颜色（分别为红色、黄色和绿色）以及两种模式：色盲模式和感色模式，默认为色盲模式。三种颜色的功能与我们日常生活中的交通指示灯中的三种颜色类似，红色表示违规数据，直接丢弃，黄色表示数据包虽然违法，但不直接丢弃，而是延迟发送，绿色为合法数据包，直接发送。
在色盲（color-blind）模式下是假设包都是没有经过“着色”处理的（不辨别包中原来标记的颜色），是根据包长度来确定包被标记的颜色。现假设到达的包长度为B（单位为bit）。若包长度B小于C桶中的令牌数Tc（也就是C桶中的令牌数足够该包发送所需），则包被标记为绿色，表示包符合要求，包发送后C桶中的令牌数Tc减少B。如果Tc<B<Te（也就是包长度大于C桶中的令牌数，而小于E桶中的令牌数），则标记为黄色，则从E桶中取出所需令牌，E桶中的令牌数Te减少B；若B>Te，标记为红色，表示是违反规定的包，直接丢弃，两令牌桶中的总令牌数都不减少。