數(shù)據(jù)挖掘中的聚類算法的研究

山東科技大學(xué) 王子墨

數(shù)據(jù)挖掘中的聚類算法的研究

山東科技大學(xué) 王子墨

本文主要研究了據(jù)挖掘中的聚類算法，利用密度以及均勻抽樣方法來(lái)縮減數(shù)據(jù)規(guī)模，從而提高了聚類的運(yùn)行效率；并將粒子群算法與及模擬退火算法相結(jié)合，在原有算法的基礎(chǔ)上進(jìn)行改進(jìn)進(jìn)而獲取更佳的初始中心；進(jìn)一步將算法應(yīng)用到和真實(shí)數(shù)據(jù)集，例證了本文方法的正確性和有效性，并進(jìn)行對(duì)比，證明新算法的高效性，也進(jìn)一步證明了新算法的正確性，對(duì)以后的研究起到了正確的指引作用。

聚類算法；粒子群算法；模擬退火法；數(shù)據(jù)挖掘

聚類分析近些年來(lái)被廣泛運(yùn)用到客戶劃分領(lǐng)域，對(duì)客戶群體的劃分，從客戶的購(gòu)買行為、瀏覽記錄等屬性劃分為不同的客戶群體。本文以數(shù)據(jù)抽樣為核心，比較分析了現(xiàn)存抽樣算法性能的優(yōu)劣，同時(shí)研究抽樣技術(shù)在海量數(shù)據(jù)聚類分析中的應(yīng)用，結(jié)合密度以及均勻抽樣方法來(lái)縮減數(shù)據(jù)量為了減少K-means 算法對(duì)初始聚類中心的依賴性和敏感性，對(duì)K-means算法初始聚類中心的優(yōu)化選擇進(jìn)行理論研究。提出基于自然選擇和基于模擬退火的粒子群算法來(lái)選取更佳的初始中心。針對(duì)K-means算法在實(shí)際應(yīng)用中算法存在的不足，結(jié)合三角不等式來(lái)減少迭代次數(shù)，提高運(yùn)算效率并提出改進(jìn)算法，使新算法具有更好的全局收斂,并將其應(yīng)用到實(shí)際問(wèn)題中，從而證明新算法的實(shí)用性。

根據(jù)以上主要內(nèi)容，擬解決的關(guān)鍵技術(shù)是對(duì)大數(shù)據(jù)抽樣和K-means算法進(jìn)行理論研究，通過(guò)對(duì)國(guó)內(nèi)外關(guān)于聚類分析的研究文獻(xiàn)，對(duì)大數(shù)據(jù)抽樣和K-means算法的理論成果做進(jìn)一步的總結(jié)。針對(duì)大多數(shù)聚類算法在面對(duì)海量高維數(shù)據(jù)所表現(xiàn)的不足以及K-means算法初始中心選取的隨機(jī)性，利用抽樣縮減數(shù)據(jù)量后，結(jié)合粒子群算法，提出改進(jìn)算法，最后對(duì)人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行挖掘，并將其應(yīng)用到實(shí)際問(wèn)題中，從而證明新算法的實(shí)用性。

從航空公司系統(tǒng)內(nèi)的客戶基本信息、乘機(jī)信息以及積分信息等詳細(xì)數(shù)據(jù)，根據(jù)末次飛行日期，抽取2006年4月1日至2008年4月1日內(nèi)所有乘客的詳細(xì)數(shù)據(jù)，總共16382條記錄，63個(gè)屬性其中包含了如卡號(hào)、入會(huì)時(shí)間、性別、年齡、會(huì)員卡級(jí)別、工作地城市、工作地所在省份、工作地所在國(guó)家、觀測(cè)窗口結(jié)束時(shí)間、觀測(cè)窗口乘積積分、飛行公里數(shù)、飛行次數(shù)、飛行時(shí)間、乘機(jī)時(shí)間間隔、平均折扣率等。對(duì)數(shù)據(jù)預(yù)處理的過(guò)程主要包括數(shù)據(jù)清洗、數(shù)據(jù)選擇以及數(shù)據(jù)轉(zhuǎn)換等操作。首先對(duì)數(shù)據(jù)進(jìn)行缺失值分析與異常值分析。由于原始數(shù)據(jù)量大，而空缺值所占比例較小，對(duì)該問(wèn)題影響不大，因此對(duì)其進(jìn)行丟棄處理；由于原始數(shù)據(jù)中屬性過(guò)多，根據(jù)航空公司客戶價(jià)值相關(guān)屬性，刪除與其不相關(guān)、弱相關(guān)或冗余的屬性。例如：卡號(hào)、性別、工作地城市、工作地所在省份、年齡等屬性；最后根據(jù)方法進(jìn)行屬性約簡(jiǎn)，簡(jiǎn)化為5個(gè)屬性指標(biāo)，給定樣本的數(shù)據(jù)特點(diǎn)，從已知的樣本屬性中提煉出L、R、F、M、C五個(gè)指標(biāo)作為航空公司客戶細(xì)分的參數(shù)。L代表客戶關(guān)系長(zhǎng)度（會(huì)員入會(huì)時(shí)間距觀測(cè)窗口結(jié)束的月數(shù)），R代表客戶最近一次消費(fèi)距今時(shí)間長(zhǎng)度，F(xiàn)代表客戶在觀測(cè)時(shí)間內(nèi)的消費(fèi)頻率，M代表客戶在觀測(cè)時(shí)間內(nèi)的飛行里程，C代表客戶在觀測(cè)時(shí)間內(nèi)所乘航班的平均艙位折扣系數(shù)五個(gè)屬性維。

由于原始數(shù)據(jù)中并沒(méi)有直接給出L、R、F、M、C五個(gè)指標(biāo)，需要通過(guò)原始數(shù)據(jù)來(lái)提取這五個(gè)指標(biāo)，具體計(jì)算方法如下：

（1）L=LOAD_TIME-FFP_DATE

會(huì)員入會(huì)時(shí)間距觀測(cè)窗口結(jié)束的月數(shù)=觀測(cè)窗口結(jié)束時(shí)間-入會(huì)時(shí)間

（2）R=DAYS_FROM_LAST_TO_END

客戶最近一次消費(fèi)距今時(shí)間長(zhǎng)度=最后一次乘機(jī)時(shí)間至觀測(cè)窗口末端時(shí)長(zhǎng)

（3）F=FLIGHT_COUNT

客戶在觀測(cè)時(shí)間內(nèi)的消費(fèi)頻率=飛行次數(shù)

（4）M=SEG_KM_SUM

客戶在觀測(cè)時(shí)間內(nèi)的飛行里程=觀測(cè)窗口總飛行公里數(shù)

（5）C=AVG_DISCOUNT

客戶在觀測(cè)時(shí)間內(nèi)所乘航班的平均艙位折扣系數(shù)=平均折扣率

待分析的客戶數(shù)據(jù)被整理成如表所示。這樣每一條客戶數(shù)據(jù)就被表示成由五個(gè)特征屬性組成的向量

根據(jù)聚類結(jié)果進(jìn)行分析如下，第1類客戶入會(huì)時(shí)長(zhǎng)（L）長(zhǎng)、平均折扣率（C）較高但是乘坐的次數(shù)（F）少、飛行里程（M）較短。這類客戶是否在本航空公司消費(fèi)的不確定性較大，可能是對(duì)本航空公司沒(méi)有較為全面的認(rèn)知，無(wú)所謂選擇哪個(gè)航空公司，所以維持與此類客戶的互動(dòng)尤為重要，航空公司需要定期向此類客戶普及本公司較其他公司的優(yōu)勢(shì)，針對(duì)他們不定期的推出系列優(yōu)惠，增加此類客戶選擇本公司的次數(shù)。

第2類客戶飛行里程（M）長(zhǎng)、最近乘坐過(guò)本公司航班（R）少。這類客戶要么不選擇本公司，要選擇的話必定會(huì)給公司帶來(lái)較大的利益，是較為理想的消費(fèi)群體，因此航空公司要考慮將精力放在他們身上，一對(duì)一聯(lián)系此類客戶，了解他們不滿意的地方，及時(shí)改進(jìn)，給他們更好的乘機(jī)體驗(yàn)，提高其滿意度，客戶自然會(huì)在以后的出行時(shí)選擇本公司，持續(xù)給公司帶來(lái)較高的利益。

第3類客戶和第4類客戶的平均折扣率（C）較高、最近乘坐過(guò)本公司航班（R）少、但飛行里程（M）較短或乘坐的次數(shù)（F）少。這類客戶需要航空公司發(fā)掘其潛在價(jià)值，提高其滿意度，使得此類客戶再次或者多次選擇本公司。

第5類客戶的最近乘坐過(guò)本公司航班（R）少、里程（M）較短、乘坐的次數(shù)（F）少。這類客戶是航空公司的一般客戶或低價(jià)值客戶，可能是在航空公司打折促銷時(shí)才會(huì)乘坐該公司的航班。所以公司最好掌握此類客戶的最新信息，在出行率較高的時(shí)期，錯(cuò)開乘機(jī)高峰時(shí)段推出優(yōu)惠力度較大的航班，通過(guò)短信或者公眾號(hào)的方式告知此類客戶。

兩種不同算法的收斂性比較情況如圖，從圖中可以看出本文改進(jìn)的聚類算法比k-means算法具有更快的收斂速度。

以對(duì)航空客戶數(shù)據(jù)進(jìn)行客戶細(xì)分為主要內(nèi)容，將基于優(yōu)化初始聚類中心的加權(quán)k-means算法與傳統(tǒng)k-means算法均應(yīng)用到航空公司客戶細(xì)分上，通過(guò)數(shù)值實(shí)驗(yàn)結(jié)果，分析了客戶細(xì)分的實(shí)驗(yàn)結(jié)果，對(duì)聚類產(chǎn)生的客戶類型進(jìn)行了解釋，說(shuō)明了應(yīng)用的合理性。

[1]朱玉全,楊鶴標(biāo)等.數(shù)據(jù)挖掘技術(shù)[M].南京:東南大學(xué)出版社,2006,163-167.

[2]章兢,張小剛等.數(shù)據(jù)挖掘算法及其工程應(yīng)用[M].北京:機(jī)械工業(yè)出版社,2006,6-9.

[3]陳安,陳寧等.數(shù)據(jù)挖掘技術(shù)及應(yīng)用[M].北京:科學(xué)出版社,2006,179-190.