@spiritnotes 2016-02-17T10:34:58.000000Z 字数 11308 阅读 2453

《集体智慧编程》

机器学习 读书笔记

第1章集体智慧导言

什么是集体智慧

通常含义是指：为了创造新的想法，而将一群人的行为、偏好或思想组合在一起

什么是机器学习

是人工智能领域中的一个子领域，允许机器进行不断地学习

机器学习的局限

机器学习算法受限于其在大量模式之上的归纳能力，而一个模式不同于算法先前曾见到过的任何其他模式，那么它有可能被误解

学习型算法的其他用途

生物工艺学
金融欺诈侦测
机器视觉
产品市场化
供应链优化
股票市场分析
国家安全

第2章提供推荐

基于用户的协作型过滤 user-based

对一大群人进行搜索，找出其中与我们的品味相近的一小群人

搜集偏好

寻找相近的用户

人与人之间进行对比，评价其相似度

欧几里得距离评价

针对共同偏好

$sim(x,y) = {1\over{1+ \sqrt{\sum_{i=1}^n (x_i-y_i)^2}}}$

皮尔逊相关度评价

可以修正“夸大分值”的情况，也即是分值分布近似，绝对值不一样，其实可以将分数进行归一化处理
针对共同偏好

$sim(x,y) = {{\sum_i(x_i*y_i) - {(\sum_ix_i)*(\sum_iy_i)\over n}}\over{\sqrt{(\sum_ix_i^2 - {(\sum_ix_i)^2\over n})*(\sum_iy_i^2 - {(\sum_iy_i)^2\over n})}}}$
函数返回-1~1之间的数值

Tanimoto系数

代表交集与并集个数的比值

匹配商品

将物与人对调可以用于计算物与物之间的相似度

构建一个基于del.icio.us的推荐链接系统

基于物品的协作型过滤 item-based

物品间的比较不会基于用户间的比较那么频繁变化

计算物品与物品之间的相似度

利用用户以及评分进行计算
当用户变化时，需要更新，但是对于大量交易的系统来说，相似度越来越趋于稳定

获得推荐

针对新商品的评分与基于用户的一样

$score(x, p) = {{\sum_{i}(score(x,i)*sim(p,i))} \over {\sum_{i}sim(p,i)}}$

使用MovieLens数据集

基于用户进行推荐还是基于物品进行推荐

对于稀疏数据集，基于物品的过滤方法通常要优于基于用户的过滤方法
对于密集型数据集而言，两者效果差不多
基于用户的过滤方法更加易于实现，无需额外步骤，适用于规模较少且变换非常频繁的内存数据集
基于用户的可以告诉用户哪些人与自己由相近偏好

todo 练习

第3章发现群组

监督学习与无监督学习

利用样本输入和期望输出来学习如何预测的技术被称为监督学习方法（supervised learning methods）。无监督学习（unsupervised learning）的目的是要在一组数据中找寻某种结构，而这些数据本身并不是我们要找的答案。

todo 非负矩阵因式分解（non-negative matrix factorization）自组织映射（self-organizing maps）

单词向量

对blog拆分为单词、转变为小写，并且选择其在blog中出现比例位于某一范围中的单词

分级聚类

通过连续不断地将最为相似的群组两两合并，来构造出一个群组的层级结构。待分级聚类完成后，其结构相当于树状图。
紧密度可以采用皮尔逊相关度来计算。
每次聚类后形成的新的聚类是通过对产生该聚类的两个cluster求平均得到。
分级聚类计算量大

列聚类

使用：对消费者群体进行分组，也即是对消费者的属性进行分组
行用以代表特征，列可以用于代表消费者购买的商品
当数据项的数量比变量多的时候，出现无意义聚类的可能性就会增加

K-均值聚类

随机选择K个中心位置
将各个数据项分配给最近的中间点
根据类别，通过平均值计算新的聚类中心点，然后重新分配数据项
一直重复，直到分配过程不再发生变化

如果某类中的数目为0，如何处理？

todo

针对偏好的聚类

Zebo

使用Beautiful Soup获取数据

以二维形式展示数据

多维缩放（multidimensional scaling）：将数据点随机放到二维图上，按照点和点之间的距离进行推远拉近，直到总体误差（实际距离与二维空间距离的差与实际距离的比值）最小。移动公式：

# 每次迭代进行的操作
for k in range(n):
    for j in range(n):
        errorterm = (fakedist[j][k]-realdist[j][k])/realdist[j][k]
        grad[k][0] += ((loc[k][0]-loc[j][0])/fakedist[j][k])*errorterm
        grad[k][1] += ((loc[k][1]-loc[j][1])/fakedist[j][k])*errorterm
        totalerror += abs(errorterm)
if lasttotalerror < totalerror:
    break
for k in rang(n):
    loc[k][0] -= rate*grad[k][0]
    loc[k][1] -= rate*grad[k][1]

todo 练习题

第4章搜索与排名

一个简单的爬虫程序

使用urllib2.urlopen(url)

建立索引

采用SQLite建立索引数据库
使用soup将正文提取出来分割成单词
将word、url关系写入数据库

查询

基于表的链接将数据查询出来并返回

select w0.urlid,w0.location,w1.location
from wordlocation w0, wordlocation w1
where w0.urlid = w1.urlid
and w0.wordid = 10
and w1.wordid = 17

基于内容的排名

评价量度：

单词频度，位于查询条件中的单词在文档中出现的次数能有助于我们判断文档的相关程度

for urlid,_,_ in rows:
    counter[urlid] += 1

文档位置，文档的主题有可能出现在靠近文档的开始处

urlid:min(sum(locations)) for urlid,locations in row

单词距离，如果查询中有多个单词，则它们在文档中出现的位置应该靠得很近

if len(row) <= 2: return 1.0 #仅查询单个词
dist = sum([abs(row[i]-row[i-1]) for i in range(2,len(row))])

权重合并，三者乘以不同权重例如(1.0, 2.0, 1.5)

归一化,结果位于0~1，越大越好：
如果原值是越小越好， float(minvalue)/value
如果原值是越大越好， value/float(maxvalue)

利用外部回指链接

简单计数
简单统计外部链接到本网页的链接数
PageRank，让热门的网页有更多权重

理论上，PageRank计算的是某个人在任意次链接点击之后到达某一网页的可能性。PageRank使用了一个值为0.85的阻尼系数，用以指示用户持续点击每个网页中链接的概率为85%。
1. 为所有的PageRank都设置为一个任意的初始值，一般为1.0
2. 迭代计算，pr = 0.15 + sum(pr_pagetome/pagetome_outnum)，计算完更新
3. 直到迭代次数

PageRank对于返回高层次和更大众化的网页来说，比较有效

利用链接文本

针对搜索中的words中某个word
    查找含有该word的link
        如果该link的toid指向结果中某个搜索结果url
        则该url的权重增加fromid的pr score

从点击行为中学习

多层感知机（multilayer perception，MLP）网络，由多层神经元构成，其中第一层神经元接受输入，最后一层神经元给予输出。中间层称为隐藏层，其职责是对输入进行组合。

设置默认的强度，从word到隐藏层为-0.2，隐藏层到url默认为0
每传入一组以前未见过的单词组合，该函数会在隐藏层中建立一个新的节点，其key为单词连接，word到hiddenid的强度为1/len(words)，haddenid到url的强度为0.1。

前馈法

反双曲正切变换函数（hyperbolic tangent）， tanh，S型函数
建立神经网路：
1. 针对输入和输出找出与其相关的haddenid
2. 建立初始的权重矩阵，worid->haddenid->urlid
3. 默认所有的word的权重为1.0，计算hiddenid的活跃度 $tanh(\sum a_{w_i}*strength_{w_i->h_j})$
4. 计算输出层的活跃程度 $tanh(\sum a_{h_i}*strength_{h_i->o_j})$

利用反向传播法进行训练

如果用户点击了预期的结果，则其应该朝1的方向推进；反之朝0的方向。训练时必须知道tanh在当前输出级别上的斜率，在函数的中段，输出为0.0时，斜率会非常陡，因此只需改变一点点输入就会获得很大的变化，反之接近-1和1，则变化越来越小。
斜率由如下公式确定 $dtanh(y) = 1.0-y*y$

反向传播法，针对输出层的每个节点：

计算节点当前输出与期望结果之间的差距
利用dtanh函数确定节点的总输入需要如何改变
改变每个外部回指链接的强度值，其值与链接的当前强度及学习速率成一定比例

针对每个隐藏层的节点：
1. 将每个输出链接的强度值乘以其目标节点所需的改变量，再累加求和，从而改变节点的输出结果
2. 使用dtanh函数确定节点的总输入所需的改变量
3. 改变每个输入链接的强度值，其值与链接的当前强度及学习速率成一定比例

#计算输出层误差
for k in range(len(urlids)):
    error = targets[k]-ao[k]
    output_deltas[k] = dtanh(ao[k])*error
#计算隐藏层误差
for j in range(len(hiddenids)):
    error = 0.0
    for k  in range(len(urlids)):
        error += output_deltas[k]*wo[j][k]
    hidden_deltas[j] = dtanh(ah[j])*error
#更新输出权重
for j in range(len(hiddenids)):
    for k  in range(len(urlids)):
        change = output_deltas[k]*ah[j]
        wo[j][k] += N*change
#更新输入权重
for i in range(len(wordids)):
    for j in range(len(hiddenids)):
        change = hidden_deltas[j]*ai[i]
        wi[i][j] += N*change

具体步骤：
1. 根据words、urls建立中间层，建立神经网络，并使用前馈法
2. 构建targets列表（选择的权重为1，其他0），并进行反向传播，保存结果

第5章优化

组团旅游

所有家庭成员需要在同一天到达纽约，然后在另外的同一天离开，需要考虑总价以及家庭成员在机场等待的时间

成本函数

价格
旅行时间，在飞机上所花的时间
等待时间
出发时间
汽车租用时间，根据早于租车时刻之前将车辆归还判断是否需要多付一天租金

随机搜索

随机产生一些解组合找出随机解中最优的

爬山法

以随机解开始，然后在其临近的解中寻找更好的题解
针对一个随机解，然后针对每个人寻找一个早一点或者晚一点的航班，然后找出其中最优的，然后进行下一步选择
爬山法有可能找到局部范围的最优解

随机爬山法

让爬山法以多个随机生成的初始解为起点运行若干次，借此希望其中有一个解能够逼近全局的最优解

模拟退火算法

从随机解开始，每一次迭代期间，算法会随机选中题解中的某个数字，然后朝某个方向变化，如果新解更优，则新解成为当前题解，否新题解仍然有可能成为当前题解
新解被接受的概率如下：
$p = {e^{(-(highcost-lowcost)/temperature)}}$

while T > 0.1:
    #随机选中某特征，随机选择一方向
    #创建一新解，判断是否有效，无效则将解变为有效
    if cost_new < cost_now or random() < pow(e, -(cost_new-cost_now)/T):
        ans_now = ans_new
    T = T*cool

遗传算法

先随机生产一组解，我们称之为组群（population），优化的每一步会计算整个种群的成本函数，从而得到一个有关题解的有序列表。
精英选拔法：将当前最优部分题解加入下一种群（比例控制），然后余下部分由修改最优解后形成。

修改方法：

变异（mutation）：对既有解进行微小、简单、随机的改变
交叉（crossover）或配对（breeding）：选取最优的两个解，将它们按照某种方法进行结合，最简单的是从一题解中随机选择一个数，余下来至另外一个题解

结束，到达指定的迭代次数或者连续经过数代后题解都没有得到改善

参数：

size，种群大小
mutprob，由变异得来的概率
elite，被认为是优秀且允许传入下一代的部分
maxiter，最多迭代次数

优化办法是否有用取决于问题本身，最优解应该接近于其他的优解。

真实的航班搜索

kayak API

涉及偏好的优化

学生宿舍优化问题
成本函数：如果是首选总成本+0，次选+1，不在选择中+3

网络可视化
质点弹簧算法：质点之间施以推力并试图分离，而节点间的链接则试图将关联节点彼此拉近。
成本函数：用以判断每两条线是否相交，相交则+1

第6章文档过滤

过滤垃圾信息

文档和单词
对所有文档划分成单词，改为小写
对分类器进行训练
fc用以记录特征在分类中出现次数
cc记录各分类被使用次数
train函数用文档和分类进行训练，获取feature并增加上面的计数，不考虑一个文档中词语出现多次的情况
计算概率
计算单词在该分类中出现的概率
fc(f, cat)/cc(cat)
对概率进行加权处理，推荐的初始值为0.5

#概率加权
def weightedprob(f, cat, prf, weight=1, ap=0.5):
    basicprob = prf(f,cat)
    totals = sum(fc(f,c) for c in cs)
    bp = ((weight*ap)+(totals*basicprob))/(weight+totals)
    return bp

朴素贝叶斯

假设各个要组合的概率是彼此独立的，即一个单词在属于某个指定分类的文档中出现的概率与其他单词出现在该分类的概率是不相关的。

文档的概率p(doc|class)： p *= weightedprob(f,cat) for f in doc
p(class|doc) = p(doc|class)*p(class) / p(doc)，p(doc)可以不需要计算

选择分类：可以定义阈值k，其本类的概率必须大于其他类的概率k倍才能认为是本类，否则可以认为是“未知”。这是因为不同的分类分错的代价不一致。

费舍尔方法

针对特征的分类概率：p(class|feature)=(具有指定特征的属于分类的文档数)/(具有指定特征的文档总数)，如果某中性词在文档分类中出现不均衡，则该方法可能导致较少文档中的分类中出现的词过多地被化为本分类

cprob(f,c) = p(feature|class)/sum(p(feature|class_i))

将各概率值结合起来
p *= weightedprob(f,cat)
fscore = -2*log(p)
ret = invchi2(fscore, len(features)*2)

倒置对数卡方函数：

def invchi2(chi, df):
    m = chi / 2
    sum = term = exp(-m)
    for i in range(1, df//2):
        term *= m/i
        sum += term
    return min(sum, 1)

阈值：可以定义bad类为0.6，good类为0.2，针对good小于0.2，对bad小于0.6，则可归为未知

持久化

SQLite

神经网络和支持向量机可以捕捉到输入特征之间更为复杂的关系

第7章决策树建模

CART(Classification and Regression Trees)分类回归树。

分列函数：是将数据集按照某feature某value分成两个集合，如果value为连续值，可以考虑>=作为分界，否则使用==

选择最好的拆分方式：

基尼不纯度，是指将来自数据集的某种结果随机应用于集合中某一个数据项的预期误差率。

total, imp = sum(class_count.values()), 0
for class, count in class_count.items():
    p1 = count / total
    for c, n in class_count.items():
        if class == c: continue
        p2 = n/total
        imp += p1*p2
imp  # 1 - sum(pi**2)

熵，代表的是集合的无序程度。

p(i) = count(i) / count(total rows)
Entropy = - 针对所有结果的p(i)*log(p(i))之和

与基尼系数相比，熵达到峰值的过程要相对慢一点

信息增益（Information gain）：所谓信息增益，是指当前熵与两个新群组经加权平均后的熵之间的差值。 gain = current_score - p(set1)*scoref(set1) - (1-p(set1))*scoref(set2)

决策树的剪枝

决策树可能变得过度拟合（overfitted）。
剪枝的过程就是对具有相同父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否会小于某个指定的阈值。此时将节点合并到父节点。如

T->
F->2:'year'?
    T->{'Basic':4}
    F->{'None':3}
--->
T->...
F->{'Basic':4,'None':3}

处理缺失数据

如果分类的时候有缺失值，而其值又位于决策树的分类路径上，则可以两边分支均走，两边赋予不同的权重。其权重可以通过结果返回的数目进行统计计算。例如T-返回{‘Basic’:4},F-返回{‘Basic’：2，‘None’：5}，则根据概率计算{'basic':4*4/11+2*7/11,'None':5*7/11}

处理数值型结果

如果结果为数值型，则不理想。如果将结果全部离散为分类，则会面对这样一个事实：有些数字彼此非常的接近，而其他则距离比较远。可以使用方差（variance）作为评价函数来取代熵或基尼不纯度。

$variance = {\sum (d-mean)^2 \over len(rows)}$
使用该函数后，选择节点判断条件的依据就变了：拆分之后令数据较大者位于树的一侧，数字较少者位于树的另一侧，以这种方式就可以降低分支的总体方差

对房屋价格进行建模

Zillow API

对热度评价进行建模

Hot or Not API

什么时候使用决策树

可以同时对数值和分类作为输入。决策树允许数据的不确定性分配（返回各种分类以及个数的字典）。
决策树的缺陷是只能创建满足“大于、小于”条件的节点，如果决定分类的因素取决于更多变量的复杂组合（如两个变量的差），则进行分类就比较困难了。
- 大量数值型输入和输出的问题，未必是好的选择
- 数值型输入之间存在许多错综复杂的关系，也不是好的选择

多路拆分

第8章构建价格模型

K-最近邻算法

knn-k近邻数：选择过少过多都会降低准确性
定义相似度：欧几里得距离算法

为近邻分配权重

反函数：将距离转变为权重，距离越近，权重越大 num/(distance+const) 两者为常量num=1,const=1，缺点：对噪声过于敏感
减法函数：常量值-距离，小于0赋值0。对于有些项可能找不到近邻
高斯函数：距离为0时为1，随着距离变大，值变小，但不会跌到0. $e^{-{dist^2\over2*sigma^2}}$ ,sigma默认为10

加权后计算公式为 ${\sum_1^k weight*price}\over \sum_1^k weight$

交叉验证

将数据拆分成训练集和测试集的一种技术的统称。
方差，对数字求平方会突显较大的差值。如果准许个别误差大，总体误差低，也可以使用差的绝对值求和。

缩放比例

对结果影响不大但是具有较大取值范围的特征会对距离计算影响特别大。对每个特征需要采用一种合适的参数进行缩放。可以采用优化方法进行优化。
成本函数：交叉验证后的方差
优化方法：退火算法、遗传算法

不对称分布

例子：商品购买信息中，部分是原价，部分是50%折扣价，是是否折扣则未知

估计概率密度：根据位于区间范围内的最近邻个数（权重和）与总体最近邻k个数（权重和）求商计算概率
累积概率：低于当前值的概率
实际概率：在价格点有凸起
平滑曲线：假设每个价位点的概率都等于其周边概率的一个加权平均

smoothed = []
for i in range(len(probs)):
    sv = 0.0
    for j in range(len(probs)):
        dist = abs(i-j)*0.1
        weight = gaussion(dist, sigma=5)
        sv += weight*probs[j]
    smoothed.append(sv)

使用真实数据 -- eBay API

第9章高阶分类：核方法与SVM

决策边界：是一条线，位于该线一侧的每一个点会被赋予某个分类，而位于另一侧的每一个点会被赋予另一个分类
线性分类的工作原理是寻找每个分类中所有数据的平均值，并构造一个代表该分类中心位置的点。然后就可以通过判断距离哪个中心点位置最近来对新的坐标点进行分类。
向量点积：将向量一的每个值和向量二的对应值相乘，再累积相加。M0、M1分别为两类的中心点
class = sign((X-(M0+M1)/2) . (M0-M1))
--> class = sign(X.M0 - X.M1 + (M0.M0 - M1.M1)/2)
class 值为 1 --> M0类 -1 -->M1类

分类特征

是否问题：
SVM只能处理数值型数据，对于分类数据来说必须转换，简单的方法：是否，是转为1，否转为-1，缺失未知为0
兴趣列表：
可以列出两人之间的共同爱好个数，可以将爱好划分不同的层次，如果位于同一大层次下可以适当加分，如滑雪和滑板可以为0.8
住址：
利用yahoo！Maps来确定距离

对数据进行缩放

各项数据进行归一化： new = (old - min)/(max - min)

核方法

对于二维环状环绕，可以通过对x**2+y**2变换获得可线性划分的新数据集。
真实问题中，变换的方法复杂得多，其中包含多维变换，如a=x**2,b=x*y,c=y**2坐标变换。
核技法：用一个新的函数来取代原来的点积函数，当借助于某个映射函数将数据第一次变换到更高维度的坐标空间时，新函数将会返回高维度坐标空间内的点积结果。
径向基函数（radial-basis function）：非线性的

def rbf(v1, v2, gamma=20):
    dv = [v1[i]-v2[i] for i in range(len(v1))]
    l = veclength(dv)
    return e**(-gamma*l)

现在对待分类点与均值之间计算距离，即可以转变为待分类点分别与两类点之间计算点积后再平均，确认两者之间谁大。

SVM

思路是尝试寻找一条尽可能远离所有分类的线。这条线被称为最大间隔超平面（maximum-margin hyperplane）。线附近的点称为支持向量。支持向量机使用的也是点积的结果，因此可以同样利用核技法用于非线性分类。

第10章寻找独立特征

应用
- 鸡尾酒宴会，多个说话声音中获取某一个
- 文档中的单词使用模式

构造文档矩阵：选取在3篇以上出现，再60%以下出现的单词作为列，行作为文档

非负矩阵因式分解NMF

权重矩阵 * 特征矩阵 = 原矩阵
特征矩阵：在该矩阵中，每个特征对应一行，每个单词对应一列。矩阵中的数字代表了某个单词相对于某个特征的重要程度。
权重矩阵：该矩阵的作用就是将特征映射到文章矩阵，其中每一行对应于一篇文章，每一列对应于一个特征。
非负矩阵：保证所有的权重和特征都是正数或者0，才具有物理意义。

算法实现：判断最终结果与理想结果的接近程度，对两个矩阵的每一元素差值平方累加。

乘法更新法则：
hn：经转置后的权重矩阵与数据矩阵相乘得到的矩阵
hd：经转置后的权重矩阵与原权重矩阵相乘，再与特征矩阵相乘得到的矩阵
wn：数据矩阵与经转置后的特征矩阵相乘得到的矩阵
wd：权重矩阵与特征矩阵相乘，再与经转置后的特征矩阵相乘得到的矩阵
1. 随机初始化权重矩阵和特征矩阵
2. 计算cost，difcost(v,w*h)，cost=0，退出
3. hn = w.T*v, hd = w.T*w*h
4. h = matrix(array(h) * array(hn) / (array(hd)))
5. wn = (v*h.T), wd = (w*h*h.T)
6. w = matrix(array(w) * array(wn) / array(wd))

第11章智能进化

遗传编程：受到生物进化理论的启发而形成的一种机器学习技术，通常工作方式是：以一大堆程序（被称做种群）开始，这些程序可能是随机产生的，也可以是人为设计的，并且被认为是某种程度上的一组优解。然后针对用户定义的任务进行竞争，排序。

进化：

变异对程序的某些部分以随机的方式稍作修改
交叉（配对）先将某个最优程序的一部分去掉，然后选择其他最优程序的一部分进行替代

终止条件：
- 找到了最优解
- 找到了表现足够好的解
- 题解再历经数代之后都没有得到任何改善
- 繁衍的代数达到了规定的限制

将程序以树形方式表示

随机产生初始解：
创建一个节点并随机选择一个函数，然后查看随机选择函数的所需子节点数，针对子节点递归创建。pc程序树所需输入参数的个数。fpr给出新建函数属于函数节点的概率，ppr给出当前节点不是函数节点时属于paranote节点的概率（pc个参数之一），maxdepth最大递归层数。

变异：改变节点上的函数；利用全新的子树来替换某一子树；变异的次数不宜，不宜对大多数节点都实施变异，定义一个小的概率，从根节点开始往下，直到有节点变异或结束。

交叉：以两棵树作为输入，以一棵树的分支取代另一颗的分支。

def crossover(t1, t2, probswap=0.7, top=1):
    if random() < probswap and not top:
        return deepcopy(t2)
    else:
        result = deepcopy(t1)
        if isinstance(t1,node) and isinstance(t2,node):
            result.children = [crossover(c,choice(t2.child), probswap, 0) for c in t1.child]
        return result

运行参数：

maxgen 最大遗传代数
rankfunction 排序程序
mutationrate 发生变异的概率，传递给mutate
breedingrate 发生交叉的概率，传给crossover
popsize 种群个数
probexp 构造新程序时，选择评价较低程序这一概率的递减比例 selectindex = int(log(random())/log(probexp))取值越小得到的数也越小
probnew 引入一个全新随机程序的概率

scores = rankfunction(pop)
if scores[0][0] == 0: break
newpop = [scores[0:len(scores)*save_rate]]
while len(newpop) < popsize:
    if random() < probnew:
        newpop.append(makerandomtree(pc))
    else:
        newpop.append(mutate(crossover(scores[selctindex()], scores[selcetindex()], probswap=breedingrate), pc, probchange=mutationrate))

仅仅选择表现优异的少数几个解很快会使种群变得极端同质化，这种称为局部最大化。