分类

类型:
不限 游戏开发 计算机程序开发 Android开发 网站开发 笔记总结 其他
评分:
不限 10 9 8 7 6 5 4 3 2 1
原创:
不限
年份:
不限 2018 2019

技术文章列表

  • 机器学习 24 、MF ANN

    前文链接:https://write-bug.com/article/2696.html
    MF(Matrix Factorization)基于矩阵分解的推荐算法-隐语义模型:ALS、LFM、SVD、SVD++
    在15年左右流行
    ALS:-交替最小二乘
    我们之前学习的协同过滤CF:单独考虑user、item
    这里同时考虑User-item两方面:
    原来我们的UI稀疏打分矩阵\<m,n>:

    一般公司用户量可以随意达到上亿,物品量如音乐可以达到几十万,用户量之所以多,是因为可能一个用户有多个账户等等,共同组成一个很大很稀疏的矩阵那么面对这样一个矩阵,我们可以通过矩阵分解来解决:
    将User和Item分别映射到新的空间,分解成两个矩阵,U 和I两个维度都不变



    K值远小于M和N,从而达到降维目的
    无需关注新空间的各个维度,只需假定存在 ,即用向量表示user和item
    新的维度称为Latent Factor(隐因子)

    K的维度相比原来来说很小很小,并且可以人为设定,只需要两个矩阵相乘就能得到UI矩阵,即R’ ≈R
    两个矩阵相似如何界定?误差
    误差表示:RMSE :均方根误差
    目标:真实矩阵,和结果矩阵之间的尽可能逼近
    最小化平方误差作为损失函数:

    考虑矩阵稳定性,引入L2正则项,得到损失函数:

    这里的rui就是上面所说的R,即原矩阵user对item打的分数
    xuyi即分解矩阵后再相乘的预估分数,两个相减就是误差
    未知数:
    Xu:user vectoryi:item vector如何求解最优值:求导=0
    公式1:

    导数为0,可得到:

    同理对yi求导(公式2):

    为什么叫交替二乘法?
    这里的做法是让x和y交替下降:

    随机生成X、Y向量(初始化)
    固定Y,更新X(公式1)
    固定X,更新Y(公式2)
    第2、3步循环,直到满足收敛条件(RMSE)

    ——均方根误差
    那么我们得到这两个小矩阵,可以做什么?
    item-item :IK*KI=IIUser-User:UK*KU=UUuser与item的向量
    LFM思路和ALS算法类似,区别在于,ALS利用坐标下降法,LFM利用梯度下降法
    假设:
    评分矩阵𝑅𝑚,𝑛,m个用户对n个物品评分

    𝑟𝑢,𝑖:用户u对物品i的评分
    𝑅𝑚,𝑛 = 𝑃𝑚,𝐹 ∙ 𝑄𝐹,𝑛:R是两个矩阵的乘积
    P:每一行代表一个用户对各隐因子的喜欢程度 ,即前面的user矩阵
    Q:每一列代表一个物品在各个隐因子上的概率分布,即前面的item矩阵


    在之前的随机梯度下降中,我们更新w(t+1)=w(t) - a*g(梯度)
    那么根据这样的思路,这里把矩阵P与Q的分数当作权重w来更新:

    矩阵展开后相当于对每个元素分数进行偏导:

    随意抽取中间这个元素作为代表,求取偏导:

    由于

    所以后面两个等式相等,之后就有一件很有意思的事情发生了:P的分数是由上一时刻的Q更新的,Q的分数是由上一时刻的P更新的。也就是类似上面的坐标下降法:交替进行。
    代入原式:

    LFM实践:
    class LFM(object): def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500): '''rating_data是list<(user,list<(position,rate)>)>类型 ''' self.F = F#维度K self.P = dict() self.Q = dict() self.alpha = alpha#学习率 self.lmbd = lmbd self.max_iter = max_iter#迭代轮数 self.rating_data = rating_data#矩阵 '''随机初始化矩阵P和Q''' for user, rates in self.rating_data: self.P[user] = [random.random() / math.sqrt(self.F) for x in xrange(self.F)] for item, _ in rates: if item not in self.Q: self.Q[item] = [random.random() / math.sqrt(self.F) for x in xrange(self.F)] def train(self): '''随机梯度下降法训练参数P和Q ''' for step in xrange(self.max_iter): for user, rates in self.rating_data: for item, rui in rates: hat_rui = self.predict(user, item) err_ui = rui - hat_rui for f in xrange(self.F): self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f]) self.Q[item][f] += self.alpha * (err_ui * self.P[user][f] - self.lmbd * self.Q[item][f]) self.alpha *= 0.9 # 每次迭代步长要逐步缩小 def predict(self, user, item): '''预测用户user对物品item的评分 ''' return sum(self.P[user][f] * self.Q[item][f] for f in xrange(self.F))if __name__ == '__main__': '''用户有A B C,物品有a b c d,列表模拟矩阵:''' rating_data = list() rate_A = [('a', 1.0), ('b', 1.0)] rating_data.append(('A', rate_A)) rate_B = [('b', 1.0), ('c', 1.0)] rating_data.append(('B', rate_B)) rate_C = [('c', 1.0), ('d', 1.0)] rating_data.append(('C', rate_C)) lfm = LFM(rating_data, 2) lfm.train() for item in ['a', 'b', 'c', 'd']: print(item, lfm.predict('A', item)) # 预测计算用户A对各个物品的喜好程度SVDLFM有什么缺点?没有考虑客观的偏置,所以带偏置的LFM称为SVD
    什么是偏置,比如说有的人很极端给一些物品很高或者很低的分数,而有的人给每个物品都很平均的分数,还有包括地区等等都会影响对物品的看法,所以就有一个偏置存在。
    偏置:事件固有的,不受外界影响的属性。

    𝜇:训练集中所有评分的平均值
    𝑏𝑢:用户偏置,代表一个用户评分的平均值
    𝑏𝑖:物品偏置,代表一个物品被评分的平均值


    更新:

    SVD实践:
    class BiasLFM(object): def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500): '''rating_data是list<(user,list<(position,rate)>)>类型 ''' self.F = F self.P = dict() self.Q = dict() self.bu = dict() self.bi = dict() self.alpha = alpha self.lmbd = lmbd self.max_iter = max_iter self.rating_data = rating_data self.mu = 0.0 '''随机初始化矩阵P和Q''' cnt = 0 for user, rates in self.rating_data: self.P[user] = [random.random() / math.sqrt(self.F) for x in xrange(self.F)] self.bu[user] = 0#初始化bu cnt += len(rates) for item, rate in rates: self.mu += rate if item not in self.Q: self.Q[item] = [random.random() / math.sqrt(self.F) for x in xrange(self.F)] self.bi[item] = 0#初始化bi self.mu /= cnt#计算μ def train(self): '''随机梯度下降法训练参数P和Q ''' for step in xrange(self.max_iter): for user, rates in self.rating_data: for item, rui in rates: hat_rui = self.predict(user, item) err_ui = rui - hat_rui #更新两个b self.bu[user] += self.alpha * (err_ui - self.lmbd * self.bu[user]) self.bi[item] += self.alpha * (err_ui - self.lmbd * self.bi[item]) for f in xrange(self.F): self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f]) self.Q[item][f] += self.alpha * (err_ui * self.P[user][f] - self.lmbd * self.Q[item][f]) self.alpha *= 0.9 # 每次迭代步长要逐步缩小 def predict(self, user, item): '''预测用户user对物品item的评分,加偏置 ''' return sum(self.P[user][f] * self.Q[item][f] for f in xrange(self.F)) + self.bu[user] + self.bi[item] + self.muif __name__ == '__main__': '''用户有A B C,物品有a b c d''' rating_data = list() rate_A = [('a', 1.0), ('b', 1.0)] rating_data.append(('A', rate_A)) rate_B = [('b', 1.0), ('c', 1.0)] rating_data.append(('B', rate_B)) rate_C = [('c', 1.0), ('d', 1.0)] rating_data.append(('C', rate_C)) lfm = BiasLFM(rating_data, 2) lfm.train() for item in ['a', 'b', 'c', 'd']: print(item, lfm.predict('A', item)) # 计算用户A对各个物品的喜好程度SVD++任何用户只要对物品i有过评分,无论评分多少,已经在一定程度上反映了用户对各个隐因子的喜好 程度𝑦𝑖 = (𝑦𝑖1,𝑦𝑖2,…,𝑦𝑖𝐹),y是物品携带的属性,什么意思?比如说A买了3个item,B买了3个item,每个item背后有一系列feature vector,那么我们用A买的3个item背后的fea向量相加(实际计算是学习更新出来的,不一定是相加)代表一个虚拟的物品A,间接表达了这个用户的偏好程度,同理得到向量B,那么对于这个每个人背后的虚拟物品向量,就是y

    所以这个打分是在P上又增加了一个类似于偏置的东西,并做了归一化

    𝑁(𝑢):用户u评价过的物品集合
    𝑏𝑢:用户偏置,代表一个用户评分的平均值
    𝑏𝑖:物品偏置,代表一个物品被评分的平均值


    SVD++实践:
    class SVDPP(object): def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500): '''rating_data是list<(user,list<(position,rate)>)>类型 ''' self.F = F self.P = dict() self.Q = dict() self.Y = dict() self.bu = dict() self.bi = dict() self.alpha = alpha self.lmbd = lmbd self.max_iter = max_iter self.rating_data = rating_data self.mu = 0.0 '''随机初始化矩阵P、Q、Y''' cnt = 0 for user, rates in self.rating_data: self.P[user] = [random.random() / math.sqrt(self.F) for x in xrange(self.F)] self.bu[user] = 0 cnt += len(rates) for item, rate in rates: self.mu += rate if item not in self.Q: self.Q[item] = [random.random() / math.sqrt(self.F) for x in xrange(self.F)] if item not in self.Y:#比之前svd多加了一个y,初始化y self.Y[item] = [random.random() / math.sqrt(self.F) for x in xrange(self.F)] self.bi[item] = 0 self.mu /= cnt def train(self): '''随机梯度下降法训练参数P和Q ''' for step in xrange(self.max_iter): for user, rates in self.rating_data: z = [0.0 for f in xrange(self.F)] for item, _ in rates: for f in xrange(self.F): z[f] += self.Y[item][f]#用户观看过物品的评分集合加和,即虚拟物品向量,即∑Yjf ru = 1.0 / math.sqrt(1.0 * len(rates)) s = [0.0 for f in xrange(self.F)] for item, rui in rates: hat_rui = self.predict(user, item, rates) err_ui = rui - hat_rui self.bu[user] += self.alpha * (err_ui - self.lmbd * self.bu[user]) self.bi[item] += self.alpha * (err_ui - self.lmbd * self.bi[item]) for f in xrange(self.F): s[f] += self.Q[item][f] * err_ui#每个物品的信息和误差相乘的累加 self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f]) self.Q[item][f] += self.alpha * ( err_ui * (self.P[user][f] + z[f] * ru) - self.lmbd * self.Q[item][f]) for item, _ in rates: for f in xrange(self.F): #Y的更新 self.Y[item][f] += self.alpha * (s[f] * ru - self.lmbd * self.Y[item][f]) self.alpha *= 0.9 # 每次迭代步长要逐步缩小 def predict(self, user, item, ratedItems): '''预测用户user对物品item的评分 ''' z = [0.0 for f in xrange(self.F)] for ri, _ in ratedItems: for f in xrange(self.F): z[f] += self.Y[ri][f] return sum( (self.P[user][f] + z[f] / math.sqrt(1.0 * len(ratedItems))) * self.Q[item][f] for f in xrange(self.F)) + \ self.bu[user] + self.bi[item] + self.muif __name__ == '__main__': '''用户有A B C,物品有a b c d''' rating_data = list() rate_A = [('a', 1.0), ('b', 1.0)] rating_data.append(('A', rate_A)) rate_B = [('b', 1.0), ('c', 1.0)] rating_data.append(('B', rate_B)) rate_C = [('c', 1.0), ('d', 1.0)] rating_data.append(('C', rate_C)) lfm = SVDPP(rating_data, 2) lfm.train() for item in ['a', 'b', 'c', 'd']: print(item, lfm.predict('A', item, rate_A)) # 计算用户A对各个物品的喜好程度ANNANN 多维空间检索算法,不完全是算法,是更偏工程的一种方法,时下正在流行的简单方式,从图像检索演化而来,复杂一点的方式一般使用DNN可以达到目的每个用户、物品背后都有自己的向量映射在多为空间的点上,我们的目标就是把这些向量全部映射在一个空间内,求user最近的item点
    稀疏场景适用物品召回:cb倒排(token)、cf倒排(user)
    —召回能力有限
    鲜花和巧克力在情人节的情况下可以关联起来,但是通过cb不能召回,通过cf需要很多很多用户共点击或者共现才会关联
    那么这里如何计算和user距离近的点?之前我们使用cos或jaccard,但是我不能把所有的物品都遍历一遍,计算量过大,所以就引出了ANN的近邻检索annoy
    Annoy目标:建立一个数据结构,在较短的时间内找到任何查询点的最近点,在精度允许的条件下通过牺牲准 确率来换取比暴力搜索要快的多的搜索速度
    先圈出一部分集合,遍历集合取top
    如果推荐的结果不理想,不喜欢,不是这个方法的问题,而是embedding方式的问题
    那么这个集合如何圈呢?
    方案:随机选择两个点,然后根据这两个点之间的连线确定一个可以垂直等分线段的超平面,灰色是两点的连 线,黑色是超平面

    从而由里面的点集合就构成了叶子节点,最终形成整棵树
    建立二叉树结构用于表示空间分布,每一个节点表示一个子空间
    假设,如果两个点在空间彼此靠近,任何超平面不会将他们分开,如果我们搜索空间中的任意一点,和其距离 近的点为推荐候选,通过对二叉树的遍历,可以完成
    重复上页步骤,继续分割 ,过程很像Kmeans要求:每个子节点包含数据不超过K个(10):


    如果落在这个空间内的节点候选太少怎么办?或者本来两个点距离很近,但是被两个空间分割导致不能计算,那么我们就拓宽区域、多建几棵树,每次建立长得样子都不太一样。
    annoy只是多维空间检索中的一种方法,其他还有:

    KD-Tree (KNN-开始不随机,直接找到全局最优,速度慢,建树慢)
    局部敏感哈希LSH
    HNSW
    OPQ等等

    ANN实践:
    annoy安装:pip
    import sysfrom annoy import AnnoyIndexa = AnnoyIndex(3)#建立3颗树a.add_item(0, [1, 0, 0])#添加用户和item点a.add_item(1, [0, 1, 0])a.add_item(2, [0, 0, 1])a.build(-1)print(a.get_nns_by_item(0, 100))#与0这个用户最近的top100集合print(a.get_nns_by_vector([1.0, 0.5, 0.5], 100))#与这个item vector 最近的top100集合下面这个代码是什么意思呢?随着我们候选集合圈的缩小,我们的计算量也在缩小,那么我们目标是让这个候选集合的top和全局的top尽量一致,也就是说要在计算量和召回率之间做一个权衡,那么全局的top我们就只能通过暴力遍历来知道答案了。
    from __future__ import print_functionimport random, timefrom annoy import AnnoyIndextry: xrangeexcept NameError: # Python 3 compat xrange = rangen, f = 100000, 40#初始化10w个点,40颗树t = AnnoyIndex(f)for i in xrange(n): v = [] for z in xrange(f): v.append(random.gauss(0, 1))#高斯分布初始化点 t.add_item(i, v)#添加在树里t.build(2 * f)t.save('test.tree')#保存树limits = [10, 100, 1000, 10000]#圈的大小k = 10#10个候选prec_sum = {}prec_n = 100time_sum = {}for i in xrange(prec_n): j = random.randrange(0, n)#随机选一个点作为用户 #print(j) closest = set(t.get_nns_by_item(j, k, n))#求取与这个用户j最近的全局top10 #print(closest) for limit in limits: t0 = time.time() toplist = t.get_nns_by_item(j, k, limit)#圈内的top10 T = time.time() - t0 found = len(closest.intersection(toplist))#用全局与圈内的top取交集 hitrate = 1.0 * found / k#准确率 #print(hitrate) prec_sum[limit] = prec_sum.get(limit, 0.0) + hitrate time_sum[limit] = time_sum.get(limit, 0.0) + T print(prec_sum[limit])for limit in limits: print('limit: %-9d precision: %6.2f%% avg time: %.6fs' % (limit, 100.0 * prec_sum[limit] / (i + 1), time_sum[limit] / (i + 1)))
    0 留言 2019-06-24 11:08:26 奖励15点积分
  • 机器学习 23 、BM25 Word2Vec

    前文链接:https://write-bug.com/article/2689.html
    word embedding什么是word embedding? 简单的来说就是将一个特征转换为一个向量。在推荐系统当中,我们经常会遇到离散特征,如userid、itemid。对于离散特征,我们一般的做法是将其转换为one-hot,但对于itemid这种离散特征,转换成one-hot之后维度非常高,但里面只有一个是1,其余都为0。这种情况下,我们的通常做法就是将其转换为embedding。
    word embedding为什么翻译成词嵌入模型?一个向量可以想象成多维空间,那么在多维空间里面找到一个点来代表这个词,相当于把这个词嵌入到了多维空间里,所以可以称为词嵌入模型。
    one-hot编码形式
    输入:
    apple on a apple tree – Bag of Words: ["apple", "on", "a", "tree"]– Word Embedding的输出就是每个word的向量表示
    最简单直接的是one-hot编码形式:那么每个word都对应了一种数值表示
    例如,apple对应的vector就是[1, 0, 0, 0],a对应的vector就是[0, 0, 1, 0]
    两类表达方式:基于频率:(本质:one-hot)
    Count vector:需要穷举所有单词,形成非常庞大、稀疏的矩阵,穷举时,计算每词的词频TF
    每个文档用词向量的组合来表示,每个词的权重用其出现的次数来表示
    假设语料库内容如下:
    – D1: He is a boy. – D2: She is a girl, good girl.那么可以构建如下2 × 7维的矩阵

    tfidf vector:同时考虑了TF与IDF
    IDF=log(N/n)。 – N代表语料库中文档的总数 – n代表某个word在几个文档中出现过;
    Co-Occurrence vector:只考虑滑动窗口内单词的共现,等于考虑了上下文之间的关系
    前面两类方法,每个字都是独立的,缺少了语义的学习
    例如: He is not lazy. He is intelligent. He is smart.
    如果Context Window大小为2,那么可以得到如下的共现矩阵:

    he和is计算方法(窗口共现):

    基于模型:
    CBOW
    Skip-Gram
    技术升级TF-IDF-》BM25
    Co-Occurrence-》WordtoVector
    BM25:定位:搜索引擎相关性评分
    通常我们在搜索信息时,搜索的句子为query,关联出的排序列表为item,即:
    query -》item
    那么可分词query-》token1 token2 token3
    同时可把item -》doc-》token token token
    词在文章中的评分:token1 -》doc :score1(tfidf)
    所以相关性评分query-》item:score1+score2+…
    公式可表示为:
    S(q,d)=∑Wi*R(qi,d)Wi用idf表示:

    N为索引中的全部文档数
    n(qi)为包含了qi的文档数
    相关性评分R:


    k1,k2,b为调节因子,一般k1=2,b=0.75
    b是调整文档长度对相关性影响的大小 • b越大,文档长度影响R越大,反之越小


    fi为qi在d中的出现频率 =TF
    qfi为qi在Query中的出现频率 =query中的TF

    在之前的tfidf中TF越大最后的分数也越大,而通常情况下,文章越长,TF大的可能性越大,没有考虑到文章长度的问题,这里BM25考虑到了这个问题,如果文章过长就要给定一定的打压,那么如何界定文章长度呢?除以avgdl,即所有文章平均长度

    dl为文档d的长度
    avgdl为所有文档的平均长度

    公式简化:
    绝大部分情况下,qi在Query中只会出现一次,即qfi=1


    BM25实践:
    1.gensim word2vec
    语料库-》每个词的50维向量即word embedding
    from gensim.models import word2vecmodel=word2vec.Word2Vec(sentences,size=50,window=5,min_count=1,workers=6)model.wv.save_word2vec_format(file_voc, binary=False)2.coumpute_idf
    每个词的idf
    file_corpus='../data/file_corpus.txt'file_voc='../data/voc.txt'file_idf='../data/idf.txt'class ComIdf(object): def __init__(self,file_corpus,file_voc,file_idf): self.file_corpus=file_corpus self.file_voc=file_voc self.file_idf=file_idf self.voc=load_voc(self.file_voc) self.corpus_data=self.load_corpus() self.N=len(self.corpus_data) def load_corpus(self): input_data = codecs.open(self.file_corpus, 'r', encoding='utf-8') return input_data.readlines() def com_idf(self,word): n = 0 for _,line in enumerate(self.corpus_data): n+=line.count(word) idf=math.log(1.0*self.N/n+1) return {word:idf} def parts(self): words=set(self.voc.keys()) multiprocessing.freeze_support() cores=multiprocessing.cpu_count() pool=multiprocessing.Pool(processes=cores-2) reuslt=pool.map(self.com_idf,words) idf_dict=dict() for r in reuslt: k=list(r.keys())[0] v=list(r.values())[0] idf_dict[k]=idf_dict.get(k,0)+v with codecs.open(self.file_idf,'w',encoding='utf-8') as f:f.write(json.dumps(idf_dict,ensure_ascii=False,indent=2,sort_keys=False))if __name__ == '__main__': t1 = time.time() IDF=ComIdf(file_corpus,file_voc,file_idf)IDF.parts()3.get_sentence
    分割句子,取出最常见句子1w个
    def get_sentence(): file_corpus=codecs.open('../data/file_corpus.txt','r',encoding='utf-8') file_sentence=codecs.open('../data/file_sentence.txt','w',encoding='utf-8') st=dict() for _,line in enumerate(file_corpus): line=line.strip() blocks=re_han.split(line) for blk in blocks: if re_han.match(blk) and len(blk)>10: st[blk]=st.get(blk,0)+1 st=sorted(st.items(),key=lambda x:x[1],reverse=True) for s in st[:10000]: file_sentence.write(s[0]+'\n') file_corpus.close() file_sentence.close()get_sentence()4.test
    各种算法计算打分:cos\idf\bm25\jaccard
    file_voc='./data/voc.txt'file_idf='./data/idf.txt'file_userdict='./data/medfw.txt'class SSIM(object): def __init__(self): t1 = time.time() self.voc=load_voc(file_voc) print("Loading word2vec vector cost %.3f seconds...\n" % (time.time() - t1)) t1 = time.time() self.idf=load_idf(file_idf) print("Loading idf data cost %.3f seconds...\n" % (time.time() - t1)) jieba.load_userdict(file_userdict) def M_cosine(self,s1,s2): s1_list=jieba.lcut(s1) s2_list=jieba.lcut(s2) v1=np.array([self.voc[s] for s in s1_list if s in self.voc]) v2=np.array([self.voc[s] for s in s2_list if s in self.voc]) v1=v1.sum(axis=0) v2=v2.sum(axis=0) sim=1-spatial.distance.cosine(v1,v2) return sim def M_idf(self,s1, s2): v1, v2 = [], [] s1_list = jieba.lcut(s1) s2_list = jieba.lcut(s2) for s in s1_list: idf_v = self.idf.get(s, 1) if s in self.voc: v1.append(1.0 * idf_v * self.voc[s]) for s in s2_list: idf_v = self.idf.get(s, 1) if s in self.voc: v2.append(1.0 * idf_v * self.voc[s]) v1 = np.array(v1).sum(axis=0) v2 = np.array(v2).sum(axis=0) sim = 1 - spatial.distance.cosine(v1, v2) return sim def M_bm25(self,s1, s2, s_avg=10, k1=2.0, b=0.75): bm25 = 0 s1_list = jieba.lcut(s1) for w in s1_list: idf_s = self.idf.get(w, 1) bm25_ra = s2.count(w) * (k1 + 1) bm25_rb = s2.count(w) + k1 * (1 - b + b * len(s2) / s_avg) bm25 += idf_s * (bm25_ra / bm25_rb) return bm25 def M_jaccard(self,s1, s2): s1 = set(s1) s2 = set(s2) ret1 = s1.intersection(s2) ret2 = s1.union(s2) jaccard = 1.0 * len(ret1)/ len(ret2) return jaccard def ssim(self,s1,s2,model='cosine'): if model=='idf': f_ssim=self.M_idf elif model=='bm25': f_ssim=self.M_bm25 elif model=='jaccard': f_ssim=self.M_jaccard else: f_ssim = self.M_cosine sim=f_ssim(s1,s2) return simsm=SSIM()ssim=sm.ssimdef test(): test_data=[u'临床表现及实验室检查即可做出诊断', u'面条汤等容易消化吸收的食物为佳', u'每天应该摄入足够的维生素A', u'视患者情况逐渐恢复日常活动', u'术前1天开始预防性运用广谱抗生素'] model_list=['cosine','idf','bm25','jaccard'] file_sentence=codecs.open('./data/file_sentence.txt','r',encoding='utf-8') train_data=file_sentence.readlines() for model in model_list: t1 = time.time() dataset=dict() result=dict() for s1 in test_data: dataset[s1]=dict() for s2 in train_data: s2=s2.strip() if s1!=s2: sim=similarity.ssim(s1,s2,model=model) dataset[s1][s2]=dataset[s1].get(s2,0)+sim for r in dataset: top=sorted(dataset[r].items(),key=lambda x:x[1],reverse=True) result[r]=top[0] with codecs.open('./data/test_result.txt','a') as f: f.write('--------------The result of %s method------------------\n '%model) f.write('\tThe computing cost %.3f seconds\n'% (time.time() - t1)) f.write(json.dumps(result, ensure_ascii=True, indent=2, sort_keys=False)) f.write('\n\n') file_sentence.close()test()word2vec继承了之前的窗口滑动思想,得到更好的语义理解
    涉及的技术点:
    – Hierarchical softmax分层softmax
    – Negative sampling负采样
    两种方式:

    CBOW:根据前后词,预测中间词
    Skip-Gram :根据中间词预测前后词,工业用的更多

    CBOW一句话包含了很多单词,时间窗口选择到了一个中间词,w3,假设左边右边各学习两个,中间词假设不知道,那么根据w1245猜测中间这个w3词,故意装作w3不知道做预测,那么w3就是中心词label,w1245就是周围词训练数据,随着时间窗口滑动,同理w4又继续成为了中间词,那么由此类推形成了很多训练样本


    Input layer:由one-hot编码的输入上下文{x1,…,xC}组成, 其中窗口大小为C,词汇表大小为V
    Hidden layer:隐藏层是N维的向量
    Output layer:被one-hot编码的输出单词y

    被one-hot编码的输入向量通过一个V×N维的权重矩阵W连接到隐藏层; 隐藏层通过一个N×V的权重矩阵W′连接到输出层
    不管输入多少词,相加并都映射为中间得隐层向量上,再做一个softmax输出
    Skip-Gram:CBOW的网络翻转
    样本怎么得到的?

    input word和output word都是one-hot编码的向量。最终模型的输出是一个概率分布

    softmax分类需要所有单词:这里是50002个单词,需要遍历一遍,那么每次计算都需要一定时间,不管是多次还是一次时间成本都很高,所以引出了分层softmax:
    Hierarchical softmax哈夫曼树

    是二叉树的一种特殊形式,又称为最优二叉树,其主要作用在于数据压缩和编码长度的优化
    定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度(WPL)达到最小,称这样的二叉 树为最优二叉树,也称为霍夫曼树(Huffman Tree)
    WPL:树的带权路径长度,所有叶子结点的带权路径长度之和

    让wpl最小,压缩数据信息
    主要用于编码:从根节点出发,向左为0,向右为1
    等长编码和哈夫曼编码


    生成:
    每个节点按权重大小从小到大排序
    两个最小的为叶子节点相加成为父节点并和其他最小的成两个叶子节点,最终形成哈夫曼树
    之前做softmax,50002个单词需要从头到尾计算一遍,把词表做成树,每个叶子节点都是一个单词,树的每个结点都是一个sigmoid,来了一个单词做一个lr二分类向左还是向右分类直至最后叶子节点为所要的词
    Negative sampling负采样
    思想:每次让一个训练样本仅更新一小部分权重
    需要离错误的样本更远

    不对所有输出神经元对应的权值进行更新,只是随机选取几个“negative”词,更新他们对应的权重。当然, 我们也会更新”positive”的对应权值
    随机取的样本只要不共现就是负样本,概率大的会多选,即出现多的单词自然被取出的概率越大
    实际论文实现:


    CBOW:input是context(周围词)而output是中心词,训练过程中其实是在从output的loss学习周围词的信息 也就是embedding,但是在中间层是average的,一共预测V(vocab size)次就够了
    一次softmax

    Skipgram:用中心词预测周围词,预测的时候是一对word pair,等于对每一个中心词都有K个词作为output, 对于一个词的预测有K次,所以能够更有效的从context中学习信息,但是总共预测K*V词
    多次softmax

    Skip-Gram的训练时间更长,更准确
    Cbow训练速度快,Skip-Gram更好处理生僻字

    Word2Vec实践:
    import sysimport torchimport torch.nn as nnimport torch.nn.functional as Fimport torch.utils.data as tudfrom torch.nn.parameter import Parameterfrom collections import Counterimport numpy as npimport randomimport mathimport pandas as pdimport scipyimport sklearnfrom sklearn.metrics.pairwise import cosine_similarity# 超参数K = 100 # number of negative samplesC = 3 # nearby words thresholdNUM_EPOCHS = 2 # The number of epochs of trainingMAX_VOCAB_SIZE = 30000 # the vocabulary sizeBATCH_SIZE = 128 # the batch sizeLEARNING_RATE = 0.2 # the initial learning rateEMBEDDING_SIZE = 100# 分词def word_tokenize(text): return text.split()with open("./data/text8", "r") as fin: text = fin.read()text = [w for w in word_tokenize(text.lower())]print(text[1])vocab = dict(Counter(text).most_common(MAX_VOCAB_SIZE - 1))#计数器,取前30000个高频元素vocab["<unk>"] = len(text) - np.sum(list(vocab.values()))print (np.sum(list(vocab.values())))print (len(text))print (vocab["<unk>"])print (len(vocab))#output:originated170052071700520769010330000idx_to_word = [word for word in vocab.keys()]word_to_idx = {word: i for i, word in enumerate(idx_to_word)}word_counts = np.array([count for count in vocab.values()], dtype=np.float32)word_freqs = word_counts / np.sum(word_counts)word_freqs = word_freqs ** (3. / 4.)word_freqs = word_freqs / np.sum(word_freqs) # 用来做 negative samplingVOCAB_SIZE = len(idx_to_word)print(VOCAB_SIZE)#text 每个单词#word_to_idx 单词id化:dict#idx_to_word 每个单词#word_freqs 负采样概率#word_counts 单词计数列表#数据样本列举:class WordEmbeddingDataset(tud.Dataset): def __init__(self, text, word_to_idx, idx_to_word, word_freqs, word_counts): ''' text: a list of words, all text from the training dataset word_to_idx: the dictionary from word to idx idx_to_word: idx to word mapping word_freq: the frequency of each word word_counts: the word counts ''' super(WordEmbeddingDataset, self).__init__() self.text_encoded = [word_to_idx.get(t, VOCAB_SIZE - 1) for t in text] self.text_encoded = torch.Tensor(self.text_encoded).long() self.word_to_idx = word_to_idx self.idx_to_word = idx_to_word self.word_freqs = torch.Tensor(word_freqs) self.word_counts = torch.Tensor(word_counts) def __len__(self): ''' 返回整个数据集(所有单词)的长度 ''' return len(self.text_encoded) def __getitem__(self, idx): ''' 这个function返回以下数据用于训练 - 中心词 - 这个单词附近的(positive)单词 - 随机采样的K个单词作为negative sample ''' center_word = self.text_encoded[idx] pos_indices = list(range(idx - C, idx)) + list(range(idx + 1, idx + C + 1)#窗口左3右3 pos_indices = [i % len(self.text_encoded) for i in pos_indices]#去除类似第一次左边无词这种情况 pos_words = self.text_encoded[pos_indices] neg_words = torch.multinomial(self.word_freqs, K * pos_words.shape[0], True) return center_word, pos_words, neg_wordsdataset = WordEmbeddingDataset(text, word_to_idx, idx_to_word, word_freqs, word_counts)dataloader = tud.DataLoader(dataset, batch_size=BATCH_SIZE, shuffle=True, num_workers=4)
    class EmbeddingModel(nn.Module): def __init__(self, vocab_size, embed_size): ''' 初始化输出和输出embedding ''' super(EmbeddingModel, self).__init__() self.vocab_size = vocab_size self.embed_size = embed_size initrange = 0.5 / self.embed_size self.out_embed = nn.Embedding(self.vocab_size, self.embed_size, sparse=False) self.out_embed.weight.data.uniform_(-initrange, initrange) self.in_embed = nn.Embedding(self.vocab_size, self.embed_size, sparse=False) self.in_embed.weight.data.uniform_(-initrange, initrange) def forward(self, input_labels, pos_labels, neg_labels): ''' input_labels: 中心词, [batch_size] pos_labels: 中心词周围 context window 出现过的单词 [batch_size * (window_size * 2)] neg_labelss: 中心词周围没有出现过的单词,从 negative sampling 得到 [batch_size, (window_size * 2 * K)] return: loss ''' input_embedding = self.in_embed(input_labels) # B * embed_size pos_embedding = self.out_embed(pos_labels) # B * (2*C) * embed_size neg_embedding = self.out_embed(neg_labels) # B * (2*C * K) * embed_size print("input_embedding size:", input_embedding.size()) print("pos_embedding size:", pos_embedding.size()) print("neg_embedding size:", neg_embedding.size()) log_pos = torch.bmm(pos_embedding, input_embedding.unsqueeze(2)).squeeze() # B * (2*C) log_neg = torch.bmm(neg_embedding, -input_embedding.unsqueeze(2)).squeeze() # B * (2*C*K)先拓展再压缩 print("log_pos size:", log_pos.size()) print("log_neg size:", log_neg.size()) log_pos = F.logsigmoid(log_pos).sum(1)#1为横向压缩,2为竖向压缩,可以试试玩 log_neg = F.logsigmoid(log_neg).sum(1) loss = log_pos + log_neg print("log_pos size:", log_pos.size()) print("log_neg size:", log_neg.size()) print("loss size:", loss.size()) return -loss def input_embeddings(self): return self.in_embed.weight.data.cpu().numpy()model = EmbeddingModel(VOCAB_SIZE, EMBEDDING_SIZE)if USE_CUDA: model = model.cuda()if __name__ == '__main__': optimizer = torch.optim.SGD(model.parameters(), lr=LEARNING_RATE) for e in range(NUM_EPOCHS): for i, (input_labels, pos_labels, neg_labels) in enumerate(dataloader): print(input_labels.size()) print(pos_labels.size()) print(neg_labels.size()) input_labels = input_labels.long() pos_labels = pos_labels.long() neg_labels = neg_labels.long() if USE_CUDA: input_labels = input_labels.cuda() pos_labels = pos_labels.cuda() neg_labels = neg_labels.cuda() optimizer.zero_grad() loss = model(input_labels, pos_labels, neg_labels).mean() loss.backward() optimizer.step() if i % 100 == 0: with open(LOG_FILE, "a") as fout: fout.write("epoch: {}, iter: {}, loss: {}\n".format(e, i, loss.item())) print("epoch: {}, iter: {}, loss: {}".format(e, i, loss.item())) embedding_weights = model.input_embeddings() torch.save(model.state_dict(), "embedding-{}.th".format(EMBEDDING_SIZE))使用场景:
    1.item title检索 +ANN+word avg,word average: – 对所有输入词向量求和并取平均 – 例如:输入三个4维词向量:(1,2,3,4),(9,6,11,8),(5,10,7,12) – 那么我们word2vec映射后的词向量就是(5,6,7,8)
    2.模型初始化:处理特征等
    3.近义词(语义理解):可通过计算词向量的加减,与相似度可进行语义理解
    实践例:
    def evaluate(filename, embedding_weights): if filename.endswith(".csv"): data = pd.read_csv(filename, sep=",") else: data = pd.read_csv(filename, sep="\t") human_similarity = [] model_similarity = [] for i in data.iloc[:, 0:2].index: word1, word2 = data.iloc[i, 0], data.iloc[i, 1] if word1 not in word_to_idx or word2 not in word_to_idx: continue else: word1_idx, word2_idx = word_to_idx[word1], word_to_idx[word2] word1_embed, word2_embed = embedding_weights[[word1_idx]], embedding_weights[[word2_idx]] model_similarity.append(float(sklearn.metrics.pairwise.cosine_similarity(word1_embed, word2_embed))) human_similarity.append(float(data.iloc[i, 2])) return scipy.stats.spearmanr(human_similarity, model_similarity)# , model_similaritydef find_nearest(word): index = word_to_idx[word] embedding = embedding_weights[index] cos_dis = np.array([scipy.spatial.distance.cosine(e, embedding) for e in embedding_weights])#1-cosine return [idx_to_word[i] for i in cos_dis.argsort()[:10]]model.load_state_dict(torch.load("model/embedding-{}.th".format(EMBEDDING_SIZE), map_location='cpu'))embedding_weights = model.input_embeddings()# 找相似的单词for word in ["good", "computer", "china", "mobile", "study"]: print(word, find_nearest(word))# 单词之间的关系,寻找nearest neighborsman_idx = word_to_idx["man"]king_idx = word_to_idx["king"]woman_idx = word_to_idx["woman"]embedding = embedding_weights[woman_idx] - embedding_weights[man_idx] + embedding_weights[king_idx]cos_dis = np.array([scipy.spatial.distance.cosine(e, embedding) for e in embedding_weights])for i in cos_dis.argsort()[:20]: print(idx_to_word[i])
    0 留言 2019-06-23 14:57:53 奖励13点积分
  • 深度学习 19、DNN

    前文链接:https://write-bug.com/article/2540.html
    深度学习在前几节介绍的模型都属于单点学习模型,比如朴素贝叶斯的模型为概率,lr与softmax的模型为w,b权重,聚类kmeans的模型为中心向量点,还有后面的决策树的树模型等等都属于单点学习模型,都有各自的用途,而这里的深度学习来说,属于机器学习的一部分,可用不同的网络结构来解决各个领域的问题,模型为深度学习网络。
    通过前几节的学习,不知道大家有没有对单点学习的模型有感触,所谓模型是什么?
    我们从已有的例子(训练集)中发现输入x与输出y的关系,这个过程是学习(即通过有限的例子发现输入与输出之间的关系),而我们使用的function就是我们的模型,通过模型预测我们从未见过的未知信息得到输出y,通过激活函数(常见:relu,sigmoid,tanh,swish等)对输出y做非线性变换,压缩值域,而输出y与真实label的差距就是误差error,通过损失函数再求取参数偏导,梯度下降降低误差,从而优化模型,我们前面见过的损失函数是mse和交叉熵

    而DNN的模型就是网络结构,在说如何选取更好的网络结构之前,我们先介绍下神经网络:

    人类大脑的神经网络如上图具象出来就是无数个神经元,而神经元分为几个结构:

    树突:接收信号源
    神经元:核心计算单元
    轴突:传输数据到下一个神经元

    通过一个个神经元的传输,生成结果,比如说条件反射:缩手
    而在我们模型中,这个网络怎么表示呢?

    感知机:最最简单的神经网络,只有一个神经元


    树突:样本特征a1
    轴突:权重w1

    树突与轴突,也就是样本特征和权重相乘,有些类似lr的wx,共同决策了神经元的输入

    神经元:对信号进一步处理,比如lr中wx的∑,并加入偏置b,默认为1
    传递函数(激活函数):对f(s)做压缩非线性变换

    假设一个二分类问题:

    输入:
    树突P1:颜色
    树突P2:形状
    香蕉(黄色,弯形):(-1,-1)
    苹果(红色,圆形):(1,1)

    相当于坐标轴的两个点,我们需要一个分类面把两个点分割开。

    P1颜色的取值为1,-1
    P2形状的取值为1,-1
    初始化w1=w2=1,b=0

    则有:
    s=p1w1+p2w2=2>0s=p2 2w2 2+p2 2w2 2=-2 < 0这个初始化的参数可以区分,但是初始化有随机性,换一组参数就不能区分了
    所以感知机的训练方法,目的就是训练权重和偏置
    w=w+epb=b+ee(误差)=t-a=期望-实际
    如,假设w1=1,w2=-1,b=0

    苹果s=0
    期望为1,e=1-0=1

    修正:
    w1=1+1*1=2w2=-1+1*1=0b=0+1=1s=3>0为苹果但是,y=wx+b只能解决线性可分的问题,对于异或问题,也就是四点对立面,需要一个曲线做分割,而这就意味着需要多层神经元和信号源共同决策分割面,也就形成了复杂的神经网络,而目标:同样是那么多边的权重。

    通过不同层间的结果作为下一层的输入,再对输入中间结果进一步处理,以此类推形成足够的深度,对于大部分问题来说都可以提到一个提升效果的作用。
    感知机只有从输出层具有激活函数,即功能神经元,这里的隐层和输出层都是具有激活函数的功能神经元。
    层与层全连接,同层神经元不连接,不跨层连接的网络又称为多层前馈神经网络。
    前馈:网络拓扑结构上不存在环和回路
    我们通过pytorch实现演示:
    二分类问题:
    假数据准备:
    # make fake data#正态分布随机产生n_data = torch.ones(100, 2)x0 = torch.normal(2*n_data, 1) # class0 x data (tensor), shape=(100, 2)y0 = torch.zeros(100) # class0 y data (tensor), shape=(100, 1)x1 = torch.normal(-2*n_data, 1) # class1 x data (tensor), shape=(100, 2)y1 = torch.ones(100) # class1 y data (tensor), shape=(100, 1)#拼接数据x = torch.cat((x0, x1), 0).type(torch.FloatTensor) # shape (200, 2) FloatTensor = 32-bit floatingy = torch.cat((y0, y1), ).type(torch.LongTensor) # shape (200,) LongTensor = 64-bit integer# tensor类型 :张量:高维特征,不可更新#variable类型:可变参数,更新w,b从而更新xy# torch can only train on Variable, so convert them to Variablex, y = Variable(x), Variable(y)设计构建神经网络:class net 继承torch.nn.model
    200\*2, 2\*10, 10\*2参数:n_fea=2,n_hidden=10,n_output=2
    输入层2
    初始化hidden层10
    self.hidden=torch.nn.linear(n_fea,n_hidden)输出层2
    self.out=torch.nn.linear(n_hidden,n_output)class Net(torch.nn.Module): def __init__(self, n_feature, n_hidden, n_output): super(Net, self).__init__() self.hidden = torch.nn.Linear(n_feature, n_hidden) # hidden layer self.out = torch.nn.Linear(n_hidden, n_output) # output layer#激活函数,在隐藏层后加relu非线性变换 def forward(self, x): x = F.relu(self.hidden(x)) # activation function for hidden layer x = self.out(x) return x #输出的预测值xnet = Net(n_feature=2, n_hidden=10, n_output=2) # define the networkprint(net)参数梯度下降sgd:
    optimizer = torch.optim.sgd(net.parameters(),lr=0.02)损失函数:交叉熵:负对数似然函数,并计算softmax
    loss_func = torch.nn.CrossEntropyLoss()参数初始化:
    optimizer.zero_grad()反向传播:
    loss.backward()计算梯度:
    optimizer.step()for t in range(100): out = net(x) # input x and predict based on x loss = loss_func(out, y) # must be (1. nn output, 2. target), the target label is NOT one-hotted optimizer.zero_grad() # clear gradients for next train loss.backward() # backpropagation, compute gradients optimizer.step() # apply gradients if t % 2 == 0: # plot and show learning process plt.cla() prediction = torch.max(F.softmax(out), 1)[1] pred_y = prediction.data.numpy().squeeze() target_y = y.data.numpy() plt.scatter(x.data.numpy()[:, 0], x.data.numpy()[:, 1], c=pred_y, s=100, lw=0, cmap='RdYlGn') accuracy = sum(pred_y == target_y)/200. plt.text(1.5, -4, 'Accuracy=%.2f' % accuracy, fontdict={'size': 20, 'color': 'red'}) plt.pause(0.1)plt.ioff()plt.show()交叉熵问题:
    二次代价:

    a 是 神经元的输出,其中 a = σ(z), z = wx + b
    C求导:w,b求偏导:
    受到激活函数影响

    交叉熵函数:


    不用对激活函数导数影响,不管是对w求偏导还是对b求偏导,都和e有关,而和激活函数的导数无关,比如说sigmoid函数,只有中间下降最快,两边的下降逐渐缓慢,最后斜率逼近于直线
    反向传播算法:errorBP
    可应用于大部分类型神经网络
    一般说BP算法时,多指多层前馈神经网络
    上面的数据为了演示,造的假数据形成200*2维的矩阵,一列label
    那么如何对接我们的真实数据呢?

    在我们前几节的数据中大都是这种形式,label feature_id:score
    定义一个数组
    output =[None]*3 维护3列tensor数据:
    max_fid = 123num_epochs = 10data_path = '/root/7_codes/pytorch_test/data/a8a'all_sample_size = 0sample_buffer = []with open(data_path, 'r') as fd: for line in fd: all_sample_size += 1 sample_buffer.append(line.strip())output = [None] *3#idids_buffer = torch.LongTensor(all_sample_size, max_fid)ids_buffer.fill_(1)output[0] = ids_buffer#weightweights_buffer = torch.zeros(all_sample_size, max_fid)output[1] = weights_buffer#labellabel_buffer = torch.LongTensor(all_sample_size)output[2] = label_bufferrandom.shuffle(sample_buffer)sample_id = 0for line in sample_buffer: it = line.strip().split(' ') label = int(it[0]) f_id = [] f_w = [] for f_s in it[1:]: f, s = f_s.strip().split(":") f_id.append(int(f)) f_w.append(float(s)) #解析数据后填入数组 f_id_len = len(f_id)#适当拓展数组大小 output[0][sample_id, 0:f_id_len] = torch.LongTensor(f_id) output[1][sample_id, 0:f_id_len] = torch.FloatTensor(f_w) output[2][sample_id] = label sample_id += 1fid, fweight, label = tuple(output)fid, fweight, label = map(Variable, [fid, fweight, label])接下来是设计网络结构:

    def emb_sum(embeds, weights): emb_sum = (embeds * weights.unsqueeze(2).expand_as(embeds)).sum(1) return emb_sum#输入结构为22696条数据*124维特征*32维特征向量:可以将其想象成立方体的三维条边#想要把id的特征向量和对应的score相乘并相加,需要把score也就是权重weight拓展成和id同样的维度,即22696 *124 *32 ,而sum(1)就是把124维相加成1维,最后形成22696×32维的平面矩阵,即每个样本后有个32维的向量存在,相当于把feature_id向量化class Net(torch.nn.Module): def __init__(self, n_embed, n_feature, n_hidden, n_output): super(Net, self).__init__() self.embedding = nn.Embedding(max_fid + 1, n_feature) #124特征*32隐层向量 self.hidden = torch.nn.Linear(n_feature, n_hidden) # hidden layer self.out = torch.nn.Linear(n_hidden, n_output) # output layer def forward(self, fea_ids, fea_weights): embeds = self.embedding(fea_ids) embeds = emb_sum(embeds, fea_weights)#对特征进一步处理,融合id与weight_score进行相容 embeds = nn.functional.tanh(embeds)#非线性变换 hidden = self.hidden(embeds) output = self.out(hidden) return outputnet = Net(n_embed = 32, n_feature= 32, n_hidden=10, n_output=2) # define the networkprint(net)以上,我们对接了真实的数据类型,那这个demo有没有什么问题呢?
    1.是否支持大规模数据,进行快速训练?mini-batch
    我们之前学BGD、SGD、MGD梯度下降的训练方法,在上面就运用了sgd的方法,不管是BGD还是SGD都是对所有样本一次性遍历一次,如果想提升,大致相当于MGD的方法:
    把所有样本分批处理,每批次有多少个样本(batch),循环所有样本循环多少轮(epoch)。
    每训练一个batch产生一条log,参数可保存,之前是每epoch输出一次log,这种方法训练快,性能虽然赶不上全局跑出来的准确率,但仍然一直逼近,小步快跑,每次加载到内存的数据较小,性能方面就高。
    num_epochs=10batch_size =1000data_path = './data/a8a'max_fid = 123def read_and_shuffle(filepath,shuffle=True): lines=[] with open(filepath,’r’) as fd: for linr in fd: lines.append(line.strip()) if shuffle: random.shuffle(lines) return linesclass DataLoader(object): def __init__(self,data_path,batch_size,shuffle = True): self.batch_size = batch_size self.shuffle = shuffle if os.path.isdir(data_path): self.files = [ join_path(data_path,i) for I in os.listdir(data_path)] else: self.files = [data_path] def parse(self,line_ite): for line in line_ite: it = line.strip().split(‘ ’) label = int(it[0]) f_id = [] f_w = [] for f_s in it[1:]: f,s = f_s.strip().split(‘:’) f_id.append(int(f)) f_w.append(float(s)) f_id_len = len(f_id) output = [] output.append(f_id) output.append(f_w) output.append(f_id_len) output.append(label) yield output def to_tensor(self,batch_data,sample_size): output =[None]*3 ids_buffer = torch.LongTensor(sample_size,max_fid) ids_buffer.fill_(1) output[0]=ids_buffer weights_buffer = torch.zeros(sample_size,max_fid) output[1]=weights_buffer label_buffer = torch.LongTensor(sample_size) output[2] = label_buffer for sample_id,sample in enumerate(batch_data): f_id,f_weight,f_id_len,label = sample output[0][sample_id,0:f_id_len] = torch.LongTensor(f_id) output[1][sample_id,0:f_id_len] = torch.FloatTensor(f_w) output[2][sample_id] = label return tuple(output) def batch(self): count = 0 batch_buffer =[] for f in self.files: for parse_res in self.parse(read_and_shuffle(f,self.shuffle)): count+=1 batch_buffer.append(parse_res) if count ==self.batch_size: t_size = len(batch_buffer) batch_tensor = self.to_tensor(batch_buffer,t_size) yield (batch_tensor,t_size) count = 0 batch_buffer = [] if batch_buffer: t_size = len(batch_buffer) batch_tensor = self.to_tensor(batch_buffer,t_size) yield (batch_tensor,t_size)for epoch in range(1,num_epochs+1): for (batch_id,data_tuple) in enumrate(dataloader.batch(),1): data = data_tuple[0] all_sample_size = data_tuple[1] fid,fweight,label =data fid,fweight,label=map(Variable,[fid,fweight,label] optimizer = torch.optim.SGD(net.parameters(), lr=0.02) loss_func = torch.nn.CrossEntropyLoss() # the target label is NOT an one-hotted out = net(fid, fweight) optimizer.zero_grad() # clear gradients for next train loss = loss_func(out, label) loss.backward() # backpropagation, compute gradients optimizer.step() # apply gradients if batch_id % 2 == 0:#每两批次打印一次 # plot and show learning process prediction = torch.max(F.softmax(out), 1)[1] pred_y = prediction.data.numpy().squeeze() target_y = label.data.numpy() accuracy = sum(pred_y == target_y)/float(all_sample_size) print "epoch: %s, batch_id: %s, acc: %s" % (epoch, batch_id, accuracy)2.怎么使用模型?
    现在模型可以训练自己数据了,效果也提升了,那如何把模型的参数保存下来?
    print "epoch: %s, batch_id: %s, acc: %s" % (epoch, batch_id, accuracy) checkpoint = { 'model': net.state_dict(),#网络静态参数 'epoch': epoch, 'batch': batch_id, } model_name = 'epoch_%s_batch_id_%s_acc_%s.chkpt' % (epoch, batch_id, accuracy) model_path = join_path('./model', model_name) torch.save(checkpoint, model_path)拆分上面大文件出各个参数:

    import osimport sysimport torchimport torch.nn as nnimport randomfrom torch.autograd import Variablefrom os.path import join as join_pathimport torch.nn.functional as Fmodel_path = sys.argv[1]checkpoint = torch.load(model_path)model_dict = checkpoint['model']for k, v in model_dict.items(): print k model_sub_file_name = k model_sub_file_path = join_path('./dump', model_sub_file_name) f = open(model_sub_file_path, 'w') value = model_dict[k].cpu().numpy() value.dump(f) f.close()模型怎么用?加载、预测
    import sysimport numpy as npimport mathembedding_weight = np.load('dump/embedding.weight')hidden_weight = np.load('./dump/hidden.weight')hidden_bias = np.load('./dump/hidden.bias')out_weight = np.load('./dump/out.weight')out_bias = np.load('./dump/out.bias')emb_dim = embedding_weight.shape[1]def calc_score(fids, fweights): embedding = np.zeros(emb_dim) for id, weight in zip(fids, fweights): embedding += weight * embedding_weight[id] embedding_tanh = np.tanh(embedding)#对应相乘,第二维相加成10维向量 hidden = np.sum(np.multiply(hidden_weight, embedding_tanh), axis=1) + hidden_bias out = np.sum(np.multiply(out_weight, hidden), axis=1) + out_bias return outdef softmax(x): exp_x = np.exp(x) softmax_x = exp_x / np.sum(exp_x) return softmax_xfor line in sys.stdin: ss = line.strip().split(' ') label = ss[0].strip() fids = [] fweights = [] for f_s in ss[1:]: f, s = f_s.strip().split(':') fids.append(int(f)) fweights.append(float(s)) pred_label = softmax(calc_score(fids, fweights))[1] print label, pred_label3.怎么评估?auc
    cat auc.raw | sort -t$'\t' -k2g | awk -F'\t' '($1==-1){++x;a+=y}($1==1){++y}END{print 1.0 - a/(x*y)}'acc=0.827auc=0.842569acc=0.745auc=0.494206轮数、acc都影响着auc,数字仅供参考
    总结以上,是以二分类为例,从头演示了一遍神经网络,大家可再找一些0-9手写图片分类任务体验一下,这里总结下,模型拥有参数,所以涉及参数初始化,有了参数后涉及正向传递,分为拟合和泛化两部分建立好模型后,学习过程就是确定参数的过程,使用的是梯度下降法,定义一个误差函数loss function 来衡量模型预测值与真实值(label)之间的差距,通过不断降低差距来使模型预测值逼近真实值,更新参数的反向传递是利用对应的误差值来求得梯度(batch、epoch、learning rate 、shuffle),评估标准也根据任务类型和具体要求可以使用更多的指标。
    回归任务常用均方差MSE作为误差函数。评估可用均方差表示。
    分类任务常用交叉熵(cross entropy)和softmax配合使用。评估可用准确率表示。
    回归任务:

    借用知乎yjango末尾的一句话:
    但最重要的并非训练集的准确率,而是模型从未见过的测试集的准确率(泛化能力),正如高考,真正的目的是为了解出从未见过的高考题,而不是已经做过的练习题,学习的困难之处正是要用有限的样本训练出可以符合无限同类样本规律的模型。是有限同无限的对抗,你是否想过,为什么看了那么多的道理、听了那么多人生讲座,依然过不哈这一生,一个原因就在于演讲者向你展示的例子都是训练集的样本,他所归纳的方法可以很轻松的完美拟合这些样本,但未必对你将面临的新问题同样奏效,人的一生都在学习,都在通过观察有限的例子找出问题和答案的规律,中医是,玄学是,科学同样是,但科学,是当中最为可靠的一种。
    0 留言 2019-06-05 13:46:30 奖励18点积分
  • 深度学习 20、CNN

    前文链接:https://write-bug.com/article/2575.html
    卷积神经网络CNN上节我们介绍了DNN的基本网络结构和演示,其网络结构为:

    DNN BP神经网络实行全连接特性,参数权值过多,需求大量样本,计算困难,所以CNN利用局部连接、权值共享来实现减少权值的尝试,即局部感知野和权值共享。擅长图像分类问题,识别二维图形,现在也可以用于文本处理。

    CNN的隐藏层分为卷积层conv、和池化层pool,一般CNN结构(LeNet)依次为:

    INPUT->[[CONV -> RELU]N -> POOL?]M -> [FC -> RELU]*K->FC经典LeNet-5结构:最早用于数字识别的CNN


    卷积层Convolitions:
    用卷积层实现对图片局部的特征提取,窗口模式卷积核形式提取特征,映射到高维平面。
    两个关键性操作:

    局部关联:每个神经元看为一个滤波器filter
    窗口滑动:filter对局部数据计算

    局部感受野:
    1000 * 1000 图像 1000 * 1000神经元全连接: 1000 * 1000 * 1000 * 1000 = 10^12 个参数
    局部感受野:每个神经元只需要知道10 * 10区域,训练参数降到100M

    权值共享:
    所有神经元用同一套权重值,100M降到100,这样得到一个feature map。100种权重值100个map,一共需要训练100*100 = 10k参数

    卷积的计算:

    窗口滑动,我们可以想象一个窗口(卷积核feature_map),设置固定的feature_size,里面是固定的权值,这个窗口在同一张图片上从左到右从上到下游走,每次固定步长,从而得到更小size的矩阵。

    这里有两个神经元的卷积层,步长stride设置为2,边缘灰色部分为填充值zero-padding,防止窗口移到边缘时不够滑动遍历所有像素,而这里的神经元个数就是卷积层深度depth。
    在卷积层中每个神经元连接数据窗的权重是固定的,每个神经元只关注一个特性。神经元就是图像处理中的滤波器,比如边缘检测专用的Sobel滤波器,即卷积层的每个滤波器都会有自己所关注一个图像特征,比如垂直边缘,水平边缘,颜色,纹理等等,这些所有神经元加起来就好比就是整张图像的特征提取器集合。

    需要估算的权重个数减少: AlexNet 1亿 => 3.5w
    一组固定的权重和不同窗口内数据做内积: 卷积卷积理解:后面输出结果的前提是依赖前面相应权值积累,比如连续吃三天药身体才好,那么这三天的相关性是不同的权值

    激活函数把卷积层输出结果做非线性映射。CNN采用的激励函数一般为ReLU(The Rectified Linear Unit/修正线性单元),它的特点是收敛快,求梯度简单,但较脆弱,图像如下。

    激励层的实践经验:

    不要用sigmoid!不要用sigmoid!不要用sigmoid!首先试RELU,因为快,但要小心点如果2失效,请用Leaky ReLU或者Maxout某些情况下tanh倒是有不错的结果,但是很少
    池化层pooling:对特征进一步缩放
    池化层夹在连续的卷积层中间,用于压缩数据和参数的量,减小过拟合,压缩图像。
    特点:

    特征不变性:图像缩小还可以认出大概
    特征降维:去除冗余信息,防止过拟合


    池化层用的方法有Max pooling 和 average pooling,而实际用的较多的是Max pooling。
    这里就说一下Max pooling,其实思想非常简单。

    对于每个2*2的窗口选出最大的数作为输出矩阵的相应元素的值,比如输入矩阵第一个2*2窗口中最大的数是6,那么输出矩阵的第一个元素就是6,如此类推。
    平移不变性

    旋转不变性

    缩放不变性

    全连接层FC
    和BP神经网络一样,两层之间互相全连接,即把压缩后的维度打平为一组向量,再通过dnn的方法进行分类处理。
    Droupout
    正则化方法,CNN中解决过拟合问题,同时通用与其他网络。

    随机在全连接层,剪掉一些神经元,防止过拟合。
    卷积网络在本质上是一种输入到输出的映射,它能够学习大量的输入与输出之间的映射关系,而不需要任何输入和输出之间的精确的数学表达式,只要用已知的模式对卷积网络加以训练,网络就具有输入输出对之间的映射能力。
    CNN一个非常重要的特点就是头重脚轻(越往输入权值越小,越往输出权值越多),呈现出一个倒三角的形态,这就很好地避免了BP神经网络中反向传播的时候梯度损失得太快。
    卷积神经网络CNN主要用来识别位移、缩放及其他形式扭曲不变性的二维图形。由于CNN的特征检测层通过训练数据进行学习,所以在使用CNN时,避免了显式的特征抽取,而隐式地从训练数据中进行学习;再者由于同一特征映射面上的神经元权值相同,所以网络可以并行学习,这也是卷积网络相对于神经元彼此相连网络的一大优势。卷积神经网络以其局部权值共享的特殊结构在语音识别和图像处理方面有着独特的优越性,其布局更接近于实际的生物神经网络,权值共享降低了网络的复杂性,特别是多维输入向量的图像可以直接输入网络这一特点避免了特征提取和分类过程中数据重建的复杂度。
    卷积神经网络之训练算法:

    同一般机器学习算法,先定义Loss function,衡量和实际结果之间差距
    找到最小化损失函数的W和b, CNN中用的算法是SGD(随机梯度下降)

    卷积神经网络之优缺:

    优点

    共享卷积核,对高维数据处理无压力无需手动选取特征,训练好权重,即得特征分类效果好
    缺点

    需要调参,需要大样本量,训练最好要GPU物理含义不明确(也就说,我们并不知道没个卷积层到底提取到的是什么特征,而且神经网络本身就是一种难以解释的“黑箱模型”)

    卷积神经网络之典型CNN:

    LeNet,这是最早用于数字识别的CNN
    AlexNet, 2012 ILSVRC比赛远超第2名的CNN,比LeNet更深,用多层小卷积层叠加替换单大卷积层。
    ZF Net, 2013 ILSVRC比赛冠军
    GoogLeNet, 2014 ILSVRC比赛冠军
    VGGNet, 2014 ILSVRC比赛中的模型,图像识别略差于GoogLeNet,但是在很多图像转化学习问题(比如object detection)上效果奇好pytorch网络结构:

    class Net(nn.Module): def __init__(self): super(Net, self).__init__() self.conv1 = nn.Conv2d(1, 20, 5, 1) self.conv2 = nn.Conv2d(20, 50, 5, 1) self.fc1 = nn.Linear(4*4*50, 500) self.fc2 = nn.Linear(500, 10) def forward(self, x): print("x size: ", x.size()) x = F.relu(self.conv1(x)) print("conv1 size: ", x.size()) x = F.max_pool2d(x, 2, 2) print("pool size: ", x.size()) x = F.relu(self.conv2(x)) print("conv2 size: ", x.size()) x = F.max_pool2d(x, 2, 2) print("pool size: ", x.size()) x = x.view(-1, 4*4*50) print("view size: ", x.size()) x = F.relu(self.fc1(x)) print("fc1 size: ", x.size()) x = self.fc2(x) print("fc2 size: ", x.size()) sys.exit() return F.log_softmax(x, dim=1)
    0 留言 2019-06-11 11:42:43 奖励13点积分
  • 深度学习 21、RNN

    前文链接:https://write-bug.com/article/2644.html
    RNN循环神经网络
    RNN(循环神经网络):一类用于处理序列(时间、空间)数据的神经网络,RNN可用于分类、回归、机器翻译、文本相似度
    隐层的神经元不仅接收输入层的或者上一层的信息流,还要接受上一时刻的同层神经元的信息流,即隐层之间的连接,连接传递的权重就是记忆能力。
    此处的记忆能力理解为人的认知往往基于过往的经验与记忆,所以模拟时,同样根据激活函数的不同会产生梯度消失和梯度爆炸问题,也反映了人的记忆往往有限,过往太久的事不会记忆或者对现在产生影响过大。
    梯度消失:每次loss反向传播时,如果使用sigmoid这样的激活函数一直乘一个小数,在这个过程中一直变小,直到逼近于0梯度爆炸:每次loss反向传播时,如果使用relu这样的激活函数,x>0时,y=x,一直乘一个大于0的数,数值过大
    所以,他的优点就是在上下文推断时,可以根据上文推断下一个出现概率最大的单词,适合短期记忆,不适合长期记忆,很难学习长距离信息,那么同样的,比较符合大脑记忆曲线

    隐层展开后为上图样式。

    t-1, t, t+1表示时间序列
    X表示输入的样本
    St表示样本在时间t处的的记忆,St = f(WSt-1 +UXt)
    W表示输入的权重
    U表示此刻输入的样本的权重

    这里的W,U,V在每个时刻都是相等的(权重共享),隐藏状态: S=f(现有的输入+过去记忆总结)。

    以上,便是最基本的RNN原理,我们为了更好的模拟人们根据过往的经验来判断和写文章,引出了
    LSTM( Long Short Term Memory Network长短期记忆网络)
    LSTM结构更复杂,不仅适合短期记忆,也适合长期记忆。

    这条黑线就是从上一时刻的输入到此刻的输出,即单元状态流,用于记忆当前状态,乘号代表着当前时刻对记忆的削减,加号代表记忆的更新,也就是新信息的汇入。
    LSTM包含3个门 (– 遗忘门 – 输入门 – 输出门)这里有这个“门”的概念,下面一个一个解释:
    遗忘门

    上一刻的信息与此刻的新信息汇入后,σ层就会把信息转化为ft,如果决定要忘记,ft就是0,如果这 个信息要保留,则为1,选择部分记忆则按照实际情况输出0~1的数,也就是激活函数,如sigmoid

    ht-1是上个网络的output(输出)xt当前网络的input(输入)网络会自动学习到对应的权重矩阵
    输入门

    首先,上一刻的信息与此刻的新信息汇入后,,统一经过σ层,决定要更新啥信息。还要另外经过tanh层,将 信息转化为一个新的候选值,两者再相乘,就是cell state中需要更新的值了。


    接着,“遗忘门”和“输入门”已经决定好了 什么要遗忘,什么要更新

    输出门

    前面的门已经决定了信息的状态如何保留和更新,得到了Ct,现在把它经过tanh层,并再次与σ层识别哪一部分信息要输出的信息相乘就得到了输出信息ht,输出两路分别给输出(比如此刻的预测词)和下一时刻输入。
    GRULSTM的变体,比LSTM结构更加简单,效果也很好,GRU只有两个门:更新门、重置门


    zt和rt分别表示更新门和重置门

    更新门用于控制前一时刻的状态信息被带入到当前状态中的程度 ,更新门的值越大说明前一时刻的状态信息带入越多
    重置门控制前一状态有多少信息被写入到当前的候选集 h̃ t 上 ,重置门越小,前一状态的信息被写入的越少

    LSTM 实践# define modelclass RNNModel(nn.Module): """ 一个简单的循环神经网络""" def __init__(self, rnn_type, ntoken, ninp, nhid, nlayers, dropout=0.5): ''' 该模型包含以下几层: - 词嵌入层 - 一个循环神经网络层(RNN, LSTM, GRU) - 一个线性层,从hidden state到输出单词表 - 一个dropout层,用来做regularization ''' super(RNNModel, self).__init__() self.drop = nn.Dropout(dropout) self.encoder = nn.Embedding(ntoken, ninp) if rnn_type in ['LSTM', 'GRU']: self.rnn = getattr(nn, rnn_type)(ninp, nhid, nlayers, dropout=dropout) else: try: nonlinearity = {'RNN_TANH': 'tanh', 'RNN_RELU': 'relu'}[rnn_type] except KeyError: raise ValueError( """An invalid option for `--model` was supplied, options are ['LSTM', 'GRU', 'RNN_TANH' or 'RNN_RELU']""") self.rnn = nn.RNN(ninp, nhid, nlayers, nonlinearity=nonlinearity, dropout=dropout) self.decoder = nn.Linear(nhid, ntoken) self.init_weights() self.rnn_type = rnn_type self.nhid = nhid self.nlayers = nlayers def init_weights(self): initrange = 0.1 self.encoder.weight.data.uniform_(-initrange, initrange) self.decoder.bias.data.zero_() self.decoder.weight.data.uniform_(-initrange, initrange) def forward(self, input, hidden): ''' Forward pass: - word embedding - 输入循环神经网络 - 一个线性层从hidden state转化为输出单词表 ''' #print("input ", input.size()) emb = self.drop(self.encoder(input)) #print("emb ", emb.size()) output, hidden = self.rnn(emb, hidden) #print("output ", output.size()) #print(len(hidden)) output = self.drop(output) decoded = self.decoder(output.view(output.size(0)*output.size(1), output.size(2))) #print("output size: ", output.size()) #print("decoded before size: ", output.view(output.size(0)*output.size(1), output.size(2)).size()) #print("decoded after size: ", decoded.size()) #sys.exit() return decoded.view(output.size(0), output.size(1), decoded.size(1)), hidden def init_hidden(self, bsz, requires_grad=True): weight = next(self.parameters()) if self.rnn_type == 'LSTM': return (weight.new_zeros((self.nlayers, bsz, self.nhid), requires_grad=requires_grad), weight.new_zeros((self.nlayers, bsz, self.nhid), requires_grad=requires_grad)) else: return weight.new_zeros((self.nlayers, bsz, self.nhid), requires_grad=requires_grad)model = RNNModel("LSTM", VOCAB_SIZE, EMBEDDING_SIZE, EMBEDDING_SIZE, 2, dropout=0.5)#模型初始化if USE_CUDA: model = model.cuda()
    0 留言 2019-06-16 20:07:46 奖励15点积分
  • 机器学习 22 、决策树 、模型融合

    前文链接:https://write-bug.com/article/2666.html
    决策树决策树(decision tree)是一种基本的分类与回归方法,模型:树结构
    主要有两大类算法:ID3 、C4.5
    学过数据结构的都知道,一棵树由节点node和有向边directed edge 构成,而节点又有几个名词:根节点、父节点、子节点、叶子节点
    这里我们用各个节点表示特征(如年龄),边表示特征属性(如青年、老年),叶子节点表示label(如买、不买)
    用决策树分类时,来了一个人根据他的特征,对某一特征进行比对,将其分到对应的子节点继续比对,直到到达叶子节点,得到预测label

    特征维度:年龄、收入、信誉、学生
    现在假设每个人都有这四类特征的数据,如何用一颗树来对这些人做一个是否购买的分类,也就是落地到某个叶子节点,那用哪个特征来做根节点父节点子节点呢?有很多组合方式。
    首先处理训练数据:

    数据特征值离散化:0 1 2 ……编码

    我们在进行特征选择时,要选择对训练数据具有分类能力的特征,以提高决策树的学习效率,决定了用哪个特征来划分特征空间,如果利用一个特征进行分类的结果和随即分类的结果没有差别,那么这个特征没有分类能力,而特征选择的准则就是信息增益与信息增益率,从而引出了ID3与C4.5算法
    ID3ID3的特征选择就是利用信息增益来进行选择,这也是我们前面提到的到底用哪个特征作为根节点哪个特征作为子节点构建树呢?
    说到信息增益,这里介绍几个概念:
    熵=随机变量的不确定性
    条件熵=在一定条件下,随机变量的不确定性
    信息增益=熵-条件熵 在一定条件下,信息不确定性减少的程度

    我们通常使用H(X)符号代表随机变量X的熵:
    H(X)=E(I(X))E代表期望值函数,I(X)代表随机变量X的自信息量。

    不确定性函数I称为事件的信息量,事件X发生概率p的单调递减函数:
    𝐼(X) = 𝑙𝑜𝑔(1/ 𝑝)=−𝑙𝑜𝑔 𝑝
    信息熵:一个信源中,不能仅考虑单一事件发生的不确定性,需要考虑所有可能情况的平均不确定性,为−𝑙𝑜𝑔 𝑝 的统计平均值E
    𝐻 (X) = 𝐸 [−𝑙𝑜𝑔 (𝑝 (x𝑖))] = −∑𝑖 𝑝(x𝑖 )𝑙𝑜𝑔 (𝑝 (x𝑖))这里的熵可以理解为混乱度,数据混乱度越大,熵取值越大,随机变量的不确定性越大
    如果H=0或1,说明数据为纯净的,一定为买或不买,而H=0.5时,混乱度最大

    伯努利分布时熵与概率的关系
    选择特征做父节点:选择熵最大(混乱程度最大)的特征
    例:

    ID3 完全用熵的概念:信息增益
    原始数据,无条件下的熵:

    label=买+不买=1024个p买=640/1024=0.635p不买 = 384/1024=0.375根据信息熵公式
    H=-∑p log(p)H=0.9544那么在年龄条件下的条件熵:
    P青年=384/1024=0.375青年分为买和不买:
    p买=128/384p不买=256/384S=384H=0.9183同理:中年:由于都是买的,所以H=0老年:H=0.9157
    年龄的三个信息熵得到了,那如何使用呢,我们对年龄求平均期望:
    平均值=占比\*信息熵E(年龄)=0.375*0.9183+0.25*0+0.375*0.9157=0.6877这个年龄作为区分的话,可以带来0.6877的增益G(年龄)=0.9544-0.6877=0.2667 为信息增益同理

    E(学生)=0.7811 G(学生)=0.1733
    E(收入)=0.9361 G(收入)=0.0183
    E(信誉)=0.9048 G(信誉)=0.0496

    从上述可以看出,按照年龄划分,收益是最大的,信息增益最大,所以年龄作为根节点,同理,从而构建整颗树.
    所以我们构建一个attrList特征列表作为一个容器存放特征,无放回的取特征
    如果取完了特征,构建出了树,但是叶子节点还是不是纯净的怎么办呢?
    分类问题:少数服从多数
    回归问题:概率比较

    缺点:因为优先选择信息增益最大的,所以导致倾向于选择属性值较多的
    贪婪性:选择收益最大的

    贪婪不是最优的算法,可能觉得本次收益最大,但从长远看收益没那么大
    奥卡姆剃刀原理:尽量用最少的东西做最多的事
    用最少的特征,区分类别,不需要所有特征都用,用最简单的方式效果最好,最优的树
    不适用于连续变量:离散型特征属性如果是身高这种线性连续的特征,对应过多类别特征,应离散化使用
    Pseudocode:
    ID3 (Examples, Target_Attribute, Attributes) Create a root node for the tree If all examples are positive, Return the single-node tree Root, with label = +. If all examples are negative, Return the single-node tree Root, with label = -. If number of predicting attributes is empty, then Return the single node tree Root, with label = most common value of the target attribute in the examples. Otherwise Begin A ← The Attribute that best classifies examples. Decision Tree attribute for Root = A. For each possible value, vi, of A, Add a new tree branch below Root, corresponding to the test A = vi. Let Examples(vi) be the subset of examples that have the value vi for A If Examples(vi) is empty Then below this new branch add a leaf node with label = most common target value in the examples Else below this new branch add the subtree ID3 (Examples(vi), Target_Attribute, Attributes – {A}) End Return RootID3实践:

    class ID3DTree(object): def __init__(self): self.tree={} self.dataSet=[] self.labels=[] def loadDataSet(self,path,labels): recordlist = [] fp = open(path,"r") # 读取文件内容 content = fp.read() fp.close() rowlist = content.splitlines() # 按行转换为一维表 recordlist=[row.split("\t") for row in rowlist if row.strip()] self.dataSet = recordlist self.labels = labels def train(self): labels = copy.deepcopy(self.labels) self.tree = self.buildTree(self.dataSet,labels) # 创建决策树主程序 def buildTree(self,dataSet,labels): cateList = [data[-1] for data in dataSet] # 抽取源数据集的决策标签列 # 程序终止条件1 : 如果classList只有一种决策标签,停止划分,返回这个决策标签 if cateList.count(cateList[0]) == len(cateList): return cateList[0] # 程序终止条件2: 如果数据集的第一个决策标签只有一个 返回这个决策标签 if len(dataSet[0]) == 1: return self.maxCate(cateList) # 算法核心: bestFeat = self.getBestFeat(dataSet) # 返回数据集的最优特征轴: bestFeatLabel = labels[bestFeat] tree = {bestFeatLabel:{}} del(labels[bestFeat]) # 抽取最优特征轴的列向量 uniqueVals = set([data[bestFeat] for data in dataSet]) # 去重 for value in uniqueVals: subLabels = labels[:] #将删除后的特征类别集建立子类别集 splitDataset = self.splitDataSet(dataSet, bestFeat, value) # 按最优特征列和值分割数据集 subTree = self.buildTree(splitDataset,subLabels) # 构建子树 tree[bestFeatLabel][value] = subTree return tree def maxCate(self,catelist): # 计算出现最多的类别标签 items = dict([(catelist.count(i), i) for i in catelist]) return items[max(items.keys())] def getBestFeat(self,dataSet): # 计算特征向量维,其中最后一列用于类别标签,因此要减去 numFeatures = len(dataSet[0]) - 1 # 特征向量维数 = 行向量维度-1 baseEntropy = self.computeEntropy(dataSet) # 基础熵:源数据的香农熵 bestInfoGain = 0.0; # 初始化最优的信息增益 bestFeature = -1 # 初始化最优的特征轴 # 外循环:遍历数据集各列,计算最优特征轴 # i 为数据集列索引:取值范围 0~(numFeatures-1) for i in range(numFeatures): # 抽取第i列的列向量 uniqueVals = set([data[i] for data in dataSet]) # 去重:该列的唯一值集 newEntropy = 0.0 # 初始化该列的香农熵 for value in uniqueVals: # 内循环:按列和唯一值计算香农熵 subDataSet = self.splitDataSet(dataSet, i, value) # 按选定列i和唯一值分隔数据集 prob = len(subDataSet)/float(len(dataSet)) newEntropy += prob * self.computeEntropy(subDataSet) infoGain = baseEntropy - newEntropy # 计算最大增益 if (infoGain > bestInfoGain): # 如果信息增益>0; bestInfoGain = infoGain # 用当前信息增益值替代之前的最优增益值 bestFeature = i # 重置最优特征为当前列 return bestFeature def computeEntropy(self,dataSet): # 计算香农熵 datalen = float(len(dataSet)) cateList = [data[-1] for data in dataSet] # 从数据集中得到类别标签 items = dict([(i,cateList.count(i)) for i in cateList]) # 得到类别为key,出现次数value的字典 infoEntropy = 0.0 # 初始化香农熵 for key in items: # 计算香农熵 prob = float(items[key])/datalen infoEntropy -= prob * math.log(prob,2) # 香农熵:= - p*log2(p) --infoEntropy = -prob * log(prob,2) return infoEntropy # 分隔数据集:删除特征轴所在的数据列,返回剩余的数据集 # dataSet:数据集; axis:特征轴; value:特征轴的取值 def splitDataSet(self, dataSet, axis, value): rtnList = [] for featVec in dataSet: if featVec[axis] == value: rFeatVec = featVec[:axis] # list操作 提取0~(axis-1)的元素 rFeatVec.extend(featVec[axis+1:]) # list操作 将特征轴(列)之后的元素加回 rtnList.append(rFeatVec) return rtnList def predict(self,inputTree,featLabels,testVec): # 分类器 root = list(inputTree.keys())[0] # 树根节点 secondDict = inputTree[root] # value-子树结构或分类标签 featIndex = featLabels.index(root) # 根节点在分类标签集中的位置 key = testVec[featIndex] # 测试集数组取值 valueOfFeat = secondDict[key] # if isinstance(valueOfFeat, dict): classLabel = self.predict(valueOfFeat, featLabels, testVec) # 递归分类 else: classLabel = valueOfFeat return classLabel # 存储树到文件 def storeTree(self,inputTree,filename): fw = open(filename,'w') pickle.dump(inputTree,fw) fw.close() # 从文件抓取树 def grabTree(self,filename): fr = open(filename) return pickle.load(fr)C4.5C4.5 用的是信息增益率的概念
    由上面,我们的信息增益:
    𝐺𝑎𝑖𝑛 (𝑆,𝐴)= 𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝑆) − ∑𝑣∈𝑉𝑎𝑙𝑢𝑒(𝐴) |𝑆𝑣|/ |𝑆| 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 (𝑆𝑣)信息增益率:
    𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜 𝐴 =𝐺𝑎𝑖𝑛(𝐴) / 𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝐴)比原来多除了一个entropy(A):属性背后的信息熵
    比如:前面的信息增益G(年龄)=0.9544-0.6877=0.2667
    𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜 𝐴=0.2667/0.6877除以一个信息熵有什么好处呢?
    如果只考虑信息增益的话,我们没有考虑A集合背后的大小,A越大也就意味着集合越混乱的可能性越高,那么C4.5考虑到了这种情况,给集合的混乱度做一个中和
    C4.5实践:


    class C45DTree(object): def __init__(self): self.tree={} self.dataSet=[] self.labels=[] def loadDataSet(self,path,labels): recordlist = [] fp = open(path,"r") content = fp.read() fp.close() rowlist = content.splitlines() recordlist=[row.split("\t") for row in rowlist if row.strip()] self.dataSet = recordlist self.labels = labels def train(self): labels = copy.deepcopy(self.labels) self.tree = self.buildTree(self.dataSet,labels) def buildTree(self,dataSet,labels): cateList = [data[-1] for data in dataSet] if cateList.count(cateList[0]) == len(cateList): return cateList[0] if len(dataSet[0]) == 1: return self.maxCate(cateList) bestFeat, featValueList = self.getBestFeat(dataSet) bestFeatLabel = labels[bestFeat] tree = {bestFeatLabel:{}} del(labels[bestFeat]) for value in featValueList: subLabels = labels[:] splitDataset = self.splitDataSet(dataSet, bestFeat, value) subTree = self.buildTree(splitDataset,subLabels) tree[bestFeatLabel][value] = subTree return tree def maxCate(self,catelist): items = dict([(catelist.count(i), i) for i in catelist]) return items[max(items.keys())] def getBestFeat(self, dataSet): Num_Feats = len(dataSet[0][:-1]) totality = len(dataSet) BaseEntropy = self.computeEntropy(dataSet) ConditionEntropy = [] # 初始化条件熵 splitInfo = [] # for C4.5, calculate gain ratio allFeatVList=[] for f in range(Num_Feats): featList = [example[f] for example in dataSet] [splitI,featureValueList] = self.computeSplitInfo(featList) allFeatVList.append(featureValueList) splitInfo.append(splitI) resultGain = 0.0 for value in featureValueList: subSet = self.splitDataSet(dataSet, f, value) appearNum = float(len(subSet)) subEntropy = self.computeEntropy(subSet) resultGain += (appearNum/totality)*subEntropy ConditionEntropy.append(resultGain) # 总条件熵 infoGainArray = BaseEntropy*ones(Num_Feats)-array(ConditionEntropy) infoGainRatio = infoGainArray/array(splitInfo) # c4.5, info gain ratio bestFeatureIndex = argsort(-infoGainRatio)[0] return bestFeatureIndex, allFeatVList[bestFeatureIndex] def computeSplitInfo(self, featureVList): numEntries = len(featureVList) featureVauleSetList = list(set(featureVList)) valueCounts = [featureVList.count(featVec) for featVec in featureVauleSetList] # caclulate shannonEnt pList = [float(item)/numEntries for item in valueCounts ] lList = [item*math.log(item,2) for item in pList] splitInfo = -sum(lList) return splitInfo, featureVauleSetList def computeEntropy(self,dataSet): datalen = float(len(dataSet)) cateList = [data[-1] for data in dataSet] items = dict([(i,cateList.count(i)) for i in cateList]) infoEntropy = 0.0 for key in items: prob = float(items[key])/datalen infoEntropy -= prob * math.log(prob,2) return infoEntropy def splitDataSet(self, dataSet, axis, value): rtnList = [] for featVec in dataSet: if featVec[axis] == value: rFeatVec = featVec[:axis] rFeatVec.extend(featVec[axis+1:]) rtnList.append(rFeatVec) return rtnList # 树的后剪枝 # testData: 测试集 def prune(tree, testData): pass def predict(self,inputTree,featLabels,testVec): root = list(inputTree.keys())[0] secondDict = inputTree[root] featIndex = featLabels.index(root) key = testVec[featIndex] valueOfFeat = secondDict[key] # if isinstance(valueOfFeat, dict): classLabel = self.predict(valueOfFeat, featLabels, testVec) else: classLabel = valueOfFeat return classLabel def storeTree(self,inputTree,filename): fw = open(filename,'w') pickle.dump(inputTree,fw) fw.close() def grabTree(self,filename): fr = open(filename) return pickle.load(fr)之前的ID3和C4.5停止条件都是结点数据类型一致(即纯净),要不就是没有特征可以选择了,但是只有这两个条件限制,在特征多树学习过深的情况下,模型容易过拟合
    防止过拟合:

    停止条件:信息增益(比例)增长低于阈值,则停止
    – 阈值需要调校 将数据分为训练集和测试集
    – 测试集上错误率增长,则停止
    剪枝:

    相邻的叶子节点,如果合并后不纯度增加在允许范围内,则合并
    测试集错误率下降,则合并 等等

    sklearn- tree实践:
    from sklearn.tree import DecisionTreeRegressor# Fit regression modelregr_2 = DecisionTreeRegressor(max_depth=10)#深度阈值print >> sys.stderr, 'begin train ==============='regr_2.fit(X, y)print >> sys.stderr, 'begin predict ==============='# Predicty_2 = regr_2.predict(X_test)for p_label in y_2: print p_label #输出预测标签(回归值)print >> sys.stderr, 'end ==============='多分类用MSE做评估:
    import sysfrom sklearn import metricsimport numpy as npimport randomres_file = sys.argv[1]y_test = []y_pred = []with open(res_file, 'r') as fd: for line in fd: ss = line.strip().split('\t') if len(ss) != 2: continue t_label = float(ss[0].strip()) p_label = float(ss[1].strip()) y_test.append(t_label) y_pred.append(p_label)print "MSE:",metrics.mean_squared_error(y_test, y_pred)print "RMSE:",np.sqrt(metrics.mean_squared_error(y_test, y_pred))模型融合Ensemble Learning(集成学习)什么是集成学习呢?假设我有多个模型,每个模型的学习准确率都是80%,或者说每个模型的准确率有学习好的有学习坏的,这时就有很多数据没有预估正确,那么我使用多个模型来共同决策,少数服从多数,通过这种方式提升准确率,把多个弱分类器集成获得一个强分类器。
    集成学习里面有两类算法:Bagging和Boosting算法
    Bagging算法是以random forest随机森林为代表的算法
    Boosting算法是以AdaBoost算法和Gbdt为代表的算法
    通过介绍我们知道这是将多个模型融合,得到一个强模型的方法,那么我们是如何证明这种方式是否靠谱呢?
    用数学上的排列组合问题表示,假设二分类问题有5个精确度为70%的弱分类器,相互独立
    采用投票的方式将5个分类器的结果进行集成:
    𝐶5 3(0.73)(0.32)+ 𝐶5 4(0.74)(0.31)+ 𝐶5 5(0.71) = 10(.7^3)(.3^2)+5(.7^4)(.3)+(.7^5) = 83.7%如果有101个分类器,精确度就可以提升到99.9%

    问题:如何得到不同的分类器,并且尽量独立? (每个模型不尽相同,不相互影响)
    方法:将一个复杂的学习问题,分解成多个简单的学习问题

    Bagging– 对训练数据采样,得到多个训练集,分别训练模型
    – 对得到的多个模型进行平均 分类问题:投票方式进行集成 回归问题:模型的输出进行平均

    训练:同一训练数据随机抽取数据并行用不同的机器和模型同时训练
    测试:对模型预测出的各个分数进行投票或者平均
    适合弱分类器(容易过拟合,效果一般):
    不稳定:随机采样会得到较不同的分类器,每个基分类器准确率略高于50%
    例如:决策树
    不适合强分类器(本身准确率高,效果较好) :
    稳定:随机采样对结果影响不大
    甚至可能不如不集成,每个基分类器只有更少的训练样本
    例如:DNN(模型复杂时,时间成本大并且容易过拟合,为了抗过拟合,最有效的办法就是让训练数据越大越好,和bagging的选取数据思想不同)
    Random Forest
    Random Forest = Bagging+决策树
    随机森林生成方法:
    – 从样本集中通过重采样的方式产生n个样本
    – 建设样本特征数目为a,对n个样本选择a中的k个特征,用建立决策树的方式获得最佳分割点
    – 重复m次,产生m棵决策树
    – 多数投票机制进行预测
    每棵树样本不同,选择特征可能不同,形成树的形状、深度都不同。
    优点:

    训练速度快、容易实现并行
    训练完成后,反馈哪些是重要特征(类似LR中的特征权重,这里的决策树靠信息熵筛选)
    抗过拟合能力强 (多棵树抗过拟合)
    可解决分类、回归问题
    不平衡数据集,rf是平衡误差有效方法

    缺点:

    取值较多的属性,影响大
    噪音大的分类、回归问题会过拟合
    只能尝试参数和种子的选择,无法洞悉内部

    Boosting每个基分类器,基于之前的分类结果,已经分对的样本不用太多关心,集中力量对付分错样本,不等权投票,好的基分类器权重大
    – 对训练数据集进行采样,对错分样本加权采样
    – 多个模型按照分类效果加权融合

    训练:同一训练数据随机抽取数据串行用不同的机器和模型进行训练,首先模型一学习预估评分后,对出错的样本,提高采样权重,用模型二再次随机抽取数据,这时由于出错样本采样权重提高重点会放在出错的样本上,以此类推串行迭代下去
    测试:对各个模型预测出的各个分数乘以对应的错误率权重公式相加
    Boosting方法的两类思想:
    传统Boost→ Adaboost:对正确、错分样本加权,每步的迭代,错误样本加权,正确样本降权
    Gradient Boosting:每次建模建立在之前模型损失函数的梯度下降方向
    Adaboost
    对不同的模型分数加权求和,错误样本加权,正确样本降权


    给数据中的每一个样本一个权重
    训练数据中的每一个样本,得到第一个分类器
    计算该分类器的错误率,根据错误率计算要给分类器分配的权重(注意这里是分类器的权重) 即前面表示的每个模型预估后的分数乘对应的分类器权重求和

    错误率:𝜀 =未正确分类的样本数目/ 所有样本数目 分类器权重: 𝛼 =1/ 2 ln((1 – 𝜀)/ 𝜀)

    将第一个分类器分错误的样本权重增加,分对的样本权重减小(注意这里是样本的权重)
    错分样本权重:𝐷𝑖^ (𝑡+1) = 𝐷𝑖 ^(𝑡)𝑒^𝑎 /𝑆𝑢𝑚(𝐷),Di^t表示上一次样本的权重,分母:训练集的规模,样本个数
    正确样本权重:𝐷𝑖^ (𝑡+1) = 𝐷𝑖^ (𝑡)𝑒^(−𝑎) / 𝑆𝑢𝑚(𝐷)

    然后再用新的样本权重训练数据,得到新的分类器,到步骤3
    直到步骤3中分类器错误率为0,或者到达迭代次数
    将所有弱分类器加权求和,得到分类结果(注意是分类器权重)

    GBDT(Gradient Boosting Decision Tree)
    是一种迭代的决策树算法,该算法由多棵决策树组,所有树的结论累加起来做最终答案
    三个概念组成:
    – Regression Decistion Tree(DT、RT)
    – Gradient Boosting(GB)
    – Shrinkage(步长)
    分类树:衡量标准最大熵——预测分类标签值
    回归树:衡量标准是最小化均方差——预测实际数值
    GBDT中的树,属于回归树,不是分类树 – 要求所有树的结果进行累加是有意义的 – GBDT是结果累加,而不是多数投票
    GBDT核心: – 每一棵树学的是之前所有树结论和的残差 – 残差就是一个加预测值后能得真实值的累加量
    残差是什么?

    因为是回归树,那么我的节点值应该是这个节点的平均值即预估值,那么来了一个人落在左边这个节点就是15岁,但是对于某些人预估的大了,有的预估的小了,那我把残差整理成新的样本再建一棵树重新学习,尽量把残差学没了,就像以前的误差值,尽力把它学为0
    这里同样的,特征选择时也是利用信息熵的方式。
    残差是学习的最优方向,体现了Gradient
    Gradient Descend梯度下降实际上是在更新参数,并且最终参数等于每次迭代的增量的累加和:
    𝜃𝑡 = 𝜃𝑡−1 + 𝜃𝑡𝜃𝑡 = −𝑎𝑡𝑔𝑡 参数更新方向为负梯度方向𝜃 =∑𝜃𝑡 最终参数等于每次迭代的增量的累加和, 𝜃0为初值而Gradient Boost是在更新整个函数
    𝑓𝑡 𝑥 = 𝑓𝑡−1 𝑥 + 𝑓𝑡 (𝑥)𝑓𝑡(𝑥) = −𝑎𝑡𝑔𝑡(𝑥) 类似地,拟合了负梯度𝐹(𝑥) = ∑𝑓𝑡(𝑥) 最终参数等于每次迭代的增量的累加和 𝑓0(𝑥)为模型初值,通常为函数所以,Boosting是一种加法模型GBDT模型F定义为加法模型
    𝐹 (𝑥;𝑤) = ∑𝑎𝑡 ℎ𝑡(𝑥;𝑤𝑡)= 𝑓𝑡(𝑥;𝑤𝑡)x为输入样本,h为分类回归树,w是分类回归树的参数,a是每棵树的权重

    2.1的公式是loss值更新函数预估值,2.2是求残差
    但是这样的加法模式比较容易过拟合,这就涉及到了Shrinkage缩减技术:
    思想:每棵树只学到了真理的一小部分,累加的时候只累加一小部分,通过多学几棵树弥补不足
    假设: yi表示第i棵树上y的预测值, y(1~i)表示前i棵树y的综合预测值
    没有shrinkage时:
    – y(i+1) = 残差(y1~yi), 其中: 残差(y1~yi) = y真实值 - y(1 ~ i)
    – y(1 ~ i) = SUM(y1, …, yi)
    有shrinkage时:
    – 第2个方程调整为:y(1 ~ i) = y(1 ~ i-1) + step /* yi
    即对每次的结果都乘一个权重
    仍然以残差作为学习目标,但对于残差的学习,每次只累加一小部分(step残差)逐步逼近目标
    本质上,Shrinkage为每棵树设置了一个weight,累加时要乘以这个weight
    偏差、方差
    偏差bias:模型不准确
    尽量选择正确模型与复杂度
    模型越简单,预估能力越差,偏差越大,方差越低
    方差variance:模型不稳定
    防止过拟合

    我们的模型融合是可以同时把方差与偏差同时降低的方法。
    RF实践:
    sklearn - rf:
    测试数据:

    import sysimport numpy as npimport matplotlib.pyplot as pltimport pandas as pd# Importing the datasetsdatasets = pd.read_csv('Position_Salaries.csv')#pandas自动解析读取X = datasets.iloc[:, 1:2].values #级别Y = datasets.iloc[:, 2].values #金额# Fitting the Regression model to the datasetfrom sklearn.ensemble import RandomForestRegressorregressor = RandomForestRegressor(n_estimators = 300, random_state = 0)#300颗树regressor.fit(X,Y)# Predicting a new result with the Random Forest RegressionY_Pred = regressor.predict([[6.5]])print(Y_Pred)# Visualising the Random Forest Regression results in higher resolution and smoother curveX_Grid = np.arange(min(X), max(X), 0.01)X_Grid = X_Grid.reshape((len(X_Grid), 1))plt.scatter(X,Y, color = 'red')plt.plot(X_Grid, regressor.predict(X_Grid), color = 'blue')plt.title('Random Forest Regression Results')plt.xlabel('Position level')plt.ylabel('Salary')plt.show()output:

    pyspark-mllib-rf:
    测试数据:

    #coding=utf8from __future__ import print_functionimport sysfrom pyspark import SparkContext, SparkConffrom pyspark.mllib.regression import LabeledPointfrom pyspark.mllib.feature import HashingTF,IDF,StandardScalerfrom pyspark.mllib.classification import LogisticRegressionWithSGD,SVMWithSGD,NaiveBayesfrom pyspark.mllib.tree import DecisionTreefrom pyspark.mllib.tree import RandomForest, RandomForestModelfrom pyspark.mllib.util import MLUtilsreload(sys)sys.setdefaultencoding('utf-8')if __name__ == "__main__": #conf = SparkConf().setMaster("spark://master:7077").setAppName("lr_pyspark_test") conf = SparkConf().setMaster("local").setAppName("lr_pyspark_test") sc = SparkContext(conf=conf) #in_file = sc.textFile("file:///root/spark_test_5/pyspark_test/lr_pyspark_test/data/a8a") data = MLUtils.loadLibSVMFile(sc, "file:///root/spark_test_5/pyspark_test/lr_pyspark_test/data/a8a") (trainingData, testData) = data.randomSplit([0.7, 0.3]) model = RandomForest.trainClassifier(\ trainingData, numClasses=2, \ categoricalFeaturesInfo={},\ numTrees=3, \ featureSubsetStrategy="auto",\ impurity='gini', maxDepth=4, maxBins=32)#3颗树,gini系数方式 predictions = model.predict(testData.map(lambda x: x.features)) labelsAndPredictions = testData.map(lambda lp: lp.label).zip(predictions) testErr = labelsAndPredictions.filter(lambda (v, p): v != p).count() / float(testData.count()) print('Test Error = ' + str(testErr)) print('Learned classification forest model:') print(model.toDebugString()) ## Save and load model #model.save(sc,"target/tmp/myRandomForestClassificationModel") #sameModel = RandomForestModel.load(sc, "target/tmp/myRandomForestClassificationModel") sc.stop()GBDT实践:
    微软lightgbm方式:
    import sysimport lightgbm as lgb #pip安装import numpy as npfrom scipy.sparse import csr_matriximport pandas as pdfrom sklearn.metrics import mean_squared_errorfrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom sklearn.datasets import make_classificationdata_in = 'D:\\bd\\share_folder\\a9a'def load_data(): target_list = [] fea_row_list = [] fea_col_list = [] data_list = [] row_idx = 0 max_col = 0 with open(data_in, 'r') as fd: for line in fd: ss = line.strip().split(' ') label = ss[0] fea = ss[1:] target_list.append(int(label)) for fea_score in fea: sss = fea_score.strip().split(':') if len(sss) != 2: continue feature, score = sss fea_row_list.append(row_idx) fea_col_list.append(int(feature)) data_list.append(float(score)) if int(feature) > max_col: max_col = int(feature) row_idx += 1 row = np.array(fea_row_list) col = np.array(fea_col_list) data = np.array(data_list) fea_datasets = csr_matrix((data, (row, col)), shape=(row_idx, max_col + 1)) x_train, x_test, y_train, y_test = train_test_split(fea_datasets, target_list, test_size=0.2, random_state=0) return x_train, x_test, y_train, y_testX_train,X_test,y_train,y_test = load_data()# 创建成lgb特征的数据集格式lgb_train = lgb.Dataset(X_train, y_train)lgb_eval = lgb.Dataset(X_test, y_test, reference=lgb_train)params = { 'task': 'train', 'boosting_type': 'gbdt', # 设置提升类型 'objective': 'regression', # 目标函数 'metric': {'l2', 'auc'}, # 评估函数 'num_leaves': 31, # 叶子节点数 'learning_rate': 0.05, # 学习速率 'feature_fraction': 0.9, # 建树的特征选择比例 'bagging_fraction': 0.8, # 建树的样本采样比例 'bagging_freq': 5, # k 意味着每 k 次迭代执行bagging 'verbose': 1 # <0 显示致命的, =0 显示错误 (警告), >0 显示信息}print('Start training...')# 训练 cv and traingbm = lgb.train(params,lgb_train,num_boost_round=20,valid_sets=lgb_eval,early_stopping_rounds=5)print('Save model...')# 保存模型到文件gbm.save_model('model.txt')print('Start predicting...')# 预测数据集y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration)print(y_test)print(y_pred)# 评估模型print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)部分模型output:
    0 留言 2019-06-21 08:22:26 奖励12点积分
  • 机器学习 14、分类算法-NB、AUC

    前文链接:https://write-bug.com/article/2428.html
    分类算法更新:NB、PR/AUC/ROC、LR、Softmax、DT、RF、GDBT、DNN、CNN、RNN
    什么是分类问题呢?
    最常见的机器学习任务:给定一个对象X,将其划分到预定义好的某一个类别Yi。
    比如说:性别识别,人群划分,新闻分类,query分类,商品分类,网页分类,垃圾邮件过滤,网页排序等等。
    对于性别识别来说,分辨男女,也就是二分类问题,即判断0和1问题。
    那我们如何评判一个人是男是女呢?这时就需要特征来解决:肤色、身高、体重、音色等等等等,我们人类打眼一看什么特征大概就知道这个人是男是女了,那机器是如何学会这个技能的呢?
    我们可以把这个机器当成是一个幼儿园小孩,如果幼儿园老师告诉小朋友,0:老虎很凶猛,1:小猫很温顺,那这时来了个狮子,小孩大脑里就会自动的拿狮子的特征去比对所见过的东西,觉得有些像老虎,那就会自然而然地离它远一些了。
    这个技能就是泛化能力,也就是说来了一个新东西,如果我能预测的很准的话,那就说明这次机器学习的模型是效果很好的,是具有泛化能力的。
    如果我想对文章做分类,一篇文章可以有很多类别,即多分类,那其中的特征是什么呢?关键词token,我提取出一篇文章的关键词,很容易就可以看出这篇文章属于哪类,每个词都有着对每个类别的倾向性,比如说‘股市’大概率都是财经文章。
    机器学习模型
    我们人类可以通过自己的学习经验一眼就可以把分类问题做出来,如果有大量数据的时候我们就需要机器去判断,也就是机器学习。
    机器学习目的:模型,可以帮我们对数据做预测。
    如果我想要机器学习对新数据预测的分类准确率高的话,我们就需要两点:

    好模型(老师/算法)
    好数据(教材/训练集)

    * 好模型 ≠ 复杂模型:

    复杂模型和性能开销成正比,即实现程度
    过拟合,对训练集学习太过深刻会把训练集中的错误数据知识也学习到了,缺少泛化能力,对测试预估效果影响较大

    评估模型学习效果:PR/AUC/ROC
    朴素贝叶斯(NB)算法
    我们在中文分词那节的语言模型中,推导过贝叶斯定理:
    p(s|c)=p(c|s)p(s)/p(c)推导:
    p(s|c) p(c)=p(s,c)—联合概率(同时发生的概率)->p(c|s)p(s)=p(c,s)-> p(s|c) p(c)= p(c|s)p(s)-> p(s|c)= p(c|s)p(s)/p(c)那假如我们设定:
    X:一篇文章
    Y:文章类别集合{}
    yi:第i个类别
    xi:文章某token
    p(yi|X):一篇文章属于哪个类别的概率
    则有:p(yi|X)=p(X|yi)p(yi)/p(X)
    p(yi):先验概率,即常识,已知规律
    我们看上面的设定来说,p(yi)代表着这个类别的概率,也就是说假设我训练集有100篇文章,我提前知道军事类别50,财经类别30,体育类别20,那么我们的先验概率也就固定下来了,p(y=军事)=50/100,以此类推,那么等到我测试集进行预测时,我的先验概率也按照这个比例来分布。
    p(X):常数,一篇文章出现的概率就像我们原先说的一个人说的每句话一样几率都是一样的。
    所以,公式简化为:
    p(yi|X)=p(X|yi)p(yi)p(X|yi)=p(x1|y1)\*p(x2|y1)\*p(x3|y1)....也就是把大X分成不同的关键词,但前提是独立同分布。
    所以朴素贝叶斯的前提:独立同分布
    那这里我需要对p(yi|X)=p(X|yi)p(yi)的参数进行估计:即最大似然估计
    p(yi),如何计算呢?统计,说白了就是我们刚才举例子的方法求得的。
    p(X|yi),两种计算方法:
    p(xi|yi)=count(xi,yi)/count(yi)count(xi,yi):即特征(关键词)xi和类别yi在训练数据中同时出现的次数
    count(yi):即某类别总数
    p(谷歌|军事)=军事类文章中包含‘谷歌’这个词的文章个数 / 军事类文章个数p(谷歌|军事)=军事类文章中包含‘谷歌’这个词的文章个数 / 军事类文章中所有词个数通过上面的分析与推导,我们得到了两个参数,如果来了一篇文章我们去预测属于那个类别,即p(yi|X),让这两个参数相乘就ok了。这个结果是一个概率,这就意味着如果是二分类问题,p(y=0|X)=70%,p(y=1|X)=30%,即有多少分类就要求多少个概率值,取概率最大的数,最致信。这个结果就是后验概率。
    优点:– 简单有效 – 结果是概率,对二值和多值同样适用
    缺点:– 独立性假设有时不合理
    NB实践:
    1.python DataConvert.py data/ nb_data
    数据准备:分好词的几千篇文章
    数据合并和转换:标签和token
    数据编码:token编码为数字,分测试集和训练集
    2.python NB.py 1 nb_data.train model
    训练数据训练,得到model(前面的两个参数)
    3.python NB.py 0 nb_data.test model out
    测试数据用model作预测—》求log
    二分类评估效果
    那我们怎么去评估我们的分类效果呢?对于二分类来说,我们最初使用混淆表(混淆矩阵)的方式进行评测:


    准确度Accuracy:(C11+C22)/(C11+C12+C21+C22)
    精确率Precision(y1):C11/(C11+C21)
    召回率Recall(y1):C11/(C11+C12)

    这种方式不好看,我们来替换成例子来看下:


    准确度Accuracy:(50+35)/(35+5+10+50)=85%
    精确率Precision(y1):50/(50+5)=90.9%
    召回率Recall(y1):50/(50+10)=83.3%

    上面的例子很明确,通常在工作中一般注重这两个指标,正确率(精确率)和召回率:

    正确率:预测样本中,正确的样本所占的比例,即看军事列
    召回率:预测样本中,正确的样本占同一类别总的样本比例,看军事行

    那么什么指标合适,在日常生活中,有的是侧重于召回,有的是侧重于正确率,越靠近底层一般越侧重于召回,越往上,越侧重于精确,即Nosq库那块侧重召回,排序模型那里侧重于精确
    上面我们提出了混淆矩阵,得到了准确率和召回率:
    这里引出了:PR、ROC、AUC
    有了这个正确率和召回率,我们可以获得一个PR曲线,即:同时评估正确率和召回率的方法就是通过PR曲线,p代表正确率,R代表召回率但是这个PR曲线很容构造成一个高正确率或高召回率的曲线,很难保证两全齐美,一般准确率高,召回率就低,召回率高,准确率低,可以构成一个二维码坐标,纵坐标是正确率,横坐标是召回率,用来确定阈值thd

    那么用生活中的两类场景来举例子:
    搜索场景,保证召回的前提下,再提高准确率
    疾病检测,保证准确性前提,提升召回
    PR曲线是个评测指标,用来协助你去选择阀值的,这个阈值怎么理解呢?比如我几篇文章被预测为军事的概率分别是0.7、0.8、0.6,如果阈值设置为thd=0.5,那么这三篇文章全被分辨为正例,都是军事。通过对阈值的调参,我得到的混淆矩阵里面的数值不同。
    那么我们看下ROC曲线的评测指标:

    纵轴:真阳率,召回率,TP/(TP+FN)
    横轴:假阳率FP/(FP+FN)
    那么ROC曲线有什么用,其实ROC曲线是为了得到AUC,即ROC曲线下的面积,,不同的阈值生成不同的混淆矩阵数值,打一个点就得到下面的曲线

    但是这样计算比较麻烦,我们可以利用其他方式去理解AUC,即负样本排在正样本前面的概率。
    假如A 0.1 B 0.9 我们假设负样本排正样本前面的概率认为正确,即A在B前面,认为是一次正确,B排在A前面,认为是一次错误。也就是按照概率进行倒序排序,上面是最小的概率,那么理想状态下,所有负例应该排在正例前面才对。
    我们可以通过一个AWK来计算:
    cat auc.raw | sort -t$'\t' -k2g |awk -F'\t' '($1==-1){++x;a+=y;}($1==1){++y;}END{print 1.0-a/(x\*y);}'x*y是正负样本pair对,a代表错误的个数,a/x*y 错误的概率,1-a/x*y 正确概率
    解释一下这个linux命令,按照第二个模型打的分数进行循环判断,小的排在前面,大的分数排在后面,当有的分数是比较小,但是不是该类的,这个a就加一个y,y从0开始加,直到结束,能够找到有多少a,进而计算评估的正确率
    例如:来了个文章,我们假如是军事类为+1,财经为-1,当然这个文章是军事类文章,即+1,然后我们设置一个阀值为0,即分类预测的分数 >0 认为是+1,<=0 认为是-1,x是负样本的个数,y是所有正样本个数,a是错误的样本个数

    那么这个最差就是0.5,压根不知道好坏,评测是到底是正确的评测还是错误的评测。最完美就是1或者0了
    0 留言 2019-04-28 12:40:13 奖励13点积分
  • 机器学习 15、分类算法 -LR

    前文链接:https://write-bug.com/article/2439.html
    逻辑回归前节中,我们分析了什么是分类以及机器学习的模型介绍、NB算法的应用、和二分类模型的评估。我们在这里再次总结一下机器学习的要素(括号内是对于LR而言):

    机器学习用数据训练出模型再应用的过程
    训练集训练所用的输入与输出
    测试集评估所用的输入与输出
    监督学习机器学习中,分为监督学习和非监督式学习,而监督式学习就是数据集有着明确的答案(即label),可供后续寻找输入输出之间的关系(误差)
    模型描述输入输出之间关系的方式(等式参数)
    训练学习输入输出之间关系的过程
    预测解决输入的预期输出的过程
    评估衡量模型好坏的过程
    泛化能力对一个前所未见的输入可以给出一个正确的预测

    在谈LR之前,我们需要介绍一些铺垫知识:
    一元线性回归何为回归为题?假如有一二维坐标系,横坐标x:西瓜重量,纵坐标y:西瓜价格,上面散落着一些点,即每个西瓜重量都有着对应的价格。如下图:

    那我如何根据这些数据,获取到一些规律,每次随意给我一个西瓜重量我都可以预测一个合理价格出来呢?我们需要像图中绿色的那条线一样,尽力去拟合所有数据,即 y=wx+b,给定x西瓜重量,返回y西瓜价格,未知参数:w,b。
    在上图中我们可以看到很多data点,同样的也就可以画出很多条线,那我们如何才能找到最可以拟合所有数据的最优线呢?我们可以给每个点和每条线之间都求取点到线的距离,即线没有拟合点的误差值,那么当我们找最优线的时候,我们把每次和这条线求的所有误差值加起来,看谁最小就好了,即最小化误差平方和:
    ∑((wx+b) - y)^2即loss function 找出最优参数,获取最优线。
    Error = y - y^那么如何求取最优参数?因为lossfunc为二次方程,坐标系中为下凸函数,所以求导=0就可以得出极小值:最优参数w,b

    模型输出:y^=wx+b
    模型参数:w,b

    多元线性回归在一元中,我们输入x为一个单因素值,即标量。在多元中,我们输入的x为多因素值,即向量。那么什么情况为多因素值呢?比如还是西瓜,那我的西瓜价格不只是重量影响着,还有颜色,拍的响声等等,而这些因素就是西瓜的特征,而西瓜在这里成为样本。
    但是这种多维度向量并不能在二维坐标系中显示,每个样本都有着多维度特征,可以想象,像二维坐标系中显示一样,在高纬度空间中散落着这些点,如果要做回归问题,就需要有一个超平面拟合这些数据点,如果做分类问题则需要一个超平面去尽力把两类样本点分开,而这里的西瓜问题是个回归问题。而这个超平面也就意味着我们的参数也变成了多维向量。即:
    X[x1,x2,x3...xn]W[w1,w2,w3,...wn]wx向量相乘是求内积。
    之前我们的等式y=wx+b,在机器学习中有了些新的名称:

    X:样本特征向量
    W:权重向量
    B:偏置

    比如:

    X样本为一个西瓜,那么西瓜的特征可能有:重量、颜色、响声、把的位置等等
    W权重即这些特征的重要程度,每个特征的权重都影响着最后的score
    B偏置的意思就是比如说各个地区的西瓜长得样子普遍不一样,那对于这类样本来说给他一个惩罚值平衡样本数据

    同样的,我们得到多元回归方程:
    𝑓(𝑥𝑖,𝑤,𝑏) = ∑𝑤𝑗𝑥𝑖𝑗 + 𝑏 = [𝑥𝑖1 ⋯ 𝑥𝑖𝑘][𝑤1 ⋮ 𝑤𝑘]+ 𝑏 = 𝑤𝑖𝑥 + 𝑏我们把b约去得到:
    𝑓(𝑥𝑖,𝑤,𝑏) = [𝑥𝑖1 ⋯ 𝑥𝑖𝑛][𝑤1 ⋮ 𝑤𝑛]+ 𝑏 = [𝑥𝑖1 ⋯ 𝑥𝑖𝑛 1][𝑤1 ⋮ 𝑤𝑛 𝑏]= 𝑤 · 𝑥𝑖所以只需要求:
    𝑓(𝑥𝑖,𝑤) = 𝑤𝑥和前面一样,为了求取最优参数,需要最小化误差平方和:
    min 𝑤 𝐿(𝑤) = ∑ (𝑤𝑥𝑖 – 𝑦𝑖)^2------》e只不过单因素标量变成了多因素向量了而已。
    同样,求导=0,但是这里w也是个向量, 根据微积分公式需要对每个w特征权重求偏导,得出:
    W=(XTX)^-1 XTYXT为X向量的转置,Y为输出后的向量
    当XT X 不可逆时,设定正数λ,W=(XTX + λI)^-1 XTY
    逻辑回归逻辑回归,logistic回归,是一种广义的线性回归分析模型,常用于数据挖掘,疾病自动诊断,经济预测等领域。常用于二分类问题,而多分类问题常用SoftMax函数来解决。
    上节说过,二分类问题也就是01问题,比如判断一个人是男是女,可以从多个特征来分辨:肤色、身高、体重、音色等等,每个特征都有自己的权重,像前面一样代表各个特征的影响度。
    设定1为男性,0为女性,则P(y=1|x)代表男性的概率,P(y=0|x)代表女性的概率。通常情况下,我们研究正例的概率,也就是y=1的概率,那么有:
    P(y=1|x)=f(x)这里的输入和前面的多元线性回归一样,但是输出是一个score,即
    f(x)=wx但是这里的score也就是y是一条直线,值域是(-∞,+∞),而概率的值域是[0-1],那如何让P(y=1|x)=wx呢?一起来推导下:
    exp(wx)的值域是[0,+无穷)p(y=0|x) = 1 - p(y=1|x)p(y=1|x) / (1 - p(y=1|x))的值域是[0,+无穷)p(y=1|x) / (1 - p(y=1|x))= exp(wx)p(y=1|x) = 1/(exp(-wx) +1)以上,我们通过压缩变换值域把他强制变到一个0-1的概率值
    在实际应用中,是客观存在这种非线性变换函数的,这里LR用Sigmoid函数:

    可以发现,和我们上面的想法推导几乎一致,但是这个函数不是我们推导出来的,而是客观存在的函数:

    那么这里我们求w这个最优参数值呢?
    在NB朴素贝叶斯中求取概率值,我们运用最大似然估计参数从而求得概率值。
    那么在这里我们同样对P运用最大似然:
    P(Y|X)=P^y * P^(1-y)这么表示并无实际含义,只是当y=0或1时的概率,那我们对它使用极大似然估计参数w:
    MLE w = arg max log(P(Y|X)) = arg max Π P(yi|xi) = arg max ∑ log P(yi|xi) = arg max ∑(yi LogP(y=1|X) +(1-yi) LogP(y=0|X))p(y=1|x) = 1/(exp(-wx) +1)p(y=0|x) = 1 - p(y=1|x)所以有:
    L(w)=-∑(yi log(𝜂(wx)) +(1-yi) (1-log(𝜂(wx))))为什么前面有个减号呢?最大似然函数是求取参数的极大值,是上凸函数,前面加个符号,图像就变成了下凸函数,这样我们就可以求取到参数极小值。
    看到上面的式子,如果你熟悉信息熵的话,是可以直接得到上面的式子的,即
    MLEmax = lossfunction min (- min CrossEntropy)信息熵公式:
    H(x)= - ∑ P(xi)log(p(xi))后面我们会有地方介绍信息熵,我们得到上面的L(w)负对数似然公式,由于它是高阶连续可导下凸函数,此时就可以将他作为损失函数来求解:
    利用梯度下降法更新参数w,求导得:
    ▽L(w)= -∑(yi- 𝜂(wx))xi机器学习的损失函数是人为设计的,用于评判模型好坏(对未知的预测能力)的一个标准,就像去评判任何一件事物一样,从不同角度看往往存在不同的评判标准,不同的标准往往各有优劣,并不冲突。唯一需要注意的就是最好选一个容易测量的标准,不然就难以评判了。
    其次,既然不同标准并不冲突,那使用最小二乘作为逻辑回归的损失函数当然是可以,那这里为什么不用最小二乘而用最大似然呢?请看一下最小二乘作为损失函数的函数曲线
    J(θ)=∑(yi- 𝜂(θx))
    以及最大似然作为损失函数的函数曲线
    L(w)=-∑(yi log(𝜂(wx)) +(1-yi) (1-log(𝜂(wx))))
    很显然,图2比图1展现的函数要简单多,很容易求到参数的最优解(凸函数),而图1很容易陷入局部最优解(非凸函数)。这就是前面说的选取的标准要容易测量,这就是逻辑回归损失函数为什么使用最大似然而不用最小二乘的原因了。
    此时,我们就可以和前面一样通过lossfunc求取最优参数w,通过不断降低差距来使预测值接近真实值(即反向传递的误差):
    由于L(w)是高阶连续可导的凸函数,根据凸优化理论,可利用梯度下降法、 牛顿法等求解,求导得到梯度:
    ▽L(w)= -∑(yi- 𝜂(wx))xi梯度:大小为导数的值,方向指向误差上升最快的方向
    当参数w维度大于1时,用相同的方法对各个维度求e偏导数(e(w)’),偏导数所组成的向量就是梯度。
    导数和梯度的区别是:导数是变化率,而梯度是一个和参数维度一样的向量。
    各个维度的数值等于对应的偏导数,那么让参数向梯度相反的方向更新,从而减小误差值。所以,使用梯度下降法更新最小化F(W),从而更新参数W:

    设置初始化w,计算F(w)=sigmoid(wx ) ->预估值我们的数据前面说过都是有label值的,也就是真实值,得到预测值和真实值之间的误差,我们希望通过学习数据让误差越来越小。
    计算梯度
    ▽F(w)=▽L(w)= -∑(yi- 𝜂(wx))xi此时我们已经得到了y真实值,w初始化值,x样本特征值,可以发现,梯度式子里面就是一个误差公式,那我们通过计算就可以直接代入乘以样本向量,得到梯度。下降方向
    dir = -▽F(w)负号:前面说过,反方向是下降最快方向
    尝试梯度更新
    𝑤𝑛𝑒𝑤 = 𝑤 +步长∗ 𝑑𝑖𝑟 得到下降后的 𝑤𝑛𝑒𝑤和F(w𝑛𝑒𝑤)如果 F(w𝑛𝑒𝑤)- F(w)较小,停止; 否则 ;跳到第2步
    1 留言 2019-05-08 22:26:17 奖励21点积分
  • 机器学习 16、分类算法 -Softmax

    前文链接:https://write-bug.com/article/2467.html
    梯度下降BGD
    在前文中,我们通过梯度下降法最优化更新参数w,那么上节那种迭代的方法为BGD,批量梯度下降。这种方法每次都把所有数据集都遍历一遍,从而每次都可以更新最优的参数。这种方式比较慢,实用性差但是效果好。

    SGD
    正常工作中,我们通常使用SGD,随机梯度下降,此种方法快,使用当前数据集的最优参数通过多次迭代不断逼近全局最优值。

    MBGD
    工业界中,常用方法minibatch小批量梯度下降,把所有样本分为不同的批次依次执行BGD(参数不变一直更新同一参数),效果介于前两种之间的折中方式。


    高参:不是模型参数,又影响训练结果的因素,根据不同的任务,人工调节
    Learning rate:参数以多大的幅度利用梯度更新,即走的步长epoch:遍历所有样本次数Batch size :每个batch中包含多少个样本的个数
    Batch:批次,每次epoch中,包含多个batch
    Step:更新一次批量
    shuffle优化:每次取的样本做随机打乱

    更新过程:
    计算误差值,将误差作为参数计算梯度,将所有参数减去对应梯度乘以学习速率完成一次更新
    多分类Softmax逻辑回归是Softmax的一般形式。在二分类中我们求取p(y=1|x)=sigmoid(wx)的概率作为正例,同时只求一组w,b的权重就可以了。
    但是在多分类中,我们的分类集合为{1,2,3,4。。。。。k}应用:数字识别、文章分类等
    那么这时,我们就需要对这个样本属于每个分类都求取一组权重:
    P(y=1|x)—w1=e^(w1x)P(y=2|x)—w2=e^(w2x)P(y=3|x)—w3=e^(w3x)P(y=1|x)=w1/(w1+w2+w3)所以求取到的每个概率看那个概率最大就属于哪个类。
    在给定输入x,对每一个类别j估算出概率值为p(y=j|x)
    输出一个k维向量(元素和为1)来表示这k个估计的概率值

    向量中所有概率相加=1。
    我们知道,逻辑回归的损失函数是

    那么由此我们可推广出softmax回归损失函数:


    k:当前类别,m:真实label
    只不过是softmax对k个值进行累加,logic对2个值进行累加
    同样的,对损失函数求导得:

    这时,你可能会好奇,到底怎么logic就成了softmax的特殊情况了,若k=2,Softmax回归退化为logistic回归:

    两个参数向量均减去向量θ1:

    此时,就得到了两个参数组成的向量,此值就是原来的概率值。
    我们在上面得到了梯度公式,就可以通过每个类乘学习率,各自更新自己的权重,得到一列权重向量。
    L1、L2正则我们可以看到上面提出的三种梯度公式都有一个λw,而这个λw可加可不加,加了之后相当于每次迭代更新时都变相给各自的权重加了个约束,对于大部分训练,效果都会变好,即正则化项。

    λ:衰退权重
    常用正则化项:

    L1范数:λ|w| 又称lassoL2范数:λ|w|^2 又称ridge(岭回归)当然在训练中,L1和L2是可以加起来跑的。L1+L2:(梯度+L1+L2)

    在日常使用中,我们需要对所有维度做一个综合考虑,达到效果最好。假设分辨男女的特征,类似戴眼镜这种没有区分能力的特征我们需要把他的w学为0,还有如果我的w声音学到了1000,w身高学到了100,w体重学到了10,单纯看每一个特征它的w都比较合理,但是从整体来看,w小的特征就会被强特征淹没掉,比如前面这几个只要出现了声音特征可能就一定确认为男性。这样的效果并不是我们想要的,泛化能力弱。
    这个正则项就是对w的惩罚项,如果加了正则项就相当于压缩了w:
    L1:|w|<1L2:sqrt(|w|^2)<1W是一组向量在公式中与各自的X相乘作内积,那上面压缩了w就相当于对每个w乘一个相同小数,Wold和Wnew比例关系相同,那么和之前的wx就是一回事了。


    由上图,我们把每次w更新的值想象为等高线(效果相同),在同倍数缩小时,和L1,L2构成的图形相交(每次更新的w都和我们的λ有着直接联系,看如何选择最优那组w)达到限制w扩散过大的目的。同时从图形中我们可以看出一些特点:

    L1:w1+w2=1,某时w与其角上会重合,过小的w会被优化为0,形成稀疏矩阵
    从系统实现角度:大大减少参数存储空间(只存储有数部分)、针对性强,泛化能力好,防止过拟合
    L2: w1^2+w2^2=1,与圆相交相切几乎都不为0,不会产生稀疏矩阵,可以对一票否决权的这种权重惩罚的也大,让权值尽可能小,防止过拟合

    欠拟合、过拟合在大部分算法中,都存在过拟合问题,即一个模型在训练集上表现得非常好,但是在实际测试中效果差,将噪声一起学到了模型中

    上图中,既可以表现过拟合的现象,又是一种防止过拟合的方法:即交叉验证
    上面的线为测试集错误率,下面为训练集错误率,在训练的同时进行测试(每训练几轮测试一下),一旦测试集错误率上升,立即停止训练,防止过拟合。
    那么还有什么防止方法呢?

    筛选特征(过多特征的筛选、降维)
    人工筛选:根据时间、重要程度等等对特征进行优先级排列或筛选
    机器筛选(如mrMR信息增益(-决策树)):比如一个特征对男女判断是否有用,可以对其求auc

    特定模型方法
    增加惩罚项(L1、L2)
    决策树高度

    增加训练数据(万能)
    神经网络Dropout(减边)

    欠拟合:一般都是训练轮数不够,那么一般增加训练轮数和决策树拓展分支
    1 留言 2019-05-16 13:39:17 奖励16点积分
  • 机器学习 18、聚类算法-Kmeans

    前文链接:https://write-bug.com/article/2530.html
    上节 我们暂时实现了一下单机版推荐系统,并且串了下知识,这节介绍下聚类,说起聚类就得先提下监督和非监督式学习:

    监督式学习:我们之前学习的分类、回归问题中的排序模型LR、Softmax,包括后面的dnn,dt等等都是需要数据事先有一个标签label作为新特征的分类
    非监督式学习:而这个有些类似之前的推荐算法,并没有特定的类别作为比对

    而今天学习的算法聚类算法也是非监督式学习。
    聚类是什么?之前对于文本分类来说,需要事先设定好类别标签对新文本进行概率分类、对label对比,而这里的聚类则可以既不需要设定类别,也不需要事先设定文本中心,其可自动将数据划分到不同的类中,使相似的数据划分到相同的类中,这种方法可应用到几乎所有分类中,用户聚类、商品聚类、生物特征、基因、图像聚类等等分类。
    比如说,随机系统中有10000篇文章,我只告诉系统分为多少个类,其他什么都不告诉,这个系统就可以自动操作完成。
    事实上,就是对特征的向量化及空间划分。
    向量化如果想对一个文章、物品等作聚类,那聚类之前,如何表示文章呢?
    向量
    比如之前的tfidf,用一个向量来表示物品之后作cos、内积、计算质心等等
    质心:各个向量的点构成的空间的中心,即每个点到这个点的最短平均距离
    A:(a1, a2, a3)B:(b1, b2, b3)C:(c1, c2, c3)质心=( (a1+b1+c1)/3, (a2+b2+c2/3, (a3+b3+c3)/3)距离矩阵、相似度矩阵
    此矩阵就像之前的推荐算法中的矩阵,各个pair相似度的矩阵
    评估如何评估聚类效果?
    内部方法
    同类尽可能相似,不同类尽可能不相似

    分子为对象到质心距离和,越小越好
    分母为质心距离,越大越好
    外部方法(准确P、召回R)
    之前利用pr曲线找到最好的分类面,但是需要有监督的情况下才能用,这里如果想用,在特定情况下,比如说文章有固定标签,用这种方法训练后再告诉label评估效果,但是工作中几乎遇到的都是无标签的,所以这种方法是很鸡肋的方法,工作中基本用内部方法解决。
    F=PR /(P+R)聚类类别层次聚类


    自底向上凝聚聚类,从不同的对象凝聚结果形成聚合节点,成树状
    自顶向下分裂聚类,从一个对象分裂结果形成分裂节点,成树状

    优点:

    可通过阈值灵活控制类个数
    层次用于概念聚类,分类后人工对其打标签,抽象概念。

    凝聚实现:

    将每个对象样本分为一类,得到N个类
    找到最接近的两个类合并为一个类:两层for循环遍历所有样本,计算cos相似度
    重新计算新类与旧类之间距离:类别之间距离和类别与对象之间距离的计算方式一般使用组合链的方式进行计算:即类中质心距离(平均距离),而与之相对的有单链(最近距离)和全链(最远距离)两种方式,一般工作中就直接使用组合链方式
    重复直到最后合并为一个类
    复杂度O(n^3)

    非层次聚类:Kmeans
    层次聚类是一种需要将向量两两比较聚类的方法,但这种方法的计算时间过长,影响效率,而Kmeans是随机选择对象作为类别中心,然后优化这些中心点的位置,使尽可能收敛到和真实中心一致的算法。
    步骤:

    任意选择K个点作为初始聚类中心 (初始化类个数)
    根据每个聚类的中心,计算每个对象与这些中心的距离(cos、欧式距离),并根据 最小距离重新对相应对象进行划分

    欧式距离:A:(a1, a2, a3) B:(b1, b2, b3)距离=sqrt((a1-b1)^2 + (a2-b2)^2 + (a3-b3)^2 )
    重新计算每个聚类的中心 (更新质心计算)
    当满足一定条件,如类别划分不再发生变化时,算法终止,否则 继续步骤2和3
    复杂度:O(Ktn^2)K个点,n个对象,t次循环,n次计算质心

    之前介绍时为什么说是向量化并分割空间,下面这个图每个点都是空间中的向量点,把两个中心点相连,中心分割的垂线就是分割面,再迭代更新质心位置,从而分割空间


    一定条件:

    轮数
    WCSS损失函数:最小化簇内对象到质心的距离平方和

    wcss变小,即空间变化不剧烈

    缺点:过于依赖初始点选择,可能导致的结果大不一样
    解决方法:只能多训练几轮,求质心平均值或者选择最小的wcss的模型。
    模型:最终计算结果的K个中心点向量
    K选择,业务场景:
    举例:半个性化推荐,即热榜推荐列表只有一部分是个性化对用户的推荐(如视频网站首页上半部),但是当用户上亿,但热榜或首页展示目录只有10个,候选集合只有100个的时候怎么办?如何给大量的用户也做一个模糊的推荐?如何在100个候选集合中选择10个作为推荐列表?
    对上亿用户作聚类,可以随意聚几千个类,再用这几千个类的向量和每个物品向量作cos,选出分数前10的物品向量作为此用户类的候选集合。
    用户向量化:利用历史行为作用户画像:token作向量
    层次 vs Kmeans

    从上面两张图,我们可以看到右面Kmeans算法的暴力分割和缺点,在生活中的数据大部分都是球面原始数据,也是Kmeans的强项,左面的那种长条数据只能用层次聚类分辨出来,而与此同时左面五颜六色的单点都是噪音数据,前面说过层次聚类非常耗时,并且我们事先并不知道数据的分布,所以部分解决办法就是增加K类个数。
    Kmeans粒度比较粗,层次粒度比较细。
    聚类这种发现规律的分类效果永远无法赶上分类回归那种有监督式的效果,即有老师无老师的区别。如果效果不好,可以适当增加K个数增加准确率。
    0 留言 2019-05-29 15:55:53 奖励16点积分
  • 【Cocos Creator实战教程(3)】——TiledMap(瓦片地图)组件 精华

    1. 前言瓦片地图是由一张一张的正方形小图片拼接成的地图,例如炸弹人,QQ堂都是非常典型的瓦片游戏。瓦片地图(Tile Map) 不但生成简单,并且可以灵活的用于Cocos2d-x引擎。不论你的游戏是角色扮演游戏, 平台动作游戏或仿打砖块游戏,这些游戏地图可以使用开源的瓦片地图编辑器Tiled Map Editor生成并保存为TMX文件格式,被Cocos2d-x支持。
    2. 步骤2.1 安装Tiled Map Editoredit(编辑)->preferences(参数)里面可以设置语言
    2.2 TiledMap制作新建一张地图

    建立三个图层和一个对象层并将资源图块导入 (最下面的图层将显示在最下面)



    ground层:用ground图块填充满(按住鼠标左键)
    barriers层:用barrier图块
    stars层:用star图块

    最终效果如下图

    选择players对象层,在如图位置插入两个图块对象,并更改名称如图

    给星星添加一个属性

    保存为tmx文件,和图片文件放在一起
    2.3 Cocos Creator中使用TiledMap:
    新建一个TiledMapTest工程,创建一个Game场景
    将刚才生成的tmx文件和相关图片一起添加到工程
    将map.tmx文件拖入层级管理器或者属性编辑器,就会自动生成map节点以及其子节点(也就是图层节点)【没有对象层节点】
    最后将player(安卓小机器人)图片拖入(位置随意),创建player节点,并使其为map节点的子节点。
    调整map和player节点的锚点都为(0,0)也就是左下角
    创建map.js脚本添加到map节点

    cc.Class({ extends: cc.Component, properties: { }, // use this for initialization onLoad: function () { this.player = this.node.getChildByName('player'); this.loadMap(); cc.systemEvent.on(cc.SystemEvent.EventType.KEY_DOWN, this.onKeyDown, this); }, onKeyDown:function(event){ var newTile = cc.p(this.playerTile.x, this.playerTile.y); switch(event.keyCode) { case cc.KEY.up: newTile.y -= 1; break; case cc.KEY.down: newTile.y += 1; break; case cc.KEY.left: newTile.x -= 1; break; case cc.KEY.right: newTile.x += 1; break; default: return; } this.tryMoveToNewTile(newTile); }, //加载地图文件时调用 loadMap: function () { //初始化地图位置 this.node.setPosition(cc.visibleRect.bottomLeft); //地图 this.tiledMap = this.node.getComponent(cc.TiledMap); //players对象层 let players = this.tiledMap.getObjectGroup('players'); //startPoint和endPoint对象 let startPoint = players.getObject('startPoint'); let endPoint = players.getObject('endPoint'); //像素坐标 let startPos = cc.p(startPoint.offset.x, startPoint.offset.y); let endPos = cc.p(endPoint.offset.x, endPoint.offset.y); //障碍物图层和星星图层 this.barriers = this.tiledMap.getLayer('barriers'); this.stars = this.tiledMap.getLayer('stars'); //出生Tile和结束Tile this.playerTile = this.startTile = this.getTilePos(startPos); this.endTile = this.getTilePos(endPos); //更新player位置 this.updatePlayerPos(); }, tryMoveToNewTile: function(newTile) { let width = this.tiledMap.node.width; let height = this.tiledMap.node.height; if (newTile.x < 0 || newTile.x >= width) return; if (newTile.y < 0 || newTile.y >= height) return; if (this.barriers.getTileGIDAt(newTile)) {//GID=0,则该Tile为空 cc.log('This way is blocked!'); return false; } this.tryCatchStar(newTile); this.playerTile = newTile; this.updatePlayerPos(); if (cc.pointEqualToPoint(this.playerTile, this.endTile)) { cc.log('succeed'); } }, tryCatchStar: function(newTile){ let GID = this.stars.getTileGIDAt(newTile); let prop = this.tiledMap.getPropertiesForGID(GID); if (this.stars.getTileGIDAt(newTile)) {//GID=0,则该Tile为空 this.stars.removeTileAt(newTile); } }, //将像素坐标转化为瓦片坐标 getTilePos: function(posInPixel) { let mapSize = this.node.getContentSize(); let tileSize = this.tiledMap.getTileSize(); let x = Math.floor(posInPixel.x / tileSize.width); let y = Math.floor(posInPixel.y / tileSize.height); return cc.p(x, y); }, updatePlayerPos: function() { let pos = this.barriers.getPositionAt(this.playerTile); this.player.setPosition(pos); },});
    最终如下图:

    3. 总结#CC.TiledMap:~properties:tmxFile//地图文件mapLoaded//地图加载是调用的函数~function:getMapSize()//setMapSize()//getTileSize()//setTileSize()//getLayer(name)//returns TieldLayergetObjectGroup(name)//returns TMXObjectGroupgetPropertiesForGID(GID)//returns Object(属性字典)#CC.TieldLayer getPositionAt(pos)//returns Vec2(像素坐标) 参数是瓦片坐标removeTileAt(pos)//瓦片坐标getTileGIDAt(pos)//returns Number(全局唯一标识,0为空)getTileAt(pos)//returns _ccsg.Sprite //removeChild(sprite);setTileGID(gid,pos)//相当于在pos位置添加GID的图块(原来的图块删除)getTileSize()//setTleSize()//getMapTileSize()#TMXObjectGroup:~properties:~function:var getObject(var objectName)//返回属性字典#_ccsg.Sprite://cocos js 里的Sprite,继承自CC.Node,而不是组件~properties:xywidthheightopacity...//节点的属性都有~function:var setSpriteFrame(var spriteFrameName)var runAction(var action) ...//节点的方法都有

    图块放置的位置是基于像素坐标,而图块在map中的索引是基于瓦片坐标(整数),所以在脚本文件中要适时转变
    对象层的对象(比如我们上面做的两个player point),在Cocos Creator中是不会显示的
    对象层记录的是位置信息,图层记录的是图片信息
    .tmx文件其实保存的图块的一种映射关系,所以图块文件和地图文件要始终放在一起,不然可能会显示出错
    GID是图块在一个地图文件中的唯一ID,(图块指的是右下角的图块文件,每一个图块都不相同,瓦片指的指地图中的块,可以是相同的图块),GID为0说明该Tile的图块为空
    当利用getPropertiesForGID(GID)之类的方法时,得到的返回值是属性字典,可以直接通过点方法得到其属性值,属性值都是字符串类型
    当用到getTileAt(pos)时,得到的返回值是Cocos2d 的Sprite,而不是Cocos Creator的Sprite,相关方法可以查找Cocos2d js的API,需要注意的一点是,Cocos2d的Sprite是继承自节点的,而不是组件式,所以我们可以直接这样写“mySprite.x = 100”而不是“mySprite.node.x = 100”
    地图中同一层只能使用一张图集里的图块

    注意:本教程资源部分来源于网络
    2 留言 2018-11-24 18:06:17 奖励15点积分
  • 计算机视觉现代优化方法

    1. 概述本次实验中,我基于OpenCV,实现了一个二维图像配准工具,全部代码均为自行实现,OpenCV用于计算图像变换与相似度。
    该工具能够将一幅图像进行变换,并与另一幅图像相匹配。支持包括平移、旋转(含平移、缩放)、仿射与透视共四种变换,使用L1、L2、无穷范数作为优化的目标函数,实现了暴力算法、梯度下降法、模拟退火算法来求解该优化问题。
    2. 应用问题如果两幅图像,它们是在同一场景、不同角度下拍摄的,那么,存在一种图像变换,使得其中一幅图像经过变换后,能与另一图像大部分重合。
    上述图像变换被称为配准(registration)T,被变换的图像被称为参考图像I_M,另一图像被称为目标图像I_F。优化的目标是使变换后的参考图像T(I_M)与目标图像I_F的差异尽可能低。
    最简单的图像变换是平移变换,需要确定两个参数: x和 y; 旋转变换通常与缩放、平移共同进行,需要确定四个参数: x、y、theta、scale; 仿射变换将矩形图像线性映射至一个平行四边形,需要确定三个坐标点,共六个参数,三个坐标点分别表示原图左上、右上、左下角变换至新图像的坐标位置; 透视变换与仿射变换相似,不同的是原图像的四个顶点可变换至任意的四边形,所以需要确定四个坐标点,共八个参数。此外,也有更为精细的图像变换方法,但相比于上述简单变换,其参数较多,难以优化,故本次实验不予考虑。
    对于图像相似度,需针对使用场景选择合适的度量方法。本实验中,实现的方法有L1(1范数)、L2(2范数)、无穷范数三种。
    总的来说,问题可以总结为如下步骤:

    输入参考图像、目标图像;
    选择合适的变换,确定参数范围;
    设置初始参数,在这个参数下变换参考图像,并计算与目标图像的差异;
    调整参数,使上述差异达到最小值;
    输出最优参数作为配准变换。

    3. 数据来源本实验使用在实验室拍摄的四张照片作为测试数据。














    4. 实现算法4.1 软件界面本实验搭建了一个二维图像配准工具。”主界面”可进行配准的各项设置,并展示参考图像与目标图像:

    “结果界面”会在运行配准之后弹出,分左中右三栏,分别为变换后的参考图像、变换后的参考图像与目标图像的对比(会交替显示两图像)、目标函数优化曲线:

    4.2 优化算法在上述基础上实现了三种优化算法,分别是暴力算法、梯度下降法、模拟退火算法。执行算法前,首先会在Registration::initialize()函数中针对不同变换方式,初始化变换的各项参数,例如旋转变换(四个参数):
    params.resize(4); // cx cy angle scalelimits.resize(4);steps.resize(4);limits[0] = std::make_pair(-c / 2, c / 2);limits[1] = std::make_pair(-r / 2, r / 2);limits[2] = std::make_pair(-180, 180);limits[3] = std::make_pair(0.5, 2);for (int i = 0; i < params.size(); i++) { params[i] = limits[i].first;}steps[0] = 1;steps[1] = 1;steps[2] = 1;steps[3] = 0.01;
    其中params表示参数数组,limits表示各个参数的取值范围,steps表示各个参数邻域的步长。
    暴力算法使用深度优先搜索遍历整个可行解空间,可求解出全局的最优解:
    void Registration::optimizeNaive(int pos) { if (pos >= params.size()) { completeIteration(); return; } for (float i = limits[pos].first; i <= limits[pos].second; i += steps[pos]) { params[pos] = i; optimizeNaive(pos + 1); }}
    梯度下降法在每轮迭代中,寻找当前最优解的邻域中最优的可行解,并以此代替最优解,直到邻域中没有比当前解更好的解为止。我实现的函数中,某个可行解的邻域定义为将第i个参数增加或减少steps[i]得到的可行解的集合(i为某个随机参数的序号)。因梯度下降法与初始值选取密切相关,选择不当会导致陷入局部最优解,我在函数中增加了一个外循环,每轮循环随机选择一组初始值,并开始一轮新的梯度下降:
    void Registration::optimizeGD() { for (int i = 0; i < 10000; i++) { double tmp_loss = 1e30; double cur_loss = 1e30; for (int j = 0; j < params.size(); j++) { // give random start values params[j] = random(limits[j].first, limits[j].second); } while (true) { std::vector<float> old = params; std::vector<float> best = params; for (int pos = 0; pos < params.size(); pos++) { params[pos] = old[pos] + steps[pos]; optimizeGDHelper(best, cur_loss); params[pos] = old[pos] - steps[pos]; optimizeGDHelper(best, cur_loss); params[pos] = old[pos]; } if (tmp_loss == cur_loss) { break; } tmp_loss = cur_loss; params = best; completeIteration(); } completeIteration(); }}void Registration::optimizeGDHelper(std::vector<float>& best, double& cur_loss) { applyTransform(); double s = getSimilarity(trans_img, tar_img, similarity_type); if (s < cur_loss) { cur_loss = s; best = params; }}
    模拟退火算法与梯度下降法相比,具有跳出局部最优解的能力。当温度较低时,算法不容易跳出局部最优解,从而退化为梯度下降法。所以,如果在温度下降到很低时没能跳入最优解附近,算法同样会收敛于局部最优解。因此,与上述梯度下降法的代码类似,我也使用了一层外循环,用于生成多个随机初始参数:
    void Registration::optimizeSA() { for (int i = 0; i < 10000; i++) { for (int j = 0; j < params.size(); j++) { // give random start values params[j] = random(limits[j].first, limits[j].second); } applyTransform(); double fi = getSimilarity(trans_img, tar_img, similarity_type); double temp = 10; double r = 0.99; int k = 1000; while (k > 0) { // select a random neighbor int len = params.size(); int r1 = rand() % len; double r2 = random(1, 10) * ((rand() % 2) * 2 - 1); params[r1] += r2 * steps[r1]; applyTransform(); double fj = getSimilarity(trans_img, tar_img, similarity_type); double delta = fj - fi; if (random(0, 1) < exp(-delta / temp)) { // jump to this neighbor completeIteration(iter % 10 == 0); fi = fj; } else { params[r1] -= r2 * steps[r1]; } temp *= r; k--; } completeIteration(); }}
    4.3 实现细节
    计算图像变换、图像相似度需要遍历图像每一像素,这一过程是较为耗时的。对此,代码中将图像先缩小至原有尺寸的1/10,即,像素数变为原来的1/100,再进行变换、相似度计算。最终再恢复至原有图像尺寸。
    图像变换后,其周围可能出现空白区域(下图),在计算图像相似度时,这一区域也是需要计算的(否则会倾向于生成全是边界的图像),所以需要填补这一区域。我使用的方法是计算全图像的平均颜色,并以平均颜色填补。


    5. 实验结果与分析5.1 目标函数值可视化下图展示了4号图片到1号图片的平移变换的优化目标函数值。平移变换有两个参数,所以可以映射到二维空间。使用上述暴力算法计算出参考图像平移至所有位置,计算其目标函数值,便得到如下的可视化结果。
    从图中可以看出目标函数最优值(最小值)位于图像中间附近,有局部最优值,但该函数较为光滑,因此可认为性质较好。

    5.2 结果5.2.1 暴力算法暴力算法效率较低,所以只进行了平移变换、旋转变换的实验。其中,平移变换约耗时3秒,旋转变换耗时数分钟。
    该算法可以确保找到最优解,可作为其他算法的验证手段。
    下图是枚举平移变换参数时,相似度函数的变化曲线:

    5.2.2 梯度下降法下图是使用梯度下降法优化仿射变换配准问题的结果,在迭代至5000轮左右时,已经找到较好的结果。这里,每一轮迭代指的是找到一个新的最优值,或开启一次新的梯度下降。
    右侧的蓝色曲线表示梯度下降过程的目标函数值变化,可以看出,在每轮梯度下降过程内,目标函数值能够快速下降。

    5.2.3 模拟退火算法下图使用了模拟退火算法来计算5.2.2中相同的优化问题以便对比。该方法约在4000轮左右取得一个较好的解,更好的解出现在50000轮左右。
    相比于梯度下降法,模拟退火在每轮迭代中不需要计算所有邻域解,而梯度下降计算数量为参数个数*2,所以模拟退火的迭代速度高于梯度下降。
    为了使两次模拟退火之间可以区分,我在两次模拟退火的能量函数之间插入了一个峰值。观察蓝色曲线可以发现,每次运行模拟退火时,前期能量函数波动较大(因为跳到更差的解的几率很大),在后期逐渐趋于稳定,类似梯度下降的结果。

    5.3 参数调整三种算法中,只有模拟退火算法有需要调整的参数。包括迭代次数k、初始温度temp与温度衰减系数r。
    k控制何时停止迭代,根据曲线取值即可。
    起初不知道如何设置初始温度与衰减系数,将温度设置得很高,衰减也很快,然后发现优化效果不如梯度下降法。分析各个参数的作用与模拟退火算法的优势之后,我得到结论:

    初始温度应与目标函数值在同一量级;
    衰减系数应调整到使得温度在进行了一半的迭代轮数之后下降到足够低,进而使得优化只向更优的可行解跳跃。

    最终的曲线和期望一致,一开始有较大的波动,随后逐渐稳定直至收敛。
    5.4 分析与结论本次实验我得到了如下结论:

    经过对比试验,对于二维照片配准问题,使用2范数作为相似性度量函数的效果较好,其次是1范数。
    参数空间的邻域结构非常重要。例如仿射变换矩阵尺寸为2*3,有六个参数,若直接优化这六个参数,则优化结果较差,很难收敛到最优解。原因可能是这六个参数的现实意义不够明确(例如,增大第一个参数会使图像怎样变化),且参数之间存在较大关联性(例如,同时增大第一个、第五个参数,作用是放大图像,而只改变一个则图像会变得不自然)。仿射变换的另一种表示方式是,原图像的左上、右上、左下三个顶点分别变换到了新图像的哪些位置,同样需要六个参数描述,但这些参数的可解释性更强,目标函数也更容易优化至最优。实验发现,选择合适的参数能够让目标函数的性质更好,更容易收敛到全局最优解。
    模拟退火算法在图像配准问题上的优势不明显。对于特别不光滑的目标函数,梯度下降算法是无能无力的,因为选择一个随机初始值下降至全局最优值的概率非常低。而模拟退火算法有助于跳出这些波动,相比梯度下降法更容易得到最优解。但是对于图像配准问题,其目标函数性质较好,局部最优解较少。于是,多次使用梯度下降算法也能够找到全局最优解,模拟退火算法的优势难以体现。
    0 留言 2019-06-16 23:22:40 奖励20点积分
  • 基于python构建搜索引擎系列——(六)系统展示及总结

    系统展示前几个博客已经介绍完搜索引擎的所有功能,为了实现更好的用户体验,需要一个web界面。这一部分是另一个队员做的,我这里借用他的代码。
    我们利用开源的Flask Web框架搭建了展示系统,搜索引擎只需要两个界面,一个是搜索界面,另一个是展示详细新闻的页面(实际搜索引擎没有这个页面)。编写好这两个模板页面并调用前面给出的接口,得到数据,展示出来就可以。
    这一部分没有太多需要讲解的算法,直接上效果图(点击图片可以查看大图)。


    由于数据量不大,只有1000条新闻,所以第一页中后面几个结果相关度就不是很高了。但是经过测试,在大数据量的情况下,不论是搜索的速度、准确率、召回率以及推荐阅读的相关度,都达到了不错的效果。
    总结至此,整个新闻搜索引擎构建完毕,总体效果令人满意,不过还是有很多可以改进的地方。下面总结一下本系统的优点和不足。
    优点倒排索引存储方式。因为不同词项的倒排记录表长度一般不同,所以没办法以常规的方式存入关系型数据库。通过将一个词项的倒排记录表序列化成一个字符串再存入数据库,读取的时候通过反序列化获得相关数据,整个结构类似于邻接表的形式。
    推荐阅读实现方式。利用特征提取的方法,用25个关键词表示一篇新闻,大大减小了文档词项矩阵规模,提高计算效率的同时不影响推荐新闻相关性。
    借用了Reddit的热度公式,融合了时间因素。
    不足构建索引时,为了降低索引规模,提高算法速度,我们将纯数字词项过滤了,同时忽略了词项大小写。虽然索引规模下降了,但是牺牲了搜索引擎的正确率。
    构建索引时,采用了jieba的精确分词模式,比如句子“我来到北京清华大学”的分词结果为“我/ 来到/ 北京/ 清华大学”,“清华大学”作为一个整体被当作一个词项,如果搜索关键词是“清华”,则该句子不能匹配,但显然这个句子和“清华”相关。所以后续可以采用结巴的搜索引擎分词模式,虽然索引规模增加了,但能提升搜索引擎的召回率。
    在推荐阅读模块,虽然进行了维度约减,但是当数据量较大时(数十万条新闻),得到的文档词项矩阵也是巨大的,会远远超过现有PC的内存大小。所以可以先对新闻进行粗略的聚类,再在类内计算两两cosine相似度,得到值得推荐的新闻。
    在热度公式中,虽然借用了Reddit的公式,大的方向是正确的,但是引入了参数k1k1和k2k2,而且将其简单的设置为1。如果能够由专家给出或者经过机器学习训练得到,则热度公式的效果会更好。
    本文转载自:

    http://bitjoy.net/2016/01/09/introduction-to-building-a-search-engine-6
    http://bitjoy.net/2016/01/09/introduction-to-building-a-search-engine-7
    1 留言 2019-06-06 17:05:21 奖励12点积分
  • 基于python构建搜索引擎系列——(五)推荐阅读 精华

    虽然主要的检索功能实现了,但是我们还需要一个“推荐阅读”的功能。当用户浏览某条具体新闻时,我们在页面底端给出5条和该新闻相关的新闻,也就是一个最简单的推荐系统。

    推荐模块的思路是度量两两新闻之间的相似度,取相似度最高的前5篇新闻作为推荐阅读的新闻。
    我们前面讲过,一篇文档可以用一个向量表示,向量中的每个值是不同词项t在该文档d中的词频tf。但是一篇较短的文档(如新闻)的关键词并不多,所以我们可以提取每篇新闻的关键词,用这些关键词的tfidf值构成文档的向量表示,这样能够大大减少相似度计算量,同时保持较好的推荐效果。
    jieba分词组件自带关键词提取功能,并能返回关键词的tfidf值。所以对每篇新闻,我们先提取tfidf得分最高的前25个关键词,用这25个关键词的tfidf值作为文档的向量表示。由此能够得到一个1000*m的文档词项矩阵M,矩阵每行表示一个文档,每列表示一个词项,m为1000个文档的所有互异的关键词(大概10000个)。矩阵M当然也是稀疏矩阵。
    得到文档词项矩阵M之后,我们利用sklearn的pairwise_distances函数计算M中行向量之间的cosine相似度,对每个文档,得到与其最相似的前5篇新闻id,并把结果写入数据库。
    推荐阅读模块的代码如下:
    from os import listdirimport xml.etree.ElementTree as ETimport jiebaimport jieba.analyseimport sqlite3import configparserfrom datetime import *import mathimport pandas as pdimport numpy as npfrom sklearn.metrics import pairwise_distancesclass RecommendationModule: stop_words = set() k_nearest = [] config_path = '' config_encoding = '' doc_dir_path = '' doc_encoding = '' stop_words_path = '' stop_words_encoding = '' idf_path = '' db_path = '' def __init__(self, config_path, config_encoding): self.config_path = config_path self.config_encoding = config_encoding config = configparser.ConfigParser() config.read(config_path, config_encoding) self.doc_dir_path = config['DEFAULT']['doc_dir_path'] self.doc_encoding = config['DEFAULT']['doc_encoding'] self.stop_words_path = config['DEFAULT']['stop_words_path'] self.stop_words_encoding = config['DEFAULT']['stop_words_encoding'] self.idf_path = config['DEFAULT']['idf_path'] self.db_path = config['DEFAULT']['db_path'] f = open(self.stop_words_path, encoding = self.stop_words_encoding) words = f.read() self.stop_words = set(words.split('\n')) def write_k_nearest_matrix_to_db(self): conn = sqlite3.connect(self.db_path) c = conn.cursor() c.execute('''DROP TABLE IF EXISTS knearest''') c.execute('''CREATE TABLE knearest (id INTEGER PRIMARY KEY, first INTEGER, second INTEGER, third INTEGER, fourth INTEGER, fifth INTEGER)''') for docid, doclist in self.k_nearest: c.execute("INSERT INTO knearest VALUES (?, ?, ?, ?, ?, ?)", tuple([docid] + doclist)) conn.commit() conn.close() def is_number(self, s): try: float(s) return True except ValueError: return False def construct_dt_matrix(self, files, topK = 200): jieba.analyse.set_stop_words(self.stop_words_path) jieba.analyse.set_idf_path(self.idf_path) M = len(files) N = 1 terms = {} dt = [] for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text docid = int(root.find('id').text) tags = jieba.analyse.extract_tags(title + '。' + body, topK=topK, withWeight=True) #tags = jieba.analyse.extract_tags(title, topK=topK, withWeight=True) cleaned_dict = {} for word, tfidf in tags: word = word.strip().lower() if word == '' or self.is_number(word): continue cleaned_dict[word] = tfidf if word not in terms: terms[word] = N N += 1 dt.append([docid, cleaned_dict]) dt_matrix = [[0 for i in range(N)] for j in range(M)] i =0 for docid, t_tfidf in dt: dt_matrix[i][0] = docid for term, tfidf in t_tfidf.items(): dt_matrix[i][terms[term]] = tfidf i += 1 dt_matrix = pd.DataFrame(dt_matrix) dt_matrix.index = dt_matrix[0] print('dt_matrix shape:(%d %d)'%(dt_matrix.shape)) return dt_matrix def construct_k_nearest_matrix(self, dt_matrix, k): tmp = np.array(1 - pairwise_distances(dt_matrix[dt_matrix.columns[1:]], metric = "cosine")) similarity_matrix = pd.DataFrame(tmp, index = dt_matrix.index.tolist(), columns = dt_matrix.index.tolist()) for i in similarity_matrix.index: tmp = [int(i),[]] j = 0 while j < k: max_col = similarity_matrix.loc[i].idxmax(axis = 1) similarity_matrix.loc[i][max_col] = -1 if max_col != i: tmp[1].append(int(max_col)) #max column name j += 1 self.k_nearest.append(tmp) def gen_idf_file(self): files = listdir(self.doc_dir_path) n = float(len(files)) idf = {} for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text seg_list = jieba.lcut(title + '。' + body, cut_all=False) seg_list = set(seg_list) - self.stop_words for word in seg_list: word = word.strip().lower() if word == '' or self.is_number(word): continue if word not in idf: idf[word] = 1 else: idf[word] = idf[word] + 1 idf_file = open(self.idf_path, 'w', encoding = 'utf-8') for word, df in idf.items(): idf_file.write('%s %.9f\n'%(word, math.log(n / df))) idf_file.close() def find_k_nearest(self, k, topK): self.gen_idf_file() files = listdir(self.doc_dir_path) dt_matrix = self.construct_dt_matrix(files, topK) self.construct_k_nearest_matrix(dt_matrix, k) self.write_k_nearest_matrix_to_db()if __name__ == "__main__": print('-----start time: %s-----'%(datetime.today())) rm = RecommendationModule('../config.ini', 'utf-8') rm.find_k_nearest(5, 25) print('-----finish time: %s-----'%(datetime.today()))
    这个模块的代码量最多,主要原因是需要构建文档词项矩阵,并且计算k邻居矩阵。矩阵数据结构的设计需要特别注意,否则会严重影响系统的效率。我刚开始把任务都扔给了pandas.DataFrame,后来发现当两个文档向量合并时,需要join连接操作,当数据量很大时,非常耗时,所以改成了先用python原始的list存储,最后一次性构造一个完整的pandas.DataFrame,速度比之前快了不少。
    本文转载自:http://bitjoy.net/2016/01/09/introduction-to-building-a-search-engine-5
    1 留言 2019-06-03 15:49:20 奖励14点积分
  • 基于python构建搜索引擎系列——(四)检索模型 精华

    构建好倒排索引之后,就可以开始检索了。
    检索模型有很多,比如向量空间模型、概率模型、语言模型等。其中最有名的、检索效果最好的是基于概率的BM25模型。
    给定一个查询Q和一篇文档d,d对Q的BM25得分公式为:

    公式中变量含义如下:

    qtf:查询中的词频
    tf:文档中的词频
    ld:文档长度
    avg_l:平均文档长度
    N:文档数量
    df:文档频率
    b,k1,k3:可调参数

    这个公式看起来很复杂,我们把它分解一下,其实很容易理解。第一个公式是外部公式,一个查询Q可能包含多个词项,比如“苹果手机”就包含“苹果”和“手机”两个词项,我们需要分别计算“苹果”和“手机”对某个文档d的贡献分数w(t,d),然后将他们加起来就是整个文档d相对于查询Q的得分。
    第二个公式就是计算某个词项t在文档d中的得分,它包括三个部分。第一个部分是词项t在查询Q中的得分,比如查询“中国人说中国话”中“中国”出现了两次,此时qtf=2,说明这个查询希望找到的文档和“中国”更相关,“中国”的权重应该更大,但是通常情况下,查询Q都很短,而且不太可能包含相同的词项,所以这个因子是一个常数,我们在实现的时候可以忽略。
    第二部分类似于TFIDF模型中的TF项。也就是说某个词项t在文档d中出现次数越多,则t越重要,但是文档长度越长,tf也倾向于变大,所以使用文档长度除以平均长度ld/avg_l起到某种归一化的效果,k1和b是可调参数。
    第三部分类似于TFIDF模型中的IDF项。也就是说虽然“的”、“地”、“得”等停用词在某文档d中出现的次数很多,但是他们在很多文档中都出现过,所以这些词对d的贡献分并不高,接近于0;反而那些很稀有的词如”糖尿病“能够很好的区分不同文档,这些词对文档的贡献分应该较高。
    所以根据BM25公式,我们可以很快计算出不同文档t对查询Q的得分情况,然后按得分高低排序给出结果。
    下面是给定一个查询句子sentence,根据BM25公式给出文档排名的函数:
    def result_by_BM25(self, sentence): seg_list = jieba.lcut(sentence, cut_all=False) n, cleaned_dict = self.clean_list(seg_list) BM25_scores = {} for term in cleaned_dict.keys(): r = self.fetch_from_db(term) if r is None: continue df = r[1] w = math.log2((self.N - df + 0.5) / (df + 0.5)) docs = r[2].split('\n') for doc in docs: docid, date_time, tf, ld = doc.split('\t') docid = int(docid) tf = int(tf) ld = int(ld) s = (self.K1 * tf * w) / (tf + self.K1 * (1 - self.B + self.B * ld / self.AVG_L)) if docid in BM25_scores: BM25_scores[docid] = BM25_scores[docid] + s else: BM25_scores[docid] = s BM25_scores = sorted(BM25_scores.items(), key = operator.itemgetter(1)) BM25_scores.reverse() if len(BM25_scores) == 0: return 0, [] else: return 1, BM25_scores
    首先将句子分词得到所有查询词项,然后从数据库中取出词项对应的倒排记录表,对记录表中的所有文档,计算其BM25得分,最后按得分高低排序作为查询结果。
    类似的,我们还可以对所有文档按时间先后顺序排序,越新鲜的新闻排名越高;还可以按新闻的热度排序,越热门的新闻排名越高。
    关于热度公式,我们认为一方面要兼顾相关度,另一方面也要考虑时间因素,所以是BM25打分和时间打分的一个综合。
    比较有名的热度公式有两个,一个是Hacker News的,另一个是Reddit的,他们的公式分别为:


    可以看出,他们都是将新闻/评论的一个原始得分和时间组合起来,只是一个用除法,一个用加法。所以我们也依葫芦画瓢,”自创“了一个简单的热度公式:

    用BM25得分加上新闻时间和当前时间的差值的倒数,k1k1和k2k2也是可调参数。
    按时间排序和按热度排序的函数和按BM25打分排序的函数类似,这里就不贴出来了,详细情况可以看我的项目News_IR_Demo。
    至此,搜索引擎的搜索功能已经实现了,你可以试着修改./web/search_engine.py的第167行的关键词,看看搜索结果是否和你预想的排序是一样的。不过由于我们的数据量只有1000个新闻,并不能涵盖所有关键词,更多的测试可以留给大家线下完成。
    本文转载自:http://bitjoy.net/2016/01/07/introduction-to-building-a-search-engine-4
    1 留言 2019-06-01 15:29:45 奖励14点积分
显示 0 到 15 ,共 15 条
eject