針對混合型分類數(shù)據(jù)改進(jìn)的K-modes算法距離公式

袁 方，楊有龍

西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安710126

1 引言

數(shù)據(jù)挖掘是從大規(guī)模數(shù)據(jù)中發(fā)現(xiàn)深層次的、有趣的、新穎的模式的過程，并且數(shù)據(jù)挖掘的過程具有可描述、可理解、可預(yù)測等特性。而聚類則是數(shù)據(jù)挖掘眾多技術(shù)中最重要的一種，它將m 維空間中的n個(gè)樣本點(diǎn)劃分為若干個(gè)組內(nèi)相似度較高的簇。從而發(fā)掘出包含有用信息的數(shù)據(jù)簇。例如，通過應(yīng)用聚類算法，在保險(xiǎn)信息中得到一組平均索賠成本很高的交通保險(xiǎn)保單持有人。

迄今為止，已經(jīng)有大量的聚類算法被提出對數(shù)值屬性的數(shù)據(jù)集進(jìn)行聚類。而為了解決分類屬性的聚類問題，Huang 拓展了經(jīng)典的K-means 算法[1-2]，使之適用于分類屬性的數(shù)據(jù)集，這就是K-modes 算法。這之后，將分類屬性的聚類算法與數(shù)值屬性的聚類算法相結(jié)合，衍生出了混合數(shù)據(jù)的聚類算法。但大多數(shù)的混合數(shù)據(jù)聚類算法只是關(guān)于數(shù)值屬性與無序分類屬性的數(shù)據(jù)集[3-8]，而對于混合分類屬性的數(shù)據(jù)集則研究較少。從本質(zhì)上講，聚類是根據(jù)不同對象之間的相似度處理數(shù)據(jù)的機(jī)器學(xué)習(xí)算法。兩個(gè)對象之間的相似度一般是基于對應(yīng)屬性值的差異，通常用距離函數(shù)來度量。對于分類屬性數(shù)據(jù)的聚類算法，很多研究者給出了針對算法改進(jìn)的距離函數(shù)[9-13]。簡而言之，目前關(guān)于分類屬性的距離度量方法有以下幾種：

（1）基于Hamming距離的簡單匹配度量方法

兩個(gè)分類屬性屬性值之間的距離為0 或1。這種距離度量方法往往導(dǎo)致簇內(nèi)相似性較弱，忽略了分類屬性中隱含的相似關(guān)系。這種方法的思想已經(jīng)在許多典型的聚類算法及其衍生算法中得到應(yīng)用，如原始K-modes算法、模糊K-modes算法和K-prototype算法等[9-13]。

（2）基于粗糙集理論的度量方法

粗糙集理論是Pawlak 于1982 年構(gòu)建的一種關(guān)于分類屬性信息系統(tǒng)的很有代表性的機(jī)器學(xué)習(xí)理論[14]。近年來，粗糙集理論被廣泛應(yīng)用于各種聚類和分類算法中[15-16]。Chen 等利用粗糙集理論來處理數(shù)據(jù)相似性度量中出現(xiàn)的模糊性和不確定性[17]。Jiang 等利用粗糙集理論中的隸屬函數(shù)概念[9]，提出了一種基于隸屬函數(shù)的檢測異常值的方法，并且給出了尋找異常值的算法。Cao 等根據(jù)生物學(xué)分類和粗糙隸屬函數(shù)思想[18]，將屬性值在數(shù)據(jù)集中的分布作為一個(gè)重要信息添加到相似性度量的方法中，最終得到了一種新的距離度量方法。

（3）映射原數(shù)據(jù)集到新度量空間的度量方法

Qian 等將原始分類數(shù)據(jù)集轉(zhuǎn)換為對應(yīng)的歐幾里德空間[19]，然后在新的度量空間進(jìn)行聚類。Jian 等定義了一個(gè)耦合相似性度量方法，將分類屬性的屬性值成對地映射為固定值，并且建立起一個(gè)關(guān)系矩陣[20]。Qian的方法提出了一種有效的度量方法，但度量空間的維數(shù)比原數(shù)據(jù)集要高，使得計(jì)算的復(fù)雜度隨著數(shù)據(jù)量的增加成指數(shù)增長。

以上幾種距離度量方法對分類屬性的類型不加區(qū)分，但是在實(shí)際應(yīng)用中，分類屬性有兩種不同的類型：

無序分類屬性（disordered categorical attribute）：其屬性值之間沒有順序或等級(jí)關(guān)系，僅僅只有定性描述，例如性別特征、國家、民族等。

有序分類屬性（ordinal categorical attribute）：其屬性值之間存在明顯的順序或等級(jí)關(guān)系，這一特性使屬性值之間既可以比較是否相等，也可以比較大小順序。例如學(xué)歷、成績等級(jí)（優(yōu)、良、中、差等）等。這種分類屬性也被稱之為有序?qū)傩曰蛐驅(qū)傩浴?/p>

有序分類屬性在現(xiàn)實(shí)生活中廣泛存在，例如調(diào)查問卷以及一些評價(jià)系統(tǒng)。原始的K-modes 算法和一些改進(jìn)的K-modes 算法在運(yùn)行時(shí)并沒有對這兩種屬性加以區(qū)分，從而在聚類過程中忽視了有序分類屬性所蘊(yùn)含的序信息[21-22]。例如，在學(xué)歷這一屬性（包含“小學(xué)、中學(xué)、大學(xué)、研究生”）中，可以直觀地發(fā)現(xiàn)“研究生”這一屬性值與“大學(xué)”和“初中”這兩個(gè)屬性值的距離是有差別的，在不考慮序信息的算法中，這兩個(gè)距離是相等的，這樣就造成了信息的丟失，所以需要一種新的有序分類屬性的距離度量公式來挖掘存在于有序分類屬性中的序信息。

本文在原有算法的基礎(chǔ)上，基于挖掘有序分類屬性序信息的思想，提出了一種新的有序分類屬性距離度量方法，最終給出了針對混合分類屬性數(shù)據(jù)的距離公式，并且改進(jìn)了原有的K-modes算法。

2 K-modes算法

K-modes 算法是對K-means 算法的擴(kuò)展，適用于分類型數(shù)據(jù)。該算法用眾數(shù)代替了均值，并且基于簡單匹配的思想，采用Hamming 距離來計(jì)算兩個(gè)樣本點(diǎn)之間的距離。

2.1 算法距離公式

設(shè)X={x1,x2,…,xn}為有n 個(gè)樣本點(diǎn)的分類型數(shù)據(jù)集，其中樣本點(diǎn)表示為xi={xi,1,xi,2,…,xi,m}，其屬性為{A1,A2,…,Am}。 每 個(gè) 屬 性 Ai的 值 域 為任 意 兩 個(gè) 樣 本 點(diǎn)xi={xi,1,xi,2,…,xi,m}和xj={xj,1,xj,2,…,xj,m},K-modes 的算法中它們的距離為：

其中：

2.2 算法流程

K-modes算法流程如下：

（1）在確定好簇?cái)?shù)K 后，隨機(jī)選取K 個(gè)點(diǎn)作為初始質(zhì)心。

（2）計(jì)算每個(gè)樣本點(diǎn)與K 個(gè)質(zhì)心的距離，將樣本點(diǎn)分配給最近的一個(gè)質(zhì)心。

（3）在劃分完數(shù)據(jù)集中的樣本點(diǎn)后，更新每個(gè)簇的質(zhì)心。

（4）不斷重復(fù)步驟（2）和步驟（3），直到算法達(dá)到終止的條件（目標(biāo)函數(shù)最小或者簇內(nèi)樣本點(diǎn)不再變化）。

3 改進(jìn)的距離公式及算法流程

本文對于算法的改進(jìn)主要是建立了一種新的適用于混合型分類數(shù)據(jù)的相似度度量公式，從而給出了新的距離公式。新的距離公式分為兩部分進(jìn)行闡述，第一部分為無序分類屬性的距離公式，第二部分為有序分類屬性距離公式。最后，本文給出一個(gè)改進(jìn)的K-modes 算法距離公式。

3.1 無序分類屬性的距離公式

基于粗糙集理論，該部分闡述了一種新的無序分類屬性的距離公式。假設(shè)數(shù)據(jù)是以矩陣的形式儲(chǔ)存的，其中每一行表示一個(gè)樣本點(diǎn)。這樣的一個(gè)數(shù)據(jù)矩陣同樣也是一個(gè)信息系統(tǒng)[23-24]。

定義1一般地，一個(gè)分類屬性的信息系統(tǒng)指的是這樣的一個(gè)四元組IS=(U,A,V,f)，其中，U 為非空的數(shù)據(jù)集，稱為論域（universe）；A為非空的屬性集合；V 為非空的屬性值的集合表示屬性a 的屬性值范圍，即屬性a的值域；f:U×A →V，是一個(gè)信息函數(shù)，它為U 中各對象的屬性指定唯一值。

定義 2設(shè)一個(gè)分類屬性的信息系統(tǒng)IS=(U,A,V,f)，且P ?A，可構(gòu)造對應(yīng)的二元等價(jià)關(guān)系：

則稱IND( )

P 為由P 構(gòu)造的不可分辨關(guān)系。

定義3設(shè)一個(gè)分類屬性的信息系統(tǒng)IS=(U,A,V,f),且P ?A。對?a ∈P,x,y ∈U,x,y 之間的相似度定義為：

在定義3 中，樣本點(diǎn)x 與y 的相似度也就是它們在信息系統(tǒng)中的相對重疊程度，sima( x,y )在本文中改寫為：

xi,xj∈U，且，其中：

當(dāng)f( xi, nomk)=f( xj, nomk)時(shí)f( xi, nomk)≡f( xj, nomk)=1

當(dāng)f( xi, nomk)≠f( xj, nomk)時(shí)f( xi, nomk)≡f( xj, nomk)=0

在聚類算法中，利用上述原理計(jì)算出的相似度有助于找出組內(nèi)凝聚更緊密的簇，并且根據(jù)得到的相似度，本文定義了如下距離公式。

定義4?xi,xj∈X,屬性集A,xi,xj之間的距離為：

其 中 ， Ndisnomk( xi,xj)=1-simnomk( xi,xj), 且

3.2 有序分類屬性的距離公式

以上，考慮到有序分類屬性的序信息，其距離公式與無序分類屬性的距離公式有很大不同。在聚類算法中，有序分類屬性的距離公式應(yīng)該體現(xiàn)其特征，并且在混合數(shù)據(jù)集中，應(yīng)該考慮到與無序分類屬性的距離公式平衡的問題。基于上述考慮，給出了一種定量描述有序分類屬性層級(jí)差異的度量方法。首先，將給出一個(gè)與之相關(guān)的集合的定義。

定義5有序分類屬性匹配集（Mate Set of Ordinal categorical Attribute，MSOA）指的是由滿足下述條件的無序分類屬性nomt構(gòu)成的一個(gè)集合：

其中，ηt為nomt值域的元素個(gè)數(shù)，δ 為指定有序分類屬性值域的元素個(gè)數(shù)。

根據(jù)上述定義5，對于某個(gè)有序分類屬性ordl，以及xi,xj∈U，建立如下的距離公式：

其中，δl指的是有序?qū)傩灾涤虻脑貍€(gè)數(shù)，而ηmax指的是無序分類屬性的值域元素?cái)?shù)的最大值，即

（1）當(dāng)1 ≤δl≤2

該有序分類屬性的值域元素個(gè)數(shù)最大為2，所以它與無序分類屬性并沒有顯著差異，從而依然以無序分類信息的相似度為標(biāo)準(zhǔn)對該屬性進(jìn)行度量。

（2）當(dāng)2 ＜δl≤2ηmax

首先，計(jì)算出參數(shù)Dod1的值。參數(shù)Dod1，即層級(jí)差異（difference of degree），是計(jì)算有序分類屬性距離的一個(gè)核心問題。根據(jù)下述方法計(jì)算得到Dod1。

（1）根據(jù)定義5，得到ordl的有序分類屬性匹配集MSOA( ordl)。一般情況，MSOA( ordl)包含一到兩個(gè)無序分類屬性。

（2）?nomt∈MSOA( ordl),?xi,xj∈U,計(jì)算得到所有非0的值，參數(shù)Dod1取其最小值，即

（3）當(dāng)2ηmax＜δl

由于有序分類屬性的屬性值值域元素個(gè)數(shù)已經(jīng)大于無序分類屬性值域元素個(gè)數(shù)較多，為了平衡兩種屬性之間的差異，Dod2的計(jì)算公式為：

3.3 改進(jìn)的距離公式

以上，分別給出了兩種屬性的距離公式，由此，得到改進(jìn)的算法距離公式。

首先給出兩點(diǎn)間的距離公式，?xi,xj∈U，距離公式為：

算法在執(zhí)行時(shí)，會(huì)不斷地生成新的簇，就要計(jì)算樣本點(diǎn)與質(zhì)心的距離，一般而言，可以將質(zhì)心作為數(shù)據(jù)集中的樣本點(diǎn)，依然按照上述距離公式計(jì)算。為了提高聚類效果，在上述基礎(chǔ)上給出一種新的距離度量公式：

?xi∈U,zi( i= 1,2,…,k )為相應(yīng)的簇的質(zhì)心，其無序分類屬性的距離公式與兩點(diǎn)間距離公式相同。

?xi∈U,zi( i= 1,2,…,k )為相應(yīng)的簇的質(zhì)心，則xi到質(zhì)心zi的有序分類屬性距離公式為：

（1）當(dāng)1 ≤δl≤2時(shí)

Odisordl( xi,zl)=1-simordl( xi,zl)

（2）當(dāng)2 ＜δl≤2ηmax時(shí)

（3）當(dāng)2ηmax＜δl時(shí)

依據(jù)新給出的樣本點(diǎn)到質(zhì)心的有序分類屬性距離公式，給出數(shù)據(jù)集中任意一點(diǎn)xi到質(zhì)心zi的距離為：

為了進(jìn)一步說明新距離公式在算法運(yùn)行中的實(shí)際效用，以下面的例子進(jìn)行說明。

例1表1 中數(shù)據(jù)為Car-evaluation 數(shù)據(jù)集的一部分?jǐn)?shù)據(jù)，其中屬性a4（汽車的維修費(fèi)用，屬性值為“很高、高、中、低”），屬性a5（汽車的價(jià)格，屬性值為“很高、高、中、低”），屬性a6（安全性“高、中、低”）具有明顯的順序等級(jí)關(guān)系，其為有序分類屬性。樣本點(diǎn)x6和x7為不同類的質(zhì)心。

表1 car-evaluation部分?jǐn)?shù)據(jù)

應(yīng)用兩種距離公式對數(shù)據(jù)進(jìn)行聚類，結(jié)果如下：

（1）不區(qū)分有序與無序分類屬性，都采用無序分類屬性距離公式進(jìn)行距離計(jì)算

可以發(fā)現(xiàn)，在不區(qū)分兩種屬性的情況下，5個(gè)樣本點(diǎn)到兩個(gè)質(zhì)心的距離都相等，無法給出樣本點(diǎn)屬于哪個(gè)簇。

（2）采用改進(jìn)的距離公式進(jìn)行距離計(jì)算

首先，計(jì)算出3 個(gè)有序分類屬性的屬性值個(gè)數(shù)為δa4=4,δa5=4,δa6=3, 可 以 得 到 其 相 對 應(yīng) 的MSOA( a4)={a1},MSOA( a5)={a1},MSOA( a6)={a2}，進(jìn)一 步 計(jì) 算 出 3 個(gè) 屬 性 對 應(yīng) 的，然后根據(jù)公式（5）與公式（7）計(jì)算可得：

從而，x1、x2被分配到第一個(gè)簇當(dāng)中，x3、x4、x5被分配到第二個(gè)簇當(dāng)中，分配結(jié)果正確。

從例1 可以看出，當(dāng)考慮有序分類屬性的序信息時(shí)，不同屬性值之間的距離是有差別的，本文提出的距離公式挖掘出了序信息提供的差別化的距離數(shù)值，從而使得樣本點(diǎn)與質(zhì)心的距離數(shù)值不僅能反應(yīng)出樣本點(diǎn)離某個(gè)質(zhì)心是否更近，也能反應(yīng)出與其他質(zhì)心距離之間的比較關(guān)系。不考慮序信息的情況下，樣本點(diǎn)與質(zhì)心的距離數(shù)值只能反應(yīng)與某個(gè)質(zhì)心是否更近，而不能反應(yīng)與其他質(zhì)心之間的比較關(guān)系，因?yàn)闃颖军c(diǎn)與其他質(zhì)心的距離數(shù)值不存在距離差異，從而樣本點(diǎn)與其他質(zhì)心之間的距離都是相同的。并且，改進(jìn)的距離公式還考慮了簇內(nèi)屬性的屬性值占比這一權(quán)重因子，這些特點(diǎn)有助于獲得更強(qiáng)的簇內(nèi)相似度，使算法可以更有效地將樣本點(diǎn)分配給更合理的簇。

3.4 改進(jìn)的算法流程及算法復(fù)雜度分析

由于采用了新的距離公式，并且新的距離公式是基于樣本點(diǎn)之間和樣本點(diǎn)與質(zhì)心之間這兩種情況給出的，算法的執(zhí)行流程也與原始算法流程有差異，算法1 給出了改進(jìn)的K-modes算法的具體步驟。

算法1改進(jìn)的K-modes算法：

輸入：數(shù)據(jù)集X={x1,x2,…,xn}，簇的個(gè)數(shù)k。

輸出：k個(gè)類。

初始條件：隨機(jī)確定k 個(gè)樣本點(diǎn)作為初始質(zhì)心z1,z2,…,zk，目標(biāo)函數(shù)值初始化為F(W ,Z )=0；

1.for j從1到n

2.for i從1到k

3.用式（4）計(jì)算xj與質(zhì)心zi之間的距離；

4.endfor

5.endfor

6.if xj與質(zhì)心zi之間的距離為最小

7.分配xj到第i個(gè)簇中；

8.end if

9.更新質(zhì)心并計(jì)算目標(biāo)函數(shù)F( )W,Z 的值；

10.while 目標(biāo)函數(shù)F( )W,Z 未達(dá)到終止條件，則循環(huán)執(zhí)行下列步驟：

11.for j從1到n

12.for i從1到k

13.用式（7）計(jì)算xj與質(zhì)心zi之間的距離；

14.end for

15.end for

16.if xj與質(zhì)心zi之間的距離為最小

17.分配xj到第i個(gè)簇中；

18.end if

19.更新質(zhì)心并計(jì)算F( )W,Z 的值；

算法的整個(gè)執(zhí)行過程詳細(xì)解釋說明如下：

（1）在確定好簇?cái)?shù)k 后，隨機(jī)選取k 個(gè)點(diǎn)作為初始質(zhì)心。

（2）步驟1～8，應(yīng)用式（4）計(jì)算數(shù)據(jù)集中每個(gè)樣本點(diǎn)與k個(gè)質(zhì)心的距離，將樣本點(diǎn)分配給最近的質(zhì)心。

（3）步驟9 在劃分完數(shù)據(jù)集的每個(gè)樣本點(diǎn)后，更新質(zhì)心，并根據(jù)得到的質(zhì)心計(jì)算目標(biāo)函數(shù)值。

（4）步驟11～15 依據(jù)公式（7）計(jì)算數(shù)據(jù)集中每個(gè)樣本點(diǎn)與k個(gè)質(zhì)心的距離，再一次劃分樣本點(diǎn)。

（5）不斷重復(fù)步驟11～15，直到滿足算法終止條件（目標(biāo)函數(shù)值F( )W,Z 最小或簇不再變化），則跳出循環(huán)，算法終止。

接下來，給出算法的復(fù)雜度分析，在算法執(zhí)行過程中，參照公式（1）和公式（2），計(jì)算兩點(diǎn)間無序分類屬性距離Ndis的計(jì)算復(fù)雜度為O( npk)。

參照公式（7），總的距離公式計(jì)算復(fù)雜度為：

假設(shè)迭代的次數(shù)為t，則應(yīng)用改進(jìn)的K-modes 聚類算法的計(jì)算復(fù)雜度為：

4 實(shí)驗(yàn)結(jié)果

本章比較了基于3種不同度量的K-modes算法的實(shí)驗(yàn)結(jié)果。

4.1 評價(jià)指標(biāo)及數(shù)據(jù)集說明

真實(shí)數(shù)據(jù)集Car-evaluation、Nursery、Solar Flare、Hayes-Roth、Primary Tumor、Solar Flare、Soybean 均來自UCI數(shù)據(jù)集（http：//archive.ics.uci.edu/ml/）。其中Carevaluation 數(shù)據(jù)集的類別包含的樣本點(diǎn)個(gè)數(shù)不平衡，對它進(jìn)行了處理，得到了3 個(gè)類內(nèi)樣本點(diǎn)個(gè)數(shù)平衡的子數(shù)據(jù)集。這些數(shù)據(jù)集的屬性都是分類屬性，并且數(shù)據(jù)集的屬性都包含有序分類屬性與無序分類屬性兩種不同屬性，它們都是混合型分類屬性數(shù)據(jù)集。例如，Car-evaluation數(shù)據(jù)集中的“價(jià)格”屬性（屬性值為“很高、高、中、低”），“維修費(fèi)用”屬性（屬性值為“很高、高、中、低”），“安全性”屬性（屬性值為“高、中、低”）都為有序分類屬性。其他屬性都為無序分類屬性?？偟臄?shù)據(jù)集屬性情況如表2和表3所述。

表2 數(shù)據(jù)屬性說明

表3 數(shù)據(jù)集數(shù)據(jù)說明

同時(shí)在算法運(yùn)行前，對數(shù)據(jù)集的屬性值進(jìn)行轉(zhuǎn)換，其中有序分類屬性都依照第3 章所提出的序數(shù)轉(zhuǎn)換方法進(jìn)行了轉(zhuǎn)換。

4.2 改進(jìn)算法的穩(wěn)定性分析

圖1 算法穩(wěn)定實(shí)驗(yàn)分析

為了測試算法的穩(wěn)定性，使用Nursery 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集包含12 960 個(gè)樣本點(diǎn)，并且包含8 個(gè)屬性。本文測試了兩種情況下的算法穩(wěn)定性，圖1（a）表明了算法與數(shù)據(jù)集的數(shù)據(jù)量相關(guān)的穩(wěn)定性，圖1（b）表明了算法與給定的簇?cái)?shù)相關(guān)的穩(wěn)定性。從圖1 可以看到運(yùn)行時(shí)間隨著參數(shù)的變化呈線性遞增，這說明改進(jìn)的算法在能達(dá)到更高精度的同時(shí)也具有良好的穩(wěn)定性。

4.3 改進(jìn)算法的有效性分析

比較了原始K-modes 算法、Cao 提出的K-modes 算法和本文改進(jìn)的K-modes算法的有效性。

實(shí)驗(yàn)過程中，對每個(gè)數(shù)據(jù)集，分別運(yùn)行了100 次程序，并計(jì)算了每一次實(shí)驗(yàn)的AC 指標(biāo)，最后計(jì)算100次實(shí)驗(yàn)結(jié)果的平均值，得到了算法的平均正確率，用來比較算法的優(yōu)劣。在實(shí)驗(yàn)中，算法的簇?cái)?shù)k 為數(shù)據(jù)集的類別數(shù)量，參數(shù)γi的值為1，

表4 聚類結(jié)果正確率比較表

根據(jù)表4 呈現(xiàn)的實(shí)驗(yàn)結(jié)果可以看出，在這8 個(gè)數(shù)據(jù)集中，本文提出的改進(jìn)算法獲得了良好的聚類效果。尤其在Nursery、Solar Flare、Car-evaluation（1）、Car-evaluation（3）這4 個(gè)數(shù)據(jù)集上表現(xiàn)出了相當(dāng)優(yōu)異的聚類效果。其中，在數(shù)據(jù)量最大的Nursery數(shù)據(jù)集上，準(zhǔn)確率提高了2%以上，在類數(shù)最多的Solar Flare 數(shù)據(jù)集，準(zhǔn)確率提高了10%以上。同時(shí)求得8 個(gè)數(shù)據(jù)集的聚類結(jié)果的平均值，也高于其他兩種算法的平均值。

結(jié)合數(shù)據(jù)集本身的特點(diǎn)，對實(shí)驗(yàn)結(jié)果進(jìn)行如下分析。首先可以看出，在正確率都高于同類算法的幾個(gè)數(shù)據(jù)集中，有序分類屬性的個(gè)數(shù)所占屬性總個(gè)數(shù)的比例較高。在Car-evaluation 這個(gè)數(shù)據(jù)集上，有序分類屬性的個(gè)數(shù)占到了屬性總個(gè)數(shù)的1/2，所以，盡管Car-evaluation（3）包含4 個(gè)不同類，但是算法在該數(shù)據(jù)集上的準(zhǔn)確率也是最高的。

由于改進(jìn)的距離公式不僅考慮到了有序分類屬性蘊(yùn)含的序信息，也考慮到了簇內(nèi)屬性值所占比例，這使其能反應(yīng)出樣本點(diǎn)與各個(gè)質(zhì)心距離之間的比較關(guān)系，隨著類別數(shù)的增加，聚類的正確率也隨之增加，例如：Car-evaluation（1）與Car-evaluation（2）的類別數(shù)都是2，它們的準(zhǔn)確率都在0.70 左右波動(dòng)，而Car-evaluation（3）具有4 個(gè)類別，正確率卻達(dá)到了0.79；Primary Tumor 數(shù)據(jù)集有17 個(gè)屬性，有2 個(gè)分類屬性，分類屬性的占比為2/17，較其他數(shù)據(jù)集的有序分類屬性個(gè)數(shù)占比較低，但因?yàn)槠漕悇e數(shù)為5，在數(shù)據(jù)類別數(shù)里較高，所以其聚類準(zhǔn)確率依然可以達(dá)到0.66，同樣，Solar Flare 數(shù)據(jù)集中有序分類屬性的占比也較低，但由于其數(shù)據(jù)類別達(dá)到了6個(gè)，是最高的數(shù)據(jù)類別數(shù)，所以算法的聚類準(zhǔn)確率在該數(shù)據(jù)集上也達(dá)到了0.74。

而對于Soybean 數(shù)據(jù)集，首先，有序分類屬性個(gè)數(shù)的占比為2/35，遠(yuǎn)低于其他數(shù)據(jù)集；其次，類別數(shù)也只有4個(gè)，相比于其他數(shù)據(jù)集的類別數(shù)并不算高，從而算法的聚類效果較差，較之其他兩個(gè)算法，本文提出的改進(jìn)算法的聚類準(zhǔn)確率也只比其中一個(gè)算法的準(zhǔn)確率高。

通過以上對實(shí)驗(yàn)數(shù)據(jù)的分析，可以看出，本文提出的新的距離公式和改進(jìn)的相應(yīng)算法，在混合型的分類屬性數(shù)據(jù)集上表現(xiàn)出了良好的性能，這說明改進(jìn)的距離公式和算法更加適合聚類混合型分類屬性數(shù)據(jù)。

5 方法評價(jià)與改進(jìn)

K-modes 算法在分類屬性聚類中有著廣泛的應(yīng)用，而距離公式對聚類算法的有效性起著至關(guān)重要的作用。本文基于挖掘有序分類屬性的序信息的思想，建立了一種K-modes 算法的距離公式。新的距離公式解決了Kmodes 算法處理這類數(shù)據(jù)集時(shí)存在的兩個(gè)主要問題：如何構(gòu)建針對有序分類屬性的距離公式，從而有效挖掘有序分類屬性包含的序信息；如何在總的距離度量公式中，有效平衡兩種不同類型屬性的距離公式的量綱問題。

盡管改進(jìn)的距離公式實(shí)驗(yàn)效果良好，并且擴(kuò)大了算法的數(shù)據(jù)集適用范圍，但是還有兩個(gè)問題值得深入探究：一是可以對有序分類屬性任意兩個(gè)相鄰屬性值間的等級(jí)差異有更深層次的討論。二是對于屬性權(quán)重γi取值的討論，在某些數(shù)據(jù)集中，有序分類屬性或許會(huì)貢獻(xiàn)更大的聚類作用，這時(shí)應(yīng)該賦予更大的權(quán)重，但是如何在初始狀態(tài)下確定有序分類屬性的權(quán)重，是一個(gè)值得討論的問題。

6 結(jié)束語

大多數(shù)現(xiàn)有的分類數(shù)據(jù)聚類算法的距離公式都忽略了其中的有序分類屬性，從而在聚類過程中遺漏了這一重要信息。而有些算法注意到了這個(gè)問題，但是并沒有建立起合理的有序分類屬性的層級(jí)差異，或者給出的層級(jí)差異計(jì)算公式粗糙，對兩種屬性的距離公式計(jì)算數(shù)值的平衡性造成了較大的不良影響。本文在前人的基礎(chǔ)上，對K-modes 算法的距離公式進(jìn)行了改進(jìn)，提出了一種切實(shí)可行的發(fā)掘序信息的距離公式，并且改進(jìn)的距離公式?jīng)]有造成計(jì)算的不平衡問題。改進(jìn)算法對混合型的數(shù)據(jù)根據(jù)屬性的差異，定義了不同的距離公式，同時(shí)給出了總的混合型數(shù)據(jù)的距離公式。實(shí)驗(yàn)表明，改進(jìn)的距離公式和聚類算法對于解決混合型分類屬性的數(shù)據(jù)集聚類問題給出了一個(gè)良好解決方案?，F(xiàn)實(shí)生活中，大量問卷調(diào)查數(shù)據(jù)和網(wǎng)絡(luò)平臺(tái)的注冊信息數(shù)據(jù)都屬于混合分類屬性數(shù)據(jù)，針對這類數(shù)據(jù)的聚類分析，本文的方法有望給出一個(gè)有效的解決方案。