蘇　婷，于　洪重慶郵電大學 計算智能重慶市重點實驗室，重慶 400065

?

基于q近鄰的不完備數(shù)據(jù)三支決策聚類方法*

蘇婷，于洪+
重慶郵電大學 計算智能重慶市重點實驗室，重慶 400065

SU Ting,YU Hong.Three-way decision clustering algorithm for incomplete data based on q-nearest neighbors.Journal of Frontiers of Computer Science and Technology,2016,10(6):875-883.

CNKI網(wǎng)絡優(yōu)先出版:2015-09-28,http://www.cnki.net/kcms/detail/11.5602.TP.20150928.1712.010.html

摘要：聚類是數(shù)據(jù)挖掘的重要技術之一，在許多實際應用領域，由于數(shù)據(jù)獲取限制，數(shù)據(jù)誤讀，隨機噪音等原因會造成大量的缺失數(shù)據(jù)，形成數(shù)據(jù)集的不完備性，而傳統(tǒng)的聚類方法無法直接對這類數(shù)據(jù)集進行聚類分析。針對數(shù)值型數(shù)據(jù)，提出了一個基于三支決策的不完備數(shù)據(jù)聚類方法。首先找到不完備數(shù)據(jù)對象的q個近鄰，使用q個近鄰的平均值填充缺失的數(shù)據(jù)；然后在“完備的”數(shù)據(jù)集上使用基于密度峰值的聚類方法得到簇劃分，對每個簇中含有不確定性的數(shù)據(jù)對象，使用三支決策的思想將其劃分到邊界域中。三支決策聚類結(jié)果采用區(qū)間集形式表示，通常一個簇被劃分成正域、負域和邊界域部分，可以更好地描述軟聚類結(jié)果。在UCI數(shù)據(jù)集和人工數(shù)據(jù)集上的實驗結(jié)果展示了算法的有效性。

關鍵詞：不完備數(shù)據(jù)；三支決策聚類；q近鄰

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0875-09

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

聚類是數(shù)據(jù)挖掘與機器學習中一個重要的研究領域，在商務智能、圖像識別、生物學等領域中有廣泛的應用[1]。然而，由于數(shù)據(jù)獲取限制，數(shù)據(jù)誤讀，隨機噪音等原因會造成大量的缺失數(shù)據(jù)，這些缺失的數(shù)據(jù)給數(shù)據(jù)分析帶來了巨大的困難。例如，在商業(yè)數(shù)據(jù)庫中，一些涉及隱私的數(shù)據(jù)，比如收入和年齡等，顧客不愿意將這些數(shù)據(jù)提供給商場，這就造成了某些商業(yè)數(shù)據(jù)的缺失，重新獲取這些數(shù)據(jù)需要花費較高的代價甚至沒有辦法獲取。作為機器學習領域基準數(shù)據(jù)庫的UCI數(shù)據(jù)集中超過40%的數(shù)據(jù)庫都含有缺失數(shù)據(jù)。這種缺失某些數(shù)據(jù)值的數(shù)據(jù)集，一般稱為不完備數(shù)據(jù)集。一般而言有3種數(shù)據(jù)缺失機制，根據(jù)Rubin等人[2-3]的分類法，數(shù)據(jù)的缺失機制被分為完全的隨機缺失（missing completely at random）、隨機缺失（missing at random）和不隨機缺失（not missing at random）。由于數(shù)據(jù)的缺失，傳統(tǒng)的聚類算法不能直接使用在不完備數(shù)據(jù)集上，因此對不完備數(shù)據(jù)進行聚類的問題是聚類分析研究中一個具有挑戰(zhàn)且不容忽視的難題。

為了解決不完備數(shù)據(jù)的聚類問題，許多新的聚類策略在已有聚類方法的基礎上被提出。Hathaway 和Bezdek[4]在模糊C均值聚類（fuzzy C-means，F(xiàn)CM）算法的基礎上提出了4種具體的不完備數(shù)據(jù)聚類方法：完整數(shù)據(jù)策略（whole-data strategy）、部分距離策略（partial distance strategy）、最優(yōu)填補策略（optimal completion strategy）和最近簇中心策略（nearest prototype strategy）。Sarkar等人[5]提出距離估計策略（distance estimation strategy）的模糊C均值方法，認為在計算隸屬度時得到不完備數(shù)據(jù)對象與簇中心之間的距離要比得到缺失的屬性值更重要。Di Nuovo[6]將不完備數(shù)據(jù)的模糊C均值方法使用在心理學研究數(shù)據(jù)集中。Aydilek等人[7]提出了一種支持向量機和遺傳算法混合的方法來估計缺失數(shù)據(jù)和最優(yōu)化FCM算法中的參數(shù)。為了充分利用類簇分布和數(shù)據(jù)集信息來處理不完備數(shù)據(jù)，Himmelspach等人[8]考慮了簇分散度，基于簇分散度為缺失數(shù)據(jù)估值提出了一個新的隸屬度方法。

國內(nèi)學者也在模糊C均值聚類算法的基礎上，提出了幾種新的不完備數(shù)據(jù)的聚類方法。Jia等人[9]按照不完備數(shù)據(jù)集中數(shù)據(jù)的缺失率采用不同的聚類策略。Li等人[10]在OCS-FCM算法基礎上引入了權(quán)重的思想，算法可以同時得到聚類結(jié)果和屬性重要性。隨后文獻[11]將遺傳算法與FCM算法相結(jié)合，在得到最終聚類結(jié)果的同時得到對缺失屬性值的最佳估計值。

近年來，最近鄰方法被廣泛使用在不完備數(shù)據(jù)分析中。Doquire等人[12]使用基于互信息的最近鄰方法估計不完備的數(shù)據(jù)。Van Hulse等人[13]在完備數(shù)據(jù)以及被填充的不完備數(shù)據(jù)中尋找未填補的不完備數(shù)據(jù)的q個近鄰，最后使用近鄰的均值填補缺失的數(shù)據(jù)。Li等人在文獻[14]中使用區(qū)間的形式來估計缺失的屬性值，區(qū)間端點為不完備數(shù)據(jù)近鄰的最大和最小值，然后改進了FCM算法，使其運用在以區(qū)間形式表示的數(shù)據(jù)集上來得到聚類結(jié)果。

此外，除了模糊聚類算法外，還有其他方法用于不完備數(shù)據(jù)的聚類。文獻[15]將不完備數(shù)據(jù)填補后直接使用在近鄰傳播方法中獲得聚類結(jié)果。Abd-Allah等人[16]沒有直接對缺失的屬性值進行填補，而是提出了一種計算含有缺失屬性值的數(shù)據(jù)對象在任意一維上的相似度，然后將改進的相似度計算方法運用到Mean Shift算法上解決了不完備數(shù)據(jù)的聚類問題。在作者前期的工作中，考慮了屬性重要性和屬性的缺失情況，提出了一個基于三支決策的不完備數(shù)據(jù)聚類方法[17]。

在實際生活中，信息具有不確定性或不完整性。這直接導致無法做出決定：接受或拒絕。在這種情況下，人們常常不自覺地使用三支決策，即三支決策理論是傳統(tǒng)二支決策理論的擴展[18]。三支決策理論是在粗糙集和決策粗糙集研究中提出的，其主要目的是為粗糙集3個域提供合理的語義解釋。粗糙集模型的正域、負域和邊界域可以解釋為接受、拒絕和不承諾3種決策結(jié)果。

在已有的聚類研究中，一個數(shù)據(jù)對象確定地屬于一個簇或者不屬于一個簇，這是一個二支決策結(jié)果。一個類簇由兩個域組成，即正域和負域，正域中的數(shù)據(jù)對象確定屬于這個簇，負域中的數(shù)據(jù)對象確定不屬于這個類，通常使用一個單一的集合來表示一個簇。在三支決策聚類中，一個簇由3個區(qū)域組成，即正域、負域和邊界域，正域中的數(shù)據(jù)對象確定屬于這個簇，邊界域中的數(shù)據(jù)對象可能屬于這個簇，負域中的數(shù)據(jù)對象確定不屬于這個簇。Yao[18]概述了三支決策的理論，并指出可以在多值邏輯和集合論的推廣中描述和解釋三支決策，包括區(qū)間集、粗糙集、決策粗糙集、模糊集以及陰影集。因此，在前期的工作中，提出了使用區(qū)間集[19]來表示三支決策聚類結(jié)果，使用一對稱為上界與下界的集合，來表示一個類簇。屬于下界的對象表示其確定屬于類簇；不屬于上界的對象表示其確定不屬于類簇，屬于上界與下界之間的對象表示其可能屬于類簇[20]。

不完備數(shù)據(jù)本身具有一定的不確定性，缺少有效的決策信息，因此將三支決策思想使用在不完備數(shù)據(jù)的聚類中是合理的。針對數(shù)值型數(shù)據(jù)，本文提出了一個基于q近鄰的不完備數(shù)據(jù)三支決策聚類方法。本文后續(xù)部分組織如下：第2章介紹相關理論；第3章是對聚類算法的詳細介紹；第4章通過在UCI數(shù)據(jù)集及人工數(shù)據(jù)集上的實驗展示算法的性能；第5章是結(jié)論與對未來工作的展望。

2　基本理論

下面首先定義本文的研究對象，即不完備信息系統(tǒng)，然后給出三支決策聚類結(jié)果的區(qū)間集描述方法，最后對新算法中使用的基于密度峰值的方法[21]進行簡要介紹。

2.1不完備信息系統(tǒng)

2.2聚類的區(qū)間集表示

根據(jù)以上類簇的表示方法，可以得到聚類結(jié)果的區(qū)間集描述形式如下：

在使用區(qū)間集表示聚類結(jié)果時，區(qū)間集滿足一些重要性質(zhì)：

性質(zhì)（1）表明任何一個類簇不能為空；為了使類簇具有物理含義，性質(zhì)（2）表明全集U的任何一個數(shù)據(jù)對象至少在一個簇的上界中。

2.3基于密度峰值的快速聚類方法

基于密度峰值的聚類方法是近期發(fā)表在Science上的文章[21]，該算法的基本思想非常的新穎而簡單，為聚類算法的設計提供了一種新的思路。

算法基于這樣的假設：類簇中心被具有較低局部密度的鄰居點包圍，且與更高密度點之間的距離相對較大，也就是說簇中心的密度大，并且簇中心點之間的距離大。通過這個簡單的假設，可以找到類簇中心。因此，為了尋找類簇中心，對于每一個數(shù)據(jù)點xi，需要計算兩個量，即點的局部密度ρi和該點到具有更高局部密度的點的最近距離δi，而這兩個值都取決于數(shù)據(jù)點間的距離Dist(xi,xj)，具體定義如下。

定義1（局部密度）數(shù)據(jù)對象xi的局部密度ρi是與xi的距離小于截斷距離閾值的點的個數(shù)，計算公式如下：

其中，當x<0時，χ(x)=1，否則χ(x)=0；dc為截斷距離，文中dc選取的是經(jīng)驗值。

定義2（數(shù)據(jù)對象與高密度點的最小距離）數(shù)據(jù)對象xi與所有密度更高點之間距離的最小值為δi，具體計算公式如下：

當數(shù)據(jù)對象xi的密度最大時，距離δi是對象xi與數(shù)據(jù)集中其他對象之間距離的最大值，即 δi=

得到類簇中心后，其他非簇中心的樣本點依據(jù)局部密度從高到低排列，并依次劃分它們到距離最近且密度更高的樣本點所屬的類別中。

3　基于q近鄰的不完備數(shù)據(jù)三支決策聚類算法

本文首先采用基于q近鄰的方法對不完備數(shù)據(jù)集中缺失的數(shù)據(jù)進行填充；然后在“完備”的數(shù)據(jù)集上使用基于密度峰值的聚類方法得到初步的聚類結(jié)果。通過以上過程大部分的數(shù)據(jù)會被正確地劃分，而處在類簇邊緣部分的數(shù)據(jù)對象的歸屬可能存在一定的不確定性，因此接下來使用三支決策的方法對每個簇中的數(shù)據(jù)對象進行分析，將含有不確定性的數(shù)據(jù)對象劃分到邊界域中。

3.1基于q近鄰的不完備數(shù)據(jù)填充方法

最近鄰（nearest neighbor，NN）規(guī)則已廣泛應用于模式識別領域的不完備數(shù)據(jù)估算中。數(shù)據(jù)對象與其q個近鄰具有很高的相似性，同樣不完備數(shù)據(jù)對象與其近鄰數(shù)據(jù)對象應具有相同或相似的屬性值，因此可以將這一思想使用在不完備數(shù)據(jù)的填充中，利用q個鄰居的屬性值得到缺失數(shù)據(jù)的合理估值。選擇數(shù)據(jù)對象的q個最近鄰居要比只選擇最近的數(shù)據(jù)對象更具有魯棒性。

基于q近鄰的不完備數(shù)據(jù)填充方法使用不完備數(shù)據(jù)對象的q個近鄰的平均值填充缺失的屬性值。因此首先需要找到不完備數(shù)據(jù)對象的q個近鄰，然而由于一些屬性值的缺失，不完備數(shù)據(jù)對象之間的距離不能使用傳統(tǒng)的歐氏距離公式計算得到。本文使用局部歐氏距離公式進行計算[4]，該公式只使用兩個數(shù)據(jù)對象均沒有缺失的那些屬性來計算它們之間的距離，具體公式如下：

當找到不完備數(shù)據(jù)的q個近鄰后，缺失的數(shù)據(jù)可以由沒有缺失該屬性值的近鄰數(shù)據(jù)對象的平均值求得?？赡軙霈F(xiàn)極端情況，即q個近鄰在某一維屬性的數(shù)據(jù)全部缺失，無法對缺失的數(shù)據(jù)進行填補時，則使用隨機數(shù)進行填補。然而，對于隨機缺失的數(shù)據(jù)集，這種情況幾乎不會發(fā)生。

3.2三支決策聚類

經(jīng)過填充后“完備”的數(shù)據(jù)對象可以由基于密度峰值的聚類算法得到聚類結(jié)果，但是由于不完備數(shù)據(jù)本身的不確定性，以及對缺失數(shù)據(jù)估值可能帶來的不確定性，會造成一些數(shù)據(jù)對象成為噪聲點，同時還有一些數(shù)據(jù)對象可能處在類簇的邊緣部分，對它們進行確定的劃分會給聚類帶來一定的誤差。

根據(jù)以上分析，利用三支決策的思想對聚類結(jié)果進行分析，將含有不確定性的數(shù)據(jù)對象劃分到相應簇的邊界域部分。劃分思想是類簇的邊界部分數(shù)據(jù)對象的密度要小于簇內(nèi)部數(shù)據(jù)對象的密度。具體的分析方法是，首先計算每個簇中數(shù)據(jù)對象的平均密度，對于密度小于平均值的數(shù)據(jù)對象，如果它的截斷距離dc范圍中含有屬于其他簇的數(shù)據(jù)對象，則將該數(shù)據(jù)對象劃分到該簇的邊界域部分。

形式化表示是，首先計算類簇Ci的平均密度-ρi，計算公式如下：

3.3算法流程

基于q近鄰的不完備數(shù)據(jù)三支決策聚類方法描述如下：

輸入：不完備數(shù)據(jù)集U={x1,x2,…,xn,…,xN}，近鄰個數(shù)q，閾值dc，類簇個數(shù)K。

輸出：三支決策聚類結(jié)果。

步驟1找到每個不完備數(shù)據(jù)對象的q個近鄰；

步驟2使用近鄰中不缺失屬性值的平均值填充不完備數(shù)據(jù)相應屬性上的缺失值；

步驟3按照2.3節(jié)介紹的方法，計算每個數(shù)據(jù)對象的局部密度ρi和距離δi，并找到K個簇中心；

步驟4每個非簇中心的數(shù)據(jù)對象，按照局部密度從高到低的順序，依次劃分它們到距離最近的更高密度樣本點所屬的類中；

步驟5將每個簇中局部密度小于簇的平均密度并且近鄰中包含其他簇對象的數(shù)據(jù)對象劃分到相應簇的邊界域部分，得到最終的三支決策聚類結(jié)果。

4　實驗分析

本文將給出在人工數(shù)據(jù)集和UCI數(shù)據(jù)集[22]上的實驗結(jié)果來驗證算法的性能。不完備數(shù)據(jù)集必須滿足以下條件：（1）數(shù)據(jù)集中每個數(shù)據(jù)對象至少有一個屬性值；（2）數(shù)據(jù)集中任何一個屬性都必須有至少一個完整的值。以上條件確保了數(shù)據(jù)集中每一個數(shù)據(jù)對象以及所有的屬性值是有意義的。

設λ={λ1,λ2,…,λk,…,λK}是數(shù)據(jù)集真實的聚類結(jié)果，C={C1,C2,…,Ck,…,CK}是本文方法得出的聚類結(jié)果。準確率將用來評估聚類結(jié)果的質(zhì)量。設θk是簇Ck中正確劃分的數(shù)據(jù)對象的個數(shù)，其中包括正確劃分的邊界域的數(shù)據(jù)對象，則聚類結(jié)果的準確率計算公式如下：

其中，N是數(shù)據(jù)對象的總數(shù)；K是類簇的個數(shù)。準確率與聚類結(jié)果的質(zhì)量成正比。

實驗1首先用一個二維人工數(shù)據(jù)集Aggregation來直觀地展示算法的效果，該數(shù)據(jù)集包含788個數(shù)據(jù)對象，7個類。數(shù)據(jù)集按照5%、10%的缺失率隨機產(chǎn)生缺失數(shù)據(jù)。在隨機缺失的數(shù)據(jù)集上運行本文方法，近鄰個數(shù)q=10，dc=2。圖1是原始Aggregation數(shù)據(jù)集；圖2是當Aggregation數(shù)據(jù)集含有5%的缺失數(shù)據(jù)時，使用本文方法對缺失數(shù)據(jù)填充后的聚類結(jié)果；圖3是當Aggregation數(shù)據(jù)集含有10%的缺失數(shù)據(jù)時，使用本文方法對缺失數(shù)據(jù)填充后的聚類結(jié)果。圖2和圖3中，使用不同的標記將每個類簇中邊界域的數(shù)據(jù)對象與正域的對象進行區(qū)分。

Fig.1　Original dataset ofAggregation圖1　Aggregation數(shù)據(jù)集

Fig.2　Clustering result ofAggregation with 5%missing圖2　Aggregation數(shù)據(jù)集缺失率為5%的聚類結(jié)果

通過觀察圖2和圖3，當數(shù)據(jù)集含有5%和10%的缺失數(shù)據(jù)時，數(shù)據(jù)集中的數(shù)據(jù)對象可以較為準確地被劃分到所屬的簇中，并且算法可以較好地識別出位于邊界域中的數(shù)據(jù)對象，填充后數(shù)據(jù)的分布基本沒有大的變化，只有少量數(shù)據(jù)對象填充不正確。因此，實驗1說明本文方法對不完備數(shù)據(jù)聚類是有效的，大多數(shù)缺失數(shù)據(jù)能夠被近似地填充，并被正確劃分到相應的簇中。同時，本文方法可以將本身位于簇的邊界和少量沒有被正確填充的數(shù)據(jù)對象劃分到簇的邊界域部分。

Fig.3 Clustering result ofAggregation with 10%missing圖3　Aggregation數(shù)據(jù)集缺失率為10%的聚類結(jié)果

實驗2此外，為了進一步驗證本文方法的性能，在UCI數(shù)據(jù)集和人工數(shù)據(jù)集上使用準確率和運行時間對算法進行評估，并與文獻[4]中的OCS-FCM方法進行對比。文獻[4]是不完備數(shù)據(jù)聚類問題研究中較為經(jīng)典的文獻，目前大多數(shù)基于模糊C均值的不完備數(shù)據(jù)聚類方法都是在文獻[4]的基礎上得到的。表1給出了這些數(shù)據(jù)集的大小、屬性個數(shù)和類簇個數(shù)。

Table 1　Data sets used in experiment表1　實驗中使用的數(shù)據(jù)集

在實驗中，首先對數(shù)據(jù)集按照5%、10%、15%和20%的缺失率隨機生成缺失數(shù)據(jù)構(gòu)造不完備數(shù)據(jù)集，每個缺失率下都對應生成10個不同的不完備數(shù)據(jù)集，以避免缺失數(shù)據(jù)的分布情況對算法性能的影響。實驗參數(shù)dc選擇經(jīng)驗值，數(shù)據(jù)對象的近鄰個數(shù)選擇經(jīng)驗值q=10，將數(shù)據(jù)集在每個缺失率下的10組實驗結(jié)果的準確率以及運行時間的平均值和方差記錄在表2中。

從表2中記錄的實驗結(jié)果可以看出，除了Iris數(shù)據(jù)集缺失率為10%和20%時的情況，本文方法的準確率均要高于對比方法。分析后不難發(fā)現(xiàn)：對比方法是基于模糊C均值的方法，易受到初始簇中心的影響，并且在非球形分布的數(shù)據(jù)集上難以取得較好的結(jié)果；本文基于密度的聚類方法能夠處理任意形狀的簇結(jié)構(gòu)。因此，本文方法的準確率高于對比方法。同時，在Page blocks數(shù)據(jù)集上，本文方法的準確率要明顯高于對比方法，通過分析數(shù)據(jù)集的數(shù)據(jù)分布情況，發(fā)現(xiàn)Page blocks數(shù)據(jù)集不同簇中數(shù)據(jù)對象的個數(shù)相差很大，因此該實驗結(jié)果還可以說明本文方法在簇中數(shù)據(jù)對象的個數(shù)相差很大時可以取得較好的效果。在大多數(shù)情況下，當數(shù)據(jù)集中數(shù)據(jù)的缺失率越高時，聚類結(jié)果的準確率越低。因為缺失率越高，近鄰信息的可靠性下降，不完備數(shù)據(jù)填充的準確度也會下降，直接導致了聚類算法性能下降。表2的實驗結(jié)果還說明本文方法的運行時間要高于對比方法，需要在今后的工作中改進。

Table 2　Experiment results on synthetic and UCI data sets表2　人工數(shù)據(jù)集和UCI數(shù)據(jù)集上的實驗結(jié)果

5　結(jié)束語

本文提出了一種基于q近鄰的不完備數(shù)據(jù)三支決策聚類方法。方法使用不完備數(shù)據(jù)的q個近鄰的平均值填充缺失的數(shù)據(jù)，然后使用基于密度峰值的聚類方法在“完備”的數(shù)據(jù)集上得到聚類結(jié)果，最后使用三支決策方法將每個簇中具有不確定性的數(shù)據(jù)對象劃分到相應簇的邊界域部分。本文方法的準確率較好，但運行時間較長，并且存在一些不足之處，例如如何較好地選擇q值，當數(shù)據(jù)集的缺失率較高時，q近鄰填充方法性能下降，在今后的工作中會逐步完善這些缺陷。

References:

[1]Jain A K.Data clustering:50 years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[2]Rubin D B.Inference and missing data[J].Biometrika, 1976,63(3):581-592.

[3]Little R J A,Rubin D B.Statistical analysis with missing data[M].Hoboken,USA:John Wiley&Sons,2014.

[4]Hathaway R J,Bezdek J C.Fuzzy C-means clustering of incomplete data[J].IEEE Transactions on Systems,Man,and Cybernetics:Part B Cybernetics,2001,31(5):735-744.

[5]Sarkar M,Leong T Y.Fuzzy K-means clustering with missing values[C]//Proceedings of the American Medical Informatics Association Symposium.Bethesda,USA:AMIA,2001: 588-592.

[6]Di Nuovo A G.Missing data analysis with fuzzy C-means: a study of its application in a psychological scenario[J].Expert Systems withApplications,2011,38(6):6793-6797.

[7]Aydilek I B,Arslan A.A hybrid method for imputation of missing values using optimized fuzzy C-means with support vector regression and a genetic algorithm[J].Information Sciences,2013,233:25-35.

[8]Himmelspach L,Conrad S.Fuzzy clustering of incomplete data based on cluster dispersion[C]//LNCS 6178:Computational Intelligence for Knowledge-Based Systems Design, Proceedings of the 13th International Conference on Information Processing and Management of Uncertainty,Dortmund,Germany,Jun 28-Jul 2,2010.Berlin,Heidelberg: Springer,2010:59-68.

[9]Jia Zhiping,Yu Zhiqiang,Zhang Chenghui.Fuzzy C-means clustering algorithm based on incomplete data[C]//Procee dings of the 2006 International Conference on Information Acquisition,Weihai,China,Aug 20-23,2006.Piscataway, USA:IEEE,2006:601-604.

[10]Li Dan,Zhong Chongquan,Li Jinhua.An attribute weighted fuzzy C-means algorithm for incomplete data sets[C]//Proceedings of the 2012 International Conference on System Science and Engineering.Dalian,China,Jun 30-Jul 2, 2012.Piscataway,USA:IEEE,2012:449-453.

[11]Li Dan,Gu Hong,Zhang Liyong.Ahybrid genetic algorithmfuzzy C-means approach for incomplete data clustering based on nearest-neighbor intervals[J].Soft Computing,2013,17 (10):1787-1796.

[12]Doquire G,Verleysen M.Feature selection with missing data using mutual information estimators[J].Neurocomputing, 2012,90:3-11.

[13]Van Hulse J,Khoshgoftaar T M.Incomplete-case nearest neighbor imputation in software measurement data[J].Information Sciences,2014,259:596-610.

[14]Li Dan,Gu Hong,Zhang Liyong.A fuzzy C-means clustering algorithm based on nearest-neighbor intervals for incomplete data[J].Expert Systems with Applications,2010,37 (10):6942-6947.

[15]Lu Cheng,Song Shiji,Wu Cheng.Affinity propagation clustering with incomplete data[C]//Computational Intelligence, Networked Systems and Their Applications:Proceedings of the International Conference of Life System Modeling and Simulation,and International Conference on Intelligent ComputingforSustainableEnergyandEnvironment, Shanghai,China,Sep 20-23,2014.Berlin,Heidelberg: Springer,2014:239-248.

[16]AbdAllah L,Shimshoni I.Mean shift clustering algorithm for data with missing values[C]//LNCS 8646:Proceedingsof the 16th International Conference on Data Warehousing and Knowledge Discovery,Munich,Germany,Sep 2-4,2014. Berlin,Heidelberg:Springer,2014:426-438.

[17]Yu Hong,Su Ting,Zeng Xianhua.A three-way decisions clustering algorithm for incomplete data[C]//LNCS 8818: Proceedings of the 9th International Conference on Rough Sets and Knowledge Technology,Shanghai,China,Oct 24-26,2014.Berlin,Heidelberg:Springer,2014:765-776.

[18]Yao Yiyu.An outline of a theory of three-way decisions[C]// LNCS 7413:Proceedings of the 8th International Conference on Rough Sets and Current Trends in Computing, Chengdu,China,Aug 17-20,2012.Berlin,Heidelberg:Springer,2012:1-17.

[19]Yao Yiyu,Lingras P,Wang Ruizhi,et al.Interval set cluster analysis:a re-formulation[C]//LNCS 5908:Proceedings of the 12th International Conference on Rough Sets,Fuzzy Sets,Data Mining and Granular Computing,Delhi,India, Dec 15-18,2009.Berlin,Heidelberg:Springer,2009:398-405.

[20]Yu Hong,Wang Ying.Three-way decisions method for overlapping clustering[C]//LNCS 7413:Proceedings of the 8th International Conference on Rough Sets and Current Trends in Computing,Chengdu,China,Aug 17-20,2012. Berlin,Heidelberg:Springer,2012:277-286.

[21]Alex R,Alessandro L.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[22]UCI machine learning repository[EB/OL].[2015-05-16]. http://archive.ics.uci.edu/ml/.

SU Ting was born in 1990.She is an M.S.candidate at Chongqing University of Posts and Telecommunications. Her research interests include data mining and three-way decision theory.

蘇婷（1990—），女，新疆伊寧人，重慶郵電大學碩士研究生，主要研究領域為數(shù)據(jù)挖掘，三支決策理論。

YU Hong was born in 1972.She received the Ph.D.degree from Chongqing University in 2003.Now she is a professor at Chongqing University of Posts and Telecommunications,and the member of CCF.Her research interests include rough sets,three-way decisions,intelligence information processing,Web intelligence and data mining.

于洪（1972—），女，重慶人，2003年于重慶大學獲得博士學位，現(xiàn)為重慶郵電大學教授，CCF會員，主要研究領域為Rough Sets理論，三支決策理論，智能信息處理，Web智能，數(shù)據(jù)挖掘。

+Corresponding author:E-mail:yuhong@cqupt.edu.cn

文獻標志碼：A

中圖分類號：TP181.1

doi:10.3778/j.issn.1673-9418.1506050

Three-Way Decision Clustering Algorithm for Incomplete Data Based on q-Nearest Neighbors*

SU Ting,YU Hong+
Chongqing Key Laboratory of Computational Intelligence,Chongqing University of Posts and Telecommunications,
Chongqing 400065,China

Abstract:Clustering is a common technique for data analysis,and has been widely used in many practical areas. However,in many practical applications,there are some reasons to cause the missing values in real data sets such as difficulties and limitations of data acquisition and random noises.Most of clustering methods can’t be used to deal with incomplete data sets for clustering analysis directly.For this reason,this paper proposes a three-way decision clustering algorithm for incomplete data based on q-nearest neighbors.Firstly,the algorithm finds the q-nearest neighbors for an object with missing values,and the missing value is filled by the average value of q-nearest neighbors. Secondly,it uses the clustering method based on density peaks for the complete data set to obtain the clustering result.For the data object with uncertainty in each cluster,it is designed to the boundary region of a cluster using the three-way decision theory.The three-way decision with interval sets naturally partitions a cluster into three regions as the positive region,boundary region and negative region,which has the advantage of dealing with soft clustering. The experimental results on some UCI data sets and synthetic data sets show preliminarily the effectiveness of the proposed algorithm.

Key words:incomplete data;three-way decision clustering;q-nearest neighbors

*The National Natural Science Foundation of China under Grant Nos.61379114,61272060(國家自然科學基金). Received 2015-06,Accepted 2015-09.