注册网站流程,用ps制作网页步骤,深入解析 wordpress,wordpress 获取根目录【数据挖掘】--算法 目录#xff1a;1. 缺失值和数值属性处理1缺失值处理#xff1a; 2. 用于文档分类的朴素贝叶斯3. 分治法#xff1a;建立决策树4. 覆盖算法建立规则5. 挖掘关联规则6. 线性模型有效寻找最近邻暴力搜索#xff08;Brute-Force Search#xff09;kd树1. 缺失值和数值属性处理1缺失值处理 2. 用于文档分类的朴素贝叶斯3. 分治法建立决策树4. 覆盖算法建立规则5. 挖掘关联规则6. 线性模型有效寻找最近邻暴力搜索Brute-Force Searchkd树k-dimensional Tree局部敏感哈希Locality Sensitive HashingLSH球树Ball Tree局部敏感哈希Locality Sensitive HashingLSH 7. 基于实例的学习8. 聚类9. Weka 目录
1. 缺失值和数值属性处理
1缺失值处理 删除法当缺失值比例较小时可删除包含缺失值的样本。但这种方法会损失数据可能影响模型准确性。例如在一个客户信息表中若少数客户的某个不关键属性有缺失值可删除这些记录。 - 填补法 - 均值/中位数填补对于数值属性用该属性的均值或中位数填补缺失值。比如在学生成绩数据中用平均成绩填补缺失的成绩值。 - 模型预测填补利用其他属性和机器学习模型预测缺失值。如使用线性回归模型基于学生的平时表现、作业成绩等属性预测缺失的考试成绩。 数值属性处理 归一化将数值属性的值映射到[0, 1]或[-1, 1]区间消除量纲影响。常见方法有最小 - 最大归一化 x n e w x − x m i n x m a x − x m i n x_{new}\frac{x - x_{min}}{x_{max}-x_{min}} xnewxmax−xminx−xmin。例如在处理不同单位的身高和体重数据时归一化可使它们在同一尺度上。标准化使数据具有零均值和单位方差公式为 z x − μ σ z\frac{x - \mu}{\sigma} zσx−μ其中 μ \mu μ是均值 σ \sigma σ是标准差。这在许多基于距离的算法中很重要如K近邻算法。
2. 用于文档分类的朴素贝叶斯
朴素贝叶斯基于贝叶斯定理和特征条件独立假设。假设文档$d$由特征向量$x(x_1,x_2,\cdots,x_n)$表示类别为$C$。贝叶斯定理为$P(C|x)\frac{P(x|C)P(C)}{P(x)}$。由于特征条件独立假设$P(x|C)\prod_{i 1}^{n}P(x_i|C)$。例如在垃圾邮件分类中 C C C表示“垃圾邮件”和“非垃圾邮件”类别 x i x_i xi可以是邮件中出现的单词。通过训练数据计算 P ( C ) P(C) P(C)先验概率和 P ( x i ∣ C ) P(x_i|C) P(xi∣C)似然概率进而对新邮件进行分类。
3. 分治法建立决策树
计算信息量信息熵是衡量数据不确定性的指标**公式为$H(X)-\sum_{i 1}^{n}p(x_i)\log_2p(x_i)$其中 p ( x i ) p(x_i) p(xi)是事件 x i x_i xi发生的概率。在决策树构建中通过计算信息增益来选择分支属性。****信息增益 $IG(X,Y)H(X)-H(X|Y)$$H(X)$是数据集$X$的熵 H ( X ∣ Y ) H(X|Y) H(X∣Y)是在属性 Y Y Y给定条件下 X X X的条件熵。高度分支属性通常选择信息增益最大的属性作为分支属性这样能使决策树在每一步划分后数据的不确定性减少最多。例如在根据天气属性晴天、多云、雨天等和温度属性划分是否适合户外运动的数据集时计算每个属性的信息增益选择信息增益大的属性优先进行分支。
4. 覆盖算法建立规则
一个简单的覆盖方法从整个数据集开始找到一条能覆盖尽可能多正例且少覆盖反例的规则。然后从数据集中移除该规则覆盖的正例重复上述过程直到所有正例都被覆盖。例如在一个二分类任务中先找到一条规则“如果年龄
30 且收入 50000那么类别为 A”移除符合该规则的正例后继续寻找下一条规则。
规则与决策列表决策列表是由一系列规则组成按顺序应用这些规则进行分类。挖掘决策列表时每次选择最优规则添加到列表中并更新数据集直到数据集分类完成。 5. 挖掘关联规则
项集项集是一组项的集合。例如在超市购物篮数据中{牛奶, 面包}就是一个项集。频繁项集是指出现次数达到一定阈值的项集。关联规则形如 A ⇒ B A \Rightarrow B A⇒B表示如果项集 A A A出现那么项集 B B B也可能出现。例如“购买啤酒的顾客也倾向于购买尿布”。有效的生成规则常用Apriori算法它基于“频繁项集的所有非空子集也一定是频繁的”这一先验性质通过逐层搜索生成频繁项集进而生成关联规则。首先找到频繁1 - 项集然后生成候选2 - 项集剪枝得到频繁2 - 项集以此类推。
6. 线性模型 数值预测线性回归假设因变量 y y y与自变量$x_1,x_2,\cdots,x_n$之间存在线性关系 加粗样式 y β 0 β 1 x 1 β 2 x 2 ⋯ β n x n ϵ 加粗样式y\beta_0\beta_1x_1\beta_2x_2\cdots\beta_nx_n\epsilon 加粗样式yβ0β1x1β2x2⋯βnxnϵ 其中 β i \beta_i βi是系数 ϵ \epsilon ϵ是误差项。通过最小化损失函数如均方误差 M S E 1 n ∑ i 1 n ( y i − y ^ i ) 2 MSE\frac{1}{n}\sum_{i 1}^{n}(y_i - \hat{y}_i)^2 MSEn1∑i1n(yi−y^i)2 y i y_i yi是真实值 y ^ i \hat{y}_i y^i是预测值来确定系数 β i \beta_i βi。例如预测房价 y y y是房价 x 1 x_1 x1是房屋面积 x 2 x_2 x2 是房间数量等。 线性分类Logistic回归用于二分类问题通过将线性函数的输出经过Sigmoid函数 σ ( z ) 1 1 e − z \sigma(z)\frac{1}{1 e^{-z}} σ(z)1e−z1 将结果映射到[0, 1]区间表示样本属于正类的概率。损失函数通常使用对数似然损失通过梯度下降等方法优化参数。 使用感知机的线性分类感知机是一种简单的线性分类模型通过权重向量 w w w和偏置 b b b对输入特征向量 x x x进行线性组合 y sign ( w T x b ) y \text{sign}(w^Tx b) ysign(wTxb)其中 sign \text{sign} sign是符号函数。感知机通过不断调整 w w w和 b b b使误分类样本数量减少。 使用Winnow的线性分类Winnow是一种用于在线学习的线性分类算法它通过对权重进行指数式更新来处理二分类问题对不同特征赋予不同的权重更关注重要特征。
有效寻找最近邻
暴力搜索Brute-Force Search
原理对于给定的查询点计算它与数据集中所有点的距离然后找出距离最小的点即最近邻。示例假设有一个包含多个二维点的数据集{(1,2), (3,4), (5,6), (7,8)}要查找点(2,3)的最近邻。通过计算(2,3)与数据集中每个点的欧氏距离如与(1,2)的距离为 ( 2 − 1 ) 2 ( 3 − 2 ) 2 2 \sqrt{(2 - 1)^2(3 - 2)^2}\sqrt{2} (2−1)2(3−2)2 2 与(3,4)的距离为 ( 2 − 3 ) 2 ( 3 − 4 ) 2 2 \sqrt{(2 - 3)^2(3 - 4)^2}\sqrt{2} (2−3)2(3−4)2 2 等比较后发现(1,2)和(3,4)都是(2,3)的最近邻。优缺点优点是实现简单在数据集较小时效果较好缺点是当数据集规模较大时计算量呈指数增长效率低下。
kd树k-dimensional Tree 原理将数据点按照k维空间进行划分构建树形结构。在搜索最近邻时利用树的结构快速排除不可能是最近邻的区域从而减少计算量。 示例对于二维数据集kd树可能会按照x轴或y轴交替划分数据空间。比如有数据点(1,1), (2,3), (4,2), (3,5)可能先按照x轴将空间分为两部分左边包含(1,1)右边包含(2,3), (4,2), (3,5)然后在右半部分再按照y轴划分等。在查找最近邻时从根节点开始根据查询点与节点的位置关系决定搜索路径。 优缺点适用于低维数据能显著提高搜索效率但在高维数据下性能可能下降存在“维数灾难”问题。 原理将数据点划分到一系列嵌套的球中每个节点对应一个球球内包含若干数据点。搜索时通过判断查询点与球的位置关系快速确定是否需要在该球内继续搜索。 示例假设有一组三维数据点球树会将这些点划分到不同的球中比如一个球内包含(1,1,1), (2,2,2), (3,3,3)等点另一个球内包含(4,4,4), (5,5,5)等点。在查找最近邻时先判断查询点位于哪些球附近再进一步在这些球内搜索。 优缺点相比kd树在高维数据下可能有更好的性能但构建球树的时间和空间复杂度较高。 局部敏感哈希Locality Sensitive HashingLSH
原理利用哈希函数将数据点映射到哈希桶中使得相似的数据点有较高概率被映射到同一个哈希桶或相邻的哈希桶中。在搜索时只需在查询点所在的哈希桶及相邻哈希桶中查找最近邻。示例对于文本数据可以根据文本的特征构建哈希函数。例如将文本中出现的单词组合作为特征通过哈希函数将文本映射到不同的哈希桶。如果两个文本相似它们包含的单词组合相似就可能被映射到同一个或相邻的哈希桶中。优缺点能快速处理大规模数据在高维数据和近似最近邻搜索中表现出色但可能会有一定的误报率即找到的不一定是真正的最近邻而是近似最近邻。
球树Ball Tree
原理将数据点划分到一系列嵌套的球中每个节点对应一个球球内包含若干数据点。搜索时通过判断查询点与球的位置关系快速确定是否需要在该球内继续搜索。示例假设有一组三维数据点球树会将这些点划分到不同的球中比如一个球内包含(1,1,1), (2,2,2), (3,3,3)等点另一个球内包含(4,4,4), (5,5,5)等点。在查找最近邻时先判断查询点位于哪些球附近再进一步在这些球内搜索。优缺点相比kd树在高维数据下可能有更好的性能但构建球树的时间和空间复杂度较高。
局部敏感哈希Locality Sensitive HashingLSH
原理利用哈希函数将数据点映射到哈希桶中使得相似的数据点有较高概率被映射到同一个哈希桶或相邻的哈希桶中。在搜索时只需在查询点所在的哈希桶及相邻哈希桶中查找最近邻。示例对于文本数据可以根据文本的特征构建哈希函数。例如将文本中出现的单词组合作为特征通过哈希函数将文本映射到不同的哈希桶。如果两个文本相似它们包含的单词组合相似就可能被映射到同一个或相邻的哈希桶中。优缺点能快速处理大规模数据在高维数据和近似最近邻搜索中表现出色但可能会有一定的误报率即找到的不一定是真正的最近邻而是近似最近邻。 ht-aligned 文本居右 |
7. 基于实例的学习
**- 距离函数用于衡量实例之间的相似性常见的有欧几里得距离 d ( x , y ) ∑ i 1 n ( x i − y i ) 2 d(x,y)\sqrt{\sum_{i 1}^{n}(x_i - y_i)^2} d(x,y)∑i1n(xi−yi)2 曼哈顿距离 d ( x , y ) ∑ i 1 n ∣ x i − y i ∣ d(x,y)\sum_{i 1}^{n}|x_i - y_i| d(x,y)∑i1n∣xi−yi∣。例如在二维空间中计算两个点之间的距离。
有效寻找最近邻可以使用KD - 树等数据结构加速最近邻搜索。KD - 树将数据空间递归划分通过比较当前节点的分割轴坐标快速定位可能包含最近邻的子空间。**
8. 聚类
基于距离的迭代聚类如K - Means算法首先随机选择 k k k个质心然后将每个样本分配到距离最近的质心所在的簇接着重新计算每个簇的质心重复上述过程直到质心不再变化或达到最大迭代次数。目标函数是最小化每个样本到其所属簇质心的距离平方和 J ∑ i 1 k ∑ x j ∈ C i ∥ x j − μ i ∥ 2 J\sum_{i 1}^{k}\sum_{x_j \in C_i}\left \| x_j - \mu_i \right \|^2 J∑i1k∑xj∈Ci∥xj−μi∥2其中 k k k是簇的数量 C i C_i Ci是第 i i i个簇 μ i \mu_i μi是第 i i i个簇的质心 x j x_j xj是 数据点。 快速距离计算对于大规模数据集可以采用一些近似算法或利用数据结构加速距离计算如使用三角不等式等性质减少不必要的距离计算。 多实例学习与传统单实例学习不同多实例学习中每个样本由多个实例组成一个包bag标签作用于包而不是单个实例。例如在图像分类中一张图像可能包含多个物体图像包被标记为包含某种物体正例或不包含反例但不知道具体哪个物体实例对应标签。 聚集输入将多个输入实例组合成一个更复杂的输入表示例如将多个时间序列数据聚合为一个特征矩阵以捕捉数据的全局特征。 聚集输出将多个模型的输出进行聚合如在集成学习中将多个分类器的预测结果通过投票、平均等方式聚合得到最终的预测结果。
9. Weka
Weka是一个基于Java的开源机器学习软件包含了大量的机器学习算法和工具。它提供了图形界面如Explorer、Experimenter等和命令行界面方便用户进行数据预处理、模型训练、评估等操作。例如在Weka的Explorer界面中可以直接加载ARFF格式数据选择不同的分类算法如朴素贝叶斯、决策树等进行训练和测试并查看模型性能指标。
