机器学习那些事

机器学习那些事

作者：佩德罗·多明戈斯（Pedro Domingos）
译者：刘知远

 

感谢作者跟译者！

数据挖掘 ： 实用机器学习技术

系统A有100个文件，其中40个为相关文件

系统B有400个文件，其中80个为相关文件

哪个系统更好呢？

• 错误的肯定：被返回但却不相关的文件数


• 错误的否定：相关的但却没有被返回的文件数

所对应的成本决定

• 精度 = 检索到的相关文件数量 / 检索到的文件总数量


• 召回率 = 检索到的相关文件数量 / 相关文件总数量

大数据 ： 笔记 chap 7 聚类

欧氏空间下，簇的半径(radius)是指簇内所有点到质心的最大距离

非欧空间下，选取簇中的一个点来代表整个簇，一般是最小化中心点到簇内其他点的距离

BFR算法

k-means的一个变形，主要是在高维欧氏空间中对数据进行聚类。对簇的形状给出了一个非常强的假设，即它们必须满足以质心为期望的正态分布。

用<点数N，所有点在每一维的分量和，所以有点在每一维的分量平方和>表示点集，方便扩展

大数据 ： chap 5 链接分析

词项作弊：往页面上添加不相干的关键词

终止点：没有出链的网页

处理终止点方法（1）：

1. 迭代删除所有终止点


2. 求强连通子图G的节点PR


3. 某个节点X，所有X的入链节点都是G中的节点，则PR(X) = sum(PR(i)/OUT(i))
   
   
   
   • 其中，i是G中的节点，且指向节点X，OUT(i)为节点i的出链数
   
   
   
   


4. 迭代求原图所有节点的PR

采集器陷阱：一系列节点集合，这些节点虽然没有终止点，但是却没有出链指向集合之外

处理采集器陷阱的方法（1）：

每次迁移，允许以一个小概率随机跳转到一个随机网页，而不一定要沿着出链迁移。

面向主题的pagerank：随机游走时，只到达一个指定主题下的随机网页，而非到达任意类别的网页

根据词汇推断网页主题

根据用户搜索的词猜测搜索的主题

在评论的地方贴小广告，指向垃圾网页

反作弊：

识别出垃圾农场的结构

TrustRank 修改pagerank计算公式，降低垃圾网页得分：只随机跳转到可靠网页的集合（要注意考虑博客下加评论，贴小广告的做法）

垃圾质量(spam mass) 识别网页的垃圾程度，不去索引垃圾网页or不去算垃圾网页的pagerank（根据trustrank值，(pr-tr)/pr )

权威页：给出高质量的内容

导航页：指向权威页

pagerank的迭代是一维的：重要的网页链向重要的网页

HITS的迭代是二维的：指向好的权威页的网页是好的导航页，好的导航页指向的网页是好的权威页

出链网页的权威度之和 ＝》当前页的导航度

入链网页的导航度之和 ＝》当前页的权威度

导航度与权威度的计算，需要归一化

模式识别 by 汪增福 ： 聚类分析笔记

一个好的相似性测度应该具有某些不变特性。

例如，它应该对样本观测空间中的平移、旋转和尺度变化是不敏感的。

例如欧氏距离对平移和旋转变化是不变的，但不是尺度变换和一般线性变换下的不变量。因此，当把欧氏距离作为相似性度量时，特征量单位/量纲的选择非常重要。

聚类算法的性能好坏一般与以下因素相关：

• 聚类中心的选择与更新


• 聚类策略和聚类准则（函数）的选择


• 控制阈值和类别数的设置

数据挖掘导论 8.5.7 : 簇有效性的监督度量

聚类分析，评估人工分类的过程可以在多大程度上被聚类分析自动地实现

簇有效性的监督度量有两种：面向分类的、面向相似性的

面向分类的度量：度量预测的类标号与实际类标号的对应程度

• 熵：每个簇由单个类的对象组成的程度


• 纯度：簇包含单个类的对象程度


• 精度：簇中一个特定类对象所占比例  Pij = Mij/Mi


• 召回率：簇包含一个特定类的所有对象的程度 Rij=Mij/Mj


• F度量：精度与召回率的组合，Fij = 2 * Pij * Rij / (Pij + Rij)

 

面向相似性的度量：同一个簇的任意两个对象也应该在同一个类，反之亦然

理想的簇相似度矩阵：第ij项为1，如果对象i和对象j在同一个簇；否则为0

理想的类相似度矩阵：第ij项为1，如果对象i和对象j在同一个类；否则为0

比较簇和类矩阵的相关性，上述两个矩阵的相关度

• f00 = 不同类+不同簇 的对象对 个数


• f01 = 不同类+相同簇 的对象对 个数


• f10 = 相同类+不同簇 的对象对 个数


• f11 =  相同类+相同簇 的对象对 个数

Rand统计量 = (f00+f11) / (f00+f01+f10+f11)

Jaccard系数 = f11 / (f00+f01+f10+f11)

 

层次聚类的一种度量：对于每个类，是否至少有一个簇相对较纯，且包含了该类的大部分对象

F = SUMj ( Mj * MAXi F(i, j) / M )

其中，最大值在所有层的所有簇i上取，Mj是类j中对象的个数

数据挖掘导论 6.7.1 : 兴趣度的客观度量

X->Y,X为前件，Y为后件

局限性

支持度S(X,Y)：潜在有意义的模式，被阈值滤掉

置信度S(X,Y)/S(X)：忽略了规则后件中项集的支持度，可能有误导

兴趣因子S(A,B)/[S(A) X S(B)] : （A，B）频繁程度的信息一定程度上被消减了

相关分析，连续变量：皮尔森相关系数

相关分析，二元变量：(f11f00- f01f10) / sqrt(f1x fx1 f0x fx0)

相关分析局限：把同时出现与同时不出现视为同等重要，更适合分析对称二元变量；样本大小成比例变化时，无法保持不变

IS度量 S(A,B)/ sqrt [ S(A) X S(B) ] ：等价于二元变量的余弦度量。即使是不相关or负相关的模式，IS度量也可能很大

==

度量是对称的，如果M(A->B) = M(B->A)。

对称度量常用于评价项集，非对称度量更适合分析关联规则。