liuzhiqiangruc
liuzhiqiangruc · 共 55 篇文章
深入理解GBDT
GBDT 全称为 Gradient Boosting Decision Tree。顾名思义,它是一种基于决策树(decision tree)实现的分类回归算法。不难发现,GBDT 有两部分组成: gradient boosting, decision tree。Boosting 作为一种模型组合方式,与gradient descent 有很深的渊源,它们之间究竟有什么关系?同时 decisiontree 作为一种 base weak learner,又是如何通过 boosting 组装成一个强分类器?本文就通过回答这两个问题来深入了解下 GBDT 的“面子”和“里子”。 Gradient D…
决策树的数学原理
说到决策树,大家肯定不陌生,由于其结构简单,学习成本低,且可解释性强,有着广泛的应用。 因此各类书籍、技术博客都有介绍,且深入浅出、图文并茂、生动形象。 鉴于已经有很多带图的博客介绍决策树,这里就不上图了,主要以公式推导为主。 本文主要分三块内容来介绍决策树: 首先会简单回顾下决策树的内容,由于这部分相对简单,大家了解的也多,因此会快速过一遍。 随后本文会对决策树的数学原理做详尽的剖析和推导,这也是本文的重点,做到知其然更知其所以然。 最后是决策树在工业应用中常见的一些形态,这部分内容在本文不做详细展开,留在后续文章中详述。 决策树的构建 通俗来讲,决策树的构建过程就是将数据根据其特征分布划…
时间序列分段算法 [Time series Breakout Detection]
在时间序列分析中,断点检测(breakout detection)是一个很基本的问题。 通过捕捉时序数据中的断点(breakout),来发现时序数据所表示的系统在过去是否发生了某种事件(event),进而为系统诊断提供必要的数据支持。 为了实现对时序断点的检测,我们首先需要对时序的整体时序做拟合。 这里我们通过一条直线来拟合一段时序,如果时序的趋势发生了变化,则用多条直线来拟合整条时序数据。 如下是对一条波动规律明显的时序做拟合之后的结果。 每个红色线条的转折点,就是我们找到的断点。 以上数据是我们在实验环境下,为了检测算法效果而人工构造的一条时序。 那么,该算法在实际情况下表现如何? 一下…
2015-12-15 20:01 · 时间序列 · 动态规划 · 线性回归 · 断点检测 · BreakoutDetection · 评论(0)
会计记账小程序
许久不来,手都有些生疏了。 写个小程序热热手先。 假设有一个数字,可以很大,理论上可以无限大。要如何转成其对应的汉子大写? 就是那种支票本上、汇款单上的那种大写金额。 例如: 数字:193817071803800182801088108 大写:壹佰玖拾叁亿捌仟壹佰柒拾万柒仟壹佰捌拾亿叁仟捌佰万壹仟捌佰贰拾捌亿零壹佰零捌万捌仟壹佰零捌 代码: #include <stdio.h> #include <string.h> static const char code[9][4]= {"壹", "贰", "叁", "肆", "伍", "陆", "柒", "捌", "玖"}; void bit_4(…
大数据杂谈
谈到大数据,让我想起了一个段子,说人们谈大数据就像青少年谈性爱,每个人都谈的头头是道,但都不知道对方说的是什么玩意,同时还要装做自己都听懂了。 好在这些曾经的青少年,有的也已经过了成人礼,或多或少的有了一些经验,没有了当初的青涩和懵懂,也没有当初那么健谈。 再说起大数据时,已经从最开始的狂热,逐步变得理性,或者有意地做理性的思考。 这不光是大数据,几乎所有的概念、技术出来都会经历这样一个过程,恍如曾经的面向对象、设计模式、ajax、数据仓库、推荐系统、互联网+,,,,都不可避免的走这么一遭。 这有点像机器学习中的退火算法,要想求得最优解,需要将初始解“加热”到随机态。 退火这个概念是从物理学…
2015-05-01 15:58 · 杂项 · 评论(0)
Viterbi 算法应用实现
算法简介: Viterbi 算法又叫维特比算法,其是HMM模型中在给出观测序列O,以及状态转移举证M 和 状态-观测矩阵Q之后,求解能够最佳解释序列O的状态序列S的一种动态规划算法。 具体如下图所示: 其中: 标记为O的 [0|1] 序列是观测序列, 标记为S的序列中横向的箭头即状态在根据转移矩阵M进行转移, 其中S序列与O序列之间向下的箭头表示根据状态生成观测的概率,也即Q矩阵。 假设我们已知观测序列O,即图片Bottom位置的0、1序列,则图片Top位置的用红框框起来的0、1序列就是对应的S序列,即我们所说的在给定矩阵M和Q之后,能最佳地解释O的序列。 算法实现: 算法的实现也很简单,主…
DTW算法时序应用与实现
关于dtw算法: dtw算法最初应用于语音识别中的孤音识别。 即已知某个词的音频模板,给定一个新的音频序列之后, 通过检测该词的音频模板与新音频序列之间的相似度,来判断该音频是否是该词。 问题在于,即使是同一个词,由于人的发音有语速、节奏、习惯的不同,其音频也不可能完全一致。 这种不一致,体现在序列长度、某个音节的音长等方面。 DTW(动态时间规整)算法应运而生: 通过将待比较的两个序列在时间维度上进行拉升、压缩操作,使其具有相同长度的同时,具有可能的最好的匹配度。 时序比较问题: 时间序列分析过程中,不可避免地需要计算两条时序的相似度或距离,用以解决诸如匹配、聚类等问题。 在时序数据的距离…
关于连续值离散化[MODL]
将连续值离散化的问题,在数据挖掘和机器学习的任务中并不鲜见,当然离散化的方法也有很多。 本文将要介绍的是一种基于数据标签(label)来对连续数据值做离散化分割的监督学习方法。 问题: 考虑有如下数据: 1,0 2,0 3,0 4,0 5,0 6,1 7,1 8,1 9,1 10,1 第一列是连续值数据,而第二列是数据的类别标签(label) 我们希望对数据进行划分,使得划分的结果符合数据的类标签的分布。 即,预期前5个值为一段,后5个值为另一段。 这个问题可能有点太naive,明眼人只要看一眼即可准确地将数据按照需要的方式划分。 可是,我们需要机器像人一样聪明,能做出同样的判断,而且能将这…
谱聚类算法实现
谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法。 将带权无向图划分为两个或两个以上的最优子图,使子图内部尽量相似,而子图间距离尽量距离较远,以达到常见的聚类的目的。 "带权无向图"这个词太学术了,我们换一种叫法,即:相似度矩阵。 假设我们有一个相似度矩阵,矩阵中存的是所有对象的两两相似度。 那么这个矩阵应该有如下性质: 矩阵为N * N,N为对象总数 矩阵对角线的值为0,自己和自己相似个毛啊 矩阵为对称矩阵,及相似度是无向的 我们将该矩阵记为:W。 谱聚类的任务就是根据这个相似度矩阵,将这一大堆对象,分成不同的小堆,小堆内部的对象彼此都很像,小堆之间则不像。…
白话NMF(Non-negative Matrix Factorization)——Matlab 实现
NMF——非负矩阵分解。如果你事先了解PMF[概率矩阵分解]的话,那么其实只要在PMF的基础上多加上一点,就是NMF了。 方法一: 在PMF中使用SGD【随机梯度下降】进行优化时,使用如下的迭代公式: 其中P、Q分别代表原始矩阵R的两个维度的隐含矩阵,在推荐应用中,一般讲P看做用户矩阵、Q看做物品矩阵。 从公式中不难看出,无论P矩阵还是Q矩阵都会出现负值的情况,上述公式并未对P、Q矩阵的值做任何限制。 在应用中,有时候需要分解出来的矩阵中不存在小于0的值,也即要求所有值非负。 怎么做到呢?其实很简单,在上述两个迭代公式中加个约束即可,如下公式: 很简单,是吧。这其实是非负矩阵分解实现中最常用…
BPR [Bayesian Personalized Ranking] 算法详解及应用实践
在推荐系统的实现中,几乎总会遇到从较多候选集中为用户选取特定的少数几个物品进行推荐,这本质上是一个Ranking问题。 在推荐场景中用户更缺乏耐性,对推荐结果的消费也十分有限。因此,排序的好坏直接决定了用户对一个准确率为90%的推荐候选集的满意度是否真的有90%。 这里我们为大家介绍一种“基于贝叶斯后验优化的个性化排序算法”: Bayesian Personalized Ranking 。 其本身并不优化用户对物品的评分,而只藉由评分来优化用户对物品的排序。按照论文的说法:it is a real ranking algorithm. BPR算法过程详解: 数据pair化预处理: BPR算法…
【0-1】矩阵分解
基于矩阵分解的推荐算法已经在工业界被广泛应用。 这类算法希望用同一个空间的维度来描述推荐过程中两个实体(用户、物品)的隐语义的特征。 无论是基于数值的矩阵分解如PMF[SVD],还是基于概率的矩阵分解如PLSA、LDA,都是如此。 只不过,用于PMF分解的评分矩阵中包含了用户对所访问物品的评分,而PLSA、LDA面对的数据则只能是用户有过某种访问行为的物品集合。 仅从信息量的角度看,PMF分解的评分矩阵中含有更多的用户行为信息。 而把数据从矩阵的角度看,与PMF相比,LDA、PLSA面对的则是一个评分全为1的矩阵。 我们的问题: 今天我们讨论的也是一个类似的问题,我们需要将推荐中的两个实体(…
推荐算法之协同过滤实战
协同过滤(Collective Filtering)可以说是推荐系统的标配算法。 在谈推荐必谈协同的今天,我们也来谈一谈基于KNN的协同过滤在实际的推荐应用中的一些心得体会。 我们首先从协同过滤的两个假设聊起。 两个假设: 用户一般会喜欢与自己喜欢物品相似的物品 用户一般会喜欢与自己相似的其他用户喜欢的物品 上述假设分别对应了协同过滤的两种实现方式:基于物品相似(item_cf)及基于用户相似(user_cf)。 因此,协同过滤在实现过程中,最本质的任务就是计算相似度的问题,包括计算item之间的相似度,或user之间的相似度。要计算相似度,就需要一个用来计算相似度的表达。 输入数据: 而协…
使用 vimrc 配置
vi是linux及类unix环境下使用的最多的文本编辑器,而使用vi编写代码几乎是程序员在linux下做的最多的事情。 vim的原始环境只是一个黑黑的面板,一切的一切都需要我们手动敲入,包括用来进行代码对其的空格。 本文分享一个vim的配置文件,可以为coder初始化一个相对友好的vim开发环境。 帮我们做一些简单的事情,比如代码对齐、tab键转空格、代码高亮、自动注释等,可以明显地减少无谓的手工劳动。 代码如下: set nocompatible set backspace=indent,eol,start filetype on syntax on set autoindent set …
2013-09-12 11:30 · Linux · 评论(0)
关于数组指针和指针数组
在C/C++的编程中,对指针的使用和了解,再熟悉都不为过。 C/C++毫无疑问的十分强大,但离开了指针和数组,它们就什么都干不了了,可见其重要。 使用数组和指针来描述数据,是C/C++编程中最常见的工作。 本文通过一个描述二维数据的问题,来回顾下数组和指针的使用。 假设我们要表示的是一个5行3列的数据,则共有如下五种常用方式。 每种方式各有优缺点以及适用场景。 方法1,二维数组: int data[5][3]; 该方法的优点是完全不用关注内存什么时候创建和销毁的问题,直接使用即可。 但需要在程序运行之前就知道数据的行列数。 该方式的内存空间由编译器在栈空间创建。 空间示例如下图: 方法2,数…