基于網(wǎng)格和密度的保險(xiǎn)業(yè)務(wù)投資風(fēng)險(xiǎn)規(guī)則聚類

邱 洋

（上海電子信息職業(yè)技術(shù)學(xué)院計(jì)算機(jī)應(yīng)用系 201411）

1 引言

聚類分析也稱群分析或者點(diǎn)群分析，是研究多要素事物分類問題的數(shù)量方法。與數(shù)據(jù)挖掘中的分類不同，它是在預(yù)先不知道目標(biāo)數(shù)據(jù)庫具體分類的情況下，希望將所有的紀(jì)錄組成不同的類，并實(shí)現(xiàn)以某種度量為標(biāo)準(zhǔn)的相似性在同類間最小化，而在不同類間最大化。

優(yōu)秀的聚類分析方法要求良好的伸縮性，能處理不同字段類型、異常數(shù)據(jù)和高維數(shù)據(jù)。能發(fā)現(xiàn)任意形狀的聚類，同時(shí)應(yīng)滿足輸入?yún)?shù)對領(lǐng)域知識的弱依賴性、結(jié)果對輸入記錄順序的無關(guān)性、結(jié)果可解釋性和可用性好，等等。這些都是傳統(tǒng)的單一聚類手段所不能達(dá)到的。

2 基于網(wǎng)格和密度的聚類算法

2.1 聚類基于的數(shù)據(jù)類型

聚類算法通常是基于如圖1的“數(shù)據(jù)矩陣(data matrix，或稱為對象與變量結(jié)構(gòu))”和“相異度矩陣（dissimilarity matrix，或稱為對象－對象結(jié)構(gòu)）”這兩種具有代表性的數(shù)據(jù)結(jié)構(gòu)。如果數(shù)據(jù)以數(shù)據(jù)矩陣的形式出現(xiàn)，那么在聚類之前通常要將它轉(zhuǎn)換為相異度矩陣。

圖1 數(shù)據(jù)矩陣和相異度矩陣的表示形式

相異度矩陣把對象間的相似度量化為距離函數(shù)d(i,j)。通常的計(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)是兩個(gè) p維的數(shù)據(jù)對象，q是一個(gè)正整數(shù)。當(dāng)q＝1時(shí)為曼哈頓距離；q＝2時(shí)為歐氏距離。并且為不同的變量賦予不同的權(quán)重。在實(shí)際計(jì)算距離時(shí)，只能憑主觀確定各個(gè)變量的權(quán)重，不同的權(quán)重對計(jì)算結(jié)果影響較大。

2.2 相關(guān)概念

在多維大集合中分散的數(shù)據(jù)點(diǎn)不易形成高支持度的聚類。單純采取基于密度算法的問題在于如何從源空間中自動發(fā)現(xiàn)子空間，使得所有數(shù)據(jù)投影后能形成具有較高點(diǎn)集密度的區(qū)域。如果以子空間為分析對象，將單元點(diǎn)密度的計(jì)算轉(zhuǎn)換成簡單的點(diǎn)計(jì)數(shù)，則處理速度可獨(dú)立于對象的數(shù)目，而僅依賴于量化空間中的網(wǎng)格數(shù)。下面給出復(fù)合算法涉及的相關(guān)概念：

(1) A=｛A1,A2,…,Ad｝是 n個(gè)域的集合，S=A1×A2×…×Ad是 一 個(gè) d維 空 間。輸 入 點(diǎn) 集 v=｛v1,v2,…,vm｝，vi=｛vi1,vi2,…,vid｝，vij∈ Aj。分 S每 一維為 ξ 個(gè)相同區(qū)間 u=｛u1,u2,…,ud｝，li≤ ui＜hi。點(diǎn) v落 入 u中 當(dāng) 且 僅 當(dāng)li≤vi＜hi對每個(gè)ui都成立。

(2) 對于密度閾值τ，稱單元格u綢密，當(dāng)且僅當(dāng)selectivity(u)=單元格中的點(diǎn)數(shù)/總的點(diǎn)數(shù)＞τ。稱k維中的兩個(gè)單元格 u1=｛rt1,rt2,…,rtk｝、u2=｛r’t1,r’t2,…,r’tk｝連通，當(dāng)且僅當(dāng)它們有一個(gè)公共面，或者它們都跟另一單元格u3連通。

(3) 對于區(qū)域R和聚類C，有R∩C=R，當(dāng)且僅當(dāng)沒有一個(gè)R的超集R’也包含于C時(shí)，R最大。C的最小描述是最大區(qū)域的一個(gè)集合r，其最大區(qū)域剛好覆蓋C，它沒有冗余。為此，這樣的區(qū)域可表示為區(qū)間的交。例如：(20≤age＜65)∧(5≤salary＜7)。

(4) 單調(diào)性引理：若k維空間是密集的，則它在任一個(gè)k-1維子空間上的投影也密集。

根據(jù)以上描述可知，聚類就是空間中連通的所有的“密集”單元格的最大集合。

2.3 算法實(shí)現(xiàn)

2.3.1 確定包含有聚類的子空間

對于高維數(shù)據(jù)，上述聚類方法還需借助一種自底向上方案。根據(jù)單調(diào)性引理，可從k-1維空間中發(fā)現(xiàn)的密集單元來推斷k維空間中的候選密集單元。算法如下（設(shè)維經(jīng)辭典排序）：

1）令k→1，遍歷一遍目標(biāo)數(shù)據(jù)庫找出所有一維的密集單元格，令所組成的集合為D1；

2）由k維的密集單元格集合Dk生成k+1維的候選密集單元格集合Ck+1；

3）若Ck+1為空則轉(zhuǎn)（4）；否則再次遍歷目標(biāo)數(shù)據(jù)庫，計(jì)算候選單元格中的selectivity，依據(jù)單調(diào)性原理將非密集單元格去掉后，記為集合Dk+1，k→k+1并轉(zhuǎn)（2）；

4）算法結(jié)束。得到包含聚類維數(shù)最高的子空間。至此完成這一步的目標(biāo)。

圖2 算法的操作對象樹

算法的操作對象是一棵如圖2（僅描述兩維子空間的情況）的樹，其葉節(jié)點(diǎn)是一個(gè)描述某個(gè)子空間中的單元格的鏈表結(jié)構(gòu)。根據(jù)維號建立樹可快速搜索出單元格所在子空間，也方便從k維的密集單元格生成k+1維的候選單元格。鏈表結(jié)構(gòu)簡化了回收非密集單元格或增加新單元格描述的操作。至此，該結(jié)構(gòu)已能很好地滿足上述的算法。實(shí)現(xiàn)該步驟的偽代碼如下：

//構(gòu)造一維樹

pRoot=pJoin=innode=alloc();

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

lCurrentDim=1;

//掃描database決定所有單元格中l(wèi)count值

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

//將相應(yīng)的單元個(gè)數(shù)中的lCount值更新……}

deleteNonDense();doMdlPrunnint();

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

//做聯(lián)接操作，若無新候選集產(chǎn)生，則算法結(jié)束。最后將子空間維數(shù)加1

……}

設(shè)存在密集單元格的最高維子空間維數(shù)為t，數(shù)據(jù)庫中記錄總數(shù)為m，則上述代碼有2t個(gè)單元格，該步驟的時(shí)間復(fù)雜度為O(ct+mt)。對于高維數(shù)據(jù)對象，可采用基于MDL的裁剪算法：依據(jù)單調(diào)性引理，將各子空間依據(jù)其中所有密集單元格包含點(diǎn)的總數(shù)進(jìn)行排序，保留包含點(diǎn)的個(gè)數(shù)多的子空間，以減輕計(jì)算量。

2.3.2 找出給定子空間中的聚類

抽樣調(diào)查結(jié)果顯示，參加城陽區(qū)鄉(xiāng)村旅游的旅游者的目的是多樣化、復(fù)合型的。其中看風(fēng)景，呼吸新鮮空氣；釋放都市緊張的生活壓力；購買新鮮的農(nóng)產(chǎn)品；品嘗當(dāng)?shù)靥厣涣私饷袼?，體驗(yàn)特色活動的旅游者占到一半以上，而去了解農(nóng)業(yè)生產(chǎn)知識、休閑度假等方面的目的較少。本文認(rèn)為這其實(shí)也是城陽區(qū)鄉(xiāng)村旅游的發(fā)展方向所在，要更多的發(fā)展農(nóng)業(yè)體驗(yàn)旅游、休閑度假旅游。

輸入一個(gè)處在同一子空間的密集單元格的集合D，輸出D的一個(gè)劃分｛D1，D2，…，Dq｝（Di中所有密集單元格相鄰，在D（ui∈Di,uj∈Dj）中沒有兩個(gè)單元格相鄰。這類似于尋找圖的連通分支，可采用深度或廣度優(yōu)先搜索。因此定義圖的數(shù)據(jù)結(jié)構(gòu)是關(guān)鍵點(diǎn)，這里用矩陣表示法。另外，用堆棧模擬需遞歸調(diào)用的DFS算法。數(shù)據(jù)結(jié)構(gòu)和算法的偽代碼如下：

struct cluster{……}; //記錄每個(gè)簇類cluster的信息

struct oneSubSpace{……}; //描述一個(gè)子空間

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

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

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

//用bfs(廣度優(yōu)先)算法來存放連通分支中所有點(diǎn)的棧及其點(diǎn)……

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);//分配一個(gè)描述簇cluster的結(jié)構(gòu)//記錄該cluster類中的點(diǎn)，把新產(chǎn)生的cluster放到描述pOnesubspace的cluster鏈末

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

2.3.3 生成一個(gè)聚類的描述

輸入k維子空間中的一密集單元格集合，其中元素構(gòu)成聚類C。輸出一個(gè)區(qū)域集合R，其任一成員都包含于C，且C中任一單元格至少包含于R的一個(gè)成員。這里采用NP-hard的貪婪算法，即尋求局部最優(yōu)可達(dá)全局較優(yōu)。首先找出覆蓋C中所有單元格的所有最大區(qū)域，結(jié)果C中的任一單元格至少被一個(gè)這樣的最大區(qū)域覆蓋。然后將最大區(qū)域的個(gè)數(shù)最小化，使最后得到的集合仍能覆蓋C中所有單元格。數(shù)據(jù)結(jié)構(gòu)和算法的偽代碼如下：

struct MaxRegion {…… //描述一個(gè)類矩形，即上下界

//定義一個(gè)三維數(shù)組，low，high，區(qū)間個(gè)數(shù) …… };

for(k=0;k＜pCluster1-＞unitsCount;K++ // 清除覆蓋標(biāo)記

……

//一直找到cluster中的單元被全部覆蓋

while(1){ if(k==pCluster1-＞unitsCount breake;//如果全部覆蓋則結(jié)束

……

while(k＜lCurrentDim){

up_increment();down_increment();k++;}//先往上再往下增長，得到一個(gè)最大區(qū)域

insert_region(pRegion1); }

minize_regoin(pRegionList); //描 述cluster的最大區(qū)域的個(gè)數(shù)最小化

3 保險(xiǎn)業(yè)務(wù)數(shù)據(jù)聚類分析

保險(xiǎn)是一項(xiàng)風(fēng)險(xiǎn)業(yè)務(wù)，其成功的關(guān)鍵在于正確的風(fēng)險(xiǎn)評估可達(dá)到設(shè)置具有競爭力的保費(fèi)和覆蓋風(fēng)險(xiǎn)之間的平衡。不斷變化的市場導(dǎo)致每年都要根據(jù)往年數(shù)據(jù)中的主要因素進(jìn)行分析和判斷來調(diào)整保費(fèi)。保險(xiǎn)專業(yè)人員通常根據(jù)經(jīng)驗(yàn)對大量統(tǒng)計(jì)報(bào)表作出粗略分析和決策，而數(shù)據(jù)挖掘提供了分析保險(xiǎn)投資組合數(shù)據(jù)庫的環(huán)境。這里采取網(wǎng)格密度聚類算法，在保單及索賠信息數(shù)據(jù)庫中找出保單中風(fēng)險(xiǎn)較大的部分，從而得出一些實(shí)用的風(fēng)險(xiǎn)控制規(guī)則來指導(dǎo)工作。

系統(tǒng)基于B/S分布式層次模型?？蛻舳丝芍苯诱{(diào)取應(yīng)用服務(wù)器上的com組件（包含挖掘數(shù)據(jù)的定義、數(shù)據(jù)預(yù)處理、挖掘內(nèi)核、模式表達(dá)與解釋等模塊）。數(shù)據(jù)源接口采用可以和數(shù)據(jù)挖掘庫、數(shù)據(jù)集市等系統(tǒng)交互的OLEDB FOR ORACLE。某市的醫(yī)保數(shù)據(jù)主要由單位信息表（tdw_information）、人員信息表（try_information）、區(qū)間（一個(gè)月）內(nèi)索賠單據(jù)表(tsp_information)等組成。進(jìn)行數(shù)據(jù)挖掘之前先要根據(jù)主觀經(jīng)驗(yàn)去除冗余信息。在分析保險(xiǎn)業(yè)務(wù)時(shí)，投保人是否索賠是關(guān)鍵信息，應(yīng)把數(shù)據(jù)集中的“是否索賠”（該屬性直接由“索賠次數(shù)”得出，有一定重復(fù)性可以去除）作為標(biāo)簽屬性，其他屬性如個(gè)人保險(xiǎn)號、個(gè)人姓名、單位名稱、投保日期等屬于不相關(guān)信息。經(jīng)過數(shù)據(jù)整理，將得到的描述一定時(shí)間段內(nèi)個(gè)人索賠信息的數(shù)據(jù)表作為訓(xùn)練集。再根據(jù)列重要性選出描述性屬性影響程度最大的列。過程見圖4：

圖3 基本數(shù)據(jù)結(jié)構(gòu)及其聚類的結(jié)果

聚類時(shí)需輸入兩個(gè)參數(shù)ξ和τ，其中ξ將影響網(wǎng)格結(jié)構(gòu)的最底層粒度。若粒度較細(xì)，處理代價(jià)將顯著增加；反之會降低聚類分析質(zhì)量。這里指定ξ＝10，τ＝0.2，把每一維分為10個(gè)區(qū)間，如[25，30)作為年齡維第一個(gè)區(qū)間。計(jì)算數(shù)據(jù)庫中混合型變量對象之間的相異度有兩種方法：一是將變量按類型分組，對每種類型的變量單獨(dú)聚類分析，若得到兼容的結(jié)果則方法可行，實(shí)際上這種可能性很??；二是將所有變量一并做一次聚類分析。通常是將不同變量組合在單個(gè)相異度矩陣中，把所有有意義的變量轉(zhuǎn)換到共同的值域[0.0，1.0]上。

進(jìn)行結(jié)果聚類描述時(shí)要注意，對于數(shù)據(jù)表格對象，可能多個(gè)子空間都含有聚類且維數(shù)一樣。同樣，一個(gè)子空間中可能存在多個(gè)聚類，一個(gè)聚類的描述可能需要多個(gè)最大區(qū)域，而一個(gè)區(qū)域的描述需要給出它的每一維的上下界。這些元素之間存在如圖5所示的一對多關(guān)系。

圖4 簇的子空間、簇、區(qū)域、維的關(guān)系圖

對表tcls_information聚類得出的幾個(gè)簇可用DNF表示為：（55≤ x1＜75）∧ (9000≤ x2＜21000)∧ (1≤ x3＜6)∨（25≤ x1＜50）∧ (6000 ≤ x2＜12000) ∧ (0≤ x3＜1)。從中看出這樣的規(guī)則：年齡和收入將較大地影響到索賠情況，即年齡或收入與索賠的概率成正比。這體現(xiàn)了我國醫(yī)保實(shí)施的實(shí)情，因此可考慮適當(dāng)提高或降低相應(yīng)投保群體的保單費(fèi)用。由于該市醫(yī)療費(fèi)用的支付方法與單位的企事業(yè)性質(zhì)有關(guān)，故投保人還應(yīng)根據(jù)自己的實(shí)際情況來支付費(fèi)用。

4 結(jié)束語

實(shí)踐證明，文中所討論的聚類算法能自動發(fā)現(xiàn)有價(jià)值的最高維子空間而無需用戶指定，能過濾“孤立點(diǎn)”；對元組輸入順序不敏感，無需假設(shè)任何規(guī)范的數(shù)據(jù)分布；可隨數(shù)據(jù)規(guī)模大小而靈活地線性伸縮；能有效處理高維數(shù)據(jù)等。然而，仍有一些需作出持續(xù)改進(jìn)的方面：

1.遞歸運(yùn)行的算法將數(shù)據(jù)空間劃分為更多的網(wǎng)格，使得落入單個(gè)網(wǎng)格中的點(diǎn)數(shù)減少。若保持τ值不變，就基本定出了最后能找到的子空間的維數(shù)，這與自動發(fā)現(xiàn)包含有趣模式的子空間的要求有一定矛盾。因此可嘗試讓τ變化或者用排序、剪切的辦法來解決問題。

2.數(shù)據(jù)表格中的每一列的含義和數(shù)據(jù)類型可能不同，本算法目前未能很好地涉及區(qū)間標(biāo)度變量、對稱和不對稱二元變量、標(biāo)稱變量等混合類型的數(shù)據(jù)。

3.為了使聚類的結(jié)果更加可釋和可用，最好在算法各階段更形象和可視化地表示數(shù)據(jù)。

［1]韓家煒，Kamber Micheline.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2001.

［2]高永梅，黃亞樓.一種基于網(wǎng)格和密度的數(shù)據(jù)流聚類算法[J].計(jì)算機(jī)科學(xué)，2008，35（2）：134-137.

［3]馬帥，王騰蛟，唐世渭，等.一種基于參考點(diǎn)和密度的快速聚類算法[J].軟件學(xué)報(bào)，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.