優(yōu)化的聚類算法與混合的K—Means分層算法

摘 要：數(shù)據(jù)挖掘是大量數(shù)據(jù)的分析，發(fā)現(xiàn)數(shù)據(jù)中有效的、新穎的、潛在有用的數(shù)據(jù)，最終變?yōu)榭衫斫獾哪Ｊ?。本文介紹了數(shù)據(jù)挖掘的概念，旨在提供k-means聚類和等級分明的聚類組合，提供的混合聚類方法在集群機(jī)制的穩(wěn)定性是非常有幫助的。

關(guān)鍵詞：數(shù)據(jù)挖掘；聚類；聚類應(yīng)用

中圖分類號：TP301.6

數(shù)據(jù)挖掘（也成數(shù)據(jù)或知識發(fā)現(xiàn)）的分析從不同的角度來分析數(shù)據(jù)，并總結(jié)將其轉(zhuǎn)化為有用信息的過程，可以用來增加收入，減少成本，或兩者兼而有之。數(shù)據(jù)挖掘的軟件是一系列的用于分析數(shù)據(jù)的工具之一。它允許用戶從不同的層面或角度的來分析數(shù)據(jù)，對其進(jìn)行分類，并總結(jié)確定了關(guān)系。

數(shù)據(jù)挖掘是知識發(fā)現(xiàn)數(shù)據(jù)庫（KDD）的核心部分。很多人把KDD作為數(shù)據(jù)挖掘的代名詞，因?yàn)樗侵R發(fā)現(xiàn)過程的一個(gè)重要組成部分。包括下列步驟的迭代序列：（1）數(shù)據(jù)清洗-即去除噪聲或不相關(guān)的數(shù)據(jù)；（2）數(shù)據(jù)集成-在多個(gè)數(shù)據(jù)源進(jìn)行組合；（3）數(shù)據(jù)選集-相關(guān)的分析任務(wù)數(shù)據(jù)被從數(shù)據(jù)庫中檢索；（4）數(shù)據(jù)轉(zhuǎn)換-數(shù)據(jù)被轉(zhuǎn)換或合并成適合挖掘的形式通過進(jìn)行匯總或聚合操作；（5）數(shù)據(jù)挖掘-在智能方法應(yīng)用中用于提取數(shù)據(jù)模式的一個(gè)必要的過程；（6）定型鑒定-要識別出代表基于一些趣味性措施的知識且真正有趣的模式；（7）知識介紹-知識表達(dá)技術(shù)用于提供給用戶目前的挖掘知識信息。

1 聚類

聚類是一種將一組數(shù)據(jù)（或?qū)ο螅┓譃橐唤M有意義的子類，稱為集群的過程。它可以幫助用戶了解數(shù)據(jù)集中的自然分組或結(jié)構(gòu)。一個(gè)好的聚類方法將生產(chǎn)高質(zhì)量的集群，其中，類內(nèi)（即，幀內(nèi)簇）的相似性高，并且類間相似性是低的。聚類結(jié)果的好壞取決于兩者所采用的方法及其實(shí)現(xiàn)的相似性度量。聚類方法的質(zhì)量也由它發(fā)現(xiàn)部分或全部隱藏模式的能力來衡量的，聚類的分析結(jié)果如圖1所示：

我們的目標(biāo)是，在一個(gè)組中的對象會(huì)是相似的（或相關(guān)的）到另一個(gè)不同于（或無關(guān)）在其他組中的對象。更大的相似性（或同質(zhì)性）中的基團(tuán)和更大的群體之間的差異，也出現(xiàn)在“更好”或“更獨(dú)特”的聚類中。

聚類分析的例子：

讓我們以圖書館系統(tǒng)的為例。在圖書館的中找了大量的不同主題的圖書。他們始終保持簇的形式，有一些書因?yàn)樗鼈冎g的相似性所以被放置在一個(gè)集群也就是簇中。例如，關(guān)于數(shù)據(jù)庫的書都放在一個(gè)架子上，而關(guān)于操作系統(tǒng)的書籍都放在一個(gè)柜子中等等。為了進(jìn)一步降低復(fù)雜性，覆蓋相同種類主題的書籍被放置在同一個(gè)柜子中。然后柜子和櫥柜都貼有相關(guān)的名稱?，F(xiàn)在，當(dāng)用戶想要一本關(guān)于特定類型的話題，圖書管理員會(huì)去相對應(yīng)的架子查找這本書，而不是搜索整個(gè)圖書館。

聚類算法可以應(yīng)用在許多領(lǐng)域，例如：

營銷：尋找相似的客戶群，給定含有客戶群提的性質(zhì)和以往的購買記錄的大型數(shù)據(jù)庫的行為。

生物學(xué)：根據(jù)動(dòng)植物的功能進(jìn)行分類。

圖書館：圖書訂購。

保險(xiǎn)：識別汽車保險(xiǎn)保單持有人的群體而且有較高的平均索賠成本，識別欺詐行為。

城市規(guī)劃：根據(jù)他們的房子的類型、價(jià)值和地理位置來識別他們的房屋群。

地震研究：使用聚類來觀測地震的震中央，以確定危險(xiǎn)區(qū)。

萬維網(wǎng)：文檔分類；使用聚類分析博客的數(shù)據(jù)，發(fā)現(xiàn)類似的訪問模式組。

2 K-均值聚類：算法

k-均值算法（勞埃德，1982）屬于一個(gè)家庭的算法，稱為優(yōu)化聚類算法。在該家庭的算法中，集群的形成，優(yōu)化了部分良好的集群算法。也就是說，實(shí)例被劃分為簇，然后簇根據(jù)一些衡量最優(yōu)化。這個(gè)名字來源K集群的形成，其中所述簇的中心是該集群內(nèi)的所有向量的算術(shù)平均值。

3 分層聚類

分層聚類算法分為兩種類別：凝聚和分裂。

凝聚聚類在底部，最初將每個(gè)數(shù)據(jù)點(diǎn)作為一個(gè)單獨(dú)的群集，然后依次合并集群，直到所有的點(diǎn)都被合并成一個(gè)單一的群集。分裂的聚類，首先將所有數(shù)據(jù)點(diǎn)集中在一個(gè)集群，然后逐漸獲得所需要的集群。具體來說，主要有兩個(gè)步驟：第一是選擇一個(gè)合適的聚類分割，二是確定如何分割成兩個(gè)新簇。

凝聚VS分裂：這方面涉及的算法結(jié)構(gòu)和操作有：一種凝聚的方法開始于不同的模式（獨(dú)立）集群，先后合并在一起，直到達(dá)到滿意的標(biāo)準(zhǔn)然后停止。一種分裂的方法是在所有模式中選擇一個(gè)單一的集群，然后執(zhí)行分裂直到滿足停止標(biāo)準(zhǔn)。其優(yōu)勢為可以產(chǎn)生對象的排序，可以信息數(shù)據(jù)顯示的排序，并且有較小的簇生成，這可能有助于發(fā)現(xiàn)。

4 WEKA

WEKA數(shù)據(jù)挖掘系統(tǒng)是新西蘭懷卡托大學(xué)的數(shù)據(jù)挖掘算法，使用Java語言進(jìn)行開發(fā).以展現(xiàn)現(xiàn)實(shí)世界中的數(shù)據(jù)挖掘問題的狀態(tài)。WEKA實(shí)現(xiàn)了對數(shù)據(jù)預(yù)處理，算法的加工，分類，回歸，聚類和關(guān)聯(lián)規(guī)則；同時(shí)還包括可視化工具。WEKA是通用公共許可下發(fā)布的開放源碼軟件。通常Weka中的數(shù)據(jù)文件是ARFF文件格式，它由特殊標(biāo)記，以指示在數(shù)據(jù)文件中不同的東西（最重要的：屬性名，屬性類型，屬性值和數(shù)據(jù)）。其主要特點(diǎn)為包含：

·49個(gè)數(shù)據(jù)預(yù)處理工具。

·76個(gè)分類/回歸算法。

·8個(gè)聚類算法。

·33個(gè)具有關(guān)聯(lián)規(guī)則的算法。

·15個(gè)特征選擇屬性/子集評估+10個(gè)搜索算法。

主要的圖形用戶界面：

·“資源管理器”（探索性數(shù)據(jù)分析）。

·“實(shí)驗(yàn)者”（實(shí)驗(yàn)環(huán)境）。

·“知識流”（新的過程模型靈感的接口）。

5 方法

我們的研究將始于各種資源的數(shù)據(jù)集收集并對WEKA工具進(jìn)行研究。從WEKA的A獲取的API將為聚類提供數(shù)據(jù)集。K均值實(shí)施將用其他群集方式和Java語言來實(shí)現(xiàn)可擴(kuò)展性和集成。K均值實(shí)施值后，我們將開發(fā)可以在同一數(shù)據(jù)集層的聚類技術(shù)。通過結(jié)合這兩種算法來減少整體處理速度和數(shù)量簇的形成。

參考文獻(xiàn)：

[1]朱琳，朱參世.計(jì)算機(jī)工程與應(yīng)用[J]，2014（01）.

[2]Jiawei Han，Micheline Kamber，Morgan Kauffman.數(shù)據(jù)挖掘：概念與技術(shù)（第二版）[M].北京：機(jī)械工業(yè)出版社，2007.

作者簡介：石靜（1988.10-），女，山東鄒平人，研究生，計(jì)算機(jī)技術(shù)專業(yè)，研究方向：數(shù)據(jù)挖掘。

作者單位：長春工業(yè)大學(xué)南湖校區(qū)，吉林長春 130012