摘要：
函数挖掘是数据挖掘的重要研究方向。传统的函数挖掘有两个局限性：(1) 挖掘目标是单个函数，但单个函数对现实世界中规律的描述能力很弱；(2) 它难以被应用在复杂的数据集上。为了弥补这些缺陷，本文作了如下探索：(1) 提出了新的，描述能力更强的函数挖掘对象——频繁函数集 (Frequent Function Set , FFS)。(2) 提出了可配置的频繁函数集挖掘算法CFFSA。灵活,可配置称不同类型，如遗传，迭代的GEP 的(3)分析FFSD 的不足，引入基于约束的频繁函数集(Constrained FFS)概念,它可以满足用户的不同兴趣需求。(4) 提出了基于约束的频繁函数集挖掘框架。
关键字：频繁函数集，基于约束的频繁函数集，基因表达式编程， 函数挖掘
1. 引言
在过去的数十年中, 随着科学技术地发展, 产生和收集了大量的数据。数据库系统尤其是关系数据库系统的成功，使我们能够高效地处理这些海量数据。然而，随着数据量日渐增大，数据类型逐步复杂，人们不再满足于对数据的简单查询，他们更希望计算机能帮助分析数据，发掘数据中隐含的关系。数据挖掘应运而生！
人类在自然科学和社会科学的各个领域不断观测积累数据，希望从观测数据中推导相关事物的内在联系。函数关系是一种特殊的事物联系，它准确、定量地描述了隐藏在数据后的知识。
在计算机发明以前，事物间函数关系的发现是依靠科学家辛勤工作完成。例如：第谷从事30 年的天文观察，积累了大量的观察材料，但是并没有发现行星运动的三大定律，而开普勒在第谷的基础上坚持几十年做大量的科学计算工作，最终做出重大发现。
函数关系挖掘是数据挖掘的重要研究方向。计算机技术作为20 世纪最伟大的技术之一深刻地影响着当今世界，广泛地渗透进生物学，物理学，经济学等各个科学分支领域中。这些应用为利用计算机进行函数关系挖掘奠定了基础。
数据挖掘领域中已提出很多技术用以从数据集中发掘函数，然而这些研究主要是集中于传统的单一函数挖掘——函数回归。传统的函数挖掘本身具有很多局限性，在实际问题中难于应用。本文对函数挖掘的概念进行扩展，提出了新的函数挖掘对象——频繁函数集，以期望得到更好地解决实际问题能力。
本文主要工作包括：
（1）分析了传统函数挖掘的不足，提出了频繁函数集(Frequent FunctionSet , FFS)的概念来描述在指定数据集上具有一定支持度的函数关系簇。
（2）分析了FFS的性质。
（3）提出了可配置C FFS挖掘算法——configurable Frequent Function Set Discovering (FFSD)。
（4）分析FFSD 的不足，进一步提出了可以满足用户不同兴趣需求的基于约束的频繁函数集(Constrained FFS)和相应的挖掘框架。
2. 背景知识设
S1，S2，…，Sn，T是n+1 个非空集合，S= S1×S2× …×Sn，映射f :S àT，使得对任意的(X1, X2,…, Xn) ∈S, 都存在唯一的y ∈ T和它对应, 则称该映射f为定义在集合S上的一个多元函数关系，简称函数。
从数据集上发现事物间函数关系的过程称作函数挖掘。在数据挖掘领域，已经提出很多方法来自动地进行函数挖掘。已经有研究者在神经网络进行函数逼近方面取得了一定成果。然而，由于构造网络结构比较复杂、不便于计算、结果的可解释性不好，这一方法难以应用到实际问题上。文献[1]讨论了线性回归和多元回归，一般采用最小二乘法求解。有研究把遗传算法应用到函数挖掘中，文献[2][3]中探讨了应用GEP进行符号回归(Symbolic Regression)。
目前已有的成果，主要是集中于传统的函数挖掘。传统的函数挖掘本身具有局限性，使其在实际问题中难以应用。
①.传统函数挖掘的目标是找到一个非常理想的函数来描述数据集中各个属性的联系。下面的例1 揭示了单个函数的局限性和引入函数集合的必要性。
②.传统函数挖掘对数据集有一定的要求——数据集中每条记录的属性数值个数相同。然而现实中复杂数据集往往不能满足这一要求。
例2．考虑加速度函数关系a Fm= 的挖掘过程。其中F 为物体所受外力，m 为物体的质量，a 为物体的加速度。如果数据集中的每条记录都只有a, F和m这三个属性的数值，传统的函数挖掘可以得到很好的结果。然而探索未知规律的观察数据受设备性能、观察者兴趣等各种干扰的综合影响，不会如此理想。数据集中记录可能包含了不同个数的属性数值。例如，某些记录只有a、m 的值，有的记录只有a、F、m 的值，还有的记录拥有a、F、m、ρ、v 的值(ρ为密度，v 为体积)。因此，传统函数挖掘将面临问题——是在属性a、m上挖掘还是在属性a、ρ、v 上挖掘？
鉴于传统函数挖掘不能很好地适应需求，本文对函数挖掘的概念进行扩展，以期望得到更好的解决实际问题能力。
3. 频繁函数集
3.1基本概念设 AttriSet={A1 , A2 , ... , Am }是属性的集合，对1≤i≤m，Ai是属性，Dom(Ai)是Ai的值域。记录r ={Ai : VAi , Aj : VAj , ... , Ak: VAk }，其中Aq∈ AttriSet（q =i,j, ...,k），VAq在Dom(Aq)中，是属性Aq在记录r中的值。rT = { Ai , Aj , ... , Ak } , 称作记录r对应的事务记录，显然rT í AttriSet 。任务相关数据集是记录的集合，记为DB，即DB={r1, r2 ,... ,rj}；DB 的大小记为|DB|, 这里|DB|=j 。DB对应的事务数据集是DB 中记录的对应事务记录的集合，记为DBT，DBT ={r1T , r2T , … , rjT}。
观察表明，一组科学数据中，常有若干个字段的值在一定程度上满足某种函数关系。为形式化描述这一事实，引入下列定义：
定义 1. 设AttriSet是属性集合，函数y= f (x1, x2 ,… , x t)，如果{y, x1, x2 ,… , x t }í AttriSet，则称y=f (x1, x2 ,… , x t )是AttriSet上的函数。
函数 y=f ( x1, x2 ,… , x t ) 有t个自变量，称为t-元函数。在属性集合AttriSet上的函数的集合记为FuncSet。
定义2. 设y=f (x1, x2 ,… , x t )是属性集合AttriSet上的函数，r={Ai : VAi , Aj : VAj , ... , Ak: VAk }
是一条记录，如果{ y, x1, x2 ,… , x t }T , 并且f (Vx1, Vx2,...,Vxt) = Vy ，则称y＝f ( x1, x2 ,… , x t )在记录r上成立。
人们并非对FuncSet中的每个函数感兴趣，本文用支持度来度量函数的兴趣度。
定义 3. 设y=f (x1, x2 ,… , x t )是属性集合AttriSet上的函数，DB 是任务相关数据集，记录集合RecordSet={r| r∈DB，且f在r上成立}。函数f 在DB 上的支持度是RecordSet的大小与DB大小的比值：
定义 4. 设y=f (x1, x2 ,…, x t)是属性集合AttriSet上的t元函数，DB 是任务相关数据集，MinSupport（0.0≤MinSupport≤1.0 )是预先指定的最小支持度，如果Support [y=f ( x1, x2 ,… , xt)]≥MinSupport ，则称函数y=f (x1, x2 ,… , x t)为频繁t-元函数，简称频繁函数。
DB 上所有频繁函数的集合称为频繁函数集（Frequent Function Set，简记FFS）。频繁k-元函数的集合称作频繁k-元函数集，记为FFSk。
根据定义，容易验证：
10． if Support[f ]>=MinSupport11． FFSk=FFSk∪{ f };12． }
13． FFS=FFS ∪FFSk;14． }
15． return FFS;图 2. FFS挖掘算法——FFSD以下对算法FFSD 作详细说明：
算法输入：任务相关数据集DB，最小支持度MinSupport。
第2步是得到数据集DB 上的属性集AttriSet;第3—14 步是采用分治法，分别挖掘各个FFSk。
第 5 步是初始FFSk为空。
第 6 步是得到对应的事务数据集DBT上的频繁(k+1)项集，这是根据性质1对第9 步的函数搜索空间进行压缩。函数find_frequent_itemsets可以通过任何一种频繁项集挖掘算法实现。
第 7－12 步是挖掘FFSk。其中循环结束条件end_condition可以是循环的次数或FFSk的大小，等等。
第 9 步Configurable_function_o 解释可配置的含义、意义。在ItemSet的基础上产生一个k元函数f。这一步是算法FFSD 的核心，它实际是在函数空间进行搜索。generate_function_on可以以任何搜索算法实现，包含了函数模型的搜索和函数中参数的优化。generate_function_on 决定了FFSD 的复杂度。
第 10，11 步判断函数f是否属于FFSk，如果f 的支持度不小于最小支持度，则加入FFSk。
第 13 步是把中间结果合并到最终结果。
第 15 步是返回最终结果FFS。
4. 基于约束的频繁函数集
尽管FFSD描述了如何从任务相关数据集中挖掘出FFS，然而在实际应用中，FFSD有如下不足：
①.FFSD缺乏交互性、可控性。FFSD以一种“黑盒子”方式进行，用户无法聚焦于感兴趣的函数，也无法提供应用领域的背景知识。如果在小数据集上，这种“黑盒子”的效率尚可接受，但在较大数据集上的表现则不理想。
②.FFSD不能满足复杂的兴趣模式。FFSD只能用最小支持度(MinSupport)表示兴趣度，对复杂的、综合的兴趣度模式无能为力。例如：对于函数y=f (x),用户不仅希望它满足最小支持度，而且希望y大于某个阈值。
③.结果集FFS的质量也不令人满意。因为对复杂的兴趣度模式无能为力，FFSD常常产生非常大的结果集，这不仅降低了挖掘的效率，也降低了挖掘的有效性——用户不得不对结果集FFS进一步探索，以期望得到有用的知识。并且，挖掘的效率和挖掘的有效性不是独立的。
针对上述不足，有必要在频繁函数集挖掘过程中考虑用户定义的兴趣度模式和背景知识。
本文先引入约束
用以表示应用领域背景知识和用户的兴趣，并提出一个挖掘框架，利用约束指导挖掘过程，为用户提供交互性、可控性。
4.1 FFS 上的约束
为了满足不同兴趣度和不同背景知识的需求，本文把约束分为三类：① FFS结果集的约束，②函数类型的约束，③评估函数约束。FFS结果集的约束是针对结果集的整体约束，函数类型（也称模式）的约束、评估函数约束针对的是结果集中的元素——函数。
4.1.1 FFS 结果集的约束
FFS结果集的约束作用在得到的结果集上，此类约束表达了用户对结果集整体质量的期望。
例如，用户可以指定结果集的大小，如：|FFS|=10。用户也可以指定更复杂的约束：
①.FFS的整体覆盖面极大化设集合USet=RecordSet2[FFS[1]3]∪RecordSet[FFS[2]]
∪…∪RecordSet[FFS[i]],i=|FFS|。
此约束即是极大化CoverSet,使结果集可以描述DB中大多数记录上的函数关系。
②.FFS的相交覆盖面极小化设集合ISet= {RecordSet[FFS[i]]∩RecordSet[FFS[j]]| 0<I,j<=|FFS|}。
此约束即是极小化CrossSet,使结果集去除冗余函数。例如，y=sin(2 x)与y=2 sin(x)cos(x)，拥有相同的RecordSet，根据该约束，就只能保留一个函数。
③.FFS的整体误差值极小化此约束是提高FFS的准确度。整体误差可以使用绝对误差，方差度量。需要注意的是噪音的影响，可以对DB进行预处理，过滤掉噪音。
④.FFS的整体复杂度极小化FFS的整体复杂度衡量结果集结构的复杂度。显然，结构越简单，FFS越理想。该约束可以作为在第②条约束下函数取舍的依据：y=sin(2x)比y=2sin(x)cos(x)结构简单得多，显然应该选择保留前者。简单的结构有利于用户理解，同时也便于进一步分析事物间的联系。简单的结构还可以减少计算函数值时所需的计算资源。
⑤.上述4种约束的综合综合的约束是上述约束的某种组合。各种约束的作用有时需要权衡，例如，复杂的函数往往拥有更高的准确度。怎样权衡决定于具体应用。
4.1.2 函数类型的约束
函数类型的约束使得用户可以结合背景知识说明他们希望得到的FFS形式。函数类型也称为元函数，元函数可以根据用户的经验、期望和对数据集的先验知识确定。例如：用户指定的元函数为log,则函数y=x3+log(z)可能属于FFS,而函数y= x3+z肯定不属于FFS,因为它不含log这个元函数。再如：观察显示，数据呈周期出现，可以根据先验知识指定元函数为sin或cos；数据呈指数出现，可以指定元函数x2, x3。
元函数也可以指定FFS中的元素必须含有的变量名。例如,假设用户指定函数必须拥有变量x、y，则不存在FFS0,FFS1 。v = f (x,y,z)是FFS3中的合法形式函数,而v = p (x,z,w)就不是合法的函数,即使它在DB上根据定义4是频繁的,但它也不是基于该约束的频繁函数。
4.1.3 评估函数约束
设y=f (x1, x2 ,… , x t )是属性集合AttriSet上的函数，把此函数在数据集DB各个记录上的取值f(r)和y 的真实值Vy对的集合记为FuncV( f ),即FuncV( f )={( Vy ,f(r))| r ∈DB }。因此，第i 条记录上y 的真实值可表示为FuncV( f )[i].Vy ,函数在该记录上的取值表示为FuncV( f )[i].f(r)。
定义5.设FuncVSet是函数集合FuncSet中函数的FuncV集合，即FuncVSet={FuncV(f) | f∈FuncSet} , value是实数集，存在映射g：FuncVSet—>value,使得对任意的FuncV(f )∈ FuncVSet,都存在唯一的v∈value和它对应, 则称该映射为函数集合上的评估函数。
定义6.设y=f (x1, x2 ,… , x t )是属性集合AttriSet上的频繁函数，g是评估函数，t是预先定义的阈值；如果g( FuncV(f) ) ≥t,则称函数y=f (x1, x2 ,… , x t )为基于评估函数g约束的频繁函数。
评估函数的功能非常强大，用户可以定义不同的评估函数来满足不同的应用需求。下面列举几个函数约束以作说明。
①.频繁函数置信度置信度也是一种兴趣度量，先前并没有定义置信度。可以利用定义6，通过评估函数来定义频繁函数的置信度。
定义7. 设频繁函数y=f (x1, x2 ,… , x t )，令评估函数为g( FuncV) =把该评估函数的值称为函数y=f (x1, x2 ,… , x t )的置信度。
②.考虑记录顺序的评估函数某些DB 中的记录是有序的，例如股票数据集，新闻记录集。从这些DB 中挖掘频繁函数时需要考虑记录的时间顺序——用户往往对最近的关系感兴趣。可以通过设置合适的评估函数来表示用户的这种兴趣模式。
例如：设函数y=f (x1, x2 ,… , x t )，评估函数是i的增函数，可以为φ(i,FuncV[i])= (1-|FuncV[i].Vy-FuncV[i].f(r)|)×i。
很显然，如果函数y=f (x1, x2 ,… , x t )描述了隐含在最近记录中的关系(即是在很多较大i值的记录上成立)，其评估函数值就大。当然，φ函数还可以是其它形式。
4.2 基于约束的频繁函数集定义
8.设FFS是数据集DB上频繁函数集，CSet是用户定义的约束集，令CFFS={ f | f ∈FFS,且对于任意C∈CSet, f 是基于约束C的频繁函数},则称CFFS为DB上基于约束集CSet的频繁函数集。
5. 基于约束的频繁函数集挖掘框架
基于约束的频繁函数集挖掘框架如图3.所示。基于约束的频繁函数集挖掘系统应该给出系统约束集，它可以是FFS结果集的约束、函数类型的约束、评估函数约束或三者的结合。用户通过参考系统约束集并使用系统提供的约束定义语言CDL 来描述具体的约束。CDL 定义的约束集传递给挖掘引擎。挖掘引擎在约束集的指导下，在数据集DB 上进行函数发掘。挖掘引擎输出结果到临时FFS。用户可以观察临时FFS，然后修改约束集，以指导挖掘继续进行。利用约束集对临时FFS进行验证以决定当前的临时FFS是否为最终结果。如果满足条件，则输出结果，否则重新启动挖掘引擎。输出的结果可以进一步处理：可以把FFS输入数据库进行管理、分析；可以把FFS中复杂函数关系分解为简单函数的乘积形式，便于理解函数所表示的本质涵义，便于直接地应用。
6. 结论
函数挖掘是数据挖掘的一个重要研究方向。传统的研究大多集中于对单个函数地挖掘。然而单个函数对复杂的现实数据的描述能力较弱。本文针对传统函数挖掘的不足，提出了频繁函数集FFS的概念，并分析了频繁k-元函数集FFSk的性质，提出了频繁函数集的挖掘算法FFSD。
结合实际应用，分析FFSD 的不足，进一步提出了基于约束的频繁函数集CFFS，最后呈现了挖掘CFFS的框架图。
提出了可配置的频繁函数集挖掘算法CFFSA。灵活,可配置称不同类型，如遗传，迭代的GEP的(3)分析FFSD 的不足，引入基于约束的频繁函数集(Constrained FFS)概念,它可以满足用户的不同兴趣需求。(4) 提出了基于约束的频繁函数集挖掘框架。
本文注重于概念和理论的阐述。在未来的研究中，将结合实际应用，采用不同的搜索算法和优化算法，实现FFSD 核心步骤generate_function_on 过程，并把FFSD 推广到具有更复杂的非数值属性数据集和超大规模数据库上，同时也将从理论角度进一步研究FFS的性质。
人次