《Web数据挖掘》读书笔记2


《Web数据挖掘》

第四章 无监督学习

4.1 基本概念      聚类是一个将数据集中在某些方面相似的数据成员进行分类组织的过程。      两种类型:

  • 划分聚类Partitional Clustering
  • 层次聚类Hierarchical Clustering

4.2 k-均值聚类      这是最著名的划分聚类算法。      思想:把给定的数据划分成k个聚类,每个聚类有一个聚类中心,它是这个聚类所有数据点的均值。      算法:

  1. 随机选k个数据点作为初始的聚类中心。

  2. 把每个数据点分配给距离离它最近的聚类中心。
  3. 分配完成后,每个聚类的聚类中心会根据现有的数据点再重新计算(计算均值)。

     这个过程将被不断重复直到满足某个终止条件。      k-均值算法的优点和缺点:      主要优点在于简洁和效率。时间复杂度为O(tkn),n是数据数,k是聚类个数,t是循环次数,因为k,t都远小于n,所以认为相对于数据来说是线性的。      缺点:

  • 只能应用在那些均值能够被定义的数据集上。
  • 需要先指定聚类数目k。
  • 算法对于异常值十分敏感。
  • 算法对于初始的随机选择十分敏感。
  • 不适用于发现那些形状不是超维椭圆体(或球体)的聚类

4.3 聚类的表示      三种主要表示方法:

  • 用聚类中心表示
  • 用分类模型表示
  • 用聚类中最常见的值表示

4.4 层次聚类      它是一系列嵌套的聚类树,单个数据点在树的子节点,根节点包含全部数据点。      两种主要的层次聚类方法: 合并(自下而上)聚类 分裂(自上而下)聚类      不同方法确定两个聚类之间的距离: 单链接方法:每一步合并那些最接近的数据点 全链接方法:找出具有最短最远数据点的两个聚类 平均链接方法:两个聚类之间的距离是两个聚类之中多个数据点对之间距离之和的平均值。时间复杂度是O(n2 log n)

4.5 距离函数      最常用的是欧几里得距离和曼哈顿距离,这两种都是闵可夫斯基距离的特例。      布尔属性和符号属性。

4.6 数据标准化      为了避免结果由某个具有很大变化范围的属性主导的情况。      处理方法: 区间度量属性:1.范围标准化:转换到[0,1] 2.z-scoer标准化:基于属性的平均值和标准差来进行标准化。 比例度量属性:对于属性不是线性变化的,例如是指数变化的,先进行对数转换,然后当作区间度量属性来处理。 符号属性:

4.7 混合属性的处理      方法:

  1. 选择一个属性作为主导类型,然后把其他类型的属性都转换成改类型。
  2. 首先根据不同类型的属性计算两个数据点之间的距离,然后把这些距离综合起来得到最终的距离。

4.8 采用哪种聚类算法      略。

4.9 聚类的评估 用户验证:邀请一个团队来对结果进行评估和验收。 真实数据 熵Entropy 纯度Purity

第五章 部分监督学习 5.1 从已标注数据和无标注数据中学习      从少量的已标注(Labeled)数据和大量无标注数据(Unlabeled)中学习,即LU学习。

  • 使用朴素贝叶斯分类器的EM算法:E: Expectation  M: Maximization.思想:使用现有的参数估计对数据的不完整部分进行填充。接着在最大化似然度的M-step中,各个参数被重新估计,以此类推,直到数据不再变化。
  • Co-training
  • 自学习
  • 直推式支持向量机
  • 基于图的方法

5.2 从正例和无标注数据中学习      PU学习:给定一个正例文档集合P和一个无标注文档集U,通过使用P和U建立一个分类器能够辨别U中的正例。      PU学习的应用:

  • 从多个无标注集中学习
  • 从不可靠的反例数据中学习
  • 发现测试集中的突发文档
  • 发现异常值

     如何建立分类器:

  1. 从无标注数据集U中发现一些可靠的反例文档集合(用RN表示)
  2. 利用P RN 和 U-RN来建立分类器。

     建立分类器采用了一些比较抽象的技术,在此就不一一总结了。


至此,数据挖掘基础的理论知识就介绍得差不多了。我也发现了自己数学功底不够扎实,数据挖掘和处理尤其用到了很多概率和数值统计方面的知识。接下来,我将继续学习本书的第二部分:Web挖掘。