0X. ML Coding

import numpy as np


def kmeans(X, k, max_iter=100):
    # 1. 随便选 k 个点当中心（最简单的初始化）
    centroids = X[np.random.choice(X.shape[0], k, replace=False)]

    for _ in range(max_iter):
        # 2. 算距离，找归属（这步最容易写晕）
        distances = np.sum((X[:, None, :] - centroids[None, :, :]) ** 2, axis=2)
        labels = np.argmin(distances, axis=1)

        # 3. 更新中心
        new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])

        # 4. 如果中心不动了，就停止
        if np.all(centroids == new_centroids):
            break
        centroids = new_centroids

    return labels, centroids

def kmeans_pp_init(X, k, rng=None):
    rng = np.random.default_rng() if rng is None else rng
    n = X.shape[0]
    centroids = [X[rng.integers(n)]]                     # 1. 随机第一个中心
    for _ in range(1, k):
        # 每个点到「最近已选中心」的平方距离 D(x)^2
        d2 = np.min([((X - c) ** 2).sum(axis=1) for c in centroids], axis=0)
        probs = d2 / d2.sum()                            # 2-3. 正比于 D(x)^2 的概率
        centroids.append(X[rng.choice(n, p=probs)])
    return np.array(centroids, dtype=float)

import numpy as np


class KMeans:
    def __init__(self, n_clusters, max_iter=100, tol=1e-4, random_state=None):
        self.n_clusters = n_clusters
        self.max_iter = max_iter
        self.tol = tol
        self.random_state = random_state
        self.centroids = None
        self.inertia_ = None

    def _init_centroids(self, X):
        rng = np.random.default_rng(self.random_state)
        n_samples = X.shape[0]
        if self.n_clusters > n_samples:
            raise ValueError("n_clusters cannot exceed n_samples")
        indices = rng.choice(n_samples, size=self.n_clusters, replace=False)
        return X[indices].astype(float)

    def _assign(self, X, centroids):
        # squared distances: shape (n_samples, n_clusters)
        distances = ((X[:, None, :] - centroids[None, :, :]) ** 2).sum(axis=2)
        return np.argmin(distances, axis=1), distances

    def _update(self, X, labels, old_centroids):
        new_centroids = np.empty_like(old_centroids)
        for k in range(self.n_clusters):
            points = X[labels == k]
            if len(points) == 0:
                # Empty-cluster fallback: keep the previous centroid.
                # Other choices: reinitialize to farthest point or random point.
                new_centroids[k] = old_centroids[k]
            else:
                new_centroids[k] = points.mean(axis=0)
        return new_centroids

    def fit(self, X):
        X = np.asarray(X, dtype=float)
        centroids = self._init_centroids(X)

        for _ in range(self.max_iter):
            labels, distances = self._assign(X, centroids)
            new_centroids = self._update(X, labels, centroids)

            shift = np.linalg.norm(new_centroids - centroids)
            centroids = new_centroids
            if shift < self.tol:
                break

        labels, distances = self._assign(X, centroids)
        self.centroids = centroids
        self.inertia_ = distances[np.arange(X.shape[0]), labels].sum()
        return self

    def predict(self, X):
        if self.centroids is None:
            raise RuntimeError("Call fit before predict.")
        X = np.asarray(X, dtype=float)
        labels, _ = self._assign(X, self.centroids)
        return labels

np.random.seed(42)
X = np.random.rand(100, 2)

model = KMeans(n_clusters=3, random_state=42)
model.fit(X)

print(model.centroids)
print(model.inertia_)

import numpy as np


def logistic_regression_train(X, y, lr=0.1, max_iter=1000):
    n_samples, n_features = X.shape
    w = np.zeros(n_features)
    b = 0.0

    for _ in range(max_iter):
        z = X @ w + b                  # 1. 前向：线性分数
        y_pred = sigmoid(z)            # 2. 过 Sigmoid 变概率

        # 3. 梯度（求导后非常干净：预测值 - 真实值）
        dw = (1 / n_samples) * (X.T @ (y_pred - y))
        db = (1 / n_samples) * np.sum(y_pred - y)

        # 4. 梯度下降更新
        w -= lr * dw
        b -= lr * db

    return w, b

import numpy as np


def sigmoid(z):
    z = np.asarray(z)
    out = np.empty_like(z, dtype=float)   # 创建一个和 z 维度相同、用来装结果的空数组

    pos = z >= 0    # 找到所有 >= 0 的位置（布尔掩码 Boolean Mask）
    neg = ~pos      # 找到所有 < 0 的位置（按位取反）

    # 1. 正数区域：用 1 / (1 + exp(-z))，此时 exp(-z) <= 1，不会溢出
    out[pos] = 1.0 / (1.0 + np.exp(-z[pos]))

    # 2. 负数区域：用 exp(z) / (1 + exp(z))，此时 exp(z) < 1，同样不会溢出
    exp_z = np.exp(z[neg])
    out[neg] = exp_z / (1.0 + exp_z)

    return out

def binary_cross_entropy_with_logits(logits, y):
    """稳定形式：max(z, 0) - z*y + log(1 + exp(-|z|))；直接吃 logits，不要先算概率"""
    logits = np.asarray(logits, dtype=float)
    y = np.asarray(y, dtype=float)

    # -np.abs(logits) 保证指数恒为负 → exp 落在 (0, 1]，永不溢出
    # np.log1p(t) 算的是 log(1+t)，t 很小时比 np.log(1+t) 精度高得多
    loss = np.maximum(logits, 0) - logits * y + np.log1p(np.exp(-np.abs(logits)))
    return loss.mean()          # 对 batch 求平均


class LogisticRegressionGD:
    def __init__(self, lr=0.1, max_iter=1000, l2=0.0, fit_intercept=True):
        self.lr = lr                      # 学习率
        self.max_iter = max_iter          # 迭代轮数
        self.l2 = l2                      # L2 正则强度，0 表示不加正则
        self.fit_intercept = fit_intercept
        self.w = None
        self.loss_history = []            # 记录每轮 loss，用来画收敛曲线 / 调试

    def _add_intercept(self, X):
        """在 X 最左边拼一列全 1，把截距 b 吸收成 w[0]，公式简化为纯矩阵乘"""
        if not self.fit_intercept:
            return X
        ones = np.ones((X.shape[0], 1))
        return np.hstack([ones, X])

    def fit(self, X, y):
        X = np.asarray(X, dtype=float)
        y = np.asarray(y, dtype=float).reshape(-1)   # 拉平成 (n,)，防止 (n,1) 触发广播 bug
        Xb = self._add_intercept(X)

        n_samples, n_features = Xb.shape
        self.w = np.zeros(n_features)     # BCE + 线性 logit 是凸问题，零初始化就够
        self.loss_history = []

        for _ in range(self.max_iter):
            logits = Xb @ self.w          # 1. 前向只算到 logits，不提前求概率
            probs = sigmoid(logits)       # 2. 转成概率

            # 3. 梯度：对 logits 求导后是 (p - y)，链式回到 w 就是 X^T (p - y) / n
            grad = Xb.T @ (probs - y) / n_samples

            if self.l2 > 0:               # 4. L2 正则的梯度就是 lambda * w
                reg = self.w.copy()
                if self.fit_intercept:
                    reg[0] = 0.0          # 截距不参与正则（它只是整体基准，不该被收缩）
                grad += self.l2 * reg

            self.w -= self.lr * grad      # 5. 梯度下降更新

            # 6. 用更新后的参数记录 loss，曲线才反映当前模型
            logits = Xb @ self.w
            loss = binary_cross_entropy_with_logits(logits, y)
            if self.l2 > 0:               # 正则项也要计入 loss，否则曲线和目标函数对不上
                reg_w = self.w[1:] if self.fit_intercept else self.w
                loss += 0.5 * self.l2 * np.dot(reg_w, reg_w)
            self.loss_history.append(loss)

        return self

    def predict_proba(self, X):
        """输出正类概率，落在 (0, 1)"""
        X = np.asarray(X, dtype=float)
        Xb = self._add_intercept(X)
        return sigmoid(Xb @ self.w)

    def predict(self, X, threshold=0.5):
        """阈值默认 0.5，但生产中应由 precision/recall 的业务成本决定"""
        return (self.predict_proba(X) >= threshold).astype(int)

np.random.seed(42)
X = np.random.randn(100, 2)
true_w = np.array([1.0, -2.0])
logits = X @ true_w + 0.2
y = (sigmoid(logits) > 0.5).astype(int)

model = LogisticRegressionGD(lr=0.1, max_iter=1000, l2=1e-3)
model.fit(X, y)

pred = model.predict(X)
print("accuracy:", (pred == y).mean())
print("weights:", model.w)

import numpy as np


def linear_regression(X, y):
    # 左边拼一列 1 当截距项：b 变成权重向量的第 0 项
    Xb = np.hstack([np.ones((X.shape[0], 1)), X])
    # lstsq 基于 SVD，比显式求逆稳定得多
    theta, *_ = np.linalg.lstsq(Xb, y, rcond=None)
    return theta                        # theta[0] 是截距 b，其余是各特征权重

import numpy as np


class LinearRegressionClosedForm:
    def __init__(self, fit_intercept=True):
        self.fit_intercept = fit_intercept
        self.theta = None                 # 拟合后是长度 (n_features + 1) 的权重向量

    def _add_intercept(self, X):
        """拼一列全 1，让截距 b 变成 theta[0]"""
        if not self.fit_intercept:
            return X
        ones = np.ones((X.shape[0], 1))
        return np.hstack([ones, X])

    def fit(self, X, y):
        X = np.asarray(X, dtype=float)
        y = np.asarray(y, dtype=float)
        Xb = self._add_intercept(X)

        # 比显式算 inv(X.T @ X) 稳得多；rcond=None 采用新版默认的奇异值截断规则
        # 返回值依次是：解、残差平方和、X 的秩、奇异值
        self.theta, residuals, rank, singular_values = np.linalg.lstsq(
            Xb, y, rcond=None
        )
        # rank < Xb.shape[1] 就说明特征间存在完全共线，此时解不唯一
        return self

    def predict(self, X):
        X = np.asarray(X, dtype=float)
        Xb = self._add_intercept(X)       # 预测时也必须拼同样的一列 1
        return Xb @ self.theta

X = np.array([
    [1, 2],
    [2, 3],
    [3, 4],
    [4, 5],
    [5, 6],
])
y = np.array([5, 7, 9, 11, 13])

model = LinearRegressionClosedForm()
model.fit(X, y)

X_new = np.array([
    [6, 7],
    [7, 8],
])

print("theta:", model.theta)
print("pred:", model.predict(X_new))

def ridge_regression(X, y, alpha=1.0, fit_intercept=True):
    X = np.asarray(X, dtype=float)
    y = np.asarray(y, dtype=float)
    if fit_intercept:
        Xb = np.hstack([np.ones((X.shape[0], 1)), X])   # 拼截距列
    else:
        Xb = X

    n_features = Xb.shape[1]
    reg = alpha * np.eye(n_features)      # alpha * I，加在 X^T X 的对角线上
    if fit_intercept:
        reg[0, 0] = 0.0                   # 截距项不正则化

    # 用 solve 而不是 inv：解方程比求逆更稳、更快
    theta = np.linalg.solve(Xb.T @ Xb + reg, Xb.T @ y)
    return theta

def polynomial_regression_1d(x, y, degree=3):
    # x: (N,) 一维数据；把 x 变成矩阵 [1, x, x^2, x^3]
    # x**0 刚好全是 1，顺便把截距项也搞定了
    X_poly = np.column_stack([x ** i for i in range(degree + 1)])

    # X_poly 形状 (N, degree+1)，完全变成了多元线性回归
    theta, *_ = np.linalg.lstsq(X_poly, y, rcond=None)
    return theta

import numpy as np


def softmax(x, axis=-1):
    x = np.asarray(x, dtype=float)

    # 减去每行最大值：数学上完全等价，但把最大的指数压成 e^0 = 1，杜绝上溢
    x_shifted = x - np.max(x, axis=axis, keepdims=True)
    exp_x = np.exp(x_shifted)

    # keepdims=True 保留被求和的那一维（(batch, 1) 而不是 (batch,)），否则广播会错位
    return exp_x / exp_x.sum(axis=axis, keepdims=True)

def softmax(x):            # 只对「一维向量」正确
    x = x - np.max(x)
    e = np.exp(x)
    return e / e.sum()

def cross_entropy_from_logits(logits, y):
    """
    logits: shape (batch, num_classes)，未经 softmax 的原始分数
    y:      shape (batch,)，整数类别标签（不是 one-hot）
    """
    logits = np.asarray(logits, dtype=float)
    y = np.asarray(y, dtype=int)

    # 1. 同样先减每行最大值做稳定化
    shifted = logits - logits.max(axis=1, keepdims=True)

    # 2. log-softmax：log(e^s / Σe^s) = s - log(Σe^s)，全程没有除法、也不会 log(0)
    log_probs = shifted - np.log(np.exp(shifted).sum(axis=1, keepdims=True))

    # 3. 花式索引取出每个样本真实类别那一项：第 i 行取第 y[i] 列
    #    等价于「和 one-hot 相乘再求和」，但不必真的构造 one-hot 矩阵
    return -log_probs[np.arange(logits.shape[0]), y].mean()

import numpy as np


def softmax(x, axis=-1):
    x = x - np.max(x, axis=axis, keepdims=True)     # 稳定化：减去每行最大值
    exp_x = np.exp(x)
    return exp_x / np.sum(exp_x, axis=axis, keepdims=True)


def scaled_dot_product_attention(Q, K, V, mask=None):
    """
    Q: shape (batch, q_len, d_k)
    K: shape (batch, kv_len, d_k)
    V: shape (batch, kv_len, d_v)
    mask: optional, broadcastable to (batch, q_len, kv_len).
          本实现约定 True = 该位置可见（不同框架约定相反，面试务必说清）

    Returns:
        output: shape (batch, q_len, d_v)
        weights: shape (batch, q_len, kv_len)
    """
    d_k = Q.shape[-1]

    # 1. 打分并缩放：swapaxes(-1,-2) 是转置最后两维，(q_len,d_k)@(d_k,kv_len) -> (q_len,kv_len)
    #    除 sqrt(d_k)：点积是 d_k 项之和、方差随维度线性增长，不缩放会让 softmax 饱和、梯度消失
    scores = Q @ np.swapaxes(K, -1, -2) / np.sqrt(d_k)

    # 2. 屏蔽：把不可见位置换成一个极小值，softmax 后权重 ≈ 0
    #    必须在 softmax 之前做，否则归一化分母里仍混进了这些位置
    if mask is not None:
        scores = np.where(mask, scores, -1e9)

    # 3. 沿 kv_len 维归一化：每个 query 对所有 key 的注意力加起来为 1
    weights = softmax(scores, axis=-1)

    # 4. 用权重加权求和 V，得到每个 query 位置的输出
    output = weights @ V
    return output, weights

def causal_mask(q_len, kv_len=None):
    if kv_len is None:
        kv_len = q_len
    # np.tril 取下三角（含对角线）：第 i 行只有前 i+1 列为 True
    # 即位置 i 只能看到 <= i 的位置，看不到未来
    return np.tril(np.ones((q_len, kv_len), dtype=bool))


batch, seq_len, d_model = 2, 4, 8
Q = np.random.randn(batch, seq_len, d_model)
K = np.random.randn(batch, seq_len, d_model)
V = np.random.randn(batch, seq_len, d_model)

mask = causal_mask(seq_len)[None, :, :]
out, weights = scaled_dot_product_attention(Q, K, V, mask=mask)

print(out.shape)      # (2, 4, 8)
print(weights.shape)  # (2, 4, 4)

import numpy as np


def multi_head_attention_core(Q, K, V, num_heads):
    batch_size, seq_len, d_model = Q.shape
    d_k = d_model // num_heads  # 每个头分到的维度（比如 512 / 8 = 64）

    # 1. split_head：把 [batch, seq, d_model] 变成 [batch, num_heads, seq, d_k]
    # （实际代码中通常先通过线性层 Linear 投影，再 reshape）
    Q = Q.reshape(batch_size, seq_len, num_heads, d_k).swapaxes(1, 2)
    K = K.reshape(batch_size, seq_len, num_heads, d_k).swapaxes(1, 2)
    V = V.reshape(batch_size, seq_len, num_heads, d_k).swapaxes(1, 2)

    # 2. 丢进 Attention 核心（num_heads 个头同时并行计算）
    scores = (Q @ K.swapaxes(-1, -2)) / np.sqrt(d_k)
    weights = np.exp(scores - np.max(scores, axis=-1, keepdims=True))
    weights = weights / np.sum(weights, axis=-1, keepdims=True)

    out = weights @ V  # 形状是 [batch, num_heads, seq_len, d_k]

    # 3. concat（拼回去）：把 head 和 d_k 重新合体变回 [batch, seq_len, d_model]
    out = out.swapaxes(1, 2).reshape(batch_size, seq_len, d_model)

    return out

import numpy as np


def split_heads(x, num_heads):
    """
    切蛋糕：把 d_model 平分给 num_heads 个头
    x: shape (batch, seq_len, d_model)
    return: shape (batch, num_heads, seq_len, d_head)
    """
    batch, seq_len, d_model = x.shape
    assert d_model % num_heads == 0          # 必须整除，否则没法平分
    d_head = d_model // num_heads

    # 先把最后一维拆成 (num_heads, d_head)
    x = x.reshape(batch, seq_len, num_heads, d_head)
    # 再把 num_heads 换到前面 —— 让它变成"批次维"，后面 h 个头就能并行算 attention
    return np.transpose(x, (0, 2, 1, 3))


def combine_heads(x):
    """
    拼回去：split_heads 的逆操作
    x: shape (batch, num_heads, seq_len, d_head)
    return: shape (batch, seq_len, d_model)
    """
    batch, num_heads, seq_len, d_head = x.shape
    x = np.transpose(x, (0, 2, 1, 3))        # 先把 seq_len 换回第 1 维
    return x.reshape(batch, seq_len, num_heads * d_head)   # 再把 h 个头首尾相接


def multi_head_attention(X, Wq, Wk, Wv, Wo, num_heads, mask=None):
    """
    X: shape (batch, seq_len, d_model)
    Wq/Wk/Wv/Wo: shape (d_model, d_model)
    mask: optional, shape broadcastable to (batch, num_heads, seq_len, seq_len)
    """
    # 1. 三次线性投影，把同一个 X 变成 Q/K/V 三种视角（三组权重互相独立，不共享）
    Q = X @ Wq
    K = X @ Wk
    V = X @ Wv

    # 2. 切成多头：注意是先投影再切，等价于每个头有自己的小投影矩阵
    Q = split_heads(Q, num_heads)
    K = split_heads(K, num_heads)
    V = split_heads(V, num_heads)

    # 3. 每个头各算各的 attention。这里 d_head = d_model / h，
    #    所以缩放用的是 sqrt(d_head) 而不是 sqrt(d_model)
    d_head = Q.shape[-1]
    scores = Q @ np.swapaxes(K, -1, -2) / np.sqrt(d_head)

    if mask is not None:
        scores = np.where(mask, scores, -1e9)

    weights = softmax(scores, axis=-1)
    context = weights @ V                    # (batch, num_heads, seq_len, d_head)

    # 4. 拼回 d_model，再过输出投影 Wo 把各头的结论融合起来
    #    没有 Wo 的话各头结果只是简单并排堆着，从未交互
    context = combine_heads(context)
    return context @ Wo, weights

batch, seq_len, d_model, num_heads = 2, 5, 16, 4
X = np.random.randn(batch, seq_len, d_model)

Wq = np.random.randn(d_model, d_model) / np.sqrt(d_model)
Wk = np.random.randn(d_model, d_model) / np.sqrt(d_model)
Wv = np.random.randn(d_model, d_model) / np.sqrt(d_model)
Wo = np.random.randn(d_model, d_model) / np.sqrt(d_model)

mask = causal_mask(seq_len)[None, None, :, :]
out, weights = multi_head_attention(X, Wq, Wk, Wv, Wo, num_heads, mask=mask)

print(out.shape)      # (2, 5, 16)
print(weights.shape)  # (2, 4, 5, 5)

import numpy as np


def apply_rope(x, freq_base=10000.0):
    """
    x: (batch_size, seq_len, num_heads, d_k)，d_k 必须是偶数（两两配对做二维旋转）
    """
    batch_size, seq_len, num_heads, d_k = x.shape
    assert d_k % 2 == 0, "d_k 必须是偶数才能进行两两旋转"

    # 1. 每个特征对的旋转频率 theta_i = base^(-2i/d_k)
    i = np.arange(0, d_k, 2)
    theta = 1.0 / (freq_base ** (i / d_k))          # (d_k/2,)

    # 2-3. 位置索引 m 与角度 m*theta 的外积
    m = np.arange(seq_len)
    freqs = np.outer(m, theta)                      # (seq_len, d_k/2)

    # 4. cos/sin 各复制一遍，对齐交错排列的 d_k 维
    cos_val = np.repeat(np.cos(freqs), 2, axis=-1)[None, :, None, :]   # (1, seq_len, 1, d_k)
    sin_val = np.repeat(np.sin(freqs), 2, axis=-1)[None, :, None, :]

    # 5. 旋转：对每一对 (x_even, x_odd) 做 x*cos + (-x_odd, x_even)*sin
    swapped = np.stack([-x[..., 1::2], x[..., ::2]], axis=-1)
    swapped = swapped.reshape(batch_size, seq_len, num_heads, d_k)

    return x * cos_val + swapped * sin_val

import numpy as np


def layer_norm(x, gamma, beta, eps=1e-5):
    """
    x: (batch_size, seq_len, d_model)
    gamma, beta: (d_model,) 可学习缩放与偏移
    """
    mean = np.mean(x, axis=-1, keepdims=True)       # 沿特征维
    variance = np.var(x, axis=-1, keepdims=True)
    x_norm = (x - mean) / np.sqrt(variance + eps)   # eps 防止分母为 0
    return gamma * x_norm + beta

import numpy as np


def beam_search(step_fn, start_token, eos_token, beam_size=3, max_len=10,
                length_penalty=0.0):
    """
    step_fn(seq) -> 长度为 vocab 的 log-prob 向量（给定已生成序列，预测下一个 token）
    返回得分最高的 (score, seq)
    """
    beams = [(0.0, [start_token])]      # (累计 log-prob, 序列)
    finished = []

    for _ in range(max_len):
        candidates = []
        for score, seq in beams:
            if seq[-1] == eos_token:                       # 已结束，移入 finished
                finished.append((score, seq))
                continue
            log_probs = step_fn(seq)
            for tok in np.argsort(log_probs)[-beam_size:]:  # 每束只展开 top-k
                candidates.append((score + log_probs[tok], seq + [int(tok)]))

        if not candidates:
            break
        candidates.sort(key=lambda t: t[0], reverse=True)
        beams = candidates[:beam_size]                      # 全局剪枝回 k 条

    finished.extend(beams)

    def norm(item):                                         # 长度惩罚
        s, seq = item
        return s / (len(seq) ** length_penalty) if length_penalty else s

    return max(finished, key=norm)

import numpy as np


def softmax(x):
    """这里输入是单条一维 logits，所以可以用不带 axis 的简版（见第 4 节的说明）"""
    x = x - np.max(x)
    e = np.exp(x)
    return e / e.sum()


def top_k_sampling(logits, k=50, temperature=1.0, rng=None):
    """logits: shape (vocab,)；返回采样得到的 token id"""
    rng = rng or np.random.default_rng()

    # 温度缩放要在 softmax 之前作用于 logits；max(..., 1e-8) 防止 T=0 时除零
    logits = np.asarray(logits, dtype=float) / max(temperature, 1e-8)

    k = min(k, logits.size)                     # k 比词表还大时退化成全采样
    # argpartition 只保证第 k 大的元素就位、左右两边各自不排序，O(V) 比全排序 O(VlogV) 快
    idx = np.argpartition(logits, -k)[-k:]      # 取最大的 k 个的下标
    probs = softmax(logits[idx])                # 只在候选集内归一化（截断后必须重新归一）
    return int(rng.choice(idx, p=probs))


def top_p_sampling(logits, p=0.9, temperature=1.0, rng=None):
    """核采样：取累计概率刚好超过 p 的最小候选集"""
    rng = rng or np.random.default_rng()
    logits = np.asarray(logits, dtype=float) / max(temperature, 1e-8)

    probs = softmax(logits)
    order = np.argsort(probs)[::-1]             # 从大到小
    cumsum = np.cumsum(probs[order])

    cutoff = np.searchsorted(cumsum, p) + 1     # 至少保留 1 个
    idx = order[:cutoff]

    kept = probs[idx] / probs[idx].sum()        # 截断后重新归一化
    return int(rng.choice(idx, p=kept))

import numpy as np


def calculate_entropy(y):
    # y 是标签数组，比如 [0, 0, 1, 1, 1]
    n_samples = len(y)
    if n_samples == 0:
        return 0.0

    _, counts = np.unique(y, return_counts=True)   # 统计各类别频次
    probabilities = counts / n_samples
    # 核心公式：Entropy = - sum(p * log2(p))；np.unique 保证 p>0
    return -np.sum(probabilities * np.log2(probabilities))


def information_gain(y_parent, y_left, y_right):
    n = len(y_parent)
    # 子节点熵的加权平均，权重是落进该子节点的样本占比
    # 必须加权：否则一个只有 2 个样本的纯净子节点会把整个分裂的评分骗高
    child = (len(y_left) / n) * calculate_entropy(y_left) \
          + (len(y_right) / n) * calculate_entropy(y_right)
    # 切分前的混乱度 - 切分后的期望混乱度，越大说明这一刀切得越有效
    return calculate_entropy(y_parent) - child

from sklearn.svm import SVC

clf = SVC(kernel='rbf', C=1.0)     # RBF（高斯核）支持向量机
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)

import numpy as np


def cosine_similarity(a, b, eps=1e-8):
    """两个一维向量的余弦相似度"""
    a = np.asarray(a, dtype=float)
    b = np.asarray(b, dtype=float)
    return float(a @ b / (np.linalg.norm(a) * np.linalg.norm(b) + eps))


def cosine_similarity_matrix(A, B, eps=1e-8):
    """
    A: shape (n, d)  B: shape (m, d)
    返回 shape (n, m)，A 中每一行与 B 中每一行的相似度
    """
    A = np.asarray(A, dtype=float)
    B = np.asarray(B, dtype=float)

    A_norm = A / (np.linalg.norm(A, axis=1, keepdims=True) + eps)
    B_norm = B / (np.linalg.norm(B, axis=1, keepdims=True) + eps)
    return A_norm @ B_norm.T          # 归一化之后，内积就是余弦

import numpy as np


def precision_recall(y_true, y_pred, eps=1e-12):
    """二分类，标签为 0/1；返回 precision、recall、f1"""
    y_true = np.asarray(y_true).astype(int)
    y_pred = np.asarray(y_pred).astype(int)

    tp = int(np.sum((y_pred == 1) & (y_true == 1)))
    fp = int(np.sum((y_pred == 1) & (y_true == 0)))
    fn = int(np.sum((y_pred == 0) & (y_true == 1)))

    precision = tp / (tp + fp + eps)
    recall = tp / (tp + fn + eps)
    f1 = 2 * precision * recall / (precision + recall + eps)
    return precision, recall, f1


def precision_recall_multiclass(y_true, y_pred, num_classes, average='macro'):
    """多分类：对每个类别做一次 one-vs-rest，再平均"""
    scores = []
    weights = []
    for c in range(num_classes):
        p, r, f = precision_recall(y_true == c, y_pred == c)
        scores.append((p, r, f))
        weights.append(np.sum(y_true == c))

    scores = np.array(scores, dtype=float)
    if average == 'macro':                       # 每类等权，小类同样重要
        return tuple(scores.mean(axis=0))
    weights = np.array(weights, dtype=float)     # weighted：按样本数加权
    return tuple(scores.T @ weights / weights.sum())