沈陽理工大學(xué)自動(dòng)化與電氣工程學(xué)院 鄭英鑫

數(shù)據(jù)挖掘中基于肘部法則的聚類分析在中小學(xué)生出行路線優(yōu)化設(shè)計(jì)的應(yīng)用

沈陽理工大學(xué)自動(dòng)化與電氣工程學(xué)院 鄭英鑫

本文介紹了在數(shù)據(jù)挖掘中，采用K-Means聚類分析算法對(duì)數(shù)據(jù)進(jìn)行分析與挖掘。但由于K-Means使用時(shí)，初始重心是隨機(jī)選取的，因此很容易陷入局部最優(yōu)解。為解決該問題，引入了肘部法則（Elbow）。K-Means通常初始時(shí)要重復(fù)運(yùn)行十幾次甚至上百次，這時(shí)采用肘部法則計(jì)算出最小的成本函數(shù)對(duì)應(yīng)的重心位置作為初始化位置，就很好的改善了局部最優(yōu)解問題。

聚類分析；K-Means算法；肘部法則

1.引言

“數(shù)據(jù)挖掘(Data Mining)”這個(gè)概念最早是由Usama Fayaad1995年加拿大蒙特利爾的第一屆知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘國際會(huì)議上提出的。數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中“挖掘”或者提取知識(shí)[1]。數(shù)據(jù)挖掘的知識(shí)模式有：概念/類描述、關(guān)聯(lián)模式、分類、聚類分析、預(yù)測(cè)、時(shí)間序列、偏差檢測(cè)。

數(shù)據(jù)挖掘源于多個(gè)學(xué)科，將聚類分析應(yīng)用到數(shù)據(jù)挖掘這樣一個(gè)多學(xué)科交叉的復(fù)雜領(lǐng)域，必定需要滿足一些要求，主要標(biāo)準(zhǔn)有：可伸縮性、能夠發(fā)現(xiàn)任意形狀的簇、能夠處理不同數(shù)據(jù)類型屬性、能夠處理帶噪聲的數(shù)據(jù)、高維性、對(duì)于決定輸入?yún)?shù)的領(lǐng)域知識(shí)需求最小化、對(duì)于輸入記錄的次序不敏感性和允許增量聚類、基于約束的聚類、可解釋性和可用性。在保證這些要求的前提下，合理運(yùn)用聚類分析算法對(duì)數(shù)據(jù)進(jìn)行分析與挖掘。

2.K-Means聚類算法

K-Means算法是1967年由MacQueen首次提出的一種經(jīng)典算法，經(jīng)常用于數(shù)據(jù)挖掘和模式識(shí)別中，是一種無監(jiān)督式的學(xué)習(xí)算法，其使用目的是對(duì)幾何進(jìn)行等價(jià)類的劃分，即對(duì)一組具有相同數(shù)據(jù)結(jié)構(gòu)的記錄按某種分類準(zhǔn)則進(jìn)行分類，以獲取若干個(gè)同類記錄集[2]。K-Means算法具體實(shí)現(xiàn)步驟：

首先從n個(gè)數(shù)據(jù)對(duì)象中任意選擇k個(gè)對(duì)象作為初始聚類中心，而對(duì)于所剩下的其它對(duì)象，則根據(jù)他們與這些聚類中心的相似度（距離），分別將他們分配給與其最相似的（聚類中心所代表的）聚類。然后再計(jì)算每個(gè)所新聚類的聚類中心（該聚類中所有對(duì)象的均值）。不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開始收斂為止。一般采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)，以歐式距離作為判斷數(shù)據(jù)間相似度的依據(jù)。

3.基于Elbow-K-Means的聚類分析

K-Means的初始重心位置是隨機(jī)選擇的，隨機(jī)選擇的重心會(huì)導(dǎo)致K-Means陷入局部最優(yōu)解，這樣分類可能失去了實(shí)際意義。為了避免局部最優(yōu)解，K-Means通常初始時(shí)要重復(fù)運(yùn)行十幾次甚至上百次。每次重復(fù)時(shí)，它會(huì)隨機(jī)的從不同的位置開始初始化。最后把最小的成本函數(shù)對(duì)應(yīng)的重心位置作為初始化位置。

肘部法則（Elbow）會(huì)把不同K值的成本函數(shù)值畫出來。隨著K值的增大，平均畸變程度會(huì)減小。每個(gè)類包含的樣本數(shù)會(huì)減少，于是樣本離其重心會(huì)更近。但是，隨著K值繼續(xù)增大，平均畸變程度的改善效果會(huì)不斷減低。K值增大過程中，畸變程度的改善效果下降幅度最大的位置對(duì)應(yīng)的K值就是肘部。

4.仿真結(jié)果

運(yùn)用K-Means聚類算法及肘部法則解決中小學(xué)生出行路線優(yōu)化設(shè)計(jì)中校車停車站點(diǎn)數(shù)目及位置的選取問題。

針對(duì)單個(gè)學(xué)校的校車停車站點(diǎn)的位置選取。運(yùn)用K-Means聚類算法，以歐式距離作為判斷各點(diǎn)相似度的依據(jù)，均方差作為測(cè)度函數(shù)，找出K個(gè)聚類中心即得到K個(gè)校車停車站點(diǎn)的位置。其中問題中沒有指定K的值，因此可以通過肘部法則進(jìn)而合理地選定該校校車的停車站點(diǎn)的數(shù)量K作為聚類的類別數(shù)，本論文中數(shù)據(jù)來源于某市某十所學(xué)校，分別包括每個(gè)學(xué)校每個(gè)學(xué)生具體的位置，上學(xué)和放學(xué)的具體出行方式及上學(xué)的具體時(shí)間，是否有乘坐校車的意愿和每個(gè)學(xué)校及其校門的具體地址。由Matlab仿真后，結(jié)果表明，基于肘部法則確定的站點(diǎn)數(shù)目及位置更加準(zhǔn)確。

[1]蔣盛益,李霞,鄭琪.數(shù)據(jù)挖掘原理與實(shí)踐[M].北京:電子工業(yè)出版社,2011.

[2]陳寶樓.K-Means算法研究在文本聚類中的應(yīng)用[D].江蘇:安徽大學(xué),2013(04).