Zhang XiJun

BLOGS

发表于 更新于 分类于 ，

正文

下面我将为你详细解释KKT（Karush-Kuhn-Tucker）条件。KKT条件是优化理论中用于求解带约束非线性规划问题的一组必要条件，广泛应用于支持向量机（SVM）等机器学习算法中。我会使用内联数学公式（如 ）来展示相关表达式。

1. 优化问题的一般形式

我们考虑一个带有约束的优化问题，数学形式如下：

  • 目标：
  • 不等式约束：，其中
  • 等式约束：，其中

这里：

  • 是目标函数，通常是我们希望最小化的函数。
  • 表示 个不等式约束。
  • 表示 个等式约束。

KKT条件的目标是找到满足这些约束的局部最优解 。

2. 拉格朗日函数

为了引入KKT条件，我们首先定义拉格朗日函数：

其中：

  • 是与不等式约束 对应的拉格朗日乘子。
  • 是与等式约束 对应的拉格朗日乘子。

拉格朗日函数将目标函数和约束条件结合在一起，通过引入乘子 和 来平衡约束对优化的影响。

3. KKT条件的组成部分

KKT条件由以下四个部分组成，只有当某些正则性条件（如Slater条件）满足时，局部最优解 才会同时满足这些条件。以下是具体的KKT条件：

3.1 梯度条件（Stationarity）

拉格朗日函数对 的梯度必须为零，即：

这意味着在最优解处，目标函数的梯度可以通过约束函数梯度的线性组合来表示。

3.2 原始可行性（Primal Feasibility）

解 必须满足原始问题的所有约束：

  • 不等式约束：，其中
  • 等式约束：，其中

这确保了解仍在问题的可行域内。

3.3 对偶可行性（Dual Feasibility）

对于不等式约束对应的拉格朗日乘子，必须满足：

这表明不等式约束的乘子非负，反映了约束对优化方向的影响。

3.4 互补松弛条件（Complementary Slackness）

对于每个不等式约束，乘子与约束函数的乘积必须为零：

这意味着：

  • 如果某个约束不“紧”（即 ），则对应的乘子 。
  • 如果 ，则该约束必须是“紧”的（即 ）。

4. KKT条件的意义

  • 梯度条件：表明最优解处目标函数的改变方向被约束完全平衡。
  • 原始可行性：确保解满足所有约束条件。
  • 对偶可行性：限制拉格朗日乘子的符号，保证优化方向的合理性。
  • 互补松弛条件：揭示哪些约束在最优解处起作用（紧约束），哪些不起作用。

5. KKT条件在SVM中的应用示例

KKT条件在支持向量机（SVM）中尤为重要。SVM的原始优化问题为：

  • 目标：
  • 约束：，其中

将其改写为标准形式的不等式约束：。

拉格朗日函数为：

应用KKT条件：

  1. 梯度条件：
    • 对 ：
    • 对 ：
  2. 原始可行性：
  3. 对偶可行性：
  4. 互补松弛条件：

这些条件帮助我们识别支持向量（ 的点）并求解最优的 和 。

6. 总结

KKT条件是求解带约束优化问题的核心工具，它通过梯度条件、原始可行性、对偶可行性和互补松弛条件，确保了解既是最优的，又满足所有约束。在机器学习中，KKT条件为SVM等算法提供了理论支持，是理解和实现这些模型的关键。

作业

关于支持向量机，推导目标函数的原始问题转换为对偶问题的过程和条件。（使用拉格朗日乘子法）

IMG_20250416_164811

下面我们将推导支持向量机（SVM）中目标函数从原始问题转换为对偶问题的过程和条件，使用拉格朗日乘子法。我们将一步步展开，确保推导清晰且完整。

1. 原始问题

支持向量机（SVM）的目标是找到一个超平面，能够最大化到最近数据点的间隔。对于线性可分的情况，原始优化问题可以定义为：

  • 目标函数：

  • 约束条件：

其中：

  • 是超平面的法向量；
  • 是超平面的截距；
  • 是训练样本， 是对应的类别标签；
  • 表示法向量的平方范数，目标是最小化它以最大化间隔；
  • 约束条件确保所有样本点被正确分类，并且到超平面的归一化距离至少为 1。

2. 引入拉格朗日乘子法

由于这是一个带不等式约束的优化问题，我们使用拉格朗日乘子法将其转换为无约束形式。引入拉格朗日乘子 ，其中 ，构造拉格朗日函数：

  • 第一项 是原始目标函数；
  • 第二项 将约束条件引入，由于是 不等式，乘子 。

我们的目标是通过拉格朗日函数，将原始问题转换为对偶问题。

3. 转换为对偶问题

对偶问题的核心思想是：先对 和 求拉格朗日函数的极小值，然后对 求极大值。即：

3.1 对 和 求偏导

为了找到 关于 和 的极小值，分别求偏导并令其为零：

  • 对 求偏导：

    解得：

  • 对 求偏导：

    解得：

这两个结果是后续推导的关键。

3.2 代入拉格朗日函数

将 代入拉格朗日函数，并利用 简化：

  • 计算第一项：

  • 计算第二项中的内积部分：

    所以：

  • 考虑 项：

代入后，拉格朗日函数变为：

化简：

3.3 对偶优化问题

于是，对偶问题是：

  • 约束条件：

为了与标准优化形式一致，常将其写为最小化问题：

  • 约束条件不变：

4. 转换的条件

原始问题与对偶问题之间的关系由强对偶性保证。在SVM中：

  • 目标函数 是凸函数（二次函数）；
  • 约束条件 是线性不等式；
  • 对于线性可分数据，Slater条件满足（存在可行解使约束严格成立）。

因此，强对偶性成立，原始问题的最优解可以通过对偶问题求解得到。

此外：

  • 最优的 通过对偶问题求解；
  • ；
  • 对于支持向量（ 的样本），，可据此解出 。

5. 总结

  • 原始问题：

    受约束：

  • 对偶问题：

    受约束：，

  • 转换条件：
    通过拉格朗日乘子法，基于凸优化和强对偶性完成转换。对偶形式不仅便于求解，还为引入核函数奠定了基础。

以上就是SVM目标函数从原始问题到对偶问题的推导过程和条件。

2.已知训练数据集中正例点x1=(2,3)，x2=(3,3)，x3=(3,2)，负例点x4=(1,2)， x5=(2,1)，x6=(3,1)，训练线性SVM分类器。求最大间隔分类超平面和分类决策函数，并画出分类超平面、间隔边界以及支持向量。

IMG_20250416_164804

发表于 更新于 分类于 ，

位运算

在这张图片中，表格列出了 x 和 y 的十六进制值，并且要求用 C 语言中的位运算符对它们进行操作。接下来，我将对每个表达式进行详细的计算和解释。

在表格中，要求使用 C 语言中的不同位运算符来计算 x 和 y 之间的结果。位运算符包括：

  1. &（位与）
  2. |（位或）
  3. ^（位异或）
  4. ~（位取反）
  5. <<（左移）
  6. >>（右移）
  7. !（逻辑非）

计算步骤：

  1. 位与运算 x & y： 位与运算会比较 x 和 y 的每一位，只有当对应位都为 1 时，结果才为 1，否则为 0。
  2. 位或运算 x | y： 位或运算会比较 x 和 y 的每一位，只要对应位有一个为 1，结果就为 1。
  3. 位异或运算 x ^ y： 位异或运算会比较 x 和 y 的每一位，当两者相同时，结果为 0；当两者不同时，结果为 1。
  4. 位取反运算 ~x 和 ~y： 位取反运算会将 x 或 y 的每一位都反转，0 变 1，1 变 0。
  5. 左移运算 x << y： 左移运算会将 x 的二进制位向左移动 y 位，并在右边补 0。
  6. 右移运算 x >> y： 右移运算会将 x 的二进制位向右移动 y 位，符号位（对于负数来说是 1）保持不变。
  7. 逻辑非运算 !x： 逻辑非运算对 x 进行布尔值判断，如果 x 为 0，则结果为 1，否则为 0。

十六进制（Hexadecimal, H）和二进制（Binary, b）之间的直接关系

核心原理: 每一个十六进制数字正好对应 4 个二进制位。这是因为 16=24。

我们可以将十六进制数 8080 108B H 中的每一位数字，分别转换为它对应的4位二进制数：

  1. 8 H = 1000 b
  2. 0 H = 0000 b
  3. 8 H = 1000 b
  4. 0 H = 0000 b
  5. 1 H = 0001 b
  6. 0 H = 0000 b
  7. 8 H = 1000 b
  8. B H (B 代表十进制的 11) = 1011 b

组合: 现在，按照原始十六进制数的顺序，把这些4位的二进制数组合起来：

1000 (来自8) + 0000 (来自0) + 1000 (来自8) + 0000 (来自0) + 0001 (来自1) + 0000 (来自0) + 1000 (来自8) + 1011 (来自B)

结果: 将它们连接在一起就得到：

1000 0000 1000 0000 0001 0000 1000 1011 b

所以，8080 108B H 等于 1000 0000 1000 0000 0001 0000 1000 1011 b 是因为每个十六进制位都可以独立地、直接地转换为一个4位的二进制表示，然后按顺序拼接起来。

指令决定了如何解释寄存器中的二进制位串

好的，我们来详细解释一下为什么在不同的指令下，寄存器 R1 和 R2 的内容 0000 108B H 和 8080 108B H 会对应不同的真值。核心原因在于，指令决定了如何解释寄存器中的二进制位串。

（1）无符号数加法指令 (Unsigned Addition)

  • 解释规则: 当执行无符号数指令时，计算机会将寄存器中的 所有32位 都视为表示数值大小（magnitude）的部分，没有单独的符号位。数值就是这个32位二进制数直接转换成的十进制（或十六进制）值。

（2）带符号整数乘法指令 (Signed Integer Multiplication)

  • 解释规则:

    当执行带符号整数指令时，计算机会使用

    补码 (Two’s Complement)

    来表示整数。

    • 最高位 (MSB, Most Significant Bit) 是符号位：0 代表正数或零，1 代表负数。
    • 正数: 其补码、原码、反码相同，数值就是除去符号位后的二进制值。
    • 负数: 其真值需要通过补码转换回原码来确定其绝对值。转换方法是：对补码再次求补（符号位不变，数值位按位取反，末位加1；或者全部位按位取反，末位加1）得到原码的绝对值。

（3）单精度浮点数减法指令 (Single-Precision Floating-Point Subtraction)

  • 解释规则:

    当执行浮点数指令时，计算机会按照

    IEEE 754 单精度 (32位)

    标准来解释寄存器中的位。格式如下：

    • 符号位 (Sign, S): 1位 (第31位)。0 为正，1 为负。
    • 阶码 (Exponent, E): 8位 (第30-23位)。存储的是 e + bias，其中 e 是实际指数，bias (偏移量) 对于单精度是 127。
    • 尾数 (Mantissa/Fraction, F): 23位 (第22-0位)。表示小数部分。对于规格化数，实际尾数是 1.F（有一个隐藏的1）。
    • 数值公式 (规格化): Value=(−1)S×(1.F)2×2(E−127)
    • 特殊情况: 需要注意 E=0 (表示0或非规格化数) 和 E=255 (表示无穷大或NaN)。

补码的基本规则

在开始计算之前，我们先了解补码的基本规则：

  1. 符号位：

    • 补码的最高位（最左边的位）是符号位。
    • 符号位为 0 表示正数或零，符号位为 1 表示负数。

  2. 正数的补码：

    • 如果符号位是 0，补码与原码相同，直接按照二进制数值解释即可。

  3. 负数的补码：

    • 如果符号位是 1，表示负数。要得到原码（即实际的数值），需要对数值部分取反（0 变 1，1 变 0），然后加 1。
    • 最后在结果前加上负号。

  4. 小数部分的处理：

    • 如果补码表示包含小数点，符号位在小数点左边，数值部分在小数点右边，按照二进制小数计算。

是的，在 C 语言中，0U 后面的 U 确实表示无符号的意思。具体来说：

  • 0 本身：这是一个整数常量，默认情况下是有符号整数类型（signed int）。
  • 0U 的含义：当在 0 后面加上 U 后缀时，它就变成了一个无符号整数常量（unsigned int）。U 后缀明确指定了这个数字是无符号类型。

C 语言中整数常量的后缀规则

在 C 语言中，可以通过后缀来指定整数常量的类型：

  • 无后缀：表示默认的有符号整数（int）。
  • U 或 u：表示无符号整数（unsigned int）。
  • L 或 l：表示长整型（long int）。
  • UL 或 ul：表示无符号长整型（unsigned long int）。

举例说明

  • 0：有符号整数，值是 0。
  • 0U：无符号整数，值仍然是 0，但它的类型是 unsigned int。

为什么这很重要？

无符号类型和有符号类型的区别在某些情况下会影响程序的行为，比如比较运算：

  • 如果比较两个无符号整数，或者两个有符号整数，直接按数值比较即可。
  • 如果一个是有符号整数，另一个是无符号整数，C 语言会将有符号整数转换为无符号整数后再比较。这可能导致意外结果，例如负数在转换为无符号整数时变成一个很大的正数。

总之，U 后缀的作用就是告诉编译器，这个整数常量是无符号的。所以你的理解是对的，后面带 U 就是无符号的意思！

让我们来分析这个问题：为什么在表达式 (unsigned) -1 > -2 中，-1 被转换为无符号整数，而 -2 也被按无符号数处理。

1. 表达式 (unsigned) -1 的含义

  • (unsigned) 是一个强制类型转换，表示将后面的值 -1 从有符号整数（int）转换为无符号整数（unsigned int）。
  • 在计算机中，整数通常以补码形式存储。以 32 位为例：
    • 有符号整数 -1 的补码是 1111...1111（32 位全 1）。
    • 当将其强制转换为无符号整数时，这串二进制位被重新解释为一个正数。
    • 1111...1111 作为无符号整数的值是 (2^{32} - 1 = 4294967295)。
  • 所以，(unsigned) -1 的结果是 4294967295。

2. 比较中的 -2 为什么按无符号数处理

  • 在表达式 (unsigned) -1 > -2 中，-2 默认是一个有符号整数（int），其补码表示为 1111...1110（32 位中最后一位是 0）。
  • 当一个无符号整数（(unsigned) -1）与一个有符号整数（-2）进行比较时，C 语言会执行隐式类型转换，以确保两个操作数的类型一致。
  • 根据 C 语言的规则：
    • 如果一个操作数是无符号整数，另一个是有符号整数，有符号整数会被转换为无符号整数。
  • 因此，-2 会被隐式转换为无符号整数：
    • 1111...1110 作为无符号整数的值是 (2^{32} - 2 = 4294967294)。

3. 比较的过程

  • 现在，表达式 (unsigned) -1 > -2 变成了：
    • (unsigned) -1 = 4294967295（无符号整数）。
    • -2 被转换为 4294967294（无符号整数）。
  • 比较 4294967295 > 4294967294，显然成立，结果为真（1）。

4. 为什么 -2 被按无符号数处理

  • -2 被按无符号数处理的原因在于 C 语言的类型转换规则：
    • 当有符号整数与无符号整数进行运算或比较时，有符号整数会被自动转换为无符号整数。
    • 这种转换基于补码的二进制表示，直接将补码重新解释为无符号值，而不改变位模式。
  • 在这个例子中：
    • (unsigned) -1 强制指定了无符号类型。
    • -2 由于与无符号数比较，被隐式转换成了无符号数。

5. 总结

  • (unsigned) -1 将 -1 显式转换为无符号整数，结果是 4294967295。
  • -2 在比较中被隐式转换为无符号整数，结果是 4294967294。
  • 这种行为是 C 语言类型转换规则的结果：为了保证比较时类型一致，-2 被按无符号数处理。

这种机制虽然确保了类型一致性，但在处理负数时可能导致意外结果，因此在使用无符号类型时需要特别注意。希望这个解释清晰地回答了你的问题！

发表于 更新于 分类于 ，

上机实验11：核化分类器判定西瓜好坏

1
2
3
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
1
2
data = pd.read_csv("work/西瓜数据集3.0α.txt")
data
1
2
3
4
5
6
7
8
9
yes = data[data['Good melon'].isin(['是'])]
no = data[data['Good melon'].isin(['否'])]
fig, ax = plt.subplots(figsize=(12, 8))
ax.scatter(yes['Density'], yes['Sugar content'], marker='o', c='b', label='Yes')
ax.scatter(no['Density'], no['Sugar content'], marker='x', c='r', label='No')
ax.legend()
ax.set_xlabel('Density')
ax.set_ylabel('Sugar content')
plt.show() # 可以发现线性不可分

output_3_0

任务1：SVM分类器判定西瓜好坏

在SVM分类器中，使用线性核与高斯核进行比较。

1
2
3
4
5
from sklearn import svm

# 使用线性核与高斯核进行比较
linear_svc = svm.SVC(kernel='linear')  # 线性核
rbf_svc = svm.SVC(kernel='rbf')        # 高斯核（RBF）
1
2
3
temp = {'是': 1, '否': -1}
X = np.array(data.iloc[:, :2])
y = np.array(data.iloc[:, 2].replace(temp))[None].T
1
2
3
4
linear_svc.fit(X, y)
linear_svc.score(X,y)
# 查看支持向量
linear_svc.support_vectors_
/opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages/sklearn/utils/validation.py:760: DataConversionWarning: A column-vector y was passed when a 1d array was expected. Please change the shape of y to (n_samples, ), for example using ravel().
  y = column_or_1d(y, warn=True)





array([[0.666, 0.091],
       [0.243, 0.267],
       [0.343, 0.099],
       [0.639, 0.161],
       [0.657, 0.198],
       [0.36 , 0.37 ],
       [0.593, 0.042],
       [0.719, 0.103],
       [0.697, 0.46 ],
       [0.774, 0.376],
       [0.634, 0.264],
       [0.608, 0.318],
       [0.556, 0.215],
       [0.403, 0.237],
       [0.481, 0.149],
       [0.437, 0.211]])

1
2
3
4
rbf_svc.fit(X, y)
rbf_svc.score(X,y)
# 查看支持向量
rbf_svc.support_vectors_
/opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages/sklearn/utils/validation.py:760: DataConversionWarning: A column-vector y was passed when a 1d array was expected. Please change the shape of y to (n_samples, ), for example using ravel().
  y = column_or_1d(y, warn=True)

array([[0.666, 0.091],
       [0.243, 0.267],
       [0.245, 0.057],
       [0.343, 0.099],
       [0.639, 0.161],
       [0.657, 0.198],
       [0.36 , 0.37 ],
       [0.593, 0.042],
       [0.719, 0.103],
       [0.697, 0.46 ],
       [0.774, 0.376],
       [0.634, 0.264],
       [0.608, 0.318],
       [0.556, 0.215],
       [0.403, 0.237],
       [0.481, 0.149],
       [0.437, 0.211]])

任务2：Kernel Logistic Regression 判定西瓜好坏

将原始的Logistic Regression 进行核化，使用不同的核函数进行比较。

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
126
127
128
129
130

import matplotlib.colors as colors
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd


class LogisticRegression:
    kern_param = 0
    X = np.array([])
    a = np.array([])
    kernel = None

    def __init__(self, kernel='poly', kern_param=None):
        if kernel == 'poly':
            self.kernel = self.__linear__
            if kern_param:
                self.kern_param = kern_param
            else:
                self.kern_param = 1
        elif kernel == 'gaussian':
            self.kernel = self.__gaussian__
            if kern_param:
                self.kern_param = kern_param
            else:
                self.kern_param = 0.1
        elif kernel == 'laplace':
            self.kernel = self.__laplace__
            if kern_param:
                self.kern_param = kern_param
            else:
                self.kern_param = 0.1

    def fit(self, X, y, max_rate=100, min_rate=0.001, gd_step=10, epsilon=0.0001):
        m = len(X)
        self.X = np.vstack([X.T, np.ones(m)]).T
        # Construct kernel matrix
        K =self.kernel(self.X, self.X, self.kern_param)  # 填空1：计算核矩阵
        # Gradient descent
        self.a = np.zeros([m])
        prev_cost = 0
        next_cost = self.__cost__(K, y, self.a)
        while np.fabs(prev_cost-next_cost) > epsilon:
            neg_grad = -self.__gradient__(K, y, self.a)
            best_rate = rate = max_rate
            min_cost = self.__cost__(K, y, self.a)
            while rate >= min_rate:
                cost = self.__cost__(K, y, self.a+neg_grad*rate)
                if cost < min_cost:
                    min_cost = cost
                    best_rate = rate
                rate /= gd_step
            self.a += neg_grad * best_rate
            prev_cost = next_cost
            next_cost = min_cost

    def predict(self, X):
        # 1. 添加偏置项（与训练数据处理一致）
        X = np.vstack([X.T, np.ones(len(X))]).T  # 形状变为 (n_samples, n_features + 1)
        
        # 2. 计算核矩阵（训练数据与测试数据之间的核函数值）
        K = self.kernel(self.X, X, self.kern_param)  # 形状：(训练样本数, 测试样本数)
        
        # 3. 计算预测得分（关键修正：移除 self.Y 的乘法）
        pred = np.dot(self.a, K) 
        
        # 4. Sigmoid转换为概率并二值化
        prob = self.__sigmoid__(pred)
        return (prob >= 0.5).astype(int)

    # Kernels
    @staticmethod
    def __linear__(a, b, parameter):
        return np.dot(a, np.transpose(b))

    @staticmethod
    def __gaussian__(a, b, kern_param):
        mat = np.zeros([len(a), len(b)])
        for i in range(0, len(a)):
            for j in range(0, len(b)):
                mat[i][j] = np.exp(-np.sum(np.square(np.subtract(a[i], b[j]))) / (2 * kern_param * kern_param))
        return mat

    @staticmethod
    def __laplace__(a, b, kern_param):
        mat = np.zeros([len(a), len(b)])
        for i in range(0, len(a)):
            for j in range(0, len(b)):
                mat[i][j] = np.exp(-np.linalg.norm(np.subtract(a[i], b[j])) / kern_param)
        return mat

    @staticmethod
    def __sigmoid__(X):
        return np.exp(X) / (1 + np.exp(X))

    @staticmethod
    def __cost__(K, y, a):
        return -np.dot(y, np.dot(a, K)) + np.sum(np.log(1 + np.exp(np.dot(a, K))))

    @classmethod
    def __gradient__(cls, K, y, a):
        return -np.dot(K, y - cls.__sigmoid__(np.dot(a, K)))


# Read data
data = pd.read_csv("work/西瓜数据集3.0α.txt")
X = np.array(data[['Density', 'Sugar content']])
y = np.array(data['Good melon']) == '是'

# Kernels
kernels = ['poly', 'gaussian', 'laplace']
titles = ['linear kernel', 'gaussian kernel, σ=0.1', 'laplace kernel, σ=0.1']

for i in range(0, len(kernels)):
    # Training
    # 填空3：实例化并训练模型
    model = LogisticRegression(kernel=kernels[i])
    model.fit(X, y)
    
    # Plot
    cmap = colors.LinearSegmentedColormap.from_list('watermelon', ['red', 'green'])
    xx, yy = np.meshgrid(np.arange(0.2, 0.8, 0.01), np.arange(0.0, 0.5, 0.01))
    Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    plt.contourf(xx, yy, Z, cmap=cmap, alpha=0.3, antialiased=True)
    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap)
    plt.xlabel('Density')
    plt.ylabel('Sugar content')
    plt.title(titles[i])
    plt.show()
/opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages/ipykernel_launcher.py:97: RuntimeWarning: overflow encountered in exp

output_10_1

output_10_2

output_10_3

1. 线性核（Linear Kernel）

  • 数学形式：
    [
    K(x_i, x_j) = x_i^T x_j + c \quad (c \text{为可选常数})
    ]
  • 特点：
    • 直接计算特征向量的内积，不进行非线性映射。
    • 决策边界为线性超平面，计算效率高。
  • 适用场景：
    • 数据线性可分（如两类可通过一条直线/平面分开）。
    • 特征维度较高时（避免核方法的计算开销）。
  • 西瓜数据集表现：
    • 生成直线决策边界，可能误分类非线性分布的样本。

2. 高斯核（Gaussian/RBF Kernel）

  • 数学形式：
    [
    K(x_i, x_j) = \exp\left(-\gamma |x_i - x_j|^2\right) \quad (\gamma > 0)
    ]
  • 特点：
    • 基于样本间的欧氏距离（L2距离），隐式映射到无限维空间。
    • 参数 γ 控制影响范围：γ 越大，局部性越强（对邻近点更敏感）。
  • 适用场景：
    • 数据非线性可分（如环形分布、复杂流形）。
    • 特征维度较低或中等时效果最佳。
  • 西瓜数据集表现：
    • 生成平滑的非线性边界，能捕捉密度与含糖量的复杂交互关系。

3. 拉普拉斯核（Laplace Kernel）

  • 数学形式：
    [
    K(x_i, x_j) = \exp\left(-\gamma |x_i - x_j|_1\right) \quad (\gamma > 0)
    ]
  • 特点：
    • 基于曼哈顿距离（L1距离），对异常值鲁棒性更强。
    • 隐式映射到无限维空间，但形状更尖锐（适合非光滑边界）。
  • 适用场景：
    • 数据分布不规则或存在离群点。
    • 特征具有稀疏性（如文本分类）。
  • 西瓜数据集表现：
    • 生成尖锐的非线性边界，可能更好地处理边缘样本。

以下是欧氏距离（Euclidean Distance）与曼哈顿距离（Manhattan Distance）的详细对比：

1. 数学定义

距离类型 公式 几何意义
欧氏距离 ( \ x - y\ 2 = \sqrt{\sum{i=1}^n (x_i - y_i)^2} ) 两点之间的直线距离
曼哈顿距离 ( \ x - y\ 1 = \sum{i=1}^n x_i - y_i ) 两点在网格路径上的行走距离

5. 选择建议

  • 优先欧氏距离：
    数据分布连续、特征维度较低、需要捕捉局部相似性时（如图像分类）。
  • 优先曼哈顿距离：
    数据稀疏（如文本）、存在噪声或异常值、特征维度较高时（如推荐系统）。

示例对比

假设两点 ( A(1, 1) ) 和 ( B(4, 5) )：

  • 欧氏距离：
    [
    \sqrt{(4-1)^2 + (5-1)^2} = 5
    ]
  • 曼哈顿距离：
    [
    |4-1| + |5-1| = 3 + 4 = 7
    ]

总结

  • 欧氏距离：强调“直线最短”，适合低维连续数据。
  • 曼哈顿距离：强调“网格路径”，适合高维稀疏数据。
  • 在核函数中的体现：
    • 高斯核通过欧氏距离捕捉平滑边界，拉普拉斯核通过曼哈顿距离增强鲁棒性。

发表于 更新于 分类于 ，

上机实验9：神经网络

任务1：神经元模型

  • 给定数据集X和y
  • 请补全以下代码以实现一个简单的神经元模型（即不包含隐层），并计算模型的参数向量w_vec

待补全代码

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
import numpy as np
import pandas as pd
# 输入X和y
X = np.array([ [0,0,1],
[1,1,1],
[1,0,1],
[0,1,1]])

y = np.array([[0,1,1,0]]).T

# 请在下方作答 #
# Sigmoid激活函数以及其导数
def sigmoid(x, derivative = False):
    # 计算sigmoid的输出
    sigmoid_value =1 / (1 + np.exp(-x))
    if derivative == False:     
        return sigmoid_value
    
    elif derivative == True:
        # 计算sigmoid的导数
        return sigmoid_value * (1 - sigmoid_value)

# 迭代次数
iter_num  = 1000
eta = 0.1

# 初始化权重向量w
num, dim = X.shape
w_vec = np.ones((dim, 1))

for iter in range(iter_num):
    
    ## X通过权重向量w_vec，实现线性加和，结果为z1
    z_1 =  X.dot(w_vec)
    
    # 经过激活函数Sigmoid，获得输出a_1
    a_1 = sigmoid(z_1)
      
    # 模型输出a_1与真实值的误差
    error = a_1 - y
    
    # 权重更新
    w_vec_delta = X.T.dot(error * sigmoid(z_1, derivative=True))
    w_vec = w_vec + eta*w_vec_delta  

print (w_vec)
[[0.94321144]
 [1.83125284]
 [4.71149329]]

任务2： 感知机

1．感知机是根据输入实例的特征向量$x$对其进行二类分类的线性分类模型：

感知机模型对应于输入空间（特征空间）中的分离超平面$w \cdot x+b=0$。

2．感知机学习的策略是极小化损失函数：

损失函数对应于误分类点到分离超平面的总距离。

3．感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。算法简单且易于实现。原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数。在这个过程中一次随机选取一个误分类点使其梯度下降。

4．当训练数据集线性可分时，感知机学习算法是收敛的。感知机算法在训练数据集上的误分类次数$k$满足不等式：

当训练数据集线性可分时，感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。

  1. 随机梯度下降算法 Stochastic Gradient Descent：

随机抽取一个误分类点使其梯度下降。

$w = w + \eta y{i}x{i}$

$b = b + \eta y_{i}$

当实例点被误分类，即位于分离超平面的错误侧，则调整$w$, $b$的值，使分离超平面向该无分类点的一侧移动，直至误分类点被正确分类。

使用iris数据集中两个类别的数据和[sepal length，sepal width]作为特征，进行感知机分类。

  1. 自定义感知机模型，实现iris数据分类；
  2. 调用sklearn中Perceptron函数来分类；
  3. 验证感知机为什么不能表示异或（选做）。

1. 自定义感知机模型，实现iris数据分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt

# load data
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target

df.columns = [
    'sepal length', 'sepal width', 'petal length', 'petal width', 'label'
]
df.label.value_counts()

data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:,:-1], data[:,-1]
y = np.array([1 if i == 1 else -1 for i in y])

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
<matplotlib.legend.Legend at 0x7f177628f110>



/opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages/matplotlib/font_manager.py:1331: UserWarning: findfont: Font family ['sans-serif'] not found. Falling back to DejaVu Sans
  (prop.get_family(), self.defaultFamily[fontext]))

output_6_2

待补全代码

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
# 数据线性可分，二分类数据
# 此处为一元一次线性方程
class Model:
    def __init__(self):
        self.w = np.ones(len(data[0]) - 1, dtype=np.float32)
        self.b = 0
        self.l_rate = 0.1

    def f(self, x, w, b):
        y = np.sign(np.dot(x, w) + b)
        return y

    # 随机梯度下降法
    def fit(self, X_train, y_train):
        is_wrong = False
        while not is_wrong:
            wrong_count = 0
            for d in range(len(X_train)):
                X = X_train[d]
                y = y_train[d]
                if y * (np.dot(X, self.w) + self.b) <= 0: #判断样本被误分类
                    # 更新权重和偏置
                    self.w = self.w + self.l_rate * y * X
                    self.b = self.b + self.l_rate * y
                    wrong_count += 1
            if wrong_count == 0:
                is_wrong = True
        return 'Perceptron Model!'

    def score(self):
        pass
1
2
3
4
5
6
7
8
9
10
11
12
13
# 进行模型训练
perceptron = Model()
perceptron.fit(X, y)

x_points = np.linspace(4, 7, 10)
y_ = -(perceptron.w[0] * x_points + perceptron.b) / perceptron.w[1]
plt.plot(x_points, y_)

plt.plot(data[:50, 0], data[:50, 1], 'bo', color='blue', label='0')
plt.plot(data[50:100, 0], data[50:100, 1], 'bo', color='orange', label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
<matplotlib.legend.Legend at 0x7f1773a0c950>

output_9_1

2. 调用sklearn中Perceptron函数来分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sklearn
from sklearn.linear_model import Perceptron
# 调用sklearn中Perceptron函数进行分类
clf = Perceptron(
    max_iter=5000,      # 增加最大迭代次数
    eta0=0.05,           # 调整学习率（原0.01可能过小）
    shuffle=True
)

# 4. 训练模型
clf.fit(X, y)
# Weights assigned to the features.
print(clf.coef_)
# 截距 Constants in decision function.
print(clf.intercept_)
[[ 1.16  -1.935]]
[-0.25]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 画布大小
plt.figure(figsize=(10,10))

# 中文标题
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus'] = False
plt.title('鸢尾花线性数据示例')

plt.scatter(data[:50, 0], data[:50, 1], c='b', label='Iris-setosa',)
plt.scatter(data[50:100, 0], data[50:100, 1], c='orange', label='Iris-versicolor')

# 画感知机的线
x_ponits = np.arange(4, 8)
y_ = -(clf.coef_[0][0]*x_ponits + clf.intercept_)/clf.coef_[0][1]
plt.plot(x_ponits, y_)

# 其他部分
plt.legend()  # 显示图例
plt.grid(False)  # 不显示网格
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
<matplotlib.legend.Legend at 0x7f1769a4eb50>



/opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages/matplotlib/font_manager.py:1331: UserWarning: findfont: Font family ['sans-serif'] not found. Falling back to DejaVu Sans
  (prop.get_family(), self.defaultFamily[fontext]))

output_12_2

3. 验证感知机为什么不能表示异或（选做）

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
import numpy as np
from sklearn.linear_model import Perceptron
import matplotlib.pyplot as plt
x=np.array([[1,0],[0,1],[0,0],[1,1]])
y=np.array([1, 1, -1, -1])
plt.plot(x[:2,0],x[:2,1],'bo',color='red',label='1')
plt.plot(x[2:4,0],x[2:4,1],'bo',color='blue',label='-1')
plt.xlabel('x1')
plt.ylabel('x2')
plt.legend()

# 请在下方作答
# 初始化感知机模型
clf = Perceptron(
    max_iter=1000,      # 增加最大迭代次数
    eta0=0.1,           # 学习率
    random_state=42,
    shuffle=True        # 每次迭代打乱数据
)

# 训练模型
clf.fit(X, y)

# 输出模型参数
print("特征权重 (w):", clf.coef_)
print("截距 (b):", clf.intercept_)

# 预测结果
predictions = clf.predict(X)
print("预测结果:", predictions)
print("真实标签:", y)


特征权重 (w): [[0. 0.]]
截距 (b): [0.]
预测结果: [-1 -1 -1 -1]
真实标签: [ 1  1 -1 -1]


/opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages/matplotlib/font_manager.py:1331: UserWarning: findfont: Font family ['sans-serif'] not found. Falling back to DejaVu Sans
  (prop.get_family(), self.defaultFamily[fontext]))

output_14_2

发表于 更新于 分类于 ，

上机实验10—支持向量机

任务1：sklearn中的SVC与惩罚系数C

  • 提供一份糖尿病患者数据集diabetes.csv，该数据集有768个数据样本，9个特征(最后一列为目标特征数据)，并且已经存入变量data。特征的具体信息如下：
特征名称 特征含义 取值举例
feature1 怀孕次数 6
feature2 2小时口服葡萄糖耐受实验中的血浆葡萄浓度 148
feature3 舒张压 (mm Hg) 72
feature4 三头肌皮褶厚度(mm) 35
feature5 2小时血清胰岛素浓度 (mu U/ml) 0
feature6 体重指数(weight in kg/(height in m)^2) 33.6
feature7 糖尿病谱系功能(Diabetes pedigree function) 0.627
feature8 年龄 50
class 是否患有糖尿病 1：阳性；0：阴性

主要任务如下：

  • 请先将数据使用sklearn中的StandardScaler进行标准化；
  • 然后使用sklearn中的svm.SVC支持向量分类器，构建支持向量机模型（所有参数使用默认参数），对测试集进行预测，将预测结果存为pred_y，并对模型进行评价；
  • 最后新建一个svm.SVC实例clf_new，并设置惩罚系数C=0.3，并利用该支持向量分类器对测试集进行预测，将预测结果存为pred_y_new，并比较两个模型的预测效果。

待补全代码

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
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report
from sklearn.svm import SVC

# 读取数据
data = pd.read_csv('diabetes.csv')

# 请在下方作答 #
# 将目标特征与其他特征分离
X = data.drop('class', axis=1)  
y = data['class']  

# 划分训练集train_X, train_y和测试集train_X, train_y
train_X, test_X, train_y, test_y = train_test_split(X, y, test_size = .2, random_state = 0)

# 训练集标准化，返回结果为scaled_train_X
scaler = StandardScaler()
scaled_train_X = scaler.fit_transform(train_X)

# 构建支持向量机模型
clf = SVC()

# 模型训练
clf.fit(scaled_train_X, train_y)

# 测试集标准化
scaled_test_X = scaler.transform(test_X)

# 使用模型返回预测值
pred_y = clf.predict(scaled_test_X)

# 打印支持向量的个数，返回结果为列表，[-1标签的支持向量，+1标签的支持向量]
print(clf.n_support_)

# 使用classification_report函数进行模型评价
print(classification_report(test_y, pred_y))

# 构建惩罚系数C为0.3的模型，并与之前的模型做比较
clf_new = SVC(C=0.3)
clf_new.fit(scaled_train_X, train_y)
pred_y_new = clf_new.predict(scaled_test_X)

print(clf_new.n_support_)
print(classification_report(test_y, pred_y_new))

#调整惩罚系数C寻优
[187 180]

              precision    recall  f1-score   support

​ 

           0       0.82      0.90      0.86       107

           1       0.70      0.55      0.62        47

​ 

    accuracy                           0.79       154

   macro avg       0.76      0.73      0.74       154

weighted avg       0.78      0.79      0.78       154

​ 

[197 196]

              precision    recall  f1-score   support

​ 

           0       0.83      0.92      0.87       107

           1       0.75      0.57      0.65        47

​ 

    accuracy                           0.81       154

   macro avg       0.79      0.75      0.76       154

weighted avg       0.81      0.81      0.80       154

​

预期结果

任务2：SVC选定RBF核函数，并寻优核带宽参数gamma

在支持向量分类器中，核函数对其性能有直接的影响。已知径向基函数 RBF 及核矩阵元素为：

且对于核矩阵K，有$K_{ij}=K(\boldsymbol{x}_i, \boldsymbol{x}_j).$

主要任务如下：

  • 自定义函数实现径向基函数 rbf_kernel，要求输入参数为两个矩阵 X、Y，以及 gamma；
  • 利用rbf_kernel核函数，计算标准化后的训练集scaled_train_X的核矩阵，并存为 rbf_matrix；
  • 利用rbf_kernel核函数，训练支持向量分类器 clf，并预测标准化后的测试数据 scaled_test_X 的标签，最后评价模型效果。

    提示：先计算各自的 Gram 矩阵，然后再使用 np.diag 提取对角线元素，使用 np.tile 将列表扩展成一个矩阵。

待补全代码

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
import numpy as np
# 请在下方作答 #
def rbf_kernel(X, Y, gamma=0.5):
    
    # 获取X和Y的大小
    num1 = X.shape[0]
    num2 = Y.shape[0]
    
    # 计算X和X^T的矩阵乘积
    gram_1 = X.dot(X.T)
    
    # 获取gram_1对角线位置的元素，组成大小(num1, 1)的列表，并将整个列表复制，扩展为(num1, num2)大小的矩阵component1
    component1 = np.tile(np.diag(gram_1).reshape(-1, 1), (1, num2))
    
    # 计算Y和Y^T的乘积
    gram_2 = Y.dot(Y.T)
     
    # 获取gram_2对角线位置的元素，组成(1, num2)的列表，并将整个列表复制，扩展为(num1, num2)大小的矩阵component2
    component2 = np.tile(np.diag(gram_2).reshape(1, -1), (num1, 1))
   
    # 计算2X和Y^T的内积 
    component3 = 2 * X.dot(Y.T)
  
    # 返回结果
    result = np.exp(gamma*(component3 - component1 - component2))
    return result

# 计算糖尿病患者训练数据集的核矩阵
rbf_matrix = rbf_kernel(scaled_train_X, scaled_train_X)

# 训练一个支持向量分类器
clf = SVC(kernel=rbf_kernel)
clf.fit(scaled_train_X, train_y)
pred_y = clf.predict(scaled_test_X)
print (clf.n_support_)
print (classification_report(test_y, pred_y))

# 调整gamma值寻找最优
[250 208]

              precision    recall  f1-score   support

           0       0.84      0.89      0.86       107

           1       0.71      0.62      0.66        47

    accuracy                           0.81       154

   macro avg       0.77      0.75      0.76       154

weighted avg       0.80      0.81      0.80       154

预期结果

任务3：自定义函数实现SVM（选做）

主要任务如下：

  • 读取sklearn中的iris数据集，提取特征与标记，并进行数据划分为训练与测试集；
  • 自定义函数实现SVM；
  • 调用SVM函数进行支持向量机训练，并对测试集进行测试。

待补全代码

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
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report
from sklearn.svm import SVC
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
import matplotlib.pyplot as plt

def create_data():
    iris = load_iris()
    df = pd.DataFrame(iris.data, columns=iris.feature_names)
    df['label'] = iris.target
    df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
    data = np.array(df.iloc[:100, [0, 1, -1]])
    for i in range(len(data)):
        if data[i,-1] == 0:
            data[i,-1] = -1
    # print(data)
    return data[:,:2], data[:,-1]

# 读取数据，拆分数据，训练测试集划分
X, y = create_data()
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25)
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
class SVM:
    def __init__(self, max_iter=100, kernel='linear'):
        self.max_iter = max_iter
        self._kernel = kernel
    
    def init_args(self, features, labels):
        self.m, self.n = features.shape
        self.X = features
        self.Y = labels
        self.b = 0.0
        
        # 将Ei保存在一个列表里
        self.alpha = np.ones(self.m)
        self.E = [self._E(i) for i in range(self.m)]
        # 松弛变量
        self.C = 1.0
        
    def _KKT(self, i):
        y_g = self._g(i)*self.Y[i]
        if self.alpha[i] == 0:
            return y_g >= 1
        elif 0 < self.alpha[i] < self.C:
            return y_g == 1
        else:
            return y_g <= 1
    
    # g(x)预测值，输入xi（X[i]）
    def _g(self, i):
        r = self.b
        for j in range(self.m):
            r += self.alpha[j] * self.Y[j] * self.kernel(self.X[j], self.X[i])
        return r
    
    # 核函数
    def kernel(self, x1, x2):
        if self._kernel == 'linear':
            return np.dot(x1, x2)
        elif self._kernel == 'poly':
            return (sum([x1[k]*x2[k] for k in range(self.n)]) + 1)**2
    
        return 0
    
    # E（x）为g(x)对输入x的预测值和y的差
    def _E(self, i):
        return self._g(i) - self.Y[i]
    
    def _init_alpha(self):
        # 外层循环首先遍历所有满足0<a<C的样本点，检验是否满足KKT
        index_list = [i for i in range(self.m) if 0 < self.alpha[i] < self.C]
        # 否则遍历整个训练集
        non_satisfy_list = [i for i in range(self.m) if i not in index_list]
        index_list.extend(non_satisfy_list)
        
        for i in index_list:
            if self._KKT(i):
                continue
            
            E1 = self.E[i]
            # 如果E2是+，选择最小的；如果E2是负的，选择最大的
            if E1 >= 0:
                j = min(range(self.m), key=lambda x: self.E[x])
            else:
                j = max(range(self.m), key=lambda x: self.E[x])
            return i, j
        
    def _compare(self, _alpha, L, H):
        if _alpha > H:
            return H
        elif _alpha < L:
            return L
        else:
            return _alpha      
    
    def fit(self, features, labels):
        self.init_args(features, labels)
        
        for t in range(self.max_iter):
            # train
            i1, i2 =self._init_alpha()
            
            # 边界
            if self.Y[i1] == self.Y[i2]:
                L = max(0, self.alpha[i1]+self.alpha[i2]-self.C)
                H = min(self.C, self.alpha[i1]+self.alpha[i2])
            else:
                L = max(0, self.alpha[i2]-self.alpha[i1])
                H = min(self.C, self.C+self.alpha[i2]-self.alpha[i1])
                
            E1 = self.E[i1]
            E2 = self.E[i2]
            # eta=K11+K22-2K12
            eta = self.kernel(self.X[i1], self.X[i1]) + \
                  self.kernel(self.X[i2], self.X[i2]) - \
                  2 * self.kernel(self.X[i1], self.X[i2])
            if eta <= 0:
                # print('eta <= 0')
                continue
                
            alpha2_new_unc = self.alpha[i2] + self.Y[i2] * (E2 - E1) / eta
            alpha2_new = self._compare(alpha2_new_unc, L, H)
            
            alpha1_new = self.alpha[i1] + self.Y[i1] * self.Y[i2] * (self.alpha[i2] - alpha2_new)
            
            b1_new = -E1 - self.Y[i1] * self.kernel(self.X[i1], self.X[i1]) * (alpha1_new-self.alpha[i1]) - self.Y[i2] * self.kernel(self.X[i2], self.X[i1]) * (alpha2_new-self.alpha[i2])+ self.b 
            b2_new = -E2 - self.Y[i1] * self.kernel(self.X[i1], self.X[i2]) * (alpha1_new-self.alpha[i1]) - self.Y[i2] * self.kernel(self.X[i2], self.X[i2]) * (alpha2_new-self.alpha[i2])+ self.b 
            
            if 0 < alpha1_new < self.C:
                b_new = b1_new
            elif 0 < alpha2_new < self.C:
                b_new = b2_new
            else:
                # 选择中点
                b_new = (b1_new + b2_new) / 2
                
            # 更新参数
            self.alpha[i1] = alpha1_new
            self.alpha[i2] = alpha2_new
            self.b = b_new
            
            self.E[i1] = self._E(i1)
            self.E[i2] = self._E(i2)
        return 'train done!'
            
    def predict(self, data):
        r = self.b
        for i in range(self.m):
            r += self.alpha[i] * self.Y[i] * self.kernel(self.X[i], data)
            
        return 1 if r > 0 else -1
    
    def score(self, X_test, y_test):
        right_count = 0
        for i in range(len(X_test)):
            result = self.predict(X_test[i])
            if result == y_test[i]:
                right_count += 1
        return right_count / len(X_test)
    
    def _weight(self):
        # linear model
        yx = self.Y.reshape(-1, 1)*self.X
        self.w = np.dot(self.alpha, yx)
        return self.w
1
2
3
4
# 调用SVM进行模型训练与测试评估
svm = SVM(max_iter=100)
svm.fit(X_train, y_train)
svm.score(X_test, y_test)
0.92

1

发表于 更新于 分类于 ，

正文

作业

类别不均衡指的是什么？有哪些解决方案。

类别不均衡（Class Imbalance） 是指分类任务中不同类别样本的数量差异显著，例如：

  • 多数类（Majority Class）：样本数量多（如正常交易占99%）。
  • 少数类（Minority Class）：样本数量极少（如欺诈交易仅占1%）。

这种问题会导致模型倾向于预测多数类，严重降低少数类的预测性能（如漏检欺诈行为）。以下是详细解释和解决方案：

1. 类别不均衡的影响

  • 模型偏差：模型过度关注多数类，忽略少数类（如将所有样本预测为多数类，准确率虚高）。
  • 评估指标失效：准确率（Accuracy）失去意义（例如：99% 的样本是多数类，模型只需预测多数类即可达到 99% 准确率）。

2. 解决方案

2.1 数据层面调整

  • 过采样（Oversampling）

    • 复制少数类样本：直接复制少数类数据（可能导致过拟合）。
    • 生成合成样本：使用 SMOTE（Synthetic Minority Over-sampling Technique）生成新样本（通过插值法）。
    • 改进版算法：如 ADASYN（自适应合成采样），根据样本分布动态生成数据。

  • 欠采样（Undersampling）

    • 随机删除多数类样本：减少多数类数量，但可能丢失重要信息。
    • 选择性欠采样：保留多数类中更具代表性的样本（如 Tomek Links 或 Cluster Centroids）。

  • 混合采样
    结合过采样和欠采样（如先过采样少数类，再欠采样多数类）。

2.2 算法层面调整

  • 调整类别权重（Class Weight）

    • 为少数类分配更高的权重（如 class_weight='balanced'），让模型更关注少数类。
    • 公式：
      [
      \text{权重} = \frac{\text{多数类样本数}}{\text{少数类样本数}}
      ]

  • 集成学习（Ensemble Methods）

    • EasyEnsemble：从多数类中随机采样多个子集，分别与少数类结合训练多个模型，集成结果。
    • BalanceCascade：逐步筛选多数类样本，避免冗余信息。
    • RUSBoost：结合欠采样和提升算法（Boosting）。

  • 改进损失函数

    • Focal Loss：降低易分类样本的权重，聚焦于难分类的少数类样本。
    • Cost-sensitive Learning：为不同类别分配不同的误分类代价。

2.3 评估指标调整

  • 避免使用准确率（Accuracy），改用以下指标：
    • F1-Score：精确率（Precision）和召回率（Recall）的调和平均。
    • AUC-ROC 曲线：衡量分类器在不同阈值下的整体性能。
    • 精确率-召回率曲线（PR Curve）：关注少数类的识别能力。
    • 平衡准确率（Balanced Accuracy）：计算每个类别的召回率的平均值。

2.4 高级技术

  • 异常检测（Anomaly Detection）
    将少数类视为异常，使用 One-Class SVM 或孤立森林（Isolation Forest）检测。

  • 生成对抗网络（GAN）
    使用 GAN 生成高质量的少数类样本（如医疗数据中的罕见病样本）。

  • 阈值调整
    根据业务需求调整分类阈值（如将欺诈检测的阈值从 0.5 降低到 0.3）。

3. 实际应用建议

  • 场景举例：
    • 欺诈检测：少数类（欺诈）样本极少，需使用 SMOTE + 集成学习。
    • 医疗诊断：罕见病识别可尝试 GAN 生成数据或异常检测。
  • 工具库：
    • Python 的 imbalanced-learn（提供 SMOTE、EasyEnsemble 等）。
    • TensorFlow/PyTorch 中的 class_weight 参数。

总结

类别不均衡的核心是让模型“看到”足够的少数类信息，同时选择合适的评估指标。根据数据特点和业务需求，灵活组合数据采样、算法改进和评估方法，才能有效提升模型对少数类的识别能力。

关于误差逆传播BP算法，详细推导E_k对w_hj的导数和对v_ih的导数。

以下是误差逆传播（Backpropagation, BP）算法中误差 ( Ek ) 对权重 ( w{hj} )（输出层权重）和 ( v_{ih} )（隐藏层权重）的详细导数推导过程：

符号定义

  • 输入层节点：( $x_i$ )（( i = 1, 2, $\dots, n $)）
  • 隐藏层节点：( $b_h$ )（( h = 1, 2, $\dots, q $)）
  • 输出层节点：( $y_j$ )（( j = 1, 2,$ \dots, l $)）
  • 隐藏层到输出层的权重：( $w_{hj}$ )（从隐藏层节点 ( h ) 到输出层节点 ( j )）
  • 输入层到隐藏层的权重：( $v_{ih}$ )（从输入层节点 ( i ) 到隐藏层节点 ( h )）
  • 激活函数：假设为 Sigmoid 函数 ($ f(x) = \frac{1}{1 + e^{-x}} $)，其导数为 ($ f’(x) = f(x)(1 - f(x)) $)
  • 损失函数：均方误差 ($ Ek = \frac{1}{2} \sum{j=1}^l (y_j - \hat{y}_j)^2 $)，其中 ( $\hat{y}_j $) 是真实标签。

1. 计算 ( $\frac{\partial Ek}{\partial w{hj}} $)（输出层权重的梯度）

步骤分解：

  1. 输出层输入：
    [
    $netj = \sum{h=1}^q w_{hj} b_h$
    ]
    输出层节点的激活值为 ( $y_j = f(net_j)$ )。

  2. 损失函数对 ( net_j ) 的导数：
    [
    $\frac{\partial E_k}{\partial net_j} = \frac{\partial E_k}{\partial y_j} \cdot \frac{\partial y_j}{\partial net_j}$
    ]

    • ( $\frac{\partial E_k}{\partial y_j} = (y_j - \hat{y}_j)$ )（均方误差导数）
    • ( $\frac{\partial y_j}{\partial net_j} = f’(net_j) = y_j (1 - y_j) $)（Sigmoid 导数）
      因此：
      [
      $\frac{\partial E_k}{\partial net_j} = (y_j - \hat{y}_j) \cdot y_j (1 - y_j)$
      ]

  3. 损失函数对 ( w_{hj} ) 的导数：
    [
    $\frac{\partial Ek}{\partial w{hj}} = \frac{\partial Ek}{\partial net_j} \cdot \frac{\partial net_j}{\partial w{hj}}$
    ]

    • ( $\frac{\partial netj}{\partial w{hj}} = bh$ )（因为 ( $net_j = \sum w{hj} bh $)）
      因此：
      [
      $\frac{\partial E_k}{\partial w      {hj}} = (y_j - \hat{y}_j) \cdot y_j (1 - y_j) \cdot b_h$
      ]

2. 计算 ( $\frac{\partial Ek}{\partial v{ih}} $)（隐藏层权重的梯度）

步骤分解：

  1. 隐藏层输入：
    [
    $neth = \sum{i=1}^n v_{ih} x_i$
    ]
    隐藏层节点的激活值为 ($ b_h = f(net_h) $)。

  2. 损失函数对 ( net_h ) 的导数：
    需要将误差从输出层反向传播到隐藏层：
    [
    $\frac{\partial Ek}{\partial net_h} = \sum{j=1}^l \left( \frac{\partial E_k}{\partial net_j} \cdot \frac{\partial net_j}{\partial b_h} \right) \cdot \frac{\partial b_h}{\partial net_h}$
    ]

    • ($ \frac{\partial netj}{\partial b_h} = w{hj} $)（输出层输入依赖于隐藏层输出 ( b_h )）
    • ($ \frac{\partial bh}{\partial net_h} = f’(net_h) = b_h (1 - b_h) $)
      因此：
      [
      $\frac{\partial E_k}{\partial net_h} = \left( \sum      {j=1}^l \frac{\partial Ek}{\partial net_j} \cdot w{hj} \right) \cdot b_h (1 - b_h)$
      ]

  3. 损失函数对 ( v_{ih} ) 的导数：
    [
    $\frac{\partial Ek}{\partial v{ih}} = \frac{\partial Ek}{\partial net_h} \cdot \frac{\partial net_h}{\partial v{ih}}$
    ]

    • ($ \frac{\partial neth}{\partial v{ih}} = xi $)（因为 ($ net_h = \sum v{ih} xi $）
      因此：
      [
      $\frac{\partial E_k}{\partial v      {ih}} = \left( \sum{j=1}^l \frac{\partial E_k}{\partial net_j} \cdot w{hj} \right) \cdot b_h (1 - b_h) \cdot x_i$
      ]

3. 最终梯度公式

  • 输出层权重梯度：
    [
    $\frac{\partial Ek}{\partial w{hj}} = \delta_j \cdot b_h, \quad \text{其中 } \delta_j = (y_j - \hat{y}_j) \cdot y_j (1 - y_j)$
    ]

  • 隐藏层权重梯度：
    [
    $\frac{\partial Ek}{\partial v{ih}} = \deltah \cdot x_i, \quad \text{其中 } \delta_h = \left( \sum{j=1}^l \deltaj \cdot w{hj} \right) \cdot b_h (1 - b_h)$
    ]

4. 参数更新规则

使用梯度下降法更新权重：

  1. 输出层权重更新：
    [
    $w{hj} \leftarrow w{hj} - \eta \cdot \frac{\partial Ek}{\partial w{hj}}$
    ]

  2. 隐藏层权重更新：
    [
    $v{ih} \leftarrow v{ih} - \eta \cdot \frac{\partial Ek}{\partial v{ih}}$
    ]
    其中，( $\eta $) 是学习率。

关键点总结

  1. 链式法则：通过逐层反向传播误差，将全局误差分解为对每个权重的局部梯度。
  2. 敏感度（Delta）：
    • 输出层：($ \delta_j = (y_j - \hat{y}_j) \cdot f’(net_j)$ )
    • 隐藏层：($ \deltah = \left( \sum \delta_j w{hj} \right) \cdot f’(net_h)$ )
  3. 高效性：通过存储中间结果（如 ( \delta_j )），避免重复计算，降低时间复杂度。

如果需要进一步解释具体步骤或示例，请随时告诉我！ 😊

参考资料

[5分钟深度学习] #01 梯度下降算法_哔哩哔哩_bilibili

反向传播算法可视化展示_哔哩哔哩_bilibili

发表于 更新于 分类于 ，

上机实验：决策树

任务1：分支节点的选择方法

现有一个数据集 weekend.txt，目标是根据一个人的特征来预测其周末是否出行。

所有特征均为二元特征，取值为 0 或 1，其中“status”（目标特征也是类别）表示用户的周末是否出行，1 表示出行，0 表示不出行，“marriageStatus”表示申请人是否已婚、“hasChild”表示申请人是否有小孩、“hasAppointment”表示申请人是否有约、“weather”表示天气是否晴朗。

已知信息熵和信息增益的公式为：

请完成以下三个内容：

  • 请自定义函数 cal_entropy(data, feature_name)计算数据集data关于feature_name的信息熵。输入参数 data 为 DataFrame，feature_name 为目标特征(或类别)的名称；

  • 请调用 cal_entropy() 函数计算决策树分支之前的信息熵，保存为 data_entropy；

  • 请自定义函数 cal_infoGain(data, base_entropy) 计算 weekend.txt 中各个特征的信息增益，保存为列表 infogains，并选择信息增益最大的分支节点 best_feature。

补全代码

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
# 导入必要库
import numpy as np
import pandas as pd

# 读取数据（假设文件为tab分隔，包含特征和目标变量'status'）
weekend_data = pd.read_table('weekend.txt', sep=' ')

## 自定义熵计算函数
def cal_entropy(data, feature_name):
    '''
    计算给定特征的信息熵
    :param data: 输入的DataFrame数据集
    :param feature_name: 需要计算熵的目标特征名称
    :return: 保留三位小数的熵值
    '''
    entropy = 0  # 初始化熵值
    num = data.shape[0]  # 获取数据集总样本数
    
    # 统计目标特征各取值的频数（如：status特征中"出门"和"不出门"的数量）
    freq_stats = data[feature_name].value_counts()
    
    # 遍历每个不同取值计算熵
    for freq in freq_stats:
        prob = freq / num  # 计算当前取值的概率
        # 根据信息熵公式累加计算（注意：熵公式为负数求和）
        entropy -= prob * np.log2(prob)  # 等价于 entropy += -prob * log2(prob)
    
    return round(entropy, 3)  # 保留三位小数

## 计算初始信息熵（假设目标特征列为'status'）
data_entropy = cal_entropy(weekend_data, 'status')

## 自定义信息增益计算函数
def cal_infoGain(data, base_entropy):
    '''
    计算所有特征的信息增益并选择最优特征
    :param data: 输入的DataFrame数据集
    :param base_entropy: 数据集的初始熵值
    :return: 信息增益列表和最优特征名称
    '''
    infogain_list = []  # 存储各特征的信息增益
    total_samples = data.shape[0]  # 总样本数
    feature_list = list(data.columns.values)  # 获取所有特征名称
    feature_list.remove('status')  # 移除目标特征（避免计算自身）
    
    # 遍历每个特征计算信息增益
    for feature in feature_list:
        sub_entropy = 0  # 初始化条件熵
        
        # 获取当前特征的取值分布（如：天气特征的"晴朗/下雨/阴天"）
        value_counts = data[feature].value_counts()
        
        # 遍历特征的每个取值
        for value, count in value_counts.items():
            # 获取特征取当前值的子集
            subset = data[data[feature] == value]
            subset_samples = subset.shape[0]  # 子集样本数
            weight = subset_samples / total_samples  # 计算权重
            
            # 计算子集的熵并累加加权熵
            sub_entropy += weight * cal_entropy(subset, 'status')
        
        # 计算信息增益（信息增益 = 基础熵 - 条件熵）
        info_gain = base_entropy - sub_entropy
        infogain_list.append(round(info_gain, 4))  # 保留四位小数
    
    # 找到信息增益最大的特征
    max_gain = max(infogain_list)  # 最大增益值
    max_index = infogain_list.index(max_gain)  # 最大值索引
    best_feature = feature_list[max_index]  # 对应的最优特征名称
    
    return infogain_list, best_feature

## 执行信息增益计算
infogains, best_feature = cal_infoGain(weekend_data, data_entropy)

## 结果输出
print('各特征的信息增益：', infogains)
print('\n信息增益最大的特征：', best_feature)
各特征的信息增益： [0.0076, 0.0076, 0.0322, 0.0868]

​ 

信息增益最大的特征： weather

期望输出：

任务2：常见的决策树算法

现在有一份有关商品销量的数据集product.csv，数据集的离散型特征信息如下：

特征名称 取值说明
天气 1：天气好；0：天气坏
是否周末 1：是；0：不是
是否有促销 1：有促销；0：没有促销
销量 1：销量高；0：销量低

请完成以下三个内容：

  • 请根据提供的商品销量数据集 data，使用 sklearn 中的 DecisionTreeClassifier()函数构建决策树模型，模型选择分支结点的特征以Gini指数为判定准则；
  • 训练模型，并对测试集test_X进行预测，将预测结果存为 pred_y，进行模型评估；
  • 将构建的决策树模型进行可视化。

补全代码

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
import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_graphviz  # 补全export_graphviz导入
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report

data = pd.read_csv('product.csv')

## 对数据集切片，获取除目标特征以外的其他特征的数据记录X
X = data[["天气", "是否周末", "是否有促销"]]  # 使用双括号选择多列

## 对数据集切片，获取目标特征`销量`的数据记录y
y = data["销量"]

## 使用train_test_split函数划分训练集train_X, train_y和测试集test_X, test_y
## 测试集所占比例为0.1,random_state为0
train_X, test_X, train_y, test_y = train_test_split(X, y, test_size=0.1, random_state=0)

## 构建分支节点选择方法为基尼指数的决策树模型tree_model，进行模型训练、测试与性能评估
tree_model = DecisionTreeClassifier(criterion='gini')  # 设置基尼指数准则
tree_model.fit(train_X, train_y)  # 模型训练

pred_y = tree_model.predict(test_X)  # 测试集预测
print("模型分类报告：")
print(classification_report(test_y, pred_y))  # 输出评估报告

## 决策树可视化（修正特征名称与数据列一致）
import graphviz
dot_data = export_graphviz(
    tree_model,
    out_file=None,
    feature_names=["天气", "是否周末", "是否有促销"],  # 修正为完整特征名称
    class_names=["销量低", "销量高"],
    filled=True,
    rounded=True
)
graph = graphviz.Source(dot_data)
graph
模型分类报告：

              precision    recall  f1-score   support

​ 

           0       1.00      0.50      0.67         2

           1       0.67      1.00      0.80         2

​ 

    accuracy                           0.75         4

   macro avg       0.83      0.75      0.73         4

weighted avg       0.83      0.75      0.73         4

​

​
svg
​

期望输出：


任务3：利用任务1的cal_infoGain函数自行实现ID3决策树算法

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
import numpy as np

import pandas as pd

from sklearn.model_selection import train_test_split

from sklearn.metrics import classification_report

import graphviz



## 任务1的熵计算函数（已完整实现）

def cal_entropy(data, feature_name):

    '''

    计算给定特征的信息熵

    :param data: 输入的DataFrame数据集

    :param feature_name: 需要计算熵的目标特征名称

    :return: 保留三位小数的熵值

    '''

    entropy = 0  # 初始化熵值

    num = data.shape[0]  # 获取数据集总样本数

    

    # 统计目标特征各取值的频数分布

    freq_stats = data[feature_name].value_counts()

    

    # 遍历每个不同取值计算熵

    for freq in freq_stats:

        prob = freq / num  # 计算当前取值的概率

        # 根据信息熵公式累加计算（Σ -p_i log2(p_i)）

        entropy -= prob * np.log2(prob)  # 等价于 entropy += -prob * log2(prob)

    

    return round(entropy, 3)  # 保留三位小数



## 任务1的信息增益计算函数（已完整实现）

def cal_infoGain(data, base_entropy):

    '''

    计算所有特征的信息增益并选择最优特征

    :param data: 输入的DataFrame数据集

    :param base_entropy: 数据集的初始熵值

    :return: 信息增益列表和最优特征名称

    '''

    infogain_list = []  # 存储各特征的信息增益

    total_samples = data.shape[0]  # 总样本数

    feature_list = list(data.columns.values)  # 所有特征名称

    

    # 自动识别目标特征（假设目标特征不在特征列表中）

    target_feature = [col for col in feature_list if col not in data.columns][0]

    feature_list = [col for col in data.columns if col != target_feature]  # 移除目标特征

    

    # 遍历每个特征计算信息增益

    for feature in feature_list:

        sub_entropy = 0  # 初始化条件熵

        # 获取当前特征的取值分布

        value_counts = data[feature].value_counts()

        

        # 计算条件熵

        for value, count in value_counts.items():

            subset = data[data[feature] == value]  # 特征取当前值的子集

            subset_samples = subset.shape[0]  # 子集样本数

            weight = subset_samples / total_samples  # 计算权重

            # 累加加权熵

            sub_entropy += weight * cal_entropy(subset, target_feature)

        

        # 计算信息增益

        info_gain = base_entropy - sub_entropy

        infogain_list.append(round(info_gain, 4))  # 保留四位小数

    

    # 选择最优特征

    max_gain = max(infogain_list)  # 最大信息增益值

    max_index = infogain_list.index(max_gain)  # 最大值索引

    best_feature = feature_list[max_index]  # 最优特征名称

    

    return infogain_list, best_feature



## ID3决策树实现

class ID3DecisionTree:

    def __init__(self):

        self.tree = None  # 存储决策树结构

        self.target = None  # 目标特征名称



    def fit(self, data, target_feature):

        '''

        训练决策树模型

        :param data: 包含特征和目标列的DataFrame

        :param target_feature: 目标特征名称（如'销量'）

        '''

        self.target = target_feature

        # 提取特征列表（排除目标特征）

        features = [col for col in data.columns if col != target_feature]

        # 递归构建决策树

        self.tree = self._build_tree(data, features)



    def _build_tree(self, data, features):

        '''

        递归构建决策树

        :param data: 当前节点的数据集

        :param features: 当前可用的特征列表

        :return: 字典形式的树节点

        '''

        # 终止条件1：所有样本属于同一类别

        if len(data[self.target].unique()) == 1:

            return {

                'class': data[self.target].values[0],  # 叶节点类别

                'samples': len(data)  # 样本数量

            }

        

        # 终止条件2：无剩余特征可用时选择多数类

        if not features:

            class_counts = data[self.target].value_counts()

            return {

                'class': class_counts.idxmax(),  # 多数类

                'samples': len(data)

            }

        

        # 计算当前数据集的熵

        base_entropy = cal_entropy(data, self.target)

        # 获取最优特征和信息增益列表

        info_gains, best_feature = cal_infoGain(data, base_entropy)

        

        # 创建当前树节点

        node = {

            'feature': best_feature,  # 分裂特征

            'info_gain': info_gains[features.index(best_feature)],  # 信息增益值

            'samples': len(data),  # 样本数量

            'children': {}  # 子节点

        }

        

        # 递归构建子树（排除当前最优特征）

        remaining_features = [f for f in features if f != best_feature]

        # 遍历最优特征的所有取值

        for value in data[best_feature].unique():

            subset = data[data[best_feature] == value]  # 获取子集

            

            # 处理空子集（采用父节点多数类）

            if subset.empty:

                class_counts = data[self.target].value_counts()

                node['children'][value] = {

                    'class': class_counts.idxmax(),

                    'samples': 0

                }

            else:

                # 递归构建子树

                node['children'][value] = self._build_tree(subset, remaining_features)

        

        return node



    def predict(self, X):

        '''

        对新样本进行预测

        :param X: 特征数据（DataFrame格式）

        :return: 预测结果列表

        '''

        predictions = []

        # 遍历每个样本

        for _, sample in X.iterrows():

            current_node = self.tree

            # 遍历树直到叶节点

            while 'children' in current_node:

                feature = current_node['feature']  # 当前分裂特征

                value = sample[feature]  # 样本在该特征的取值

                

                # 处理未见过的特征值（采用当前节点多数类）

                if value not in current_node['children']:

                    class_counts = self._get_class_counts(current_node)

                    # 选择样本数最多的类别

                    predictions.append(max(class_counts, key=class_counts.get))

                    break  # 跳出循环

                

                # 移动到子节点

                current_node = current_node['children'][value]

            

            # 记录叶节点类别

            if 'class' in current_node:

                predictions.append(current_node['class'])

        

        return predictions



    def _get_class_counts(self, node):

        '''

        递归统计节点中的类别分布

        :param node: 当前节点

        :return: 类别计数字典

        '''

        counts = {}

        # 如果是叶节点直接返回

        if 'class' in node:

            return {node['class']: node['samples']}

        

        # 递归统计子节点

        for child in node['children'].values():

            child_counts = self._get_class_counts(child)

            for cls, cnt in child_counts.items():

                counts[cls] = counts.get(cls, 0) + cnt

        

        return counts



    def visualize(self, feature_names, class_names):

        '''

        可视化决策树

        :param feature_names: 特征名称列表

        :param class_names: 类别名称列表

        :return: graphviz对象

        '''

        dot = graphviz.Digraph()  # 创建有向图

        # 递归构建图形

        self._build_graph(dot, self.tree, feature_names, class_names)

        return dot



    def _build_graph(self, dot, node, feature_names, class_names, parent=None, edge_label=""):

        '''

        递归构建graphviz图形

        :param dot: graphviz.Digraph对象

        :param node: 当前节点

        :param feature_names: 特征名称列表

        :param class_names: 类别名称列表

        :param parent: 父节点（用于连接边）

        :param edge_label: 边标签（特征取值）

        '''

        # 叶节点样式

        if 'class' in node:

            label = f"{class_names[int(node['class'])]}\\n{node['samples']} samples"

            dot.node(

                str(id(node)),  # 唯一节点ID

                label,

                shape="box",  # 矩形框

                style="filled",  # 填充颜色

                fillcolor="lightblue"  # 浅蓝色

            )

        # 内部节点样式

        else:

            label = f"{node['feature']}\\nIG={node['info_gain']:.3f}\\n{node['samples']} samples"

            dot.node(

                str(id(node)),

                label,

                shape="ellipse",  # 椭圆

                style="filled",

                fillcolor="lightgreen"  # 浅绿色

            )

        

        # 创建父节点到当前节点的边

        if parent:

            dot.edge(

                str(id(parent)),

                str(id(node)),

                label=edge_label  # 显示特征取值

            )

        

        # 递归处理子节点

        if 'children' in node:

            for value, child in node['children'].items():

                self._build_graph(

                    dot,

                    child,

                    feature_names,

                    class_names,

                    node,  # 当前节点作为父节点

                    str(value)  # 边标签为特征取值

                )
1

发表于 分类于 ，

环境搭建

安装vmware虚拟机

安装ubuntu

在Ubuntu终端里编写C语言程序

打开终端：ctrl+alt+t

新建文件：vim hello.c

输入

1
2
3
4
5
6
7
8
#include <stdio.h>
#define DISPLAY "hello c!"
int main(void)
{
  printf("%s\n", DISPLAY);
  return 0;
}
ZZ（*说明：ZZ当前文件进行快速保存操作*）

退出编译模式：shift+：

输入：w保存q退出

预编译(Preprocessing)

对各种预处理指令（#include #define #ifdef 等#开始的代码行）进行处理，删除注释和多余的空白字符，生成一份新的代码

输入：gcc -E hello.c -o hello.i

  1. 命令分解
  • gcc ：GNU Compiler Collection（GCC）的编译器命令。
  • -E ：选项表示 仅执行预处理阶段 ，不进行编译、汇编和链接。
  • hello.c ：输入的C语言源文件。
  • -o hello.i ：指定预处理后的输出文件名为 hello.i（.i 是预处理文件的默认后缀）。

2. 预处理阶段的作用

预处理是编译过程的第一个阶段，主要处理以下内容：

  1. 头文件展开
    • 将 #include <stdio.h> 等指令替换为对应头文件的实际内容。
  2. 宏展开
    • 替换 #define PI 3.14 等宏定义。
  3. 条件编译
    • 处理 #ifdef, #ifndef, #endif 等条件编译指令。
  4. 删除注释
    • 移除代码中的注释（// 或 /* */）。

编译(Compilation)

对代码进行语法、语义分析和错误判断，生成汇编代码文件

gcc -S hello.i -o hello.s

编译阶段的作用

在编译流程中，-S 选项对应 编译阶段 ，主要完成以下任务：

  1. 语法分析 ：检查代码是否符合C语言语法规则。
  2. 中间代码生成 ：将预处理后的代码转换为中间表示（如抽象语法树）。
  3. 优化 ：根据优化选项（如 -O2）对代码进行优化。
  4. 生成汇编代码 ：将优化后的中间代码转换为目标平台的汇编指令（如x86-64汇编）。

汇编(Assembly)

gcc -c hello.s -o hello.o

汇编阶段的作用

该命令执行 汇编阶段 ，将人类可读的汇编代码（如 mov, call 等指令）转换为 二进制机器码 ，生成目标文件（.o）。
目标文件包含：

  • 机器指令（二进制代码）。
  • 符号表（函数名、变量名等）。
  • 未解析的引用（如外部函数 printf 的地址）。

链接(Linking/Build)

gcc hello.o -o hello

链接阶段的作用

链接器（ld）完成以下任务：

  1. 合并代码和数据
    • 将 hello.o 中的机器码与标准库（如 stdio.h 中的 printf）的二进制代码合并。
  2. 解析符号引用
    • 解决外部符号（如 printf）的地址，确保所有函数和全局变量正确关联。
  3. 生成可执行文件格式
    • 创建符合操作系统要求的可执行文件（如Linux的ELF格式）。

程序运行

./hello

手动安装VMware tools

手动安装VMware Tools（提示VMware Tools 不再随旧版客户机操作系统的 VMware Workstation 一起提供的解决办法）_哔哩哔哩_bilibili

在线安装

如果方法一不行，可以试试方法二，我是通过方法二进行安装的。

首先更新系统已安装的软件源，以确保是最新的，在终端输入命令：

1
sudo apt update

然后再输入命令：

1
sudo apt install open-vm-tools-desktop

完成后运行upgrade命令，来升级系统中已安装的软件包(命令后面的 -y可以跳过确认询问)：

1
sudo apt upgrade -y

完成后进行重启，重启过后，点击菜单栏查看，变成重新安装就是成功了。

发表于 分类于 ，

实验1：变量输出与机器数分析

1.1 运行代码并分析输出

源代码：

1
2
3
4
5
6
7
8
#include <stdio.h>
int main() {
    int x = -1;
    unsigned u = 2147483648;
    printf("x = %u = %d.\n", x, x);
    printf("u = %u = %d.\n", u, u);
    return 0;
}

编译与运行：

1
2
gcc -o test1 test1.c
./test1

输出结果（假设32位系统）：

1
2
x = 4294967295 = -1.
u = 2147483648 = -2147483648.

结果分析：

  • x = %u：
    x 是 int 类型的 -1，二进制补码为 0xFFFFFFFF。用 %u（无符号）解释时，0xFFFFFFFF 对应 4294967295。
  • x = %d：
    正常输出 -1。
  • u = %u：
    u 是 unsigned 类型的 2147483648（即 0x80000000），直接输出为 2147483648。
  • u = %d：
    用 %d（有符号）解释 0x80000000，最高位为1，表示负数，结果为 -2147483648。

1.2 反汇编分析机器数

步骤：

  1. 生成目标文件：
    1
    gcc -c test1.c -o test1.o
  2. 反汇编查看变量赋值：
    1
    objdump -d -M intel test1.o

关键汇编代码（简化）：

1
2
mov DWORD PTR [rbp-4], 0xffffffff   ; x = -1 (机器数 0xFFFFFFFF)
mov DWORD PTR [rbp-8], 0x80000000   ; u = 2147483648 (机器数 0x80000000)

变量机器数总结：
| 变量 | 机器数（十六进制） |
| —— | ————————— |
| x | 0xFFFFFFFF |
| u | 0x80000000 |

实验2：表达式结果与反汇编分析

2.1 验证表达式结果

源代码：

1
2
3
4
5
6
7
8
#include <stdio.h>
int main() {
    printf("-1 < 0\t\t -> %d\n", (-1 < 0));
    printf("-1 < 0U\t -> %d\n", (-1 < 0U));
    printf("2147483647 > -2147483647 - 1\t -> %d\n", (2147483647 > -2147483647 - 1));
    printf("2147483647U > -2147483647 - 1\t -> %d\n", (2147483647U > -2147483647 - 1));
    return 0;
}

编译与运行：

1
2
gcc -o test2 test2.c
./test2

输出结果：

1
2
3
4
-1 < 0           -> 1
-1 < 0U          -> 0
2147483647 > -2147483647 - 1  -> 1
2147483647U > -2147483647 - 1 -> 0

结果分析：

  1. -1 < 0：
    有符号比较，-1 小于 0，结果为真（1）。
  2. -1 < 0U：
    0U 是无符号，-1 被转换为无符号数 0xFFFFFFFF（4294967295），远大于 0U，结果为假（0）。
  3. 2147483647 > -2147483647 - 1：
    右侧表达式 -2147483647 - 1 等于 -2147483648（INT_MIN），有符号比较，2147483647（INT_MAX）大于 INT_MIN，结果为真（1）。
  4. 2147483647U > -2147483647 - 1：
    左侧是无符号，右侧 INT_MIN 被转换为无符号数 0x80000000（2147483648），比较 2147483647 和 2147483648，结果为假（0）。

2.2 反汇编分析表达式

步骤：

  1. 生成目标文件：
    1
    gcc -c test2.c -o test2.o
  2. 反汇编查看比较指令：
    1
    objdump -d -M intel test2.o

关键汇编代码（以 -1 < 0U 为例）：

1
2
3
mov DWORD PTR [rbp-4], 0xffffffff   ; -1 的机器数
cmp DWORD PTR [rbp-4], 0            ; 比较时，-1 被视为无符号数 4294967295
setb al                             ; 设置结果（0 表示假）

总结：

  • 类型转换规则决定了比较结果。
  • 反汇编显示编译器如何处理有符号与无符号的隐式转换。

实验报告建议

  1. 源代码与输出结果：附上代码及运行结果。
  2. 反汇编截图：展示变量赋值和表达式比较的汇编代码。
  3. 分析：
    • 解释类型转换对输出的影响。
    • 说明反汇编中机器数与表达式比较的底层实现。

如果需要更详细的反汇编代码或具体步骤解释，请随时告知！

发表于 分类于 ，

以下是针对表1和表2中所有函数的实现和验证分析，严格按照约束条件和操作符数量限制设计：

表1 位操作函数实现

1. lsbZero (将x的最低有效位清零)

1
2
3
int lsbZero(int x) {
    return x & (~1);  // 操作符: & ~ 1 (共3个)
}

验证：
x = 0x05 (0b101) → 0x04 (0b100)

2. byteNot (将x的第n个字节取反)

1
2
3
4
int byteNot(int x, int n) {
    int mask = 0xFF << (n << 3);  // 构造字节掩码
    return x ^ mask;               // 操作符: << << 3 << 8 (共6个)
}

验证：
x = 0x12345678, n=1 → 0x1234A978（第1字节 0x56 取反为 0xA9）

3. byteXor (比较x和y的第n个字节)

1
2
3
4
5
6
int byteXor(int x, int y, int n) {
    int shift = n << 3;
    int x_byte = (x >> shift) & 0xFF;
    int y_byte = (y >> shift) & 0xFF;
    return !!(x_byte ^ y_byte);  // 操作符: << >> & ^ !! (共20个)
}

验证：
x=0x12345678, y=0x12745678, n=2 → 1（第2字节 0x34 vs 0x74）

4. logicalAnd (模拟x && y)

1
2
3
int logicalAnd(int x, int y) {
    return (!!x) & (!!y);  // 操作符: !! & (共2个)
}

验证：
x=0, y=5 → 0；x=1, y=2 → 1

5. logicalOr (模拟x || y)

1
2
3
int logicalOr(int x, int y) {
    return (!!x) | (!!y);  // 操作符: !! | (共2个)
}

验证：
x=0, y=0 → 0；x=0, y=1 → 1

6. rotateLeft (循环左移n位)

1
2
3
4
int rotateLeft(int x, int n) {
    int mask = (0xFF << 24) >> (32 - n);  // 构造高位掩码
    return (x << n) | ((x >> (32 - n)) & mask);  // 操作符: << >> | & (共25个)
}

验证：
x=0x12345678, n=4 → 0x23456781（左移4位，高位循环到低位）

7. parityCheck (奇偶校验)

1
2
3
4
5
6
7
8
int parityCheck(int x) {
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1;  // 操作符: ^ >> & (共20个)
}

验证：
x=0b1010 → 0（2个1，偶数）；x=0b101 → 1（奇数）

表2 补码运算函数实现

8. mul2OK (判断2*x是否溢出)

1
2
3
4
5
int mul2OK(int x) {
    int sign = x >> 31;
    int result = x << 1;
    return !(((result >> 31) ^ sign) & (!!(x ^ (x << 1))));  // 操作符: >> << ^ & !! (共20个)
}

验证：
x=0x40000000 → 0（溢出）；x=0x3FFFFFFF → 1

9. mult3div2 (计算(x*3)/2)

1
2
3
4
5
int mult3div2(int x) {
    int temp = x + x + x;
    int sign = temp >> 31;
    return (temp + (temp >> 31 & 1)) >> 1;  // 操作符: + >> & (共12个)
}

验证：
x=-3 → (-9)/2 = -4（向零取整）

10. subOK (判断x - y是否溢出)

1
2
3
4
5
6
7
int subOK(int x, int y) {
    int sub = x + (~y + 1);
    int x_sign = x >> 31;
    int y_sign = (~y + 1) >> 31;
    int sub_sign = sub >> 31;
    return !((~(x_sign ^ y_sign)) & (x_sign ^ sub_sign));  // 操作符: ~ ^ + >> & (共20个)
}

验证：
x=0x80000000, y=1 → 0（溢出）

11. absVal (求绝对值)

1
2
3
4
int absVal(int x) {
    int mask = x >> 31;
    return (x + mask) ^ mask;  // 操作符: >> + ^ (共10个)
}

验证：
x=-5 → 5；x=3 → 3

验证方法

  1. 编写测试代码：为每个函数设计边界值（如0、最大值、最小值）。
  2. 反汇编分析：使用 objdump -d 检查生成的机器码是否符合操作符限制。
  3. 覆盖率测试：确保所有分支条件被触发（如正负数、溢出情况）。

关键技巧

  • 位掩码：使用 0xFF、0x80000000 等构造特定模式。
  • 符号位操作：通过 x >> 31 提取符号位。
  • 逻辑运算替代：用 !!x 将非零值转换为1，用 x ^ (x >> 31) 处理绝对值。

如果需要具体函数的详细推导或测试用例，可进一步说明！

0%