万方数据第2期郑垂勇,等:一种聚类算法改进及其在税源分析中的应用203中,聚类不仅可用于揭示大量涉税数据中隐含的纳税人宏观分类模式(很多纳税人在发票领购使用、经营销售模式或财务处理方式上具有相当大的类似性,形成具有共性的纳税人群体,实现比传统税源分析方法更深入、有效的税收监管,“”而且可用于发现偏离于正常纳税行为的小模式,如个别纳税人的偷、漏、骗税等异常行为模式,实现重点税源筛选。常用的聚类算法【43大致可分为:划分方法(par—titioningmethods、层次方法(hierarchicalmethods和基于密度的方法(density—basedmeth—ods等等。其中,划分方法与层次方法需要用户预先确定聚类个数或算法结束条件等参数。考虑到实际涉税数据分析中,优化参数的选取依赖于数据分布的具体特性,当数据量较大时,让用户来设置参数是不切实际的。此外,层次方法的时间复杂度比较高,也难以适合大量涉税数据处理的应用需求。基于密度的聚类方法是针对复杂形状的聚类而提出的,其基本思想是每个聚类对应数据分布的一个相对密集区,通过将空间划分为若干由低密度区域(对应噪声或离群数据所分割的连通高密度区域来实现聚类分析。该方法不需要用户输入聚类个数或算法结束条件,能够处理大量的噪声数据,比较适合聚类个数未知情况下的实际涉税数据分析。典型的代表算法包括DBSCAN、0PTICS和DENCI。UE等[4。]。但目前密度聚类方法中密度门限(对应噪声或离群数据的取值大都侧重于揭示数据分布的典型聚簇特性(即大模式,“”而将偏离典型模式的小模式或离群点(outlier视为噪声加以剔除。考虑到税源监管中离群点本身具有非常重要的意义。例如,规“”模或效益远远超过其它纳税人的特大型企业往往是税务行业中值得特别关注的重点税源或优质纳税人,而各种偷税、漏税等异常涉税犯罪行为也是税源监管的重点。因此,在税源分析系统中,聚类分析与异常检测应该是两个联系密切的重要任务.而把两者结合起来综合考虑的聚类算法将具有很好的实用性。2一种改进的聚类算法2.1DENCLUE算法的基本思想DENCI,UE‘算法53是一种泛化的密度聚类算法。已知空间n∈∥中包含,z个对象的数据集D一{.r。,z:,…,丁。,其基本思想是:引入全局密度函数的核估计尸c丁,=告耋Kc孚,.其中,K(z为核函数,口为核函数的窗宽。通过搜索全局密度函数的局部极大值点(或密度吸引子实现基于中心或任意形状的聚类划分。该算法可以很好地泛化DBSCAN等密度聚类算法,但算法存在2个重要参数,即核函数的窗宽仃和全局密度门限享。其中,盯用于产生合理的全局密度估计尸(z,手用于确定最终的聚类结果。对于给定的密度门限值拿,DENCI,UE算法的聚类结果相当于用一个密度值为享的超平面切割全局密度函数尸(z所得的连通高密区。但实际应用中,由于不同聚类的密度分布往往各不相同,采用单一手值通常无法发现所有的聚类模式。如图1(a所示的测试数据集包括5个不同大小、密度的自然聚类A、B、C、D、E.其中,A、B、D、E图1DENCLUE算法的不同聚类结果Fig.1ClusteringresultsofDENCLUEalgorithm万方数据万方数据第2期郑垂勇,等:一种聚类算法改进及其在税源分析中的应用205计算空间任一点的密度函数值及其梯度值所需要的时间为B+树的平均检索时间,即O(19(以州a,搜索临界点,对数据进行初始划分的时间复杂度为0(咒・lg(ngfId;令密度函数的鞍点个数为“刀。削,对初始聚类进行递归合并的时间复杂度为O(‰削k・lg(,29rid。算法总的时间复杂度为0(咒+(咒州+,z+以。址・Ig(Hgrid。显然,改进算法具有与DEN—CI。UE算法相似的时间复杂度,即O(九・log(ntaa【5],能较好地满足大规模涉税数据分析的应用需求。3实验结果与比较本文采用2个模拟数据集和1个实际的涉税数据集来检验改进算法的有效性,所有程序用Matlab7实现,测试实验在1台PC机(WindowsXPProfes—sional上进行。实验1测试数据Datasetl采用图1(a所示的测试数据集,该数据集包含3200个数据点,数据分布呈现5个不同大小、密度的球形和椭球形聚类。根据§2.1的分析,无论用户如何调整密度门限拿,DENCLUE算法都不能有效揭示该数据分布的5个自然聚类。采用本文算法对其进行聚类分析(令亭=O,聚类结果如图2(b所示,显然,该算法能够发现不同形状、大小...