保序回归算法步骤_weixin_30906185的博客-程序员信息网

技术标签: matlab  人工智能  大数据  

保序回归

1 保序回归

  保序回归解决了下面的问题:给定包含n个数据点的序列 y_1,y_2,...,y_n , 怎样通过一个单调的序列 beta_1,beta_2,...,beta_n 来归纳这个问题。形式上,这个问题就是为了找到

1.1

 

  大部分时候,我们会在括号前加上权重w_i。解决这个问题的一个方法就是 pool adjacent violators algorithm(PAVA) 算法。粗略的讲,PAVA算法的过程描述如下:

  我们从左边的y_1开始,右移y_1直到我们遇到第一个违例(violation)即y_i < y_i+1,然后,我们用违例之前的所有y的平方替换这些y,以满足单调性。我们继续这个过程,直到我们最后到达y_n

2 近似保序

  给定一个序列y_1,y_2,...,y_n,我们寻找一个近似单调估计,考虑下面的问题

1.2

 

  在上式中,X_+表示正数部分,即X_+ = X.1 (x>0)。这是一个凸优化问题,处罚项处罚违反单调性(即beta_i > beta_i+1)的邻近对。

  在公式(2)中,隐含着一个假设,即使用等距的网格测量数据点。如果情况不是这样,那么可以修改惩罚项为下面的形式

1.3

 

  x_i表示y_i测量得到的值。

3 近似保序算法流程

  这个算法是标准PAVA算法的修改版本,它并不从数据的左端开始,而是在需要时连接相邻的点,以产生近似保序最优的顺序。相比一下,PAVA对中间的序列并不特别感兴趣,只关心最后的序列。

  有下面一个引理成立。

1.4

 

  这个引理证明的事实极大地简化了近似保序解路径(solution path)的构造。假设在参数值为lambda的情况下,有K_lambda个连接块,我们用A_1,A_2,..,A_K_lambda表示。这样我们可以重写(2)为如下(3)的形式。

1.5

 

  上面的公式,对beta求偏导,可以得到下面的次梯度公式。通过这个公式即可以求得beta

 

1.6

 

  为了符合方便,令s_0 = s_K_lambda = 0。并且,

1.7

 

  现在假设,当lambda在一个区间内增长时,组A_1,A_2,...,A_K_lambda不会改变。我们可以通过相应的lambda区分(4)。

1.8

 

  这个公式的值本身是一个常量,它意味着上式的betalambda的线性函数。

  随着lambda的增长,方程(5)将连续的给出解决方案的斜率直到组A_1,A_2,...,A_K_lambda改变。更加引理1,只有两个组合并时,这才会发生。m_i表示斜率,那么对于每一个i=1,...,K_lambda - 1A_iA_i+1合并之后得到的公式如下

 

1.9

 

  因此我们可以一直移动,直到lambda “下一个”值的到来

1.10

 

  并且合并A_i^starA_i^star+1,其中

1.11

 

  注意,可能有超过一对组别到达了这个最小值,在这种情况下,会组合所有满足条件的组别。公式(7)和(8)成立的条件是t_i,i+1大于lambda,如果没有t_i,i+1大于lambda,说明没有组别可以合并,算法将会终止。

  算法的流程如下:

    • 初始时,lambda=0K_lambda=n,A_i={i},i=1,2,...,n。对于每个i,解是beta_lambda,i = y_i

    • 重复下面过程  

    • **1、**通过公式(5)计算每个组的斜率m_i

    •   **2、**通过公式(6)计算没对相邻组的碰撞次数t_i,i+1

        **3、**如果t_i,i+1 < lambda,终止

        **4、**计算公式(7)中的临界点lambda^star,并根据斜率更新解

      1.12

        对于每个i,根据公式(8)合并合适的组别(所以K_lambda^star = K_lambda - 1),并设置lambda = lambda^star

       

      4 源码分析

        在1.6.x版本中,并没有实现近似保序回归,后续会实现。现在我们只介绍一般的保序回归算法实现。

      4.1 实例

      import org.apache.spark.mllib.regression.{
                    IsotonicRegression, IsotonicRegressionModel} val data = sc.textFile("data/mllib/sample_isotonic_regression_data.txt") // 创建(label, feature, weight) tuples ,权重默认设置为1.0 val parsedData = data.map { line => val parts = line.split(',').map(_.toDouble) (parts(0), parts(1), 1.0) } // Split data into training (60%) and test (40%) sets. val splits = parsedData.randomSplit(Array(0.6, 0.4), seed = 11L) val training = splits(0) val test = splits(1) // Create isotonic regression model from training data. // Isotonic parameter defaults to true so it is only shown for demonstration val model = new IsotonicRegression().setIsotonic(true).run(training) // Create tuples of predicted and real labels. val predictionAndLabel = test.map { point => val predictedLabel = model.predict(point._2) (predictedLabel, point._1) } // Calculate mean squared error between predicted and real labels. val meanSquaredError = predictionAndLabel.map { case (p, l) => math.pow((p - l), 2) }.mean() println("Mean Squared Error = " + meanSquaredError)

      4.2 训练过程分析

        parallelPoolAdjacentViolators方法用于实现保序回归的训练。parallelPoolAdjacentViolators方法的代码如下:

      private def parallelPoolAdjacentViolators(
            input: RDD[(Double, Double, Double)]): Array[(Double, Double, Double)] = { val parallelStepResult = input //以(feature,label)为key进行排序 .sortBy(x => (x._2, x._1)) .glom()//合并不同分区的数据为一个数组 .flatMap(poolAdjacentViolators) .collect() .sortBy(x => (x._2, x._1)) // Sort again because collect() doesn't promise ordering. poolAdjacentViolators(parallelStepResult) }

        parallelPoolAdjacentViolators方法的主要实现是poolAdjacentViolators方法,该方法主要的实现过程如下:

      var i = 0
      val len = input.length while (i < len) { var j = i //找到破坏单调性的元祖的index while (j < len - 1 && input(j)._1 > input(j + 1)._1) { j = j + 1 } // 如果没有找到违规点,移动到下一个数据点 if (i == j) { i = i + 1 } else { // 否则用pool方法处理违规的节点 // 并且检查pool之后,之前处理过的节点是否违反了单调性约束 while (i >= 0 && input(i)._1 > input(i + 1)._1) { pool(input, i, j) i = i - 1 } i = j } }

        pool方法的实现如下所示。

      def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = { //取得i到j之间的元组组成的子序列 val poolSubArray = input.slice(start, end + 1) //求子序列sum(label * w)之和 val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum //求权重之和 val weight = poolSubArray.map(_._3).sum var i = start //子区间的所有元组标签相同,即拥有相同的预测 while (i <= end) { //修改标签值为两者之商 input(i) = (weightedSum / weight, input(i)._2, input(i)._3) i = i + 1 } }

        经过上文的处理之后,input根据中的labelfeature均是按升序排列。对于拥有相同预测的点,我们只保留两个特征边界点。

      val compressed = ArrayBuffer.empty[(Double, Double, Double)] var (curLabel, curFeature, curWeight) = input.head var rightBound = curFeature def merge(): Unit = { compressed += ((curLabel, curFeature, curWeight)) if (rightBound > curFeature) { compressed += ((curLabel, rightBound, 0.0)) } } i = 1 while (i < input.length) { val (label, feature, weight) = input(i) if (label == curLabel) { //权重叠加 curWeight += weight rightBound = feature } else {
                                                    //如果标签不同,合并 merge() curLabel = label curFeature = feature curWeight = weight rightBound = curFeature } i += 1 } merge()

        最后将训练的结果保存为模型。

      //标签集
      val predictions = if (isotonic) pooled.map(_._1) else pooled.map(-_._1) //特征集 val boundaries = pooled.map(_._2) new IsotonicRegressionModel(boundaries, predictions, isotonic)

      4.3 预测过程分析

      def predict(testData: Double): Double = { def linearInterpolation(x1: Double, y1: Double, x2: Double, y2: Double, x: Double): Double = { y1 + (y2 - y1) * (x - x1) / (x2 - x1) } //二分查找index val foundIndex = binarySearch(boundaries, testData) val insertIndex = -foundIndex - 1 // Find if the index was lower than all values, // higher than all values, in between two values or exact match. if (insertIndex == 0) { predictions.head } else if (insertIndex == boundaries.length){ predictions.last } else if (foundIndex < 0) { linearInterpolation( boundaries(insertIndex - 1), predictions(insertIndex - 1), boundaries(insertIndex), predictions(insertIndex), testData) } else { predictions(foundIndex) } }

        当测试数据精确匹配一个边界,那么返回相应的特征。如果测试数据比所有边界都大或者小,那么分别返回第一个和最后一个特征。当测试数据位于两个边界之间,使用linearInterpolation方法计算特征。 这个方法是线性内插法。

    •  

    •  

      原文链接:https://github.com/endymecy/spark-ml-source-analysis/blob/master/%E5%88%86%E7%B1%BB%E5%92%8C%E5%9B%9E%E5%BD%92/%E4%BF%9D%E5%BA%8F%E5%9B%9E%E5%BD%92/isotonic-regression.md 

  • http://fa.bianp.net/blog/2013/isotonic-regression/

转载于:https://www.cnblogs.com/earendil/p/10000734.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30906185/article/details/97909868

智能推荐

深度学习边缘计算综述论文阅读笔记_zjdy106678的博客-程序员信息网_边缘计算深度学习

文章《Convergence of Edge Computing and Deep Learning: A Comprehensive Survey》这是一篇关于深度学习和边缘计算基础知识的综述,包含了深度学习DL的几种网络模型的介绍,边缘计算的基础知识的介绍,以及二者的结合,如何利用DL来发展边缘计算,如何用边缘计算发展DL,怎么在边缘计算的框架下进行DL的训练,DL在边缘上运行的预测结果怎么样,二者怎么更好融合形成智慧边缘(Intelligent Edge)和边缘智慧(Edge Intelligen

SR显著图(A Spectral Residual Approach)_GHelpU的博客-程序员信息网_显著性图

1 简介SR(Spectral Residual,剩余谱)模型独立于对象的特征,类别或其他形式的先验知识。通过分析输入图像的对数谱,可以在空间域中获取输入图像的剩余谱,进而用快速的方法在空间域中构造相关的显著性图。模型在自然图像和艺术图像的测试结果表明该方法具有计算效率高且鲁棒性好的特点[1]。论文指出,图像的信息是由先验知识的信息和显著部分的信息构成,通过在对数谱中用图像的信息减去先验知...

SwiftUI捕获键盘提交动作在iOS15之前和之后的兼容实现_大熊猫侯佩的博客-程序员信息网_swiftui 键盘

在本篇博文中,我们实现了兼容iOS 15之前和之后捕获键盘提交动作的功能,并讨论了在SwiftUI中如何避免onChange中相同新旧状态的比较。

Go语言自学系列 | golang标准库encoding/xml_COCOgsta的博客-程序员信息网_golang xml

视频来源:B站《golang入门到项目实战 [2021最新Go语言教程,没有废话,纯干货!持续更新中...]》一边学习一边整理老师的课程内容及试验笔记,并与大家分享,侵权即删,谢谢支持!附上汇总贴:Go语言自学系列 | 汇总_COCOgsta的博客-程序员信息网_go语言自学xml包实现xml解析将struct编码成xml,可以接收任意类型将xml转码成struct结构体从输入流读取并解析xml写xml到输出流运行结果也可以读写文件运行结果运行结果...

Android 换肤demo,轻量快捷接入集成,判断是否夜间模式_meixi_android的博客-程序员信息网

实现效果昼白天 夜晚上 实现方法:1、创建昼夜两种颜色color.xml资源文件昼&lt;?xml version="1.0" encoding="utf-8"?&gt;&lt;reso...

随便推点

一行代码搞定你的QueryString!(原创)_sunfollowme的博客-程序员信息网

导读:   Web开发做得多了,总觉得是体力活,于是搞些代码让自己脱离无聊的Coding吧(是脱离“无聊的”Coding,不是脱离无聊的“Coding”)。      初级阶段   为每个QueryString写转换的代码,针对不同的类型,进行转换和错误处理。      中级阶段   写了一个函数,专门做转换(1.1里写的):   /// /// Convert query string

CSFramework---通信层(Communication)的实现_Ailsa Zhang的博客-程序员信息网

C/S 开发框架之通信层的实现CSFramework编写的主要目的是,为未来编写相应的服务器/客户端模式下的应用系统提供便利。也就是说,我们的CSFramework将完成最底层的相应工作,使得开发人员在使用此框架时,无需再编写底层操作的代码。最底层–通信层(Communication)的实现基于服务器端和客户端,双方之间需要进行信息的交互,也就是说,无论是服务器端还是客户端,都同时作为信息的...

指令集_diandianyangyi的博客-程序员信息网_指令集怎么写

转载自 http://www.cnblogs.com/li-daphne/p/4067241.html一个完整的指令集结构包括Instuction Fetch Instuction DecodeOperand FetchExcuteResult StoreNext Instruction

php内存管理机制、垃圾回收机制_jacklin_001的博客-程序员信息网_php内存管理机制和垃圾回收机制

一、内存管理机制&lt;?php//内存管理机制var_dump(memory_get_usage());//获取内存方法,加上true返回实际内存,不加则返回表现内存$a = "laruence";var_dump(memory_get_usage());unset($a);var_dump(memory_get_usage());//输出(在我的个人电脑上, 可能会因为系统,PHP版本,载入的扩展不同而不同)://int 240552//int 240720//int 2405

全息裸眼3D主题餐厅沉浸式互动投影无人未来点餐系统_komstone的博客-程序员信息网

全息裸眼3D主题餐厅互动投影无人未来餐厅点餐系统【3D/AR/VR/全息互动投影视觉开发】(1)功能:自身团队开发3D程序,激光雷达感应更精确更灵敏,手势翻页查看菜单,多点触摸点菜,扫码买单付款,真正的有交互有互动,而不是播放视频(2)自定义:可自己编辑菜谱图片名称价格,自定义编辑菜谱书本的数量位置大小,自定义买单二维码(3)内容定制:可根据客户需求定制开发背景特效,对接视频服务器...

paddleocr打包exe,10大报错的解决。。。。成功打包运行_Joyce1001的博客-程序员信息网_paddle打包exe

打包paddleocr时,出现Error: Can not import avx core while this file exists: xxxxxx(你安装Python的径)\paddle2.0\lib\site-packages\paddle\fluid\core_avx.pyd错误:解决方法:进入paddle安装对应的虚拟环境下,如下图所示,找到paddle/libs,如下所示:Copy所有的dll文件到dist下的:pyinstaller可执行文件报错astor:解决方法:注销这三行.

推荐文章

热门文章

相关标签