基于一般函数式识别赋值计算与Powell算法的非线性回归计算技术

基于一般函数式识别赋值计算与Powell算法的非线性回归计 算技术

技术领域

本发明属于电子与信息类的应用软件技术，具体是一种基于一般函数式识别赋值计算与Powell算法的非线性回归计算技术。

背景技术

本发明的背景技术主要有三个方面：（一）基于中缀表达的一般函数式识别及赋值计算技术；（二）四项改进的Powell算法；（三）基于前两项技术的非线性回归计算技术。本发明将它们首次结合并且已经完成软件系统的研发进入实用。

（一）基于中缀表达的一般函数式识别及赋值计算技术

常用的函数表达式是普通学校里教学使用的式子，称为中缀表达式。它将运算符放在运算对象的中间，如：1×3×（5＋2），3×sin（X+4），其特点是符合人类的思维习惯，用户使用起来很顺手，但是需要括号来帮助界定运算顺序。中缀表达式不太适合逻辑推演和计算机运算，于是人们又提出后缀表达式和前缀表达式。

后缀表达式又称为逆波兰式，是波兰逻辑学家 J．Lukasiewicz于 1929 年提出的，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。这种表示法的一个特点是，表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号指示运算顺序，因而又称为无括号式。例如一个中缀表达式是A＋B×C，那么它的后缀表达式是ABC×＋，而另一个中缀表达式（A＋B）×（C＋D）其后缀表达式则是AB＋CD＋×。

前缀表达式是把每一运算符置于其运算对象之前。例如，中缀式 a＋b 和（a＋b）／c相应的前缀表示分别为＋ab和／＋abc，和后缀表达式一样也是不要括号，但是读起来拗口。

中缀表达式可以直接使用堆栈原理求值。定义两个栈 OPND，OPTR，分别存放运算符和运算数。计算基本思想是：一次读入表达式的每个字符，若是操作数则进栈（stack2），若为操作符则与栈 stack1 中的栈顶运算符比较，此处设表达式中当前扫描到的操作符为x，stack1 中栈顶操作符为 y。则有如下两种情况：

（1）x＜y 或 x＝y 操作数栈出栈两次，得到两个操作数A、B，运算符栈出栈一次，得到操作符 M，对 A、B 进行 M 运算，将结果入操作数栈（stack1）。

（2）x ＞ y 此时操作符入栈。

重复进行，一直扫描到表达式尾部为止。

（3）针对四则运算的第三条规则，定义“（”的优先级最低，“）”的优先级最高，并且当扫描到“）”时一直计算到运算符栈中的“（”出栈为止。

（4）由于按照算法最后总有一步运算没有计算，如 3×（5＋2）－15 最后运算符栈中有一个“×”，运算数栈中为21、5，所以在表达式的头和尾各添加一个辅助运算符“＃”，从而辅助算法计算。

直接使用中缀表达式进行计算函数式的值，方法可见参考文献[1]和[2][3]。它需要准备两个堆栈，文[2]中是命名为OPND，OPTR，本发明是采用中缀表达式直接计算函数式的值，C程序语言里也是采用OPND和OPTR两个堆栈。为了规范各种算符的运算次序，本方法的程序需要准备一个优先表。

中缀表达式计算量比较大，许多计算机程序采用前缀表达式或者后缀表达式进行计算，此时一般只需要准备1个堆栈，这是与中缀表达式直接计算的一个很明显的区别。前缀后缀方法也不需要准备优先表，这是与中缀表达式直接计算的又一个明显区别。但是这样做需要事先将输入的中缀表达式解析出前缀表达式或者解析出后缀表达式，这又增加了一些麻烦。具体步骤可以参考文献[1]和[4][5]。本发明没有这样做，所以这里不仔细叙述。

（二）Powell算法

很多极值问题都可以归类为多模态函数优化问题或多峰值函数优化问题。如何构造一种快速、有效的优化算法，使之能求出全部全局最优解和尽可能多的局部最优解，已成为优化计算的一个重要研究方向。见参考文献[6]。

算法是由Powell, M. J. D. 教授于1964年提出的一种解无约束最优化问题的常规的直接局部搜索法，它具有计算简单、收敛速度快、不需要计算导数、精度高、可靠性好等优点。为了保证收敛到全局最优值，必须认真选择初始点。方法具有较强的局部搜索能力，可以出每个个体在目前环境下所对应的局部最优解。

算法还可以通过改进，与其他算法相结合，得出更加符合实际问题的方法。比如利用均匀设计具有使实验点高维空间均匀分散的特点，与Powell算法结合，并适当改进，经过经典的全局最优化函数测试，发现它能够跳出局部最优陷阱，从而准确地到全局最优点。

（三）一般非线性回归计算技术

所谓回归分析法，是在掌握大量观察数据的基础上，利用数理统计方法建立因变量与自变量之间的回归关系函数表达式（称回归方程式）。回归分析中，当研究的因果关系只涉及因变量和一个自变量时，叫做一元回归分析；当研究的因果关系涉及因变量和两个或两个以上自变量时，叫做多元回归分析。此外，回归分析中，又依据描述自变量与因变量之间因果关系的函数表达式是线性的还是非线性的，分为线性回归分析和非线性回归分析。一般的线性回归模型可以表示为，一般的非线性回归模型可以表示为，这里是可观察的独立随机变量，是待估的参数向量，是独立观察变量，是随机误差。函数形式(·)是已知的。

非线性回归模型的解法主要有两个。一个是最小二乘法，即求向量与集合的最短距离：

一个是极大似然法，即假设误差的分布密度函数已知，作似然函数（样本的联合密度函数），再求其最大值：

可见解法都归结到求极值问题。

一般的求解非线性回归模型有两种方法。一种是非线性模型LSE的Gauss-Newton算法，它是针对非线性回归函数做一阶Taylor展开计算导数值，然后迭代计算出LSE。另一种是非线性模型LSE的Newton-Raphson算法，它是针对极值函数做二阶Taylor展开计算导数值，然后迭代计算出LSE。详细介绍见参考文献[7]。

上述求极值的计算方法都需要计算导函数。如果是等距的，自然没有什么问题，可是数理统计里的数据是随机的，未必等距，甚至有时为0，这将由于分母为0而使计算溢出。另一种求极值的方法是采用Sargent改进的Powell算法，它不需要计算导函数或差分，计算稳定。本发明采用的就是这个Powell算法。

主要参考文献目录

宁正元，赖贤伟，算法与数据结构(第2版)(高等院校信息技术规划教材) 清华大学出版社，北京，2012。

司庆福，程书伟，表达式求值算法比较，电脑学习，2010年2月，第1期，127-129.

白宇，郭显娥，中缀算术表达式的轻量化求值算法，计算机应用，2013，33(11) : 3163－3166.

郭萌萌，许永昌，中缀及后缀算术表达式在运算中的应用研究，电脑知识与技术，Vol.5，No.32, 2009, pp.8921-8923.

胡云，一个将中缀表达式转换为前缀表达式的算法，湖北广播电视大学学报，22（3）2005，pp.124-126.

宁桂英；曹敦虔；周永权，一种融合Powell搜索法的差分进化算法，高等学校计算数学学报，39（3）267-280。

童恒庆，理论计量经济学（第七章），科学出版社，北京，2005.

发明内容

（一）一般函数式识别与赋值计算技术（本项技术是本专利的一个组成部分，但不是作为单独专利权的要求）

本项技术直接使用中缀表达式，通过计算机的堆栈原理实现多重小括号解析，通过运算优先级表安排四则运算次序，结合对基本初等函数表达式的识别，以及原始数据（包括系数与变量）的输入，实现函数式的赋值计算。

本项技术已经编译通过，并且成功应用于我们自己研发的DASC软件十多年。由于已有其他的发明专利使用后缀表达式进行函数式的识别和赋值计算，所以这项技术我们不单独作为发明权利要求。

下面从技术结构、技术流程两个方面阐述本项技术的内容。

技术结构：

本项技术由可执行文件(软件本体)、函数式输入表单(Form)、具体菜单头文件、函数式解析头文件四部分组成。具体如下：

可执行文件(软件本体)：它包括250多个模型和算法菜单，其中有若干个菜单如自编函数的非线性回归等，需要应用到函数式的独立输入技术。具体见图1。

函数式输入表单(Form)：它是用户输入自己函数式的地方，在表单(Form)里的文本框(Memo)里操作。具体见图2。

菜单头文件(*.h)：这些头文件提供函数式输入技术需要的头文件支持，同时也提供自编函数式的规则要求。具体见图3。

函数式解析头文件：这是函数式输入解析技术的关键文件，包括整个技术过程的实质性步骤。具体见图4。

技术流程：

技术流程包括如下五个步骤，见附图5。

步骤一、读入函数式文本

读入函数式从表单的Memo框里实现，关键是需要用户遵守函数式的书写规则。为此Memo文档给出如下提示。

数学表达式使用符号:

+ - * / ( ) sin cos tg ctg exp ln 以及数字和英文小写字母变量

数学表达式格式如:

一元函数 x:sin(x*2)+cos(x*x)

二元函数 x,y:sin(x*2)+ln(y*x)

三元函数 x,y,z:2+tg(x*y*z)+exp(y*x)

最多 26 元函数, 变量顺序以英文顺序, 函数式中间不能空格。

变量用英文小写字母; 只认识减号不认识负号, 请先整理函数式

如 x,y:-x-y 可写成 x,y:0-x-y; x:exp(-x*x) 写成 x:exp(0-x*x)

表达式文件固定存放于\\DASC\\She\\lizi\\She*\\han*-bds.txt

或者\\DASC\\She\\User Data\\UserData*\\han*-bds.txt

或者\\DASC\\Common Data\\CommonData*\\han*-bds.txt

本模板只对函数式文件han*-bds.txt操作，然后读取该文件的函数式进行计算。

步骤二、识别基本初等函数名

包括三角函数和反三角函数，以及指数函数、对数函数。在后面的步骤还要结合输入的具体数值检查运算的合理性，如数不能被0除，0和负数不能取对数，反三角函数要符合其定义域等等。

步骤三、结合优先表识别运算符

数学函数式具体识别解析过程由若干头文件、字符串的定义、优先级表以及关键程序组成。

需要包括的头文件如<stdio.h>、<conio.h>、<stdlib.h>、<math.h>、<string.h>。

需要定义的操作包括运算符堆栈、运算符指针、操作数堆栈、操作数指针、取得函数的代号、比较运算符关系、标准函数判断等，特别是如下的符号和函数名称：

char operation[OPTNUM]= {'~','!','$','^','&','%','<','>','+','-','*','/','(',')','#'}

char *optrstr[HANSHU]= {"exp","ln","sin","cos","tg","ctg","asin","atg","sqrt"}。

需要定义的优先级表是一个16×16的矩阵，元素由0、1、2、3四个数字组成。可以参见附图3。

步骤四、结合堆栈和小括号解析函数式

数学函数式识别解析的关键程序，主要实现对函数式的大写改小写、格式校验、数学函数定义域校验（排除分母为0、负数和0取对数、负数开平方，以及校验反三角函数的定义域等）。具体C语言代码主要是一系列判断语句，在每个判断之后给出提示语句如"出错: 表达式格式不对!"、"出错: 函数 ln 无意义!"、"出错: 函数 tg 无意义!"、"出错: 函数 sqrt无意义!"、"出错: 函数 asin 无意义!""出错: 数被 0 除!"，等等。

步骤五、赋值计算

赋值包括函数式的系数赋值和变量赋值。赋值以后、计算之前，还要检查函数式的合理性。

尽管本发明采用基于一般中缀函数式识别与赋值计算技术，成功使得软件在编译成为可执行文件之后能够读入、识别、解析、计算用户输入的非线性函数，这些技术和我们提供的程序完全可以作为其他软件编程借鉴，但是我们不把它作为单独的发明专利权要求。

（二）四项改进的Powell算法（本项技术是本专利的一个组成部分，但不是作为单独专利权的要求）

下面从技术结构和技术流程两个方面阐述本项技术的内容。

技术结构：

Powell 算法包含三个程序，一个计算目标函数值的子函数OBF()，一个基本程序Powell()，一个计算各个方向步长跨点函数值的子函数DSCPOW()。

（1）子函数OBF()。需要开发者在程序里改写，以适应不同的目标函数需要，在非线性回归里它是求回归误差平方和的最小值，或者是求似然函数的极大值。函数形式是OBF(float B[]，int Nc，float xtx[]，float yty[]，float xtz[]，float gz[]，float rr[]，float fb[]，char str[])。一旦这个子函数连同主程序编译成可执行文件，用户就不需要改写它了，而只需要在可执行文件弹出的Form框里填入用户的非线性函数即可。一个非线性回归的目标子函数程序源代码见图6。

（2）基本程序Powell()。原始程序是Fortran语言编写的，公开发表在学术杂志上，我们将它改编成C语言的，并且为了读入用户的非线性函数，加入了char str[]，为了读入参数和样本矩阵数值，加入了一些数组如float xtx[]，float yty[]，float xtz[]，float gz[]，float rr[]，float fb[]。现在的函数形式是POWELL(float X[]，float Y[]，float DIR[]，int N，int IMOS，int ICOVG，int IT，float xtx[]，float yty[]，float xtz[]，float gz[]，float rr[]，float fb[]，char str[])。用户只需调用，无需对其函数体进行改写。为了避免分母为0和其他一些计算溢出，函数体中已经加入一些检查和处理。程序源代码见图7的左半部分。

（3）子函数DSCPOW()。其改编原则和上面基本程序是一样的，函数形式是DSCPOW(float X[]，float Y[]，float S[]，float DELX[]，int N，int INDIC，int ITOL，intITER，int IEX，float xtx[]，float yty[]，float xtz[]，float gz[]，float rr[]，float fb[]，char str[])。程序源代码见图7的右半部分。

技术流程：

技术流程包括如下五个步骤，见附图8。

步骤一、主程序调用Powell算法基本程序Powell()。注意函数体需要对应好，遵循一般C语言程序规则。

步骤二、Powell()调用子函数DSCPOW()协助计算。这个过程不仅在已经编译好的软件本体可执行文件对于用户是傻瓜式不用考虑的，而且对于任何软件开发者而言，程序也是傻瓜式的，根本就不用细看程序源代码了。

步骤三、Powell()调用目标函数OBF()计算最小二乘值。这个过程在已经编译好的软件本体可执行文件里，对于用户是傻瓜式不用考虑的。但是对于软件开发者而言，程序依目标函数的不同需要开发者具体编写。其实也很简单，只需要改写目标函数一行即可。

步骤四、OBF()的计算过程中，需要识别数学函数式并计算其解析值，这可以调用头文件里包含的hanshuC()即可。

步骤五、当最小二乘值小于指定误差，完成计算。

尽管本发明对Powell算法程序完成了四项改进使之适应软件编程，包括从Fortran语言改写成C语言，对程序中的各种可能产生溢出或者非法计算的地方进行检查修正，对目标函数进行规范使得用户无需改动主程序而只需改动目标函数，对函数体增加数组、整型参数和字符串的传递调用。但是本发明不将这些改进单独作为发明专利权的要求。

（三）基于一般函数式识别赋值计算与Powell算法的非线性回归计算技术（本项技术是三项技术的综合，属于本发明专利的核心技术和基本权利要求）

Powell算法计算函数极值问题，最大的优点在于它无需计算函数的导数，从而避免了计算溢出，具有很好的稳健性。目前在所有的文献里还没有使用Powell算法求解非线性回归模型的记述。本发明采用我们自己作出四项改进的Powell算法求解非线性回归模型，计算回归的最小二乘估计LSE和极大似然估计MLE，完成参数估计及后续的各种统计计算。同时本发明采用基于一般中缀函数式识别与赋值计算技术，使得软件在编译成为可执行文件之后能够读入、识别、解析、计算用户输入的非线性函数。这三种技术的合成具有新颖性，创造性，实用性。

实现形式：

具体实现界面和过程。

软件主菜单界面见附图1。可以在网站“计量统计云” www.tongdasc 或者“数据分析与统计计算园地” http://tonghq.scholar.whut.edu/ 下载DASC.zip，解压后进入目录\DASC\，点击可执行文件DASC.exe，即可得到附图1。注意主菜单是选择回归分析----非线性回归----自编函数非线性回归模型。

点击”开始计算”按钮以后，软件弹出函数式输入表单(小界面)，编辑器显示一个例子数学函数式，用户可以在此修改成自己需要的函数式，见附图2。如果要显示函数式的编写规则，可以点击提示按钮，见附图3。函数式编写基本规则是由头文件的函数规定，C语言程序见附图4，当然这个C语言程序在用户那里是看不到的。

在完成编辑以后，可以保存函数式，然后选择退出按钮，则主程序读入并且解析用户输入的函数式，结合软件A区的输入数据，完成函数式的识别和赋值计算，流程见附图5。流程中涉及的软件内部的Powell算法的C语言程序见附图6和附图7。同时软件使用Powell算法完成非线性函数回归的最小二乘或者最大似然的极值问题计算，过程见附图8。

上述三个过程综合起来，程序基于一般中缀函数式识别和赋值计算以及Powell算法，完成非线性回归模型的求解以及后续的计算，整体过程见附图9。对恩格尔曲线的统计计算结果和图像显示见附图10。

附图说明：

图1是DASC软件中自编函数的非线性回归的主菜单。

图2是DASC软件中数学函数式输入表单。

图3是DASC软件中数学函数式输入规则提示。

图4是数学函数式识别解析程序头文件hanshuC.h的说明部分。

图5是数学函数式识别解析的基本流程图。

图6是Powell算法中的目标函数C语言程序。

图7是Powell算法中的主程序(左)和子函数(右)的C语言程序。

图8是Powell算法的基本流程图。

图9是基于一般函数式识别和Powell算法的非线性回归流程图。

图10是DASC软件中一个非线性回归例子的计算结果。

软件教学版可以在网站“计量统计云”www.tongdasc下载。