混合尺度聚類模型收斂性分析及仿真

王文慶， 薛 飛

(1.西安郵電大學(xué) 自動(dòng)化學(xué)院， 陜西 西安 710121； 2.西安郵電大學(xué) 管理工程學(xué)院， 陜西 西安 710121)

混合尺度聚類模型收斂性分析及仿真

王文慶1， 薛 飛2

(1.西安郵電大學(xué) 自動(dòng)化學(xué)院， 陜西 西安 710121； 2.西安郵電大學(xué) 管理工程學(xué)院， 陜西 西安 710121)

針對(duì)被分類對(duì)象屬性多樣性的客觀實(shí)際，分析使用單一間隔尺度或名義尺度進(jìn)行聚類的局限性，并提出一種混合尺度聚類模型。新模型以明氏距離及翻轉(zhuǎn)距離為基礎(chǔ)，引入混合尺度。利用下準(zhǔn)則函數(shù)及逐步聚類算法可證新模型的收斂性。以某小區(qū)保安預(yù)警系統(tǒng)的采樣數(shù)據(jù)為例，運(yùn)用Matlab軟件對(duì)新模型進(jìn)行仿真驗(yàn)證，結(jié)果表明，新模型可應(yīng)用于被分類對(duì)象具有多種特征屬性的聚類問題。

混合尺度聚類；下準(zhǔn)則函數(shù)；聚類收斂性

單一的間隔尺度或名義尺度聚類的研究已經(jīng)非常深入[1-2]。但描述被分類對(duì)象的指標(biāo)卻非常的復(fù)雜、繁多，無論是間隔尺度指標(biāo)還是名義尺度指標(biāo)都無法完整的描述事物的特性。例如某一類物體具有如下指標(biāo)(重量、數(shù)量、高度、形態(tài)、顏色、氣味)，要對(duì)其進(jìn)行聚類，若用間隔尺度聚類，就會(huì)忽略形態(tài)、顏色、氣味，若用名義尺度聚類就會(huì)忽略重量、數(shù)量、高度。這樣，傳統(tǒng)單一的間隔尺度或名義尺度聚類都不能滿足人們對(duì)聚類的需求。因此，混合尺度(兼用間隔尺度和名義尺度)聚類就變得尤為重要。

文獻(xiàn)[1]對(duì)名義尺度聚類問題進(jìn)行了研究；文獻(xiàn)[2]針對(duì)間隔尺度聚類提出了一種并行聚類算法，并使其構(gòu)建在MapReduce并行框架上，以使得算法能夠應(yīng)用于大規(guī)模數(shù)據(jù)分類；文獻(xiàn)[3]提到了混合聚類模型，但只對(duì)其做出了簡單的理論說明，并未進(jìn)行實(shí)際的證明；文獻(xiàn)[4]提出判別模糊C-均值聚類算法以提高大樣本數(shù)據(jù)的聚類速度；文獻(xiàn)[5]主要討論了聚類方法的發(fā)展?fàn)顩r，提出了基于有限維聯(lián)合混合模型的聚類算法BGMMn；文獻(xiàn)[6]給出了一種一般逐步聚類模型，并對(duì)其收斂性進(jìn)行了證明；文獻(xiàn)[7]提出了一種基于BIRCH算法的混合屬性聚類算法；文獻(xiàn)[8]對(duì)聚類分析進(jìn)行了相關(guān)描述。

本文以文獻(xiàn)[3,6]的研究工作為基礎(chǔ)，著重分析混合尺度(間隔尺度和名義尺度相結(jié)合)聚類模型及其收斂性，并通過實(shí)際數(shù)據(jù)對(duì)模型進(jìn)行仿真。文章提出的混合尺度聚類模型，就是要為人們在處理復(fù)雜事物時(shí)提供方便，把相似的事物更加精確的歸為一類，差異較大的事物歸在不同的類當(dāng)中，以提高人們的工作或?qū)W習(xí)效率。

1 混合尺度聚類模型

設(shè)有

Y=P1,

Z=G1×G2×…×GP2,

其中

P1+P2=P

為描述被分類對(duì)象的指標(biāo)數(shù)。P元變量

x=(y,z)T∈X

的前P1個(gè)分量y∈Y是間隔尺度變量，而后P2個(gè)分量z∈Z是名義尺度變量。以X表示所有的樣品。設(shè)已取得N個(gè)樣品

E={x1,x2,…,xN} (xi∈X),

為了消除量綱影響并使兩種變量處于同等地位，假定其中各間隔尺度變量都已極差標(biāo)準(zhǔn)化，即以

(i=1,2,…,P;k=1,2,…,N)

(1)

代替原來的yik,將歸一化后的E記為Λ,其中的樣品記為

λ=(μ,ν)T∈Λ。

定義

(2)

為描述兩個(gè)樣品各指標(biāo)之間的距離，其中λ，x∈Λ為不同的樣品，μ代表間隔尺度指標(biāo)、ν代表名義尺度指標(biāo)。

根據(jù)明氏(Minkowski)距離公式

當(dāng)q=2時(shí)，上式即為歐式距離

(3)

上式即為兼顧間隔尺度與名義尺度的混合尺度“距離”。以下將證明可作為聚類距離尺度。

2 收斂性分析

定義1(距離空間)[9]設(shè)C是某些元素組合的集合，如果對(duì)任何x,y∈C,按照一定的法則確定一個(gè)非負(fù)實(shí)數(shù)d(x,y),且滿足

(ⅰ) 非負(fù)性：d(x,y)≥0, 且d(x,y)=0當(dāng)且僅當(dāng)x和y為C中同一個(gè)樣本元素。

(ⅱ) 對(duì)稱性：d(x,y)=d(y,x)。

(ⅲ) 三角不等式： 任給x,y,z∈C,有

d(x,y)≤d(x,z)+d(z,y)。

則d(x,y):C×C→2叫做C上的距離，C稱為距離空間。

定義2(翻轉(zhuǎn)距離) 名義尺度樣本xi和xj之間的翻轉(zhuǎn)距離|xi-xj|定義為xi=xj前的翻轉(zhuǎn)次數(shù)。xi和xj的屬性xik和xjk∈(k=1,2,…,n)。

事實(shí)上，根據(jù)Minkowski不等式

其中k≥1,ai,bi是實(shí)數(shù)或復(fù)數(shù)，可得

d(x,z)+d(z,y)。

3 算法仿真

某小區(qū)的保安預(yù)警系統(tǒng)，需要將門禁監(jiān)控抓拍到的出入小區(qū)人員體貌特征，與近期公安系統(tǒng)發(fā)布的犯罪嫌疑人的體貌特征進(jìn)行比對(duì)分析，以協(xié)助案件偵破并保證小區(qū)安全。這種人員體貌特征分析是一個(gè)典型的混合尺度聚類問題。為此，選取9個(gè)體貌特征數(shù)據(jù){體重(kg)，年齡(歲)，身高(cm),性別，胖瘦，膚色，衣著，發(fā)型，臉型}進(jìn)行聚類分析。其中，前三個(gè)特征屬于間隔尺度，后六個(gè)特征屬于名義尺度。對(duì)名義尺度做如下量化處理，如表1所示。

表1 名義尺度的量化

經(jīng)一段時(shí)間采樣獲得數(shù)據(jù)如表2。

表2 采樣所得原始數(shù)據(jù)

表2中的9號(hào)數(shù)據(jù)為公安系統(tǒng)發(fā)布的犯罪嫌疑人體貌特征，其余數(shù)據(jù)為采樣獲得的有待分析的數(shù)據(jù)。

應(yīng)用聚類模型，具體步驟如下。

第1步 將間隔尺度轉(zhuǎn)換為名義尺度，即體重：65～70kg用1替換，71～75kg用2替換，76～80kg用3替換；年齡：20～30 歲用1替換，31～40 歲用2替換，41～50 歲用3替換；身高：170～175cm用1替換，176～180cm用2替換，181～185cm用3替換。得出表3。

表3 間隔尺度轉(zhuǎn)換為名義尺度后的數(shù)據(jù)

第2步 所有數(shù)據(jù)已轉(zhuǎn)成名義尺度，用名義尺度的測量方法“翻轉(zhuǎn)距離”對(duì)數(shù)據(jù)進(jìn)行聚類。用Matlab軟件對(duì)該例進(jìn)行分析聚類[10](Matlab程序見附錄)，并輸出聚類譜系圖(圖1)。

圖1 Matlab聚類譜系圖

用以聚類的Matlab程序流程如下。

(1) 判斷每兩行元素是否相同。

(2) 統(tǒng)計(jì)出不同元素的個(gè)數(shù)(數(shù)字越大距離越遠(yuǎn))。

(3) 根據(jù)每兩行之間的距離調(diào)用Matlab函數(shù)(dendrogram)畫譜系圖。

從聚類譜系圖能夠直觀的得出8號(hào)數(shù)據(jù)與9號(hào)數(shù)據(jù)吻合度最高，可以確定8號(hào)數(shù)據(jù)對(duì)應(yīng)的人員和公安系統(tǒng)所尋找的犯罪嫌疑人最為相似，所以8號(hào)應(yīng)作為重點(diǎn)監(jiān)控對(duì)象。

這里有幾點(diǎn)需要特別說明。

(1) 將進(jìn)、出小區(qū)人員體貌特征與犯罪嫌疑人體貌特征進(jìn)行聚類分析，顯然，這種聚類是一種混合尺度聚類問題，適合所提模型，所以能夠驗(yàn)證該模型。

(2) 兩種尺度的轉(zhuǎn)換。把間隔尺度轉(zhuǎn)換為名義尺度：給間隔尺度的某一取值范圍附一變量作為名義尺度變量，名義尺度變量所代表的間隔尺度變量的取值范圍可實(shí)時(shí)調(diào)節(jié)，以適應(yīng)聚類的要求。(此類聚類中亦可將名義尺度變量轉(zhuǎn)換為間隔尺度變量)。

(3) 不同需求的分類對(duì)各指標(biāo)的側(cè)重點(diǎn)要求不同，必要的情況下每個(gè)指標(biāo)前還可以根據(jù)不同的需求附加不同的權(quán)值，以提高分類的實(shí)用性。

4 結(jié) 語

以前人的工作結(jié)果為前提，指出了傳統(tǒng)的間隔尺度和名義尺度聚類已經(jīng)不能滿足日益發(fā)展的聚類需求，討論了基于混合尺度(間隔尺度和名義尺度相結(jié)合)的聚類模型，證明了該模型的收斂性，用Matlab軟件對(duì)論證了該模型實(shí)用性的實(shí)例進(jìn)行了仿真。未來混合尺度聚類將會(huì)得到更廣泛的應(yīng)用，有關(guān)在間隔尺度和名義尺度之間轉(zhuǎn)換的問題是本文今后繼續(xù)研究的方向之一，以提高混合尺度聚類的有效性和實(shí)用性。

附錄： 混合尺度聚類Matlab程序

A=[ 1 2 1 1 1 2 3 3 2

3 3 2 1 3 3 3 1 2

1 2 3 1 1 2 1 2 2

1 3 2 1 2 2 1 1 1

3 2 3 1 1 3 2 1 3

2 1 2 1 2 1 3 2 3

1 2 1 2 1 2 2 1 1

3 3 2 1 3 3 1 3 2

3 3 2 1 3 3 1 2 2]

t12=0;t13=0;t14=0;t15=0;t16=0;t17=0;t18=0;t19=0;

t23=0;t24=0;t25=0;t26=0;t27=0;t28=0;t29=0;

t34=0;t35=0;t36=0;t37=0;t38=0;t39=0;

t45=0;t46=0;t47=0;t48=0;t49=0;

t56=0;t57=0;t58=0;t59=0;

t67=0;t68=0;t69=0;

t78=0;t79=0;

t89=0;

for i=1

for j=1:9

n=i+1;

if A(i,j)～=A(n,j)

t12=t12+1;

end

end

for j=1:9

n=i+2;

if A(i,j)～=A(n,j)

t13=t13+1;

end

end

for j=1:9

n=i+3;

if A(i,j)～=A(n,j)

t14=t14+1;

end

end

for j=1:9

n=i+4;

if A(i,j)～=A(n,j)

t15=t15+1;

end

end

for j=1:9

n=i+5;

if A(i,j)～=A(n,j)

t16=t16+1;

end

end

for j=1:9

n=i+6;

if A(i,j)～=A(n,j)

t17=t17+1;

end

end

for j=1:9

n=i+7;

if A(i,j)～=A(n,j)

t18=t18+1;

end

end

for j=1:9

n=i+8;

if A(i,j)～=A(n,j)

t19=t19+1;

end

end

end

for i=2

for j=1:9

n=i+1;

if A(i,j)～=A(n,j)

t23=t23+1;

end

end

for j=1:9

n=i+2;

if A(i,j)～=A(n,j)

t24=t24+1;

end

end

for j=1:9

n=i+3;

if A(i,j)～=A(n,j)

t25=t25+1;

end

end

for j=1:9

n=i+4;

if A(i,j)～=A(n,j)

t26=t26+1;

end

end

for j=1:9

n=i+5;

if A(i,j)～=A(n,j)

t27=t27+1;

end

end

for j=1:9

n=i+6;

if A(i,j)～=A(n,j)

t28=t28+1;

end

end

for j=1:9

n=i+7;

if A(i,j)～=A(n,j)

t29=t29+1;

end

end

end

for i=3

for j=1:9

n=i+1;

if A(i,j)～=A(n,j)

t34=t34+1;

end

end

for j=1:9

n=i+2;

if A(i,j)～=A(n,j)

t35=t35+1;

end

end

for j=1:9

n=i+3;

if A(i,j)～=A(n,j)

t36=t36+1;

end

end

for j=1:9

n=i+4;

if A(i,j)～=A(n,j)

t37=t37+1;

end

end

for j=1:9

n=i+5;

if A(i,j)～=A(n,j)

t38=t38+1;

end

end

for j=1:9

n=i+6;

if A(i,j)～=A(n,j)

t39=t39+1;

end

end

end

for i=4

for j=1:9

n=i+1;

if A(i,j)～=A(n,j)

t45=t45+1;

end

end

for j=1:9

n=i+2;

if A(i,j)～=A(n,j)

t46=t46+1;

end

end

for j=1:9

n=i+3;

if A(i,j)～=A(n,j)

t47=t47+1;

end

end

for j=1:9

n=i+4;

if A(i,j)～=A(n,j)

t48=t48+1;

end

end

for j=1:9

n=i+5;

if A(i,j)～=A(n,j)

t49=t49+1;

end

end

end

for i=5

for j=1:9

n=i+1;

if A(i,j)～=A(n,j)

t56=t56+1;

end

end

for j=1:9

n=i+2;

if A(i,j)～=A(n,j)

t57=t57+1;

end

end

for j=1:9

n=i+3;

if A(i,j)～=A(n,j)

t58=t58+1;

end

end

for j=1:9

n=i+4;

if A(i,j)～=A(n,j)

t59=t59+1;

end

end

end

for i=6

for j=1:9

n=i+1;

if A(i,j)～=A(n,j)

t67=t68+1;

end

end

for j=1:9

n=i+2;

if A(i,j)～=A(n,j)

t68=t68+1;

end

end

for j=1:9

n=i+3;

if A(i,j)～=A(n,j)

t69=t69+1;

end

end

end

for i=7

for j=1:9

n=i+1;

if A(i,j)～=A(n,j)

t78=t78+1;

end

end

for j=1:9

n=i+2;

if A(i,j)～=A(n,j)

t79=t79+1;

end

end

end

for i=8

for j=1:9

n=i+1;

if A(i,j)～=A(n,j)

t89=t89+1;

end

end

end

w=[t12 t13 t14 t15 t16 t17 t18 t19 t23 t24 t25 t26 t27 t28 t29 t34 t35 t36 t37 t38 t39 t45 t46 t47 t48 t49 t56 t57 t58 t59 t67 t68 t69 t78 t79 t89] %翻轉(zhuǎn)距離

B=squareform(w) %構(gòu)成矩陣

Z = linkage(w); % 最短距離法

T = cluster(Z,5); %等價(jià)于 { T=clusterdata(X,3) }

find(T==3); % 第3類集合中的元素

[H,T]=dendrogram(Z); % 畫聚類圖

[1] 許洪波，卜東波，白碩.一種針對(duì)名義尺度變量的優(yōu)化聚類算法[J].微電子學(xué)與計(jì)算機(jī),2003(12):11-15.

[2] 卜東波.聚類分類理論研究及其在文本挖掘中的應(yīng)用[D].北京：中國科學(xué)院計(jì)算機(jī)研究所，2000：22-35.

[3] 趙平.建設(shè)工程項(xiàng)目總承包風(fēng)險(xiǎn)管理研究[D].西安：西北工業(yè)大學(xué),2010:31-40.

[4] 支曉斌，田溪.判別C-均值模糊聚類法[J].西安郵電大學(xué)學(xué)報(bào),2013,18(5):26-30.

[5] 劉洋.基于混合模型聚類的方法[D].長春：東北師范大學(xué),2010:30-37.

[6] 周光亞.逐步聚類的一般模型及其收斂性[J].吉林大學(xué)學(xué)報(bào)，1978(1)：47-56.

[7] 李賢.混合屬性聚類算法研究[D].長沙：長沙理工大學(xué),2010:28-35.

[8] 何曉群.多元統(tǒng)計(jì)分析[M].3版.北京:中國人民大學(xué)出版社,2012:57-83.

[9] 李廣民.應(yīng)用泛函分析原理[M].西安：西安電子科技大學(xué)出版社,2003:35-42.

[10] 張繼生,白秋穎.C語言程序設(shè)計(jì)[M].2版.北京：清華大學(xué)出版社,2011:127-186.

[責(zé)任編輯:王輝]

Convergence analysis and simulation of mixed-scale clustering model

WANG Wenqing1, XUE Fei2

(1. School of Automation, Xi’an University of Posts and Telecommunications, Xi’an 710121, China； 2. School of Management Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to classify the objectives with complex attributes, a novel mixed-scale clustering model is proposed after analyzing the limitation of both interval scales and nominal scale for clustering. This model is based on Minkowski’s distance and flip distance, and its convergence is proved with under criterion function and stepwise-clustering algorithm. Sample data collected form a security early-warning system of neighborhoods is used to verify the model with Matlab software. The results show that the model is valid to classify the objectives with complex attributes.

mixed-scale clustering, under criterion function, cluster convergence

10.13682/j.issn.2095-6533.2014.03.012

2014-03-08

國家自然科學(xué)基金資助項(xiàng)目(61305098)

王文慶(1964-)，男，教授，從事智能信息處理研究。E-mail: wwq@xupt.edu.cn 薛飛(1986-)，男，碩士研究生，研究方向?yàn)樾畔⒐芾?。E-mail: xuefeifei.good@163.com

TP301.6

A

2095-6533(2014)03-0058-06