基于劃分的數(shù)據(jù)挖掘K?means聚類算法分析

曾俊

摘? 要： 為提升數(shù)據(jù)挖掘中聚類分析的效果，在分析數(shù)據(jù)挖掘、聚類分析、傳統(tǒng)K?means算法的基礎(chǔ)上，提出一種改進(jìn)的K?means算法。首先將整體數(shù)據(jù)集分為[k]類，然后設(shè)定一個密度參數(shù)為[?]，該密度參數(shù)反映數(shù)據(jù)庫中數(shù)據(jù)所處區(qū)域的密度大小，[?]值與密度大小成正比，通過密度參數(shù)優(yōu)化[k]個樣本數(shù)據(jù)的聚類中心點(diǎn)選取;依據(jù)歐幾里得距離公式對未選取的其他數(shù)據(jù)到各個聚類中心之間的距離進(jìn)行計(jì)算，同時以此距離為判別標(biāo)準(zhǔn)，對各個數(shù)據(jù)進(jìn)行種類劃分，從而得到初始的聚類分布;初始聚類分布得到之后，對每一個分布簇進(jìn)行再一次的中心點(diǎn)計(jì)算，并判斷與之前所取中心點(diǎn)是否相同，直到其聚類收斂達(dá)到最優(yōu)效果。最后通過葡萄酒數(shù)據(jù)集對改進(jìn)算法進(jìn)行驗(yàn)證分析，改進(jìn)算法比傳統(tǒng)K?means算法的聚類效果更優(yōu)，能夠更好地在數(shù)據(jù)挖掘當(dāng)中進(jìn)行聚類。

關(guān)鍵詞： 數(shù)據(jù)挖掘; 聚類分析; K?means聚類算法; 聚類中心選取; K?means算法改進(jìn); 初始中心點(diǎn)

中圖分類號： TN911.1?34? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）03?0014?04

Analysis of partition?based data mining K?means clustering algorithm

ZENG Jun

（College of Big Data and Intelligent Engineering， Yangtze Normal University， Chongqing 408100， China）

Abstract： An improved K?means algorithm on the basis of the analysis of data mining， clustering analysis and traditional K?means algorithm is proposed to improve the effect of clustering analysis in data mining. The whole data set is divided into [k] classes firstly， and then a density parameter [?] is set， which reflects the density of the area in which the data is located in the database. The value of [?] is proportional to the density. The selection of cluster center points of [k] sample data is optimized by the density parameter. The distance between other unselected data and each cluster center is calculated by Euclidean distance formula. At the same time， the distance is taken as the criterion to divide each data into different categories， so as to get the initial clustering distribution. After the initial clustering distribution is obtained， the center point of each distribution cluster is calculated again to judge whether it is the same as the previous center point， until the clustering convergence reaches the optimal effect. Finally， the wine algorithm is used to verify and analyze the improved algorithm. The results show that the improved algorithm has better clustering effect than the traditional K?means algorithm， and can better perform clustering in data mining.

Keywords： data mining; clustering analysis; K?means clustering algorithm; clustering center selection; K?means algorithm improvement; initial center point

0? 引? 言

信息時代的來臨及其快速發(fā)展為人們的生活與工作帶來了極大便利，數(shù)據(jù)資源對于人們的影響也越來越大。如何從龐大繁雜的數(shù)據(jù)資源當(dāng)中汲取有效信息變得極其重要，數(shù)據(jù)挖掘應(yīng)用而生。聚類分析在數(shù)據(jù)挖掘模型當(dāng)中的作用巨大。基于劃分的K?means算法是聚類分析中具有代表性的算法，其收斂性相對較強(qiáng)，但傳統(tǒng)的K?means仍存在諸多問題，對于K?means算法應(yīng)當(dāng)如何改進(jìn)，怎樣通過算法融合和各類技術(shù)手段進(jìn)行優(yōu)化，很多專家學(xué)者對此相當(dāng)關(guān)注。當(dāng)前K?means算法主要存在的缺陷主要是樣本數(shù)據(jù)[k]值的選擇，孤立點(diǎn)的影響仍然難以消除等。同時，K?means算法計(jì)算量相對較大，需要承擔(dān)較大的計(jì)算壓力。本文提出通過設(shè)定密度參數(shù)進(jìn)行初始中心點(diǎn)的優(yōu)化，從而進(jìn)行聚類分析，做到更好的數(shù)據(jù)挖掘效果。

1? 數(shù)據(jù)挖掘概述

1.1? 數(shù)據(jù)挖掘的現(xiàn)狀

總體來看，數(shù)據(jù)挖掘所要研究的數(shù)據(jù)大致可以分為半結(jié)構(gòu)化數(shù)據(jù)、結(jié)構(gòu)化數(shù)據(jù)、非結(jié)構(gòu)化數(shù)據(jù)以及異構(gòu)數(shù)據(jù)等[1]。

隨著信息技術(shù)翻天覆地的發(fā)展與進(jìn)步，數(shù)據(jù)挖掘以及人工智能在生產(chǎn)生活當(dāng)中的位置愈發(fā)重要。無論是工業(yè)生產(chǎn)還是日常生活，都能夠通過數(shù)據(jù)挖掘帶來更好的利益與便利，更好地提高人民的生產(chǎn)生活水平。

1.2? 數(shù)據(jù)挖掘的流程

數(shù)據(jù)挖掘的一般流程如下簡述：

1） 對數(shù)據(jù)進(jìn)行選擇以及集成，是指從已有的數(shù)據(jù)庫當(dāng)中進(jìn)行相應(yīng)的目標(biāo)數(shù)據(jù)選取，并以此作為下一步的處理目標(biāo)。

2） 對所選數(shù)據(jù)進(jìn)行預(yù)處理，是指對所選數(shù)據(jù)當(dāng)中的重復(fù)部分以及噪聲做出消除，同時對缺失數(shù)據(jù)進(jìn)行計(jì)算彌補(bǔ)。數(shù)據(jù)的預(yù)處理是整個數(shù)據(jù)挖掘過程當(dāng)中的關(guān)鍵一步，其中步驟不需要順序排列，同時可以多次執(zhí)行以達(dá)到所求效果。

3） 數(shù)據(jù)的轉(zhuǎn)化，數(shù)據(jù)轉(zhuǎn)化的過程是將步驟2）所得數(shù)據(jù)進(jìn)行對應(yīng)實(shí)際需求的轉(zhuǎn)化，如多維到低維的轉(zhuǎn)化，通過轉(zhuǎn)化達(dá)到數(shù)據(jù)挖掘更為高效的目的。

4） 相關(guān)數(shù)據(jù)挖掘的算法，依據(jù)聚類、回歸、概括或者分類等各種模型的建立，做出對應(yīng)的數(shù)據(jù)建模。

5） 對數(shù)據(jù)做出進(jìn)一步的評估，以獲得有價(jià)值的結(jié)論，提供實(shí)用信息。

2? 聚類分析簡述

2.1? 聚類分析的定義

聚類分析是指對整體的數(shù)據(jù)庫依據(jù)一定算法進(jìn)行分析與計(jì)算，將其進(jìn)行類別劃分，同類當(dāng)中的數(shù)據(jù)具備盡量大的相似性，不同類之間的差異性盡可能大[2]。具體表達(dá)上，整體數(shù)據(jù)可以定義為集合[N]，[N=x1，x2，…，xn]，其中，[n]表示整體數(shù)據(jù)中的數(shù)據(jù)量。在對整體數(shù)據(jù)庫[N]進(jìn)行聚類時，把數(shù)據(jù)庫[N]中的[n]個數(shù)據(jù)依照目標(biāo)相似度進(jìn)行劃分，劃分為[m]類[y1，y2，…，ym]，其中，[yi]為劃分的第[i]類，聚類結(jié)果用集合[Q]表示，表達(dá)式如下：

2.2? 聚類分析的現(xiàn)狀

聚類分析目前已經(jīng)應(yīng)用到各類領(lǐng)域，其中難點(diǎn)是算法的普適性以及有效性的提升[3]。這主要是由于當(dāng)前信息時代越來越大的數(shù)據(jù)分析需求。同時，聚類分析作為以距離為主要分析依據(jù)的劃分技術(shù)，理論依據(jù)是統(tǒng)計(jì)學(xué)與機(jī)器學(xué)習(xí)。當(dāng)前聚類分析的發(fā)展中，由于需要面對越來越龐雜的數(shù)據(jù)量，聚類分析往往存在一定缺陷，難以實(shí)現(xiàn)高效和精準(zhǔn)。大數(shù)據(jù)時代數(shù)據(jù)的差異性也決定了很難找到一個普適的聚類算法對所有數(shù)據(jù)進(jìn)行分析。

多數(shù)聚類算法與爬山算法有一定的相同之處，其缺點(diǎn)主要表現(xiàn)在兩個方面：一是容易產(chǎn)生局部最優(yōu);二是數(shù)據(jù)量過大時，往往難以聚類精準(zhǔn)。因此，聚類算法仍然需要不斷的完善與改進(jìn)，以適應(yīng)更大更復(fù)雜的數(shù)據(jù)處理。具體上，可以通過學(xué)科互補(bǔ)進(jìn)行聚類分析的優(yōu)化。如以混沌理論作為基本依據(jù)的聚類分析或者是借助各類優(yōu)化算法所進(jìn)行的聚類分析[4]。

2.3? 聚類分析的流程

聚類分析旨在理清整體數(shù)據(jù)，首要工作是整體數(shù)據(jù)的選擇，并從中進(jìn)行信息提取。在此過程中，歐幾里得空間距離是其相似性的基本判斷依據(jù)。相似性判斷之后，進(jìn)行對應(yīng)的結(jié)果驗(yàn)證[5]。通常結(jié)果驗(yàn)證需要進(jìn)行多組數(shù)據(jù)的檢驗(yàn)，以提高其普適性。聚類分析具體的流程如圖1所示。

2.4? 聚類算法的數(shù)據(jù)結(jié)構(gòu)

聚類算法的數(shù)據(jù)結(jié)構(gòu)主要分為兩類：一類是相異度矩陣;另一類是數(shù)據(jù)矩陣。下面對兩類數(shù)據(jù)結(jié)構(gòu)做簡單介紹。

2.4.1? 相異度矩陣

相異度矩陣主要體現(xiàn)樣本數(shù)據(jù)之間的差異性，其作為對象?對象的一種數(shù)據(jù)表達(dá)方式，是多種聚類算法的底層基礎(chǔ)。當(dāng)樣本數(shù)據(jù)為[m]時，其相異度矩陣為[m×m]維，所表達(dá)的是[m]個樣本數(shù)據(jù)的差異性。對于含[m]個樣本數(shù)據(jù)的數(shù)據(jù)庫集合[N=a1，a2，…，an]來說，其相異度矩陣可以表示為：

式中[d（i，j）]是樣本數(shù)據(jù)[i]與樣本數(shù)據(jù)[j]之間的量化表示，多數(shù)情況下，此值非負(fù)。若兩個樣本數(shù)據(jù)之間的相似度越高，則此值相應(yīng)越小;若兩個樣本數(shù)據(jù)之間的相異度越高，則此值越大。

2.4.2? 數(shù)據(jù)矩陣

數(shù)據(jù)矩陣能夠?qū)φw數(shù)據(jù)當(dāng)中的所有樣本數(shù)據(jù)的屬性值進(jìn)行表示。其數(shù)據(jù)樣本以行表示，數(shù)據(jù)的屬性以列表示。如數(shù)據(jù)庫所組成的集合[Q=a1，a2，…，an]，其對應(yīng)的數(shù)據(jù)對象[ai]若有[m]個屬性，則表示其維度為[m]，矩陣表示如下：

3? K?means聚類算法簡述

3.1? K?means算法研究現(xiàn)狀

K?means聚類算法自提出至今，有關(guān)于此類算法的研究有很多。同時在工商業(yè)、科學(xué)、統(tǒng)計(jì)學(xué)以及人工智能等各個領(lǐng)域有廣泛的應(yīng)用。當(dāng)下比較熱門的微博熱點(diǎn)的提取、銀行中客戶信息的整理以及圖形處理等方面都會應(yīng)用到K?means聚類算法。近年來，關(guān)于K?means算法的優(yōu)化算法多種多樣，同時學(xué)者們也對K?means算法做出了進(jìn)一步的完善，如通過聚類評價(jià)指標(biāo)的更新獲得更好的聚類結(jié)果;利用學(xué)科融合，K?means算法與粒子群相結(jié)合或是K?means算法與神經(jīng)網(wǎng)絡(luò)相結(jié)合的算法等[6]。

3.2? K?means算法的基本思想與實(shí)現(xiàn)步驟

K?means算法是基于劃分的一類經(jīng)典的聚類算法，此類算法能夠在[n]維的數(shù)據(jù)空間中進(jìn)行廣泛應(yīng)用。K?means算法通過多次迭代對給定的樣本數(shù)據(jù)進(jìn)行不同的種類劃分，劃分的每一種類的內(nèi)部數(shù)據(jù)盡可能相似，與其他種類的數(shù)據(jù)盡可能相異。K?means算法的基本思想是：首先將整體數(shù)據(jù)集分為[k]類，并從整體數(shù)據(jù)集當(dāng)中選取[k]個樣本數(shù)據(jù)作為最初的聚類中心;最初聚類中心確定之后，依據(jù)歐幾里得距離公式對未選取的其他數(shù)據(jù)到各個聚類中心之間的距離進(jìn)行計(jì)算，同時以此距離為判別標(biāo)準(zhǔn)，對各個數(shù)據(jù)進(jìn)行種類劃分，從而得到初始的聚類分布。初始聚類分布得到之后，對每一個分布簇進(jìn)行再一次的中心點(diǎn)計(jì)算，并判斷與之前所取中心點(diǎn)是否相同，若不同，則進(jìn)行新的迭代調(diào)整，直到其聚類收斂能夠達(dá)到研究所需，停止迭代，結(jié)束算法。K?means聚類算法進(jìn)行聚類的過程是通過迭代計(jì)算對中心點(diǎn)進(jìn)行更好確立的過程。此類算法往往簡便易行、效率較高，同時收斂速度很快。其具體步驟簡述如下：

1） 設(shè)整體數(shù)據(jù)集為[N]，在數(shù)據(jù)集[N]中選擇[k]個樣本數(shù)據(jù)，這[k]個樣本數(shù)據(jù)定義為最初聚類中心，得到[M1]，[M2]，…，[Mk]個最初的聚類中心點(diǎn)，以此區(qū)別劃分種類的數(shù)量。

2） 對數(shù)據(jù)集合中未選取的樣本數(shù)據(jù)到各個聚類中心點(diǎn)間的距離進(jìn)行計(jì)算，并依據(jù)距離進(jìn)行樣本數(shù)據(jù)的劃分，形成初始的聚類分布。

3） 以公式[Mi=1nix∈φiN]為計(jì)算依據(jù)，對各個聚類簇進(jìn)行再一次的中心點(diǎn)計(jì)算，所得到的新的中心點(diǎn)用[Mn1，Mn2]，…，[Mnk]表示。

4） 判斷是否符合目標(biāo)收斂度，若不符合，則返回步驟2），直到滿足目標(biāo)收斂度為止。

5） 輸出所得的聚類數(shù)據(jù)。

K?means算法的流程圖如圖2所示。

4? 優(yōu)化中心點(diǎn)對K?means算法進(jìn)行改進(jìn)

4.1? 提出問題

K?means算法是否能夠產(chǎn)生更好的聚類效果，在很大程度上取決于初始中心點(diǎn)的選取。原有的K?means算法在進(jìn)行初始中心點(diǎn)選取時，無法確定中心點(diǎn)選取是否整體分散，抑或中心點(diǎn)是否會選擇到噪聲數(shù)據(jù)或者是邊緣數(shù)據(jù)。其聚類結(jié)果的時效性以及穩(wěn)定性無法得到保障。具體應(yīng)用當(dāng)中，找到合適的中心點(diǎn)能夠幫助K?means算法達(dá)到效果最優(yōu)。

K?means算法的中心點(diǎn)選取時，受數(shù)據(jù)分布影響會產(chǎn)生較大誤差，可參照圖3進(jìn)行分析。

圖3中，a）與b）中心點(diǎn)與其中部分對象的歐氏距離相同，但是二者的整體分布存在差異;b）與c）的整體分布大致相同，但是個別點(diǎn)與中心點(diǎn)的距離不同。在中心點(diǎn)的選取過程當(dāng)中，個別中心點(diǎn)選取所反映的整體數(shù)據(jù)分布存在差異。如何選取一個合適的中心點(diǎn)，更好地處理整體數(shù)據(jù)分布，反映數(shù)據(jù)聚類信息，是解決中心點(diǎn)選取的關(guān)鍵。

4.2? 通過密度參數(shù)優(yōu)化中心點(diǎn)選取

可以設(shè)定一個密度參數(shù)為[?]，該密度參數(shù)反映數(shù)據(jù)庫中數(shù)據(jù)所處區(qū)域的密度大小，[?]值與密度大小成正比。此值通過以選定的樣本數(shù)據(jù)[ai]作為中心，將與其距離相近的[n]個參數(shù)到此對象的距離平均值作為[?]值。主要的算法依據(jù)是：首先通過歐幾里得空間距離進(jìn)行樣本數(shù)據(jù)之間的距離計(jì)算;而后對各數(shù)據(jù)的密度參數(shù)[?]值進(jìn)行計(jì)算，并計(jì)算[?]值的平均值[?]。所有密度參數(shù)值組成集合[D]。[k]個初始中心點(diǎn)從集合[D]中進(jìn)行選取，而后進(jìn)行基于K?means算法的聚類分析。從集合[D]中選取[k]個初始中心點(diǎn)的步驟如下：

1） 在密度集合[D]中選擇最小密度參數(shù)值[?]所對應(yīng)的樣本數(shù)據(jù)，以此作為首個聚類中心點(diǎn)[ai（i=1）]。

2） 集合[D]刪除[?]半徑內(nèi)的數(shù)據(jù)與中心點(diǎn)[a1]。

3） 令新的密度集合為[D]，并計(jì)算密度參數(shù)[?]。

4） 執(zhí)行步驟1），得到聚類中心點(diǎn)[ai]。

5） 判斷[i]是否等于[k]，若是，則輸出[k]個中心點(diǎn)。否則，返回步驟2）。

中心點(diǎn)選取的具體流程如圖4所示。

中心點(diǎn)選取完畢后，依照K?means算法的步驟進(jìn)行聚類分析。

4.3? 結(jié)果驗(yàn)證與分析

通過Wine葡萄酒數(shù)據(jù)集對改進(jìn)算法進(jìn)行驗(yàn)證分析。Wine葡萄酒數(shù)據(jù)集包括3種起源不同的葡萄酒的178條記錄。同時，包含13個不同屬性，表示葡萄酒的13種不同化學(xué)成分。實(shí)驗(yàn)采用傳統(tǒng)K?means算法改進(jìn)后的算法相對比的方式進(jìn)行，并得出對應(yīng)的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果如表1所示。

通過實(shí)驗(yàn)結(jié)果不難發(fā)現(xiàn)，K?means算法的聚類結(jié)果不夠穩(wěn)定，其準(zhǔn)確度多數(shù)低于改進(jìn)算法。同時，K?means算法的準(zhǔn)確度均值要低于改進(jìn)算法。實(shí)驗(yàn)結(jié)果證明，改進(jìn)算法比K?means算法的聚類效果更優(yōu)，能夠更好在數(shù)據(jù)挖掘當(dāng)中進(jìn)行聚類分析。

5? 結(jié)? 語

針對傳統(tǒng)K?means算法中心點(diǎn)選取的不足之處，借助密度參數(shù)對中心點(diǎn)選取進(jìn)行優(yōu)化。經(jīng)過實(shí)驗(yàn)對比分析，改進(jìn)算法比傳統(tǒng)K?means算法的聚類效果更優(yōu)，能夠更好地在數(shù)據(jù)挖掘當(dāng)中進(jìn)行聚類。

參考文獻(xiàn)

[1] 李國杰，程學(xué)旗.大數(shù)據(jù)的研究現(xiàn)狀與科學(xué)思考[J].中國科學(xué)院院刊，2012，27（6）：647?657.

[2] 黃敏，何中市.一種新的K?means聚類中心選取算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（35）：132?134.

[3] 劉兵，夏世雄，周勇.基于樣本加權(quán)的可能性模糊聚類算法[J].電子學(xué)報(bào)，2012，34（5）：1332?1335.

[4] 鄭丹，王潛平.K?means初始聚類中心的選擇算法[J].計(jì)算機(jī)應(yīng)用，2012，32（8）：2186?2188.

[5] 金曉民，張麗萍.基于最小生成樹的多層次K?means聚類算法及其在數(shù)據(jù)挖掘中的應(yīng)用[J].吉林大學(xué)學(xué)報(bào)（理學(xué)版），2018，56（5）：153?158.

[6] 龔敏，鄧珍榮，黃文明.基于用戶聚類與Slope One填充的協(xié)同推薦算法[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（22）：144?148.

[7] WANG Zhiqiong， XIN Junchang， YANG Hongxu. Distributed and weighted extreme learning machine for imbalanced big data learning [J]. Tsinghua science and technology， 2017（2）： 160?173.

[8] LI Peng， LUO Hong， SUN Yan. Similarity search algorithm over data supply chain based on key points [J]. Tsinghua science and technology， 2017（2）： 174?184.

[9] DAN Tao， LIN Zhaowen， WANG Bingxu. Load feedback?based resource scheduling and dynamic migration?based data locality for virtual Hadoop clusters in OpenStack?based clouds [J]. Tsinghua science and technology， 2017（2）： 149?159.