文章目录
- 分级聚类
- 理论
- 分级聚类的详细说明
- 1. 定义
- 2. 算法
- 3. 计算
- 4. 例子
- 5. 例题
- 皮尔逊相关系数
- julia实现
- 参考文献
分级聚类
理论
分级聚类的详细说明
1. 定义
分级聚类(Hierarchical Clustering),又称为层次聚类,是一种通过连续不断地将最为相似的群组两两合并,来构造出一个群组的层级结构的聚类方法。分级聚类是一种无监督学习算法,它不依赖于带有正确答案的样本数据进行训练,而是直接在一组数据中找寻某种结构。在分级聚类中,每个群组都是从单一元素开始的,通过不断合并,最终形成一个树状的层次结构。
2. 算法
分级聚类的基本算法过程如下:
- 初始化:每个数据点被视为一个单独的群组。
- 计算距离:计算每两个群组之间的距离或相似度。这通常基于数据点之间的距离度量,如欧氏距离、曼哈顿距离或皮尔逊相关系数等。
- 合并群组:选择距离最近(或相似度最高)的两个群组合并成一个新的群组。
- 重复迭代:重复上述步骤,直到所有的数据点都被合并成一个群组,或者达到某个预设的停止条件(如群组数量达到预设值)。
在分级聚类中,群组之间的距离有多种计算方式,包括但不限于:
- 最小距离法:群组之间的距离定义为两个群组中最近的两个数据点之间的距离。
- 最大距离法:群组之间的距离定义为两个群组中最远的两个数据点之间的距离。
- 平均距离法:群组之间的距离定义为两个群组中所有数据点对的平均距离。
- 重心法:群组之间的距离定义为两个群组的重心(或均值)之间的距离。
3. 计算
以皮尔逊相关系数为例,分级聚类的计算过程可能涉及以下步骤:
- 读取数据:从文件或数据库中读取待聚类的数据。
- 计算相关系数:使用皮尔逊相关系数公式计算每两个数据点之间的相似度。
- 构建距离矩阵:将相关系数转换为距离(或相似度)矩阵,其中每个元素表示两个数据点之间的距离(或相似度)。
- 合并群组:根据距离矩阵,选择距离最近(或相似度最高)的两个群组合并。
- 更新距离矩阵:合并后,需要重新计算新群组与其他群组之间的距离,并更新距离矩阵。
- 重复迭代:重复上述步骤,直到满足停止条件。
4. 例子
假设有以下五个数据点(以二维坐标表示):A(1,2)、B(2,3)、C(8,7)、D(6,5)、E(7,6)。使用分级聚类算法(以最小距离法为例)进行聚类,过程可能如下:
- 初始化:每个数据点被视为一个单独的群组。
- 计算距离:计算每两个数据点之间的距离,得到距离矩阵。
- 合并群组:选择距离最近的两个点(如A和B)合并成一个新的群组。
- 更新距离矩阵:计算新群组(AB)与其他数据点(C、D、E)之间的距离,并更新距离矩阵。
- 重复迭代:继续选择距离最近的两个群组合并,直到所有数据点都被合并成一个群组或达到预设的群组数量。
5. 例题
由于例题通常涉及具体的数学运算和详细的步骤,这里提供一个简化的示例问题:
问题:给定一组二维数据点,使用分级聚类算法(以最小距离法)进行聚类,并描述聚类过程。
解答:
- 读取数据:假设数据点已给出,如前面例子中的A、B、C、D、E。
- 计算距离:计算每两个数据点之间的距离,并确定哪两个点距离最近。
- 合并群组:将距离最近的两个点合并为一个新的群组,并更新群组列表。
- 重复迭代:继续计算新群组与其他群组之间的距离,并选择距离最近的两个群组合并,直到所有群组合并为一个或达到预设条件。
皮尔逊相关系数
皮尔逊相似度,在更严谨的学术表述中,通常被称为皮尔逊相关系数(Pearson Correlation Coefficient),是衡量两个变量之间线性相关程度的一个统计指标。
它的值域为[-1, 1],其中1表示完全正相关,-1表示完全负相关,0表示没有线性相关关系。
皮尔逊相关系数的计算公式为:
r = ∑ i = 1 n ( x i − x ˉ ) ( y i − y ˉ ) ∑ i = 1 n ( x i − x ˉ ) 2 ∑ i = 1 n ( y i − y ˉ ) 2 r = \frac{\sum_{i=1}^{n} (x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum_{i=1}^{n} (x_i - \bar{x})^2} \sqrt{\sum_{i=1}^{n} (y_i - \bar{y})^2}} r=∑i=1n(xi−xˉ)2∑i=1n(yi−yˉ)2∑i=1n(xi−xˉ)(yi−yˉ)
其中:
- n n n 是观测值的数量。
- x i x_i xi 和 y i y_i yi 分别是两个变量在第 i i i 个观测值上的取值。
- x ˉ \bar{x} xˉ 和 y ˉ \bar{y} yˉ 分别是 x x x 和 y y y 的平均值(即样本均值)。
计算步骤可以归纳为:
- 计算两个变量的平均值。
- 计算每个观测值与平均值的差。
- 计算这些差的乘积的和。
- 计算每个变量差的平方和,并开方得到标准差。
- 将步骤3的结果除以步骤4中两个标准差的乘积,得到皮尔逊相关系数。
julia实现
using Statistics
# 定义二叉树节点
struct TreeNode val :: Vector{Float64}left :: Union{TreeNode, Nothing} right :: Union{TreeNode, Nothing} function TreeNode(value, left=nothing, right=nothing) new(value, left, right) end
end function addLeftNode(a,b,parent_node)parent_node.left=TreeNode((a,b))
end
function addRightNode(a,b,parent_node)parent_node.right=TreeNode((a,b))
end#计算两个变量的平均值
function getMean(a,b) return mean.([a,b])
end#计算每个观测值与平均值的差
function getCha(a,b,mean_a,mean_b) return (a.-mean_a,b.-mean_b)
end#计算这些差的乘积的和
function getChaSum(cha_a,cha_b)return sum(cha_a.*cha_b)
end# 计算每个变量差的平方和,并开方得到标准差
function getChaSumSqrt(cha_a,cha_b)return (sqrt(sum(cha_a.^2)),sqrt(sum(cha_b.^2)))
end#得到皮尔逊相关系数
function getR(a,b)mean_a,mean_b=getMean(a,b)cha_a,cha_b=getCha(a,b,mean_a,mean_b)cha_sum=getChaSum(cha_a,cha_b)Cha_a_sumsqrt,Cha_b_sumsqrt=getChaSumSqrt(cha_a,cha_b)return cha_sum/(Cha_a_sumsqrt*Cha_b_sumsqrt)
end lst::Vector{Vector{Float64}}=[[20.,15.,124.],[73.,26.,71.],[99.,69.,132.],[33.,111.,128.],[241.,8.,71.],[19.,109.,41.]]
node_lst::Vector{TreeNode}=TreeNode.(lst)function getBestR(lst::Vector{Vector{Float64}}) ab_r_lst=[(i,j,1.0-abs(getR(lst[i],lst[j]))) for i in 1:length(lst) for j in 1:length(lst) if i != j]ab_r_matrix=fill(1.5,length(lst),length(lst))for d_r in ab_r_lsti,j,r=d_rab_r_matrix[i,j]=rendmin_r_val, id_r = findmin(ab_r_matrix) min_a_id= id_r[1]min_b_id=id_r[2]return (min_a_id,min_b_id)
endfunction groupNode(lst::Vector{Vector{Float64}},node_lst::Vector{TreeNode})if length(lst)==1return node_lst[1]endmin_a_id,min_b_id=getBestR(lst)right_node=node_lst[min_b_id]left_node=node_lst[min_a_id]root_node_value=((left_node.val).+right_node.val)/2.0root_node=TreeNode(root_node_value,left_node,right_node) deleteat!(lst,sort([min_a_id,min_b_id]))deleteat!(node_lst,sort([min_a_id,min_b_id]))push!(lst,root_node_value)push!(node_lst,root_node)groupNode(lst,node_lst)
endfunction levelOrder(root::TreeNode) if isnothing(root) return [] end # 使用 Vector 模拟队列 queue = [root] result = [] while !isempty(queue) # 当前层的节点数 level_size = length(queue) # 当前层的值列表 level_values = [] for _ in 1:level_size # 弹出队列的前端节点 node::TreeNode = popfirst!(queue) # 注意:popfirst! 会移除并返回数组的第一个元素 push!(level_values, node.val) # 如果左子节点存在,加入队列 if !isnothing(node.left) push!(queue, node.left) end # 如果右子节点存在,加入队列 if !isnothing(node.right) push!(queue, node.right) end end # 将当前层的值列表添加到结果中 push!(result, level_values) end return result
endroot=groupNode(lst,node_lst)
result = levelOrder(root)
println(result)
Any[Any[[56.8125, 43.34375, 118.9375]], Any[[93.625, 71.6875, 113.875], [20.0, 15.0, 124.0]], Any[[88.25, 74.375, 95.75], [99.0, 69.0, 132.0]], Any[[143.5, 37.75, 63.5], [33.0, 111.0, 128.0]], Any[[46.0, 67.5, 56.0], [241.0, 8.0, 71.0]], Any[[19.0, 109.0, 41.0], [73.0, 26.0, 71.0]]]* Terminal will be reused by tasks, press any key to close it.
参考文献
1.文心一言