数据挖掘与生物医学应用作业 杨帆

1、数据挖掘与生物医学应用作业 姓名：杨帆 学号： B110903141. 请用分箱方法对向量3, 6, 7, 15, 11, 40, 33, 20, 30进行清除噪声处理。要求是分别使用等深度和等宽度分割，然后再分别使用均值、中值和边界平滑。答：等深度分割： 分类一：3 6 7 分类二：11 15 20 分类三：30 33 40 均值平滑: 5 5 5 15 15 15 34 34 34 中值平滑: 6 6 6 15 15 15 33 33 33 边界平滑: 3 7 7 11 11 20 30 30 40 等宽度分割： 分类一：3 6 7 11 3 ,14 分类二： 15 20 15 ,26 分

2、类三：30 33 40 27 ,40 均值平滑： 7 7 7 7 18 18 34 34 34 中值平滑： 7 7 7 7 18 18 33 33 33 边界平滑： 3 3 3 14 15 15 27 27 40 2. 用直方图表示价格向量1, 1, 5, 5, 5, 6, 6, 8, 8, 10, 10, 10, 12, 13, 13, 14, 15, 16, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 20, 20, 22, 22, 23, 23, 25, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 3

3、0, 30, 30。答： 3. 请用表一所示数据作为训练数据，给出构建分类预测模型的步骤。用表二所示数据作为测试数据，给出预测每个人是否为终身教授(Tenured)的步骤。表一表二答：分为两步：一，构建基于训练数据的模型； 在测试样本数据时，我们以样本的Years和Rank两个属相值为评判标准，来获得训练模型。在上述的实验中，我们对表一进行训练，得出模型的训练标准为Rank属性为Professor或者Years属性值大于6时，我们判断该目标的Tenured为Yes，否则，为No 二，使用构建模型预测目标的类型或特征值。 将表二中的数据带入训练模型，通过判断其Rank和Years属性是否符合判断

4、标准，断定其Tenured属性。 则结果：Tom Rank属性不是Professor且Years属性为2，故其Tenured属性为No； Merlisa Rank属性不是Professor但Years属性为7，故其Tenured属性为Yes； George Rank属性是Professor故其Tenured属性为Yes； Joseph Rank属性不是Professor但Years属性为7，故其Tenured属性为Yes；4. 请用年龄、是否为学生以及信用等级为属性构建一棵决策树，用于判断能否批准客户的信用卡申请。答：决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构

5、成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在本题中，我们对一个目标的年龄、是否为学生以及信用等级来作为判断标准进行评判。在这三个属性中，很明显年龄属性可以包含其余两个属性，因此我们将其作为决策树的根节点。对于大部分人小于30岁的一般为学生或者刚毕业，要对其进行是否学生的评判。30到40岁的人一般都有工作，默认其有能力申请信用卡。而大于40岁的人一般都已经建立了自己的信用等级，可以根据这个判断能否申请信用卡。具体的决策树如下：年龄 ? >40 <3030

6、-40信用等级 ?学生?是 否是优良一般否否否 否 5. 请查阅相关文献后给出决策树发展历史上有哪些重要的决策树算法？并简要描述其基本原理，并给出相关文献的出处。答：（一）：第一个关于决策树的算法 E. B. Hunt, J. Marin, and P. T. Stones book “Experiments in Induction” published by Academic Press in 1966原理：从一个空的决策树出发，通过添加新的判定节点来完善 原有的决策树，直到新的决策树能够正确地将训练实例分类为止。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下

7、的递归方式，在决策树的内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。（二）：第一个引起广泛关注的决策树算法 - ID3原理：ID3采用贪心方法，其中决策树以自顶向下递归的分治方式构造。大多数决策树归纳算法都沿用这种自顶向下的方法，从训练元组集和它们的相关联的类标号开始构造决策树。随着树的构建，训练集递归地划分成较小的子集。ID3算法中关键的一步是属性选择度量，即选择分裂准则。其中的三种度量方法分别是信息增益、增益率和Gini指标。（示例算法选择了第一种方法）。当获取信息时，

8、将不确定的内容转为确定的内容，因此信息伴着不确定性。出处：J. R. Quinlans paper in a book “Expert Systems in the Micro Electronic Age” edited by D. Michie, published by Edinburgh University Press in 1979（三）：最流行的决策树算法 - C4.5原理：C4.5决策树能够根据决策树生成一系列规则集,我们可以把一颗决策树看成一系列规则的组合。一个规则对应着从根节点到叶子节点的路径，该规则的条件是路径上的条件，结果是叶子节点的类别。C4.5首先根据决策树的每个叶

9、子节点生成一个规则集，对于规则集中的每条规则，算法利用“爬山”搜索来尝试是否有条件可以移除，由于移除一个条件和剪枝一个内部节点本质上是一样的，因此前面提到的悲观剪枝算法也被用在这里进行规则简化。MDL准则在这里也可以用来衡量对规则进行编码的信息量和对潜在的规则进行排序。简化后的规则数目要远远小于决策树的叶子节点数。根据简化后的规则集是无法重构原来的决策树的。规则集相比决策树而言更具有可操作性，因此在很多情况下我们需要从决策树中推理出规则集。C4.5有个缺点就是如果数据集增大了一点，那么学习时间会有一个迅速地增长。出处：J. R. Quinlans book “C4.5: Programs fo

10、r Machine Learning” published by Morgan Kaufmann in 1993（四）：最流行的用于回归的决策树算法 CART原理：CART算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。出处：L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stones book “Classification and Regression Trees” published by Wadsworth in 1984（五

11、）：目前最强的基于决策树的算法 随机森林 原理：简单的说，随机森林就是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林里的每一颗决策树之间是没有关联的，在得到森里之后，当有一个新的输入进入样本的时候，就让森里中的每一颗决策树进行一下判断，看看这个样本应该属于那一类（对于分类算法），然后看看那一类被选择最多，就预测这个样本为那一类。而随机森林的算法主要包括决策树的生长和投票过程。出处：L. Breimans MLJ01 paper “Random Forests” 6. 在构建决策树时，如何选择属性作为当前节点的测试属性对最终结果有着重要的影响。现在表三和表四中给出两组不同学生的相

12、关信息，要求用信息增益度量的方法计算出选择哪种属性才是最佳的当前测试属性。表三表四答： 对于信息增益度量的方法即选择具有最高信息增益(或最大熵压缩)的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小,并反映划分的最小随机性或 “不纯性”。 对一个给定的样本分类所需的期望信息由下式给出 I(S1,S2，···，Sm) =-i=1mSiSlog2SiS其中：S 是 数据样本的总集合 si 是 类别Ci的训练样本 (i=1,2, , m)aj是属性A的值 (j=1,2, , v)设属性 A 具有 v 个不同值a1 ,., av。可以用属性 A

13、 将 S 划分为 v 个S1 ,.,Sv;其中, Sj包含 S 中这样一些样本,它们在 A 上具有值 aj 设 sij是子集 Sj中类 Ci的样本数，则根据 A划分子集的熵或期望信息式给出: Ent(A)=i=1ySiAS-j=1mSijASiAlog2SijASiA基于属性A的信息增益为 ：Gain(A)= I(S1,S2，···，Sm)- Ent(A)信息增益值越大，属性A用于分类的效果就越好 所以要正确分类的训练集的信息是I(S1,S2)=I(120,130)=-120250log2120250-130250log2130250=0.9988假设major主

14、要是选择分割训练集 当 major=”science” ：S11=84 , S12=42 I(S11,S12)= -84126log284126-42126log242126 =0.9183 当 major=”engineering” ：S21=36, S22=46I(S21,S22)= -3682log23682-4682log24682 =0.9892当 major=“business” : S31=0, S32=42I(S31,S32)=0所以major的熵：E(major)=126250I(S11,S12)+82250I(S21,S22)+42250I(S31,S32)=0.7873主

15、要的信息增益：Gain(major)=I(S1,S2)-E(major)=0.2115我们还可以得到属性的信息增益:Gain(gender)=0.0003 Gain(birth_country)=0.0407 Gain(gpa)=0.4490 Gain(age_range)=0.5971通过比较：Gain(age_range)> Gain(gpa)> Gain(major)> Gain(birth_country)> Gain(gender)所以选择age_range作为当前的最佳测试属性。7. 请使用朴素贝叶斯分类方法对同学X做出其是否能够买电脑的判断，其中同学X的年

16、龄小于30，收入为medium，行用等级为fair，训练数据如表五所示。表五答：贝叶斯分类是一种统计学分类方法，基于贝叶斯法则可以预测类成员关系的可能性，如给定样本属于一个特定类的概率。其中贝叶斯法则公式如下：P(H|X)=PHXP(H)P(X) （1）其中： P(H | X ) 是后验概率,或条件 X 下, H 的后验概率。 例如,假定数据样本世界由水果组成,用它们的颜色和形状描述。假定 X 表示红色和圆的,H 表示假定 X 是苹果,则 P(H | X ) 反映当我们看到 X 是红色并是圆的时,我们对 X 是苹果的确信程度. P(H)是先验概率,或 H 的先验概率。 对于上面的例子,它是任意

17、给定的数据样本为苹果的概率,而不管数据样本看上去如何。 P(X | H) 是条件 H 下,X 的后验概率。 已知 X 是苹果,X 是红色并且是圆的的概率。 P(X)是 X 的先验概率。 由我们的水果集取出一个数据样本是红的和圆的的概率。 由公式（1）可知P(Ci|X)=PCiXP(H)P(X) (2)当Ci之间相互独立，i（0 ， n）则P(X|Ci)=k=1nP(Xk|Ci) (3) 如果是连续值属性,则通常假定该属性服从高斯分布。因而 P(Xk|Ci)=g(Xk, Ci, Ci)=12Cie-(x-Ci)22Ci2 (4)所以结果如下：给出一个实例进行分类： X=(age=<30，i

18、ncome=medium,student=yes,credit_rating=fair)P(Ci): P(C1)=(buys_computer=yes)=9/14=0.643 P(C2)=(buys_computer=no)=5/14=0.357P(X|Ci): since P(age=<30|buys_computer=yes)=0.222 P(age=<30|buys_computer=no)=0.6 P(incomen=medium|buys_computer=yes)=0.444 P(income=medium|buys_computer=no)=0.4 P(student

19、=yes|buys_computer=yes)=0.667 P(student=yes|buys_computer=no)=0.2 P(credit_rating=fair|buys_computer=yes)=0.667 P(credit_rating=fair|buys_computer=no)=0.4 Then P(X|C1)=0.044 P(X|C2)=0.016P(X|Ci)P(Ci)=0.007所以，对于同学X buys_computer=yes8. 请简要描述K均值聚类方法的原理。答：对于K均值的划分方法当结果簇是密集的,而簇与簇之间区别明显时,它的效果较好。 对处理大数据集,该

20、算法是相对可伸缩的和高效率的。 要求用户必须事先给出 k(待生成簇的数目)不适合发现大小差别很大的簇。 对于“噪音”和孤立点数据是敏感的,少量的该类数据能够对平均值产生极大的影响。 因此可分为五步来进行：(1) 任意选择k个对象作为初始的簇中心(2) 根据与每个中心的距离，将每个对象赋给最近的簇(3) 重新计算每个簇的均值并将其作为新蔟中心点; （4）根据与每个新中心的距离,重新将每个对象赋给“最近”的簇;（5）不断循环（3）-（4）直至每个簇的中心点不再变化。9. 在模型数目已知和未知两种情况下，给出如何使用高斯混合模型方法(GMM)计算模型高斯参数的步骤。答： 已知高斯密度函数如下：P(x

21、)=1(2)k2|12e-12x-1（x-） （1） 对上式等号两边取自然对数结果如下：lnP(x|,)=-12（ln2+ln|+（x-）-1（x-） （2） （1）当模型已知时： 通过 最大化密度函数以求得高斯模型的参数 N（，） 使用最大似然函数法结果如下：xUlnP(x|,) xlnPx,/=0xlnPx,/=0=1NP,=1NP,(-)(-) N=XP(X|,) （2）当模型数目未知时使用期望最大算法： (1) 根据贝叶斯法则计算后验概率： Cx=arg maxi=1,2,3P(x|ui,i)wi (2)首先假定模型和参数：（1，1，w1=1k）,···，（k，k，wk=1k） (3)每一个对象归类为其后验概率值最大的类: Cx=arg maxi=1,···，kP(x|ui,i)wi(4