基于網格和密度的保險業務投資風險規則聚類

邱 洋

（上海電子信息職業技術學院計算機應用系 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.