从零实现5大机器学习基础算法：Python代码与数学推导

1. 从零实现机器学习基础算法的必要性在机器学习领域调用现成的库如scikit-learn固然方便但真正理解算法本质的开发者都会选择自己动手实现一遍。这就像学习烹饪时从切菜开始准备食材比直接使用预制菜更能掌握料理的精髓。自己动手实现基础算法有三个不可替代的价值深入理解数学原理每个公式都会转化为具体的代码逻辑掌握实现细节了解算法在各种边界条件下的表现培养工程能力从理论到实践的完整闭环训练Python作为机器学习的主流语言其清晰的语法和丰富的科学计算生态NumPy、Matplotlib特别适合用来实现这些算法。下面我将带您完整实现5个最基础的机器学习算法包括它们的数学推导和Python实现技巧。2. 准备工作与环境搭建2.1 基础工具链配置推荐使用Python 3.8环境这是目前最稳定的版本。我们需要以下基础库pip install numpy matplotlib注意虽然可以单独实现所有数学运算但使用NumPy不仅能提高性能其API设计也更贴近数学表达形式方便我们验证实现的正确性。2.2 测试数据集准备为了方便验证算法效果我们准备两个经典数据集线性回归测试数据使用正弦函数加噪声生成def make_regression_data(n_samples100): X np.linspace(0, 2*np.pi, n_samples) y np.sin(X) np.random.normal(0, 0.1, n_samples) return X.reshape(-1,1), y分类测试数据使用sklearn的make_classification生成仅用于测试不用于算法实现from sklearn.datasets import make_classification X, y make_classification(n_features2, n_redundant0, n_informative2)3. 线性回归实现3.1 数学原理推导普通最小二乘法(OLS)的目标是最小化残差平方和 $$ \min_w |Xw - y|_2^2 $$其解析解为 $$ w (X^TX)^{-1}X^Ty $$3.2 Python实现代码class LinearRegression: def __init__(self): self.w None def fit(self, X, y): # 添加偏置项 X np.hstack([np.ones((X.shape[0], 1)), X]) # 计算解析解 self.w np.linalg.inv(X.T X) X.T y def predict(self, X): X np.hstack([np.ones((X.shape[0], 1)), X]) return X self.w3.3 梯度下降实现当数据量较大时可以使用梯度下降法def fit_gd(self, X, y, lr0.01, n_iters1000): X np.hstack([np.ones((X.shape[0], 1)), X]) self.w np.zeros(X.shape[1]) for _ in range(n_iters): grad 2 * X.T (X self.w - y) / len(y) self.w - lr * grad实操技巧学习率(lr)通常从0.01开始尝试观察损失函数下降曲线调整4. 逻辑回归实现4.1 Sigmoid函数与决策边界逻辑回归使用sigmoid函数将线性输出映射到(0,1)区间 $$ \sigma(z) \frac{1}{1e^{-z}} $$决策边界为 $$ w^Tx b 0 $$4.2 交叉熵损失函数损失函数定义为 $$ J(w) -\frac{1}{m}\sum_{i1}^m [y^{(i)}\log(h(x^{(i)})) (1-y^{(i)})\log(1-h(x^{(i)}))] $$其梯度为 $$ \nabla_w J(w) \frac{1}{m}X^T(\sigma(Xw) - y) $$4.3 Python实现class LogisticRegression: def __init__(self, lr0.01, n_iters1000): self.lr lr self.n_iters n_iters self.w None def _sigmoid(self, z): return 1 / (1 np.exp(-z)) def fit(self, X, y): X np.hstack([np.ones((X.shape[0], 1)), X]) self.w np.zeros(X.shape[1]) for _ in range(self.n_iters): z X self.w h self._sigmoid(z) grad X.T (h - y) / len(y) self.w - self.lr * grad def predict_proba(self, X): X np.hstack([np.ones((X.shape[0], 1)), X]) return self._sigmoid(X self.w) def predict(self, X, threshold0.5): return (self.predict_proba(X) threshold).astype(int)5. K近邻算法实现5.1 距离度量选择常用的距离度量包括欧式距离$\sqrt{\sum_{i1}^n (x_i - y_i)^2}$曼哈顿距离$\sum_{i1}^n |x_i - y_i|$余弦相似度$\frac{x \cdot y}{|x||y|}$5.2 投票机制实现class KNN: def __init__(self, k3, metriceuclidean): self.k k self.metric metric def _distance(self, a, b): if self.metric euclidean: return np.sqrt(np.sum((a - b)**2)) elif self.metric manhattan: return np.sum(np.abs(a - b)) def fit(self, X, y): self.X_train X self.y_train y def predict(self, X): preds [] for x in X: # 计算所有训练样本的距离 distances [self._distance(x, x_train) for x_train in self.X_train] # 获取最近的k个样本索引 k_indices np.argsort(distances)[:self.k] # 获取对应标签 k_labels self.y_train[k_indices] # 多数投票 pred np.bincount(k_labels).argmax() preds.append(pred) return np.array(preds)性能优化提示对于大数据集可以使用KD树或Ball树加速近邻搜索6. 朴素贝叶斯实现6.1 概率计算公式对于分类问题我们需要计算 $$ P(y|x_1,...,x_n) \frac{P(y)P(x_1|y)...P(x_n|y)}{P(x_1,...,x_n)} $$由于分母相同比较分子即可 $$ \hat{y} \arg\max_y P(y)\prod_{i1}^n P(x_i|y) $$6.2 高斯朴素贝叶斯实现class GaussianNB: def __init__(self): self.class_priors None self.class_means None self.class_vars None def fit(self, X, y): self.classes np.unique(y) n_classes len(self.classes) n_features X.shape[1] self.class_priors np.zeros(n_classes) self.class_means np.zeros((n_classes, n_features)) self.class_vars np.zeros((n_classes, n_features)) for i, c in enumerate(self.classes): X_c X[y c] self.class_priors[i] len(X_c) / len(X) self.class_means[i] X_c.mean(axis0) self.class_vars[i] X_c.var(axis0) def _gaussian_pdf(self, x, mean, var): return np.exp(-(x - mean)**2 / (2 * var)) / np.sqrt(2 * np.pi * var) def predict(self, X): posteriors [] for i, c in enumerate(self.classes): prior np.log(self.class_priors[i]) likelihood np.sum(np.log(self._gaussian_pdf(X, self.class_means[i], self.class_vars[i])), axis1) posterior prior likelihood posteriors.append(posterior) return self.classes[np.argmax(np.array(posteriors), axis0)]7. 决策树实现7.1 信息增益计算使用信息增益选择最佳分割特征 $$ IG(D_p, f) I(D_p) - \sum_{j1}^m \frac{N_j}{N_p}I(D_j) $$其中$I$可以是基尼系数或熵基尼系数$I_G(t) 1 - \sum_{i1}^c p(i|t)^2$熵$I_E(t) -\sum_{i1}^c p(i|t)\log_2 p(i|t)$7.2 递归构建决策树class DecisionTree: def __init__(self, max_depthNone, criteriongini): self.max_depth max_depth self.criterion criterion self.tree None def _gini(self, y): _, counts np.unique(y, return_countsTrue) probs counts / len(y) return 1 - np.sum(probs**2) def _entropy(self, y): _, counts np.unique(y, return_countsTrue) probs counts / len(y) return -np.sum(probs * np.log2(probs)) def _information_gain(self, X_col, y, split_threshold): parent_impurity self._gini(y) if self.criterion gini else self._entropy(y) left_idx X_col split_threshold right_idx X_col split_threshold n, n_left, n_right len(y), sum(left_idx), sum(right_idx) if n_left 0 or n_right 0: return 0 child_impurity (n_left/n)*self._gini(y[left_idx]) (n_right/n)*self._gini(y[right_idx]) \ if self.criterion gini else \ (n_left/n)*self._entropy(y[left_idx]) (n_right/n)*self._entropy(y[right_idx]) return parent_impurity - child_impurity def _best_split(self, X, y): best_gain -1 best_feature, best_threshold None, None for feature_idx in range(X.shape[1]): X_col X[:, feature_idx] thresholds np.unique(X_col) for threshold in thresholds: gain self._information_gain(X_col, y, threshold) if gain best_gain: best_gain gain best_feature feature_idx best_threshold threshold return best_feature, best_threshold def _build_tree(self, X, y, depth0): n_samples, n_features X.shape n_classes len(np.unique(y)) # 终止条件 if (self.max_depth is not None and depth self.max_depth) or n_classes 1: return {class: np.bincount(y).argmax()} # 寻找最佳分割 feature, threshold self._best_split(X, y) if feature is None: return {class: np.bincount(y).argmax()} # 递归构建子树 left_idx X[:, feature] threshold right_idx X[:, feature] threshold left_subtree self._build_tree(X[left_idx], y[left_idx], depth1) right_subtree self._build_tree(X[right_idx], y[right_idx], depth1) return { feature: feature, threshold: threshold, left: left_subtree, right: right_subtree } def fit(self, X, y): self.tree self._build_tree(X, y) def _predict_sample(self, x, node): if class in node: return node[class] if x[node[feature]] node[threshold]: return self._predict_sample(x, node[left]) else: return self._predict_sample(x, node[right]) def predict(self, X): return np.array([self._predict_sample(x, self.tree) for x in X])8. 算法评估与比较8.1 评估指标实现def accuracy_score(y_true, y_pred): return np.sum(y_true y_pred) / len(y_true) def mean_squared_error(y_true, y_pred): return np.mean((y_true - y_pred)**2)8.2 交叉验证实现def cross_val_score(model, X, y, cv5, scoringaccuracy): n_samples len(X) fold_size n_samples // cv indices np.arange(n_samples) np.random.shuffle(indices) scores [] for i in range(cv): start i * fold_size end (i 1) * fold_size if i ! cv - 1 else n_samples test_idx indices[start:end] train_idx np.concatenate([indices[:start], indices[end:]]) X_train, X_test X[train_idx], X[test_idx] y_train, y_test y[train_idx], y[test_idx] model.fit(X_train, y_train) y_pred model.predict(X_test) if scoring accuracy: score accuracy_score(y_test, y_pred) elif scoring mse: score mean_squared_error(y_test, y_pred) scores.append(score) return np.array(scores)9. 工程实践中的优化技巧9.1 数值稳定性处理在逻辑回归中sigmoid函数可以改写为数值稳定的版本def _sigmoid(self, z): # 防止数值溢出 z np.clip(z, -500, 500) return 1 / (1 np.exp(-z))9.2 向量化计算优化以线性回归为例矩阵运算比循环快100倍以上# 不好的实现 def predict(self, X): return np.array([np.dot(x, self.w) for x in X]) # 好的实现 def predict(self, X): return X self.w9.3 超参数调优策略实现简单的网格搜索def grid_search(model, X, y, param_grid, cv5): best_score -np.inf best_params None # 生成参数组合 keys, values zip(*param_grid.items()) for params in itertools.product(*values): params_dict dict(zip(keys, params)) model.set_params(**params_dict) scores cross_val_score(model, X, y, cvcv) mean_score np.mean(scores) if mean_score best_score: best_score mean_score best_params params_dict return best_params, best_score10. 扩展与进阶方向掌握了这些基础算法实现后可以考虑以下进阶方向正则化实现为线性回归和逻辑回归添加L1/L2正则化项多分类扩展改造逻辑回归为softmax回归核方法实现为SVM添加核函数支持集成方法基于决策树实现随机森林和GBDT神经网络从零实现多层感知机每个算法的完整实现通常需要考虑更多工程细节比如异常值处理缺失值处理类别不平衡处理在线学习支持并行计算优化这些实现虽然比直接调用库更复杂但对理解算法本质和提升工程能力有着不可替代的作用。建议读者在理解本文代码的基础上尝试为每个算法添加更多功能和优化。