竇 婷，張正軍

(南京理工大學(xué) 理學(xué)院, 南京 210094)

基于IGS方法的最佳分類數(shù)研究*

竇 婷，張正軍**

(南京理工大學(xué) 理學(xué)院, 南京 210094)

針對選擇Gap Statistic(GS)方法估計聚類數(shù)能夠得到數(shù)據(jù)集的粗略分類，但不能進一步對數(shù)據(jù)集進行細分類這一問題，對GS方法進行改進；將Gap統(tǒng)計量引入到ISODATA算法中，提出了IGS模型；實證表明，IGS模型不僅可以實現(xiàn)數(shù)據(jù)的細分類，而且通過IGS模型估計數(shù)據(jù)集的最佳分類數(shù)準確率明顯高于原GS模型。

Gap Statistics；IGS模型；聚類數(shù)；ISODATA算法

0 引 言

2000年，Tibshirani R[1]等在K-means方法基礎(chǔ)上提出了用Gap Statistic(GS)方法估計數(shù)據(jù)集的最佳聚類數(shù)，該方法提出之后，就引起了廣泛關(guān)注和應(yīng)用。GS方法從統(tǒng)計學(xué)的角度解釋并通過理論證明了樣本數(shù)據(jù)的合理分類數(shù)的有效性。通過大量的仿真實驗，GS方法比其他算法在估計最佳聚類數(shù)方面要好。

2003年，Mei 和Lajbcygier等[2]通過將GS方法與傳統(tǒng)方法進行比較，分析了日本投資者共有的投資模式，發(fā)現(xiàn)通過GS方法有較多的優(yōu)點。2005年，張正軍，黃陳蓉等[3]通過樣本灰度數(shù)據(jù)分布的差別從而定義了多尺度的圖像灰度間隙,首先提出了反分布函數(shù)概念,在此基礎(chǔ)上又建立了圖像邊緣檢測的多尺度灰度Gap統(tǒng)計模型。2006年，李娜[4]對Gap統(tǒng)計量進行改進修正，計算出一維情況下具體Gap統(tǒng)計量的表達式，從而減少了計算量。2007年，Mingjin Yan[5]通過把類內(nèi)離差程度總和變成每一類的平均離差程度之和的方法，使得每類離散程度的表示不受類內(nèi)樣本數(shù)量影響，從而更能體現(xiàn)出類內(nèi)的相似度，使得GS方法更具有穩(wěn)定性。2008年，岳士宏等[6]通過類內(nèi)離差程度的二階差分作為最佳聚類數(shù)的一個評判標(biāo)，故而省去了選擇參考分布，使算法變得簡單有效。

GS方法可以適用于硬聚類，同樣也可適用于模糊聚類。2007年，Sentelle C等[7]把GS方法的思想應(yīng)用于FCM方法上，提出了FGS模型，該模型可以更好地刻畫出某些模糊數(shù)據(jù)集的聚類特征。2008年，Arima C等[8]在FGS模型基礎(chǔ)上對其進行改進，并提出了MFGS模型，該模型適應(yīng)于基因表達數(shù)據(jù)集。2011年，童波[9]又對FGS模型進行了不同改進，提出了相應(yīng)的MFGS模型，并且把該模型應(yīng)用在圖像分割中。2013年，劉倩[10]接著提出了WGS及DWGS模型，對原始灰度圖像進行了合理的分割。

針對傳統(tǒng)GS方法不能對數(shù)據(jù)集進行細分類的不足，對GS方法進行改進從而提出相應(yīng)的改進模型IGS，通過它估計出數(shù)據(jù)集的最佳分類數(shù)，并且將GS模型和IGS模型在聚類收斂速度和聚類準確率兩方面進行比較。

1 GS模型

傳統(tǒng)的Gap Statistic方法的核心思想是：首先，選擇一個參考分布，通過參考分布生成參考數(shù)據(jù)集；其次，將待分類數(shù)據(jù)的離散程度和參考數(shù)據(jù)集的離散程度進行比較，將分類數(shù)作為自變量，建立一個Gap統(tǒng)計量；最后，通過分析Gap統(tǒng)計量關(guān)于聚類數(shù)的變化情況來確定最佳聚類數(shù)[9]。

傳統(tǒng)的Gap Statistic的主要內(nèi)容有：假設(shè)數(shù)據(jù)集已由K-means算法聚成k類：C1,C2,…,Ck，nr=Cr。令

(1)

其中，Dr表示聚類r中所有數(shù)據(jù)兩兩之間的距離平方和。再令

(2)

其中，Wk表示k類離差程度的總和。由此定義Gap統(tǒng)計量：

(3)

2 IGS模型

使用傳統(tǒng)的GS方法能夠得到數(shù)據(jù)集的粗略分類，然而不能進一步對數(shù)據(jù)進行細分類。GS方法基于K-means聚類算法，在 K-means 算法中聚類數(shù)值K是事先給定的，但是這個K值的選定是非常難以估計的。對于高維或者海量的數(shù)據(jù)集事先不知道應(yīng)該分成多少個類別才最合適，然而ISODATA算法可以通過類的自動合并和分裂[11]，得到較為合理的類型數(shù)目K。IGS模型即將Gap統(tǒng)計量引入到ISODATA算法[12-15]中。通過IGS方法對類別數(shù)相對較多的數(shù)據(jù)集聚類可以得到數(shù)據(jù)集的細分類，比如Glass數(shù)據(jù)集，GS方法對Glass數(shù)據(jù)集進行聚類得到的最佳聚類數(shù)為2，而通過IGS方法對Glass數(shù)據(jù)集進行聚類得到的最佳聚類數(shù)為7?？紤]到ISODATA算法相對K-means算法時間略長些，故對生成的參考數(shù)據(jù)集依舊用K-means進行聚類。

IGS模型的算法步驟如下：

Step1 通過ISODATA算法對數(shù)據(jù)集進行聚類，得到各類別的類內(nèi)離差平方和Wk；

(4)

Gap(k)≥Gap(k+ 1)-sk + 1

(5)

3 仿真實驗及分析

通過幾組實驗與原始GS方法進行比較，驗證提出的IGS方法的可行性與優(yōu)越性。對參考分布的生成進行蒙特卡洛模擬，采用的聚類算法是ISODATA算法。通過這個算法得出的聚類結(jié)果較穩(wěn)定，故采用Gap曲線圖來分析IGS方法的結(jié)果。

(1) 實驗數(shù)據(jù)集，實驗使用的UCI機器學(xué)習(xí)數(shù)據(jù)庫的4個測試聚類算法的常用數(shù)據(jù)集的描述見表1。

表1 實驗所用的UCI數(shù)據(jù)集描述

(2) IGS方法的實驗結(jié)果和分析。本實驗采用UCI數(shù)據(jù)庫中的Iris，Glass，Haberman和Ionoshpere 4個數(shù)據(jù)集，采用GS和IGS兩種方法對以上數(shù)據(jù)集進行聚類并估計出最佳聚類數(shù)，檢驗IGS方法的可行性。

對于ISODATA算法來說，參數(shù)的選取直接影響到聚類的效果，對于Iris數(shù)據(jù)集參數(shù)選取如下：θN=5，θS=1.8，θC=1.5，L=2，I=100，從圖1中可以看出既可以用傳統(tǒng)GS方法估計出最佳聚類數(shù)，所得的最佳聚類數(shù)為3，也可以用所介紹的IGS方法估計出最佳聚類數(shù)，得到的最佳聚類數(shù)為3。

圖1 Iris數(shù)據(jù)集中Gap和IGap隨聚類數(shù)的變化曲線Fig.1 Iris data set Gap and IGap change Curve with the number of clusters

對于Glass數(shù)據(jù)集，ISODATA算法選取的參數(shù)為θN=5，θS=2.5，θC=0.2，L=2，I=100，由圖2可知，IGS方法得到的估計值為7，而GS方法得到的估計數(shù)為2，這是因為ISODATA算法可以自動低分裂和合并，對于類別較多的樣本而言，可以通過IGS方法對其進行細分類。

圖2 Glass數(shù)據(jù)集中Gap和IGap隨聚類數(shù)的變化曲線Fig.2 Glass data set Gap and IGap change curve with the number of clusters

對于Haberman數(shù)據(jù)集，ISODATA算法選取的參數(shù)為θN=5，θS=15，θC=0.1，L=2，I=100。由圖3可知，通過GS方法得到的最佳估計數(shù)為3，通過IGS得到的最佳估計數(shù)為2，IGS得到的聚類數(shù)較為準確。由于ISODATA算法較K-means算法而言，初始中心的選取對ISODATA算法的影響不大[16]，而且該算法能夠?qū)崿F(xiàn)自動分裂與合并，可以看出可準確地將Iris數(shù)據(jù)集分為3類。

圖3 Haberman數(shù)據(jù)集中Gap和IGap隨聚類數(shù)的變化曲線Fig.3 Haberman data set Gap and IGap change Curve with the number of clusters

對于Ionosphere數(shù)據(jù)集，ISODATA算法選取的參數(shù)為θN=10，θS=0.9，θC=3，L=2，I=100。由圖4可知，通過GS方法得到的最佳聚類數(shù)為3，而通過IGS方法可以將Ionosphere數(shù)據(jù)集準確地分為2類。

圖4 Ionosphere數(shù)據(jù)集中Gap和IGap隨聚類數(shù)的變化曲線Fig.4 Ionosphere data set Gap and IGap change Curve with the number of clusters

4 IGS模型與傳統(tǒng)GS模型性能比較

實驗采用2種評價指標(biāo)對聚類結(jié)果進行評價：對表1中4個數(shù)據(jù)集，分別利用GS和IGS重復(fù)運行50次，估計出最佳聚類數(shù)的正確率p，算法運行時間t。

從表2中可以看出，IGS方法和GS方法對數(shù)據(jù)集聚類所用的時間差不多，但是通過表3發(fā)現(xiàn)IGS方法估計數(shù)據(jù)集最佳聚類數(shù)的準確率比傳統(tǒng)GS方法要高，改進后的算法較好。

表2 數(shù)據(jù)集聚類所用的時間

表3 數(shù)據(jù)集最佳聚類數(shù)估計的準確率

5 結(jié) 論

對傳統(tǒng)的GS模型進行改進，提出了IGS模型，運用IGS模型對數(shù)據(jù)集進行聚類，IGS方法可以實現(xiàn)對數(shù)據(jù)集的細分類。實證表明，通過IGS方法估計數(shù)據(jù)集最佳聚類數(shù)準確率比較高。

[1] TIBSHIRANI R, WALTHER G, HASTIE T. Estimating the Number of Clusters in a Data Set via the Gap Statistic[J]. Journal of the Royal Statistical Society, 2000, 63(2):411-423

[2] LAJBCYGIER P, ONG M Y. Estimating the Number of Mutual Fund Styles Using the Generalized Style Classification Approach and the GAP Statistic[C]//Computational Intelligence for Financial Engineering, Hong Kong, China, 2003

[3] 黃陳蓉, 張正軍, 吳慧中. 圖像邊緣檢測的多尺度灰度Gap統(tǒng)計模型[J]. 中國圖像圖形學(xué)報, 2005, 10(8):1018-1023

HUANG C R, ZHANG Z J, WU H Z. Multiscale Gray Scale Gap Statistical Model for Image Edge Detection[J].Chinese Journal of Image and Graphics,2005, 10(8):1018-1023

[4] 李娜. 基于GS方法的圖像最佳分割的研究[D]. 南京:南京理工大學(xué), 2006.

LI N.Research on image Segmentation Based on GS Method[D].Nanjing: Nanjing University of Science and Technology,2006

[5] YAN M, YE K. Determining the Number of Clusters Using the Weighted Gap Statistic[J]. Biometrics, 2007, 63(4):1031-1037

[6] YUE S H, WANG X X, WEI M M. Application of Two-Order Difference to Gap Statistic[J]. Transactions of Tianjin University, 2008, 14(3):217-221

[7] SENTELLE C, HONG S L, GEORGIOPOULOS M, et al. A Fuzzy Gap Statistic for Fuzzy C-Means[C]// Proceedings of the Eleventh IASTED International Conference on Artificial Intelligence and Soft Computing. ACTA Press, 2007

[8] ARIMA C, HAKAMADA K, OKAMOTO M, et al. Modified Fuzzy Gap Statistic for Estimating Preferable Number of Clusters in Fuzzy K-means Clustering.[J]. Journal of Bioscience & Bioengineering, 2008, 105(3):273-281

[9] 童波. 基于MFGS方法圖像最佳分割數(shù)的研究[D]. 南京: 南京理工大學(xué), 2011

TONG B.Research on the Optimal Number of Image Segmentation Based on MFGS Method[D]. Nanjing: Nanjing University of Science and Technology,2011

[10] 劉倩. 基于GS方法的圖像分割估計數(shù)的多信息動態(tài)研究[D]. 南京: 南京理工大學(xué), 2013

LIU Q.Research on Information Dynamic Estimation of the Number of Image Segmentation Based on GS Method[D]. Nanjing: Nanjing University of Science and Technology,2013

[11] 李前進, 王寅龍, 李志祥,等. 基于直覺模糊的ISODATA算法[J]. 計算機工程與應(yīng)用, 2012, 48(9):176-177

LI Q J,WANG Y L,LI Z X, et al. ISODATA Algorithm based on Intuitionistic Fuzzy[J].Computer Engineering and Applications,2012, 48(9):176-177

[12] 萬建, 王繼成. 基于ISODATA算法的彩色圖像分割[J]. 計算機工程, 2002, 28(5):135-136

WAN J,WANG J C.Color Image Segmentation Based on ISODATA Algorithm[J].Computer Engineering,2002, 28(5):135-136

[13] 康永輝, 戴激光, 王廣哲. 改進的自適應(yīng)模糊ISODATA灰度圖像分割算法[J]. 計算機工程與應(yīng)用, 2016, 52(17):198-202

KANG Y H,DAI J G,WANG G Z.An Improved Adaptive Fuzzy ISODATA Algorithm for Image Segmentation[J].Computer Engineering and Applications,2016, 52(17):198-202

[14] 張麗娜, 姜新華, 那日蘇. 基于改進的ISODATA算法的大樣本數(shù)據(jù)聚類方法研究[J]. 內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(自然科學(xué)版), 2013, 34(1):133-137

ZHANG L N,JIANG X H,NA R F.Research on Large Sample Data Clustering Method Based on Improved ISODATA Algorithm[J].Journal of Inner Mongolia Agricultural University (Natural Science Edition), 2013, 34(1):133-137

[15] 黃健元. 模糊ISODATA聚類分析方法的改進[J]. 南京航空航天大學(xué)學(xué)報, 2000, 32(2):179-183.

HUANG J Y.Improvement of Fuzzy ISODATA Clustering Analysis[J].Journal of Nanjing University of Aeronautics and Astronautics, 2000, 32(2):179-183

[16] 陳平生. K-means和ISODATA聚類算法的比較研究[J]. 江西理工大學(xué)學(xué)報, 2012, 33(1):78-82

CHEN P S.Comparative Study of K-means and ISODATA Clustering Algorithms[J].Journal of Jiangxi University of Science and Technology, 2012, 33(1):78-82

Research on the Optimal Number of Classification Based on IGS Method

DOUTing,ZHANGZheng-jun

(School of Science, Nanjing University of Science and Technology, Nanjing 210094, China)

According to the problem that Gap Statistics (GS) method can get rough classification of data sets and can not get the fine classification of data sets, this paper improves GS method by introducing Gap statistic into ISODATA algorithm and proposes IGS model. Empirical research indicates that IGS model can not only realize the fine classification of data but also can estimate the optimal number of classification of the data sets through IGS model whose accuracy is obviously higher than original GS model.

Gap Statistics; IGS model; cluster number; ISODATA algorithm

TP314

A

2017-04-25；

2017-06-03.

面向云存儲的密文訪問控制理論研究(BK20141405).

竇婷(1990-)，女，江蘇徐州人，碩士研究生，從事數(shù)據(jù)挖掘與處理研究.

**通訊作者：張正軍(1965-)，男，江蘇阜寧人，副教授，從事數(shù)據(jù)科學(xué)與統(tǒng)計方法、數(shù)據(jù)挖掘與處理研究.

責(zé)任編輯：羅姍姍