一种面向计数问题的公式发现方法

《一种面向计数问题的公式发现方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、文章编号：2095-1248（2016）05-0061-07一种面向计数问题的公式发现方法蔡东风，朱耀辉，白宇（沈阳航空航天大学知识工程研究中心，沈阳110136）摘要：在分析计数问题特点的基础之上，提出了一种面向计数问题的公式发现方法。该方法能根据给定的计数数列，自动发现其计数递推公式。将计数递推公式按公式的系数不同分为10种不同的公式类型（也称公式模式），对给定的计数数列，采用ＳＶＭ方法进行公式模式的分类，采用求解线性方程组方法对识别的公式模式参数进行求解，并为了防止过拟合得到错误的公式，利用专用的验证数据对求解后得到的具

2、体计数递推公式进行公式验证。最后，采用国际公开的整数数列集ＯＥＩＳ中的645个计数问题进行十折交叉验证实验，求解正确率达92.56％。在新公式发现实验中，发现了目前ＯＥＩＳ数据集中尚未包含的10个新公式。关键词：公式发现；机器发现；计数问题；模式分类；递推公式中图分类号：ＴＰ391.1文献标志码：Ａdoi：10．3969／ｊ．ｉｓｓｎ．2095-1248．2016．05．012FormuladiscoverymethodforcountingproblemＣＡＩＤｏｎｇ-ｆｅｎｇ，ＺＨＵＹａｏ-ｈｕｉ，ＢＡＩＹｕ（Ｋｎｏｗｌｅ

3、ｄｇｅＥｎｇｉｎｅｅｒｉｎｇＲｅｓｅａｒｃｈＣｅｎｔｅｒ，ＳｈｅｎｙａｎｇＡｅｒｏｓｐａｃｅＵｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ110136，Ｃｈｉｎａ）Abstract：Ｉｎｓｐｉｒｅｄｂｙｔｈｅｐｒｏｐｅｒｔｙｏｆｃｏｕｎｔｉｎｇｐｒｏｂｌｅｍｓ，ｗｅｐｒｏｐｏｓｅｄａｆｏｒｍｕｌａｄｉｓｃｏｖｅｒｙｍｅｔｈｏｄｆｏｒｃｏｕｎｔｉｎｇｐｒｏｂｌｅｍ．Ｔｈｅｍｅｔｈｏｄｃｏｕｌｄａｕｔｏｍａｔｉｃａｌｌｙｄｅｒｉｖｅｔｈｅｒｅｃｕｒｓｉｏｎｆｏｒｍｕｌａｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏｓｏｍｅｇｉｖｅｎｃｏｕｎｔｉｎｇｓｅｑ

4、ｕｅｎｃｅ．Ｓｐｅｃｉｆｉｃａｌｌｙ，ｗｅｆｉｒｓｔｇｒｏｕｐｅｄｔｈｅｒｅｃｕｒｓｉｏｎｆｏｒｍｕｌａｓｉｎｔｏｄｉｆｆｅｒｅｎｔｔｙｐｅｓ，ｉ．ｅ．ｐａｔｔｅｒｎ，ａｎｄｔｈｅｎｕｓｅｄＳＶＭｔｏｄｏｐａｔｔｅｒｎｃｌａｓｓｉｆｉｃａｔｉｏｎｏｎｔｈｅｉｎｐｕｔｃｏｕｎｔｉｎｇｓｅｑｕｅｎｃｅ．Ｗｈｅｎｔｈｅｐａｔｔｅｒｎｗａｓｄｅｔｅｒ-ｍｉｎｅｄ，ｗｅｏｂｔａｉｎｅｄｔｈｅｓｐｅｃｉｆｉｃｒｅｃｕｒｓｉｏｎｆｏｒｍｕｌａｂｙｃａｌｃｕｌａｔｉｎｇｔｈｅｐａｒａｍｅｔｅｒｓ（ｉｎｔｈｅｐａｔｔｅｒｎ），ｗｈｉｃｈｃｏｕｌ

5、ｄｂｅｔｒａｎｓｌａｔｅｄｉｎｔｏｓｏｌｖｉｎｇｓｙｓｔｅｍｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓ．Ｆｉｎａｌｌｙ，ｗｅｃｈｅｃｋｅｄｔｈｅｃｏｒｒｅｃｔｎｅｓｓｏｆｔｈｅｄｉｓｃｏｖｅｒｅｄｒｅ-ｃｕｒｓｉｏｎｆｏｒｍｕｌａｏｎｕｎｕｓｅｄｐａｒｔｏｆｔｈｅｉｎｐｕｔｄａｔａ．Ｂｙｕｓｉｎｇｔｈｅｔｅｎ-ｆｏｌｄｃｒｏｓｓｖａｌｉｄａｔｉｏｎｔｅｓｔ，ｗｅａｃｈｉｅｖｅｄ92.56％ａｃｃｕｒａｃｙｏｎ645ｃｏｕｎｔｉｎｇｐｒｏｂｌｅｍｓｆｒｏｍｔｈｅＯｎ-ｌｉｎｅＥｎｃｙｃｌｏｐｅｄｉａｏｆＩｎｔｅｇｅｒＳｅｑｕｅｎｃｅ（Ｏ

6、ＥＩＳ）．Ｉｎｔｈｅｍｅａｎｗｈｉｌｅ，ｗｅｄｉｓｃｏｖｅｒｅｄ10ｎｅｗｆｏｒｍｕｌａｓａｒｅｎｏｔｉｎｃｌｕｄｅｄｉｎＯＥＩＳ．Keywords：ｆｏｒｍｕｌａｄｉｓｃｏｖｅｒｙ；ｍａｃｈｉｎｅｄｉｓｃｏｖｅｒｙ；ｃｏｕｎｔｉｎｇｐｒｏｂｌｅｍ；ｐａｔｔｅｒｎｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｒｅｃｕｒｓｉｏｎｆｏｒｍｕｌａ由于人工求解计数问题，特别是对比较复杂于模式（模式分类+模式求解）的公式发现方法。［1］的计数问题相当困难，本文尝试利用机器学习的迄今为止，已有多种公式发现方法被提方法自动发现计数公式，提出了一种利用ＳＶＭ

7、出。其中，ＰａｔＬａｎｇｌｙ等人1977年提出的ＢＡ-［2-4］进行公式模式的分类和利用线性方程组对公式模ＣＯＮ系统是公式发现的先驱，成功地重新发式的参数进行求解的计数公式发现方法，简称基现了开普勒行星运动第三定律、理想气体定律、万收稿日期：2015-10-28作者简介：蔡东风（1958-），男，辽宁沈阳人，教授，主要研究方向：人工智能、自然语言处理，Ｅ-ｍａｉｌ：ｃａｉｄｆ@ｖｉｐ．163．ｃｏｍ。62沈阳航空航天大学学报第33卷［5］ｎ有引力定律等物理和化学公式。Ｚｅｍｂｏｗｉｔｚ等Ｄ=0，Ｄ=ｎＤ+（-1）或Ｄ=0，Ｄ=

8、1，1ｎｎ-112人在搜索公式时考虑数据的误差进而研发了Ｄ=（ｎ-1）（Ｄ-Ｄ）。ｎｎ-1ｎ-2［6-7］ＦＡＨＲＥＮＨＥＩ系统。Ｄｚｅｒｏｓｋｉ等人采用多元计数问题通常希望找到一个简洁的数学表达线性回归同时考虑多个变量，并添加微分项拓展式描述集合元素的个数，这样简洁的数学表