基于代數(shù)粒的聚類方法*

肖振國(guó),陳林書,孫少杰,梅本霞,柳媛慧,趙 磊

(1.湖南科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,湖南 湘潭 411201;2.湖南科技大學(xué)外國(guó)語學(xué)院,湖南 湘潭 411201; 3.湖南警察學(xué)院信息技術(shù)(網(wǎng)監(jiān))系,湖南 長(zhǎng)沙 410138)

1 引言

粒計(jì)算作為智能計(jì)算研究領(lǐng)域中信息處理的一種新理念和新方法,其本質(zhì)是通過選擇合適的粒度來尋找一種較好的、近似的解決問題的方案,并且在此過程中去除繁冗,降低問題求解的復(fù)雜性[1,2]。粒化,作為粒計(jì)算中的核心工作,主要是將未分組的粒子(細(xì)粒度)聚類為分組(粗粒度)。聚類,作為機(jī)器學(xué)習(xí)的最重要任務(wù)之一,旨在將相似的對(duì)象分組在一個(gè)聚類中,它主要包括數(shù)據(jù)預(yù)處理和知識(shí)聚類這2個(gè)步驟[3]。從這個(gè)角度來看,粒計(jì)算中的粒化與機(jī)器學(xué)習(xí)中的聚類任務(wù)是相同的。近年來,越來越多的研究人員也開始逐漸從粒計(jì)算的角度研究聚類方法。

粒計(jì)算中的粒度包括3個(gè)部分:粒子、粒屬性和粒結(jié)構(gòu)。粒子是粒計(jì)算的基本計(jì)算單元,因其相似性、相鄰性和一致性而內(nèi)部不可區(qū)分。粒屬性為同一粒度上所有粒子所共有的一組公共特征。粒結(jié)構(gòu)描述了同一粒度上所有粒子之間的結(jié)構(gòu)關(guān)系。目前大部分粒計(jì)算模型都是基于粒屬性進(jìn)行聚類,而沒有考慮粒結(jié)構(gòu),例如表1中的容差鄰域模型[4,5]和粗糙集理論[6,7]。表1中的商空間理論[8,9]和代數(shù)商模型[10-12]雖然分別引入了拓?fù)淞＝Y(jié)構(gòu)和代數(shù)粒結(jié)構(gòu),但僅從粒層上討論粒度的轉(zhuǎn)換方法,而沒有研究相應(yīng)的粒度聚類方法。事實(shí)上,代數(shù)粒結(jié)構(gòu)廣泛應(yīng)用于包括數(shù)字編碼、形式語言、電子電路設(shè)計(jì)等在內(nèi)的信息與通信領(lǐng)域。例如,漢明編碼是一種以模2運(yùn)算為代數(shù)粒結(jié)構(gòu)的典型應(yīng)用[12]。但是,目前系統(tǒng)地討論代數(shù)粒結(jié)構(gòu)的文獻(xiàn)非常有限。

Table 1 Brief introduction to the research of granular computing and clustering model表1 對(duì)粒計(jì)算與聚類模型研究的簡(jiǎn)述

基于以上分析,本文在作者前期工作[10-15 ]的基礎(chǔ)上,從粒計(jì)算的角度提出一種基于代數(shù)結(jié)構(gòu)的聚類方法,主要工作有以下3個(gè)方面:

(1)基于代數(shù)二元算子,建立代數(shù)粒模型,為代數(shù)結(jié)構(gòu)的粒度數(shù)據(jù)提供形式化描述方法。

(2)通過同余關(guān)系粒化,從粒計(jì)算的角度提出一種基于代數(shù)粒的聚類方法,通過粒集的同余劃分和粒結(jié)構(gòu)的同態(tài)映射進(jìn)行粒度聚類。該方法為代數(shù)結(jié)構(gòu)的粒度聚類提供一種新型方法,從結(jié)構(gòu)上豐富了粒度計(jì)算理論。

(3)將基于代數(shù)粒的聚類方法與容差鄰域模型和商空間模型進(jìn)行對(duì)比分析。實(shí)驗(yàn)結(jié)果表明,基于代數(shù)粒的聚類方法具有更好的結(jié)構(gòu)完備性和應(yīng)用魯棒性。

2 相關(guān)知識(shí)

2.1 粒計(jì)算與聚類

粒計(jì)算,最早是由Lin[6]在1997年提出的,粒計(jì)算被視為與粒子相關(guān)的所有理論、策略、方法、技術(shù)和工具[2],現(xiàn)已廣泛應(yīng)用于機(jī)器學(xué)習(xí)[16]、知識(shí)獲取[17]、復(fù)雜問題解決[18]、圖像處理、模式識(shí)別、智能控制、人工神經(jīng)網(wǎng)絡(luò)和語言動(dòng)態(tài)系統(tǒng)等領(lǐng)域。作為粒計(jì)算的關(guān)鍵工作之一,粒化可以分為變量粒化(聚類)、概念粒化(聚合)和值粒化(量化)。在數(shù)據(jù)預(yù)處理的過程中,粒化將原始數(shù)據(jù)轉(zhuǎn)換成具有不同行和列語義的表,其中行對(duì)應(yīng)于原始元組的組(粒),列表示關(guān)于每個(gè)組內(nèi)原始值的聚類信息。

聚類,是對(duì)一組對(duì)象進(jìn)行分組的任務(wù),使同一組(一類)中的對(duì)象比不同組(聚類)中的對(duì)象在某種意義上更相似。聚類是數(shù)據(jù)挖掘的主要任務(wù),也是統(tǒng)計(jì)數(shù)據(jù)分析的常用技術(shù),應(yīng)用于許多領(lǐng)域,包括圖像處理[19]、機(jī)器學(xué)習(xí)[20]、服務(wù)計(jì)算[21]、模式識(shí)別、信息檢索、生物信息學(xué)、數(shù)據(jù)壓縮和計(jì)算機(jī)圖形學(xué)。

基于粒屬性的聚類,是一種旨在創(chuàng)建聚類樹的分層聚類算法,其最終目的是降低維度、冗余和存儲(chǔ)需求。目前大多數(shù)粒計(jì)算聚類方法都是基于粒屬性的,例如:容差鄰域模型[4,5]基于容差關(guān)系進(jìn)行粒化,并且根據(jù)粒屬性的值將粒集聚集成類;粗糙集理論[6,7]粒化基于等價(jià)關(guān)系,粒集根據(jù)等價(jià)劃分被聚類。然而,上述基于粒屬性的聚類方法僅考慮粒屬性,即它預(yù)先假設(shè)粒度上的所有粒子都是獨(dú)立的,它們之間沒有任何結(jié)構(gòu)關(guān)系。

基于粒結(jié)構(gòu)的聚類,是近年來出現(xiàn)的基于粒結(jié)構(gòu)的粒計(jì)算聚類方法,如表1所示。Zhang等人[8,9]提出了商空間理論,將粒結(jié)構(gòu)指定為拓?fù)浣Y(jié)構(gòu),通過同余關(guān)系進(jìn)行粒化,為不同粒子之間的變換和分解提供了理論支持。Wang等人[22,23]將粒定義為一個(gè)七元組G=(C,Rc,Ri,Ro,B,Ω,Θ),粒結(jié)構(gòu)是由內(nèi)部關(guān)系Rc、輸入關(guān)系Ri和輸出關(guān)系Ro組成的開放系統(tǒng),為粒系統(tǒng)提供了一個(gè)強(qiáng)有力的建模概念。 Chen等人[10-12]提出粒計(jì)算的代數(shù)商模型,將粒結(jié)構(gòu)看作一個(gè)代數(shù)運(yùn)算,并通過同余關(guān)系進(jìn)行粒化。但是,上述研究?jī)H將粒結(jié)構(gòu)分別指定為拓?fù)湫蚝痛鷶?shù)運(yùn)算,而沒有從粒計(jì)算角度研究相應(yīng)的聚類方法。

2.2 粒度體系結(jié)構(gòu)

粒度,是粒計(jì)算中最基本和最重要的概念。圖1給出了論域U={ui|i=1,2,…,P}上的粒度三元組定義(UN,FQ,S),其中,P是論域U中元素個(gè)數(shù),粒集UN={vi|i=1,2,…,N}中的粒子vi是U的子集,N表示粒子數(shù)量,粒屬性FQ={fj|j=1,2,…,Q},Q表示屬性數(shù)量,粒結(jié)構(gòu)S表示粒集UN上粒子之間的結(jié)構(gòu)關(guān)系。

Figure 1 Architecture of granularity (UN,FQ,S)圖1 粒度(UN,FQ,S)的體系結(jié)構(gòu)

一般地,問題空間都是從最復(fù)雜的原始最細(xì)(離散空間上)粒度開始求解,下面提出的新型聚類方法,就是從細(xì)粒度到粗粒度進(jìn)行聚類。因此,下文所指的原始粒度(UN,FQ,S)對(duì)應(yīng)的粒集UN={vi|i=1,2,…,N},就是論域U={ui|i=1,2,…,N}上的最細(xì)粒度UN={{ui}|i=1,2,…,N}。

粒屬性FQ是所有粒子相互共有的一組特征,目前已有成熟的聚類算法,如劃分聚類(k-Means、圍繞中心點(diǎn)的劃分聚類PAM(Partitioning Around Medoid))、層次聚類(自底向上的層次聚類AGNES(Agglomerative Nesting)、自頂向下的層次聚類DIANA(DIvisive ANAlysis))和密度聚類DBSCAN(Density-Based Spatial Clustering of Applications with Noise),本質(zhì)上都是基于粒屬性離散值的距離度量,進(jìn)而對(duì)樣本集進(jìn)行聚類。基于粒屬性的聚類方法,作者在文獻(xiàn)[12,15]中另有討論。

本文不討論粒屬性,僅從粒結(jié)構(gòu)上討論信息粒化和聚類方法。因此,粒度(UN,FQ,S)可以簡(jiǎn)單地表示為二元組(UN,S)。并且,由于粒結(jié)構(gòu)作為代數(shù)被廣泛應(yīng)用于信息和通信領(lǐng)域,所以UN中的粒結(jié)構(gòu)S被特指為代數(shù)二元算子°(x,y),即粒度簡(jiǎn)化為二元組(UN,°)。

2.3 基于粒計(jì)算的聚類方法

圖2展示了聚類過程的典型步驟,以及本文工作的重點(diǎn),即從粒計(jì)算的角度設(shè)計(jì)新型聚類方法的框架。圖2下層是一個(gè)通用的聚類過程,包括從源數(shù)據(jù)中選擇特征、預(yù)處理數(shù)據(jù)、聚類方法選擇和驗(yàn)證聚類結(jié)果以及在應(yīng)用中將最終聚類結(jié)果解釋為知識(shí)表示4個(gè)步驟。圖2上層給出了本文提出的基于代數(shù)粒的聚類方法的主要內(nèi)容,包括代數(shù)粒定義的預(yù)處理和粒度粗化過程的聚類方法,對(duì)應(yīng)于機(jī)器學(xué)習(xí)視角下的特征選擇和聚類方法選擇。

Figure 2 Clustering process from the perspective of granular computing圖2 粒計(jì)算視角下的聚類過程

圖2上層的粒度定義到粒度粗化的過程,本質(zhì)上是粒計(jì)算中的粒化過程,它旨在將未分組的粒子(細(xì)粒度)聚集成幾個(gè)部分(粗粒度),而這也正是粒度聚類過程。例如,35歲、2個(gè)月、13天的客戶可以被聚類成35歲客戶的粗粒度,并且也可以被繼續(xù)聚類成中年(30～55歲)客戶的更粗粒度。在本文的設(shè)計(jì)中,數(shù)據(jù)預(yù)處理是生成信息粒度,從粒度計(jì)算角度看,其目標(biāo)是在粒化之前的信息格式化和粒度創(chuàng)建。聚類方法對(duì)應(yīng)粒計(jì)算的粒化過程,即將具有模糊或不確定性的不同粒子進(jìn)行聚類。因此,預(yù)處理和聚類方法對(duì)應(yīng)于粒化過程中的粒度定義和粒度粗化過程。

3 本文方法

基于圖2中的通用聚類框架和新型聚類方法,本節(jié)從粒計(jì)算的角度提出基于代數(shù)粒的聚類方法,主要包括以下任務(wù):

(1) 將具有代數(shù)運(yùn)算關(guān)系的粒結(jié)構(gòu)定義為一個(gè)二元算子°,進(jìn)而定義代數(shù)粒為(UN,°N×N)。

(2) 以同余關(guān)系R進(jìn)行粒化,將粒子集UN聚類到同余劃分UM中,粒結(jié)構(gòu)°N×N同態(tài)映射到⊕M×M,從而將代數(shù)粒(UN,°N×N)粒化為粗粒度(UM,⊕M×M)。其中,M表示聚類粒結(jié)構(gòu)⊕M×M的度,即聚類粒集UM的粒子數(shù)量。

3.1 粒度建模

粒度是粒計(jì)算中一個(gè)非常重要的概念,因?yàn)榱Ｏ到y(tǒng)中的孤立粒子沒有任何意義,只有當(dāng)粒子處于由具體粒化規(guī)則下的某一粒度上時(shí),它才有意義。在聚類算法的初始階段,每個(gè)聚類可以被視為粒計(jì)算中的粒子集,因?yàn)橐粋€(gè)類別本質(zhì)上是訓(xùn)練集中樣本的集合。從這個(gè)角度來看,粒計(jì)算中的每個(gè)粒子與訓(xùn)練集的每個(gè)樣本一一對(duì)應(yīng),粒子ui上的粒子集UN對(duì)應(yīng)整個(gè)訓(xùn)練集,粒度(UN,°)上的粒結(jié)構(gòu)°表示粗度UN上粒子之間的結(jié)構(gòu)關(guān)系,2.2節(jié)已將其指定為一個(gè)代數(shù)二元算子°(x,y),于是,代數(shù)粒模型可以定義如下:

定義1代數(shù)粒被定義為一個(gè)二元組(UN,°N×N),其中:

UN={ui|i=1,…,N}

(1)

°N×N={si,j←ui°uj|ui,uj,si,j∈UN}

(2)

其中,粒集UN是N元有限集,粒結(jié)構(gòu)°N×N是UN上的代數(shù)二元算子。

定義1中的°N×N的結(jié)果是二維矩陣,其描述任意2個(gè)粒子ui和uj之間的結(jié)構(gòu)關(guān)系的二元映射函數(shù),即ui°uj→si,j。顯然,定義1中的粒結(jié)構(gòu)°N×N是粒集UN上的一個(gè)代數(shù)運(yùn)算,即對(duì)于粒集UN的任意2個(gè)粒子ui和uj,在封閉二元算子°的運(yùn)算下,當(dāng)且僅當(dāng)ui和uj映射到UN中的1個(gè)元素,即si,j∈UN。

表2給出了一個(gè)代數(shù)粒(UN,°N×N)的例子,其中粒集UN={{a},{b},{c},g0gggggg,{e},{f},{g},{h}}處于問題最初始階段(離散空間)的最細(xì)粒度,即UN中的每個(gè)元素都是一個(gè)粒子,粒結(jié)構(gòu)°N×N的結(jié)果是一個(gè)二維矩陣,表示UN中任意2個(gè)變量之間的二元代數(shù)運(yùn)算,例如{a}°{b}={a},{c}°{g}={e}。若分別將粒子{a},{b},{c},g0gggggg,{e},{f},{g},{h}同態(tài)映射為0,1,2,3,4,5,6,7,則表2中的粒結(jié)構(gòu)°N×N是同余代數(shù)運(yùn)算(x×y)%8,即x乘以y并除以8的余數(shù),如表3所示。

3.2 基于代數(shù)粒的聚類方法

從粒計(jì)算的角度來看,聚類方法主要對(duì)應(yīng)于粒化過程,其核心工作是將原始粒度聚類成更粗的粒度。在3.1節(jié)定義了代數(shù)粒之后,本節(jié)主要設(shè)計(jì)基于代數(shù)粒的聚類方法,即如何將代數(shù)粒(UN,°N×N)進(jìn)行粒化。因此,本節(jié)將針對(duì)以下2個(gè)問題進(jìn)行討論:

Table 2 Granule structure °N×N results表2 粒結(jié)構(gòu)°N×N的結(jié)果

Table 3 Granule structure °N×N resultsin homomorphic mapping of table 2表3 同態(tài)映射表2中的粒結(jié)構(gòu)°N×N的結(jié)果

Q1:如何對(duì)粒集UN進(jìn)行粒化,即如何將粒集UN聚類為更粗的簇?

Q2:如何粒化粒結(jié)構(gòu)°N×N,即在對(duì)粒集UN進(jìn)行聚類時(shí),如何將粒結(jié)構(gòu)°N×N同態(tài)映射到更粗的粒度上?

為了求解問題Q1,在對(duì)粒集UN進(jìn)行聚類時(shí),需要一個(gè)粒化規(guī)則R。例如,在不考慮粒結(jié)構(gòu)的情況下,容差鄰域模型以相容關(guān)系進(jìn)行粒化[4,5];粗糙集模型以等價(jià)關(guān)系進(jìn)行粒化[6,7];商空間模型指定粒結(jié)構(gòu)為拓?fù)湫?并以等價(jià)關(guān)系進(jìn)行粒化[8,9]。以表2中的代數(shù)粒(UN,°N×N)為例,若基于相容關(guān)系,它可以被粒化為具有3個(gè)粒子{a,b,c,d},{c,d,e,f},{g,h}的覆蓋,其中粒子{a,b,c,d}和{c,d,e,f}之間存在一個(gè)交集{c,d}。若基于等價(jià)關(guān)系,它們可以被粒化成1個(gè)等價(jià)劃分{{a,c},{b,f},{d,h},{e,g}},它們之間沒有交集,即互不相容。(UN,°N×N)對(duì)問題Q1中的UN進(jìn)行粒化時(shí),至少需要一個(gè)等價(jià)關(guān)系,因?yàn)樽鳛榇鷶?shù)粒度,粒集UN是互斥的,它們之間沒有交集。

在求解問題Q2過程中,當(dāng)對(duì)粒度(UN,°N×N)的代數(shù)結(jié)構(gòu)進(jìn)行聚類時(shí),粒化不能由容差關(guān)系或等價(jià)關(guān)系決定,因?yàn)樗c最初的二元代數(shù)算子°N×N的粒結(jié)構(gòu)有關(guān)。實(shí)際上,為了同態(tài)映射代數(shù)算子°N×N到一個(gè)更粗的粒度上,粒化必須基于同余關(guān)系,也就是說,只有給定一個(gè)同余關(guān)系R,原粒結(jié)構(gòu)°N×N才會(huì)同態(tài)映射到聚類粒結(jié)構(gòu)上。

基于以上分析,基于代數(shù)粒的粒度聚類方法可以定義如下:

i∈p-1(i′),j∈p-1(j′),i′,j′=1,2,…,M

(3)

i∈p-1(i′),j∈p-1(j′),i′,j′=1,2,…,M}

(4)

定義2描述了如何將原始粒度(UN,°N×N)聚類成更粗粒度(UM,⊕M×M)。式(3)給出了聚類粒集UM的獲取方法,即從原始粒集UN到聚類粒集UM的映射方法。式(4)給出了原始粒結(jié)構(gòu)°N×N構(gòu)造聚類粒結(jié)構(gòu)⊕M×M的方法。

定義2中式(3)是聚類粒集的獲取方法,因?yàn)橐阎獥l件R是一個(gè)同余關(guān)系,它本質(zhì)是根據(jù)自然映射p:UN→(UN/R)獲取同余劃分UN/R的過程。事實(shí)上,經(jīng)典商空間模型和粗糙集理論根據(jù)等價(jià)關(guān)系R進(jìn)行粒化,即其聚類粒集是一個(gè)等價(jià)劃分UN/R;而容差鄰域模型根據(jù)相容關(guān)系R進(jìn)行粒化,即其聚類粒集是一個(gè)完全覆蓋UN/R。事實(shí)上,多數(shù)文獻(xiàn)對(duì)粗糙集理論和商空間模型的分析,都是直接給出等價(jià)關(guān)系的等價(jià)類,粗糙集理論主要討論知識(shí)粗糙/近似表示和知識(shí)約簡(jiǎn),商空間模型主要討論知識(shí)粒化和粒度轉(zhuǎn)換。

為簡(jiǎn)單起見,下文將新方法與商空間模型和容差鄰域模型進(jìn)行實(shí)例對(duì)比分析時(shí),直接給出其粒化關(guān)系——同余關(guān)系、等價(jià)關(guān)系、相容關(guān)系的相應(yīng)同余劃分、等價(jià)劃分、完全覆蓋,如表4第3列所示。

圖3展示了定義2中基于代數(shù)粒的聚類方法的主要步驟,對(duì)應(yīng)粒計(jì)算理論中的粒化過程,即粒集粗化UN→UM和粒結(jié)構(gòu)粗化°N×N→⊕M×M。所以,定義2提供了一個(gè)基于代數(shù)粒的聚類新方法,并從粒結(jié)構(gòu)的角度豐富了粒計(jì)算理論。

Figure 3 Clustering method of granules UN and granule structure °N×N圖3 粒集UN和粒結(jié)構(gòu)°N×N的聚類方法

3.3 聚類方法實(shí)現(xiàn)

算法1描述了定義2中基于代數(shù)粒的聚類方法實(shí)現(xiàn)的偽代碼。輸入論域U={u1,u2,…,uN}上的最細(xì)粒度(UN,°N×N)對(duì)應(yīng)的原始粒集UN,原始粒結(jié)構(gòu)°N×N對(duì)應(yīng)的二維矩陣AN×N,以及同余關(guān)系R的粒化規(guī)則;算法輸出聚類粒集UM與聚類粒結(jié)構(gòu)⊕M×M對(duì)應(yīng)的二維矩陣BM×M。

Table 4 Comparative results of several models to cluster algebraic granularity in table 2表4 幾種模型對(duì)表2中代數(shù)粒進(jìn)行聚類比較

算法1 對(duì)粒度(UN,N×N)進(jìn)行聚類輸入:初始粒集 UN={{u1},{u2},…,{uN}},粒結(jié)構(gòu)N×N即AN×N,同余關(guān)系 R。輸出:聚類粒集 UM,聚類粒結(jié)構(gòu)⊕M×M。Step 1 由同余關(guān)系R獲得同余劃分UM=UN/R;Step 2 M=|UM/R|;Step 3.1 初始化 BM×M,即?bi,j←?;Step 3.2 for t1←1 to N doStep 3.3 for t2←1 to N doStep 3.4 獲得 at1,t2 from AN×N;Step 3.5 for s1,s2←1 to M do Step 3.6 Search ut1∈us1的索引s1,where ut1∈UN,us1∈UM;Step 3.7 Search ut2∈us2的索引s2,where ut2∈UN,us2∈UM;Step 3.8 end forStep 3.9 bs1,s2←bs1,s2∪at1,t2;Step 3.10 end for Step 3.11 end for Step 4 輸出聚類粒集 UM;Step 5 輸出聚類粒結(jié)構(gòu)⊕M×M,即BM×M

在算法1中,Step 1根據(jù)定義2中的已知條件——同余關(guān)系R直接獲得聚類粒集UM,即同余劃分UN/R。Step 3.1將粒結(jié)構(gòu)⊕M×M的結(jié)果初始化為空矩陣,然后Step 3.2～Step 3.11建立聚類粒結(jié)構(gòu)⊕M×M的矩陣BM×M,這是該聚類方法中最重要的步驟。根據(jù)式(4),?x,y,有x°y∈[x]⊕[y],其中[x]指粒子x的聚類粒集,即聚類前的任意2個(gè)粒子的運(yùn)算結(jié)果一定屬于這2個(gè)粒子的同余類的運(yùn)算結(jié)果。于是,Step 3.2～Step 3.11中聚類粒結(jié)構(gòu)⊕M×M的建立方法是,從聚類前的表2出發(fā),Step 3.9逐步將表2中各粒子的運(yùn)算結(jié)果(表2中每一項(xiàng))歸并到聚類后的表5中,其中Step 3.5～Step 3.8先檢索表2中粒子所要?dú)w并入的表5中位置(下標(biāo))i′和j′。最后,Step 4和Step 5輸出聚類粒集UM,以及聚類粒結(jié)構(gòu)⊕M×M的結(jié)果即二維矩陣BM×M。

現(xiàn)在從時(shí)間復(fù)雜度分析聚類粒結(jié)構(gòu)⊕M×M的生成矩陣BM×M。如果根據(jù)式(3),從聚類后的表5出發(fā),逐個(gè)生成表5中元素bi,j,顯然外循環(huán)的時(shí)間復(fù)雜度為O(M2),而每個(gè)元素bi,j根據(jù)[x]⊕[y]=[x°y]生成,其時(shí)間復(fù)雜度為O(N2),所以,整個(gè)算法的時(shí)間復(fù)雜度為O(N2·M2)。顯然,如果直接根據(jù)定義(2)進(jìn)行聚類,其時(shí)間復(fù)雜性O(shè)(N2·M2)比較高。于是,本文采用啟發(fā)式方法設(shè)計(jì)了效率更高的聚類算法 ,如算法1所示,時(shí)間復(fù)雜度由Step 3.2、Step 3.3和Step 3.5決定,整個(gè)算法的時(shí)間復(fù)雜度改進(jìn)為O(N2·M)。

Table 5 Clustering the granule structure °N×N results in table 2表5 對(duì)表2的粒結(jié)構(gòu)°N×N的結(jié)果進(jìn)行聚類

下面進(jìn)一步舉例說明算法1的實(shí)現(xiàn)過程。如表4所示,當(dāng)通過同余關(guān)系R7對(duì)表2中的代數(shù)粒(UN,°N×N)進(jìn)行聚類時(shí),Step 1獲得聚類粒集UM={{a,e},{b,f},{c,g},{d,h}}。Step 3.1將聚類粒結(jié)構(gòu)⊕M×M初始化為空矩陣,其中Step 2指定矩陣⊕M×M規(guī)模為M=|UN/R|。Step 3.2～Step 3.11根據(jù)定義2中式(4)將聚類粒結(jié)構(gòu)⊕M×M推導(dǎo)為表5所示的矩陣BM×M,其同態(tài)映射矩陣如表6所示。顯然,表6中聚類粒結(jié)構(gòu)⊕M×M是一個(gè)代數(shù)運(yùn)算(x×y)%4,即它是一個(gè)同余運(yùn)算,其具體聚類過程如圖4所示,圖中U1～U4表示全論域U的子集。

Table 6 Granule structure ⊕M×M results in homomorphic mapping of table 5表6 同態(tài)映射表5中的聚類結(jié)構(gòu)⊕M×M的結(jié)果

Figure 4 Clustering process of algebraic granularity (UN,°N×N) in table 2圖4 表2中代數(shù)粒(UN,°N×N)的聚類過程

4 模型對(duì)比與分析

本節(jié)將提出的基于代數(shù)粒的聚類方法與傳統(tǒng)粒計(jì)算聚類方法中的容差鄰域模型和商空間模型進(jìn)行對(duì)比實(shí)驗(yàn),分析三者之間的差異性,得出結(jié)論:基于代數(shù)粒的聚類方法具有更好的結(jié)構(gòu)完備性,且具有更好的有效性和魯棒性。

表2描述了一個(gè)代數(shù)粒(UN,°N×N),粒集為UN={{a},{b},{c},g0gggggg,{e},{f},{g},{h}},通過表3的同態(tài)映射可以清楚地看出,粒結(jié)構(gòu)°N×N是(x×y)%8的二元代數(shù)運(yùn)算。下面以表2中的代數(shù)粒為例,通過基于代數(shù)粒的聚類方法、容差鄰域模型和商空間模型分別對(duì)其進(jìn)行聚類。

4.1 基于代數(shù)粒的聚類

定義1給出了代數(shù)粒的形式化描述(UN,°N×N),定義2給出了代數(shù)粒的聚類方法,即基于同余關(guān)系R的粒集聚類UN→UM和粒結(jié)構(gòu)聚類°N×N→⊕M×M。

在基于代數(shù)粒的聚類方法中,3.3節(jié)已經(jīng)通過算法分析了表2中代數(shù)粒的聚類過程,顯然其粒結(jié)構(gòu)由表3中的同余運(yùn)算(x×y)%8聚類為表6中的同余運(yùn)算(x×y)%4。

將表2中的代數(shù)粒(UN,°N×N)按表4中同余關(guān)系R6進(jìn)行聚類,其粒集UN由{{a},{b},{c},g0gggggg,{e},{f},{g},{h}}聚類為更粗粒集UM={{a},{b,f},{c},g0gggggg,{e},{g},{h}}。根據(jù)式(4),其粒結(jié)構(gòu)°N×N由表2聚類成表7。若將表7中的粒子{a},{b,f},{c},{d,h},{e},{g}分別同態(tài)映射為0,1,2,3,4,5,則表7中的聚類粒結(jié)構(gòu)同態(tài)映射為表8。雖然表8中代數(shù)算子不表示為 (x×y)%6,但根據(jù)定義1中的代數(shù)粒定義,對(duì)于任何ui,uj∈UM,都存在ui°uj∈UM,即表7和表8中的聚類粒結(jié)構(gòu)仍然具有代數(shù)運(yùn)算的封閉性,即表2中的原始粒結(jié)構(gòu)仍被聚類為更粗的粒結(jié)構(gòu),表7和表8中的聚類粒結(jié)構(gòu)仍然具備結(jié)構(gòu)完備性。因此,本文所提出的基于代數(shù)粒的聚類方法仍然有效。

Table 7 Clustering the granule structure ⊕M×M in table 2 with congruence relation R6表7 用同余關(guān)系R6對(duì)表2的粒結(jié)構(gòu)⊕M×M的結(jié)果進(jìn)行聚類

Table 8 Granule structure ⊕M×M results in homomorphic mapping of table 7表8 同態(tài)映射表7中的聚類結(jié)構(gòu)⊕M×M的結(jié)果

4.2 容差鄰域模型聚類

在容差鄰域模型中,不對(duì)粒結(jié)構(gòu)進(jìn)行討論,粒集通過相容關(guān)系進(jìn)行聚類。例如,在表2的代數(shù)粒(UN,°N×N)中,如果按表4中的容差關(guān)系R2和R3進(jìn)行聚類,則聚類粒集為覆蓋{{a},{b,d},{c,f,h},{d,f,h},{e},{g}}和{{a,b,d,f},{b,d,g,h},{c,e,f}},但粒結(jié)構(gòu)UN×N不能被聚類,如表4所示。

4.3 商空間模型聚類

在商空間模型中,粒結(jié)構(gòu)被指定為拓?fù)浣Y(jié)構(gòu),粒集通過等價(jià)關(guān)系進(jìn)行聚類,而粒結(jié)構(gòu)被聚類為商拓?fù)洹Ｒ虼?一個(gè)代數(shù)粒(UN,°N×N)的粒集UN仍然可以利用商空間模型進(jìn)行聚類,但代數(shù)算子的粒結(jié)構(gòu)°N×N不能被聚類。若仍然按照定義2中式(4)進(jìn)行粒結(jié)構(gòu)聚類,則聚類粒結(jié)構(gòu)不再具有定義1中的結(jié)構(gòu)完備性。

將表2中的代數(shù)粒(UN,°N×N)按表4中等價(jià)關(guān)系R4進(jìn)行聚類,其粒集UN由{{a},{b},{c},g0gggggg,{e},{f},{g},{h}}聚類為更粗粒集{{a},{b,e,f},{c,g},{d,h}}。若仍然根據(jù)定義2中式(4)對(duì)粒結(jié)構(gòu)進(jìn)行聚類,則粒結(jié)構(gòu)°N×N的結(jié)果將由表2聚類成表9。若將表2中的粒子{a},{b,e,f},{c,g},{d,h}分別同態(tài)映射為0,1,2,3,則表9中的聚類粒結(jié)構(gòu)同態(tài)映射為表10,但顯然表10中代數(shù)算子卻不表示為(x×y)%4。

表9和表10的粗體項(xiàng)表示,聚類后的代數(shù)算子⊕M×M的粒結(jié)構(gòu)不再與原代數(shù)算子°N×N同構(gòu),即雖然粒集UN={{a},{b},{c},g0gggggg,{e},{f},{g},{h}}被成功聚類為UM={{a},{b,e,f},{c,g},{d,h}},但原始粒結(jié)構(gòu)°N×N未被聚類。因?yàn)楦鶕?jù)定義1,代數(shù)粒結(jié)構(gòu)必須具有代數(shù)運(yùn)算封閉性,即具有結(jié)構(gòu)完備性,但表9和表10中的聚類粒結(jié)構(gòu)顯然不具備結(jié)構(gòu)完備性。例如,表10中b1,1={a,b,e,f}?UM,但u1,1=u0∪u1= {a}∪{b,e,f},即通過等價(jià)關(guān)系R4進(jìn)行聚類,則定義2中的聚類方法不再有效。

Table 9 Clustering the granule structure ⊕M×M resultsin table 2 with equivalence relation R4表9 用等價(jià)關(guān)系R4對(duì)表2的粒結(jié)構(gòu)⊕M×M的結(jié)果進(jìn)行聚類

Table 10 Granule structure ⊕M×M resultsin homomorphic mapping of table 9表10 同態(tài)映射表9中的聚類結(jié)構(gòu)⊕M×M的結(jié)果

4.4 差異性分析

從上述基于代數(shù)粒的聚類方法、容差鄰域模型和商空間模型對(duì)代數(shù)粒進(jìn)行聚類的實(shí)驗(yàn)結(jié)果及其分析可以發(fā)現(xiàn),它們之間的根本性區(qū)別在于:基于代數(shù)粒的聚類方法通過同余關(guān)系對(duì)粒集進(jìn)行聚類,并通過定義2中式(4)對(duì)粒結(jié)構(gòu)進(jìn)行聚類;容差鄰域模型通過相容關(guān)系對(duì)粒集進(jìn)行聚類,且不考慮粒結(jié)構(gòu);商空間模型通過等價(jià)關(guān)系對(duì)粒集進(jìn)行聚類,同時(shí)將粒結(jié)構(gòu)聚類到拓?fù)渖炭臻g。

表面上,基于代數(shù)粒的聚類方法、容差鄰域模型和商空間模型這三者之間似乎沒有明顯的相關(guān)性,但在數(shù)學(xué)上,同余關(guān)系Ra、等價(jià)關(guān)系Rb和容差關(guān)系Rc之間存在如下偏序關(guān)系Ra?Rb?Rc,從而有式(5)而立:

?x,y∈UN,Ra(x,y)?Rb(x,y)?Rc(x,y)

(5)

上述偏序關(guān)系從本質(zhì)上決定了粒集與粒結(jié)構(gòu)的聚類方法,因此可以從表4中得出結(jié)論,若給定代數(shù)粒(UN,°N×N)上的同余關(guān)系Ra,因?yàn)橥嚓P(guān)系既是等價(jià)關(guān)系又是相容關(guān)系,則既可以基于代數(shù)粒的聚類方法來對(duì)粒集UN進(jìn)行聚類,也可以用容差鄰域模型和商空間模型來對(duì)粒集UN進(jìn)行聚類。但是,如果給定同余關(guān)系Ra,代數(shù)算子的粒結(jié)構(gòu)°N×N只能使用基于代數(shù)粒的聚類方法進(jìn)行粒結(jié)構(gòu)聚類,詳見表9和表10中的粗體項(xiàng)。這意味著,與容差鄰域模型和商空間模型相比,基于代數(shù)粒的聚類方法在對(duì)粒結(jié)構(gòu)進(jìn)行聚類時(shí),具有更好的結(jié)構(gòu)完備性,且具有更好的有效性和魯棒性,而這需要在更嚴(yán)格的同余關(guān)系的前提條件下進(jìn)行。

5 結(jié)束語

本文從粒計(jì)算角度提出了一種新的基于代數(shù)粒的聚類方法。首先,基于代數(shù)二元算子,建立代數(shù)粒模型;其次,將粒度通過同余關(guān)系進(jìn)行粒化,提出了基于代數(shù)粒的聚類方法,其中粒集被聚類為同余劃分簇,粒結(jié)構(gòu)被同態(tài)映射成更粗粒結(jié)構(gòu);然后,將新型聚類方法與容差鄰域模型和商空間模型進(jìn)行對(duì)比實(shí)驗(yàn),結(jié)果表明,新型聚類方法具有更好的結(jié)構(gòu)完備性和應(yīng)用魯棒性。

基于代數(shù)粒的聚類方法為代數(shù)結(jié)構(gòu)的粒度聚類提供了一種新型方法,從結(jié)構(gòu)上豐富了粒度計(jì)算理論,并為粒計(jì)算理論與機(jī)器學(xué)習(xí)的融合研究提供了理論依據(jù)。