人工智能原理复习7
智能优化算法问题
复习目标:
对于三种算法的流程掌握
一、GA
宏观认知:既能解决离散优化问题,又能解决连续优化问题
算法流程:

选择策略:轮盘赌

交叉策略:掩码的概念,哪里换哪里不换(0不换,1换)

结束策略:设置固定的迭代次数、还是达到目标精度
二、PSO
宏观认知:只能解决连续优化问题
PSO 不能解决离散优化问题(如TSP旅行商问题)
算法流程:

更新公式:

pbest 粒子自身最好的位置
gbest 全局最优的位置
三、ACO
宏观认知:只能解决离散优化问题
算法流程:

聚类
聚类的框架:

具体的聚类方法-对于聚类结果的评价
复习目标:
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算法描述如下

AGNES 凝聚层次聚类
凝聚层次聚类AGNES
凝聚的层次聚类方法使用自底向上的策略把对象组织到层次结构中。开始时以每个对象作为一个簇,每一步合并两个最相似的簇。
AGNES算法是典型的凝聚层次聚类,起始将每个对象作为一个簇,然后根据合并准则逐步合并这些簇。
两个簇间的相似度由这两个不同簇中距离最近的数据点的相似度确定。
聚类的合并过程反复进行直到所有对象最终满足终止条件设置的簇数目
AGNES算法描述如下




会根据矩阵提供算法流程的细节
DBSCAN 基于密度的聚类
参考链接: http://t.csdnimg.cn/Ndt47
http://t.csdnimg.cn/BL875
基于密度的带有噪声的空间聚类应用
掌握算法流程
DBSCAN算法的流程如下:
1 |
|
DBSCAN的算法时间复杂度为:O(nlogn)
DBSCAN中的点分为三类:
核心点、边界点和噪声点
核心点是指那些在邻域内具有足够多的点的对象
边界点则是那些邻近核心点但自身不是核心点的点
而噪声点则既不是核心点也不是边界点
直接密度可达和间接密度可达
优缺点:对于两个参数很敏感
Eps(ε):领域的最大半径
MinPts:领域中的最小点数
什么是好的聚类?
参考链接: https://blog.csdn.net/qq_51392112/article/details/129169630
要求:
会算准确率、召回率(在F-Measure里面,重点关注就行)
评价聚类质量的指标:
一、基于匹配的度量:纯度
对于聚类后的结果我们并不知道每个簇所对应的真实类别,因此需要取每种情况下的最大值
(注意这里是聚类后的每种情况)


二、基于匹配的度量:F-Measure
涉及两个变量的计算:精度(同上文的纯度)、召回率
具体的计算过程参考这一案例

三、基于熵的度量:条件熵
这个老师上课好像没有讲,考试也没有要求