简介面向数据挖掘初学者、相关课程学生及准备算法面试的开发者这份源代码包精准覆盖了关联规则Apriori、决策树C4.5/CART、EM聚类、K-means、KNN、PageRank共7种经典算法的Python实现每个算法均可独立运行并对照教材理解。压缩包共15个文件其中7个py为各算法主程序4个xml为工程配置2个testset为测试数据集1个md为说明文档1个iml为工程文件整体仅14KB轻量易读测试数据可直接配合脚本运行输出结果。资源已有1146人学习下载代码按算法分目录组织便于快速验证频繁项集挖掘、信息增益切分、距离计算与迭代收敛等关键思路适合课程实验、毕业设计、算法刷题或实际数据预处理任务中复用也可帮助读者通过源码理顺十大经典算法的内在逻辑。无论用于快速入门还是作为项目脚手架都能让读者直接受益。 最近把数据挖掘领域公认的十大经典算法用Python从头写了一遍最大的感受是调包的时候觉得每个算法都挺简单真到自己实现才发现各种边界条件、收敛判断、数据预处理里的细节才是拉开差距的地方。这篇不是教你用sklearn调参而是把每份源代码里的核心逻辑拆开讲一遍包含完整可运行的实现思路、关键代码片段和我在写代码过程中踩过的坑。适合已经会用scikit-learn、想补底层原理的读者也适合准备算法岗面试、需要手推加手写代码的人。1. 这十个算法为什么值得从零写一遍先亮一下名单。数据挖掘领域公认的十大经典算法是2006年ICDMIEEE国际数据挖掘大会评选出来的分别是C4.5、K-Means、SVM、Apriori、EM、PageRank、AdaBoost、kNN、Naive Bayes、CART。这十个算法覆盖了分类、聚类、关联规则、图挖掘、集成学习、概率模型几乎所有主干方向。不管你以后做推荐系统、风控模型还是知识图谱底层逻辑基本都从这里面长出来的。我见过不少同学简历上写着熟练使用sklearn实际工作里调包确实够用但一旦遇到三个问题就卡壳第一面试官问K-Means初始中心怎么选只会回答random第二线上特征分布变了模型效果掉得厉害不知道是算法假设出了问题还是数据预处理出了问题第三想改进某个算法比如给Apriori加个并行逻辑翻开源码一脸懵。自己把每个算法用numpy手写一遍之后这些问题会缓解很多。比如写K-Means的时候你会发现如果某个簇在迭代中变成空的程序直接报错这就是真实数据和教学数据最大的不同写朴素贝叶斯的时候你会发现测试集里出现一个训练时没见过的特征取值概率直接变成零必须做平滑。这些细节调参的时候根本接触不到。所以这套源代码的设计原则是除了数据加载和可视化之外尽量不依赖第三方机器学习库核心算法全部手写。每个算法独立成一个文件方便单独阅读、调试和二次开发。2. 环境准备与源码结构规划2.1 依赖版本与数据集选择我用的是Python 3.10依赖库只有numpy、pandas和matplotlib。其中numpy负责矩阵运算pandas负责加载和预览数据matplotlib只在画聚类图和ROC曲线的时候才会用到。写代码的时候建议用虚拟环境避免把系统Python环境搞乱。数据集方面分类算法我建议用Iris鸢尾花数据集和手写数字digits数据集。Iris简单直观150条样本、4个特征、3个类别几乎每个算法都能在两秒内跑完非常适合验证代码逻辑是否正确。手写数字是8x8的图像数据适合验证kNN、SVM和AdaBoost在稍复杂数据上的表现。聚类算法用Iris去掉标签后的数据就行关联规则算法则需要准备一个超市购物篮风格的交易数据每条记录是一个订单的商品列表。2.2 源代码目录结构我实际使用的目录结构是这样的algorithms/ ├── common/ │ ├── data_loader.py # 数据加载与预处理工具 │ └── metrics.py # 准确率、精确率、召回率、F1、混淆矩阵 ├── knn.py # k近邻 ├── naive_bayes.py # 朴素贝叶斯 ├── c45.py # C4.5决策树 ├── cart.py # CART分类回归树 ├── kmeans.py # K-Means聚类 ├── apriori.py # Apriori关联规则 ├── svm.py # SVM支持向量机 ├── adaboost.py # AdaBoost集成学习 ├── em_gmm.py # EM算法与高斯混合模型 └── pagerank.py # PageRank图算法common模块很关键。数据加载和指标计算是所有算法共用的抽出来之后每个算法文件的代码会清爽很多。特别提醒一下metrics.py里不要只写准确率建议把精确率、召回率、F1、混淆矩阵都实现一遍后面评估SVM和AdaBoost在这种类别不均衡的数据上会用到。3. 十大算法源码拆解每个关键步骤为什么这样写3.1 kNN——最近邻分类的工程陷阱kNN的原理一句话就能说清样本空间中离谁最近就属于谁。但写代码时有个非常容易被忽略的问题——距离度量。我见过很多初版实现直接用欧氏距离但对量纲敏感的特征比如收入和年龄收入数值大距离计算时几乎完全主导了结果。def predict(self, X): preds [] for x in X: # 欧氏距离向量化计算 diff self.X_train - x dist np.sqrt((diff ** 2).sum(axis1)) k_idx np.argsort(dist)[:self.k] k_labels self.y_train[k_idx] preds.append(np.bincount(k_labels).argmax()) return np.array(preds)写kNN第二个容易踩的坑是特征缩放。我刚开始在digits数据集上跑每个像素取值0到16直接算距离效果还可以。后来换到包含年龄收入消费金额的模拟数据上收入特征数值上千直接把其他特征淹没了准确率从80%掉到60%。解决办法是在fit之前对X做标准化这一步发生在数据加载模块里所有依赖距离的算法kNN、SVM、K-Means都会用到。3.2 朴素贝叶斯——先验、似然与平滑缺一不可朴素贝叶斯的核心是贝叶斯公式加上特征条件独立这个强假设。代码实现起来其实不复杂麻烦的是不同数据类型的处理方式完全不一样。连续特征我用高斯分布估计类条件概率离散特征用统计频次。def fit(self, X, y): self.classes np.unique(y) self.means {} self.stds {} self.priors {} for c in self.classes: X_c X[y c] self.means[c] X_c.mean(axis0) self.stds[c] X_c.std(axis0) 1e-6 # 避免除零 self.priors[c] (len(X_c) 1) / (len(X) len(self.classes))这里面有两个关键细节。第一标准差加上1e-6是为了防止某个特征在某个类别里方差为零导致概率计算除零报错。第二先验概率我用的是加1平滑也就是拉普拉斯平滑这是处理离散特征新取值问题的标准手段。如果不做平滑训练集里没出现过的特征组合在预测时概率会直接变成零一票否决这在文本分类里特别致命。3.3 C4.5决策树——信息增益率解决偏好问题决策树的核心就是特征选择。ID3用信息增益C4.5用信息增益率。为什么要换成增益率因为信息增益天然偏向取值多的特征。比如把样本ID作为一个特征每个ID只对应一个样本条件熵是零信息增益最大但这对泛化毫无帮助。def info_gain_ratio(self, X, y, feature): base_entropy self._entropy(y) values, counts np.unique(X[:, feature], return_countsTrue) cond_entropy 0.0 for v, cnt in zip(values, counts): subset_y y[X[:, feature] v] cond_entropy (cnt / len(y)) * self._entropy(subset_y) gain base_entropy - cond_entropy split_info self._entropy(X[:, feature]) # 特征自身的熵 return gain / (split_info 1e-6)C4.5源码里还有个容易忽略的点连续特征的处理。它会把连续特征排序尝试每一个相邻值的中间点作为切分点计算出该切分点下的信息增益率取最大的那个。这个逻辑会让代码的复杂度明显上升但效果也确实比直接离散化要好。3.4 CART——基尼系数与回归树CART和C4.5最大的区别在于CART是二叉树用基尼系数做分类特征选择而且既可以做分类也可以做回归。基尼系数的含义是从数据集中随机抽取两个样本类别不一致的概率所以基尼系数越小纯度越高。def gini(self, y): _, counts np.unique(y, return_countsTrue) p counts / counts.sum() return 1 - (p ** 2).sum()回归树的切分依据则是方差减少量。每次切分之前计算父节点的方差切分之后计算两个子节点的加权方差二者之差越大说明切分效果越好。CART的剪枝也是一个重点我用的是代价复杂度剪枝通过一个参数alpha控制树的复杂度惩罚。3.5 K-Means——迭代聚类里的初始化难题K-Means的逻辑特别清晰初始化中心点、分配样本、更新中心点、重复直到收敛。但这个算法有一个著名的bug——初始化不当会陷入局部最优。我写第一版的时候直接用np.random.choice随机选中心点跑十次结果能有三四种。# 简化版K-Means未做K-Means初始化 def fit(self, X, k, max_iter100): centers X[np.random.choice(len(X), k, replaceFalse)] for _ in range(max_iter): dist np.linalg.norm(X[:, None, :] - centers, axis2) labels np.argmin(dist, axis1) new_centers np.array([X[labels i].mean(axis0) for i in range(k)]) if np.allclose(centers, new_centers, rtol1e-4): break centers new_centers return labels, centers运行的时候你会碰到一个很实际的问题某个簇可能一个样本都没分到X[labels i].mean(axis0)直接报错或者算出nan。我处理这个问题的办法是遇到空簇就重新随机初始化一个中心点。另外实际项目中强烈建议用K-Means初始化它的核心逻辑是让初始中心点互相离得远一点能显著减少迭代次数和局部最优的概率。K值的选择可以用肘部法画出代价函数J随K变化的曲线找拐点。3.6 Apriori——频繁项集的连接与剪枝Apriori是关联规则挖掘的入门算法核心思想是频繁项集的子集也一定是频繁的。这个性质可以用来剪枝生成候选集的时候如果某个项集的子集不在上一轮的频繁项集中直接砍掉。def apriori(dataset, min_support0.5): # 第一步生成频繁1项集 item_count defaultdict(int) for trans in dataset: for item in trans: item_count[frozenset([item])] 1 total len(dataset) freq {itemset: cnt / total for itemset, cnt in item_count.items() if cnt / total min_support} k 2 while True: # 连接步k项候选集 candidates set() freq_list list(freq.keys()) for i in range(len(freq_list)): for j in range(i 1, len(freq_list)): union freq_list[i] | freq_list[j] if len(union) k: candidates.add(union) # 剪枝步子集不在频繁项集的去掉 candidates {c for c in candidates if all(frozenset(sub) in freq for sub in combinations(c, k - 1))} if not candidates: break # 计算支持度 freq {} for cand in candidates: cnt sum(1 for trans in dataset if cand.issubset(trans)) if cnt / total min_support: freq[cand] cnt / total k 1 return freq写Apriori的时候我踩了一个性能坑直接用list作为项集频繁项集做交集判断时非常慢而且会有重复项。后来全部改用frozenset既保证了哈希效率又天然去重。在真实交易数据上min_support设得太低会导致候选项集爆炸式增长这个参数需要结合业务场景反复调。3.7 SVM——对偶问题、核函数和SMOSVM是十大算法里数学最重的一个。最早我想自己实现完整的SMO序列最小优化算法折腾了两个晚上才把收敛条件调好完整代码两百多行。SMO的核心思路是一次只优化两个拉格朗日乘子其他乘子固定把二次规划问题拆成一系列最小子问题迭代求解。如果只是为了理解SVM的源码逻辑我建议分两步走。第一步先实现一个不依赖核函数的线性SVM用梯度下降优化合页损失第二步实现高斯核函数理解特征映射到高维空间的过程。# 高斯核函数计算 def rbf_kernel(X1, X2, gamma0.1): sq_dist np.sum(X1 ** 2, axis1, keepdimsTrue) \ np.sum(X2 ** 2, axis1) \ - 2 * np.dot(X1, X2.T) return np.exp(-gamma * sq_dist)SVM实践中最容易被坑的是gamma参数。gamma越小高斯核的影响半径越大决策边界越平滑gamma越大边界越复杂容易过拟合。我在digits数据集上把gamma从0.001调到10训练集准确率一路升到100%测试集却从95%掉到85%典型的过拟合。3.8 AdaBoost——弱分类器如何变强AdaBoost是我写的这十个算法里最直觉的一个先训练一个弱分类器把分错的样本权重调大再训练下一个让后面的分类器更关注之前被分错的样本。最终预测是所有弱分类器的加权投票。def fit(self, X, y, T50): n len(y) w np.ones(n) / n self.models [] self.alphas [] for t in range(T): h DecisionStump() h.fit(X, y, sample_weightw) pred h.predict(X) err (w * (pred ! y)).sum() if err 0.5: break alpha 0.5 * np.log((1 - err) / max(err, 1e-10)) w * np.exp(-alpha * y * pred) w / w.sum() self.models.append(h) self.alphas.append(alpha)注意代码里y用的是1和-1这样y * pred为正表示预测正确为负表示预测错误权重更新的表达式才简洁。如果y用0和1这个公式就不对了。这是很多初写AdaBoost的人容易搞混的细节。基分类器我用的是深度为1的决策树桩也就是只有一个特征参与分裂。树桩虽然弱但配合权重更新之后集成起来的分类能力能超过很多强分类器。3.9 EM——隐变量模型的标准解法EM期望最大化算法最经典的应用是高斯混合模型GMM。我们把数据看成由多个高斯分布混合生成的但每个样本来自哪个分布是未知的这就是隐变量。E步根据当前参数计算每个样本属于每个高斯分布的后验概率M步用这些概率加权更新均值和协方差。# E步计算后验概率 for k in range(K): likelihood_k multivariate_normal.pdf(X, meanmeans[k], covcovs[k]) gamma[:, k] prior[k] * likelihood_k gamma / gamma.sum(axis1, keepdimsTrue) # M步更新参数 for k in range(K): Nk gamma[:, k].sum() means[k] (gamma[:, k].reshape(-1, 1) * X).sum(axis0) / Nk covs[k] np.dot((gamma[:, k].reshape(-1, 1) * (X - means[k])).T, (X - means[k])) / Nk prior[k] Nk / len(X)我写EM的时候第一个版本没有判断收敛跑了固定一百次迭代结果发现最后一二十次参数几乎没变白白浪费计算时间。后来加了对数似然变化量判断当变化小于1e-4就停止。还有一个坑是协方差矩阵在迭代过程中可能变成奇异矩阵也就是某个高斯分布退化到几乎只有一个样本点这时需要在协方差矩阵的对角线上加一个极小值做正则化。3.10 PageRank——图上随机游走的幂法迭代PageRank当初是Google用来给网页排名的现在推荐系统、知识图谱、反作弊领域都在用。它的数学本质是一个马尔可夫链的平稳分布想象一个用户在网页间随机点链接最终落在每个页面上的概率就是PageRank值。def pagerank(adj, d0.85, max_iter100, tol1e-6): n adj.shape[0] out_deg adj.sum(axis1, keepdimsTrue) out_deg[out_deg 0] 1 # 处理悬挂节点 M adj / out_deg r np.ones(n) / n for _ in range(max_iter): new_r (1 - d) / n d * M.T r if np.linalg.norm(new_r - r, ord1) tol: break r new_r return r源码里最容易漏的是悬挂节点处理。如果某个网页没有任何出链那它的出度为零除零操作直接就崩了。实际处理办法是把悬挂节点的出链指向所有页面。阻尼系数d取0.85的经验值含义是用户有15%的概率不继续点链接而是随机跳到任意页面保证整个马尔可夫链是遍历的一定会收敛。4. 让源码在真实数据上可用预处理、评估与调参4.1 归一化与特征编码kNN/SVM的生死线写完十个算法后我在模拟数据集上做了一次对比实验发现预处理方式对结果的影响比算法选择还大。kNN、SVM、K-Means都是基于距离的算法特征量纲不一致时数值范围大的特征会彻底主导距离计算。我一般在common/data_loader.py里封装一个standardize函数用z-score归一化把每个特征变成均值为0、方差为1。对决策树和朴素贝叶斯来说归一化影响不大但类别特征的编码方式值得注意。C4.5和CART对离散特征可以直接按取值分裂但SVM和kNN不行必须做One-Hot编码否则类别之间的数值大小关系会被模型错误利用。4.2 训练集、验证集与交叉验证我第一版测试代码的时候犯了个低级错误直接拿全部数据训练再拿全部数据评估结果决策树准确率100%还以为代码没问题后来才发现模型把训练数据背下来了。正确的做法是至少拆分成训练集和测试集我用的是70%训练、30%测试的简单划分。调参阶段再用K-Fold交叉验证把数据切成5份轮流拿4份训练、1份验证最后取平均指标。这里有个额外的建议样本量不大的时候建议用分层抽样保证训练集和测试集里各个类别的比例和原始数据一致。numpy的random.choice虽然能实现但写起来容易出错我图省事直接用sklearn的train_test_split它的stratify参数一行搞定。4.3 评估指标与调参思路分类算法不要只看准确率。我在一个模拟的风控场景里样本只有5%的正例模型全预测为负例准确率95%但业务上一个正例都没抓住完全不可用。所以在metrics.py里我实现了Precision、Recall、F1和混淆矩阵。对kNN调K值我画了一个K从1到20的准确率曲线发现K太小会过拟合K太大会把边界样本平滑掉最优值基本落在5左右。对SVM调gamma和C我用了网格搜索的思路遍历几组候选参数观察F1的变化趋势。5. 从零复现过程的避坑清单5.1 随机种子与结果可复现K-Means、EM、AdaBoost都涉及随机初始化或者随机抽样。如果你不在代码开头设置随机种子每次运行结果都不一样排查问题时很难判断改动是让算法变好了还是随机波动。我习惯在任何涉及随机性的算法入口处加np.random.seed(42)实验对比时才公平。5.2 浮点精度与数值稳定性写朴素贝叶斯的时候我踩了个精度坑。高斯分布的概率密度值可能小到1e-200多个特征的概率连乘之后直接下溢成0所有类别都是0argmax取不到有效结果。解决办法是在对数空间计算对概率取log连乘变成连加最后再比较大小。SVM和AdaBoost里也会出现exp计算溢出所以alpha的公式里用了max(err, 1e-10)做保护。5.3 空簇、稀疏矩阵与高维灾难K-Means的空簇问题前面已经说过。Apriori在真实交易数据上还有一个存储问题候选项集数量可能达到百万级纯Python的字典和集合操作内存占用很大我后来用前缀树结构压缩存储才勉强跑起来。高维数据对kNN很不友好维度越高样本间距离越趋于一致最近邻和次近邻几乎没区别所以实际项目里一般先做PCA降维再跑kNN。最后再分享一个写代码时的习惯每实现完一个算法先在小数据集上手工计算一遍结果再和程序输出对比。比如kNN我拿Iris的前五条样本人肉算最近邻确认没问题之后才继续跑完整的数据。写算法源码不是为了替代sklearn而是通过亲手实现把每个公式变成看得见、能调试、会出错的具体代码这个过程中建立的直觉才是这套源码最大的价值。本文还有配套的精品资源点击获取
十大经典机器学习算法Python手写实现与避坑指南
简介面向数据挖掘初学者、相关课程学生及准备算法面试的开发者这份源代码包精准覆盖了关联规则Apriori、决策树C4.5/CART、EM聚类、K-means、KNN、PageRank共7种经典算法的Python实现每个算法均可独立运行并对照教材理解。压缩包共15个文件其中7个py为各算法主程序4个xml为工程配置2个testset为测试数据集1个md为说明文档1个iml为工程文件整体仅14KB轻量易读测试数据可直接配合脚本运行输出结果。资源已有1146人学习下载代码按算法分目录组织便于快速验证频繁项集挖掘、信息增益切分、距离计算与迭代收敛等关键思路适合课程实验、毕业设计、算法刷题或实际数据预处理任务中复用也可帮助读者通过源码理顺十大经典算法的内在逻辑。无论用于快速入门还是作为项目脚手架都能让读者直接受益。 最近把数据挖掘领域公认的十大经典算法用Python从头写了一遍最大的感受是调包的时候觉得每个算法都挺简单真到自己实现才发现各种边界条件、收敛判断、数据预处理里的细节才是拉开差距的地方。这篇不是教你用sklearn调参而是把每份源代码里的核心逻辑拆开讲一遍包含完整可运行的实现思路、关键代码片段和我在写代码过程中踩过的坑。适合已经会用scikit-learn、想补底层原理的读者也适合准备算法岗面试、需要手推加手写代码的人。1. 这十个算法为什么值得从零写一遍先亮一下名单。数据挖掘领域公认的十大经典算法是2006年ICDMIEEE国际数据挖掘大会评选出来的分别是C4.5、K-Means、SVM、Apriori、EM、PageRank、AdaBoost、kNN、Naive Bayes、CART。这十个算法覆盖了分类、聚类、关联规则、图挖掘、集成学习、概率模型几乎所有主干方向。不管你以后做推荐系统、风控模型还是知识图谱底层逻辑基本都从这里面长出来的。我见过不少同学简历上写着熟练使用sklearn实际工作里调包确实够用但一旦遇到三个问题就卡壳第一面试官问K-Means初始中心怎么选只会回答random第二线上特征分布变了模型效果掉得厉害不知道是算法假设出了问题还是数据预处理出了问题第三想改进某个算法比如给Apriori加个并行逻辑翻开源码一脸懵。自己把每个算法用numpy手写一遍之后这些问题会缓解很多。比如写K-Means的时候你会发现如果某个簇在迭代中变成空的程序直接报错这就是真实数据和教学数据最大的不同写朴素贝叶斯的时候你会发现测试集里出现一个训练时没见过的特征取值概率直接变成零必须做平滑。这些细节调参的时候根本接触不到。所以这套源代码的设计原则是除了数据加载和可视化之外尽量不依赖第三方机器学习库核心算法全部手写。每个算法独立成一个文件方便单独阅读、调试和二次开发。2. 环境准备与源码结构规划2.1 依赖版本与数据集选择我用的是Python 3.10依赖库只有numpy、pandas和matplotlib。其中numpy负责矩阵运算pandas负责加载和预览数据matplotlib只在画聚类图和ROC曲线的时候才会用到。写代码的时候建议用虚拟环境避免把系统Python环境搞乱。数据集方面分类算法我建议用Iris鸢尾花数据集和手写数字digits数据集。Iris简单直观150条样本、4个特征、3个类别几乎每个算法都能在两秒内跑完非常适合验证代码逻辑是否正确。手写数字是8x8的图像数据适合验证kNN、SVM和AdaBoost在稍复杂数据上的表现。聚类算法用Iris去掉标签后的数据就行关联规则算法则需要准备一个超市购物篮风格的交易数据每条记录是一个订单的商品列表。2.2 源代码目录结构我实际使用的目录结构是这样的algorithms/ ├── common/ │ ├── data_loader.py # 数据加载与预处理工具 │ └── metrics.py # 准确率、精确率、召回率、F1、混淆矩阵 ├── knn.py # k近邻 ├── naive_bayes.py # 朴素贝叶斯 ├── c45.py # C4.5决策树 ├── cart.py # CART分类回归树 ├── kmeans.py # K-Means聚类 ├── apriori.py # Apriori关联规则 ├── svm.py # SVM支持向量机 ├── adaboost.py # AdaBoost集成学习 ├── em_gmm.py # EM算法与高斯混合模型 └── pagerank.py # PageRank图算法common模块很关键。数据加载和指标计算是所有算法共用的抽出来之后每个算法文件的代码会清爽很多。特别提醒一下metrics.py里不要只写准确率建议把精确率、召回率、F1、混淆矩阵都实现一遍后面评估SVM和AdaBoost在这种类别不均衡的数据上会用到。3. 十大算法源码拆解每个关键步骤为什么这样写3.1 kNN——最近邻分类的工程陷阱kNN的原理一句话就能说清样本空间中离谁最近就属于谁。但写代码时有个非常容易被忽略的问题——距离度量。我见过很多初版实现直接用欧氏距离但对量纲敏感的特征比如收入和年龄收入数值大距离计算时几乎完全主导了结果。def predict(self, X): preds [] for x in X: # 欧氏距离向量化计算 diff self.X_train - x dist np.sqrt((diff ** 2).sum(axis1)) k_idx np.argsort(dist)[:self.k] k_labels self.y_train[k_idx] preds.append(np.bincount(k_labels).argmax()) return np.array(preds)写kNN第二个容易踩的坑是特征缩放。我刚开始在digits数据集上跑每个像素取值0到16直接算距离效果还可以。后来换到包含年龄收入消费金额的模拟数据上收入特征数值上千直接把其他特征淹没了准确率从80%掉到60%。解决办法是在fit之前对X做标准化这一步发生在数据加载模块里所有依赖距离的算法kNN、SVM、K-Means都会用到。3.2 朴素贝叶斯——先验、似然与平滑缺一不可朴素贝叶斯的核心是贝叶斯公式加上特征条件独立这个强假设。代码实现起来其实不复杂麻烦的是不同数据类型的处理方式完全不一样。连续特征我用高斯分布估计类条件概率离散特征用统计频次。def fit(self, X, y): self.classes np.unique(y) self.means {} self.stds {} self.priors {} for c in self.classes: X_c X[y c] self.means[c] X_c.mean(axis0) self.stds[c] X_c.std(axis0) 1e-6 # 避免除零 self.priors[c] (len(X_c) 1) / (len(X) len(self.classes))这里面有两个关键细节。第一标准差加上1e-6是为了防止某个特征在某个类别里方差为零导致概率计算除零报错。第二先验概率我用的是加1平滑也就是拉普拉斯平滑这是处理离散特征新取值问题的标准手段。如果不做平滑训练集里没出现过的特征组合在预测时概率会直接变成零一票否决这在文本分类里特别致命。3.3 C4.5决策树——信息增益率解决偏好问题决策树的核心就是特征选择。ID3用信息增益C4.5用信息增益率。为什么要换成增益率因为信息增益天然偏向取值多的特征。比如把样本ID作为一个特征每个ID只对应一个样本条件熵是零信息增益最大但这对泛化毫无帮助。def info_gain_ratio(self, X, y, feature): base_entropy self._entropy(y) values, counts np.unique(X[:, feature], return_countsTrue) cond_entropy 0.0 for v, cnt in zip(values, counts): subset_y y[X[:, feature] v] cond_entropy (cnt / len(y)) * self._entropy(subset_y) gain base_entropy - cond_entropy split_info self._entropy(X[:, feature]) # 特征自身的熵 return gain / (split_info 1e-6)C4.5源码里还有个容易忽略的点连续特征的处理。它会把连续特征排序尝试每一个相邻值的中间点作为切分点计算出该切分点下的信息增益率取最大的那个。这个逻辑会让代码的复杂度明显上升但效果也确实比直接离散化要好。3.4 CART——基尼系数与回归树CART和C4.5最大的区别在于CART是二叉树用基尼系数做分类特征选择而且既可以做分类也可以做回归。基尼系数的含义是从数据集中随机抽取两个样本类别不一致的概率所以基尼系数越小纯度越高。def gini(self, y): _, counts np.unique(y, return_countsTrue) p counts / counts.sum() return 1 - (p ** 2).sum()回归树的切分依据则是方差减少量。每次切分之前计算父节点的方差切分之后计算两个子节点的加权方差二者之差越大说明切分效果越好。CART的剪枝也是一个重点我用的是代价复杂度剪枝通过一个参数alpha控制树的复杂度惩罚。3.5 K-Means——迭代聚类里的初始化难题K-Means的逻辑特别清晰初始化中心点、分配样本、更新中心点、重复直到收敛。但这个算法有一个著名的bug——初始化不当会陷入局部最优。我写第一版的时候直接用np.random.choice随机选中心点跑十次结果能有三四种。# 简化版K-Means未做K-Means初始化 def fit(self, X, k, max_iter100): centers X[np.random.choice(len(X), k, replaceFalse)] for _ in range(max_iter): dist np.linalg.norm(X[:, None, :] - centers, axis2) labels np.argmin(dist, axis1) new_centers np.array([X[labels i].mean(axis0) for i in range(k)]) if np.allclose(centers, new_centers, rtol1e-4): break centers new_centers return labels, centers运行的时候你会碰到一个很实际的问题某个簇可能一个样本都没分到X[labels i].mean(axis0)直接报错或者算出nan。我处理这个问题的办法是遇到空簇就重新随机初始化一个中心点。另外实际项目中强烈建议用K-Means初始化它的核心逻辑是让初始中心点互相离得远一点能显著减少迭代次数和局部最优的概率。K值的选择可以用肘部法画出代价函数J随K变化的曲线找拐点。3.6 Apriori——频繁项集的连接与剪枝Apriori是关联规则挖掘的入门算法核心思想是频繁项集的子集也一定是频繁的。这个性质可以用来剪枝生成候选集的时候如果某个项集的子集不在上一轮的频繁项集中直接砍掉。def apriori(dataset, min_support0.5): # 第一步生成频繁1项集 item_count defaultdict(int) for trans in dataset: for item in trans: item_count[frozenset([item])] 1 total len(dataset) freq {itemset: cnt / total for itemset, cnt in item_count.items() if cnt / total min_support} k 2 while True: # 连接步k项候选集 candidates set() freq_list list(freq.keys()) for i in range(len(freq_list)): for j in range(i 1, len(freq_list)): union freq_list[i] | freq_list[j] if len(union) k: candidates.add(union) # 剪枝步子集不在频繁项集的去掉 candidates {c for c in candidates if all(frozenset(sub) in freq for sub in combinations(c, k - 1))} if not candidates: break # 计算支持度 freq {} for cand in candidates: cnt sum(1 for trans in dataset if cand.issubset(trans)) if cnt / total min_support: freq[cand] cnt / total k 1 return freq写Apriori的时候我踩了一个性能坑直接用list作为项集频繁项集做交集判断时非常慢而且会有重复项。后来全部改用frozenset既保证了哈希效率又天然去重。在真实交易数据上min_support设得太低会导致候选项集爆炸式增长这个参数需要结合业务场景反复调。3.7 SVM——对偶问题、核函数和SMOSVM是十大算法里数学最重的一个。最早我想自己实现完整的SMO序列最小优化算法折腾了两个晚上才把收敛条件调好完整代码两百多行。SMO的核心思路是一次只优化两个拉格朗日乘子其他乘子固定把二次规划问题拆成一系列最小子问题迭代求解。如果只是为了理解SVM的源码逻辑我建议分两步走。第一步先实现一个不依赖核函数的线性SVM用梯度下降优化合页损失第二步实现高斯核函数理解特征映射到高维空间的过程。# 高斯核函数计算 def rbf_kernel(X1, X2, gamma0.1): sq_dist np.sum(X1 ** 2, axis1, keepdimsTrue) \ np.sum(X2 ** 2, axis1) \ - 2 * np.dot(X1, X2.T) return np.exp(-gamma * sq_dist)SVM实践中最容易被坑的是gamma参数。gamma越小高斯核的影响半径越大决策边界越平滑gamma越大边界越复杂容易过拟合。我在digits数据集上把gamma从0.001调到10训练集准确率一路升到100%测试集却从95%掉到85%典型的过拟合。3.8 AdaBoost——弱分类器如何变强AdaBoost是我写的这十个算法里最直觉的一个先训练一个弱分类器把分错的样本权重调大再训练下一个让后面的分类器更关注之前被分错的样本。最终预测是所有弱分类器的加权投票。def fit(self, X, y, T50): n len(y) w np.ones(n) / n self.models [] self.alphas [] for t in range(T): h DecisionStump() h.fit(X, y, sample_weightw) pred h.predict(X) err (w * (pred ! y)).sum() if err 0.5: break alpha 0.5 * np.log((1 - err) / max(err, 1e-10)) w * np.exp(-alpha * y * pred) w / w.sum() self.models.append(h) self.alphas.append(alpha)注意代码里y用的是1和-1这样y * pred为正表示预测正确为负表示预测错误权重更新的表达式才简洁。如果y用0和1这个公式就不对了。这是很多初写AdaBoost的人容易搞混的细节。基分类器我用的是深度为1的决策树桩也就是只有一个特征参与分裂。树桩虽然弱但配合权重更新之后集成起来的分类能力能超过很多强分类器。3.9 EM——隐变量模型的标准解法EM期望最大化算法最经典的应用是高斯混合模型GMM。我们把数据看成由多个高斯分布混合生成的但每个样本来自哪个分布是未知的这就是隐变量。E步根据当前参数计算每个样本属于每个高斯分布的后验概率M步用这些概率加权更新均值和协方差。# E步计算后验概率 for k in range(K): likelihood_k multivariate_normal.pdf(X, meanmeans[k], covcovs[k]) gamma[:, k] prior[k] * likelihood_k gamma / gamma.sum(axis1, keepdimsTrue) # M步更新参数 for k in range(K): Nk gamma[:, k].sum() means[k] (gamma[:, k].reshape(-1, 1) * X).sum(axis0) / Nk covs[k] np.dot((gamma[:, k].reshape(-1, 1) * (X - means[k])).T, (X - means[k])) / Nk prior[k] Nk / len(X)我写EM的时候第一个版本没有判断收敛跑了固定一百次迭代结果发现最后一二十次参数几乎没变白白浪费计算时间。后来加了对数似然变化量判断当变化小于1e-4就停止。还有一个坑是协方差矩阵在迭代过程中可能变成奇异矩阵也就是某个高斯分布退化到几乎只有一个样本点这时需要在协方差矩阵的对角线上加一个极小值做正则化。3.10 PageRank——图上随机游走的幂法迭代PageRank当初是Google用来给网页排名的现在推荐系统、知识图谱、反作弊领域都在用。它的数学本质是一个马尔可夫链的平稳分布想象一个用户在网页间随机点链接最终落在每个页面上的概率就是PageRank值。def pagerank(adj, d0.85, max_iter100, tol1e-6): n adj.shape[0] out_deg adj.sum(axis1, keepdimsTrue) out_deg[out_deg 0] 1 # 处理悬挂节点 M adj / out_deg r np.ones(n) / n for _ in range(max_iter): new_r (1 - d) / n d * M.T r if np.linalg.norm(new_r - r, ord1) tol: break r new_r return r源码里最容易漏的是悬挂节点处理。如果某个网页没有任何出链那它的出度为零除零操作直接就崩了。实际处理办法是把悬挂节点的出链指向所有页面。阻尼系数d取0.85的经验值含义是用户有15%的概率不继续点链接而是随机跳到任意页面保证整个马尔可夫链是遍历的一定会收敛。4. 让源码在真实数据上可用预处理、评估与调参4.1 归一化与特征编码kNN/SVM的生死线写完十个算法后我在模拟数据集上做了一次对比实验发现预处理方式对结果的影响比算法选择还大。kNN、SVM、K-Means都是基于距离的算法特征量纲不一致时数值范围大的特征会彻底主导距离计算。我一般在common/data_loader.py里封装一个standardize函数用z-score归一化把每个特征变成均值为0、方差为1。对决策树和朴素贝叶斯来说归一化影响不大但类别特征的编码方式值得注意。C4.5和CART对离散特征可以直接按取值分裂但SVM和kNN不行必须做One-Hot编码否则类别之间的数值大小关系会被模型错误利用。4.2 训练集、验证集与交叉验证我第一版测试代码的时候犯了个低级错误直接拿全部数据训练再拿全部数据评估结果决策树准确率100%还以为代码没问题后来才发现模型把训练数据背下来了。正确的做法是至少拆分成训练集和测试集我用的是70%训练、30%测试的简单划分。调参阶段再用K-Fold交叉验证把数据切成5份轮流拿4份训练、1份验证最后取平均指标。这里有个额外的建议样本量不大的时候建议用分层抽样保证训练集和测试集里各个类别的比例和原始数据一致。numpy的random.choice虽然能实现但写起来容易出错我图省事直接用sklearn的train_test_split它的stratify参数一行搞定。4.3 评估指标与调参思路分类算法不要只看准确率。我在一个模拟的风控场景里样本只有5%的正例模型全预测为负例准确率95%但业务上一个正例都没抓住完全不可用。所以在metrics.py里我实现了Precision、Recall、F1和混淆矩阵。对kNN调K值我画了一个K从1到20的准确率曲线发现K太小会过拟合K太大会把边界样本平滑掉最优值基本落在5左右。对SVM调gamma和C我用了网格搜索的思路遍历几组候选参数观察F1的变化趋势。5. 从零复现过程的避坑清单5.1 随机种子与结果可复现K-Means、EM、AdaBoost都涉及随机初始化或者随机抽样。如果你不在代码开头设置随机种子每次运行结果都不一样排查问题时很难判断改动是让算法变好了还是随机波动。我习惯在任何涉及随机性的算法入口处加np.random.seed(42)实验对比时才公平。5.2 浮点精度与数值稳定性写朴素贝叶斯的时候我踩了个精度坑。高斯分布的概率密度值可能小到1e-200多个特征的概率连乘之后直接下溢成0所有类别都是0argmax取不到有效结果。解决办法是在对数空间计算对概率取log连乘变成连加最后再比较大小。SVM和AdaBoost里也会出现exp计算溢出所以alpha的公式里用了max(err, 1e-10)做保护。5.3 空簇、稀疏矩阵与高维灾难K-Means的空簇问题前面已经说过。Apriori在真实交易数据上还有一个存储问题候选项集数量可能达到百万级纯Python的字典和集合操作内存占用很大我后来用前缀树结构压缩存储才勉强跑起来。高维数据对kNN很不友好维度越高样本间距离越趋于一致最近邻和次近邻几乎没区别所以实际项目里一般先做PCA降维再跑kNN。最后再分享一个写代码时的习惯每实现完一个算法先在小数据集上手工计算一遍结果再和程序输出对比。比如kNN我拿Iris的前五条样本人肉算最近邻确认没问题之后才继续跑完整的数据。写算法源码不是为了替代sklearn而是通过亲手实现把每个公式变成看得见、能调试、会出错的具体代码这个过程中建立的直觉才是这套源码最大的价值。本文还有配套的精品资源点击获取
