基于网格和密度的保险业务投资风险规则聚类

邱 洋

（上海电子信息职业技术学院计算机应用系 201411）

1 引言

聚类分析也称群分析或者点群分析，是研究多要素事物分类问题的数量方法。与数据挖掘中的分类不同，它是在预先不知道目标数据库具体分类的情况下，希望将所有的纪录组成不同的类，并实现以某种度量为标准的相似性在同类间最小化，而在不同类间最大化。

优秀的聚类分析方法要求良好的伸缩性，能处理不同字段类型、异常数据和高维数据。能发现任意形状的聚类，同时应满足输入参数对领域知识的弱依赖性、结果对输入记录顺序的无关性、结果可解释性和可用性好，等等。这些都是传统的单一聚类手段所不能达到的。

2 基于网格和密度的聚类算法

2.1 聚类基于的数据类型

聚类算法通常是基于如图1的“数据矩阵(data matrix，或称为对象与变量结构)”和“相异度矩阵（dissimilarity matrix，或称为对象－对象结构）”这两种具有代表性的数据结构。如果数据以数据矩阵的形式出现，那么在聚类之前通常要将它转换为相异度矩阵。

图1 数据矩阵和相异度矩阵的表示形式

相异度矩阵把对象间的相似度量化为距离函数d(i,j)。通常的计算公式有：欧几里得距离、曼哈顿距离。它们具有一些共性：d(i,j)≥ 0，d(i,i)= 0，d(i,j)=d(j,i)，d(i,j)≤ d(i,h)+d(h,j)。而明氏距离则是两者的通式：

其中，i=(xi1,xi2…,xip)和 j=(xj1,xj2…,xjp)是两个 p维的数据对象，q是一个正整数。当q＝1时为曼哈顿距离；q＝2时为欧氏距离。并且为不同的变量赋予不同的权重。在实际计算距离时，只能凭主观确定各个变量的权重，不同的权重对计算结果影响较大。

2.2 相关概念

在多维大集合中分散的数据点不易形成高支持度的聚类。单纯采取基于密度算法的问题在于如何从源空间中自动发现子空间，使得所有数据投影后能形成具有较高点集密度的区域。如果以子空间为分析对象，将单元点密度的计算转换成简单的点计数，则处理速度可独立于对象的数目，而仅依赖于量化空间中的网格数。下面给出复合算法涉及的相关概念：

(1) A=｛A1,A2,…,Ad｝是 n个域的集合，S=A1×A2×…×Ad是 一 个 d维 空 间。输 入 点 集 v=｛v1,v2,…,vm｝，vi=｛vi1,vi2,…,vid｝，vij∈ Aj。分 S每 一维为 ξ 个相同区间 u=｛u1,u2,…,ud｝，li≤ ui＜hi。点 v落 入 u中 当 且 仅 当li≤vi＜hi对每个ui都成立。

(2) 对于密度阈值τ，称单元格u绸密，当且仅当selectivity(u)=单元格中的点数/总的点数＞τ。称k维中的两个单元格 u1=｛rt1,rt2,…,rtk｝、u2=｛r’t1,r’t2,…,r’tk｝连通，当且仅当它们有一个公共面，或者它们都跟另一单元格u3连通。

(3) 对于区域R和聚类C，有R∩C=R，当且仅当没有一个R的超集R’也包含于C时，R最大。C的最小描述是最大区域的一个集合r，其最大区域刚好覆盖C，它没有冗余。为此，这样的区域可表示为区间的交。例如：(20≤age＜65)∧(5≤salary＜7)。

(4) 单调性引理：若k维空间是密集的，则它在任一个k-1维子空间上的投影也密集。

根据以上描述可知，聚类就是空间中连通的所有的“密集”单元格的最大集合。

2.3 算法实现

2.3.1 确定包含有聚类的子空间

对于高维数据，上述聚类方法还需借助一种自底向上方案。根据单调性引理，可从k-1维空间中发现的密集单元来推断k维空间中的候选密集单元。算法如下（设维经辞典排序）：

1）令k→1，遍历一遍目标数据库找出所有一维的密集单元格，令所组成的集合为D1；

2）由k维的密集单元格集合Dk生成k+1维的候选密集单元格集合Ck+1；

3）若Ck+1为空则转（4）；否则再次遍历目标数据库，计算候选单元格中的selectivity，依据单调性原理将非密集单元格去掉后，记为集合Dk+1，k→k+1并转（2）；

4）算法结束。得到包含聚类维数最高的子空间。至此完成这一步的目标。

图2 算法的操作对象树

算法的操作对象是一棵如图2（仅描述两维子空间的情况）的树，其叶节点是一个描述某个子空间中的单元格的链表结构。根据维号建立树可快速搜索出单元格所在子空间，也方便从k维的密集单元格生成k+1维的候选单元格。链表结构简化了回收非密集单元格或增加新单元格描述的操作。至此，该结构已能很好地满足上述的算法。实现该步骤的伪代码如下：

//构造一维树

pRoot=pJoin=innode=alloc();

for(i=0;i＜m_lColCount;i++){pLeaf1=pJoin-＞pSon[i].pLeaf=leaf_alloc();……}

lCurrentDim=1;

//扫描database决定所有单元格中lcount值

while(lCurrentDim＜n_lColCount){……while(！pRs-＞MY_EOF){transform();

//将相应的单元个数中的lCount值更新……}

deleteNonDense();doMdlPrunnint();

//去掉非密集的单元格，基于MDL剪枝

//做联接操作，若无新候选集产生，则算法结束。最后将子空间维数加1

……}

设存在密集单元格的最高维子空间维数为t，数据库中记录总数为m，则上述代码有2t个单元格，该步骤的时间复杂度为O(ct+mt)。对于高维数据对象，可采用基于MDL的裁剪算法：依据单调性引理，将各子空间依据其中所有密集单元格包含点的总数进行排序，保留包含点的个数多的子空间，以减轻计算量。

2.3.2 找出给定子空间中的聚类

抽样调查结果显示，参加城阳区乡村旅游的旅游者的目的是多样化、复合型的。其中看风景，呼吸新鲜空气；释放都市紧张的生活压力；购买新鲜的农产品；品尝当地特色；了解民俗，体验特色活动的旅游者占到一半以上，而去了解农业生产知识、休闲度假等方面的目的较少。本文认为这其实也是城阳区乡村旅游的发展方向所在，要更多的发展农业体验旅游、休闲度假旅游。

输入一个处在同一子空间的密集单元格的集合D，输出D的一个划分｛D1，D2，…，Dq｝（Di中所有密集单元格相邻，在D（ui∈Di,uj∈Dj）中没有两个单元格相邻。这类似于寻找图的连通分支，可采用深度或广度优先搜索。因此定义图的数据结构是关键点，这里用矩阵表示法。另外，用堆栈模拟需递归调用的DFS算法。数据结构和算法的伪代码如下：

struct cluster{……}; //记录每个簇类cluster的信息

struct oneSubSpace{……}; //描述一个子空间

for(k=0;k＜subunitsCoun;k++){……} //建立邻接矩阵

//找出所有的连通分支while (1)

for(long ltemp1=0;ltemp1＜subUnitsCount;ltemp1++){if(pUnitsFlag[ltemp1]==0) break;}……

//用bfs(广度优先)算法来存放连通分支中所有点的栈及其点……

while(lLow-lHigh){ //bfs算法主体i=pstack[lLow];

for(k=0;k＜subUnitsCount;k++){

if(pConnectMatrix[i*subUnitsCount+k]==1&&pUnitsf lag[k]==0)

{pstack[lHigh]=k;pUnitsFlag[k]=1;lHigh++;}}lLow++;}

pCluster1=cluster_alloc(lHigh);//分配一个描述簇cluster的结构//记录该cluster类中的点，把新产生的cluster放到描述pOnesubspace的cluster链末

for(k=0;k＜lHigh;k++) put_in_cluster(pOnesubspace,pCluster1); }

2.3.3 生成一个聚类的描述

输入k维子空间中的一密集单元格集合，其中元素构成聚类C。输出一个区域集合R，其任一成员都包含于C，且C中任一单元格至少包含于R的一个成员。这里采用NP-hard的贪婪算法，即寻求局部最优可达全局较优。首先找出覆盖C中所有单元格的所有最大区域，结果C中的任一单元格至少被一个这样的最大区域覆盖。然后将最大区域的个数最小化，使最后得到的集合仍能覆盖C中所有单元格。数据结构和算法的伪代码如下：

struct MaxRegion {…… //描述一个类矩形，即上下界

//定义一个三维数组，low，high，区间个数 …… };

for(k=0;k＜pCluster1-＞unitsCount;K++ // 清除覆盖标记

……

//一直找到cluster中的单元被全部覆盖

while(1){ if(k==pCluster1-＞unitsCount breake;//如果全部覆盖则结束

……

while(k＜lCurrentDim){

up_increment();down_increment();k++;}//先往上再往下增长，得到一个最大区域

insert_region(pRegion1); }

minize_regoin(pRegionList); //描 述cluster的最大区域的个数最小化

3 保险业务数据聚类分析

保险是一项风险业务，其成功的关键在于正确的风险评估可达到设置具有竞争力的保费和覆盖风险之间的平衡。不断变化的市场导致每年都要根据往年数据中的主要因素进行分析和判断来调整保费。保险专业人员通常根据经验对大量统计报表作出粗略分析和决策，而数据挖掘提供了分析保险投资组合数据库的环境。这里采取网格密度聚类算法，在保单及索赔信息数据库中找出保单中风险较大的部分，从而得出一些实用的风险控制规则来指导工作。

系统基于B/S分布式层次模型。客户端可直接调取应用服务器上的com组件（包含挖掘数据的定义、数据预处理、挖掘内核、模式表达与解释等模块）。数据源接口采用可以和数据挖掘库、数据集市等系统交互的OLEDB FOR ORACLE。某市的医保数据主要由单位信息表（tdw_information）、人员信息表（try_information）、区间（一个月）内索赔单据表(tsp_information)等组成。进行数据挖掘之前先要根据主观经验去除冗余信息。在分析保险业务时，投保人是否索赔是关键信息，应把数据集中的“是否索赔”（该属性直接由“索赔次数”得出，有一定重复性可以去除）作为标签属性，其他属性如个人保险号、个人姓名、单位名称、投保日期等属于不相关信息。经过数据整理，将得到的描述一定时间段内个人索赔信息的数据表作为训练集。再根据列重要性选出描述性属性影响程度最大的列。过程见图4：

图3 基本数据结构及其聚类的结果

聚类时需输入两个参数ξ和τ，其中ξ将影响网格结构的最底层粒度。若粒度较细，处理代价将显著增加；反之会降低聚类分析质量。这里指定ξ＝10，τ＝0.2，把每一维分为10个区间，如[25，30)作为年龄维第一个区间。计算数据库中混合型变量对象之间的相异度有两种方法：一是将变量按类型分组，对每种类型的变量单独聚类分析，若得到兼容的结果则方法可行，实际上这种可能性很小；二是将所有变量一并做一次聚类分析。通常是将不同变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域[0.0，1.0]上。

进行结果聚类描述时要注意，对于数据表格对象，可能多个子空间都含有聚类且维数一样。同样，一个子空间中可能存在多个聚类，一个聚类的描述可能需要多个最大区域，而一个区域的描述需要给出它的每一维的上下界。这些元素之间存在如图5所示的一对多关系。

图4 簇的子空间、簇、区域、维的关系图

对表tcls_information聚类得出的几个簇可用DNF表示为：（55≤ x1＜75）∧ (9000≤ x2＜21000)∧ (1≤ x3＜6)∨（25≤ x1＜50）∧ (6000 ≤ x2＜12000) ∧ (0≤ x3＜1)。从中看出这样的规则：年龄和收入将较大地影响到索赔情况，即年龄或收入与索赔的概率成正比。这体现了我国医保实施的实情，因此可考虑适当提高或降低相应投保群体的保单费用。由于该市医疗费用的支付方法与单位的企事业性质有关，故投保人还应根据自己的实际情况来支付费用。

4 结束语

实践证明，文中所讨论的聚类算法能自动发现有价值的最高维子空间而无需用户指定，能过滤“孤立点”；对元组输入顺序不敏感，无需假设任何规范的数据分布；可随数据规模大小而灵活地线性伸缩；能有效处理高维数据等。然而，仍有一些需作出持续改进的方面：

1.递归运行的算法将数据空间划分为更多的网格，使得落入单个网格中的点数减少。若保持τ值不变，就基本定出了最后能找到的子空间的维数，这与自动发现包含有趣模式的子空间的要求有一定矛盾。因此可尝试让τ变化或者用排序、剪切的办法来解决问题。

2.数据表格中的每一列的含义和数据类型可能不同，本算法目前未能很好地涉及区间标度变量、对称和不对称二元变量、标称变量等混合类型的数据。

3.为了使聚类的结果更加可释和可用，最好在算法各阶段更形象和可视化地表示数据。

［1]韩家炜，Kamber Micheline.数据挖掘概念与技术[M].北京：机械工业出版社，2001.

［2]高永梅，黄亚楼.一种基于网格和密度的数据流聚类算法[J].计算机科学，2008，35（2）：134-137.

［3]马帅，王腾蛟，唐世渭，等.一种基于参考点和密度的快速聚类算法[J].软件学报，2003，14（6）：1089-1095.

［4]Qian Wei-ning，Gong Xue-qing，Zhou Ao-ying.Clustering in Very Large Databases Based on Distance and Density[J].Comp Sei & Technol Jan，2003，18(1)：67-76.

［5]Sun Zhiwei，Zhao Zheng，Wang Hongmei.CLUGD ：A fast clustering algorithm based on grid and density[C]//Proceedings of the Canadian Conference on Electrical and Computer Engineering.Saskatoon，Canada，2005：2297-2300.