1 2023年06月 机器学习-决策树 黄海广 副教授 2 本章目录 01 决策树原理 02 ID3算法 03 C4.5算法 04 CART算法 3 1.决策树原理 01 决策树原理 02 ID3算法 03 C4.5算法 04 CART算法 4 长相 能 帅 不帅 家庭背景 好 能 不好 人品 好 上进心 能 不能 有 有 无 不能 不好 1.决策树原理 ⚫ 决策树：从训练数据中学习得出一个树状 结构的模型。 ⚫ 决策树属于判别模型。 ⚫ 决策树是一种树状结构，通过做出一系列 决策（选择）来对数据进行划分，这类似 于针对一系列问题进行选择。 ⚫ 决策树的决策过程就是从根节点开始，测 试待分类项中对应的特征属性，并按照其 值选择输出分支，直到叶子节点，将叶子 节点的存放的类别作为决策结果。 node) 5 1.决策树原理 根节点 (root node) 非叶子节点 (non-leaf node) (代表测试条件，对数据属性的测试) 分支 (branches) (代表测试结果) 叶节点 (leaf node) (代表分类后所获得的分类标记) ⚫ 决策树算法是一种归纳分类算法 ，它通过对训练集的学习，挖掘 出有用的规则，用于对新数据进 行预测。 ⚫ 决策树算法属于监督学习方法。

所有基模型的预测形成新的测试集，最后再对测试集进行预测。 测试 数据 7 Random Forest（随机森林） 用随机的方式建立一个森林。随机森林算法由很多决策树组成，每一棵决 策树之间没有关联。建立完森林后，当有新样本进入时，每棵决策树都会 分别进行判断，然后基于投票法给出分类结果。 优点 1. 在数据集上表现良好，相对于其他算法有较大的优势 2. 易于并行化，在大数据集上有很大的优势； 体，它在以决策树为基学习器构建 Bagging 集成的 基础上，进一步在决策树的训练过程中引入了随机特 征选择，因此可以概括 随机森林包括四个部分： 1. 随机选择样本（放回抽样）； 2. 随机选择特征； 3. 构建决策树； 4. 随机森林投票（平均）。 随机森林 训练数据 Bootstrap随机抽取 决策树1 最终预测结果 测试 数据 决策树n …… 决策树2 预测1 预测n 随机选择样本和 Bagging 相同，采用的是 Bootstraping 自助采样法；随机选择特征是 指在每个节点在分裂过程中都是随机选择特 征的（区别与每棵树随机选择一批特征）。 这种随机性导致随机森林的偏差会有稍微的 增加（相比于单棵不随机树），但是由于随 机森林的“平均”特性，会使得它的方差减 小，而且方差的减小补偿了偏差的增大，因 此总体而言是更好的模型。 随机森林 数据集 自助采样

韩家炜老师在2000年提出的关联分析算法，它采 取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree）， 但仍保留项集关联信息。 该算法是对Apriori方法的改进。生成一个频繁模式而不需要生成候选模式。 FP-growth算法以树的形式表示数据库，称为频繁模式树或FP-tree。 此树结构将保持项集之间的关联。数据库使用一个频繁项进行分段。这个片段被称 为“模式 算法发现频繁项集的过程是： (1)构建FP树； (2)从FP树中挖掘频繁项集。 28 3.FP-Growth算法 FP-growth算法思想 该算法和Apriori算法最大的不同有两点： 第一，不产生候选集 第二，只需要两次遍历数据库，大大提高了效率。 29 3.FP-Growth算法 FP-Tree （ Frequent Pattern Tree ） FP树(FP-Tree)是由数据库的初始项集组成的树状结构。 FP树(FP-Tree)是由数据库的初始项集组成的树状结构。 FP树的目的是挖掘最 频繁的模式。FP树的每个节点表示项集的一个项。 根节点表示null，而较低的节点表示项集。在形成树的同时，保持节点与较 低节点（即项集与其他项集）的关联。 30 3.FP-Growth算法 算法步骤 FP-growth算法的流程为： 首先构造FP树，然后利用它来挖掘频繁项集。 在构造FP树时，需要对数据集扫描两遍， 第一遍扫描用来统计频率，第二遍扫描至考虑频繁项集。

2021年04月 机器学习-KNN算法 黄海广 副教授 2 01 距离度量 02 KNN算法 本章目录 03 KD树划分 04 KD树搜索 3 01 距离度量 02 KNN算法 03 KD树划分 04 KD树搜索 1.距离度量 4 距离度量 欧氏距离(Euclidean distance) ? ?, ? = ෍ ? ?? − ? ∥ = σ?=1 ? ?? × ?? σ?=1 ? ( ??)2 × σ?=1 ? ( ??)2 10 01 距离度量 02 KNN算法 03 KD树划分 04 KD树搜索 2.KNN算法 11 2.KNN算法 ?近邻法（k-Nearest Neighbor,kNN）是一种比较成熟也是最简单的机器学习算 法，可以用于基本的分类与回归方法。 算法的主要思路： 01 距离度量 02 KNN算法 03 KD树划分 04 KD树搜索 3.K-D-Tree划分 15 KD树划分 KD树(K-Dimension Tree)，，也可称之为K维树 ，可以用更高的效率来对空间进行划分，并且其 结构非常适合寻找最近邻居和碰撞检测。 假设有 6 个二维数据点，构建KD树的过程： ? = (2,3), (5,7), (9,6), (4

强  机器学习能力 = 数据 + 特征 + 模型 • 数据  海量数据： 美团的亿级用户、千万级POI • 特征  大规模离散特征 > 小规模泛化特征 • 模型  DNN > 树模型 > LR 美团超大规模模型应用场景 • 可扩展的机器学习架构  基于Parameter Server架构  数据并行 —— 支持超大规模训练集  模型并行 —— 支持超大规模模型 粗排模型 • 精排模型 排序模型解决方案 • 粗排阶段的特点  候选集大，通常在千到万级别  线上的响应时间要求高，通常在几到十几ms • 简单模型  计算耗时短：线性模型LR、树模型  模型表达能力不足，效果一般 • 复杂模型  DNN模型解决耗时是关键，利用预计算解决耗时问题  效果保障：保证用户的个性化信息，降低候选集计算复杂度 粗排模型 • 精排阶段的特点  线上耗时相对宽松，几十毫秒（视效果而定） • 精排模型的特点  结构复杂，怎么有效果怎么来  特征多样：历史行为、统计值、id类特征、高维交叉, etc. • 模型发展历程  树模型：Random Forest、XGBoost  小规模DNN：MLP、小规模的Wide & Deep  大规模离散DNN：大规模的Wide & Deep、DeepFM、DCN 精排模型

XGBoost模型 - 采用近似求解算法，找出可能的分裂点，避免选用贪心算法的过高时间复杂度 - 计算采用不同分裂点时，叶子打分函数的增益；并选择增益最高的分裂点，作为新迭代树的最终分裂 节点，构造新的迭代树 - 通过调节迭代树数目、学习倍率、迭代树最大深度、L2正则化参数等进一步避免过拟合 2 获取样本数据 过滤数据 抽取基础特征 组合基础特征，构造组合特征 组合基础特征，构造组合特征 统计基础信息，构造统计特征

predict(X_test) LASSO linear_model.Lasso Ridge linear_model.Ridge ElasticNet linear_model.ElasticNet 回归树 tree.DecisionTreeRegressor 15 2.Scikit-learn主要用法 监督学习算法-分类 from sklearn.tree import DecisionTreeClassifier clf.fit(X_train, y_train) y_pred = clf.predict(X_test) y_prob = clf.predict_proba(X_test) 使用决策树分类算法解决二分类问题， y_prob 为每个样本预测为 “0”和“1”类的概率 16 1.Scikit-learn概述 逻辑回归 支持向量机 朴素贝叶斯 K近邻 linear_model.LogisticRegression depth=5) scores = cross_val_score(clf, X_train, y_train, cv=5, scoring=’f1_weighted’) 使用5折交叉验证对决策树模型进行评估， 使用的评分函数为F1值 sklearn提供了部分带交叉验证功能的模型 类如LassoCV、LogisticRegressionCV等， 这些类包含cv参数 26 2.Scikit-learn主要用法

感知机和SVM、神经网络。另外，线性回归类的几个模型一般情况下也 是需要做数据归一化/标准化处理的。 不需要做数据归一化/标准化 决策树、基于决策树的Boosting和Bagging等集成学习模型对于特征取 值大小并不敏感，如随机森林、XGBoost、LightGBM等树模型，以及 朴素贝叶斯，以上这些模型一般不需要做数据归一化/标准化处理。 3.正则化、偏差和方差 19 过拟合和欠拟合 欠拟合

感知机和SVM。另外，线性回归类的几个模型一般情况下也是需要做数 据归一化/标准化处理的。 不需要做数据归一化/标准化 决策树、基于决策树的Boosting和Bagging等集成学习模型对于特征取 值大小并不敏感，如随机森林、XGBoost、LightGBM等树模型，以及 朴素贝叶斯，以上这些模型一般不需要做数据归一化/标准化处理。 22 3. 正则化 01 线性回归 02 梯度下降

➢利用正则化，如L1, L2 范数，主要应用于如线性回归、逻辑回归以及 支持向量机(SVM)等算法；优点：降低过拟合风险；求得的 w 会有 较多的分量为零，即：它更容易获得稀疏解。 ➢使用决策树思想，包括决策树、随机森林、Gradient Boosting 等。 嵌入式 4. 特征选择 36 许永洪,吴林颖.中国各地区人口特征和房价波动的动态关系[J].统计研究,2019,36(01) 在