邱 洋

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

1 引言

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

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

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)。通常的計算公式有：歐幾里得距離、曼哈頓距離。它們具有一些共性：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維的數(shù)據(jù)對象，q是一個正整數(shù)。當q＝1時為曼哈頓距離；q＝2時為歐氏距離。并且為不同的變量賦予不同的權(quán)重。在實際計算距離時，只能憑主觀確定各個變量的權(quán)重，不同的權(quán)重對計算結(jié)果影響較大。

2.2 相關(guān)概念

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

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

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

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

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

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

2.3 算法實現(xiàn)

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

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

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

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

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

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

圖2 算法的操作對象樹

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

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

deleteNonDense();doMdlPrunnint();

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

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

……}

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

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

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

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

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(廣度優(yōu)先)算法來存放連通分支中所有點的棧及其點……

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

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

2.3.3 生成一個聚類的描述

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

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

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

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

……

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

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

……

while(k＜lCurrentDim){

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

insert_region(pRegion1); }

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

［2]高永梅，黃亞樓.一種基于網(wǎng)格和密度的數(shù)據(jù)流聚類算法[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.