The Keynote of Data Mining by myself
数据挖掘—–自己整理的笔记
将近一个月没有更新博客，主要这期间有太多的考试，数据挖掘就是其中的一门比较难的课程，由于一直不敢怎么掉以轻心，总结了好长的笔记来复习。其实在读研期间也曾考虑学习Data Mining方向，虽说不是很擅长，但是通过这门课也算是data mining入了门。
本科时候也学过这门课，那时候主要以计算为主，其中的原理有很多是云里雾里的感觉。这次的学习，使得我从数据的预处理，到关联规则，分类，聚类的算法，有了清晰的了解，并可以通过分析各个算法的优缺点，改进现有某个算法的存在的问题。
比如：
#####支持向量机（ SVM）是 一种具有高准确率的分类方法。但是SVM 处理大型数据元组集时，速度很慢试开发一种可伸缩的算法克服以上困难。
- 先使用层次聚类的CF-tree构造出微小的聚类簇
- 找出聚类簇的质心代表该聚类，然后使用SVM进行训练,这样可以大大减少数据元组的数量。
- 找出超平面来划分这些微型聚类簇。
- 加入新的聚类簇来进行SVM训练
- 直到没有新的聚类簇加入，分类完毕
又比如：
#####提升的基本思想:假设你是一位患者,有某某些症状.你选择咨询多位医生,假设你根据医生先前的诊断准确率,对每位医生的诊断赋予一个权重.然后这些加权诊断的组合最为最终的诊断,这就是提升的基本思想.
提高决策归纳准确性的原因:在提升方法中,权重赋予每个训练元组.迭代的学习K个分类器序列,学习得到分类器Mi之后,更新权重,使得其后的分类器Mi+1”更关注” Mi误分类的训练元组，最终提升的分类器M*组合每个个体分类器，其中每个分类器投票的权重是其准确率的函数。可以扩充提升算法，预测连续值。
这个就是分类与聚类的结合，通过这种方式，我们克服了SVM的缺点，为我们所用！
下面贴出我从数据预处理，OLAP，到数据各种分类算法的笔记：
——————————————————————————————————–
1.数据仓库的概念： 数据仓库是一种为信息分析提供了良好的基础并支持管理决策活动的分析环境，是面向主题的，集成的，稳定的，不可更新的,随时间变化的，分层次的,多维的集成数据集合。
特点： 1主题与面向主题；2数据的集成性；3数据的不可更新性；4数据的时态性。为什么要建立数据仓库：为了使数据能够发挥其最佳效用，更好的为用户服务，才要建立数据仓库。它可以从各信息源提取决策需要的数据，加工后，存储到数据仓库中；并且可以提供用户的查询和决策分析的依据。
为什么建立数据仓库
} 提高两个系统的性能
◦ DBMS是为OLTP而设计的：存储方式,索引, 并发控制, 恢复
◦ 数据仓库是为OLAP而设计：复杂的 OLAP查询, 多维视图，汇总
} 不同的功能和不同的数据:
◦ 历史数据: 决策支持需要历史数据，而这些数据在操作数据库中一般不会去维护
◦ 数据汇总：决策支持需要将来自异种源的数据统一（如聚集和汇总）
◦ 数据质量: 不同的源使用不一致的数据表示、编码和格式，对这些数据进行有效的分析需要将他们转化后进行集成
建立数据仓库过程：
1.自顶向下法：由总体设计和规划开始，在技术成熟、商业理解透彻的情况下使用。
2.自底向上法：以实验和原型开始，常用在模型和技术开发的初期，可以有效的对使用的技术和模型进行评估，降低风险。 3.混合方法：上述两者的结合
从软件过程的观点
1.瀑布式方法：在进行下一步前，每一步都进行结构化和系统的分析
2.螺旋式方法：功能渐增的系统的快速产生，相继版本之间间隔很短
- 数据预处理：
} 不完整数据的成因：
◦ 数据收集的时候就缺乏合适的值
◦ 数据收集时和数据分析时的不同考虑因素
◦ 人为/硬件/软件 问题
} 噪声数据（不正确的值）的成因
◦ 数据收集工具的问题
◦ 数据输入时的 人为/计算机 错误
◦ 数据传输中产生的错误
} 数据不一致性的成因
◦ 不同的数据源
◦ 违反了函数依赖性
} 没有高质量的数据，就没有高质量的挖掘结果
◦ 高质量的决策必须依赖高质量的数据
◦ 数据仓库需要对高质量的数据进行一致地集成
◦ 数据预处理将是构建数据仓库或者进行数据挖掘的工作中占工作量最大的一个步骤
} 数据清理
◦ 填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性
} 数据集成
◦ 集成多个数据库、数据立方体或文件
} 数据变换
◦ 规范化和聚集
} 数据归约
◦ 得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果
} 数据离散化
◦ 数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要
3.数据仓库的数据模型有哪些？
数据仓库的数据模型包括：星型数据模型、雪花型数据模型、星群型数据模型。
其中星型模型包括一个中央表（事实表）和一系列的附表（维度表），附表环绕中央表，并产生关系，但不关联。雪花型数据模型设计其附表（维度表）被进一步规范化，分割出额外的表，产生的图形像雪花状。这种形式易于维护并节省存储空间。但表之间的关联多，影响系统的性能，其使用没有星型构架广泛。星群型架构的数据模型设计是多个主表（事实表）共享附表（维度表），其是星型的集合。对于数据集市使用星群数据模型，雪花模型。
#####4.OLAP操作主要优点
} 数据视图经过演化的、集成的数据
} OLAP面向市场（分析）历史的、汇总的数据
} 访问模式只读查询（但很多是复杂的查询）
} 访问数据量数百万个
} 用户数数百个
} 数据库规模100GB-数TB
} 设计优先性高灵活性、端点用户自治
◦ 度量查询吞吐量、响应时间，复杂的 OLAP查询, 多维视图，汇总
} 不同的功能和不同的数据:
◦ 历史数据: 决策支持需要历史数据，而这些数据在操作数据库中一般不会去维护
◦ 数据汇总：决策支持需要将来自异种源的数据统一（如聚集和汇总）
◦ 数据质量: 不同的源使用不一致的数据表示、编码和格式，对这些数据进行有效的分析需要将他们转化后进行集成
5.OLAP操作方法
} 上卷(roll-up):汇总数据
◦ 通过一个维的概念分层向上攀升或者通过维规约
◦ 当用维归约进行上卷时，一个或多个维由给定的数据立方体删除
} 下钻(drill-down)：上卷的逆操作
◦ 由不太详细的数据到更详细的数据，可以通过沿维的概念分层向下或引入新的维来实现 (为给定数据添加更多细节)
} 切片和切块(slice and dice)
◦ 切片操作在给定的数据立方体的一个维上进行选择，导致一个子方
◦ 切块操作通过对两个或多个维进行选择，定义子方
} 转轴(pivot)
◦ 立方体的重定位，可视化，或将一个3维立方体转化为一个2维平面序列
◦ 转轴是一种可视化操作，通过转动当前数据的视图来提供一个数据的替代表示
} 其他OLAP操作
◦ 钻过(drill_across)：执行涉及多个事实表的查询
◦ 钻透(drill_through)：使用关系SQL机制，钻到数据立方体的底层，到后端关系表
◦ 其他OLAP操作可能包括列出表中最高或最低的N项，以及计算移动平均值、增长率、利润、统计函数等等
6.Apriori过程，不足
Apriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。Apriori算法利用的是Apriori性质：频繁项集的所有非空子集也必须是频繁的。
Apriori算法由连接和剪枝两个步骤组成。
连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。
Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk 。为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。
不足：1.要对数据进行多次扫描；2.会产生大量的候选项集；3.对候选项集的支持度计算非常繁琐；
7.简述决策树归纳算法，分析优缺点
常见的算法有ID3，C4.5，CART算法，他们都是采用贪心（非回溯）的方法。
树以代表训练样本的单个节点（N）开始 如果样本都在同一个类，则该节点成为树叶，并用该类标记 否则，算法调用Attribute_selection_method，选择能够最好的将样本分类的属性；确定“分裂准则”，指出“分裂点”或“分裂子集”。 对测试属性每个已知的值，创建一个分支，并以此划分元组 算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现 递归划分步骤停止的条件：划分D（在N节点提供）的所有元组属于同一类，没有剩余属性可以用来进一步划分元组——使用多数表决，没有剩余的样本，给定分支没有元组，则以D中多数类创建一个树叶 优点(1) 速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。
(2) 准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。
缺点(1) 缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。(2) 要多次扫描数据集，导致低效。决策树技术也可能产生子树复制和碎片问题。
8.简述人工神经网络分类方法及其优缺点
人工神经网络分类方法主要包括，贝叶斯信念网络，向后传播分类，SVM，频繁模式分类，遗传算法。（人工神经网络分类方法很多都是监督学习，模型的学习在被告知每个训练样本属于哪个类的“指导”下进行，新数据使用训练数据集中得到的规则进行分类）贝叶斯信念网络通过计算元素的相关度，将元素进行划分。后向传播是一种神经网络学习算法；神经网络是一组连接的输入/输出单元，每个连接都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标号来学习。SVM使用一种非线性的映射，将原训练数据映射到较高的维，使用一个适当的对足够高维的非线性映射，两类的数据总可以被超平面分开。遗传算法对于一个规模为N的种群S,按每个染色体si∈S的选择计算适应度，进行复制操作。
} 优点：预测精度总的来说较高，健壮性好，训练样本中包含错误时也可正常工作
，输出可能是离散值、连续值或者是离散或量化属性的向量值，对目标进行分类较快
} 缺点：训练（学习）时间长，蕴涵在学习的权中的符号含义很难理解，很难和专业领域知识相整合
提高分类准确率的技术：装袋，提升，adaboost。
} Bagging技术和boosting技术都通过将T个学习得到的分类法C1,C2…CT组合起来，从而创造一个改进的分类法C*
} Boosting技术，每个训练样本赋予一个权值Ct的权值取决于其错误率
48、简述决策树归纳算法，分析优缺点
常见的算法有ID3，C4.5，CART算法，他们都是采用贪心（非回溯）的方法。
树以代表训练样本的单个节点（N）开始 如果样本都在同一个类，则该节点成为树叶，并用该类标记 否则，算法调用Attribute_selection_method，选择能够最好的将样本分类的属性；确定“分裂准则”，指出“分裂点”或“分裂子集”。 对测试属性每个已知的值，创建一个分支，并以此划分元组 算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现 递归划分步骤停止的条件：划分D（在N节点提供）的所有元组属于同一类，没有剩余属性可以用来进一步划分元组——使用多数表决，没有剩余的样本，给定分支没有元组，则以D中多数类创建一个树叶 优点(1) 速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。
(2) 准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。
缺点(1) 缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。(2) 要多次扫描数据集，导致低效。决策树技术也可能产生子树复制和碎片问题。
61、贝叶斯网络的特点：
（1）贝叶斯分类提供了一种用图形模型来捕获特定领域的先验知识的方法，网络还可以用来对变量间的因果依赖关系进行编码。（2）构造网格可能既费时又费力，但一旦网格结构确定下来，添加新变量就十分容易。（3）贝叶斯网络很适合处理不完整的数据。（4）因为数据和先验知识以概率方式结合起来了，所以该方法对模型的过分拟合问题是非常鲁棒的。
62、神经网络的特点
（1）对于噪声数据的承受能力高，对未经训练的数据的模式分类能力强。（2）神经网络可以处理冗余特征，对训练数据中的噪声非常敏感。（3）不像大部分的决策数算法，它非常适合连续值得输入和输出。(4)神经网络算法是固有并行的，可以使用并行技术来加快计算过程。(5)神经网络权值学习使用的梯度下降方法经常会收敛到局部极小值。训练神经网络是一个很耗时的过程，而测试样例分类时非常快。
51、分类的过程包括获取数据、预处理、分类器设计和分类决策。
2、分类器设计阶段包含三个过程：划分数据集、分类器构造和分类器测试。
3、分类问题中常用的评价准则有精确度、查全率和查准率和集合均值。
52、聚类分析包括连续型、二值离散型、多值离散型和混合类型4种类型描述属性的相似度计算方法。
63、K 最邻近分类特点：
（1）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。(2) 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。数量影响运行结果。(可以采用权值的方法来改进)。(3)该方法的另一个不足之处是计算量较大。(4)准确率受噪声影响。
####9,。简述主要的聚类方法，分析聚类算法以及各自特点。
划分方法：K-均值，K-中心点，CLARA
给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇，并且k<=n。每个组至少包含一个对象，每个对象属于且仅属于一个组。
k-平均算法由簇的平均值来代表整个簇。噪声，离群点产生较大影响，不适用于非凸形状的簇，需要指定k。
k中心点算法，由处于簇的中心区域的某个值代表整个簇。每次迭代复杂度比较大，需要指定k。
CLARA ，先抽样，然后用样本进行k中心点算法。
基于距离的聚类方法的缺点：只能发现球状的簇，难以发现任意形状的簇。
层次的方法：对给定数据对象集合进行层次分解
自底向上方法（凝聚AGNES）：开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组，直到所有的组合并为一个，或者达到一个终止条件。
输入:包含n个对象的数据库，终止条件簇的数目k
输出:k个簇，达到终止条件规定簇数目
(1)将每个对象当成一个初始簇；
(2)Repeat
(3) 根据两个簇中最近的数据点（单链接）找到最近的两个簇；
(4) 合并两个簇，生成新的簇的集合；
(5)Until 达到定义的簇的数目
AGNES算法比较简单，但经常会遇到合并点选择的困难。如果在某一步没有很好地选择出合并点，很可能导致低质量的聚类结果。而且此算法没有良好的可伸缩性，算法复杂度较高。
自顶向下方法（分裂DIANA）：开始将所有的对象置于一个簇中，在迭代的每一步，一个簇被分裂为多个更小的簇，直到最终每个对象在一个单独的簇中，或达到一个终止条件
输入：包含n个对象的数据库，终止条件簇的数目k
输出：k个簇，达到终止条件规定簇数目
（1）将所有对象整个当成一个初始簇
（2） For ( i=1;i!=k; i++)
（3） 在所有簇中挑选出具有最大直径的簇c；
（4） 找出簇c里与其他点平均相异度最大的一个点放入splinter group，剩余的放入old party中。
（5） Repeat
（6） 在old party里找出到splinter group中点的最近距离不大于old party中点的最近距离的点，并将该点加入splinter group
（7） Until 没有新的old party的点被分配给splinter group；
（8） Splinter group 和old party为被选中的簇分裂成的两个簇，与其他簇一起组成新的簇集合
（9） end for
（9） END
缺点：合并或分裂的步骤不能被撤销。类之间不能交换对象。如果在某步没有选择好分裂点，可能会导致低质量的聚类结果。大数据集不太适用。
BIRCH(聚类特征树): 首先使用层次聚类算法将对象分组成微簇，然后用另一个聚类方法对这些微簇进行宏聚类。
算法第一阶段：构造CF树（两个参数：分枝因子B和阈值T）第二阶段：用选定的聚类算法对叶结点进行聚类
分枝因子B：定义节点的分支最大个数 阈值T：定义叶结点中子簇的最大直径
CF 树的构造过程实际上是一个数据点的插入过程
(1) 从根节点root 开始递归往下，计算当前条目与要插入数据点之间的距离，寻找距离最小的那个路径，直到找到与该数据点最接近的叶节点中的条目。
(2) 比较计算出的距离是否小于阈值T，如果小于则当前条目吸收该数据点；反之，则继续第三步。
(3) 判断当前条目所在叶节点的条目个数是否小于L，如果是，则直接将数据点插入作 为该数据点的新条目，否则需要分裂该叶节点。分裂的原则是寻找该叶节点中距离最远的两 个条目并以这两个条目作为分裂后新的两个叶节点的起始条目，其他剩下的条目根据距离最 小原则分配到这两个新的叶节点中，删除原叶节点并更新整个CF 树。
基于密度的方法：DBSCAN，OPTICS，DENCLUE
DBSCAN，OPTICS， DENCLUE：基于连接和密度函数：只要临近区域的密度（对象或数据点的数目）超过某个临界值，就继续聚类。优点：可以过滤掉“噪声”和“离群点”，发现任意形状的簇。需要定义密度参数作为终结条件
基于网格的方法: 基于多层粒度结构，把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类都在这个网格结构上进行。
STING，CLIQUE，优点：处理数度快，缺点：簇边界都是竖直的，降低簇的质量和精确性。
基于模型的方法：为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。
42、K-均值 划分方法
给定k 值, k -均值算法 通过以下4个步骤实现:
随机选择k个对象，每个对象初始地代表一个簇的平均值或中心；
其余每个对象，根据其与各个簇中心的距离，将它赋给最近的簇；
重新计算每个簇的平均值 ；
重复此过程，直至准则函数收敛。
- K-均值聚类法的优缺点：
缺点: 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。
在K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。
从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。
对“噪声”数据敏感。
优点： 本算法确定的K个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为O(NKt)，其中N是数据对象的数目，t是迭代的次数。一般来说，K«N，t«N 。
57、K中心点算法的优缺点：
优点： 对噪声不敏感，具有较强的数据鲁棒性。
缺点: 聚类过程的高耗时性，计算速度慢，计算量大：通过迭代来寻找最佳的聚类中心点集时，需要反复地在非中心点对象与中心点对象之间进行最近邻搜索，从而产生大量非必需的重复计算，聚类过程缓慢，不能满足实际应用的需求。
43、DBSCAN算法
l 任选一对象 p；
l 检索所有从p关于ε和MinPts 密度可达的对象；
l 如果 p 是核心对象, 则创建一个新簇；
l 如果 p 是边界点, 无任何对象是从p关于ε和MinPts 密度可达的对象，DBSCAN 访问数据库中的下一对象；
l 继续此过程直到所有的点已处理。
数据挖掘在软件工程中应用：
#####1.软件漏洞检测用于找出软件开发过程中的错误或漏洞，以便及时进行修正，保证软件可靠性和质量。选择合适的数据挖掘模型进行训练和验证。根据项目需求选择合适的挖掘方法，为该方法生成训练集和测试集，通过比较结果选择最合适的方法；通过前面步骤中的方法对软件漏洞进行分类、定位和描述。找出未知的漏洞，根据一定规则对漏洞进行分类和描述。
#####2.开源软件挖掘中最常用的方法之一是克隆代码检测，通常情况下，OSS 之间共用代码的情况是非常普遍的，有实验表明50%以上的源文件被应用到两个以上的开源项目中。因此就可以使用克隆代码检测的方法对单个软件内以及两个软件之间的代码进行检测。克隆代码就是以代码复用为目的而进行拷贝和粘贴的代码段，对克隆代码进行检测可以有效防止漏洞的拷贝性传播，另外还有利于软件在演化过程中的维护。
#####3.版本控制系统（如CVS，SVN，Visual SourceSafe ，Git等）用以确保项目参与者所编辑的同一档案得到统一的，全局的更新。目前几乎所有的软件开发都会采用版本控制系统来管理软件开发活动。当前对版本控制信息的挖掘应用基本都是对软件变更历史进行挖掘的，用以发现不同程序模块及其子系统之间的相互依赖关系，从而预测程序漏洞的引入方式或者未来的变化。通过以上挖掘活动，可以有效地降低系统后期维护代价，预防一些因变更而引入的漏洞，从而为软件系统的后期维护提供警示作用，为项目的管理及相关决策提供重要的参考依据。