王慧冰, 林銘煒, 姚志強(qiáng)

(福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院, 福州 350117)

聚類算法已經(jīng)在經(jīng)濟(jì)學(xué), 計(jì)算機(jī)科學(xué), 天文學(xué)等各個(gè)領(lǐng)域得到廣泛應(yīng)用[1,2]. 傳統(tǒng)的聚類算法是根據(jù)準(zhǔn)確的數(shù)值對(duì)確定的對(duì)象進(jìn)行劃分的, 但是隨著社會(huì)的進(jìn)步, 模糊數(shù)據(jù)、糊模模型成為了一種新的趨勢(shì), 這意味著傳統(tǒng)的硬劃分聚類方法也要逐漸轉(zhuǎn)向軟劃分聚類方法[3]. 研究模糊聚類的前提是要引入模糊集理論, 因?yàn)槟：垲愂腔谀：M(jìn)行劃分的. Zadeh[4]首先引入模糊語(yǔ)言學(xué)理論, 然后將模糊集應(yīng)用于多標(biāo)準(zhǔn)決策(MCDM)問(wèn)題中, 稱之為模糊 MCDM. 之后, Torra[5]提出了猶豫模糊集(HFSs), 它允許使用多個(gè)屬于[0, 1]范圍的值來(lái)評(píng)估一個(gè)屬性, 增強(qiáng)了模糊性. 然而, 在實(shí)際問(wèn)題中, 我們更多的時(shí)候得到的數(shù)據(jù)是定性信息, 不是定量值[6,7]. 例如, 當(dāng)人們?cè)u(píng)估汽車的性能時(shí), 他們可能會(huì)更偏向于使用“差”, “好”, “非常好”等語(yǔ)言術(shù)語(yǔ)來(lái)表達(dá)他們的評(píng)估結(jié)果. 因此, Zadeh提出了采用模糊語(yǔ)言學(xué)方法對(duì)評(píng)估信息進(jìn)行建模的思想, 最典型的模型有:二類模糊集合模型[8], 二元語(yǔ)言模型[9]和虛擬語(yǔ)言模型[10]. 這些語(yǔ)言模型的缺陷是: 它們要求一個(gè)對(duì)象的一個(gè)屬性只能對(duì)應(yīng)一個(gè)語(yǔ)言術(shù)語(yǔ)[11]. 基于猶豫模糊集思想和模糊語(yǔ)言學(xué)方法, Rodríguez 等人[12]提出了HFLTSs的概念, 它允許一個(gè)對(duì)象的一個(gè)屬性可以用多個(gè)語(yǔ)言術(shù)語(yǔ)來(lái)描述, 提高了評(píng)估屬性的靈活性.

目前已經(jīng)存在許多關(guān)于模糊聚類的研究, 比如, 文獻(xiàn)[13]和文獻(xiàn)[14]提出了基于直覺(jué)模糊集(IFSs)的聚類方法; 文獻(xiàn)[15]提出了猶豫模糊環(huán)境下的最小生成樹(shù)(MST)聚類方法; 文獻(xiàn)[16]通過(guò)計(jì)算猶豫模糊集的相關(guān)系數(shù)得到相關(guān)系數(shù)矩陣, 然后構(gòu)造相關(guān)系數(shù)矩陣的等價(jià)矩陣, 最后, 基于λ置信值切割矩陣得到聚類結(jié)果; 文獻(xiàn)[17]提出了一種層次猶豫模糊k-means聚類方法, 以層次聚類的結(jié)果作為k-means的初始聚類中心進(jìn)行迭代以獲得最終聚類結(jié)果, 該算法減少了k-means的迭代次數(shù), 計(jì)算成本和聚類時(shí)間; 近期, 文獻(xiàn)[18]將文獻(xiàn)[16]的方法擴(kuò)展到猶豫模糊積性集(HMSs)上使用,并取得了一定的成果; 文獻(xiàn)[19]則提出了一種基于猶豫模糊環(huán)境下的正交聚類算法. 但是目前還沒(méi)有比較成熟的基于HFLTSs的聚類方法, 而HFLTSs在實(shí)際應(yīng)用中較HFSs、IFSs及HMSs的使用更加廣泛且靈活性更大, 因此, 本文針對(duì)HFLTSs提出了一種新的正交模糊聚類算法.

1 理論基礎(chǔ)

1.1 猶豫模糊語(yǔ)言術(shù)語(yǔ)集

定義 1[12]. 設(shè)是給定的一個(gè)語(yǔ)言術(shù)語(yǔ)集, 一個(gè)HFLTS,指的是上有限個(gè)連續(xù)的語(yǔ)言術(shù)語(yǔ)的有序子集, 表示為:

備注1. 在定義1中, HFLTSs是一些離散的數(shù)值,為了避免丟失語(yǔ)言信息, 可以將離散形式擴(kuò)展為連續(xù)形式, 即,

1.2 上下文無(wú)關(guān)語(yǔ)法

文獻(xiàn)[20]提出了一種上下文無(wú)關(guān)文法, 我們可以將一些簡(jiǎn)單而豐富的語(yǔ)言表達(dá)通過(guò)轉(zhuǎn)換函數(shù)[21]轉(zhuǎn)換成HFLTSs.

定義2. 假設(shè)表示將語(yǔ)言表達(dá)轉(zhuǎn)換成HFLTSs的轉(zhuǎn)換函數(shù)表示上下文無(wú)關(guān)方法是語(yǔ)言術(shù)語(yǔ)集.通過(guò)將轉(zhuǎn)換成的表達(dá)式如下:

具體轉(zhuǎn)換過(guò)程如下:

例 1. S={極差, 很差, 差, 一般, 好, 很好, 極好}作為一本書的語(yǔ)言術(shù)語(yǔ)集, 假設(shè)一位評(píng)估者給出的對(duì)三本書的三個(gè)屬性的評(píng)估結(jié)果如下:

2 基于 HFLTSs的距離測(cè)度

距離測(cè)度是聚類分析的重要指標(biāo)之一[22], 本節(jié)將介紹基于HFLTSs的傳統(tǒng)距離測(cè)度以及改進(jìn)之后的距離測(cè)度.

2.1 傳統(tǒng)距離測(cè)度

定義3[23].設(shè)是一個(gè)語(yǔ)言術(shù)語(yǔ)集,和是 S上的任意兩個(gè)HFLTSs,表示中每一個(gè)語(yǔ)言術(shù)語(yǔ)的下標(biāo),指的是中的猶豫模糊語(yǔ)言術(shù)語(yǔ)元素(HFLTEs)個(gè)數(shù),則之間的距離測(cè)度為:

傳統(tǒng)距離測(cè)度公式要求兩個(gè)HFLTSs的HFLTEs個(gè)數(shù)一樣, 而實(shí)際上如例 1所示, 兩個(gè)不同的HFLTSs 的 HFLTEs 個(gè)數(shù)可能不同. 因此, 傳統(tǒng)距離測(cè)度采用最大值、最小值或者平均值來(lái)補(bǔ)齊HFLTEs個(gè)數(shù)較少的HFLTSs, 使HFLTEs的個(gè)數(shù)一致[24].

傳統(tǒng)距離測(cè)度方法, 涉及到有多個(gè)HFLTSs時(shí), 是對(duì)這些HFLTEs個(gè)數(shù)進(jìn)行兩兩對(duì)比, 得到距離測(cè)度.

2.2 新型距離測(cè)度

針對(duì)上面提到的傳統(tǒng)距離測(cè)度存在的缺陷, 本文對(duì)其做出改進(jìn), 重新定義如定義4.

L表示需要進(jìn)行對(duì)比的所有HFLTSs中HFLTEs個(gè)數(shù)最多的HFLTSs的長(zhǎng)度.

2.3 考慮猶豫度的新型距離測(cè)度

HFLTSs 的傳統(tǒng)距離測(cè)量只考慮了HFLTEs的值的差異, 而不考慮 HFLTEs的個(gè)數(shù)差異. 文獻(xiàn)[25]在距離測(cè)度中考慮到了猶豫度這個(gè)影響因素, 提高了計(jì)算HFSs的距離測(cè)度的準(zhǔn)確性和可靠性. 文獻(xiàn)[26]受此啟發(fā), 也在HFLTSs的距離測(cè)度公式中考慮猶豫度對(duì)其的影響, 提出了新的距離測(cè)度公式.

定義5[20]. 設(shè)是一個(gè)語(yǔ)言術(shù)語(yǔ)集,上任意的一個(gè)HFLTSs, 則的猶豫度定義為:

定義6[25]. 設(shè)是一個(gè)語(yǔ)言術(shù)語(yǔ)集是S 上任意兩個(gè)HFLTSs, 定義的距離測(cè)度公式為:

將上述距離測(cè)度擴(kuò)展到多個(gè)屬性的情況, 則定義為如定義7所示形式.

3 基于 HFLTSs的正交模糊聚類算法

3.1 基于猶豫模糊環(huán)境的正交聚類算法

近來(lái), 文獻(xiàn)[19]提出了基于HFSs的正交聚類算法,簡(jiǎn)化了聚類過(guò)程, 降低了算法復(fù)雜度, 提高了算法的效率. 該算法的步驟如下.

算法1. 基于HFSs正交模糊聚類算法.

步驟4. 根據(jù)列向量之間的正交關(guān)系對(duì)樣本進(jìn)行聚類, 具體原理如下:

為了說(shuō)明計(jì)算的復(fù)雜性, 文獻(xiàn)[19]隨機(jī)生成一些HFSs用以對(duì)比正交模糊聚類算法和模糊網(wǎng)絡(luò)聚類算法. 表1是兩種聚類方法得到聚類結(jié)果之前的運(yùn)行時(shí)間, 顯然, 正交模糊聚類算法消耗更少的時(shí)間.

表1 運(yùn)行時(shí)間對(duì)比 (單位: s)

但是該算法存在一個(gè)缺陷, 當(dāng)樣本數(shù)量大時(shí), 會(huì)得到一個(gè)非常高維的距離測(cè)度矩陣, 如果矩陣中的所有不相同的值都作為置信水平對(duì)距離測(cè)度矩陣進(jìn)行切割, 則需要消耗大量的計(jì)算成本, 且其中存在很多重復(fù)操作, 因此本文對(duì)該算法做出了改進(jìn).

3.2 基于HFLTSs的正交k-means聚類方法

針對(duì)算法1存在的問(wèn)題, 如果我們可以解決樣本數(shù)量大帶來(lái)的高維矩陣難以計(jì)算的問(wèn)題, 那么就可以進(jìn)一步降低計(jì)算復(fù)雜度. 本文采取的解決方法是減少距離測(cè)度矩陣內(nèi)部元素的差異性, 以此縮小置信水平的取值空間, 具體原理是采用構(gòu)造等價(jià)矩陣[14](等價(jià)矩陣的概念將直接體現(xiàn)在算法步驟中), 替代原始距離測(cè)度矩陣, 在等價(jià)矩陣的基礎(chǔ)上進(jìn)行正交聚類. 后期,為了證明該算法的可行性和高效性, 還將通過(guò)k-means算法對(duì)聚類結(jié)果進(jìn)行驗(yàn)證.

基于HFLTSs的正交模糊聚類算法過(guò)程如算法2.

算法2. 基于HFLTSs正交模糊聚類算法.

步驟5. 根據(jù)列向量之間的正交關(guān)系對(duì)樣本進(jìn)行聚類, 得到聚類結(jié)果.

K-means算法是常用的聚類算法, 該算法需要給定k值用以指定將目標(biāo)對(duì)象劃分成k個(gè)類別. 算法的第一個(gè)步驟是要計(jì)算初始數(shù)據(jù)的質(zhì)心, 然后計(jì)算數(shù)據(jù)到質(zhì)心的距離進(jìn)而得到新的集群質(zhì)心, 不斷迭代這個(gè)過(guò)程, 直到質(zhì)心的位置不再變化, 即聚類結(jié)束. 該算法精度高, 是最為廣泛使用的聚類算法之一, 但是kmeans的效率高低很大程度上依靠于對(duì)k值和初始質(zhì)心的選擇, 選擇不當(dāng)往往造成迭代次數(shù)多, 計(jì)算量大,消耗時(shí)間成本大的問(wèn)題, 因此本文只借助它的優(yōu)點(diǎn)來(lái)對(duì)本文提出的算法結(jié)果的準(zhǔn)確性進(jìn)行驗(yàn)證.

本文將算法2的聚類結(jié)果作為k-means的初始數(shù)據(jù), 代入到 k-means 算法中, 進(jìn)行一次迭代運(yùn)算, 求得迭代之后的聚類結(jié)果, 如果該結(jié)果與算法2的聚類結(jié)果一致, 則說(shuō)明聚類結(jié)果準(zhǔn)確.

4 實(shí)例分析

聚類分析在各行各業(yè)的應(yīng)用十分常見(jiàn), 對(duì)顧客進(jìn)行細(xì)分是最為常見(jiàn)的分析需求, 本文以顧客細(xì)分為例,驗(yàn)證本文提出的正交模糊聚類算法的可行性和高效性.

設(shè)某公司要對(duì)自己的客戶進(jìn)行劃分, 劃分客戶的主要參考因素為以下5個(gè): (1)消費(fèi)水平(2)收入水平(3)文化程度(4)上網(wǎng)時(shí)間長(zhǎng)度(5)外貌長(zhǎng)相等級(jí)5 個(gè)屬性分別所占權(quán)重為: w=(0.25, 0.2, 0.25,0.15, 0.15)T, 依據(jù)語(yǔ)言評(píng)價(jià)術(shù)語(yǔ)集, S1={s–3: 非常低, s–2:很低, s–1: 低, s0: 一般, s1: 高, s2: 很高, s3: 非常高},S2={s–3: 非常短, s–2: 很短, s–1: 短, s0: 一般, s1: 長(zhǎng), s2: 很長(zhǎng), s3: 非常長(zhǎng)}, 給出了 10 位客戶的評(píng)估信息, 如表2所示.

表2 某公司針對(duì) 10 位客戶的評(píng)估信息

步驟1. 將得到的評(píng)估信息進(jìn)行規(guī)范化, 即為元素較少的HFLTSs補(bǔ)齊元素, 使HFLTEs個(gè)數(shù)一致:

步驟2. 根據(jù)距離測(cè)量公式(7)計(jì)算樣本之間的距離測(cè)度, 其中得到距離測(cè)量矩陣

步驟3. 計(jì)算距離測(cè)量矩陣D的等價(jià)矩陣:

例如當(dāng)λ=0.1983時(shí),

當(dāng)λ=0.0486時(shí),

步驟6. 將上面得到的聚類結(jié)果作為k-means算法的初始集群, 做進(jìn)一步聚類分析, 驗(yàn)證本文算法聚類結(jié)果的準(zhǔn)確性. 因?yàn)榉譃?0個(gè)類和1個(gè)類的結(jié)果都只有一種, 所以下面只對(duì)分為2–9個(gè)類的結(jié)果進(jìn)行驗(yàn)證.

表3 正交模糊聚類結(jié)果

計(jì)算每一個(gè)樣本到類之間的距離測(cè)度:

5 總結(jié)

模糊聚類逐漸成為新的研究熱點(diǎn), 許多模糊聚類算法已經(jīng)被提出, 但是基于HFLTSs的模糊聚類算法尚未成熟, 存在計(jì)算復(fù)雜度高的缺陷, 而HFLTSs是比較流行而且靈活度很高的語(yǔ)言術(shù)語(yǔ), 因此本文提出了計(jì)算復(fù)雜度相對(duì)較低的基于HFLTSs的正交模糊聚類算法. 該算法基于HFLTSs的距離測(cè)量矩陣采用正交思想, 確定無(wú)法劃分為同個(gè)類別的樣本, 得到聚類結(jié)果.為了驗(yàn)證算法的準(zhǔn)確性和高效性, 本文還通過(guò)一個(gè)實(shí)例結(jié)合 k-means算法對(duì)本文算法進(jìn)行了驗(yàn)證. 未來(lái) , 我們將繼續(xù)研究將該算法擴(kuò)展延伸至可以應(yīng)用于更多類型的語(yǔ)言術(shù)語(yǔ), 例如概率語(yǔ)言術(shù)語(yǔ)集(PLTSs), 以及為了使該算法可以更好地應(yīng)用于大數(shù)據(jù)做進(jìn)一步的研究和努力.