人工智能与机器学习原理精解【12】

分级聚类

理论

分级聚类的详细说明

1. 定义

分级聚类（Hierarchical Clustering），又称为层次聚类，是一种通过连续不断地将最为相似的群组两两合并，来构造出一个群组的层级结构的聚类方法。分级聚类是一种无监督学习算法，它不依赖于带有正确答案的样本数据进行训练，而是直接在一组数据中找寻某种结构。在分级聚类中，每个群组都是从单一元素开始的，通过不断合并，最终形成一个树状的层次结构。

2. 算法

分级聚类的基本算法过程如下：

• 初始化：每个数据点被视为一个单独的群组。
• 计算距离：计算每两个群组之间的距离或相似度。这通常基于数据点之间的距离度量，如欧氏距离、曼哈顿距离或皮尔逊相关系数等。
• 合并群组：选择距离最近（或相似度最高）的两个群组合并成一个新的群组。
• 重复迭代：重复上述步骤，直到所有的数据点都被合并成一个群组，或者达到某个预设的停止条件（如群组数量达到预设值）。

在分级聚类中，群组之间的距离有多种计算方式，包括但不限于：

• 最小距离法：群组之间的距离定义为两个群组中最近的两个数据点之间的距离。
• 最大距离法：群组之间的距离定义为两个群组中最远的两个数据点之间的距离。
• 平均距离法：群组之间的距离定义为两个群组中所有数据点对的平均距离。
• 重心法：群组之间的距离定义为两个群组的重心（或均值）之间的距离。

3. 计算

以皮尔逊相关系数为例，分级聚类的计算过程可能涉及以下步骤：

• 读取数据：从文件或数据库中读取待聚类的数据。
• 计算相关系数：使用皮尔逊相关系数公式计算每两个数据点之间的相似度。
• 构建距离矩阵：将相关系数转换为距离（或相似度）矩阵，其中每个元素表示两个数据点之间的距离（或相似度）。
• 合并群组：根据距离矩阵，选择距离最近（或相似度最高）的两个群组合并。
• 更新距离矩阵：合并后，需要重新计算新群组与其他群组之间的距离，并更新距离矩阵。
• 重复迭代：重复上述步骤，直到满足停止条件。

4. 例子

假设有以下五个数据点（以二维坐标表示）：A(1,2)、B(2,3)、C(8,7)、D(6,5)、E(7,6)。使用分级聚类算法（以最小距离法为例）进行聚类，过程可能如下：

1. 初始化：每个数据点被视为一个单独的群组。
2. 计算距离：计算每两个数据点之间的距离，得到距离矩阵。
3. 合并群组：选择距离最近的两个点（如A和B）合并成一个新的群组。
4. 更新距离矩阵：计算新群组（AB）与其他数据点（C、D、E）之间的距离，并更新距离矩阵。
5. 重复迭代：继续选择距离最近的两个群组合并，直到所有数据点都被合并成一个群组或达到预设的群组数量。

5. 例题

由于例题通常涉及具体的数学运算和详细的步骤，这里提供一个简化的示例问题：

问题：给定一组二维数据点，使用分级聚类算法（以最小距离法）进行聚类，并描述聚类过程。

解答：

1. 读取数据：假设数据点已给出，如前面例子中的A、B、C、D、E。
2. 计算距离：计算每两个数据点之间的距离，并确定哪两个点距离最近。
3. 合并群组：将距离最近的两个点合并为一个新的群组，并更新群组列表。
4. 重复迭代：继续计算新群组与其他群组之间的距离，并选择距离最近的两个群组合并，直到所有群组合并为一个或达到预设条件。

皮尔逊相关系数

皮尔逊相似度，在更严谨的学术表述中，通常被称为皮尔逊相关系数（Pearson Correlation Coefficient），是衡量两个变量之间线性相关程度的一个统计指标。
它的值域为[-1, 1]，其中1表示完全正相关，-1表示完全负相关，0表示没有线性相关关系。
皮尔逊相关系数的计算公式为：

$$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}}$$

其中：

• $n$ 是观测值的数量。
• $x_i$ 和 $y_i$ 分别是两个变量在第 $i$ 个观测值上的取值。
• $\bar{x}$ 和 $\bar{y}$ 分别是 $x$ 和 $y$ 的平均值（即样本均值）。

计算步骤可以归纳为：

1. 计算两个变量的平均值。
2. 计算每个观测值与平均值的差。
3. 计算这些差的乘积的和。
4. 计算每个变量差的平方和，并开方得到标准差。
5. 将步骤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.文心一言