数据挖掘复习资料_西交 数据挖掘 复习

K-means 算法是一个迭代优化算法，每次迭代我们需要重新计算簇的中心。一般就是通过计算每个簇类所有样本的平均值来获得。可以使用 Numpy 里面的 mean 方法np.mean(x,0)来计算均值。K-means是一类非常经典的无监督机器学习算法，通常在实际应用中用于从数据集中找出不同样本的聚集模式，其基本原理就是类中样本的距离要远远小于类间样本的距离。
K-means聚类算法的流程如下：
首先从数据集x1,x2,x3,…,xn中随机选择k个样本作为簇中心
C=(C1,C2,…,Ck)。 然后，进入T轮迭代，在每个迭代中执行以下两个步骤。
1、对于每个样本 xi，计算距离其最近的簇中心yˉi=argmini dist(xi,Cj)
2、对于每一个簇j，重新计算其簇中心

其含义实际上就是对于每一个簇j，计算分配在其中的样本向量的平均值。
DBSCAN算法的基本概念
基本概念
在DBSCAN算法中，有两个基本的领域参数，分别为eps邻域和Minpts。
eps邻域表示的是在数据集D中与样本点xi的距离不大于eps的样本。
样本点xi的eps邻域如图所示：

在图中，样本点x不在样本点xi的eps邻域内。xi的密度由xi的eps邻域内的点的数量来估计。Minpts表示的是在样本点xi的eps邻域内的最少样本点数目。基于邻域参数 eps 和 Minpts（设置 Minpts 的值为8），在DBSCAN算法中将数据点分为以下三类：
1.核心点：若样本xi的eps邻域内至少包含了 Minpts 个样本，则称样本点xi为核心点。x1
2.边界点：若样本xi的eps邻域内包含的样本数目小于 Minpts，但是它在其它核心点的邻域内，则称样本点xi为边界点。x2
3.噪音点：指的是既不是核心点，又不是边界点的点。x3
DBSCAN算法的基本概念

在 DBSCAN 算法中，还定义了如下的一些概念：
1.直接密度可达：若样本点xj 在核心点xi的eps邻域内，则称样本点xj从样本点xi直接密度可达。样本点x2从样本点x1直接密度可达。样本点x3从样本点x2直接密度可达。
2.密度可达：若在样本点x1和样本点xn之间存在一序列x2,…,xn−1且xi+1从xi直接密度可达，则称xn从x1密度可达。x2从样本点x1直接密度可达，则样本点x3从样本点x1密度可达。
3.密度相连：对于样本点xi和样本点xj，若存在样本点xk，使得xi和xj都从xk密度可达，则称xi和xj密度相连。

DBSCAN算法原理
基于密度的聚类算法通过寻找被低密度区域分离的高密度区域，并将高密度区域作为一个簇。在DBSCAN算法中，聚类簇定义为：由密度可达关系导出的最大的密度相连样本集合。
DBSCAN算法流程
在DBSCAN算法中，由核心对象出发，找到与该核心对象密度可达的所有样本形成一个聚类簇。DBSCAN算法流程如下：

1. 如果一个点的eps邻域包含多于MinPits个对象，则创建一个集合P作为核心对象的新簇。
2. 寻找核心对象的直接密度可达的对象，并合并为一个新的簇。
3. 直到没有点可以更新簇时算法结束。
   降维
   既然维数太大可能引发维数灾难，那么如果能有算法能够自动地帮我们把重要性比较高的特征维度保留下来，把其他的维度过滤掉就好了。那这个过程我们称之为降维。
   从维数灾难的概念出发，我们就能知道降维的作用了。
   降低机器学习算法的时间复杂度；
   节省了提取不必要特征的开销；
   缓解因为维数灾难所造成的过拟合现象。
   PCA与降维
   降维的方法有很多，而最为常用的就是PCA(主成分分析)。 PCA 是将数据从原来的坐标系转换到新的坐标系，新的坐标系的选择是由数据本身决定的。第一个新坐标轴选择的是原始数据中方差最大的方向，第二个新坐标轴的选择和第一个坐标轴正交且方差最大的方向。然后该过程一直重复，重复次数为原始数据中的特征数量。最后会发现大部分方差都包含在最前面几个新坐标轴中，因此可以忽略剩下的坐标轴，从而达到降维的目的。
   PCA的算法流程
   PCA 在降维时，需要指定将维度降至多少维，假设降至 k 维，则 PCA 的算法流程如下：
   1、demean；
   2、计算数据的协方差矩阵；
   3、计算协方差矩阵的特征值与特征向量；
   4、 按照特征值，将特征向量从大到小进行排序；
   5、选取前 k 个特征向量作为转换矩阵；
   6、demean 后的数据与转换矩阵做矩阵乘法获得降维后的数据。
   欧氏距离
   欧氏距离是最容易直观理解的距离度量方法，两个点在空间中的距离一般都是指欧氏距离。
   二维平面上点a(x1,y1),b(x2,y2)间的欧氏距离:
   d12=sqrt(x1−x2)2+(y1−y2)2
   三维空间点a(x1,y1,z1),b(x2,y2,z2)间的欧氏距离:
   d12=sqrt(x1−x2)2+(y1−y2)2+(z1−z2)2
   n维空间点a(x11,x12,…,x1n),b(x21,x22,…,x2n)间的欧氏距离（两个n维向量）：
   d12=sqrtsumk=1n(x1k−x2k)2
   曼哈顿距离
   曼哈顿距离也称为“城市街区距离”。
   

聚类性能评估指标
外部指标
聚类的性能度量大致分为两类：一类是将聚类结果与某个参考模型作为参照进行比较，也就是所谓的外部指标；另一类则是直接度量聚类的性能而不使用参考模型进行比较，也就是内部指标。外部指标通常使用 Jaccard Coefficient ( JC系数 )、 Fowlkes and Mallows Index ( FM指数 )以及 Rand index （ Rand指数 ）。
首先需要计算出a，c，d，e。假设数据集E={x1,x2,…,xm}。通过聚类模型给出的簇划分为C={C1,C2,…Ck}，参考模型给出的簇划分为D={D1,D2,…Ds}。λ与λ∗分别表示C与D对应的簇标记，则有:

内部指标
内部指标通常使用 Davies-Bouldin Index ( DB 指数 )以及 Dunn Index （ Dunn 指数 ）。
DB指数
DB 指数又称 DBI，计算公式如下：

公式中的表达式其实很好理解，其中k代表聚类有多少个簇，μi代表第i个簇的中心点，avg(Ci)代表Ci第i个簇中所有数据与第i个簇的中心点的平均距离。dc(μi,μj)代表第i个簇的中心点与第j个簇的中心点的距离。
什么是逻辑回归
可能会认为逻辑回归是一种解决回归问题的算法，然而逻辑回归是通过回归的思想来解决二分类问题的算法。
逻辑回归是将样本特征和样本所属类别的概率联系在一起，假设现在已经训练好了一个逻辑回归的模型为 f(x) ，模型的输出是样本 x 的标签是 1 的概率，则该模型可以表示， p^=f(x) 。若得到了样本 x 属于标签 1 的概率后，很自然的就能想到当 p^>0.5 时 x 属于标签 1 ，否则属于标签 0 。所以就有

(其中 y^ 为样本 x 根据模型预测出的标签结果，标签 0 和标签 1 所代表的含义是根据业务决定的，比如在癌细胞识别中可以使 0 代表良性肿瘤， 1 代表恶性肿瘤)。
由于概率是 0 到 1 的实数，所以逻辑回归若只需要计算出样本所属标签的概率就是一种回归算法，若需要计算出样本所属标签，则就是一种二分类算法。
其实和线性回归有关系，线性回归无非就是训练出一组参数 WT 和 b 来拟合样本数据，线性回归的输出为 y^=WTx+b 。不过 y^ 的值域是 (−∞,+∞) ，如果能够将值域为 (−∞,+∞) 的实数转换成 (0,1) 的概率值的话问题就解决了。要解决这个问题很自然地就能想到将线性回归的输出作为输入，输入到另一个函数中，这个函数能够进行转换工作，假设函数为 σ ，转换后的概率为 p^ ，则逻辑回归在预测时可以看成p^=σ(WTx+b) 。
训练逻辑回归模型的过程其实与之前学习的线性回归一样，就是去寻找合适的 WT 和 b 使得模型的预测结果与真实结果尽可能一致。所以就需要一个函数能够衡量模型拟合程度的好坏，也就是说当模型拟合误差越大的时候，函数值应该比较大，反之应该比较小，这就是损失函数。
逻辑回归的损失函数
逻辑回归计算出的样本所属类别的概率 p^=σ(WTx+b) ，样本所属列表的判定条件为

很明显，在预测样本属于哪个类别时取决于算出来的p^。从另外一个角度来说，假设现在有一个样本的真实类别为 1 ，模型预测样本为类别 1 的概率为 0.9 的话，就意味着这个模型认为当前样本的类别有 90% 的可能性为 1 ，有 10% 的可能性为0。所以从这个角度来看，逻辑回归的损失函数与 p^ 有关。
支持向量机简介
SVM(支持向量机，英文全名：(Support Vector Machines,SVM)是分类器的一种，SVM有很多种实现，但是我们只讲序列最小优化算法Sequential Minimal Optimization,即SMO算法。 在正式介绍SVM之前，先解释几个概念考虑图6-1中个方框中的数据点分布，能否画出一条直线

这张图中的数据已经分的够开了，所以很容易在图中画出一条直线将两组数据点分开，在这种情况下，这种数据被称为线性可分数据。 上述将数据集分隔开来的直线称为分隔超平面（separatinghyperplane)。在上面给出的例子中，由于数据点都在二维平面上，所以此时分隔超平面就只是一条直线。但是，如果所给的数据集是三维的，那么此时用来分隔数据的就是一个平面。显而易见，更高维的情况可以依此类推。如果数据集是1024维的，那么就需要一个1023维的某某对象来对数据进行分隔。这个1023维的某某对象到底应该叫什么？ n-1维呢？该对象被称为超平面(hyperplane) ，也就是分类的决策边界。分布在超平面一侧的所有数据都属于某个类别，而分布在另一侧的所有数据则属于另一个类别。 我们希望能采用这种方式来构建分类器，即如果数据点离决策边界越远,那么其最后的预测结果也就越可信。考虑图6-2框B到框D的三条直线，它们都能将数据分隔开，但是其中哪一条最好呢？是否应该最小化数据点到分隔超平面的平均距离？来求最佳直线如果是那样，图6-2的B和C框中的直线是否真的就比D框中的直线好呢？如果这样做，是不是有点寻找最拟合直线的感觉？我们希望找到离分隔超平面最近的点，确保它们离分隔面的距离尽可能远。这里点到分隔面的距离被称为间隔。我们希望间隔尽可能地大，这是因为如果我们犯错或者在有限数据上训练分类器的话，我们希望分类器尽可能健壮。 支持向量（Support vector）就是离分割超平面最近的那些点。我们接下来要最大化支持向量到分割面的距离，需要找到此问题的优化求解方法。
寻找最大间隔
如图6-3，分隔超平面的形式可以写 ，要计算点八到分隔超平面的距离，就必须给出点到分隔面的法线或垂线的长度，该值为 。这里的常数b类似于Logisti回归中的截距W,这里的向量w和常数b一起描述了所给数据的分隔线或超平面。

SVM的一般框架： ⑴收集数据：可以使用任意方法。 (2)准备数据：需要数值型数据。 (3)分析数据：有助于可视化分隔超平面。 (4)训练算法：SVM的大部分时间都源自训练，该过程主要实现两个参数的调优。 (5)测试算法：十分简单的计算过程就可以实现。 (6)使用算法：几乎所有分类问题都可以使用SVM，值得一提的是，SVM本身是一个二类分类器，对多类问题应用SVM需要对代码做一些修改。
SVM的优缺点
优点：
(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；
(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；
(3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。
(4)SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题。
(5)SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。
(6)少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:
①增、删非支持向量样本对模型没有影响;
②支持向量样本集具有一定的鲁棒性;
③有些成功的应用中,SVM 方法对核的选取不敏感
缺点：
(1) SVM算法对大规模训练样本难以实施
由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法
(2) 用SVM解决多分类问题存在困难
经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。
决策树的相关概念
决策树是一种可以用于分类与回归的机器学习算法，但主要用于分类。用于分类的决策树是一种描述对实例进行分类的树形结构。决策树由结点和边组成，其中结点分为内部结点和叶子结点，内部结点表示一个特征或者属性，叶子结点表示标签（脑回路图中黄色的是内部结点，蓝色的是叶子结点）。
信息熵
信息是个很抽象的概念。信息熵的概念来描述信源的不确定度。信源的不确定性越大，信息熵也越大。
从机器学习的角度来看，信息熵表示的是信息量的期望值。如果数据集中的数据需要被分成多个类别，则信息量I(xi)的定义如下(其中xi表示多个类别中的第i个类别，p(xi)数据集中类别为xi的数据在数据集中出现的概率表示)：
I(Xi)=−log2p(xi)
由于信息熵是信息量的期望值，所以信息熵H(X)的定义如下(其中n为数据集中类别的数量)：
H(X)=−sumi=1np(xi)log2p(xi)
从这个公式也可以看出，如果概率是0或者是1的时候，熵就是0（因为这种情况下随机变量的不确定性是最低的）。那如果概率是0.5，也就是五五开的时候，此时熵达到最大，也就是1。（就像扔硬币，你永远都猜不透你下次扔到的是正面还是反面，所以它的不确定性非常高）。所以呢，熵越大，不确定性就越高。
条件熵
条件熵H(Y|X)表示特征X为某个值的条件下，类别为Y的熵。条件熵的计算公式如下：
H(Y∣X)=sumi=1npiH(Y∣X=xi)
当然条件熵的性质也和熵的性质一样，概率越确定，条件熵就越小，概率越五五开，条件熵就越大。
ID3算法
ID3算法其实就是依据特征的信息增益来构建树的。其大致步骤就是从根结点开始，对结点计算所有可能的特征的信息增益，然后选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，然后对子结点递归执行上述的步骤直到信息增益很小或者没有特征可以继续选择为止。
为什么要有训练集与测试集
我们想要利用收集的西瓜数据构建一个机器学习模型，用来预测新的西瓜的好坏，但在将模型用于新的测量数据之前，我们需要知道模型是否有效，也就是说，我们是否应该相信它的预测结果。不幸的是，我们不能将用于构建模型的数据用于评估模型的性能。因为我们的模型会一直记住整个训练集，所以，对于训练集中的任何数据点总会预测成正确的标签。这种记忆无法告诉我们模型的泛化能力如何，即预测新样本的能力如何。我们要用新数据来评估模型的性能。新数据是指模型之前没见过的数据，而我们有这些新数据的标签。通常的做法是，我们把手头上的数据分为两部分，训练集与测试集。训练集用来构建机器学习模型，测试集用来评估模型性能。
什么是欠拟合与欠拟合的原因
欠拟合：模型在训练集上误差很高；
欠拟合原因：模型过于简单，没有很好的捕捉到数据特征，不能很好的拟合数据。

如上面例子，我们的数据是一份非线性数据，如果你想要用线性回归来拟合这份数据，由于数据是非线性的，模型是线性，则过于简单。所以，无论模型怎么训练，最终都不能很好的拟合数据。
什么是过拟合与过拟合的原因
过拟合：在训练集上误差低，测试集上误差高；
过拟合原因：模型把数据学习的太彻底，以至于把噪声数据的特征也学习到了，这样就会导致在后期测试的时候不能够很好地识别数据，模型泛化能力太差。

如上面例子，在训练集上，模型为了拟合数据，添加了更多的多次项，使模型过于复杂，对噪音数据也能很好的拟合，所以在训练集上正确率很高，而在测试集上没有这些噪音数据，所以正确率很低。
在分类的问题中，如下例子:
欠拟合：由于模型过于简单，只学习到绿色这个特征，只要是绿色就都判断为树叶，结果将树当做了树叶。
过拟合：模型过于复杂，将锯齿这个普通特征，看的过于重要，认为必须有锯齿才是树叶，结果将树叶误判为不是树叶。偏差与方差
偏差：预计值的期望与真实值之间的差距；
方差：预测值的离散程度，也就是离其期望值的距离
防止过拟合的方法：
（1） 数据扩增，这是解决过拟合最有效的方法，但是对于算法工程师来说，目前的数据是固定不变的，不应该从这里下手收集更多数据，而是找其他方法。
（2） 选择合适的模型，其实过拟合最主要的2个原因是：数据太少+模型太复杂，前面提到数据很难再去收集了，但是我们可以选择合适复杂度的模型来防止过拟合问题。对于神经网络来说，我们可以从以下几个方面来限制网络的拟合能力，从而防止过拟合：
（3） 正则化方法（regularization）：正则化方法是指在进行目标函数或代价函数优化时，在目标函数或代价函数后面加上一个正则项，一般有L1正则与L2正则等。
弹性网络是一种使用 L1，L2范数作为先验正则项训练的线性回归模型.这种组合允许学习到一个只有少量参数是非零稀疏的模型，就像 Lasso一样，但是它仍然保持一些像Ridge的正则性质。我们可利用 l1_ratio 参数控制L1和L2的凸组合。弹性网络是一不断叠代的方法
弹性网络最妙的地方是它永远可以产生有效解。由于它不会产生交叉的路径，所以产生的解都相当不错。举例来说，对一个随机产生的50个城市的推销员问题，弹性网络的解只有比德宾和威尔萧的论文中所提的最具竞争力的演算法长2%（什么是最具竞争力的演算法？有人说是林－克尼根（Lin-Kernighan）演算法，也有人说是SA+OP）。但是弹性网络最吸引人的地方不在它的有效解，而在它收敛的速度。许多人试着去改善弹性网络收敛的速度，都有不错的结果。举例来说，柏尔（Burr）所提出的改良版可令50个城市的推销员问题的收敛次数由1250大幅降为30次。一个最佳化的弹性网络的速度会比林－克尼根快两倍。
弹性网络在很多特征互相联系的情况下是非常有用的。Lasso 很可能只随机考虑这些特征中的一个，而弹性网络更倾向于选择两个。 在实践中，Lasso 和 Ridge 之间权衡的一个优势是它允许在循环过程（Under rotate）中继承 Ridge 的稳定性。
L1,L2正则化关系
L1正则化会让你的参数变得更稀疏，也就是使很多参数退化到0，这样可以起到类似于Dropout和特征选取的功能。另外，L1正则化的公式不可导，这使得反向求偏导数以优化参数时计算过程变得复杂，也使得优化带有L1正则化项的损失函数更加复杂，方法也五花八门。
L2正则化，则不会让你的参数退化到0，也就是使你的参数稀疏，因为有平方的存在，当参数很小的时候，这个参数基本就被忽略了，并不会被进一步调整为0。而且L2正则化的公式可导，这使得在优化时计算过程比L1要简洁。
支持度和置信度、Apriori算法
支持度a表示，a出现次数/总次数。支持度（a，b）表示a，c在一个例子中同时出现次数/总次数
Support(X→Y) = P(X,Y) / P(I) = P(X∪Y) / P(I) = num(XUY) / num(I)
a对b的置信度：a为条件，且使用条件公式 a，b同时发生次数/a发生次数。
Confidence(X→Y) = P(Y|X) = P(X,Y) / P(X) = P(XUY) / P(X)

此题中最小置信度自定于为0.2.概率大于等于0.2才可以出现，否则删除

欢迎大家加我微信学习讨论