聚类分析

• 聚类模型的本质：将数据集中相似的样本进行分组的过程
• 每个组称为一个簇(cluster)每个簇的样本对应一个潜在的类别
• 样本是没有类别标签的，因此聚类是一种典型的无监督学习任务 ，这些簇满足以下两个条件：
  • 相同簇的样本之间距离较近
  • 不同簇的样本之间距离较远

K-means模型

层次聚类

层次聚类(hierarchical clustering)在不同层级上对样本进行聚类，逐步形成树状的结构
根据层次分解是以自底向上（合并）还是自顶向下（分裂）方式，层次聚类方法可以分为
聚合式聚类(agglomerative clustering)
分拆式聚类(divisive clustering)
两种方法均是启发式的策略，并没有去优化一个明确的目标函数来实现聚类，很难严格评价聚类的效果

聚合式聚类

单连接

完整连接

平均连接

比较

单连接法只需要两簇内有成员对距离足够近就将两簇合并，而并没有考虑其他簇内其他成员的距离，因此单连接方法形成的簇很有可能违背紧致性特征 即簇内成员应该尽可能相似
完整连接法是另外一个极端，只有当两簇的联合的成员间的距离相对较小时才将两簇进行合并，因此完整连接法倾向于生成紧致簇
平均连接法是介于单连接和完整连接之间的方法，易于生成相对紧致的簇同时簇间距离较远

分拆式聚类

分拆式聚类将所有样本集合看作一簇，以自上而下的方式，递归地将现有的簇分拆为两个子簇
利用不同的启发式方法进行分拆方式的选择：
二分K-means聚类
选择半径最大的簇，对该簇进行K-means聚类分为两个子簇
重复此过程直到达到想要的簇个数
最小生成树法
将每个样本看作一个图节点，将样本间距离看作节点间边的权重，根据此图建立最小生成树
从权重最大处将该簇分拆为两簇，然后重复此过程直到达到想要的簇个数。实际上，该方法得到的聚类结果和单连接的聚合聚类得到的结果一致

总结

层次聚类一次性地得到了整个聚类的过程，想要分多少个簇都可以直接根据树图来得到结果，改变簇的数目不需要再次计算数据点的归属类别;
单连接和完全连接代表了簇间距离度量的两个极端，它们对离群点或噪声数据过分敏感;
平均连接是一种折中方法，它可以克服离群点敏感性问题
层次聚类的缺点是计算量大，而且错分在层次聚类中是不可修正的，一旦某个样本被分到某个聚类中，则该样本永远停留在该聚类中

密度聚类

密度聚类又称为基于密度聚类（density-based clustering）。此类算法假设聚类结构由样本分布的紧密程度确定，以数据集在空间分布上的稠密程度为依据进行聚类，即只要一个区域中的样本密度大于某个阈值，就把它划入与之相近的簇中。
不同于基于质心的原型聚类算法，基于密度的算法不需要事先设置k值。常用的密度聚类算法：DBSCAN、MDCA、OPTICS、DENCLUE等。

DBSCAN算法

算法原理
DBSCAN是一种著名的密度聚类算法，它基于一组邻域参数(ϵ，Minpts)刻画样本分布的紧密程度，寻找数据集中的高密度以及低密度区域来完成聚类。可以将该算法归纳为三个步骤：设定邻域参数，数据点分类，聚类。
第一步：设定邻域参数(ϵ，Minpts)
以各个数据点为中心，以ϵ为半径，计算其ϵ-邻域内的数据点密度。其中Minpts代表一个簇中最少的数据点个数，高于这个值则为高密度区域，否则为低密度区域。用户可以根据数据集的实际密度的不同设置这两个参数。
第二步：数据点分类
基于邻域参数，在DBSCAN算法中，所有的数据点可以分为以下三个类别：
核心点:如果某个点的邻域内的数据点数目高于阈值minpts，则将这个点视为核心点。
边界点是位于核心点邻域之内的，但是其自身的邻域内数据点数小于minpts的点，起到将高密度区域与低密度区域分割开的作用。
噪声点:既不是核心点也不是边界点的其他数据点，他们组成低密度区域。
![[Pasted image 20230604194801.png]]
进行密度聚类之前还需要了解下面三个概念：
密度直达：两个同属于一个邻域的数据点是密度直达关系
密度可达：o在p的邻域内，从p到o是密度直达，而q对象的邻域内不包括p，但是包括o，这样p->o->q，称p到q是密度可达的。
密度相连：q和p是密度可达的, q和t也是密度可达的，则p和t是密度相连的。
第三步：聚类
DBSCAN的目标为找到密度相连数据点的最大集合，此集合作为最终的一簇。首先核心点各自成簇，采用密度相连的概念逐步对簇进行合并，打上标记。
最终核心点密集的区域会被低密度噪声点包围，噪声点不单独成簇。所以采用DBSCAN进行聚类，最终的结果有一些数据点是没有标记的，这些就是噪声点。
优点：

1. 无需事先设定簇的个数，算法根据数据自身找出各簇
2. 适于稠密的非凸数据集，可以发现任意形状的簇
3. 可以在聚类时发现噪音点、对数据集中的异常点不敏感
4. 对样本输入顺序不敏感
   缺点：
5. 因为是基于密度分析，如果客观存在的两个簇没有明显的可分间隔，则很有可能被合并为同一个簇
6. 同时DBSCAN聚类的参数调节较为复杂，参数设置对结果影响较大
7. DBSCAN对高维的数据处理效果不好

PageRank算法

基本思想：

1. 不只考虑词项，还考虑指向该网页的链接情况
2. 被越多优质的网页所指的网页，它是优质的概率就越大
   Dead End问题
   链接农场问题
   交换网站
   黄金链
   如何解决链接农场问题？
3. 对链接的质量进行评估：Google 能够评估链接的质量，通过评估，会考虑链接的来源、内容以及对页面质量产生的影响等因素。
4. 对链接的数量进行评估：如果某个网站的链接数量异常突出，Google 就会高度怀疑这些链接的真实性，因此会对这些链接进行评估，以判断它们是否具有真正价值。
5. 采用基于内容的评估方法：Google 会对链接所指向的网页进行内容判断，如果发现这些页面的内容与链接不相关或者低质量，就会对链接产生负面评价。