基于Agent的数据挖掘技术在公共服务信誉检测中的应用

1、基于Agent的数据挖掘技术在公共服务信誉检测中的应用李春生大庆石油学院计算机与信息技术学院1、 摘要 随着数据库技术和网络技术的成熟和应用，公共服务行业产生和收集了大量的数据。如何从不同层次的信息中发现潜在的有价值的规则以便在管理和经营中迅速地做出正确的决策，这就要求新技术和工具的出现帮助管理人员将海量数据转换成有用的信息和知识。我们设计了基于多Agent技术的数据挖掘模型来挖掘公共服务中的无信用行为，并根据发现的模式来对用户进行信誉评估。作为模型的验证，我们为大庆石油管理局供水公司建立了水费信用检测系统。2、 引言数据挖掘技术是在数据库中发现有用的知识。Agent技术在构建复杂软件系统工作

2、中，为我们提供了一种令人兴奋的方式。把多Agent技术引入到数据挖掘中，用agent实现数据挖掘过程的各个部分。利用多智能体实现数据的规约、准备，知识的自动抽取及根据所挖掘知识对数据的识别。使整个系统实现了知识性、智能性。3、 基于Agent的数据挖掘系统的建立 数据挖掘系统模型包括explore agent , data mining agent, and Human-Computer interface Agent evaluation agent .在数据的探索阶段，采用了决策树算法选择和分类有关的属性，并且去除了矛盾数据以免数据干扰，确定适合用于挖掘和训练的数据集合。可用于挖掘模型建立

3、的算法很多，可以根据调查，和综合测评决定。本模型以神经网络BP算法为例论述了挖掘模型的建立。系统协作模型：在多Agent系统中，社会智能不但来源于个体组织的智能水平，还来源于群体的通信交互与协作。为了保证挖掘模式的动态学习，需要多Agent“社会”内部各个Agent实体组织的协同工作，以实现信息间的交换，转化和同步。协作意味着一个Agent在采取行动或作出决定定时，受其他同类或异类Agent的状态、知识的影响，正因如此，系统中各Agent才能根据运行过程中所传递的消息来协调彼此行为，实现合作或消解冲突，完成问题并行求解。 Agent接收到任务后可以进一步分解，Agent能够连续不断的感知外界发

4、生的以及自身状态的变化，并产生相应的动作。在本系统中，每个成员Agent仅有不完全的信息和问题求解能力，数据是分散或者分布的，计算是异步的。因此，Agent通过协同计算以完成挖掘和识别任务。Agent间的协作机制包含许多方面的内容，本系统从三方面定义协作：消息协议，通信方式，交互协议。在系统实现中采取直接/被动合作模型。交互协议：根据合作模型交互协议涉及了三种通信行为有被动服务请求，直接被动服务允诺，和通信行为。基于这三种通信行为交互协议的描述为：一方主体i（服务请求方的角色）首先向另一方主体j（服务允诺放和服务提供方的角色）发出被动服务请求，要求服务提供方主体j为它提供服务；服务允诺方主体j

5、根据服务请求向服务请求方主体i做出直接被动服务允诺，被动的提供服务并通过通知通信行为将服务结果返回给服务请求主体i，服务被提供则意味着合作结束。通信方式：根据应用的特点，通信方式采取Agent之间建立信道的点对点消息传递通信方式，基于该通信信道进行双向，对等的消息传递。消息协议：Agent通过消息协议可以互相理解和交换信息，并对消息做出处理。在本系统实现中，消息协议采用了基于KQML语言定义的面向数据挖掘的通信语言，它以KQML作为协同通讯的协议，对其进行扩充，采用XML来描述消息的内容体，在此基础上设计了一套比较完整的、可扩充的通讯语言(协议)。4、 Explore Agent原始数据经清理

6、、集成、变换后存储于数据仓库中。但是由于数据仓库中选择数据，数据集将非常庞大，使复杂的数据分析和挖掘需要很长的时间。这样，分析会变得不现实或不可行2。因此，我们设计了Explore Agent来完成数据的维归约。Explore Agent会始终询问数据是否发生变化，当得到变化通知，则请求数据并根据更新的数据得到新的规约模型。并且通知挖掘Agent。挖掘Agent在得知模型更新后向Explore Agent查询最新的模式。根据Explore Agent提供的知识完成样本数据的选择。用于分析的数据可能包含数以百计的属性，其中有些是与挖掘任务相关的，有些是无关的。Explore Agent的任务就是

7、从原属性集合中，寻找一个好的子集。使得数据类的概率尽量分布尽可能的接近使用原有属性的原分布。由于决策树具有可以清晰显示重要属性的优点，我们选择了用信息增益度量建立分类决策树的方法完成属性的估计度量。The design Explore agent : Explore agent的任务为利用已有业务数据，通过决策树算法逐层选择对于客户分类产生最大影响的客户背景要素即可用于挖掘的相关属性，然后计算该客户所属的客户类别与该种客户分类之间的关系，这样依次扩展，最后形成一个完整的决策树，不出现在树中的所有属性假定为不相关的，出现在树中的属性构成了归约后的最佳子集。Explore Agent会始终询问数据

8、是否发生变化，当得到变化通知，则请求数据并根据更新的数据得到新的规约模型。 处理器归纳构造的决策树模型类似于流程图的结构。每个内部节点（非树叶）表示一个属性上的测试，每个分支对应于测试的一个输出，每个外部节点（树叶）表示一个判定类。在每个节点上算法选择“最好”的属性，将数据划分为类。一般来说，挖掘任务是分类，而确定属性子集又选用了挖掘算法，可以达到更高的精确性2。属性选取的流程如图：Agent处理中心采用决策树的经典算法ID3算法来处理数据，使用information gain度量来选择测试属性。关于ID3算法的详细内容可以参见资料。下面介绍Agent 处理中心的主要结构：1）数据预处理：首先

9、，对所有用户进行类别划分。确保每个客户都具有正确的类别属性，以便在模型训练中起到正确的指导作用。其次，将原数据中数值型数据，如：水费系统中的用户单位时间内应缴纳费用进行离散化，生成单位时间内应缴纳费用字段编码。2）算法实现：核心算法由一个类来实现，主要包括四个方法：数据前期处理方法（DataPrepare），算法生成方法（GenerateDecisionTree），模型存储方法（ModelStore），模型显示方法（ModelDisplay）。工作过程为由Dataprepare方法完成算法执行前的数据预处理及前期初始化工作，处理完毕的数据进入GenerateDecisionTree方法运作得出

10、决策树模型。此时，模型存储方法将所生成的模型存储于Agent的知识库中，显示方法以类似于流程图的树结构向用户显示所生成模型的结构。数据的存储结构根据信息量的大小，Explore Agent根据知识库中的模型提取节点的信息，选择出和分类结果真正相关的数性集合。为挖掘模型选择良好的训练属性集合。5、挖掘Agent：挖掘Agent接收到更新的决策树模型，由于Explore Agent知识库中的决策树模型的数据结构存储为树，根据得到的知识Value Reduction Agent可以遍历决策树获得不同模式的可信度。并通过连接数据库，选取可信程度高的模式的样本作为训练样本。样本集的分布特征对网络的训练有

11、根大的影响。实际中许多问题由于样本没有经过精心的筛选，致使在同一个训练集中若干样本出现矛盾现象即存在具有相近输入向量的两个或多个样本的输出相异。针对这一问题，我们利用决策树的决策规则来完成了矛盾样本的去除。试验证明，该方法对于减少矛盾数据对网络的影响有效。神经网络可以模仿人的头脑，通过向一个训练数据集学习和应用所学知识来生成分类和预测的模式。在数据是不定形的并且无法观察到明显的规则时，这种方法依然有效。在本模型中，采用了神经网络中附加动量因子技术的BP网络训练方法作为挖掘Agent的核心算法。BP网络改进分析：多层神经网络是由输入层、输出层及它们之间一个或多个隐层构成 ，其BP算法包括前馈传播

12、和误差反向传播两个过程，首先输入信号从输入层经隐层单元传向输出层，如果输出层上不能得到期望结果，则转入反向传播，将误差信号反向由输出层传向输入层，通过修改各层神经元的权值，使得误差信号最小。在系统中，采用了双隐层单元BP网络。通过DecisionAgent知识库中模型节点知识所提供的属性集合确定网络的输入单元个数。 定义：Wij上一层单元到本层单元的连接权。单元的偏置。On单元的输出。BP网络的数学模型：1）提供训练集，输入数据向量为x1,x2,xn输入层节点j的输出为xj1=f (xj),为了使BP网络隐含层的输入规范化，f为归一函数：f=(X-Xmin)/(Xmax-Xmin)其中，Xmi

13、n为节点输入的下限，Xmax为节点输入的上限。2）隐含层及输出层的输入为：Ij=偏置用来充当阈值，改变单元的活性。3）将激活函数作用于输入向量逐级计算输出值。激活函数选用了S型函数对于节点J输出为4）BP网络的权值调整基于实际输出与期望输出的最小均方差即：E=C：输出层单元数；Tk：输出层单元k的期望输出； 5）为了使学习以尽可能减小误差均方差的方式进行，因此，采用使E沿梯度方向下降的方式进行调整： ； 对于，中间隐层，则采用递归的方法从输出节点K返回到中间隐层。6）权重，单元偏置的修改公式为：； 用步骤5）多次修改网络权值，直到达到精度要求或网络不收敛。传统的BP算法在修正权值时只按照t时刻

14、负梯度方向进行修正而没有考虑以前时刻的梯度方向，从而常常使训练过程产生振荡。为了解决以上问题，系统设计的修正权值方案为惯性系数指数增长法。即按设计比例加上前一次学习时校正量：； ：本次校正量；：由梯度下降求出的校正量；：前次校正量。：权值的总数和限定学习次数的乘积。由上式可知：当前一次的校正量过调时，惯性项与本次误差校正项符号相反，使得本次实际校正量减小，起到减小振荡的作用;当前次校正量欠调时，惯性项与本次误差校正项符号相同，起到加速校正的作用。另外，动量因子还可以防止学习过程在错误表面上的表层局部最小化时终止3。在系统设计的动量项指数增长方案中，惯性因子是一个变量，且随校正过程不断变化。当校

15、正方向为欠调时加大调整步伐，当校正方向为过调时减小调整步伐。从而更好的达到网络收敛的效果。评估Agent为了获得优良的网络性能，我们需要对建立的模型进行迭代估计。评估Agent通过对挖掘Agent发现的模式进行自动评估，来确定识别Agent所需要的识别模型。挖掘Agent通过处理器的工作抽取相关的变量得出学习的模式，该模式被告知评估Agent。评估Agent通过对模型的检测给出性能评价，并将评价送入评价处理模块。处理模块采用平均方法对性能进行评价。由处理模块统一处理，选择有趣的挖掘模式。最终的模式被提交给识别Agent作为识别模型。识别Agent通过人机界面Agent与管理人员交互，完成对用户

16、的识别。6、案例分析：目前，供水部门费用拖欠问题逐渐引起了行业的注意。对于饱受欠费之苦的供水部门建立健全长效的预警机制尤为必要。本节基于上述模型，介绍了水费行业用户费用拖欠预警系统模型的建立，并对运行效果进行了描述。1） Explore Agent从数据集中选择用于分析的数据，将可用数据送入Explore Agent进行处理。Agent根据历史数据决定可以完成正确分类任务的属性集合。经过数据处理可以得到以下决策树：决策树模型节点信息以树形结构被存储于知识库，向挖掘Agent提供和类别相关联的属性集合。外购水总表、含税状况、结算单位、与预计水表差值、有无自备井、用水性质、本月应交费用、用水地点属

17、性集被选择为挖掘属性，data mining Agent的预处理过程将对相应属性内容进行量化。数值型字段的分界值作为量化参考。数据挖掘模型的建立样本的选则： 通过Explore Agent的信息可以得知可信度高的模式。在数据库中查询符合可信度高的模式的样本进行训练。减少学习样本中，矛盾数据的出现。经过测试我们比较了没有经过样本选择和经过样本选择的结果：没有经过样本选择的收敛曲线 经过样本选择的收敛曲线1、 参数确定：经过决策树Agent的工作，可以获得和分类相关的属性集和。我们将这些用户因素经过量化、归一预处理后，转换为数字信息作为网络的输入向量。经过试验，本设计采用两个隐层每个隐层二十个节点

18、的网络。网络的输出为对应与输入因素的一个关于用户欠费风险的判断。训练指导中，如果用户欠费则风险置1，否则置0。网络的学习因子为=0.3；惯性系数初始化为；。 2、训练学习为了得到更好的训练模型，我们抽取了200条样本，分别对标准BP网络，恒定惯性量BP网络，和惯性系数指数增长的网络性能作了测试，测试结果如下所示：Goal：0.1 Goal：0.1 Goal：0.1Epochs：601;Time：11 seconds Epochs：256;Time： 7 seconds Epochs：111;Time：2 secondsTypical BPA BPA with invariable momentum BPA with momentumincrease by exponentialGoal：0.01 Goal：0.01 Goal：0.01Epochs: 10914;Time: 11 seconds Epochs: 5446;Time: 46seconds Epochs: 854;Time: 17secondsTypical BPA BPA with invariable momentum BPA with momentumincrease by exponential系统评估：在系统中