凝聚中心猶豫度恒定的模糊層次聚類算法

王志飛，陸億紅

(浙江工業大學 計算機科學與技術學院，杭州 310023)

1 引 言

隨著信息時代的發展，數據呈現爆炸式的增長，數據的處理以及數據隱性知識的發掘再次成為了學術界研究的熱點.聚類分析作為數據挖掘一個重要的組成部分，受到了國內外學者的廣泛關注[1].聚類分析應用于解決現實生活中的確定性數據問題，通過數據集包含的信息，可以將相似的數據點劃分到同一個簇中，將不相似的數據點劃分到不同的簇中.聚類分析其主要分為基于劃分的方法、基于層次的方法、基于密度的方法以及基于網格的方法.在每個領域都有各自的代表算法，如基于劃分的K-means[2]、基于層次的AGNES[3]、基于密度的DPC[4]、基于網格的STING[5].

以上介紹的傳統聚類算法主要是用于解決確定性數據集，但是隨著科技的進步以及信息時代的不斷發展，研究人員在解決數據方面的方法也是越來越豐富，還可以通過運用元組不確定性概率和屬性值不確定性概率來對確定性數據集進行研究分析[6].從模糊集合[7]理論產生以來，數學中的模糊概念與計算機方面的結合為處理確定性數據提供了一個新的研究方向，因此，越來越多的國內外學者將模糊集理論應用于聚類分析領域[8].在這種大環境下，模糊聚類算法主要分為兩個研究方向，一種是應用于傳統的確定性數據集，另外一種則是應用于模糊數據集.將模糊聚類算法應用于傳統確定性數據集時，其比傳統的聚類算法更加靈活，數據集中的數據點不再確定性的屬于某一個簇，每個數據點與每個簇之間都有一個隸屬度來表示數據點在某個簇的所屬程度，典型的代表算法就是模糊C均值算法(FCM clustering algorithm--FCM)[9]，自此，越來越多的學者開始關注模糊聚類算法[10]和模糊分類算法.

在模糊集概念出現后，K.T.Atanassov提出了直覺模糊集合的概念(A-IFS)[11]，直覺模糊集是模糊集的延伸，被稱為模糊集的包絡.A-IFS由隸屬度函數和非隸屬度函數組成，直覺模糊集的研究也層出不窮，如基于Jaccard索引為相似性度量的直覺模糊集在聚類中的應用[12]和將多粒度粗糙集與粗糙直覺模糊集相結合的模型研究[13]等.

在模糊集概念提出以來，衍生的相關概念與應用也層出不窮，其與聚類分析、決策與群決策[14]的結合領域更是成為了研究熱點.在前面介紹的兩個研究領域都是針對確定性數據集，但隨著時代的發展，數據也不再僅限于確定型數據，如生產零件，對于零件的尺寸要求就不再是一個確定性的值，是一個區間，這種是數據集本身的不確定性，現實生活中也充斥個各種各樣的不確定數據集急需處理.

2010年，Torra提出了猶豫模糊集合[15]并進行了深入研究[16]，通過猶豫模糊集合提高了猶豫問題的解決能力,Xu等人對猶豫模糊集方面的公式進行了定義和總結[17].對于猶豫模糊集合，其通過定義一組函數來為數據集的每個對象計算出一個隸屬度的集合.這種情況就是不同的評審專家對于數據對象x屬于集合A有自己的評判標準，其每個評價就是數據對象x屬于集合A的隸屬度，組合起來就是數據對象x屬于集合A的隸屬度集合，如{0.3,0.5,0.7}，這種情況在決策中十分常見.因為猶豫模糊集合更加的符合現實情況，所以在剛提出不久，就被眾多的學者應用于聚類分析[18，19].

猶豫模糊集合是在原來的模糊集合中演變而來，與直覺模糊集密切相關，猶豫模糊集合本質上是一種不確定數據的表示方法，這一概念模型很好的詮釋了現實生活中的遇事“猶豫不決”以及不同人對于事物具有不同的看法這一觀點，是近年來較為熱門且具有研究價值的一個領域.

相關文獻[14,15,18]提出了猶豫模糊數據集的聚類問題.在建立猶豫模糊對象距離函數等數學模型基礎上，給出了猶豫模糊數據集的層次聚類算法，并用實例驗證了算法理論的正確性和算法的可用性.對于該領域的實際應用有很好的貢獻，但同樣存在一些不足之處，主要體現在以下兩個方面：

1)文獻[18]采用的是加權距離函數，但在具體應用時，僅僅使用平均權值，或使用人為主觀給出的權值，沒有給出具體的權值計算公式，更沒有考慮模糊數據集本身這個客觀因素對距離權值的影響.

2)文獻[18]在計算簇中心時，其時間復雜度和空間復雜度較高，均為指數級.因此，該算法在處理數據量龐大的數據集時效果不理想，甚至無法使用，對于現實生活中來說，該算法是無效的.

針對上述兩個問題，本文提出了新的權重計算公式和簇中心計算公式，新提出的權重公式可以根據數據集本身的信息計算出更加適合的權重，而且在數據集的屬性重要性分布趨于平均分布時，權重公式兼顧了原有的平均分配原則；當簇中包含的對象逐漸增多時，新提出的簇中心計算公式的計算時間復雜度和空間復雜度不會呈指數級增長，可以將算法的時間復雜度和空間復雜度從指數級降為線性級，對于現實應用更有意義.

2 相關定義

本部分主要對本文算法以及本文研究領域方面所用到的一些概念進行普及及定義.

2.1 猶豫模糊集合

在現實生活的問題中，一個元素屬于一個集合只用一個隸屬度來表示其歸屬是很難解決的，而是可能由一組不同的隸屬值來進行表示.在這種情況下，Torra等人在文章中介紹了猶豫模糊集合[hesitant fuzzy set-HFS][15]作為模糊集新擴展的概念，HFS是由幾個取值范圍在[0,1]之間的隸屬度組成，其定義如下:

定義1[15,16].令X為一個固定集(fixed set)，則X上的一個猶豫模糊集合(HFS)是集合X經過函數h轉變成一個元素取值為[0，1]之間的集合.

此外，對于給定的一組模糊集，可以根據隸屬度的并集來定義HFS，如下所示：

定義2[15,16].令M={μ1,μ2,…,μc}為一組包含c個隸屬度函數的集合，并且x∈X.則與M相關的猶豫模糊集合(HFS)-hM定義如下：

hM(x)=∪μ∈M{μ(x)}

(1)

在此基礎上，Xia和Xu[16]通過數學總結給出了猶豫模糊集合(HFS)的表達公式如下：

A={}

(2)

其中的hA(x)是一個取值在[0，1]之間的集合，來表示元素x∈X的可能性的隸屬度.為了方便起見，hA(x)被稱為一個猶豫模糊元素(HFE)，是猶豫模糊集合(HFS)的基本單位.

上述定義1只是給出了猶豫模糊集合的語言描述，并未給出形式化的定義以及數學表達；定義2在定義1的基礎上更進一步，給出了其數學表達的定義，但是其并不便應用于解決聚類問題.有鑒于此，本文會對數學符號以及數學公式進行統一的形式化描述，以便有效地解決聚類問題.

2.2 算法相關定義

定義3.設隸屬度函數集合u={u1(x),u2(x),…,ur(x)}，若存在x使得ut(x)∈[0,1](t=1,2,…,r),則稱u為猶豫模糊集，稱|u|為猶豫模糊集u的猶豫度.

在進行后續的運算時，我們需要對猶豫模糊集的元素進行排序，也需要在計算的時候將參與運算的猶豫模糊集的猶豫度進行統一，即將猶豫度小的進行擴充，使其與猶豫度大的猶豫模糊集的維度保持一致.

對于將猶豫模糊集進行擴充時應該填入什么值，其實沒有什么固定的標準，這主要取決于研究者的風險偏好以及積累的經驗.添加不同的值可能會影響決策結果，但是這是合理的，因為添加的值所導致的決策結果是我們希望看到的結果，符合決策者的預期，本文對猶豫模糊集擴充值的方法與文獻[18]保持一致，即選用集合中最小值進行填補.

為了計算方便，本文后續所采用的猶豫模糊集都默認為有序，即猶豫模糊集的元素已按非減方式排序.

定義4.任意兩個升序排列的猶豫模糊集u={u1(x),u2(x),…,uw(x)}，v={v1(x),v2(x),…,vt(x)},兩個猶豫模糊集的猶豫度分別為|u|=w、|v|=t,若w

對于任意2個猶豫度相同的猶豫模糊集x，y，可定義如下運算.

定義5.任意給定兩個猶豫模糊集x，y，則：

1)補集：xc=∪γ∈x{1-γ}

2)并集：x∪y=∪γ1∈x,γ2∈y{γ1,γ2}

3)交集：x∩y=∪{min(γyp,γxp)}xp∈x,x,yp∈y,

|x|=|y|=σ,p=1,2,…,σ

4)數乘：λx=∪γ∈x{1-(1-γ)λ}

5)指數：xλ=∪γ∈x{γλ}

補集的計算是猶豫模糊集中每一個隸屬度與1的差值取正后得到，最終得到的補集的猶豫度與原猶豫模糊集一致.并集則是將兩個猶豫模糊集合并在一起，合并后的猶豫度是兩個猶豫模糊集的猶豫度之和.交集的計算需要兩個猶豫模糊集合保持相同的猶豫度并有序，猶豫度不同的按照定義4進行擴充，計算后得到的猶豫模糊集的猶豫度與計算前兩個猶豫模糊集較大的猶豫度一致.數乘以及指數運算，其計算后得到的猶豫模糊集的猶豫度與之前的猶豫度一致.

定義6.若d維向量X=(x1,x2,…,xd)的每個分量都是猶豫模糊集，則稱X為d維猶豫模糊對象，簡稱猶豫模糊對象.

定義7.若集合S=(X1,X2,…,Xn)中每個元素X=(xi1,xi2,…,xid)都是d維猶豫模糊對象，則稱S為猶豫模糊對象集.

任意給定兩個猶豫度相同的猶豫模糊對象X、Y，所以基于傳統的漢明距離和歐式距離，可以得到猶豫模糊加權漢明距離和猶豫模糊加權歐式距離[18]的公式如下：

猶豫模糊加權漢明距離：

(3)

猶豫模糊加權歐式距離：

(4)

對于3個猶豫度相同的猶豫模糊對象X、Y、Z，它們之間的距離為d(X,Y)，其具有以下幾個特性：

1)d(X,Y)∈[0,1]

2)d(X,Y)=0當且僅當X=Y

3)對稱性：d(X,Y)=d(Y,X)

4)三角不等式：d(X,Y)≤d(Y,Z)+d(X,Z)

有猶豫模糊集x1={x11,x12},x2={x21,x22},y1={y11,y12},y2={y21,y22},z1={z11,z12},z2={z21,z22}包含兩個隸屬值的猶豫模糊集看作二維平面的點，則可得到：

d(x1,y1)≤d(x1,z1)+d(y1,z1)；d(x2,y2)≤d(x2,z2)+d(y2,z2)

?d(x1,y1)+d(x2,y2)≤d(x1,z1)+d(y1,z1)+d(x2,z2)+d(y2,z2)

其中x={x11,x12,x21,x22},y={y11,y12,y21,y22},z={z11,z12,z21,z22}.上述x1,x2兩個集合進行合并后得到x.?2d(x,y)≤2(d(x,z)+d(y,z))?d(x,y)≤(d(x,z)+d(y,z))

x1，x2等之間的距離具有三角不等式，可得到猶豫模糊集之間的距離具有三角不等式性質.猶豫模糊對象之間的距離是每個分量上猶豫模糊集之間的距離的加權和，且距離都為正數，則加法不等號方向不變，可得到猶豫模糊對象之間的距離也具有三角不等式性質.

2.3 猶豫模糊層次聚類算法

層次聚類算法通過將數據分組到一個聚類樹中來進行聚類工作.層次聚類算法可以進一步分為凝聚型和分裂型，本文采用的是層次凝聚算法來進行聚類分析.該算法則是將層次聚類算法運用于猶豫模糊對象集上，來進行聚類分析.

算法對于簇中心的更新以及和一些運算法則給出了一些相應的定義.

定義9[15].令E={x1,x2,…,xn″}，包含n″個猶豫模糊集，θ是E上的一個函數，并且θ:[0,1]N→[0,1]，可得到：

θE=∪γ∈{x1×x2×…×xn″}{θ(γ)}

(5)

Xia和Xu[16]在上述定義情況下給出了兩個猶豫度相同的猶豫模糊對象X={x1,x2,…,xd}和Y={y1,y2,…,yd}之間的一些運算.

1)“加”：X⊕Y={x1⊕y1,x2⊕y2,…,xd⊕yd}

xj⊕yj=∪γ1∈xj,γ2∈yj{γ1+γ2-γ1γ2}

(j=1,2,…,d)

2)“乘”：X⊕Y={x1?y1,x2?y2,…,xd?yd}

xj?yj=∪γ1∈xj,γ2∈yj{γ1γ2}(j=1,2,…,d)

3)數乘：λX={λx1,λx2,…,λxd}

對象的數乘是每個分量的數乘

4)指數：Xλ={x1λ,x2λ,…,xdλ}

對象的指數運算是每個分量的指數運算

猶豫模糊對象的數乘與指數運算是每個分量上的猶豫模糊集進行計算，并不涉及跨分量，其計算規則與猶豫模糊集一致.猶豫模糊對象的“和”、“乘”運算也是每個分量上的猶豫模糊集進行計算，并不涉及跨分量，但是在運算過程中，對于兩個猶豫模糊集，計算和、乘時，需要取遍兩個集合中的每個元素進行計算，涉及兩個集合的全排列問題，如兩個集合的猶豫度都為3，則進行和、乘運算后，得到的集合的猶豫度為3*3=9，故計算后的猶豫模糊集的猶豫度是兩個猶豫模糊集猶豫度的乘積.

根據上述的法則運算可以得到簇中心的計算公式.

定義10[18].令Xi={xi1,xi2,…,xid|xij∈Xi}(i=1,2,…,n′;j=1,2,…,d)是一組猶豫模糊對象，則它們的簇{X1,X2,…,Xn′}的中心可以用“平均值”表示：

(6)

根據運算法則將公式進行轉換可以得到如下公式：

(7)

原有的猶豫模糊層次聚類算法(Hesitant fuzzy hierarchical clustering algorithm)在本文中稱為算法1，為描述方便，將該算法簡稱為HFHC算法，本文后續所有描述均由HFHC算法指代猶豫模糊層次聚類算法.

算法1.HFHC算法

輸入：猶豫模糊對象集S={X1,X2,…,Xn}，輸入所需簇的個數q

輸出：含q個簇的一個聚類C={C1,C2,…,Cq}

1.將S的每個對象當成一個初始簇，形成初始聚類C

2.REPEAT

3.根據公式(3)計算每個簇簇中心之間的距離取簇中心之間距離最小的兩個簇進行合并，并根據公式(7)計算合并后的簇的聚類中心

4.UNTIL簇的數目等于q

5.輸出聚類C={C1,C2,…,Cq}

3 FHCA算法

猶豫模糊層次聚類算法是聚類算法在猶豫模糊集上的探索性的應用，其時間復雜度與空間復雜度都是指數級的，在實際的大數據聚類應用中可能是無效的，故不能在現實生活中普及性的來解決聚類分析問題，本文提出的凝聚中心猶豫度恒定的模糊層次聚類算法(Fuzzy hierarchical clustering algorithm with constant hesitation of agglomeration center,簡稱FHCA)，降低其龐大的時間和空間消耗，使得層次聚類算法可以有效的應用于聚類分析領域.

3.1 公式定義

定義11.對于數據集S中的猶豫模糊對象之間的加權距離，其權重公式如下：

(8)

定義12.給定兩個猶豫模糊集x，y，則其之間的距離為：

(9)

計算兩個猶豫模糊對象距離時采用猶豫模糊加權漢明距離:

(10)

對于簇中心的計算，HFHC算法的公式最終得到的簇中心，因為計算的時間復雜度以及空間復雜度都是呈現指數級的增長，于現實生活中的聚類問題的應用是無效的.在此基礎上，對于原文的公式進行分析，發現公式(6)中是猶豫模糊集合的一種“平均值”的計算方法，其在每一個猶豫模糊分量上求取其“平均值”，如若計算X1,X2,…,X8這8個猶豫模糊對象合并后在分量x1上的結果，則計算出來的結果在必在[min(∪γ∈xi1γ),max(∪γ∈xi1γ)](i=1,2,…,8)之間.由于其計算出來的猶豫模糊集合中的元素個數呈現指數級增長，所以當i=n，且n足夠大時，其猶豫模糊集合中的元素值會充滿區間[min(∪γ∈xijγ),max(∪γ∈xijγ)],則選擇最小值，最大值以及平均值保證了原來猶豫模糊集的3個特性.考慮到實例的猶豫模糊集的猶豫度較小，故將其簇中心進行壓縮，使其猶豫度恒定不變，以此來有效的解決聚類問題.

定義13.令E={x1,x2,…,xn″}，包含n″個猶豫模糊集，θ是E上的一個函數，可得到：

θE=(minγ,θ(γ),maxγ)γ∈{x1×x2×…×xn″}

(11)

給出兩個猶豫度相同的猶豫模糊對象X和Y，根據猶豫模糊集之間的運算法則，可以定義兩個猶豫模糊對象之間的運算規則，其之間的運算如下所示：

3)數乘：λX={λx1,λx2,…,λxd}

對象的數乘是每個分量的數乘

4)指數：Xλ={x1λ,x2λ,…,xdλ}

對象的指數運算是每個分量的指數運算

并集、指數和數乘運算參考猶豫模糊集，此處并不過多解釋.對于本文的定義和運算，兩個猶豫模糊集計算后得到的猶豫模糊集的猶豫度為3，不會隨著原有的猶豫度而變化.

根據上述運算規則，得到下面簇中心的計算公式.

定義14.若現有兩個將要進行合并的簇Cr={Xr1,Xr2,…,Xre}、Cl={Xl1,Xl2,…,Xlg}，Rc={r1,r2,…,re,l1,l2,…,lg}其中簇Cr包含e個猶豫模糊對象，簇Cl包含g個猶豫模糊對象，則合并后的簇中心的公式如下：

(12)

其中xj代表若干個數據點聚集成一個簇后其第j個分量，p=1,2,…,mij.

根據前面的定義以及運算法則，可以得到如下結論.

定理 1.給定兩個猶豫模糊集x，y；3個猶豫模糊對象X,Y,Z則有：

1)(xc)λ=(λx)c

2)λxc=(xλ)c

證明：為了敘述方便，在此只證明1),其他結論可類似證明得到.

xcλ=∪γ∈x{1-γ}λ=∪γ∈x{(1-γ)λ} (λx)c=∪γ∈x{1-(1-γ)λ}c=∪γ∈x{1-(1-(1-γ)λ)}=∪γ∈x{(1-γ)λ} 左邊=右邊，則xcλ=(λx)c

3.2 FHCA算法流程

將本文所提出的權重公式和簇中心更新公式應用于層次聚類算法中解決猶豫模糊對象集問題得到FHCA算法.

算法2.FHCA算法

輸入：猶豫模糊對象集S={X1,X2,…,Xn}，輸入所需簇的個數q

輸出：含q個簇的一個聚類C={C1,C2,…,Cq}

1.將S的每個對象當成一個初始簇，形成初始聚類C

2.REPEAT

3.根據公式(10)計算每個簇簇中心之間的距離

4.取簇中心之間距離最小的兩個簇進行合并，并根據公式(12)計算合并后的簇中心

5.UNTIL簇的數目等于q

6.輸出聚類C={C1,C2,…,Cq}

4 實例分析

下面將用兩個例子來對上述公式進行驗證，例子由8個猶豫模糊對象組成，其中4個猶豫模糊對象組成一個簇，另外4個組成另外一個簇，屬性維度為3，在簇中4個猶豫模糊對象的某一個屬性維度上的猶豫模糊集合的平均值相等，兩個簇在這一屬性維度上的平均值相差較大，以此來明確區分這兩個簇，具體數據如表1所示.

表1 猶豫模糊對象集Table 1 Hesitation blurry object sets

進行第1次微簇合并時，每一個猶豫模糊對象就是一個簇，故簇中心就是猶豫模糊對象本身.本文采用猶豫模糊加權漢明距離公式來計算距離，則根據公式(8)，計算猶豫模糊分量所對應的權重，得到ω1=0.2900，ω2=0.3318，ω3=0.3782.

根據距離式(9)、式(10)以及計算出來的權重，可以得到各簇中心之間的加權距離矩陣dFHCA，其中距離矩陣dFHCA中的行從左到右依次為X1,X2,…,X8，列從上到下依次為X1,X2,…,X8，由猶豫模糊對象之間的距離性質3)對稱性可以得到矩陣沿左上至右下對角線對稱，是一個特殊的矩陣-對稱矩陣，故距離矩陣可寫成上三角矩陣.如第3行第2列的值代表猶豫模糊對象X3和X2之間的距離為0.0697，即得到d(X2,X3)=0.0697.由對稱性和猶豫模糊集之間的距離性質2)可以得到對角線元素全部為零.

如距離矩陣dFHCA所示，距離最近的兩個簇是{X7}和{X8}，所以選擇這兩個簇進行合并，得到新的簇{X7,X8}，根據公式(12)計算新簇的簇中心，得到c{X7,X8}=f{X7,X8}={{0.57,0.75,0.95},{0.75,0.8,0.86},{0.6,0.7,0.8}},其余的簇簇中心不變則得到更新后的簇的簇中心數據表如表2所示.

后續計算過程此處略過，當合并為一個簇時，算法終止.

表2 合并后數據對象表Table 2 Merged data objects

在實例上用HFHC算法進行計算，得到相應的結果，與FHCA算法的計算結果對比如表3所示.

從表3可以看出，本文方法與原文的方法最大的區別在形成4個簇以及3個簇的時候，我們可以先看數據的分布，然后再來看兩種方法形成的簇的優劣.表1所示的猶豫模糊對象集，將其每個猶豫模糊元素中的值取平均值，結果如表4所示.

從表4可以看出，猶豫模糊對象X1,X2，X3，X4在屬性X3上的屬性值相等，猶豫模糊對象X5,X6，X7，X8在屬性X3上屬性值相等，故其在X3屬性上可不在圖形展示上展現出來，即可用二維坐標系展現出數據點的大致分布圖，分布圖如圖1所示.

表3 HFHC和FHCA聚類結果對比表Table 3 Comparison results of HFHC and FHCA

表4 對象均值表Table 4 Mean values of objects

圖1 對象均值分布圖Fig.1 Distribution of the object mean values

從圖1可以看出，當簇數為4時，形成的簇為以下4種：

1){{X1,X2},{X3,X4},{X5,X6},{X7,X8}}

2){{X1,X3},{X2,X4},{X5,X6},{X7,X8}}

3){{X1,X2},{X3,X4},{X5,X7},{X6,X8}}

4){{X1,X3},{X2,X4},{X5,X7},{X6,X8}}

較為合理，本文形成的簇的情況為第2)種，比原文的簇的形成更加合理.

當簇數為3時，形成的簇為：

1){{X1,X2,X3,X4},{X5,X6},{X7,X8}}

2){{X1,X3},{X2,X4},{X5,X6,X7,X8}}

3){{X1,X2,X3,X4},{X5,X7},{X6,X8}}

4){{X1,X2},{X3,X4},{X5,X6,X7,X8}}

較為合理，本文形成的簇的情況為第1)種，也比原文的簇的形成更加合理，通過對比發現，FHCA算法優勢明顯.

另外采用HFHC算法的例子進行計算，最終結果如表5所示.

表5 HFHC和FHCA聚類結果對比表Table 5 Comparison results of HFHC and FHCA

從表5中可以看到，本文方法與原文方法的計算結果一致.總體來說，兩個例子中，FHCA算法效果有一個表現與原文一致，另一個甚至優于原文的方法，在此基礎上還降低了時間復雜度與空間復雜度，此部分后續會進行詳細的分析.

5 復雜度分析

本部分將對新算法的時間復雜度和空間復雜度進行相應的分析，同時也會對原算法進行分析，兩者進行對應的比較分析，來證實新算法的實用性.

5.1 時間復雜度分析

根據章節相關算法分析部分，可以得到相對應的時間復雜度的分析，即進行HFHC算法時，若最終聚集成一個簇時，則簇中包含n個猶豫模糊對象，則可以得到兩個算法的時間復雜度對比如表6所示.

表6 時間復雜度對比表Table 6 Time complexity of various methods

5.2 空間復雜度

從時間復雜度方面的計算可知，當設置的算法停止條件為凝成一個簇時，即n個猶豫模糊對象在一個簇，則對其進行相應的分析.

FHCA算法因采用簇中心猶豫度恒定的方法，用最大值、最小值以及平均值來進行簇中心的計算，從計算公式也可以得到相應的結論，最終的空間復雜度為O(1)，得到兩個算法對比結果如表7所示.

表7 空間復雜度對比表Table 7 Space complexity of various methods

從上述兩方面的分析可以看出，在兩個例子的計算中，原文的例子，本文方法與原文方法效果相同，但是時間和空間開銷都相應的降低了；而另外一個例子，本文方法在降低時間和空間消耗時，也獲得了優于原文的實驗結果.

當所處理的數據集中的數據對象規模巨大的時候，顯然原文這種高時間和空間成本是難以承受的，而本文則將時間和空間的復雜度從原來的指數級降低到現在的多項式級，而且實驗效果并沒有變差，顯然是更加適用于現實應用場景.

6 總 結

本文提出的基于數據集本身所含信息的權重公式以及簇中心的計算公式，通過理論分析以及實例證明，在將時間復雜度以及空間復雜度從指數級降至線性級的情況下，還可以得到理想的聚類效果，聚類精度有所改善，相比較而言更加的適用于現實生活，在沒有巨大的開銷就可以解決現實生活中的“猶豫不決”等數據集問題，提供決策支持.因沒有相關數據集，同時該領域研究用示例來演示，本文同樣用示例進行了模擬展示，下一步的研究方向則是在數據集上的效果以及在聚類分析領域的拓展，例如在密度聚類等算法上的實際應用問題.