鏈?zhǔn)侥は到y(tǒng)及直接(間接)膜算法與聚類分析研究進(jìn)展

劉希玉， 姜珍妮， 趙玉禎

(山東師范大學(xué) 管理科學(xué)與工程學(xué)院，山東 濟(jì)南 250014)

膜計(jì)算一詞是由歐洲科學(xué)院院士、羅馬尼亞科學(xué)院院士Gheorghe Pǎun[1]在1998年提出，并于2002年將其成果見刊發(fā)表.2003年，美國(guó)科學(xué)情報(bào)檢索機(jī)構(gòu)(institute for scientific information,簡(jiǎn)稱ISI)將膜計(jì)算列為計(jì)算機(jī)科學(xué)中快速發(fā)展的前沿領(lǐng)域.此時(shí)起，膜計(jì)算便成為了一個(gè)新興的研究領(lǐng)域.膜系統(tǒng)主要由膜結(jié)構(gòu)、對(duì)象以及進(jìn)化規(guī)則3部分組成，通過模擬細(xì)胞、組織或者器官的基本結(jié)構(gòu)而構(gòu)造的膜結(jié)構(gòu)是計(jì)算的主體，規(guī)則是實(shí)現(xiàn)膜內(nèi)和膜間物質(zhì)交流的基礎(chǔ)，對(duì)象則被置于膜內(nèi)，依據(jù)相應(yīng)的規(guī)則，可完成相應(yīng)的信息傳遞過程.

目前為止，膜計(jì)算模型主要分為3種：細(xì)胞型計(jì)算模型、組織型計(jì)算模型和神經(jīng)型計(jì)算模型.細(xì)胞型計(jì)算模型是基于單細(xì)胞結(jié)構(gòu)，組織型計(jì)算模型基于組織中細(xì)胞群結(jié)構(gòu)，神經(jīng)型計(jì)算模型基于神經(jīng)元細(xì)胞.現(xiàn)已被證明，3種模型皆具有圖靈等價(jià)的計(jì)算能力.無(wú)論哪種膜系統(tǒng)，其基本計(jì)算都是開始于膜系統(tǒng)的某個(gè)初始格局，計(jì)算隨著初始格局的轉(zhuǎn)移而不斷進(jìn)行下去，直至在輸出膜中出現(xiàn)計(jì)算結(jié)果為止.目前基于膜系統(tǒng)提出的近似優(yōu)化算法是膜計(jì)算應(yīng)用方面一個(gè)較熱的研究方法，將膜計(jì)算與其他傳統(tǒng)的優(yōu)化算法進(jìn)行結(jié)合，可發(fā)揮膜系統(tǒng)的優(yōu)良特性，并借此改善傳統(tǒng)算法的不足.

針對(duì)膜計(jì)算的研究已經(jīng)層出不窮，但是大部分改進(jìn)膜系統(tǒng)依然基于圖結(jié)構(gòu)的設(shè)計(jì)，為了充分發(fā)揮出膜系統(tǒng)的計(jì)算性能，兩種新型的膜系統(tǒng)應(yīng)運(yùn)而生：(1)在單純形結(jié)構(gòu)和離散Morse理論基礎(chǔ)上構(gòu)造的單純形P系統(tǒng);(2)基于細(xì)胞多維框架思想的鏈?zhǔn)絇系統(tǒng).論文將對(duì)兩種新型的膜系統(tǒng)進(jìn)行詳細(xì)介紹，同時(shí)對(duì)基于現(xiàn)有膜系統(tǒng)進(jìn)行的聚類研究進(jìn)行綜述，并對(duì)未來(lái)相關(guān)研究的發(fā)展提出幾點(diǎn)展望.

1 新型P系統(tǒng)

1.1 單純形P系統(tǒng)

Liu等[2]基于單純形的思想結(jié)合離散Morse結(jié)構(gòu)提出一種新型的單純形P系統(tǒng)，并構(gòu)建了P系統(tǒng)上的交流規(guī)則.在該系統(tǒng)中，作者使用了基于網(wǎng)格的聚類方法實(shí)現(xiàn)了Wisconsin breast cancer數(shù)據(jù)集的聚類過程.實(shí)驗(yàn)結(jié)果表明，新構(gòu)建的單純復(fù)形P系統(tǒng)(simplicial complexes with membrane coefficients,簡(jiǎn)稱SSP系統(tǒng))的性能要優(yōu)于傳統(tǒng)的P系統(tǒng).Xue等[3]提出一種帶有膜系數(shù)的SSP系統(tǒng)，在復(fù)形上擴(kuò)展了現(xiàn)有的膜結(jié)構(gòu)，并給出了4種基于鏈?zhǔn)浇Y(jié)構(gòu)和邊操作的交流規(guī)則.通過模擬寄存器證明了新提出SSP系統(tǒng)的計(jì)算完備性，同時(shí)將其應(yīng)用于文檔聚類中.通過實(shí)驗(yàn)結(jié)果進(jìn)一步證明了新提出的SSP系統(tǒng)較于傳統(tǒng)P系統(tǒng)更具聚類優(yōu)勢(shì).

新型的單純形膜系統(tǒng)的膜結(jié)構(gòu)如圖1所示.通過一系列的頂點(diǎn){a0,a1,…,ak}表示單純復(fù)形K，一個(gè)單形σ∈K被稱為一個(gè)膜，其中單形由頂點(diǎn)表示.如果一個(gè)單形不是單純復(fù)形K中其他膜的組成部分，則記該膜為最大膜.頂點(diǎn)是0維膜，稱為基本膜.若膜τ<σ是σ的一部分，則記σ是τ的父膜.若兩個(gè)單形σ1，σ2是同一個(gè)更高維單形的組成部分，則稱σ1和σ2是鄰居關(guān)系，記作(σ1,σ2)τ，其中τ表示二者的共同超面，也可以記作(σ1,σ2)L.如果單形τ是兩個(gè)單形σ1，σ2的一部分，則σ1，σ2是內(nèi)鄰關(guān)系，記作(σ1,σ2)τ，也可以記作(σ1,σ2)U或者(σ1,σ2).圖1為一個(gè)簡(jiǎn)單的3維單純形膜系統(tǒng)實(shí)例，圖2為單純形膜結(jié)構(gòu)圖1的鄰居關(guān)系.

圖1 單純形膜結(jié)構(gòu)

圖2 膜結(jié)構(gòu)的網(wǎng)絡(luò)模型

該膜系統(tǒng)共包含15個(gè)膜.單純形膜系統(tǒng)的膜數(shù)量計(jì)算方式為

(1)

單純復(fù)形K上表示的系統(tǒng)稱為單純形P系統(tǒng).帶有共運(yùn)輸和逆運(yùn)輸規(guī)則的單純形膜系統(tǒng)定義為

∏=(m,O,E,ω1,…,ωm,R1,…,Rm,ch,F(i,j)|(i,j)∈ch,i0)，

其中：o是字母表；m表示細(xì)胞的數(shù)量標(biāo)簽，標(biāo)號(hào)依次為1,2,…,m；E是環(huán)境中的無(wú)限制多重集；ωi表示膜i中的初始字符串；Ri表示膜i中的共運(yùn)輸/逆運(yùn)輸規(guī)則；ch?{(i,j)U,(i,j)L:i,j∈{1,2,…,m}}表示關(guān)聯(lián)集；F(i,j)表示關(guān)系(i,j)∈ch上的共運(yùn)輸/逆運(yùn)輸規(guī)則；i0表示輸出膜.

單純形P系統(tǒng)中的膜規(guī)則，首先明確每個(gè)類型的規(guī)則都存在out,in,up,down這4種操作.

(1)Rσ(τ1,τ2)中向上關(guān)聯(lián)規(guī)則形式為

[(x,y),up;(α,β),in]U→[z,in;γ,down],[u,out;v,in|τ1<σ],[u,out;v,in|τ2<σ]，

該規(guī)則表示將細(xì)胞τ1中的x以及細(xì)胞τ2中的y變成z移動(dòng)到父代σ中，同時(shí)將父代σ中的γ分別變成τ1中的α以及細(xì)胞τ2中的β.

(2)Rσ(τ1,τ2)中向下關(guān)聯(lián)規(guī)則形式為

[(x,y),down;(α,β),in]L→[z,in;γ,up],[u,out;v,in|σ<τ1],[u,out;v,in|σ<τ2]，

該規(guī)則表示將細(xì)胞τ1中的x以及細(xì)胞τ2中的y變成z移動(dòng)到超面σ中，同時(shí)將父代σ中的γ分別變成上一層細(xì)胞τ1中的α以及上一層細(xì)胞τ2中的β.

1.2 鏈?zhǔn)侥は到y(tǒng)

與單純形P系統(tǒng)的提出一樣，同樣基于離散Morse結(jié)構(gòu)，欒靜等[4]提出一種與離散Morse結(jié)構(gòu)相結(jié)合的具有鏈?zhǔn)浇Y(jié)構(gòu)的新型脈沖神經(jīng)P系統(tǒng)(spiking neural P system on chain,簡(jiǎn)稱SNPC系統(tǒng)).SNPC系統(tǒng)的神經(jīng)膜細(xì)胞通過離散梯度矢量路徑設(shè)置鏈，構(gòu)建鏈?zhǔn)浇Y(jié)構(gòu)的SNP(spiking neural P system)系統(tǒng).作者證明了新提出的SNPC系統(tǒng)在進(jìn)行自然數(shù)運(yùn)算方面的可行性，并從生成數(shù)據(jù)集和生成字符串語(yǔ)言的角度給出了SNPC系統(tǒng)中算術(shù)運(yùn)算的算法.Xue等[5]提出了一種結(jié)合離散Morse理論的新型定向鏈?zhǔn)絇系統(tǒng)，P系統(tǒng)中的對(duì)象以正負(fù)兩級(jí)的形式存在，并證明了該鏈?zhǔn)絇系統(tǒng)具有和圖靈機(jī)等價(jià)的計(jì)算能力，將其用于線性時(shí)間內(nèi)對(duì)滿足性問題的求解，經(jīng)與其他的P系統(tǒng)對(duì)比證明了該鏈?zhǔn)絇系統(tǒng)的有效性.

將鏈?zhǔn)浇Y(jié)構(gòu)與膜系統(tǒng)進(jìn)行結(jié)合，同樣是基于膜對(duì)象、膜結(jié)構(gòu)和膜規(guī)則3個(gè)角度進(jìn)行.鏈?zhǔn)侥そY(jié)構(gòu)設(shè)定如下：(1) 若一個(gè)膜內(nèi)部不再包含其他膜，則該膜為基本膜；(2) 將多個(gè)膜相互連接組成一個(gè)有序鏈表，稱為鏈膜；(3) 鏈膜上的每一個(gè)膜為單元膜；(4) 各個(gè)基本膜中的符號(hào)稱為基本對(duì)象，鏈膜中每個(gè)單元膜中的基本對(duì)象依次連接構(gòu)成的有序?qū)ο蠓Q為鏈對(duì)象.鏈?zhǔn)侥は到y(tǒng)可以分為有向鏈?zhǔn)侥は到y(tǒng)和無(wú)向鏈?zhǔn)侥は到y(tǒng)，無(wú)向鏈?zhǔn)侥は到y(tǒng)是以單純形多維結(jié)構(gòu)構(gòu)建的膜系統(tǒng)，各個(gè)單元膜之間沒有順序關(guān)系.此處僅對(duì)有向鏈?zhǔn)侥は到y(tǒng)進(jìn)行說明.

有向鏈?zhǔn)侥は到y(tǒng)的形式化定義如下

∏=(O,μ,w1,w2,…,wm,R1,R2,…,Rm,io)，

其中：O是字母表；μ是膜結(jié)構(gòu)，包括鏈膜的組成結(jié)構(gòu)以及整個(gè)膜系統(tǒng)的組成結(jié)構(gòu)；wi(i=1,2,…,m)為鏈膜σi中鏈對(duì)象的集合；Ri(i=1,2,…,m)為膜σi內(nèi)的規(guī)則；io是輸出膜.

有向鏈?zhǔn)侥は到y(tǒng)中的膜以鏈膜形式存在，表示為σi=hi1*σi1?hi2*σi2?…?hini*σini，其中：σi1,σi2,…,σini表示該鏈膜上的單元膜；hi1,hi2,…,hini表示整數(shù)；hijσij表示該鏈膜中包含|hij|個(gè)單元膜σij.通過規(guī)則控制信息在各單元膜以及各個(gè)鏈膜之間進(jìn)行交流.有向鏈?zhǔn)侥は到y(tǒng)中，對(duì)象以鏈表形式表示，具體表示為ai=x1?x2?…?xn，代表的含義為單元膜σi中包含單元對(duì)象xi.有向鏈?zhǔn)侥ひ?guī)則表示為ri={ri,1,ri,2,…,ri,n}，表示ri是由n個(gè)子規(guī)則組成，這n個(gè)子規(guī)則按照從左至右的順序依次執(zhí)行.設(shè)ai1=gnxn?gn-1xn-1?…?g1x1和ai2=hnxn?hn-1xn-1?…?h1x1是某有向鏈?zhǔn)侥は到y(tǒng)中的任意兩個(gè)鏈膜，則鏈膜相加規(guī)則為

ai3=ai1+ai2為ai1+ai2=(gn+hn)xn?(gn-1+hn-1)xn-1?…?(g1+h1)x1，

它也是一個(gè)鏈膜.同樣鏈?zhǔn)侥は到y(tǒng)中也可以進(jìn)行相減、交叉等其他操作.兩種鏈?zhǔn)侥そY(jié)構(gòu)形式如圖3、4所示.

圖3 樹形膜結(jié)構(gòu)

圖4 圖形膜結(jié)構(gòu)

2 膜計(jì)算在聚類問題中的應(yīng)用

根據(jù)膜計(jì)算與聚類算法的結(jié)合程度可將其分為兩個(gè)大類：(1)利用直接膜算法求解聚類問題；(2)利用間接膜算法求解聚類問題.直接膜算法是指用P系統(tǒng)的對(duì)象表示算法中的數(shù)據(jù)對(duì)象，用P系統(tǒng)的進(jìn)化規(guī)則表示對(duì)數(shù)據(jù)對(duì)象操作過程的算法.間接膜算法是將傳統(tǒng)的近似算法和膜計(jì)算的特性相結(jié)合，是一類新的分布式演化算法.此處需要說明關(guān)于直接膜算法和間接膜算法兩個(gè)名詞的定義依據(jù)的是當(dāng)前研究現(xiàn)狀，并非是一種嚴(yán)格的說法.

聚類分析是數(shù)據(jù)挖掘中一個(gè)非?；钴S的研究領(lǐng)域，現(xiàn)已有很多聚類算法.按照聚類思想的不同，可將聚類簡(jiǎn)單劃分為兩大類：劃分方法和自生長(zhǎng)方法.劃分方法，即事先確定好類數(shù)目，然后按照指定的劃分標(biāo)準(zhǔn)將數(shù)據(jù)集直接生成最終的聚類結(jié)果；自生長(zhǎng)方法則是從一個(gè)數(shù)據(jù)點(diǎn)出發(fā)，按照某種規(guī)則，逐步形成一個(gè)簇.基于層次的聚類方法和基于密度的聚類算法都屬于自生長(zhǎng)算法，比較典型的代表包括：BIRCH(balanced iterative reducing and clustering using hierarchies)、CURE(clustering using representatives)、ROCK(robust clustering using links)、Chameleon算法、DBSCAN(density-based spatial clustering of applications with noise)、OPTICS(ordering points to identify the clustering structure)和DENCLUE(density-based clustering)算法等.除了以上幾類聚類問題，基于網(wǎng)格的聚類以及基于圖論的聚類問題等，也是當(dāng)前的研究熱點(diǎn).

當(dāng)前已經(jīng)存在很多關(guān)于膜計(jì)算的研究，但是將膜計(jì)算應(yīng)用在聚類分析領(lǐng)域的研究還比較少.將膜計(jì)算的極大并行性融入聚類問題分析中，可以有效提高聚類分析的效率，求解大數(shù)據(jù)下高復(fù)雜度、高稀疏性問題，具有一定的應(yīng)用價(jià)值和實(shí)踐意義.

2.1 基于直接膜算法求解聚類問題

劃分方法(partitioning method，簡(jiǎn)稱PAM)的基本思想是首先創(chuàng)建k個(gè)劃分(即聚類數(shù)為k)，然后通過一定的預(yù)設(shè)指標(biāo)將每個(gè)數(shù)據(jù)點(diǎn)從一個(gè)劃分轉(zhuǎn)移到另一個(gè)劃分，從而改善劃分的質(zhì)量.比較典型的劃分方法包括：K-means、K-medoids、CLARA(clustering large applications)等方法.目前學(xué)者們習(xí)慣性地統(tǒng)稱該類劃分方法為廣義K-means聚類.盡管該聚類方法操作簡(jiǎn)單、高效，但是依然存在很多缺陷，如該方法需要預(yù)先指定聚類數(shù)目，同時(shí)算法采用隨機(jī)選取初始聚類中心的方法容易使算法陷入局部最優(yōu)，且由于算法基本思想的限制使得該算法僅適用于球形數(shù)據(jù)集的聚類.

2012年，有學(xué)者開始嘗試將膜計(jì)算引入聚類問題中[6]，借助P系統(tǒng)的極大并行性和較低的計(jì)算復(fù)雜度特性，有效地提高了聚類的效率.簡(jiǎn)單的實(shí)驗(yàn)運(yùn)行證明了該思想的可行性，同時(shí)也成了膜計(jì)算應(yīng)用層面新的嘗試.盡管P系統(tǒng)的引入提高了聚類效率，但是依然無(wú)法掩蓋聚類算法自身存在的不足，所以在融合P系統(tǒng)進(jìn)行聚類的同時(shí)，引入K近鄰思想以及基于數(shù)據(jù)點(diǎn)密度等優(yōu)化方法優(yōu)化K-medoids算法初始聚類中心[7-11]，可進(jìn)一步提高算法的有效性.

與改進(jìn)聚類算法本身的思想一致，改進(jìn)P系統(tǒng)的結(jié)構(gòu)也是提高算法計(jì)算能力的一種方式.Xu等[12]基于劃分聚類中的中心點(diǎn)思想提出一種用于聚類問題的剪接P系統(tǒng)，并使用了10個(gè)數(shù)據(jù)點(diǎn)測(cè)試了該P(yáng)系統(tǒng)的可行性.

集成聚類是一類魯棒性非常好的聚類方法，它可以根據(jù)多個(gè)已知的基本聚類劃分得出最終的聚類結(jié)果.Zhao等[13]在集成聚類中引入了K-medoids算法和帶有促進(jìn)劑和抑制劑的類細(xì)胞P系統(tǒng)，提出了一種基于類細(xì)胞P系統(tǒng)的K-medoids集成聚類算法.并通過實(shí)驗(yàn)證明了所提出的集成聚類算法可以在短時(shí)間內(nèi)獲得更高質(zhì)量的聚類結(jié)果.

基于層次的聚類算法分為自上而下和自下而上兩種方式.Cardona等[14]將P系統(tǒng)應(yīng)用到層次聚類中，以矩陣的形式存儲(chǔ)數(shù)據(jù)點(diǎn)之間的相異度，該思路為后期P系統(tǒng)在聚類中的應(yīng)用提供了思路.Sun等[15]基于該思路對(duì)P系統(tǒng)進(jìn)行簡(jiǎn)單改進(jìn)，使用了簡(jiǎn)單的數(shù)據(jù)集對(duì)論文提出的聚類算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，最終結(jié)果證明了所改進(jìn)算法的有效性.Zhao等[16]同樣也將活性膜P系統(tǒng)應(yīng)用到分層聚類中.

層次聚類的代表算法主要包括BIRCH、CURE、ROCK、Chameleon算法.Bai等[17-18]將擴(kuò)展的脈沖神經(jīng)P系統(tǒng)引入到了層次聚類中.Zhao等[19]構(gòu)建了基于活性膜P系統(tǒng)的改進(jìn)ROCK算法，借助于P系統(tǒng)的極大并行性，極大地降低了改進(jìn)之后聚類算法時(shí)間復(fù)雜度.Zhao等[20]將類組織P系統(tǒng)應(yīng)用到凝聚變色龍聚類算法中，實(shí)驗(yàn)差錯(cuò)率更低，聚類效果更準(zhǔn)確.Zhao等[21]使用基于網(wǎng)格的聚類算法和并行進(jìn)化機(jī)制以及帶有促進(jìn)和抑制因子的分類組織P系統(tǒng)，改進(jìn)了變色龍算法.

密度聚類則是根據(jù)對(duì)象之間的密度進(jìn)行完成聚類，該方式可以發(fā)現(xiàn)任意形狀的聚類，代表性的密度聚類算法有DBSCAN、OPTICS和DENCLUE算法.Sun等[22]將P系統(tǒng)運(yùn)用到DBSCAN聚類中.Xue等[23]提出一種基于加權(quán)脈沖神經(jīng)P系統(tǒng)用于求解密度-網(wǎng)格聚類問題.

網(wǎng)格方法可以有效減少算法的計(jì)算復(fù)雜度，且同樣對(duì)密度參數(shù)敏感.Xue等[24]提出了一種基于網(wǎng)格的帶有交流規(guī)則的新型P系統(tǒng)，稱為格上交流P系統(tǒng)(communication P system on lattice，簡(jiǎn)稱LTC-P).將該系統(tǒng)與基于密度的聚類、基于分層的聚類以及基于劃分的聚類進(jìn)行結(jié)合，用于求解聚類問題.聚類過程在膜中實(shí)現(xiàn)，聚類結(jié)果通過膜輸出.最終將新的P系統(tǒng)在UCI(university of californiaIrvine)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證，結(jié)果表明該系統(tǒng)比傳統(tǒng)算法消耗時(shí)間更短，所用規(guī)則更少，同時(shí)還能提供更簡(jiǎn)單的膜結(jié)構(gòu).Xue[25]提出一種基于菱形網(wǎng)格算法和脈沖神經(jīng)網(wǎng)絡(luò)P系統(tǒng)的新型算法(combining rhombic grids based algorithm and spiking neural P systems used for solving clustering problems，簡(jiǎn)稱RGSNPS)，并將其用于求解聚類問題，最終通過Iris和Wine數(shù)據(jù)集證明了該混合算法的有效性和準(zhǔn)確性.

除了以上聚類方法，基于圖論的聚類算法也是當(dāng)前的研究熱點(diǎn)之一.Zhao等[26]直接將聚類問題轉(zhuǎn)化成圖論問題，提出了一種基于活性膜P系統(tǒng)的聚類算法.計(jì)算時(shí)，首先將聚類中的對(duì)象轉(zhuǎn)化成圖中的頂點(diǎn)，對(duì)象之間的相異度表示圖的邊.Xue等[27]提出一種格上P系統(tǒng)并將其用于求解圖聚類問題.Liu等[28]提出一種新的基于圖的P系統(tǒng)，該P(yáng)系統(tǒng)的主要特點(diǎn)就是在圖的頂點(diǎn)和邊上都存在膜室.兩種間隔之間與某些通訊規(guī)則是拓?fù)潢P(guān)聯(lián)的.為尋找Hopfield神經(jīng)網(wǎng)絡(luò)的均衡，論文還提出一種新的神經(jīng)網(wǎng)絡(luò)計(jì)算技術(shù)來(lái)求解類分裂問題，通過與傳統(tǒng)算法的比較，證明了論文新提出P系統(tǒng)的計(jì)算效率.

除此之外，Xue等[29]提出的一種基于樹結(jié)構(gòu)的P系統(tǒng)實(shí)現(xiàn)空間聚類分析，考慮傳統(tǒng)的空間聚類分析都是基于馮·諾依曼計(jì)算架構(gòu)，將直接膜算法運(yùn)用到聚類問題中，通過給出渠道和規(guī)則具體呈現(xiàn)了新的交流P系統(tǒng).Xiu等[30]提出一種結(jié)合了Bin-packing技術(shù)的新型P系統(tǒng)，并將其應(yīng)用于聚類分析中，聚類過程的變異、交換以及能量變換過程均以規(guī)則的形式在P系統(tǒng)的膜結(jié)構(gòu)中進(jìn)行實(shí)現(xiàn)，最終將該系統(tǒng)應(yīng)用于心臟病數(shù)據(jù)集的聚類中.Xue等[31]提出一種具有上層/下層規(guī)則以及同層溶解結(jié)構(gòu)的新型P系統(tǒng)，使用膜規(guī)則求解聚類問題，并在UCI的急性炎癥信息數(shù)據(jù)集中進(jìn)行了實(shí)驗(yàn)驗(yàn)證，聚類準(zhǔn)確率達(dá)到83%.實(shí)驗(yàn)結(jié)果表示該新型P系統(tǒng)能夠準(zhǔn)確地對(duì)數(shù)據(jù)集進(jìn)行聚類.

2.2 基于間接膜算法求解聚類問題

Peng等[32]提出一種具有全局連通結(jié)構(gòu)的類組織膜聚類算法，使用速度-位置作為進(jìn)化規(guī)則，所提出的算法在進(jìn)化-交流機(jī)制下，該膜系統(tǒng)不僅可以獲得最佳聚類數(shù)目，而且還能非常好地實(shí)現(xiàn)聚類劃分.Peng等[33]基于前期研究提出了基于類組織P系統(tǒng)求解多目標(biāo)模糊聚類問題，文中所使用的多目標(biāo)函數(shù)為

(2)

其中：Z1,…,Zk表示需要優(yōu)化的K個(gè)聚類中心；3個(gè)目標(biāo)函數(shù)分別表示3種有效性測(cè)量指標(biāo).

Hou等[34]借助P系統(tǒng)的極大并行性優(yōu)化量子遺傳算法，使用改進(jìn)之后的算法優(yōu)化K-means聚類算法的初始聚類中心，克服了K-means算法隨機(jī)選取聚類中心的不足.改進(jìn)之后的算法能有效縮短算法的運(yùn)行時(shí)間，并可用于處理大規(guī)模數(shù)據(jù)集以及未知聚類數(shù)據(jù)數(shù)目的數(shù)據(jù)集.Jiang等[35]提出了一種基于DNA遺傳算法和P系統(tǒng)的K-means聚類算法，借助DNA遺傳算法的選擇、交叉、變異操作實(shí)現(xiàn)了初始聚類中心的選擇，克服了傳統(tǒng)的K-means聚類算法隨機(jī)選擇初始聚類中心的不足，同時(shí)借助P系統(tǒng)的極大并行性有效地實(shí)現(xiàn)了聚類.

3 結(jié)束語(yǔ)

綜合目前的研究可以發(fā)現(xiàn)，有關(guān)膜計(jì)算的研究已經(jīng)存在很多，但是將膜計(jì)算應(yīng)用于聚類分析領(lǐng)域的研究還比較少.膜計(jì)算在聚類分析領(lǐng)域是一個(gè)新課題，將膜計(jì)算的極大并行性與聚類模型進(jìn)行結(jié)合，可以用來(lái)處理高復(fù)雜度、高數(shù)據(jù)量的數(shù)據(jù)集，具有一定的實(shí)踐意義和應(yīng)用價(jià)值.

膜計(jì)算融合其他優(yōu)化算法進(jìn)行數(shù)據(jù)處理的間接膜算法是目前較為熱點(diǎn)的研究方向，待求解的問題有：(1)對(duì)P系統(tǒng)的進(jìn)化-交流機(jī)制進(jìn)行改進(jìn)，使其可以實(shí)現(xiàn)自動(dòng)聚類和多目標(biāo)聚類；(2)目前研究中的固定膜結(jié)構(gòu)并不可以實(shí)現(xiàn)自動(dòng)聚類，所以未來(lái)可研究動(dòng)態(tài)膜結(jié)構(gòu)，并將其用于處理優(yōu)化問題；(3)嘗試構(gòu)建新型P系統(tǒng)，使其可以用于處理更大規(guī)模的數(shù)據(jù)集；(4)將膜計(jì)算用于求解更廣范圍的聚類問題；(5)目前學(xué)者們的研究主要是借用UCI數(shù)據(jù)集及人工數(shù)據(jù)集進(jìn)行實(shí)現(xiàn)驗(yàn)證，未來(lái)可注重將P系統(tǒng)用于求解實(shí)際問題.

參考文獻(xiàn)：

[2] LIU X Y, XUE A. Communication P systems on simplicial complexes with applications in cluster analysis[J]. Discrete Dynamics in Nature and Society, 2012, 55 (1): 12-17.

[3] XUE J, LIU X Y. Spiking simplicial P systems with membrane coefficients and applications in document clustering[C]// Lecture Notes in Computer Science, 2016: 158-168.

[4] LUAN J, LIU X Y. A variant of P system with a chain structure[J]. Journal of Information & Computational Science, 2013, 10 (10): 3189-3197.

[5] XUE J, LIU X Y, CHEN P. Communication P System with oriented chain membrane structures and applications in graph clustering[J]. Journal of Computational and Theoretical Nanoscience, 2016, 13 (7): 4198-4210.

[6] ZHAO Y Z, LIU X Y, ZHANG H. The K-medoids clustering algorithm with membrane computing[J]. Indonesian Journal of Electrical Engineering and Computer Science, 2013, 11 (4): 2050-2057.

[7] ZHAO Y Z, LIU X Y, QU J H. The k-medoids clustering algorithm by a class of P system[J]. Journal of International & Computional Science, 2012, 9 (18): 5777-5790.

[8] LI Q, LIU X Y. A K-memoids clustering algorithm with initial centers optimized by a P system[C]// Lecture Notes in Computer Science, 2015: 488-500.

[9] HAN L S, XIANG L S, LIU X Y. The K-medoids algorithm with initial centers optimized based on a P system[J]. Journal of Information & Computational Science, 2014, 11 (6): 1765-1773.

[10] SUN W, XIANG L S, LIU X Y. An improved K-medoids clustering algorithm based on a grid cell graph realized by the P system[C]// Lecture Notes in Computer Science, 2016: 365-374.

[11] SUN W, XIANG L S, LIU X Y. A new P system with hybrid MDE-K-means algorithm for data clustering[J]. Wseas on Computers, 2016, 15: 93-102.

[12] XU J L, LIU X Y, XUE J. Cluster analysis by a class of splicing P systems[C]// Lecture Notes in Electrical Engineering, 2014: 575-581.

[13] ZHAO Y Z, LIU X Y, SUN W X. K-medoids-based consensus clustering based on cell-like P systems with promoters and inhibitors[J]. Communications in Computer and Information Science, 2017, 681: 95-108.

[14] CARDONA M, COLOMER M, ZARAGOZA A. Hierarchical clustering with membrane computing[J]. Computing and Informatics, 2012, 27 (3): 497-513.

[15] SUN J, LIU X Y. Hierarchical clustering with improved P system[C]// Lecture Notes in Computer Science, 2012: 454-460.

[16] ZHAO Y Z, LIU X Y, LI X F. The improved hierarchical clustering algorithm by a P system with active membranes[J]. WSEAS Transactions on Computers, 2013, 12 (2): 8-17.

[17] BAI X, LIU X Y. Hierarchical clustering algorithm by extended SN P systems on friendship building in social networks[J]. Journal of Computational Information Systems, 2013, 9 (12): 4849-4859.

[18] BAI X, LIU X Y. Extended asynchronous SN P systems for solving sentiment clustering of customer reviews in e-commerce websites[J]. WSEAS Transactions on Information Science and Applications, 2013, 10 (6): 195-208.

[19] ZHAO Y Z, LIU X Y, WANG W P. ROCK clustering algorithm based on the P system with active membranes[J]. WSEAS Transactions on Computers, 2014 (13): 289-299.

[20] ZHAO Y Z, LIU X Y, WANG W P. An agglomerate chameleon algorithm based on the tissue-like P system[C]// Communications in Computer and Information Science, 2015, 562: 706-723.

[21] ZHAO Y Z, LIU X Y. A grid-based chameleon algorithm based on the tissue-like P system with promoters and inhibitors[J]. Journal of Computational and Theoretical Nanoscience, 2016, 13 (6): 3652-3658.

[22] SUN J, LIU X Y. The DBSCAN clustering algorithm by a P system with active membranes[J]. WSEAS Transactions on Computers, 2016, 12 (8): 309-319.

[23] MAI S T, HE X, FENG J, et al. Anytime density-based clustering of complex data[J]. Knowledge and Information Systems, 2015, 45 (2): 1-37.

[24] XUE J, LIU X Y. Lattice based communication P systems with applications in cluster analysis[J]. Soft Computing, 2014, 18 (7): 1425-1440.

[25] XUE J, LIU X Y. Rhombic grid based clustering algorithm with spiking neural P systems[J]. Journal of Computational and Theoretical Nanoscience, 2016, 13 (6): 3895-3901.

[26] ZHAO Y Z, LIU X Y, QU J H. Research on the application of the P system with active membranes in clustering[C]// Lecture Notes in Computer Science, 2013: 883-890.

[27] XUE J, LIU X Y. Graph cluster analysis by lattice based P system with conditional rules[C]// Lecture Notes in Computer Science, 2014: 375-377.

[28] XIU X Y, XUE J. A cluster splitting technique by Hopfield networks and P systems on simplices[J]. Neural Processing Letters, 2017: 1-24.

[29] XUE J, LIU X Y. Spatial cluster by communication P system on trees[J]. Journal of Information & Computational Science, 2012, 9 (13): 3883-3893.

[30] LIU X Y, XUE J, XIANG L S. A membrane bin-packing technique for heart disease cluster analysis[C]// Lecture Notes in Electrical Engineering, 2013: 39-49.

[31] XUE J, LIU X Y. Acute inflammations analysis by P system with floor membrane structure[C]// Frontier and Future Development of Information Technology in Medicine and Education, 2014: 281-291.

[32] PENG H, WANG J, PENG S. An automatic clustering algorithm inspired by membrane computing[J]. Pattern Recognition Letters, 2015 (68): 34-40.

[33] PENG H, PENG S, WANG J. Multiobjective fuzzy clustering approach based on tissue-like membrane systems[J]. Knowledge-Based Systems, 2017, 125 (1): 74-82.

[34] HOU C P, LIU X Y. P system based quantum genetic algorithm to solve the problem of clustering[C]// Lecture Notes in Computer Science, 2016: 661-667.

[35] JIANG Z N, ZANG W K, LIU X Y. Research of K-means clustering method based on DNA genetic algorithm and P system[C]// Lecture Notes in Computer Science, 2016: 193-203.