K-Means

模板题：K-Means Clustering

def k_means_clustering(points: list[tuple[float, float]], k: int, initial_centroids: list[tuple[float, float]], max_iterations: int) -> list[tuple[float, float]]:
    dist = np.zeros(len(points), dtype=np.int32) #points归属的中心点索引
    final_centroids=initial_centroids
    points=np.array(points)
    initial_centroids=np.array(initial_centroids)

    
    for _ in range(max_iterations):
        for i in range(len(points)):
            d=np.zeros(k) #到每个中心点的距离
            for j in range(k):
                d[j]=( ((points[i]-final_centroids[j]) ** 2).sum() )
            dist[i]=d.argmin()
        for kk in range(k):
            final_centroids[kk]= points[np.where(dist==kk)].mean(axis=0)


    return final_centroids

线性回归

正则法求 $\theta$

def linear_regression_normal_equation(X: list[list[float]], y: list[float]) -> list[float]:

    X=np.array(X)

    y=np.array(y)

    theta=np.linalg.solve(X.T @ X, X.T @ y)

    return theta

梯度下降法求 $\theta$

目标函数：$h_\theta(x) = a_1 * x_1 + a_2 * x_2 + … + b$

代价函 $J(\theta)$ 如下:

m: 样本数

化成矩阵的形式就是如下：

$$y_{pred}=X \times \theta, error=y_{pred}-y, $$

$$ gradient=(X.T \times error) /m$$

整体代码：

import numpy as np
def linear_regression_gradient_descent(X: np.ndarray, y: np.ndarray, alpha: float, iterations: int) -> np.ndarray:
    # Your code here, make sure to round
    m, n = X.shape
    theta = np.zeros((n, 1))
    #print(y)
    y=y.reshape(-1, 1)

    for _ in range(iterations):
        y_pred=X @ theta
        #print(y_pred)
        error=y_pred-y
        #print('error', error)
        gradient = (X.T @ error)/m
        #print(gradient)
        theta -= alpha * gradient 

    return theta

print(linear_regression_gradient_descent(np.array([[1, 1], [1, 2], [1, 3]]), np.array([1, 2, 3]), 0.01, 1000))

常数项处理（本质上可以融合进矩阵中，$b(x_b)$ 相当于 $sample_b * x_b$，只不过这个 $sample_b$ 一直都是1，等价于常数）

特征缩放

• 标准化和归一化

def feature_scaling(data: np.ndarray) -> (np.ndarray, np.ndarray):
    mean=data.mean(axis=0)
    std=data.std(axis=0)
    print(mean, std)
    standardized_data = (data - mean) / std
    
    minv=data.min(axis=0) 
    maxv=data.max(axis=0)
    normalized_data = (data - minv) / (maxv-minv)

    return standardized_data, normalized_data

data = np.array([[1, 2], [3, 4], [5, 6]])
feature_scaling(data)

###

线性代数

特征值

定义1：设 $A$ 是 $n$ 阶矩阵，如果数 $\lambda$ 和 $n$ 维非零 $\alpha$ 使关系式 $A\alpha = \lambda \alpha$成立，则这样的数称为方阵 $A$ 的特征值，非零向量 $\alpha$ 成为 $A$对应特征值 $\lambda$ 的特征向量。

1. 特征值 $\alpha \ne 0$，特征值问题是对方阵而言的。
2. $n$ 阶方阵 $A$ 的特征值，就是使齐次线性方程组 $(\lambda I -A)x=0$ 有非零解的 $\lambda$ 值，即满足方程 $\left| \lambda I – A \right| =0$ 的 $\lambda$ 都是矩阵 $A$ 的特征值。

定义2： $A$ 是 $n$ 阶矩阵，$\lambda I -A$ 为 $A$ 的特征矩阵，其行列式为 $\left| \lambda I – A \right|$ 的 $n$ 次多项式，称为 $A$ 的特征多项式，$\left| \lambda I – A \right| =0$ 称为 $A$ 的特征方程。

二阶方阵特征值求解例子

import numpy as np
import math

def calculate_eigenvalues(matrix) -> list[float]:
    a, b, c, d=matrix[0][0], matrix[0][1], matrix[1][0], matrix[1][1]

    theta = (a + d) ** 2 - 4 * (a*d-b*c)
    x1=((a + d) - theta ** 0.5)/2 
    x2=((a + d) + theta ** 0.5)/2

    return [max(x1, x2), min(x1, x2)]


matrix = [[2, 1], [1, 2]]

calculate_eigenvalues(matrix)

numpy求解：eigenvalues, eigenvectors = np.linalg.eig(matrix)

逆阵求法

伴随矩阵法和高斯消元法。有点麻烦，之后有需要再补。

协方差矩阵

• 对角线元素 $\Sigma_{ii}$ 是变量 $X_i$​ 的​​方差​​。
• 非对角线元素$\Sigma_{ij}$​ 是变量 $X_i$ 和 $X_j$​的​​协方差​​。

求法：$$\Sigma=\frac{1}{n-1}(X-\bar{X})^{T}(X-\bar{X})$$

• $\bar{X}$ 是每个变量的均值向量 ($1\times m$)。
• $X- \bar{X}$ 表示数据中心化（每个变量减去均值）。

Code

import numpy as np

# 假设 X 是（特征数，观测值），此时需要Transpose

def calculate_covariance_matrix(vectors: list[list[float]]) -> list[list[float]]:
	X=np.array(vectors).T
	X_b=X.mean(axis=0)

	res = (X-X_b).T @ (X-X_b) /(X.shape[0]-1)

	return res

vec=[[1, 2, 3],
	[4, 5, 6]]


calculate_covariance_matrix(vec)

SVD（奇异值分解）

numpy计算：U, S, Vh = np.linalg.svd(A, full_matrices=True)

手撕后补