人工智能原理复习7

智能优化算法问题

复习目标：

对于三种算法的流程掌握

一、GA

宏观认知：既能解决离散优化问题，又能解决连续优化问题

算法流程：

alt text

选择策略：轮盘赌

https://pic.imgdb.cn/item/667f7003d9c307b7e9d378d5.png

交叉策略：掩码的概念，哪里换哪里不换（0不换，1换）

alt text

结束策略：设置固定的迭代次数、还是达到目标精度

二、PSO

宏观认知：只能解决连续优化问题

PSO 不能解决离散优化问题（如TSP旅行商问题）

算法流程：

alt text

更新公式：

alt text

pbest 粒子自身最好的位置

gbest 全局最优的位置

三、ACO

宏观认知：只能解决离散优化问题

算法流程：

alt text

聚类

聚类的框架：

alt text

具体的聚类方法-对于聚类结果的评价

复习目标：

k-means

表述算法流程：

1、随机选取k个聚类中心

2、将每个数据点分配给距离最近的聚类中心点

3、更新聚类中心

4、重复第2、3步，直到没有点的分配再发生变化或达到预期的迭代次数

https://zhuanlan.zhihu.com/p/667109831

缺陷：需要在第一步强制的确定k值；只能处理凸的情况

AGENS Vs DIANA

参考链接： http://t.csdnimg.cn/qngh4

层次聚类 （Hierarchical Clustering）就是按照某种方法进行层次分类，直到满足某种条件为止。层次聚类主要分成两类

凝聚：从下到上。首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者满足某个终结条件

分裂：从上到下。首先将所有对象置于同一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件

掌握算法流程

DIANA 分裂层次聚类

分裂的层次聚类方法使用自顶向下的策略把对象划分到层次结构中。从包含所有对象的簇开始，每一步分裂一个簇，直到仅剩单点簇或者满足用户指定的簇数为止

DIANA算法是典型的层次分裂聚类算法

DIANA算法中用到如下两个定义

簇的直径：计算一个簇中任意两个数据点之间的欧式距离，选取距离中的最大值作为簇的直径

平均相异度：两个数据点之间的平均距离

DIANA算法描述如下

alt text

AGNES 凝聚层次聚类

凝聚层次聚类AGNES

凝聚的层次聚类方法使用自底向上的策略把对象组织到层次结构中。开始时以每个对象作为一个簇，每一步合并两个最相似的簇。

AGNES算法是典型的凝聚层次聚类，起始将每个对象作为一个簇，然后根据合并准则逐步合并这些簇。

两个簇间的相似度由这两个不同簇中距离最近的数据点的相似度确定。

聚类的合并过程反复进行直到所有对象最终满足终止条件设置的簇数目

AGNES算法描述如下

alt text

alt text

alt text

alt text

会根据矩阵提供算法流程的细节

DBSCAN 基于密度的聚类

参考链接： http://t.csdnimg.cn/Ndt47

http://t.csdnimg.cn/BL875

基于密度的带有噪声的空间聚类应用

掌握算法流程

DBSCAN算法的流程如下：

1、随机选择一个未被访问的数据点p。

2、以p为中心，以半径Eps为半径，找到半径内的所有数据点。

3、如果半径内的数据点数目小于MinPts，则将p标记为`噪声点`；否则，以p为`核心点`，创建一个新的簇，并将半径内的所有点加入该簇中。

4、以半径内的所有点为新的种子点，重复上述过程，直到该簇被完全发现。

5、重复以上过程，直到所有点都被访问过。

DBSCAN的算法时间复杂度为：O(nlogn)

DBSCAN中的点分为三类：

核心点、边界点和噪声点

核心点是指那些在邻域内具有足够多的点的对象

边界点则是那些邻近核心点但自身不是核心点的点

而噪声点则既不是核心点也不是边界点

直接密度可达和间接密度可达

优缺点:对于两个参数很敏感

Eps（ε）：领域的最大半径

MinPts：领域中的最小点数

什么是好的聚类？

参考链接： https://blog.csdn.net/qq_51392112/article/details/129169630

要求：

会算准确率、召回率（在F-Measure里面，重点关注就行）

评价聚类质量的指标：

一、基于匹配的度量：纯度

对于聚类后的结果我们并不知道每个簇所对应的真实类别，因此需要取每种情况下的最大值（注意这里是聚类后的每种情况）

alt text

https://pic.imgdb.cn/item/667fae72d9c307b7e9248d73.png

二、基于匹配的度量：F-Measure

涉及两个变量的计算：精度（同上文的纯度）、召回率

具体的计算过程参考这一案例

alt text

三、基于熵的度量：条件熵

这个老师上课好像没有讲，考试也没有要求