目录

机器学习 ML

ML 23 k-means

ML24 交叉验证数据拆分

ML25 主成分分析 (PCA)

ML26 k近邻算法

深度学习

NLP287624 最优字符串对齐距离

NLP287602 实现TF-IDF

DL23 位置编码计算器

---

机器学习 ML

ML 23 k-means

法一：直接调用 sklearn.cluster 的 k_means

import numpy as np
from sklearn.cluster import k_means

def k_means_clustering(points, k, initial_centroids, max_iterations):

    # 中心点；标签；样本点到所属簇中心的距离平方和
    centroid, labels, inertia = k_means(
        points, k, init=np.array(initial_centroids), max_iter=max_iterations
    )

    ans = [] # 按题目要求，把结果点的坐标 原二维列表 -> 元组
    for p in centroid:
        p = p.round(4)
        ans.append(tuple(p))
    return ans

法二：手搓

每行是 中心点位置，每列是 points；

每一列 points 根据欧式距离，分配到最小距离的那个中心点。

对每个簇 取均值算新中心点；检查和之前是否重合。

def k_means_clustering(points, k, initial_centroids, max_iterations):
    points = np.array(points)
    centroids = np.array(initial_centroids)
     
    for _ in range(max_iterations):
        # Assign points to the nearest centroid
        distances = np.array([np.sqrt(((points - centroid) ** 2).sum(axis=1)) for centroid in centroids])
        assignments = np.argmin(distances, axis=0)
 
        new_centroids = np.array([points[assignments == i].mean(axis=0) if len(points[assignments == i]) > 0 else centroids[i] for i in range(k)])
         
        # Check for convergence
        if np.all(centroids == new_centroids):
            break
        centroids = np.round(new_centroids, 4)

    return [tuple(centroid) for centroid in centroids] 

ML24 交叉验证数据拆分

k 折每一次的 i，第 i 折作为测试集，其余前后拼接起来作为训练集。

预处理 先把每个子块的开始位置和结束位置；最后把 np 转换为 list。

def cross_validation_split(data, k, seed=42):
    np.random.seed(seed)
    np.random.shuffle(data)
    n, m = data.shape
    sub_size = int(np.ceil(n / k))
    
    # 每一子区间的开始和结束索引
    id_s = np.arange(0, n, sub_size)
    id_e = id_s + sub_size
    if id_e[-1] > n:
        id_e[-1] = n

    return [[np.concatenate([data[:id_s[i]], data[id_e[i]:]], axis=0).tolist(), data[id_s[i]: id_e[i]].tolist()] for i in range(k)]

ML25 主成分分析 (PCA)

对每列每个特征 标准化数据集，计算 X^T*X的协方差矩阵，

找到特征值和特征向量，返回主成分（与前 k 大特征值对应的特征向量）

def pca(data, k):
    data_standardized = (data - np.mean(data, axis=0)) / np.std(data, axis=0)
     
    covariance_matrix = np.cov(data_standardized, rowvar=False)
     
    eigenvalues, eigenvectors = np.linalg.eig(covariance_matrix)
    
    # 对特征值倒序索引以及对应向量
    idx = np.argsort(eigenvalues)[::-1]
    eigenvectors_sorted = eigenvectors[:,idx]
     
    principal_components = eigenvectors_sorted[:, :k]
     
    return np.round(principal_components, 4)

调用 sklearn；

from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler

def pca(data, k):

    # 检查k值是否有效
    n_samples, n_features = data.shape
    k = min(k, n_features)  # k不能超过特征数量
    
    # 1. 标准化数据
    scaler = StandardScaler()
    data_standardized = scaler.fit_transform(data)
    
    # 2. 创建PCA对象，指定主成分数量
    pca_ = PCA(n_components=k)
    
    # 3. 拟合数据
    pca_.fit(data_standardized)
    
    # 4. 获取主成分并调整格式
    components = pca_.components_.T  # 转置，使每列是一个主成分
    
    return np.round(components, 4)

ML26 k近邻算法

m行 m个样本，每个样本 n 个特征，一个标签。

找 test 的 k近邻，先求与每个样本距离差的二范数  axis = 1

-> 前 k 小的距离对应的索引和标签。

对得到的标签投片：均值 or 众数

def k_nearest_neighbors(X, y, test_sample, k):
    distances = np.linalg.norm(X - test_sample, axis=1)
    nearest_indices = np.argsort(distances)[:k]
    nearest_labels = y[nearest_indices]
    
    return int(np.round(np.mean(nearest_labels))) # 标签均值

    unique, counts = np.unique(nearest_labels, return_counts=True)
    return unique[np.argmax(counts)] # 

深度学习

NLP287624 最优字符串对齐距离

允许的编辑操作（每个操作代价为1）：
1. 插入一个字符
2. 删除一个字符
3. 替换一个字符
4. 交换相邻的两个字符 （比之前的编辑距离多了这个）

二维 dp 先初始化单边的 dp[0][i] = i

如果当前两个字母相同，一定就不改 dp[i-1][j-1]

否则 增删改 分别对应 (i-1,j)  (i,j-1)   (i-1,j-1)

交换两个字符，仅在 最后两个字符正好对应的倒序这个操作才有意义，额外判断。

def OSA(source: str, target: str) -> int:
    n, m = len(source), len(target)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(m):
        dp[0][i] = i
    for i in range(n):
        dp[i][0] = i

    for i in range(1,n+1):
        for j in range(1,m+1):
            if source[i-1] == target[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
            if i>1 and j>1 and source[i-1] == target[j-2] and source[i-2] == target[j-1]:
                dp[i][j] = min(dp[i][j],dp[i-2][j-2]+1)
    return dp[-1][-1]

NLP287602 实现TF-IDF

评估一个词对于文档集中的某个文档的重要程度。TF * IDF

TF = 词在文档中出现次数 / 文档总词数
IDF = log((文档总数 + 1) / (包含该词的文档数 + 1)) + 1

1. 建立词典和索引

2. 按每个文档 统计每个词的频率 -> TF

3. TF 的（每个词）列非零出现在多少文档 -> IDF

最终把 query 中词对应索引的那些列输出。

def compute_tf_idf(corpus, query):
	# 文档和问题的并集 ->  所有词的词表，建立索引到词的映射
    vocab = sorted(set(word for document in corpus for word in document).union(query))
    word_to_index = {word: idx for idx, word in enumerate(vocab)}

	# 文档 - 词
    tf = np.zeros((len(corpus), len(vocab)))

    for doc_idx, document in enumerate(corpus):
        for word in document:
            word_idx = word_to_index[word]
            tf[doc_idx, word_idx] += 1
		# 统计每个文档中 每个词的词频，再除以文档长度
        tf[doc_idx, :] /= len(document)

	# 每列（每个词）多少个文档中出现
    df = np.count_nonzero(tf > 0, axis=0)
    num_docs = len(corpus)
    idf = np.log((num_docs + 1) / (df + 1)) + 1
    tf_idf = tf * idf

	# 输出 query 对应列的情况
    query_indices = [word_to_index[word] for word in query]
    return np.round(tf_idf[:, query_indices], 5).tolist()

DL23 位置编码计算器

PE(pos, 2i)   = sin(pos / 10000^(2i/d_model))    # 偶数维度
PE(pos, 2i+1) = cos(pos / 10000^(2i/d_model))    # 奇数维度

位置为分子，维度为分母（变化快慢不一样）

就像 sin (w*pos) ，不同维度的系数 w 不一样。

每行pos，每列维度，计算角度矩阵。偶项正弦，奇项余弦，拼接转换为 float16.

def pos_encoding(position: int, d_model: int):
    # 检查
    if position == 0 or d_model <= 0:
        return np.array(-1)

    # 初始化位置 列向量 pos 和 行向量 ind
    pos = np.array(np.arange(position), np.float32)
    ind = np.array(np.arange(d_model), np.float32)
    pos = pos.reshape(-1, 1)
    ind = ind.reshape(1, -1)

    # 计算角度
    angle1 = pos / np.power(10000, (2 * (ind // 2)) / np.float32(d_model))

    # 拼接正弦和余弦
    sine = np.sin(angle1[:, 0::2])
    cosine = np.cos(angle1[:, 1::2])
    pos_encoding = np.concatenate([sine, cosine], axis=-1)
    
    # 转换为16位浮点数
    return np.float16(pos_encoding)