人工智能与机器学习原理精解【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_lst
        i,j,r=d_r
        ab_r_matrix[i,j]=r
    end
    min_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)
end

function groupNode(lst::Vector{Vector{Float64}},node_lst::Vector{TreeNode})
    if length(lst)==1
        return node_lst[1]
    end
    min_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.0
    root_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)
end


function 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  
end

root=groupNode(lst,node_lst)
result = levelOrder(root)  
println(result)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

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
2

参考文献

1.文心一言