集体智慧编程笔记

阅读集体智慧编程所做的一些笔记

集体智慧导言

集体智慧：为了创造新的想法，而将一群人的行为、偏好和思想组合在一起

机器学习：是人工智能（AI,artificial intelligence）领域中和算法相关的一个子域，它允许机器不断地学习。大多数情况下，将一组数据传递给算法，由算法推断出与这些数据的属性相关的信息。数据->训练->模型->预测->结果。

• 局限性：只能凭借已有数据进行归纳训练，而且归纳方式也有局限性

提供推荐

协作型过滤

Collaborative filtering：对一大群人进行搜索，并从中找出品味相近的一小群人

条件：人、特征、特征值

相似度计算函数(值越大，相似度越高)：

1. 欧几里得距离：当距离越大，则偏好越近；当=1时则代表偏好相同 $$\frac{1}{1+\sqrt{\left({x_2-x_1}\right)^2 + \left({y_2-y_1}\right)^2}}$$ ​

2. 皮尔逊相关度：判断两组数据与某一直线拟合程度的一种度量。

   • 找出两者都存在的特征
   • 计算两者特征值总和(sum1,sum2)、平方总和(sumSq1,sumSq2)以及乘积之总和(pSum)
   • 之后按如下公式进行计算

   # 计算皮尔逊评价值
   num = pSum - (sum1 * sum2 / n)
   den = sqrt((sumSq1 - pow(sum1 , 2) / n) * (sumSq2 - pow(sum2 , 2) / n))
   if den == 0 : return 0
   
   r = num / den

   $$num = pSum - \frac{sum1-sum2}{n}$$ $$den = \sqrt{\left(sumSq1 - \frac{sum1^2}{n}\right) * \left(sumSq2 - \frac{sum2^2}{n}\right) }$$

3. 曼哈顿距离算法

4. Jaccard/Tanimoto系数(Tanimoto coefficient)：数据中交集和并集的比例

   '''
   若数据集中取值只有0或1，则可定义度量如下
   下列代码使用1-系数的作用是使得值越小代表相似度越高
   '''
   def tanimoto(v1 , v2) :
       c1 , c2 , shr = 0 , 0 , 0 
       for i in range(len(v1)) :
           if v1[i] != 0 : c1 += 1 # 出现在v1中
           if v2[i] != 0 : c2 += 1 # 出现在v2中
           if v1[i] != 0 && v2[i] != 0 : shr += 1 # 同时出现在v1和v2中
       
       return 1.0 - (float(shr) / (c1 + c2 - shr))

   ​

5. 互信息系数：度量非线性相关性

6. 更多相似度计算函数

推荐用户

1. 通过相似度计算函数计算除当前用户外的所有用户的相似度
2. 将相似度值从大到小依次排序
3. 取得前n个结果

推荐物品

1. 构建相似度表

用户	相似度	物品	S.x物品
xxx	取值为0~1	用户评价值	用户评价值 * 相似度
总计			$\sum_{i=1}^n s_i$
Sim.Sum			相似度之和(该用户所有评论的物品)
总计/Sim.Sum			.

1. 将相似度表从大到小排序

发现群组

分级聚类

分级聚类：通过连续不断地将最为相似的群组两两合并，来构造出一个群组的层级结构（每个群组都是由单一元素开始的）

群组数据结构

'''
聚类群组(层级树)：以树状结构表示
可通过PIL(Python Imaging Library)进行树状图绘制
'''
class bicluster:
    def __init__(self , vec , left = None , right = None , distance = 0.0 , id = None):
        self.vec = vec 		# 数据集，两个群组合并后的数据集为其均值
        self.left = left 	# 左节点
        self.right = right	# 右节点
        self.id = id		# 聚类唯一id，合并聚类的id为负数
        self.distance = distance	# 群组的距离

步骤

1. 初始化聚类群组列表(数据集的每一行为一个群组)
2. loop start：计算每个群组间的距离（可参考上述的相似度计算函数），找到距离最小的两个群组x和y
3. 计算距离最小的两个群组的均值—>作为新群组的数据集
4. 构造新群组
5. 从群组列表中删除x和y，并将新群组加入到群组列表中 loop end
6. 返回群组列表第一个元素 —>其为聚类最终结果

缺点

1. 在没有额外投入的情况下，树状图不会真正将数据拆分到不同组
2. 该算法的计算量很大，时间复杂度为$n^3$

K-均值聚类

K-均值聚类：在分级聚类的基础上添加k个中心点的概念，即最终确定的聚类是k个，而非1个

步骤

1. 随机确定k个中心位置，
2. loop start：将各个群组分配到最临近的中心点；
3. 分配完成后，聚类中心点会移动到该聚类的的所有节点的平均位置处
4. 当分配过程不再发生变化，结束循环loop end

搜索与排名

构建搜索引擎的步骤一般如下：

1. 数据搜集：获取网页url、内嵌网页等

2. 建立索引：创建网页中单词与网页的索引，附属信息有：位置及归属网页等

3. 搜索排名：根据单词搜索结果，使用不同的度量方法进行排名；方法有以下几种

   • 基于内容排名

     • 单词频度
     • 文档位置
     • 单词距离

   • 利用外部回指链接

     • 简单计数法

 - PageRank算法
 - 基于链接文本的pr值

• 基于点击行为的神经网络

归一化函数

对于评价值来说，其特点有值区间不确定性、可比较性差；为了让其具有相同的值域和变化方向，需要对结果归一化处理。

而评价值的大小比较，取决于评价方法而定，有的评价方法评分值越大越好，有的则越小越好。

下列是该书中的归一化处理函数：

def normalizescores(self , scores , smallIsBetter = 0):
       vsmall = 0.00001 # 避免被零整除
	
       # 当值越小时，评价值越高
       if smallIsBetter :
           minscore = min(scores.values())
           return dict([(u , float(minscore) / max(vsmall , l)) for u , l in scores.items()])
       else :
           maxscore = max(scores.values())
           if maxscore == 0 : maxscore = vsmall
           return dict([(u, float(c) / maxscore) for u, c in scores.items()])

归一化资料可参考：

• 离差标准化和Z-Score标准化)
• 数据的标准化和归一化

基于内容排名

顾名思义，将网页搜索结果根据网页内容进行评价，根据评价结果进行排名

单词频度

单词频度：根据搜索词在网页中出现的次数对网页进行评价

缺陷：若搜索词在某个网页中出现次数很多，可是该网页却不是最优结果

文档位置

文档位置：根据搜索词在文档中的位置之和进行评价，位置越靠前评价值越高

单词距离

单词距离：根据查询的多个搜索词在网页中的距离之和进行评价，距离越小评价值越高

利用外部回指链接

简单计数

简单计数：根据网页被其他网页引用次数进行评价，引用次数越多评价值越高

PageRank算法

PageRank算法由Google创始人(以Larry Page命名)发明，该算法为每个网页都赋予了一个指示网页重要程度的评价值

计算公式：

假设有A,B,C,D四个网页，那么PR(A)的计算公式如下：

PR(A) = 0.15 + 0.85 * (PR(B) / linkcount(B) + PR(C) / linkcount(C) + PR(C) / linkcount(C))

阻尼因子=0.85，指示用户持续点击每个网页中链接的概率为85%

利用链接文本

利用链接文本：根据网页的链接文本来决定网页的相关程度

描述：根据搜索词得到网页A和B，A->B，若B在搜索结果列表中，则把B的评价值加上A的pr值

搜索结果列表
for 搜索词 in 搜索词列表 :
	获取搜索词对应的网页链接关系表[(from , to) , ...]
    for (from , to) in [(from , to) , ...]:
        if to in 搜索结果列表 :
            pr = pr(from)
            搜索结果列表[to] += pr

优化

solve：协作类问题

擅长处理：受多种变量影响，存在许多可能解的问题，以及结果因这些变量的组合而产生很大变化的问题

优化算法是通过尝试许多不同题解并给这些题解打分以确定其质量的方式来找到一个问题的最优解。

步骤：

1. 描述题解
2. 确定成本函数(The Cost Function)
3. 选取优化算法

随机搜索

算法思想：构造可能出现的解题输入参数组合，并代入到成本函数，将每组解进行比较，得到最优解（如下图，从所有题解中找到最优解—这里只标记了几个局部最优解，进行比较）

缺点：该算法是到处跳跃的(jumps around)，非常低效；其不会自动寻找已经发现的最优解相近的题解

爬山法

算法思想：从一个随机搜索题解开始，然后在其临近的题解中寻找最优解；下图中假设找到红点A，将临近往上或往下的点进行解计算后，找到更优解，重复该步骤，直到邻近的解都比该解大，则认为是该点是最优解

对比：相较于随机搜索，其具有更低的成本

缺点：算法结果得到的其实不是全局最优解，而是局部最优解(类似于Gradient descent)

为了得到全局最优解，其算法有个更好的替代方案—随机重复爬山法(random-restart hill climbing),即让爬山法以多个随机生成的初始解为起点运行若干次，借此希望其中有一个解能逼近全局最优解

模拟退火算法

退火：将合金加热后再慢慢冷却的过程

算法思想：以一个问题随机解开始，通过退火期间的迭代，随机选取题解中的某个数字，然后朝某个方向变化；算法执行过程中实际计算当前题解和新题解(即随机选取的数字计算的解)，当新题解优于当前题解时，则新题解替换当前题解；若新题解劣于当前题解，则需要判断新题解是否在可接受范围，若可接受，则替换当前题解

退火过程如下：

条件 —> 温度(temperature) , 冷却因子(coolfactor)

公式 —> temperature = temperature * coolfactor

接受范围值计算公式：

$$p = e^{(-(highcost - lowcost) / temperature)}$$

由于初始温度很高，所以p初始时将无限趋近于1，随着题解的差异越来越大，概率越来越低，因此该算法更倾向于稍差的解，而不会是最差的解

核心代码：

'''
p : 可能的题解范围
costfunction : 成本计算函数
t : 初始温度
cf : 冷却因子
'''
def annealingoptimize(p , costfunction , t , cf) :
    while t > 0.1 :
        i # 当前题解参数
        j # 新题解参数
        # 计算当前题解
        currentcost = costfunction(i)
        # 移动方向，计算新题解
        newcost = costfunction(j)
        # 这里为什么使用random.random()? 
        # 因为如果使用上一次的p，则大概率的可能只能求取到局部最优解
        if newcost < currentcost or random.random() < pow(math.e , - (newcost - currentcost) / t ) :
            currentcost = newcost
        t = t * cf

遗传算法

算法思想：通过成本函数建立种群，在种群中通过精英选拔法(elitism)得到最优解，种群剩余的解再通过修改题解的参数得到全新的题解，两者组合得到新种群；通过重复以上过程n次后，最终得到的题解为最优解

名词概念：

• 种群(population)：随机生成一组解
• 精英选拔法：种群中位于最顶层的题解
• 修改题解
  • 变异(mutation)：对现有解进行微小的、简单的、随机的改变
  • 交叉(crossover)或配对(breeding)：随机选取两个解，并将两者按某种方式进行结合

伪代码：

'''
popsize : 群组解个数
costfunction : 成本函数
n : 迭代次数
'''
def geneticoptimize(popsize , costfunction , n ) :
    pop = []
    for i in range(popsize) :
        pop.append(costfunction(i))
    
    for i in range(n) :
        # 当前种群的最优题解
        sorted(pop)
        # 创建新群组
        newpop = []
        # 添加当前群组最优解
        newpop.append(pop[:1])
        # 添加当前群组剩余群组修改题解后的群组
        remainpop = pop[1:]
        newpop.append(mutation(remainpop) or crossover(remainpop))
        
        pop = newpop
    
    # 输出最优解
    return pop[0]

文档过滤

solve：通过算法学习并鉴别文档所属的分类

典型应用场景：

• 自动划分邮件类别
• 垃圾邮件过滤

早期的邮件过滤做法都是基于规则的分类器（rule-based classifiers）；事先定义好规则，例如单词黑名单、英文大写字母的过多使用等等

存在的问题：

• 过滤不准确，正常邮件被认为是垃圾邮件

文档分类的一般做法如下：

1. 收集现有的已分类好的文档数据作为训练数据
2. 计算文档中单词在该分类的概率P(word | category)
3. 对2计算的概率作加权平均(当训练集过小时，会导致分类不准确)
4. 通过学习算法计算文档属于分类的概率P(category | document)
   • 朴素贝叶斯(NaiveBayes)
   • 费舍尔方法(SpamBayes)

朴素贝叶斯

贝叶斯定理公式：

$$P(A | B) = \frac{ P(B | A) * P(A) } {P(B)}$$

使用贝叶斯的条件：A和B发生的概率是相互独立，不相关的

代入到上述文档分类步骤：

1. 计算P(document | category)，即将该document所有的word出现在该category概率相乘

$$P(document | category) = \prod_i^n P(word_i | category)$$

1. 通过1计算的概率，代入到贝叶斯公式计算P(category | document) $$P(category | document) = \frac{P(document | category) * P(category)}{P(document)}$$

限于算法计算的概率是依赖训练集的丰富程度的，所以对文档的分类会存在不准确性的；为了规避这种不准确性，可以设置一个分类划分的阈值n— 即算法得到的分类的概率值必须大于在其他分类中的概率的n倍

费尔舍方法

费尔舍方法为文档中的每个特征都求得了分类的概率，然后又将这些概率组合起来，并判断其是否有可能构成一个随机集合。

步骤：

1. 通过已经计算好P(word | category)，来求出P(category | word)；常见方法是(具有指定特征的属于某分类的文档数) / (具有指定特征的文档总数)
   • 属于某分类的概率clf = P(word | category)
   • 属于所有分类的概率freqsum = P(word | category)之和
   • 最终概率p = clf / freqsum
2. 算出文档中所有word的概率之积
3. 去取自然对数再乘以-2；score = -2 * log(p)
4. 最后利用倒置对数卡方函数求得概率，得出该组概率的最大值—如果概率彼此独立且随机分布，则此计算结果满足对数卡方分布(chi-squared distribution)