基础聚类

kmeans

kmeans++

选取距离这个聚类中心越远的点会有更高的概率被选为第二个聚类中心

PAM,Partitioning Around Medoids

首先随机选择k个对象作为中心，把每个对象分配给离它最近的中心。
然后随机地选择一个非中心对象替换中心对象，计算分配后的距离改进量
如果总的损失减少，则交换中心对象和非中心对象；
如果总的损失增加，则不进行交换

CLARA，Clustering LARge Applications

简单来说，当面对一个大样本量时，CLARA每次随机选取样本量中的一小部分进行PAM聚类，然后将剩余样本按照最小中心距离进行归类。在各次重复抽样聚类的结果中，选取误差最小，即中心点代换代价最小的结果作为最终结果。

总结:

算法	具体描述
k-means	以集群点的平均值作为参考对象进行聚类
k-medoids	以集群点中最中心（中位数）的对象为参考进行聚类
k-modes	以集群点特征的众数作为参考进行聚类
PAM	k-medoids的一个变体，使用迭代和贪心算法进行聚类
CLARA	在PAM的基础上对数据进行了抽样

算法	优缺点
k-means	优点：算法简单，时间复杂度低。缺点：无法处理非球形等不规则的数据、对初始值k的设置很敏感、对离群点敏感。
k-medoids	优点：对噪点和离群点不敏感。缺点：处理时间比k-means长、须事先指定所需聚类簇个数k。
k-modes	优点：可适用于离散性数据集、时间复杂度更低。缺点：需要事先对k值进行确定。
PAM	优点：对离群点数据不敏感。缺点：时间复杂度高。
CLARA	优点：可用于大规模数据集的聚类。缺点：在对数据进行随机抽样过程中采样不准确。

基于密度的聚类

算法流程

a.指定合适的r（点的半径）和M（在一个点半径内至少包含的点的个数）；
b.计算所有的样本点，如果点p的r邻域里有超过M个点，则创建一个以p为核心点的新簇；
c.反复寻找这些核心点直接密度可达的点，将其加入到相应的簇，对于核心点发生"密度相连"状况的簇，给予合并；
d.当没有新的点可以被添加到任何簇，算法结束。

OPTICS #revise/🚩

邻接矩阵

$近邻法$
他设置了一个距离阈值,然后用欧氏距离度量任意两点和的距离.即相似矩阵,然后根据和的大小关系,来定义邻接矩阵如下:

K近邻法
利用KNN算法遍历所有的样本点，取每个样本最近的k个点作为近邻，只有和样本距离最近的k个点之间的 𝑤𝑖𝑗>0 。但是这种方法会造成重构之后的邻接矩阵W非对称，我们后面的算法需要对称邻接矩阵。为了解决这种问题，一般采取下面两种方法之一：
全连接法
可以选择不同的核函数来定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。最常用的是高斯核函数RBF，此时相似矩阵和邻接矩阵相同：

实际情况中,用的最多的是第三种

拉普拉斯矩阵

L=D-W

总结

代表算法：DBSCAN、OPTICS、DENCLUE等。

算法	具体描述
DBSCAN	这类方法采用空间索引技术来搜索对象的邻域，将簇看做是数据空间中被低密度区域分割开的稠密对象区域
OPTICS	是DBSCAN算法的一种改进，对数据对象集合中的对象进行排序，得到一个有序的对象列表，其中包含了足够的信息用来提取聚类
DENCLUE	将每个数据点的影响用一个数学函数形式化地模拟出来，聚类簇通过密度吸引点（全局密度函数的局部最大值）来确定

各种算法的优缺点比较：

算法	优缺点
DBSCAN	优点：可以处理任何形状的聚类簇、能够检测异常点。缺点：需要给定数据点的半径r和最少数量m、对输入参数较敏感。
OPTICS	优点：对输入参数不敏感。缺点：计算量大、速度较慢。
DENCLUE	优点：对有巨大噪声的数据点有良好的聚类效果、比DBSCAN算法快得多、有严格的数学基础。缺点：需要大量的参数并且参数对结果的影响巨大。

指标

误差平方和(SSE,Sum of Squared Error)

这种损失最大的缺点是更加重视原理中心的点