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

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

?

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

蘇婷，于洪+
重慶郵電大學 計算智能重慶市重點實驗室，重慶 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網絡優先出版:2015-09-28,http://www.cnki.net/kcms/detail/11.5602.TP.20150928.1712.010.html

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

關鍵詞：不完備數據；三支決策聚類；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　引言

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

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

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

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

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

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

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

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

2　基本理論

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

2.1不完備信息系統

2.2聚類的區間集表示

根據以上類簇的表示方法，可以得到聚類結果的區間集描述形式如下：

在使用區間集表示聚類結果時，區間集滿足一些重要性質：

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

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

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

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

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

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

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

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

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

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

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

3.1基于q近鄰的不完備數據填充方法

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

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

當找到不完備數據的q個近鄰后，缺失的數據可以由沒有缺失該屬性值的近鄰數據對象的平均值求得。可能會出現極端情況，即q個近鄰在某一維屬性的數據全部缺失，無法對缺失的數據進行填補時，則使用隨機數進行填補。然而，對于隨機缺失的數據集，這種情況幾乎不會發生。

3.2三支決策聚類

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

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

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

3.3算法流程

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

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

輸出：三支決策聚類結果。

步驟1找到每個不完備數據對象的q個近鄰；

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

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

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

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

4　實驗分析

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

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

其中，N是數據對象的總數；K是類簇的個數。準確率與聚類結果的質量成正比。

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

Fig.1　Original dataset ofAggregation圖1　Aggregation數據集

Fig.2　Clustering result ofAggregation with 5%missing圖2　Aggregation數據集缺失率為5%的聚類結果

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

Fig.3 Clustering result ofAggregation with 10%missing圖3　Aggregation數據集缺失率為10%的聚類結果

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

Table 1　Data sets used in experiment表1　實驗中使用的數據集

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

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

Table 2　Experiment results on synthetic and UCI data sets表2　人工數據集和UCI數據集上的實驗結果

5　結束語

本文提出了一種基于q近鄰的不完備數據三支決策聚類方法。方法使用不完備數據的q個近鄰的平均值填充缺失的數據，然后使用基于密度峰值的聚類方法在“完備”的數據集上得到聚類結果，最后使用三支決策方法將每個簇中具有不確定性的數據對象劃分到相應簇的邊界域部分。本文方法的準確率較好，但運行時間較長，并且存在一些不足之處，例如如何較好地選擇q值，當數據集的缺失率較高時，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—），女，新疆伊寧人，重慶郵電大學碩士研究生，主要研究領域為數據挖掘，三支決策理論。

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年于重慶大學獲得博士學位，現為重慶郵電大學教授，CCF會員，主要研究領域為Rough Sets理論，三支決策理論，智能信息處理，Web智能，數據挖掘。

+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.