机器学习

浅入浅出:PageRank算法 使用 TextRank 算法为文本生成关键字和摘要 基于物品的协同过滤 如何使用MapReduce实现基于物品的协同过滤(1) 如何使用MapReduce实现基于物品的协同过滤(2) 浅入浅出:K近邻算法 使用mahout下的朴素贝叶斯分类器对新闻分类 使用Affinity Propagation进行聚类 K-medoids聚类 矩阵分解在推荐系统中的应用:NMF和经典SVD实战 使用特征递归消除筛选特征 如何分配权重 比较NMF、PCA和VQ 方差和协方差 基于SVD的协同过滤 逻辑斯谛回归代码实现 隐语义模型和NMF(非负矩阵分解) 使用PCA处理MNIST数据集 使用GBDT选取特征 基于贝叶斯的文本分类系统的数据库设计 在hadoop1.2.1上安装mahout 0.9 Hadoop 2.4 实现Kmeans聚类算法 在Iris数据集上对比PCA、LDA、NMF 基于贝叶斯的文本分类实战 单层决策树 Logistic regression(逻辑斯蒂回归) 基于用户的协同过滤 词袋模型与文档-词矩阵 如何实现拼音与汉字的互相转换 梯度下降法 如何判定相似度 MovieLens数据集介绍 基于KNN的文本分类实战 Jasper文本分类系列博客阅读摘录 使用 Mean Shift进行聚类 朴素贝叶斯的三个常用模型:高斯、多项式、伯努利 使用决策树处理iris数据集 浅入浅出:从Kmeans到Kmeans++ 如何持久化scikit-learn中训练好的模型 浅入浅出:DBSCAN聚类算法(1) 浅入浅出:DBSCAN聚类算法(2) 2015阿里移动推荐算法比赛第一赛季总结 爬山算法 使用朴素贝叶斯分类器划分邮件 层次聚类 基于MapReduce的频繁项集挖掘 搜狗实体关系提取比赛

爬山算法


#机器学习


2014-04-03

**爬山法(climbing method)**是一种优化算法,其一般从一个随机的解开始,然后逐步找到一个最优解(局部最优)。 假定所求问题有多个参数,我们在通过爬山法逐步获得最优解的过程中可以依次分别将某个参数的值增加或者减少一个单位。例如某个问题的解需要使用3个整数类型的参数x1、x2、x3,开始时将这三个参数设值为(2,2,-2),将x1增加/减少1,得到两个解(1,2,-2), (3, 2,-2);将x2增加/减少1,得到两个解(2,3, -2),(2,1, -2);将x3增加/减少1,得到两个解(2,2,-1),(2,2,-3),这样就得到了一个解集:

(2,2,-2), (1, 2,-2), (3, 2,-2), (2,3,-2), (2,1,-2), (2,2,-1), (2,2,-3)

从上面的解集中找到最优解,然后将这个最优解依据上面的方法再构造一个解集,再求最优解,就这样,直到前一次的最优解和后一次的最优解相同才结束“爬山”。

一个例子

设方程 y = x1+x2-x3x1是区间[-2, 5]中的整数,x2是区间[2, 6]中的整数,x3是区间[-5, 2]中的整数。使用爬山法,找到使得y取值最小的解。

代码如下:

import random

def evaluate(x1, x2, x3):
    return x1+x2-x3

if __name__ == '__main__':
    x_range = [ [-2, 5], [2, 6], [-5, 2] ]
    best_sol = [random.randint(x_range[0][0], x_range[0][1]), 
           random.randint(x_range[1][0], x_range[1][1]), 
           random.randint(x_range[2][0], x_range[2][1])]
    
    while True:
        best_evaluate = evaluate(best_sol[0], best_sol[1], best_sol[2])
        current_best_value = best_evaluate
        sols = [best_sol]
        
        for i in xrange(len(best_sol)):
            if best_sol[i] > x_range[i][0]:
                sols.append(best_sol[0:i] + [best_sol[i]-1] + best_sol[i+1:])
            if best_sol[i] < x_range[i][1]:
                sols.append(best_sol[0:i] + [best_sol[i]+1] + best_sol[i+1:])
        print sols
        for s in sols:
            el = evaluate(s[0], s[1], s[2])
            if el < best_evaluate:
                best_sol = s
                best_evaluate = el
        if best_evaluate == current_best_value:
            break
    
    print 'best sol:', current_best_value, best_sol

某次运行结果如下:

[[0, 5, 1], [-1, 5, 1], [1, 5, 1], [0, 4, 1], [0, 6, 1], [0, 5, 0], [0, 5, 2]]
[[-1, 5, 1], [-2, 5, 1], [0, 5, 1], [-1, 4, 1], [-1, 6, 1], [-1, 5, 0], [-1, 5, 2]]
[[-2, 5, 1], [-1, 5, 1], [-2, 4, 1], [-2, 6, 1], [-2, 5, 0], [-2, 5, 2]]
[[-2, 4, 1], [-1, 4, 1], [-2, 3, 1], [-2, 5, 1], [-2, 4, 0], [-2, 4, 2]]
[[-2, 3, 1], [-1, 3, 1], [-2, 2, 1], [-2, 4, 1], [-2, 3, 0], [-2, 3, 2]]
[[-2, 2, 1], [-1, 2, 1], [-2, 3, 1], [-2, 2, 0], [-2, 2, 2]]
[[-2, 2, 2], [-1, 2, 2], [-2, 3, 2], [-2, 2, 1]]
best sol: -2 [-2, 2, 2]

可以看到,最优解是-2,对应的x1、x2、x3分别取值-2、2、2

如何找到全局最优

爬山法获取的最优解的可能是局部最优,如果要获得更好的解,多次使用爬山算法(需要从不同的初始解开始爬山),从多个局部最优解中找出最优解,而这个最优解也有可能是全局最优解。

另外,模拟退火算法也是一个试图找到全局最优解的算法。


( 本文完 )