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

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

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

1 引言

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

粒計(jì)算中的粒度包括3個(gè)部分:粒子、粒屬性和粒結(jié)構(gòu)。粒子是粒計(jì)算的基本計(jì)算單元,因其相似性、相鄰性和一致性而內(nèi)部不可區(qū)分。粒屬性為同一粒度上所有粒子所共有的一組公共特征。粒結(jié)構(gòu)描述了同一粒度上所有粒子之間的結(jié)構(gòu)關(guān)系。目前大部分粒計(jì)算模型都是基于粒屬性進(jìn)行聚類(lèi),而沒(méi)有考慮粒結(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)換方法,而沒(méi)有研究相應(yīng)的粒度聚類(lèi)方法。事實(shí)上,代數(shù)粒結(jié)構(gòu)廣泛應(yīng)用于包括數(shù)字編碼、形式語(yǔ)言、電子電路設(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ì)算與聚類(lèi)模型研究的簡(jiǎn)述

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

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

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

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

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

2.1 粒計(jì)算與聚類(lèi)

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

聚類(lèi),是對(duì)一組對(duì)象進(jìn)行分組的任務(wù),使同一組(一類(lèi))中的對(duì)象比不同組(聚類(lèi))中的對(duì)象在某種意義上更相似。聚類(lèi)是數(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é)。

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

基于粒結(jié)構(gòu)的聚類(lèi),是近年來(lái)出現(xiàn)的基于粒結(jié)構(gòu)的粒計(jì)算聚類(lèi)方法,如表1所示。Zhang等人[8,9]提出了商空間理論,將粒結(jié)構(gòu)指定為拓?fù)浣Y(jié)構(gòu),通過(guò)同余關(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組成的開(kāi)放系統(tǒng),為粒系統(tǒng)提供了一個(gè)強(qiáng)有力的建模概念。 Chen等人[10-12]提出粒計(jì)算的代數(shù)商模型,將粒結(jié)構(gòu)看作一個(gè)代數(shù)運(yùn)算,并通過(guò)同余關(guān)系進(jìn)行?；５?上述研究?jī)H將粒結(jié)構(gòu)分別指定為拓?fù)湫蚝痛鷶?shù)運(yùn)算,而沒(méi)有從粒計(jì)算角度研究相應(yīng)的聚類(lèi)方法。

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)

一般地,問(wèn)題空間都是從最復(fù)雜的原始最細(xì)(離散空間上)粒度開(kāi)始求解,下面提出的新型聚類(lèi)方法,就是從細(xì)粒度到粗粒度進(jìn)行聚類(lèi)。因此,下文所指的原始粒度(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是所有粒子相互共有的一組特征,目前已有成熟的聚類(lèi)算法,如劃分聚類(lèi)(k-Means、圍繞中心點(diǎn)的劃分聚類(lèi)PAM(Partitioning Around Medoid))、層次聚類(lèi)(自底向上的層次聚類(lèi)AGNES(Agglomerative Nesting)、自頂向下的層次聚類(lèi)DIANA(DIvisive ANAlysis))和密度聚類(lèi)DBSCAN(Density-Based Spatial Clustering of Applications with Noise),本質(zhì)上都是基于粒屬性離散值的距離度量,進(jìn)而對(duì)樣本集進(jìn)行聚類(lèi)?；诹傩缘木垲?lèi)方法,作者在文獻(xiàn)[12,15]中另有討論。

本文不討論粒屬性,僅從粒結(jié)構(gòu)上討論信息?；途垲?lèi)方法。因此,粒度(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ì)算的聚類(lèi)方法

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

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

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

3 本文方法

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

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

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

3.1 粒度建模

粒度是粒計(jì)算中一個(gè)非常重要的概念,因?yàn)榱Ｏ到y(tǒng)中的孤立粒子沒(méi)有任何意義,只有當(dāng)粒子處于由具體粒化規(guī)則下的某一粒度上時(shí),它才有意義。在聚類(lèi)算法的初始階段,每個(gè)聚類(lèi)可以被視為粒計(jì)算中的粒子集,因?yàn)橐粋€(gè)類(lèi)別本質(zhì)上是訓(xùn)練集中樣本的集合。從這個(gè)角度來(lái)看,粒計(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},,{c},j5i0abt0b,{e},{f},{g},{h}}處于問(wèn)題最初始階段(離散空間)的最細(xì)粒度,即UN中的每個(gè)元素都是一個(gè)粒子,粒結(jié)構(gòu)°N×N的結(jié)果是一個(gè)二維矩陣,表示UN中任意2個(gè)變量之間的二元代數(shù)運(yùn)算,例如{a}°={a},{c}°{g}={e}。若分別將粒子{a},,{c},j5i0abt0b,{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ù)粒的聚類(lèi)方法

從粒計(jì)算的角度來(lái)看,聚類(lèi)方法主要對(duì)應(yīng)于粒化過(guò)程,其核心工作是將原始粒度聚類(lèi)成更粗的粒度。在3.1節(jié)定義了代數(shù)粒之后,本節(jié)主要設(shè)計(jì)基于代數(shù)粒的聚類(lèi)方法,即如何將代數(shù)粒(UN,°N×N)進(jìn)行?；?。因此,本節(jié)將針對(duì)以下2個(gè)問(wèn)題進(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聚類(lèi)為更粗的簇?

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

為了求解問(wèn)題Q1,在對(duì)粒集UN進(jìn)行聚類(lèi)時(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)系,它們可以被?；?個(gè)等價(jià)劃分{{a,c},{b,f},{d,h},{e,g}},它們之間沒(méi)有交集,即互不相容。(UN,°N×N)對(duì)問(wèn)題Q1中的UN進(jìn)行粒化時(shí),至少需要一個(gè)等價(jià)關(guān)系,因?yàn)樽鳛榇鷶?shù)粒度,粒集UN是互斥的,它們之間沒(méi)有交集。

在求解問(wèn)題Q2過(guò)程中,當(dāng)對(duì)粒度(UN,°N×N)的代數(shù)結(jié)構(gòu)進(jìn)行聚類(lèi)時(shí),?；荒苡扇莶铌P(guān)系或等價(jià)關(guān)系決定,因?yàn)樗c最初的二元代數(shù)算子°N×N的粒結(jié)構(gòu)有關(guān)。實(shí)際上,為了同態(tài)映射代數(shù)算子°N×N到一個(gè)更粗的粒度上,?；仨毣谕嚓P(guān)系,也就是說(shuō),只有給定一個(gè)同余關(guān)系R,原粒結(jié)構(gòu)°N×N才會(huì)同態(tài)映射到聚類(lèi)粒結(jié)構(gòu)上。

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

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)聚類(lèi)成更粗粒度(UM,⊕M×M)。式(3)給出了聚類(lèi)粒集UM的獲取方法,即從原始粒集UN到聚類(lèi)粒集UM的映射方法。式(4)給出了原始粒結(jié)構(gòu)°N×N構(gòu)造聚類(lèi)粒結(jié)構(gòu)⊕M×M的方法。

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

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

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

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

算法1描述了定義2中基于代數(shù)粒的聚類(lèi)方法實(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ī)則;算法輸出聚類(lèi)粒集UM與聚類(lèi)粒結(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)行聚類(lèi)比較

算法1 對(duì)粒度(UN,N×N)進(jìn)行聚類(lèi)輸入:初始粒集 UN={{u1},{u2},…,{uN}},粒結(jié)構(gòu)N×N即AN×N,同余關(guān)系 R。輸出:聚類(lèi)粒集 UM,聚類(lèi)粒結(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 輸出聚類(lèi)粒集 UM;Step 5 輸出聚類(lèi)粒結(jié)構(gòu)⊕M×M,即BM×M

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

現(xiàn)在從時(shí)間復(fù)雜度分析聚類(lèi)粒結(jié)構(gòu)⊕M×M的生成矩陣BM×M。如果根據(jù)式(3),從聚類(lèi)后的表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)行聚類(lèi),其時(shí)間復(fù)雜性O(shè)(N2·M2)比較高。于是,本文采用啟發(fā)式方法設(shè)計(jì)了效率更高的聚類(lèi)算法 ,如算法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)行聚類(lèi)

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

Table 6 Granule structure ⊕M×M results in homomorphic mapping of table 5表6 同態(tài)映射表5中的聚類(lèi)結(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)的聚類(lèi)過(guò)程

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

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

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

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

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

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

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

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)行聚類(lèi)

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

4.2 容差鄰域模型聚類(lèi)

在容差鄰域模型中,不對(duì)粒結(jié)構(gòu)進(jìn)行討論,粒集通過(guò)相容關(guān)系進(jìn)行聚類(lèi)。例如,在表2的代數(shù)粒(UN,°N×N)中,如果按表4中的容差關(guān)系R2和R3進(jìn)行聚類(lèi),則聚類(lèi)粒集為覆蓋{{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不能被聚類(lèi),如表4所示。

4.3 商空間模型聚類(lèi)

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

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

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

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)行聚類(lèi)

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

4.4 差異性分析

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

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

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

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

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