1. 决策树归纳算法 (Decision Tree Induction Algorithm)
说明: 决策树归纳算法是一种贪心算法，采用自顶向下递归的方式构建决策树。它在每一步选择最优的属性来划分数据集，直到满足预设的停止条件（例如，节点中的所有样本都属于同一类别，或没有可用于划分的属性）。
伪代码:
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
| 函数 Generate_decision_tree(数据集 E, 属性集 F):
// 1. 创建结点N
结点 N = createNode()
// 2. 检查停止条件
如果 E 中所有记录都属于同一个类 C:
N.label = C // 标记为叶结点
返回 N
如果 F 为空 (没有更多属性可用于划分):
N.label = E 中最常见的类 (多数表决) // 标记为叶结点
返回 N
// 3. 选择最佳划分属性和条件
root.test_cond = find_best_split(E, F) // 寻找能够最大化增益（或最小化不纯度）的最佳划分属性和条件
标记结点 N 为 root.test_cond
// 4. 根据划分条件递归构建子树
对于 root.test_cond 的每个可能输出值 v:
Ev = {e | root.test_cond(e) == v 并且 e 属于 E} // 获取满足条件v的子集
创建从 N 到 child 的分支，标记为 v
如果 Ev 为空:
child = createNode()
child.label = E 中最常见的类 (多数表决) // 为空子集添加默认叶结点
否则:
child = Generate_decision_tree(Ev, F - {root.test_cond.attribute}) // 递归调用，移除已用属性
将 child 作为 N 的派生结点添加到树中
返回 N
|
2. k-近邻分类算法 (k-Nearest Neighbor Classification Algorithm)
说明: k-NN是一种惰性学习算法（Lazy Learner），它不预先构建显式模型。对于一个未知测试样本，它通过计算与训练集中所有样本的距离，找出距离最近的 k 个邻居，然后根据这些邻居的类别进行多数表决（或距离加权表决）来决定测试样本的类别。
伪代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 函数 k_Nearest_Neighbor_Classify(训练集 D, 测试样本 z=(x', y'), 参数 k):
// 1. 计算测试样本 z 与训练集中每个样本的距离
对于 D 中的每个训练样本 (x_i, y_i):
计算 z 的特征向量 x' 和 x_i 之间的距离 d(x', x_i)
// 2. 找出 k 个距离最近的训练样本
将 D 中的样本按距离 d(x', x_i) 升序排序
选择距离 z 最近的 k 个训练样本，构成集合 Dz
// 3. 根据 k 个邻居的类别进行多数表决
y_prime_predicted = argmax_v (∑ (i 属于 Dz) I(v == y_i)) // I 是指示函数，v 是类别标签
// 另一种常见的表决方式是距离加权表决：
// y_prime_predicted = argmax_v (∑ (i 属于 Dz) (1/d(x', x_i)) * I(v == y_i))
返回 y_prime_predicted
|
3. 后向传播算法 (Backpropagation Algorithm for Artificial Neural Network)
说明: 后向传播是训练多层前馈神经网络的迭代算法。它通过两个主要阶段：向前传播输入以计算输出，然后向后传播误差。根据计算出的误差，算法会调整网络中的连接权重和偏置，以最小化网络的预测误差。
伪代码:
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
| 函数 Backpropagation(训练数据集 D, 学习率 l, 神经网络 Network):
// 1. 初始化权重和偏置
将 Network 中所有权重和偏置初始化为小的随机数 (例如，介于 -1.0 到 1.0 之间)
// 2. 迭代训练直到满足终止条件
当 终止条件不满足 时: // 终止条件可以是最大迭代次数、误差低于阈值等
对于 D 中的每个训练元组 X (输入) 及其真实输出 T:
// 2.1 向前传播输入 (计算各层的净输入和输出)
对于 每个输入层单元 j:
Oj = Ij // 输入单元的输出等于其输入值
对于 隐藏层和输出层每个单元 j:
净输入 Ij = ∑ (i 来自上一层) (w_ij * Oi) + θj // w_ij 是权重，Oi 是上一层单元i的输出，θj 是偏置
输出 Oj = 1 / (1 + e^(-Ij)) // 使用 Logistic 激活函数
// 2.2 后向传播误差 (从输出层开始向后计算误差)
对于 输出层每个单元 j:
Err_j = Oj * (1 - Oj) * (Tj - Oj) // Tj 是单元j的真实输出
对于 从最后一个到第一个隐藏层，对于隐藏层每个单元 j:
Err_j = Oj * (1 - Oj) * ∑ (k 来自下一较高层) (w_kj * Err_k) // w_kj 是单元j到下一层单元k的权重
// 2.3 更新权重和偏置 (根据计算出的误差调整网络参数)
对于 Network 中每个权重 w_ij (从单元 i 到单元 j):
Δw_ij = l * Err_j * Oi // 权值增量
w_ij = w_ij + Δw_ij // 权值更新
对于 Network 中每个偏置 θj:
Δθj = l * Err_j // 偏置增量
θj = θj + Δθj // 偏置更新
返回 训练后的神经网络 Network
|
4. Bagging 算法
说明: Bagging (自助聚集) 是一种集成学习（Ensemble Learning）方法。它通过有放回抽样从原始训练集生成多个自助训练集，然后在每个自助集上独立地训练一个基分类器（通常是同类型的弱学习器）。最终分类时，所有基分类器对测试样本进行投票（分类问题为多数投票，回归问题为平均），选择得票最高的类别。
伪代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 函数 Bagging_Train(原始训练集 D, 基分类器算法 A, 基分类器数量 M):
分类器集合 C = {}
对于 i 从 1 到 M:
// 1. 从 D 中有放回地随机抽样，生成与 D 容量相同的子集 D_i
// (此过程称为自助抽样)
D_i = Bootstrap_Sample(D)
// 2. 在自助抽样数据集 D_i 上训练基分类器 C_i
C_i = A.train(D_i) // 使用算法 A 在数据集 D_i 上训练分类器
将 C_i 添加到 C
返回 分类器集合 C
函数 Bagging_Classify(分类器集合 C, 测试样本 x):
类别预测计数 = 一个空字典 (用于存储每个类别的票数)
对于 C 中的每个分类器 C_i:
预测类别 p = C_i.predict(x) // 获取当前基分类器的预测结果
增加 p 在类别预测计数中的票数
返回 类别预测计数中票数最高的类别
|
5. Boosting 算法 (通用框架)
说明: Boosting 是一种迭代的集成学习方法。它为每个训练样本赋予权重，并迭代地训练一系列基分类器。每次训练时，后续的基分类器会“更关注”前一个分类器误分类的样本（通过调整样本权重实现）。最终分类时，基分类器根据其在训练中的表现（通常是其准确率的函数）进行加权投票。Adaboost 是其一个流行实现。
伪代码:
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
| 函数 Boosting_Train(训练集 D, 基分类器算法 A, 迭代次数 K):
N = D 的样本总数
初始化 D 中每个训练记录的权重 w_j = 1/N (j = 1 to N)
分类器集合 C = []
重要性权重集合 Alpha = [] // 存储每个基分类器的权重
对于 i 从 1 到 K:
// 1. 根据当前样本权重 w_j，训练基分类器 C_i
// (算法 A 在训练时会考虑样本权重)
C_i = A.train(D, w_j)
// 2. 计算分类器 C_i 的分类误差 ε_i
ε_i = ∑ (j = 1 to N) w_j * I(C_i(x_j) != y_j) // I 是指示函数，当预测错误时为 1
// 3. 计算分类器 C_i 的重要性 α_i
α_i = 0.5 * ln((1 - ε_i) / ε_i) // 示例公式，具体可能因算法而异
// 4. 更新训练样本的权重
对于 j 从 1 到 N:
如果 C_i(x_j) 误分类了样本 j:
w_j = w_j * e^(α_i)
否则 (C_i 正确分类了样本 j):
w_j = w_j * e^(-α_i)
规范化权重 w_j，使其总和为 1 (∑w_j = 1)
添加 C_i 到 C
添加 α_i 到 Alpha
返回 (分类器集合 C, 重要性权重集合 Alpha)
函数 Boosting_Classify(分类器集合 C, 重要性权重集合 Alpha, 测试样本 x):
最终预测票数 = 一个空字典 (存储每个类别的加权票数)
对于 C 中的每个分类器 C_i (对应的重要性权重 α_i):
预测类别 p = C_i.predict(x)
将 α_i 加到 p 的最终预测票数中
返回 最终预测票数中票数最高的类别
|
6. Adaboost 算法
说明: Adaboost (Adaptive Boosting) 是 Boosting 算法的一个具体且流行的实现。它通过迭代训练一系列弱分类器，在每次迭代中，会增加前一轮被错误分类样本的权重，减少被正确分类样本的权重，使得后续的弱分类器更关注“困难”的样本。最终，通过加权多数投票的方式组合所有弱分类器，其中每个弱分类器的投票权重由其在训练中的错误率决定。
伪代码:
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
| 函数 Adaboost_Train(训练集 D = {(x_j, y_j)}, 基分类器算法 A, 迭代次数 K):
N = D 的样本总数
初始化每个训练样本的权重 w_j = 1/N (j = 1 to N)
弱分类器集合 H = [] // 存储弱分类器
弱分类器重要性权重集合 Alpha = [] // 存储每个弱分类器的权重
对于 i 从 1 到 K:
// 1. 使用当前样本权重 w_j 训练弱分类器 h_i
// (这里假设算法 A 能处理带权重的样本)
h_i = A.train(D, w_j)
// 2. 计算弱分类器 h_i 的分类误差 ε_i
ε_i = ∑ (j = 1 to N) w_j * I(h_i(x_j) != y_j) // I 是指示函数，当预测错误时为 1
// 3. 检查误差，如果误差过大（大于 0.5），则视为无效学习，重新初始化权重并继续
如果 ε_i > 0.5:
w_j = 1/N (j = 1 to N) // 重置权重
继续下一次迭代 (跳过当前迭代的剩余步骤)
// 4. 计算弱分类器 h_i 的重要性权重 α_i
α_i = 0.5 * ln((1 - ε_i) / ε_i)
// 5. 更新样本权重
对于 j 从 1 到 N:
如果 h_i(x_j) != y_j: // 如果分类错误
w_j = w_j * e^(α_i)
否则: // 如果分类正确
w_j = w_j * e^(-α_i)
// 规范化权重 w_j，使其总和为 1
w_sum = ∑ (j = 1 to N) w_j
对于 j 从 1 到 N:
w_j = w_j / w_sum
添加 h_i 到 H
添加 α_i 到 Alpha
返回 (弱分类器集合 H, 弱分类器重要性权重集合 Alpha)
函数 Adaboost_Classify(H, Alpha, 测试样本 x):
最终预测投票 = {} // 存储每个类别的加权票数
对于 k 从 1 到 H.size():
预测类别 p = H[k].predict(x) // 获取第 k 个弱分类器的预测结果
将 Alpha[k] (第 k 个弱分类器的权重) 加到 最终预测投票[p] 中
返回 最终预测投票中票数最高的类别
|
7. k-means 算法
说明: k-means 是一种迭代的划分聚类算法，旨在将 n 个数据对象划分为 k 个簇。它通过最小化平方误差准则（即每个簇内数据点到其簇中心的距离之和）来优化簇的划分。算法会反复调整簇的成员关系和簇中心，直到收敛。
伪代码:
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
| 函数 k_means_Cluster(数据集 D, 簇数目 k):
// 1. 初始化：任意选择 k 个对象作为初始的簇中心 (平均值)
随机选择 D 中的 k 个点作为初始均值 (μ_1, μ_2, ..., μ_k)
重复:
// 2. 簇分类 (分配步骤)：将每个对象分配到距离最近的簇
创建 k 个空簇 C_1, C_2, ..., C_k
对于 D 中的每个对象 x_j:
找到距离 x_j 最近的簇中心 μ_i
将 x_j 分配到簇 C_i
// 3. 更新簇平均值 (更新步骤)：重新计算每个簇的平均值作为新的簇中心
所有簇中心都设置为 null
对于 每个簇 C_i (i = 1 to k):
μ_i_new = C_i 中所有对象的平均值
// 4. 检查收敛条件
如果 所有簇中心 μ_i 不再明显地变化 (例如，新旧中心距离小于阈值)
// 或 准则函数 E 不再明显地变化 (平方误差和)
// E = ∑ (i=1 to k) ∑ (x 属于 C_i) ||x - μ_i_new||^2:
跳出循环
否则:
μ_i = μ_i_new // 更新簇中心为新计算的值
返回 k 个最终簇 C_1, C_2, ..., C_k
|
8. AGNES 算法 (层次凝聚聚类)
说明: AGNES (AGglomerative NESting) 是一种自底向上的层次聚类算法。它开始时将每个数据对象视为一个单独的簇，然后迭代地合并最相似的两个簇，直到达到预定义的簇数量。簇之间的相似度通常由它们之间最近的数据点对的距离确定（即“最小距离”准则）。
伪代码:
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
| 函数 AGNES_Cluster(数据集 D, 终止簇数目 k):
// 1. 初始化：将每个对象当成一个初始簇
簇集合 Clusters = { {o} | o 属于 D } // 每个对象都是一个单例簇
重复:
// 2. 检查终止条件
如果 Clusters 中的簇数目 == k:
跳出循环
// 3. 找到当前簇集合中距离最近的两个簇
min_distance = 无穷大
closest_cluster_1 = null
closest_cluster_2 = null
对于 Clusters 中的每对不同簇 (C_a, C_b):
// 计算 C_a 和 C_b 之间的距离 (例如，使用最小距离：两簇间最近点的距离)
distance_ab = min(dist(p, q)) for p in C_a, q in C_b
如果 distance_ab < min_distance:
min_distance = distance_ab
closest_cluster_1 = C_a
closest_cluster_2 = C_b
// 4. 合并最近的两个簇
从 Clusters 中移除 closest_cluster_1 和 closest_cluster_2
将 (closest_cluster_1 U closest_cluster_2) 添加到 Clusters // 合并后的新簇
返回 最终的簇集合 Clusters
|
9. DIANA 算法 (层次分裂聚类)
说明: DIANA (Divisive ANAlysis) 是一种自顶向下的层次聚类算法。它开始时将所有对象放在一个簇中，然后迭代地将当前簇中“最不相似”（通常是直径最大或平均相异度最大的）的簇分裂成两个子簇，直到达到预定义的簇数量。分裂过程通常涉及识别簇中最“离群”的点作为新簇的种子。
伪代码:
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
| 函数 DIANA_Cluster(数据集 D, 终止簇数目 k):
// 1. 初始化：将所有对象整个当成一个初始簇
簇集合 Clusters = { D }
对于 i 从 1 到 k-1: // 需要进行 k-1 次分裂才能得到 k 个簇
// 2. 在所有当前簇中挑出具有最大直径（或平均相异度最大）的簇 C_to_split
C_to_split = Clusters 中直径最大的簇 // 或者其他“最不紧凑”的度量
// 3. 在 C_to_split 中找出与其它点平均相异度最大的一个点 p
// (此点将被作为分裂的起点，形成新的分裂组)
p = C_to_split 中平均相异度最大的点 // p 称为 splinter_group 的初始点
splinter_group = {p}
old_party = C_to_split - {p}
重复:
has_moved = 假
// 4. 将 old_party 中满足条件（更接近 splinter_group）的点移入 splinter_group
对于 old_party 中的每个点 q:
dist_to_splinter = q 到 splinter_group 中点的最小距离
dist_to_old_party = q 到 old_party 中点的最小距离
如果 dist_to_splinter <= dist_to_old_party:
将 q 从 old_party 移到 splinter_group
has_moved = 真
直到 not has_moved // 没有点再被移动
// 5. 更新簇集合：移除被分裂的簇，加入新形成的两个子簇
从 Clusters 中移除 C_to_split
将 splinter_group 和 old_party 添加到 Clusters
返回 最终的簇集合 Clusters
|
10. DBSCAN 算法
说明: DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一种基于密度的聚类算法。它能够发现任意形状的簇，并且对噪声数据具有鲁棒性。DBSCAN 通过定义核心点、边界点和噪声点的概念，从核心点开始，将所有密度可达的点连接成簇。
伪代码 (根据概念描述综合，非直接源于PPT中的伪代码):
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
| 函数 DBSCAN_Cluster(数据集 D, 邻域半径 Eps, 最小点数 MinPts):
簇标签 C = 一个映射，存储每个点所属的簇ID，初始为 未访问 (UNVISITED)
簇ID = 0
对于 D 中的每个点 P:
如果 C[P] != UNVISITED:
继续下一个点 (P 已经被处理过)
C[P] = VISITED // 标记为已访问
Neighbors = 获取 P 的 Eps-邻域内的所有点 // 包含 P 自身
如果 Neighbors.size() < MinPts:
C[P] = NOISE // 标记为噪声点
否则:
簇ID = 簇ID + 1 // 发现一个新的簇
扩展簇(P, Neighbors, 簇ID, Eps, MinPts, D, C)
返回 簇标签 C (每个点所属的簇ID或噪声标记)
函数 扩展簇(P_core, Neighbors, current_cluster_ID, Eps, MinPts, D, C):
C[P_core] = current_cluster_ID // 将核心点 P_core 分配到当前簇
队列 Q = new Queue()
将 Neighbors 中的所有点添加到 Q
当 Q 不为空时:
CurrentP = Q.dequeue() // 从队列中取出一个点
如果 C[CurrentP] == NOISE:
C[CurrentP] = current_cluster_ID // 将噪声点重新分配为边界点
如果 C[CurrentP] == UNVISITED: // 如果点未被访问过
C[CurrentP] = VISITED // 标记为已访问
CurrentP_Neighbors = 获取 CurrentP 的 Eps-邻域内的所有点
如果 CurrentP_Neighbors.size() >= MinPts: // CurrentP 是新的核心点
对于 CurrentP_Neighbors 中的每个点 N_neighbor:
如果 C[N_neighbor] == UNVISITED 或者 C[N_neighbor] == NOISE:
Q.enqueue(N_neighbor) // 将未访问或噪声点加入队列，以便后续处理
C[CurrentP] = current_cluster_ID // 将 CurrentP 分配到当前簇
|
11. Apriori 算法 (频繁项集产生和规则产生)
说明: Apriori 算法是经典的关联规则挖掘算法，分为两个主要阶段：
- 频繁项集产生: 发现所有满足最小支持度阈值 (minsup) 的项集。它利用“先验原理”（任何非频繁项集的超集一定也是非频繁的）来有效剪枝搜索空间。
- 规则产生: 从所有发现的频繁项集中，提取满足最小置信度阈值 (minconf) 的关联规则。
伪代码:
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
| 函数 Apriori_Frequent_Itemset_Generation(事务数据集 T, 最小支持度 minsup):
// 1. 发现频繁 1-项集 (F1)
C1 = D 中所有唯一的项 (1-项集) 组成的集合
F1 = {c 属于 C1 | c.support_count / |T| >= minsup} // 计算支持度并筛选
频繁项集总集合 Frequent_Itemsets = F1
k = 1
重复:
k = k + 1
// 2. 候选项集产生 (Apriori-gen): 从 F(k-1) 生成 Ck
// (此步骤会合并 F(k-1) 中的项集，并进行剪枝：如果一个 k-项集的任何 k-1 子集不在 F(k-1) 中，则该 k-项集不是频繁的)
Ck = Apriori_candidate_generation(Fk-1)
// 3. 计算候选项集 Ck 的支持度计数
对于 T 中的每个事务 t:
对于 Ck 中的每个候选项集 c:
如果 c 包含在 t 中:
c.support_count++
// 4. 从 Ck 中筛选出频繁项集 Fk
Fk = {c 属于 Ck | c.support_count / |T| >= minsup}
将 Fk 中的所有项集添加到 Frequent_Itemsets
直到 Fk 为空 (没有新的频繁 k-项集产生)
返回 Frequent_Itemsets // 所有频繁项集的集合
函数 Apriori_Rule_Generation(频繁项集 Frequent_Itemsets, 最小置信度 minconf):
强关联规则集合 Rules = {}
对于 Frequent_Itemsets 中的每个频繁项集 itemset (其长度 >= 2):
// 对于 itemset 的每个非空真子集 antecedent:
// 后件 consequent = itemset - antecedent
// 剪枝原则：如果规则 X -> Y 的置信度不满足，那么任何 X' 包含 X 的规则 X' -> Y 的置信度也不会满足。
// （这允许我们从后件最少的情况开始生成规则，并根据置信度进行剪枝）
// 此处伪代码简化为直接遍历所有可能的 Antecedent 和 Consequent 组合
对于 itemset 的每个非空真子集 antecedent:
consequent = itemset - antecedent
如果 consequent 为空:
继续下一个子集 (后件不能是空集)
confidence = itemset.support_count / antecedent.support_count
如果 confidence >= minconf:
将规则 (antecedent -> consequent) 添加到 Rules
返回 Rules
|