基于K-prototypes的混合屬性數(shù)據(jù)聚類算法改進

摘 要：屬性數(shù)據(jù)分為數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)，一般情況下對于數(shù)值型數(shù)據(jù)運算前要進行標準化處理，但是對于數(shù)值型數(shù)據(jù)差異大的數(shù)據(jù)，由于大數(shù)掩蓋小數(shù)的影響，按照K-prototypes聚類算法，數(shù)值型數(shù)據(jù)標準化后而且不對相應的分類數(shù)據(jù)有任何預處理或者在計算時沒有進行任何改變，很可能提高分類數(shù)據(jù)在聚類中的影響，并且分類型數(shù)據(jù)并未進一步地細分，不能滿足不同要求的混合屬性聚類。該文在將數(shù)值型數(shù)據(jù)標準化的基礎上，將分類數(shù)據(jù)細分為二元數(shù)據(jù)和類型數(shù)據(jù)，并用相異度系數(shù)距離計算分類數(shù)據(jù)之間的距離，并且賦予二元和類型數(shù)據(jù)相應的權重，來改進K-prototypes聚類算法，使該算法滿足不同要求的混合屬性數(shù)據(jù)聚類，最后通過C#語言，在ArcEngine2010版本上實現(xiàn)。

關鍵詞：K-prototypes算法；混合屬性；類型數(shù)據(jù)；相異度系數(shù)；加權屬性

中圖分類號：TP311.1 文獻標志碼：A 文章編號：2095-2945（2024）28-0031-05

Abstract： Attribute data is divided into numerical data and classification data. Generally， numerical data needs to be standardized before operation. However， for data with large differences in numerical data， since the large number hides the influence of decimal numbers， according to the K-prototypes clustering algorithm， after the numerical data is standardized and the waterlogging classification data is not preprocessed or changed during calculation， the influence of classification data in clustering is likely to be improved. Moreover， the classified data has not been further subdivided and cannot meet the different requirements of mixed attribute clustering. Based on standardizing numerical data， this paper divides classified data into binary data and type data， uses dissimilarity coefficient distance to calculate the distance between classified data， and assigns waterlogging weights to the binary and type data to improve the K-prototypes clustering algorithm， so that the algorithm can meet different requirements for mixed attribute data clustering. Finally， it is implemented on ArcEngine2010 version through C# language.

Keywords： K-prototypes algorithm; mixed attributes; type data; dissimilarity coefficient; weighted attributes

聚類分析是人類認識客觀事物最樸素、最常用的手段之一，也是人類認識自然最基本、最有效的技能之一[1]。從簡單的“物以類聚，人以群分”到用數(shù)學工具去提取相關聯(lián)的信息，聚類分析快速發(fā)展成為重要的數(shù)據(jù)挖掘技術，有效地改變了現(xiàn)代“數(shù)據(jù)豐富，信息貧乏”的困境[2-3]。

MacQueen于1967年首次提出了K-means聚類算法[4]，但是此算法只能對數(shù)值屬性進行處理，對其他的分類數(shù)據(jù)無法處理。1998年，Huang[5]提出了K-modes算法，此算法雖然能夠通過匹配差異描述相異性對分類屬性數(shù)據(jù)進行處理，但對于混合屬性數(shù)據(jù)的處理還是存在一定不足。Huang等[6]進一步將K-modes算法在K-prototypes算法中推廣應用，用以解決分類屬性數(shù)據(jù)和混合屬性數(shù)據(jù)的聚類問題。

隨后又有很多基于K-prototypes算法的改進算法，如2007年趙立江等[7]改進混合屬性聚類算法，2010年陳丹等[8]研究一種改進的混合屬性聚類算法的初始中心點選擇算法，2010年陳韡等[9]基于K-prototypes混合屬性數(shù)據(jù)聚類算法的分類屬性相異度，以及2013年白天等[10]的混合屬性聚類新方法從全局上把握初始原型，還有2014年劉強等[11]改進的加權K-prototypes算法等，都是從初始點選擇或者聚類原型選擇以及分類屬性相異度計算的基礎上進行算法的改進，并未進一步對分類數(shù)據(jù)劃分計算。為此，本文在將數(shù)值型數(shù)據(jù)標準化的基礎上，將分類數(shù)據(jù)細分為二元數(shù)據(jù)和類型數(shù)據(jù)，并用相異度系數(shù)計算分類數(shù)據(jù)之間的距離，并且賦予二元和類型數(shù)據(jù)相應的權重，進一步改進K-prototypes聚類算法，使該算法滿足不同要求的混合屬性數(shù)據(jù)聚類，最后通過C#語言，在ArcEngine2010版本上實現(xiàn)。

1 K-prototypes算法

把K-means及K-modes兩種算法相融合，引入?yún)?shù)γ，在聚類過程中能夠實現(xiàn)對數(shù)值屬性以及分類屬性的權重的控制[3]。令X={X1，X2，X3，…，Xn}表示具有n個樣本的數(shù)據(jù)集，其中Xi=[Xi1，Xi2，…，Xip，Xi（p+1），…，Xim]表示第i個樣本的m個屬性值（1至p表示數(shù)值型數(shù)據(jù)屬性，p+1至m表示分類型數(shù)據(jù)屬性）。使數(shù)據(jù)集的初始聚類數(shù)為k，V={V1，V2，…，Vk}為對應模的集合，聚類過程中迭代聚類集為C={C1，C2，…，Ck}，Ci=[Ci1，Ci2，…，Cik]：①首先確定類的個數(shù)k，并為每個類選擇k個初始的聚類原型；②對樣本與各原型的距離進行計算，根據(jù)計算結果，把樣本劃分到距離最近的聚類原型相應的聚類中；③重新計算各個聚類相應的聚類原型；④循環(huán)③及④，至每個聚類中數(shù)據(jù)對象趨于穩(wěn)定，迭代F（X，V）無變化，方可停止。

定義1[5]數(shù)值屬性的距離測量采用歐幾里得距離的平方，樣本Xi與模Vl數(shù)值屬性的距離定義為

d1（Xi，Vl）=∑Xij-Vlj。 （1）

采用海明威距離公式進行類屬性距離計算，樣本Xi以及模Vl類屬性的距離為d2（Xi，Vl）

d2（Xi，Vl）=∑δ（Xij，Vlj）， （2）

式中：當Xij=Vlj時，δ（Xij，Vlj）=1；當Xij≠Vlj時δ（Xij，Vlj）=0。

定義2[5]相異性測量函數(shù)計算樣本到模的距離，d（Xi，Vl）為樣本Xi至模Vl的距離

d（Xi，Vl）=∑Xij－Vlj+γ∑δ（Xij，Vlj）

=d1（Xi，Vl）+γd2（Xi，Vl）

式中：γ表示分類屬性的權重值；δ表示分類屬性的相異度。

定義3[9]求解聚類優(yōu)化問題的目標函數(shù)（代價函數(shù)）

F（X，V）=∑∑uijd（Xi，Vj） ， （4）

∑uij=1；uij∈[0，1] ， （5）

式中：uij為1時，表示樣本Xi在類Cl中；uij為0，則不屬于類Cl。

1.1 屬性數(shù)據(jù)類型

屬性數(shù)據(jù)類型一般可以分為數(shù)值型屬性數(shù)據(jù)和分類型屬性數(shù)據(jù)，同時分類屬性數(shù)據(jù)中又包括值均為0和1類型的數(shù)據(jù)以及其他類型的數(shù)據(jù)，由于二元數(shù)據(jù)值只有0和1，任意2個維度的相同屬性值相等的概率一般比較大，所以即使二元屬性所賦權重值較小也有很高的相似性，而其他的類型數(shù)據(jù)同屬性相比相等的概率就比較低，所以要相當?shù)臋嘀刂挡拍鼙ＷC一定的相似性。因此，根據(jù)不同專題屬性的要求和影響以及分類可操控程度的不同，將分類型數(shù)據(jù)分為二元屬性數(shù)據(jù)和類型屬性數(shù)據(jù)。

數(shù)值型數(shù)據(jù)比較常見，也是聚類的基礎數(shù)據(jù)類型。對于二元屬性數(shù)據(jù)通常取值只有0和1兩個狀態(tài)，此類屬性相似性度量聚類方面通常采用匹配測度，比如農(nóng)業(yè)數(shù)據(jù)中種植作物的有和無等均可用1和0二元數(shù)據(jù)表示。而類型數(shù)據(jù)通常為0，1，2，…，n等整數(shù)，分別代表不同數(shù)據(jù)的不同類別，比如農(nóng)業(yè)數(shù)據(jù)中地貌類型、作物種類等均可賦予不同的整數(shù)來代表不同的類型。

1.2 相似性度量

1.2.1 數(shù)值型屬性數(shù)據(jù)

數(shù)值型數(shù)據(jù)相似性測度通常采用距離測度，比如切氏距離、馬氏距離、Caberra距離和平均距離等方法。一般情況下，由于數(shù)值型數(shù)據(jù)量綱、來源、量級均不相同，所以計算距離前應進行標準化處理。數(shù)據(jù)的歸一化處理是最典型的，將數(shù)據(jù)統(tǒng)一映射到[0，1]區(qū)間上，常用的標準化方法有離差標準化、標準差標準化等。

1.2.2 二元型屬性數(shù)據(jù)

二元型屬性數(shù)據(jù)相似性度量通常采用匹配測度[1]。對于2個分別包含d維二元屬性的空間實體P和Q，其中任一分量pi和qi的比較將構成以下4個變量。

1）f00：pi為0且qi也為0的屬性個數(shù)；

2）f01：pi為0且qi也為1的屬性個數(shù)；

3）f10：pi為1且qi也為0的屬性個數(shù)；

4）f11：pi為1且qi也為1的屬性個數(shù)。

此時的匹配方法有以下幾種簡單匹配系數(shù)：Jaccard系數(shù)、Tanimoto系數(shù)、Dice系數(shù)以及Kulzinsky系數(shù)等，最常用的是Jaccard系數(shù)，算法如下：對于2個分別包含d維二元屬性的空間實體P和Q，其Jaccard系數(shù)記為J（P，Q），即

J（P，Q）=f11/（f01+f10+f11） 。 （6）

1.2.3 類型屬性數(shù)據(jù)

類型屬性數(shù)據(jù)通常采用一種簡單的相似系數(shù)，根據(jù)二元屬性的定義，2個空間實體P和Q，如果這2個實體中的分量（pi和qi）相等的個數(shù)為m，分量總個數(shù)為n，則類型相似系數(shù)L（P，Q）=m/n。

2 屬性數(shù)據(jù)相異度度量

相異度度量是根據(jù)混合屬性相異度的需要，在相似性度量的基礎上建立起來的混合度量方法。

2.1 數(shù)值型距離相異度

數(shù)值型數(shù)據(jù)距離相異度，就是在數(shù)值上相距的遠近，通常采用歐式距離和歐式距離平方等方法，而K-prototypes聚類方法中數(shù)值屬性數(shù)據(jù)就是采用歐幾里平方的方法計算數(shù)值相異度。

當然，計算前要對數(shù)據(jù)進行標準化處理，處理后一般為小數(shù)，處于（0～1）之間，此時K-prototypes聚類算法不僅要計算數(shù)值型數(shù)據(jù)，而且要計算分類型數(shù)據(jù)，yes或者no型數(shù)據(jù)轉化為二元數(shù)據(jù)，其他字符串型（非數(shù)字）數(shù)據(jù)轉化為類型數(shù)據(jù)。

2.2 二元型相異度

根據(jù)二元型屬性數(shù)據(jù)相似性度量中的匹配系數(shù)，不難想到二元相異度系數(shù)即為相似度的對立面公式為

J反（P，Q）=1-f11/（f01+f10+f11） 。 （7）

取相異度系數(shù)與二元單維屬性總個數(shù)（Num）的算術平方根相乘作為二元相異度距離，即為J反（P，Q）·。

2.3 類型屬性相異度

同樣對于類型屬性數(shù)據(jù)相異度系數(shù)的定義為

L反（P，Q）=1-m/n 。 （8）

當然取相異度系數(shù)與二元單維屬性總個數(shù)的算術平方根相乘作為類型相異度距離，即為L反（P，Q）·。

3 K-prototypes算法的改進

對于K-prototypes算法中數(shù)值型數(shù)據(jù)進行標準化處理后依然選用歐幾里平方來計算距離相異度

d1（Xi，Vl）=∑Xij－Vlj。 （9）

對于二元和類型屬性數(shù)據(jù)則采用相異度系數(shù)的方法計算

d2（Xi，Vl）=J反（P，Q）·， （10）

d３（Xi，Vl）=Ｌ反（P，Q）·。 （11）

然后引入β和γ兩個參數(shù)，對聚類過程中二元屬性和類型屬性的權重進行控制。令X={X1，X2，X3，…，Xn}表示具有n個樣本的數(shù)據(jù)集，其中Xi=[Xi1，Xi2，…，Xip，Xi（p+1），…，Xim，Xim+1，…，XiH]表示第i個樣本的H個屬性值（1至p為數(shù)值型數(shù)據(jù)屬性，p+1至m為二元數(shù)據(jù)屬性，m+1至H為類型數(shù)據(jù)屬性）。令k為數(shù)據(jù)集的初始聚類數(shù)，對應模的集合為V={V1，V2，…，Vk}，迭代聚類集為C={C1，C2，…，Ck}，Ci= [Ci1，Ci2，…，Cik］，具體步驟：①首先明確類的個數(shù)k，并為每個類選擇k個初始的聚類原型；②根據(jù)改進后的K-prototypes聚類公式，對樣本到各原型距離進行計算，依據(jù)計算結果，把樣本劃分到距離最近的聚類原型相應的聚類中；③對聚類原型全部進行重新計算；④循環(huán)③及④，直至各個聚類中數(shù)據(jù)對象趨于穩(wěn)定不變，方可停止。

于是改進后的K-prototypes算法

式中：β和γ分別為二元和類型屬性數(shù)據(jù)的權重值（0～1）。

不難看出，當沒有分類型數(shù)據(jù)時，即β=0，γ=0時，該算法即為K-means算法；當沒有二元數(shù)據(jù)時，即β=γ時，該算法與K-prototypes算法相似，但其實并不相同。

4 改進后K-prototypes聚類算法實現(xiàn)與結果分析

4.1 數(shù)據(jù)選擇和計算

屬性數(shù)據(jù)選用全國農(nóng)業(yè)種植統(tǒng)計數(shù)據(jù)（2 368個城（縣、區(qū)），每個區(qū)域包含37個數(shù)值型數(shù)據(jù)，12個二元數(shù)據(jù)，4個類型數(shù)據(jù)），數(shù)值型數(shù)據(jù)標準化后計算過程如圖1所示。

4.2 改進方法聚類結果與分析

為了方便比較和分析，本次選擇34個代表縣區(qū)的所有屬性數(shù)據(jù)作為處理對象。當β=1，γ=1，k=13時，聚類結果如圖2所示。隨著β和γ值的變化，有變化的聚類個數(shù)如圖3所示。

如圖3所示，標準化后的數(shù)值型數(shù)據(jù)均在0～1，經(jīng)過歐幾里平方相加后數(shù)據(jù)不會太大，分類數(shù)據(jù)屬性相異度距離有效降低了分類數(shù)據(jù)的2個權重值在聚類過程中在某一范圍內(nèi)大幅度改變聚類結果的影響，因此還是要根據(jù)不同要求選擇合理的權重值。

5 結束語

本研究從數(shù)據(jù)標準化和分類數(shù)據(jù)細化方面，對屬性數(shù)據(jù)的計算進行改進，特別是將分類數(shù)據(jù)劃分為二元數(shù)據(jù)和類型數(shù)據(jù)，滿足和方便了用戶對不同類型數(shù)據(jù)的重要性和影響程度進行操控，實現(xiàn)理想的分類結果，對混合屬性聚類分析有一定的指導意義。當然，后期還可以對K-prototypes聚類算法的其他問題和局限進行探討，比如初始中心點選擇、全局性等方面。

參考文獻：

[1] 鄧敏，劉啟亮，李光強，等.空間聚類分析及應用[M].北京：科學出版社，2177.0101.

[2] 陳治平，林亞平，彭雅，等.基于最小無關類的數(shù)據(jù)挖掘算法[J].電子學報，2003，31（11）1750－1754．

[3] CHEN N，CHEN A，ZHOU L X.Fuzzy K-prototypes algorithm for clustering mixed numeric and categorical valued data[J].Journal of Software，2001.12（8）1107－1119．

[4] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學報，2008，19（1）48－61．

[5] HUANG Z. Extensions to the K-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery II，1998（2）283－304．

[6] Huang Z.， Ng M. A fuzzy K-modes algorithm for clustering categorical data[J].IEEE Transacitons on Fuzzy Systems，1999，7（4）：446－452．

[7] 趙立江，黃永青，劉玉龍.改進的混合屬性數(shù)據(jù)聚類算法[J].計算機工程與設計，2007，28（20）：4850－4852．

[8] 陳丹，王振華.一種改進的混合屬性數(shù)據(jù)聚類算法[J].電腦知識與技術，2010，6（11）：2713-2716.

[9] 陳韡，王雷，蔣子云，等.基于K-prototypes的混合屬性數(shù)據(jù)聚類算法[J].計算機應用，2010，30（8）：2003-2005.

[10] 白天，冀進朝，何加亮，等.混合屬性數(shù)據(jù)聚類的新方法[J].吉林大學學報（工學版），2013，43（1）：130-134.

[11] 劉強，鄧磊，賈振紅，等.一種改進的加權K-prototypes算法[J].激光雜志，2014，35（1）：18-20.