一種改進的粗糙集聚類算法

王一萍++孫明

摘要：針對傳統通聚類算法大都是研究非重疊、無法解決現實普遍存在的重疊聚類現象的問題，提出一種改進的粗糙k-means聚類算法。并將這Lingas提出的k-means聚類算法與本文算法應用到林業(yè)數據集中進行比較。測試結果證明，改進后的方法聚類效果較好，在整個范圍內都能提供有意義的結果。

關鍵詞：聚類 粗糙集 重疊

中圖分類號：TP313；G642.0 文獻標識碼：A 文章編號：1007-9416（2014）08-0134-02

聚類分析[1]屬非監(jiān)督性模式識別，是數據挖掘等領域廣泛應用算法，如商業(yè)、生物等行業(yè)。聚類是按某相似性度量法將有相似特征樣本歸為一類，使類內相似度大，類之間差異大。已有聚類算法大都是研究非重疊問題，但現實中重疊聚類現象很普通，如社會網絡中基于個人興趣、職業(yè)等聚集，很多人同屬幾個聚集；代謝網絡中基于功能聚集，有些蛋白質同屬幾個功能小組等。Steve Gregory提出模糊重疊聚類[6]，但事先需隸屬度函數確定每個數據屬于各個聚集，建立樣本對于類別不確定性的描述。Lingas等人提出了粗糙k-means算法，但邊界域中節(jié)點受初始設置閾值和重復因子影響較大，基于此，筆者通過改進的粗糙k-means來克服此缺點。

1 粗糙聚類算法

加拿大學者Lingas將RS理論[2]-[4]引入K-均值聚類，提出了RSK-均值算法。引入RS 的3條公理，（1）1個數據對象至多屬1個聚類和下近似；（2）屬1個聚類下近似成員同時也是這個聚類上近似成員；（3）如1個數據對象不隸屬于何1個聚類下近似，則它一定至少是2個聚類上近似成員。筆者采用的變量如下。

粗糙集聚類算法描述如下：

第1步：初始化，設置聚集數K和閾值。隨機分配k個數據對象作為聚集下近似對象，由上面公理3得這個對象也屬該聚集的上近似。然后將其余N-k個數據分配到1個離其最近的聚類中。

第2步：計算每個聚集新的質心。質心計算（均值函數）為公式（1）。

和是聚集下近似和邊界域的權重。

第3步：將數據對象分配到聚集的近似集中。對于Xn確定離它最近的質心，使用公式（2）將數據分配到聚集的上近似中。使用公式（3）確定質心，對于給定閾值，求集合T。

如果不空，則除距離很近外，距離T中任意t對應的也很近，則；否則，。

第4步：檢查算法的收斂性，即聚類是否變化。如果沒有收斂繼續(xù)第2步，否則算法結束。

2 改進的粗糙K-means算法

本文在Lingas提出的粗糙k-means算法上做了修改，使用相對閾值代替Lingas的K-means中的絕對閾值。算法步驟如下。

第1步：初始化。隨機分配每個數據到1個下近似中，由RS公理2得此數據也屬同一聚類上近似。

第2步：使用公式4計算每個聚集的新的均值。

第3步：為使每個聚集下近似至少有1個成員，即有：，由前公理2得，將每個數據對象分配到近似集中，1）最能代表1個集群的數據對象分配到它的上下近似中。

（1）計算所有對象與各個聚集的離，找到數據對象和聚集，使得距離聚集最近，則將數據分配到聚集的下近似和上近似中。計算過程中使用公式5：

（2）如果在（a）中有還有一些聚集沒有被分配到數據對象，即聚集的下近似為空，則返回（a）繼續(xù)將離每個聚集最近的1個數據分配到其下近似中，否則繼續(xù)第3）步。

（3）將剩余 N-k個數據對象，利用公式（2）確定離它最近的質心，將分配到聚集的上近似中。（3）確定是否有聚集，它的質心和的距離與和的距離的比在事先規(guī)定的閾值范圍內，即滿足公式（6）。

如不空，則說明除離近，距離中任何對應質心也很近，所以將分到聚集上近似中；否則，屬于的下近似。

第4步：檢查算法是否收斂，如不收斂，則繼續(xù)執(zhí)行第（3）步，否則結束。

3 實驗

對本文算法進行測試，與Lingas等人的算法在DBI結果進行比較。實驗中選擇wl=0.7、wu=0.3。

數據源來源于知識發(fā)現數據源網的林業(yè)數據，它描述30×30米區(qū)域森林覆蓋類型。有581012條記錄含54個屬性，10個數值變量，其余為二進制型，數值中有1個屬性描述7種森林植被類型（如云杉、楊木等）。對數據進行預處理，從中隨機選擇2345個記錄及10個數值屬性，設置集群數為7，表示森林覆蓋類型。數據歸一化為[0，1]。設重復因子r=50，imax=500。

聚類結果分析：Lingas等人算法選擇=0.0，…，0.0125時，提供了有意義結果，如圖1描述。圖中顯示邊界區(qū)數據對象對的依賴性。高的重復因子r對于較大值將導致穩(wěn)定最優(yōu)值，但算法所需時間顯著增加，同時算法收斂性也下降。相比之下，本文聚類算法在整個范圍內都能提供有意義的結果，邊界區(qū)域的對象數從0到2338（見圖2）。

一般改進的算法也表示DBI值略有改善，如圖3所示。值得注意是，Lingas算法對于邊界域中有大量數據對象時，由于大的使算法的收斂性降低。且重復因子r能導致更好DBI，但是以降低效率作為代價的。

4 結語

筆者提出一些方案。通過引入一個改進的粗糙k-means，在森林數據集上成功測試驗證了本文算法的有效性。

參考文獻

[1]聶舟，程遠國.一種基于平均相對偏差的聚類算法[J].兵工自動化，2008，27（8）：32-34.

[2]Pawlak Z.Rough Sets[J].Journal of Information and ComputerSciences，1982，11（5）：145-172.

[3]胡云，苗奪謙，王睿智等.一種基于粗糙k均值的雙聚類算法[J].計算機科學，2007，34（11）：174-177.

[4]鄭超，苗奪謙，王睿智.基于密度加權的粗糙k均值聚類改進算法[J].計算機科學，2009，36（3）：220-222.endprint

摘要：針對傳統通聚類算法大都是研究非重疊、無法解決現實普遍存在的重疊聚類現象的問題，提出一種改進的粗糙k-means聚類算法。并將這Lingas提出的k-means聚類算法與本文算法應用到林業(yè)數據集中進行比較。測試結果證明，改進后的方法聚類效果較好，在整個范圍內都能提供有意義的結果。

關鍵詞：聚類 粗糙集 重疊

中圖分類號：TP313；G642.0 文獻標識碼：A 文章編號：1007-9416（2014）08-0134-02

聚類分析[1]屬非監(jiān)督性模式識別，是數據挖掘等領域廣泛應用算法，如商業(yè)、生物等行業(yè)。聚類是按某相似性度量法將有相似特征樣本歸為一類，使類內相似度大，類之間差異大。已有聚類算法大都是研究非重疊問題，但現實中重疊聚類現象很普通，如社會網絡中基于個人興趣、職業(yè)等聚集，很多人同屬幾個聚集；代謝網絡中基于功能聚集，有些蛋白質同屬幾個功能小組等。Steve Gregory提出模糊重疊聚類[6]，但事先需隸屬度函數確定每個數據屬于各個聚集，建立樣本對于類別不確定性的描述。Lingas等人提出了粗糙k-means算法，但邊界域中節(jié)點受初始設置閾值和重復因子影響較大，基于此，筆者通過改進的粗糙k-means來克服此缺點。

1 粗糙聚類算法

加拿大學者Lingas將RS理論[2]-[4]引入K-均值聚類，提出了RSK-均值算法。引入RS 的3條公理，（1）1個數據對象至多屬1個聚類和下近似；（2）屬1個聚類下近似成員同時也是這個聚類上近似成員；（3）如1個數據對象不隸屬于何1個聚類下近似，則它一定至少是2個聚類上近似成員。筆者采用的變量如下。

粗糙集聚類算法描述如下：

第1步：初始化，設置聚集數K和閾值。隨機分配k個數據對象作為聚集下近似對象，由上面公理3得這個對象也屬該聚集的上近似。然后將其余N-k個數據分配到1個離其最近的聚類中。

第2步：計算每個聚集新的質心。質心計算（均值函數）為公式（1）。

和是聚集下近似和邊界域的權重。

第3步：將數據對象分配到聚集的近似集中。對于Xn確定離它最近的質心，使用公式（2）將數據分配到聚集的上近似中。使用公式（3）確定質心，對于給定閾值，求集合T。

如果不空，則除距離很近外，距離T中任意t對應的也很近，則；否則，。

第4步：檢查算法的收斂性，即聚類是否變化。如果沒有收斂繼續(xù)第2步，否則算法結束。

2 改進的粗糙K-means算法

本文在Lingas提出的粗糙k-means算法上做了修改，使用相對閾值代替Lingas的K-means中的絕對閾值。算法步驟如下。

第1步：初始化。隨機分配每個數據到1個下近似中，由RS公理2得此數據也屬同一聚類上近似。

第2步：使用公式4計算每個聚集的新的均值。

第3步：為使每個聚集下近似至少有1個成員，即有：，由前公理2得，將每個數據對象分配到近似集中，1）最能代表1個集群的數據對象分配到它的上下近似中。

（1）計算所有對象與各個聚集的離，找到數據對象和聚集，使得距離聚集最近，則將數據分配到聚集的下近似和上近似中。計算過程中使用公式5：

（2）如果在（a）中有還有一些聚集沒有被分配到數據對象，即聚集的下近似為空，則返回（a）繼續(xù)將離每個聚集最近的1個數據分配到其下近似中，否則繼續(xù)第3）步。

（3）將剩余 N-k個數據對象，利用公式（2）確定離它最近的質心，將分配到聚集的上近似中。（3）確定是否有聚集，它的質心和的距離與和的距離的比在事先規(guī)定的閾值范圍內，即滿足公式（6）。

如不空，則說明除離近，距離中任何對應質心也很近，所以將分到聚集上近似中；否則，屬于的下近似。

第4步：檢查算法是否收斂，如不收斂，則繼續(xù)執(zhí)行第（3）步，否則結束。

3 實驗

對本文算法進行測試，與Lingas等人的算法在DBI結果進行比較。實驗中選擇wl=0.7、wu=0.3。

數據源來源于知識發(fā)現數據源網的林業(yè)數據，它描述30×30米區(qū)域森林覆蓋類型。有581012條記錄含54個屬性，10個數值變量，其余為二進制型，數值中有1個屬性描述7種森林植被類型（如云杉、楊木等）。對數據進行預處理，從中隨機選擇2345個記錄及10個數值屬性，設置集群數為7，表示森林覆蓋類型。數據歸一化為[0，1]。設重復因子r=50，imax=500。

聚類結果分析：Lingas等人算法選擇=0.0，…，0.0125時，提供了有意義結果，如圖1描述。圖中顯示邊界區(qū)數據對象對的依賴性。高的重復因子r對于較大值將導致穩(wěn)定最優(yōu)值，但算法所需時間顯著增加，同時算法收斂性也下降。相比之下，本文聚類算法在整個范圍內都能提供有意義的結果，邊界區(qū)域的對象數從0到2338（見圖2）。

一般改進的算法也表示DBI值略有改善，如圖3所示。值得注意是，Lingas算法對于邊界域中有大量數據對象時，由于大的使算法的收斂性降低。且重復因子r能導致更好DBI，但是以降低效率作為代價的。

4 結語

筆者提出一些方案。通過引入一個改進的粗糙k-means，在森林數據集上成功測試驗證了本文算法的有效性。

參考文獻

[1]聶舟，程遠國.一種基于平均相對偏差的聚類算法[J].兵工自動化，2008，27（8）：32-34.

[2]Pawlak Z.Rough Sets[J].Journal of Information and ComputerSciences，1982，11（5）：145-172.

[3]胡云，苗奪謙，王睿智等.一種基于粗糙k均值的雙聚類算法[J].計算機科學，2007，34（11）：174-177.

[4]鄭超，苗奪謙，王睿智.基于密度加權的粗糙k均值聚類改進算法[J].計算機科學，2009，36（3）：220-222.endprint

摘要：針對傳統通聚類算法大都是研究非重疊、無法解決現實普遍存在的重疊聚類現象的問題，提出一種改進的粗糙k-means聚類算法。并將這Lingas提出的k-means聚類算法與本文算法應用到林業(yè)數據集中進行比較。測試結果證明，改進后的方法聚類效果較好，在整個范圍內都能提供有意義的結果。

關鍵詞：聚類 粗糙集 重疊

中圖分類號：TP313；G642.0 文獻標識碼：A 文章編號：1007-9416（2014）08-0134-02

聚類分析[1]屬非監(jiān)督性模式識別，是數據挖掘等領域廣泛應用算法，如商業(yè)、生物等行業(yè)。聚類是按某相似性度量法將有相似特征樣本歸為一類，使類內相似度大，類之間差異大。已有聚類算法大都是研究非重疊問題，但現實中重疊聚類現象很普通，如社會網絡中基于個人興趣、職業(yè)等聚集，很多人同屬幾個聚集；代謝網絡中基于功能聚集，有些蛋白質同屬幾個功能小組等。Steve Gregory提出模糊重疊聚類[6]，但事先需隸屬度函數確定每個數據屬于各個聚集，建立樣本對于類別不確定性的描述。Lingas等人提出了粗糙k-means算法，但邊界域中節(jié)點受初始設置閾值和重復因子影響較大，基于此，筆者通過改進的粗糙k-means來克服此缺點。

1 粗糙聚類算法

加拿大學者Lingas將RS理論[2]-[4]引入K-均值聚類，提出了RSK-均值算法。引入RS 的3條公理，（1）1個數據對象至多屬1個聚類和下近似；（2）屬1個聚類下近似成員同時也是這個聚類上近似成員；（3）如1個數據對象不隸屬于何1個聚類下近似，則它一定至少是2個聚類上近似成員。筆者采用的變量如下。

粗糙集聚類算法描述如下：

第1步：初始化，設置聚集數K和閾值。隨機分配k個數據對象作為聚集下近似對象，由上面公理3得這個對象也屬該聚集的上近似。然后將其余N-k個數據分配到1個離其最近的聚類中。

第2步：計算每個聚集新的質心。質心計算（均值函數）為公式（1）。

和是聚集下近似和邊界域的權重。

第3步：將數據對象分配到聚集的近似集中。對于Xn確定離它最近的質心，使用公式（2）將數據分配到聚集的上近似中。使用公式（3）確定質心，對于給定閾值，求集合T。

如果不空，則除距離很近外，距離T中任意t對應的也很近，則；否則，。

第4步：檢查算法的收斂性，即聚類是否變化。如果沒有收斂繼續(xù)第2步，否則算法結束。

2 改進的粗糙K-means算法

本文在Lingas提出的粗糙k-means算法上做了修改，使用相對閾值代替Lingas的K-means中的絕對閾值。算法步驟如下。

第1步：初始化。隨機分配每個數據到1個下近似中，由RS公理2得此數據也屬同一聚類上近似。

第2步：使用公式4計算每個聚集的新的均值。

第3步：為使每個聚集下近似至少有1個成員，即有：，由前公理2得，將每個數據對象分配到近似集中，1）最能代表1個集群的數據對象分配到它的上下近似中。

（1）計算所有對象與各個聚集的離，找到數據對象和聚集，使得距離聚集最近，則將數據分配到聚集的下近似和上近似中。計算過程中使用公式5：

（2）如果在（a）中有還有一些聚集沒有被分配到數據對象，即聚集的下近似為空，則返回（a）繼續(xù)將離每個聚集最近的1個數據分配到其下近似中，否則繼續(xù)第3）步。

（3）將剩余 N-k個數據對象，利用公式（2）確定離它最近的質心，將分配到聚集的上近似中。（3）確定是否有聚集，它的質心和的距離與和的距離的比在事先規(guī)定的閾值范圍內，即滿足公式（6）。

如不空，則說明除離近，距離中任何對應質心也很近，所以將分到聚集上近似中；否則，屬于的下近似。

第4步：檢查算法是否收斂，如不收斂，則繼續(xù)執(zhí)行第（3）步，否則結束。

3 實驗

對本文算法進行測試，與Lingas等人的算法在DBI結果進行比較。實驗中選擇wl=0.7、wu=0.3。

數據源來源于知識發(fā)現數據源網的林業(yè)數據，它描述30×30米區(qū)域森林覆蓋類型。有581012條記錄含54個屬性，10個數值變量，其余為二進制型，數值中有1個屬性描述7種森林植被類型（如云杉、楊木等）。對數據進行預處理，從中隨機選擇2345個記錄及10個數值屬性，設置集群數為7，表示森林覆蓋類型。數據歸一化為[0，1]。設重復因子r=50，imax=500。

聚類結果分析：Lingas等人算法選擇=0.0，…，0.0125時，提供了有意義結果，如圖1描述。圖中顯示邊界區(qū)數據對象對的依賴性。高的重復因子r對于較大值將導致穩(wěn)定最優(yōu)值，但算法所需時間顯著增加，同時算法收斂性也下降。相比之下，本文聚類算法在整個范圍內都能提供有意義的結果，邊界區(qū)域的對象數從0到2338（見圖2）。

一般改進的算法也表示DBI值略有改善，如圖3所示。值得注意是，Lingas算法對于邊界域中有大量數據對象時，由于大的使算法的收斂性降低。且重復因子r能導致更好DBI，但是以降低效率作為代價的。

4 結語

筆者提出一些方案。通過引入一個改進的粗糙k-means，在森林數據集上成功測試驗證了本文算法的有效性。

參考文獻

[1]聶舟，程遠國.一種基于平均相對偏差的聚類算法[J].兵工自動化，2008，27（8）：32-34.

[2]Pawlak Z.Rough Sets[J].Journal of Information and ComputerSciences，1982，11（5）：145-172.

[3]胡云，苗奪謙，王睿智等.一種基于粗糙k均值的雙聚類算法[J].計算機科學，2007，34（11）：174-177.

[4]鄭超，苗奪謙，王睿智.基于密度加權的粗糙k均值聚類改進算法[J].計算機科學，2009，36（3）：220-222.endprint