基于距离阈值的聚类算法
1.最大最小距离算法
算法思想
对待分类模式样本集 以最大距离选取新的聚类中心，以最小距离原则进行模式归类。
算法步骤
- 从N个样本集中的任选取一个样本，作为第一个聚类中心 z 1 z_1 z 1 ；
- 选取距离第一个聚类中心 z 1 z_1 z 1 最远的样本作为第二个聚类中心 z 2 z_2 z 2 ；
- 计算剩余样本与 z 1 , z 2 z_1,z_2 z 1 ,z 2 之间的距离，并求出他们中的最小值，即： d i j = ∣ ∣ x i − z j ∣ ∣ , j = 1 , 2 ; d i = m i n [ d i 1 , d i 2 ] , i = 1 , 2 , ⋯ , N \displaystyle d_{ij}=||x_i-z_j||,\;j=1,2\;;\;\;\;d_i=min[d_{i1},d_{i2}],\;i=1,2,\cdots,N d i j =∣∣x i −z j ∣∣,j =1 ,2 ;d i =m i n [d i 1 ,d i 2 ],i =1 ,2 ,⋯,N
- 根据选定的比例系数 θ \theta θ，计算d l = m a x i { m i n [ d i 1 , d i 2 ] } \displaystyle d_l={max}i{min[d{i1},d_{i2}]}d l =m a x i {m i n [d i 1 ,d i 2 ]}； 若 d l > θ ⋅ ∣ ∣ z 1 − z 2 ∣ ∣ \displaystyle d_l>\theta\cdot ||z_1-z_2||d l >θ⋅∣∣z 1 −z 2 ∣∣，则相应的样本 x l x_l x l 作为第三个聚类中心 z 3 z_3 z 3 ，并转至下一步继续判断是否存在新的聚类中心； 否则，跳转至第 6 步;
- 假设存在 k 个聚类中心，计算个样本到各个聚类中心的距离 d i j d_{ij}d i j ,并算出：d l = m a x i { m i n [ d i 1 , d i 2 , ⋯ , d i k ] } \displaystyle d_l={max}i{min[d{i1},d_{i2},\cdots,d_{ik}]}d l =m a x i {m i n [d i 1 ,d i 2 ,⋯,d i k ]}； 若 d l > θ ⋅ ∣ ∣ z 1 − z 2 ∣ ∣ \displaystyle d_l>\theta\cdot ||z_1-z_2||d l >θ⋅∣∣z 1 −z 2 ∣∣，则 z k + 1 = x l z_{k+1}=x_l z k +1 =x l ,并继续在第五步循环，判断是否有新的聚类中心存在； 否则，转至第 6 步。
- 当判断不再有新的聚类中心存在时，计算：d i j = ∣ ∣ x i − z j ∣ ∣ , j = 1 , 2 , ⋯ , k ; i = 1 , 2 , ⋯ , N \displaystyle d_{ij}=||x_i-z_j||,\;j=1,2,\cdots,k\;;i=1,2,\cdots,N d i j =∣∣x i −z j ∣∣,j =1 ,2 ,⋯,k ;i =1 ,2 ,⋯,N，将样本集按最小距离原则分类到各个类中。
2.近邻聚类法
N个代分类样本{ x 1 , x 2 , ⋯ , x n } {x_1,x_2,\cdots,x_n}{x 1 ,x 2 ,⋯,x n }，将他们按照距离阈值 T T T 分类到以 z 1 , z 2 , ⋯ z_1,z_2,\cdots z 1 ,z 2 ,⋯ 为中心的类别中。
算法步骤
- 从N个样本中的任选取一个样本 x i x_i x i ，作为第一个聚类中心，如令 z 1 = x 1 z_1=x_1 z 1 =x 1 ；
- 计算样本 x 2 x_2 x 2 到 z 1 z_1 z 1 的欧式距离 d 21 = ∣ ∣ x 2 − x 1 ∣ ∣ d_{21}=||x_2-x_1||d 2 1 =∣∣x 2 −x 1 ∣∣： 若d 21 > T d_{21}>T d 2 1 >T，则定义一新的聚类中心 z 2 = x 2 z_2=x_2 z 2 =x 2 ； 否则，x 2 ∈ x_2\in x 2 ∈ 以 z 1 z_1 z 1 为中心的聚类；
- 假设已有聚类中心 z 1 , z 2 z_1, z_2 z 1 ,z 2 ，计算 d 31 = ∣ ∣ x 3 − z 1 ∣ ∣ ， d 32 = ∣ ∣ x 3 − z 2 ∣ ∣ d_{31}=||x_3-z_1||，d_{32}=||x_3-z_2||d 3 1 =∣∣x 3 −z 1 ∣∣，d 3 2 =∣∣x 3 −z 2 ∣∣： 若 d 31 > T d_{31}>T d 3 1 >T，则建立第三个聚类中心 z 3 = x 3 z_3=x_3 z 3 =x 3 ; 否则，x 2 ∈ x_2\in x 2 ∈ 离 z 1 和 z 2 z_1和z_2 z 1 和z 2 中最近的类（最近邻的聚类中心）； ⋯ ⋯ \cdots\cdots ⋯⋯
- 以此类推，直到将所有的 N 个样本都进行分类。
算法分析
用先验知识指导阈值 T T T 和起始点 z 1 z_1 z 1 的选择，可获得合理的聚类结果。否则只能选择不同的初值重复试探，并对聚类结果进行验算，根据一定的评价标准，得出合理的聚类结果。
缺点：很大程度上依赖于第一个聚类中心的位置选择、待分类模式样本的排列次序、距离阈值T的大小以及样本分布的几何性质等。
优点：计算简单。
Original: https://blog.csdn.net/qq_41536160/article/details/122110719
Author: 有梦想的雨
Title: 聚类——基于距离阈值的聚类算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/549994/
转载文章受原作者版权保护。转载请注明原作者出处！