【数据挖掘】--算法

目录：

1. 缺失值和数值属性处理

1缺失值处理：

删除法：当缺失值比例较小时，可删除包含缺失值的样本。但这种方法会损失数据，可能影响模型准确性。例如在一个客户信息表中，若少数客户的某个不关键属性有缺失值，可删除这些记录。
- 填补法：
- 均值/中位数填补：对于数值属性，用该属性的均值或中位数填补缺失值。比如在学生成绩数据中，用平均成绩填补缺失的成绩值。
- 模型预测填补：利用其他属性和机器学习模型预测缺失值。如使用线性回归模型，基于学生的平时表现、作业成绩等属性预测缺失的考试成绩。

• 数值属性处理：
  • 归一化：将数值属性的值映射到[0, 1]或[-1, 1]区间，消除量纲影响。常见方法有最小 - 最大归一化：$x_{new}=\frac{x-x_{min}}{x_{max}-x_{min}}$。例如在处理不同单位的身高和体重数据时，归一化可使它们在同一尺度上。
  • 标准化：使数据具有零均值和单位方差，公式为$z=\frac{x-\mu }{\sigma }$，其中$\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$表示“垃圾邮件”和“非垃圾邮件”类别，$x_i$可以是邮件中出现的单词。通过训练数据计算$P(C)$（先验概率）和$P(x_i|C)$（似然概率），进而对新邮件进行分类。

3. 分治法：建立决策树

• 计算信息量：信息熵是衡量数据不确定性的指标，
• **公式为$H(X)=-\sum_{i = 1}^{n}p(x_i)\log_2p(x_i)$，
• 其中$p(x_i)$是事件$x_i$发生的概率。在决策树构建中，通过计算信息增益来选择分支属性。****
• 信息增益 $IG(X,Y)=H(X)-H(X|Y)$，$H(X)$是数据集$X$的熵，$H(X|Y)$是在属性$Y$给定条件下$X$的条件熵。
• 高度分支属性：通常选择信息增益最大的属性作为分支属性，这样能使决策树在每一步划分后，数据的不确定性减少最多。例如在根据天气属性（晴天、多云、雨天等）和温度属性划分是否适合户外运动的数据集时，计算每个属性的信息增益，选择信息增益大的属性优先进行分支。
  

4. 覆盖算法建立规则

• 一个简单的覆盖方法：从整个数据集开始，找到一条能覆盖尽可能多正例且少覆盖反例的规则。然后从数据集中移除该规则覆盖的正例，重复上述过程，直到所有正例都被覆盖。例如在一个二分类任务中，先找到一条规则“如果年龄
  

30 且收入 > 50000，那么类别为 A”，移除符合该规则的正例后继续寻找下一条规则。

• 规则与决策列表：决策列表是由一系列规则组成，按顺序应用这些规则进行分类。挖掘决策列表时，每次选择最优规则添加到列表中，并更新数据集，直到数据集分类完成。

5. 挖掘关联规则

• 项集：项集是一组项的集合。例如在超市购物篮数据中，{牛奶, 面包}就是一个项集。频繁项集是指出现次数达到一定阈值的项集。
• 关联规则：形如$A\Rightarrow B$，表示如果项集$A$出现，那么项集$B$也可能出现。例如“购买啤酒的顾客也倾向于购买尿布”。
• 有效的生成规则：常用Apriori算法，它基于“频繁项集的所有非空子集也一定是频繁的”这一先验性质，通过逐层搜索生成频繁项集，进而生成关联规则。首先找到频繁1 - 项集，然后生成候选2 - 项集，剪枝得到频繁2 - 项集，以此类推。

6. 线性模型

• 数值预测：线性回归：假设因变量$y$与自变量$x_1,x_2,\cdots,x_n$之间存在线性关系$加粗样式y={\beta }_0+{\beta }_1{x}_1+{\beta }_2{x}_2+\cdots +{\beta }_n{x}_n+ϵ$，

• 其中${\beta }_i$是系数，$ϵ$是误差项。通过最小化损失函数（如均方误差$MSE=\frac{1}{n}{\sum }_{i=1}^n(y_i-{\hat{y}}_i{)}^2$，

• $y_i$是真实值，${\hat{y}}_i$是预测值）来确定系数${\beta }_i$。例如预测房价，$y$是房价，$x_1$是房屋面积，$x_2$ 是房间数量等。

• 线性分类：Logistic回归：用于二分类问题，通过将线性函数的输出经过Sigmoid函数$\sigma (z)=\frac{1}{1+e^{-z}}$，
  

• 将结果映射到[0, 1]区间，表示样本属于正类的概率。损失函数通常使用对数似然损失，通过梯度下降等方法优化参数。

• 使用感知机的线性分类：感知机是一种简单的线性分类模型，通过权重向量$w$和偏置$b$对输入特征向量$x$进行线性组合$y=\text{sign}(w^{T}x+b)$，其中$\text{sign}$是符号函数。感知机通过不断调整$w$和$b$，使误分类样本数量减少。

• 使用Winnow的线性分类：Winnow是一种用于在线学习的线性分类算法，它通过对权重进行指数式更新来处理二分类问题，对不同特征赋予不同的权重，更关注重要特征。

有效寻找最近邻

暴力搜索（Brute-Force Search）

• 原理：对于给定的查询点，计算它与数据集中所有点的距离，然后找出距离最小的点，即最近邻。
• 示例：假设有一个包含多个二维点的数据集{(1,2), (3,4), (5,6), (7,8)}，要查找点(2,3)的最近邻。通过计算(2,3)与数据集中每个点的欧氏距离，如与(1,2)的距离为$\sqrt{(2-1{)}^2+(3-2{)}^2}=\sqrt{2}$，与(3,4)的距离为$\sqrt{(2-3{)}^2+(3-4{)}^2}=\sqrt{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 Hashing，LSH）

• 原理：利用哈希函数将数据点映射到哈希桶中，使得相似的数据点有较高概率被映射到同一个哈希桶或相邻的哈希桶中。在搜索时，只需在查询点所在的哈希桶及相邻哈希桶中查找最近邻。
• 示例：对于文本数据，可以根据文本的特征构建哈希函数。例如，将文本中出现的单词组合作为特征，通过哈希函数将文本映射到不同的哈希桶。如果两个文本相似，它们包含的单词组合相似，就可能被映射到同一个或相邻的哈希桶中。
• 优缺点：能快速处理大规模数据，在高维数据和近似最近邻搜索中表现出色；但可能会有一定的误报率，即找到的不一定是真正的最近邻，而是近似最近邻。

球树（Ball Tree）

• 原理：将数据点划分到一系列嵌套的球中，每个节点对应一个球，球内包含若干数据点。搜索时，通过判断查询点与球的位置关系，快速确定是否需要在该球内继续搜索。
• 示例：假设有一组三维数据点，球树会将这些点划分到不同的球中，比如一个球内包含(1,1,1), (2,2,2), (3,3,3)等点，另一个球内包含(4,4,4), (5,5,5)等点。在查找最近邻时，先判断查询点位于哪些球附近，再进一步在这些球内搜索。
• 优缺点：相比kd树，在高维数据下可能有更好的性能；但构建球树的时间和空间复杂度较高。

局部敏感哈希（Locality Sensitive Hashing，LSH）

• 原理：利用哈希函数将数据点映射到哈希桶中，使得相似的数据点有较高概率被映射到同一个哈希桶或相邻的哈希桶中。在搜索时，只需在查询点所在的哈希桶及相邻哈希桶中查找最近邻。
• 示例：对于文本数据，可以根据文本的特征构建哈希函数。例如，将文本中出现的单词组合作为特征，通过哈希函数将文本映射到不同的哈希桶。如果两个文本相似，它们包含的单词组合相似，就可能被映射到同一个或相邻的哈希桶中。
• 优缺点：能快速处理大规模数据，在高维数据和近似最近邻搜索中表现出色；但可能会有一定的误报率，即找到的不一定是真正的最近邻，而是近似最近邻。
  ht-aligned 文本居右 |

7. 基于实例的学习

**- 距离函数：用于衡量实例之间的相似性，常见的有欧几里得距离$d(x,y)=\sqrt{{\sum }_{i=1}^n(x_i-y_i{)}^2}$，曼哈顿距离$d(x,y)={\sum }_{i=1}^n|x_i-y_i|$。例如在二维空间中，计算两个点之间的距离。

• 有效寻找最近邻：可以使用KD - 树等数据结构加速最近邻搜索。KD - 树将数据空间递归划分，通过比较当前节点的分割轴坐标，快速定位可能包含最近邻的子空间。**

8. 聚类

• 基于距离的迭代聚类：如K - Means算法，首先随机选择$k$个质心，然后将每个样本分配到距离最近的质心所在的簇，接着重新计算每个簇的质心，重复上述过程直到质心不再变化或达到最大迭代次数。目标函数是最小化每个样本到其所属簇质心的距离平方和

$J={\sum }_{i=1}^k{\sum }_{x_j\in C_i}{\Vert x_j-{\mu }_i\Vert }^2$，其中$k$是簇的数量，$C_i$是第$i$个簇，${\mu }_i$是第$i$个簇的质心，$x_j$是

数据点。

• 快速距离计算：对于大规模数据集，可以采用一些近似算法或利用数据结构加速距离计算，如使用三角不等式等性质减少不必要的距离计算。

• 多实例学习：与传统单实例学习不同，多实例学习中每个样本由多个实例组成一个包（bag），标签作用于包而不是单个实例。例如在图像分类中，一张图像可能包含多个物体，图像（包）被标记为包含某种物体（正例）或不包含（反例），但不知道具体哪个物体实例对应标签。

• 聚集输入：将多个输入实例组合成一个更复杂的输入表示，例如将多个时间序列数据聚合为一个特征矩阵，以捕捉数据的全局特征。

• 聚集输出：将多个模型的输出进行聚合，如在集成学习中，将多个分类器的预测结果通过投票、平均等方式聚合，得到最终的预测结果。
  

9. Weka

Weka是一个基于Java的开源机器学习软件，包含了大量的机器学习算法和工具。它提供了图形界面（如Explorer、Experimenter等）和命令行界面，方便用户进行数据预处理、模型训练、评估等操作。例如，在Weka的Explorer界面中，可以直接加载ARFF格式数据，选择不同的分类算法（如朴素贝叶斯、决策树等）进行训练和测试，并查看模型性能指标。