【机器学习】机器学习中用到的高等数学知识-6. 组合数学 (Combinatorics)

embedded/2024/11/22 14:15:28/

组合计数：用于计算特征选择和模型复杂度。

组合数学 (Combinatorics)

组合数学是研究有限或可数对象的组合、排列及计数规律的数学分支，在计算特征选择、模型复杂度和优化算法中有着广泛应用。以下详细介绍组合计数的概念、公式、推导过程以及实际应用。

1. 组合计数的基本概念

排列 (Permutation)

排列是指从 n 个不同元素中，按照一定顺序选出 r 个元素的排列方式。

公式：

$P(n, r) = \frac{n!}{(n-r)!}$

推导：

从 n 个元素中选第一个有 n 种选择。
第二个有 n−1 种选择，依此类推，总共有 $n \cdot (n-1) \cdot \ldots \cdot (n-r+1)$ 种选择，等价于公式 $\frac{n!}{(n-r)!}$ 。

组合 (Combination)

组合是指从 n 个不同元素中，不考虑顺序，选出 r 个元素的方式。

公式：

$C(n, r) = \binom{n}{r} = \frac{n!}{r! \cdot (n-r)!}$

推导：

从 n 个元素中选出 r 个元素的排列数为 P(n, r)。
但每个组合包含 r! 种不同排列，所以组合数为：

$C(n, r) = \frac{P(n, r)}{r!} = \frac{n!}{r! \cdot (n-r)!}$

2. 实际应用

(1) 特征选择

在机器学习中，假设有 n 个特征，从中选择 r 个用于模型训练。可以通过组合计算出可能的特征组合数：

$C(n, r) = \frac{n!}{r!(n-r)!}$

(2) 模型复杂度

当训练神经网络时，若有 n 层，每层有 k 个神经元，则全连接层的可能连接数为：

$C(k, 2) \times \text{number of layers}$

(3) 数据采样

在统计中，若有 n 个样本，从中随机选择 r 个进行实验或交叉验证，组合计数直接给出可能的采样方式数。

3. Python实现

以下代码演示了排列和组合的计算，并绘制相关的直方图进行可视化。

import math
import matplotlib.pyplot as plt
import numpy as np# 计算排列数
def permutation(n, r):return math.factorial(n) // math.factorial(n - r)# 计算组合数
def combination(n, r):return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))# 示例参数
n_values = range(1, 11)  # n 从 1 到 10
r = 3  # 固定 r 为 3# 计算排列和组合
perms = [permutation(n, r) for n in n_values if n >= r]
combs = [combination(n, r) for n in n_values if n >= r]# 绘制图形
plt.figure(figsize=(10, 6))
plt.bar(n_values[:len(perms)], perms, alpha=0.7, label="Permutation P(n, r)", color="blue")
plt.bar(n_values[:len(combs)], combs, alpha=0.7, label="Combination C(n, r)", color="orange")
plt.xlabel("n (number of elements)")
plt.ylabel("Count")
plt.title("Permutation and Combination Counts")
plt.legend()
plt.grid()
plt.show()