基于改進(jìn)的K-means算法在高校學(xué)生消費(fèi)數(shù)據(jù)中的應(yīng)用

馬幸飛，李引

（無錫商業(yè)職業(yè)技術(shù)學(xué)院教育信息化中心，江蘇無錫 214153）

基于改進(jìn)的K-means算法在高校學(xué)生消費(fèi)數(shù)據(jù)中的應(yīng)用

馬幸飛，李引

（無錫商業(yè)職業(yè)技術(shù)學(xué)院教育信息化中心，江蘇無錫 214153）

校園一卡通系統(tǒng)作為數(shù)字化校園建設(shè)的重要組成部分，集多種功能為一體，并代替?zhèn)鹘y(tǒng)的消費(fèi)管理模式，能更好處理噪聲和孤立點(diǎn)。文章采用新距離標(biāo)準(zhǔn)的K-均值算法對(duì)學(xué)生三餐消費(fèi)、商鋪營(yíng)業(yè)等情況進(jìn)行聚類分析，并將結(jié)果應(yīng)用于校內(nèi)貧困生的評(píng)定工作及經(jīng)營(yíng)單位的產(chǎn)品、服務(wù)定位。

校園一卡通；數(shù)據(jù)挖掘；聚類分析；新距離標(biāo)準(zhǔn)；K-均值算法

隨著校園信息化建設(shè)進(jìn)程的不斷發(fā)展，校園一卡通系統(tǒng)在高校中的應(yīng)用越來越成熟，數(shù)字化校園建設(shè)日益完善?！靶@一卡通”[1]基于一個(gè)數(shù)據(jù)中心集中存放所有數(shù)據(jù)，實(shí)現(xiàn)數(shù)據(jù)整合、信息共享及資源的綜合利用，同時(shí)為高校人員提供具有開放性、靈活性的管理平臺(tái)。

目前校園一卡通所覆蓋的校園業(yè)務(wù)非常廣泛，包括食堂消費(fèi)、超市消費(fèi)、醫(yī)療消費(fèi)、洗浴消費(fèi)、水果休閑吧消費(fèi)、圖書借閱等。其中食堂消費(fèi)數(shù)據(jù)最穩(wěn)定、準(zhǔn)確、全面，能夠很好地反映大學(xué)生在校的消費(fèi)行為。一卡通消費(fèi)數(shù)據(jù)均為流水?dāng)?shù)據(jù)，記錄學(xué)生在校的每一筆消費(fèi)。這些流水?dāng)?shù)據(jù)，不僅提供了學(xué)生消費(fèi)行為特征，而且反映了經(jīng)營(yíng)單位的營(yíng)業(yè)狀況。

一、數(shù)據(jù)挖掘技術(shù)

數(shù)據(jù)挖掘[2-4]是一門新興的交叉學(xué)科，從廣義上講，數(shù)據(jù)挖掘是指從大量的、不完全的、有噪聲的、模糊的實(shí)際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又具有潛在使用價(jià)值的信息和知識(shí)的過程。狹義上的數(shù)據(jù)挖掘是知識(shí)發(fā)現(xiàn)過程中的一個(gè)步驟，即利用分析工具發(fā)現(xiàn)模式的子過程。按照挖掘的知識(shí)類型分類，數(shù)據(jù)挖掘可分為特征規(guī)則挖掘、聚類規(guī)則挖掘、關(guān)聯(lián)規(guī)則挖掘等。

二、聚類分析

聚類分析[5]作為數(shù)據(jù)挖掘技術(shù)中的重要方法，是將數(shù)據(jù)對(duì)象按相似性標(biāo)準(zhǔn)劃分到不同的類或者簇的過程，使得屬于同類別的數(shù)據(jù)相似度盡量高，而不同類別的數(shù)據(jù)差異性盡量大。聚類分析是一個(gè)無監(jiān)督的學(xué)習(xí)過程，它不僅是數(shù)據(jù)挖掘的一項(xiàng)獨(dú)立工具，也是其他知識(shí)發(fā)現(xiàn)算法的預(yù)處理基礎(chǔ)。聚類分析已經(jīng)廣泛應(yīng)用于多個(gè)領(lǐng)域，包括市場(chǎng)營(yíng)銷、圖像處理、模式識(shí)別等，目前學(xué)者和專家提出了眾多的、典型的算法。例如：基于距離的K-均值和K-中心聚類算法；基于層次的凝聚和分裂算法；基于密度的DBSCAN算法；基于網(wǎng)格的STING 和CLIQUE算法等，各個(gè)獨(dú)立的算法都有其代表性。但到目前為止，仍然沒有一個(gè)通用算法，能夠同時(shí)包含超強(qiáng)的聚類能力、超高的執(zhí)行效率和簡(jiǎn)單的參數(shù)設(shè)置等優(yōu)勢(shì)。因此一般情況下，學(xué)者們會(huì)根據(jù)數(shù)據(jù)類型、簇形、噪聲、孤立點(diǎn)、高低緯度等提出不同的聚類算法，使得算法具有可伸縮性、可用性、可解釋性等特點(diǎn)。

（一）K-均值聚類算法

k-均值，也被稱為硬C-均值聚類算法[6]，是一種基于距離的劃分聚類算法，目前已在多個(gè)領(lǐng)域廣泛使用。K-均值算法的基本原則是：對(duì)于給定的數(shù)據(jù)對(duì)象集X，以數(shù)據(jù)對(duì)象到聚類中心點(diǎn)的距離和作為聚類準(zhǔn)則函數(shù)，通過求準(zhǔn)則函數(shù)的極小值方法進(jìn)行迭代，把數(shù)據(jù)對(duì)象劃分到聚類個(gè)數(shù)為c的類中，并使得每個(gè)類內(nèi)部的數(shù)據(jù)對(duì)象相似程度最大，而不同類的數(shù)據(jù)對(duì)象不相關(guān)程度最大。

（二）基于新距離的K-均值聚類算法

在基本的K-均值聚類算法的平方誤差和準(zhǔn)則函數(shù)中運(yùn)用了歐氏距離，使得其聚類過程會(huì)受到噪聲、孤立點(diǎn)數(shù)據(jù)的影響。使用已給出的一種新距離度量標(biāo)準(zhǔn)取代歐氏距離，應(yīng)用在K-均值聚類算法中，能夠適應(yīng)噪聲和孤立點(diǎn)的處理，具有較強(qiáng)的魯棒性特性，提高了整個(gè)聚類性能。

使得新目標(biāo)函數(shù)達(dá)到最小的必要條件是其中心向量公式更新為：

通過相關(guān)的仿真實(shí)驗(yàn)證明：不同于基本HCM聚類算法，AHCM聚類算法對(duì)處理具有不同大小和密度的圖形或有噪聲存在的環(huán)境數(shù)據(jù)，有較小的誤差。

三、實(shí)驗(yàn)與結(jié)論

（一）校園消費(fèi)數(shù)據(jù)預(yù)處理

學(xué)生在校消費(fèi)的特點(diǎn)存在實(shí)時(shí)性、冗余性，而且易使校園一卡通消費(fèi)數(shù)據(jù)大量存儲(chǔ)在數(shù)據(jù)庫(kù)中，長(zhǎng)期積累下來，這些數(shù)據(jù)往往是含噪聲、空值、孤立點(diǎn)等，不適合直接進(jìn)行數(shù)據(jù)分析，挖掘內(nèi)部規(guī)則，需要對(duì)原始數(shù)據(jù)進(jìn)行選擇、清洗、轉(zhuǎn)換等預(yù)處理來保證數(shù)據(jù)的準(zhǔn)確和完整。

一卡通消費(fèi)數(shù)據(jù)均為流水?dāng)?shù)據(jù)，實(shí)時(shí)記錄學(xué)生在校的每一筆消費(fèi)，包括學(xué)生學(xué)號(hào)、姓名、消費(fèi)日期、當(dāng)前消費(fèi)金額、消費(fèi)類型、消費(fèi)檔口名稱等信息。以無錫商業(yè)職業(yè)技術(shù)學(xué)院為例，校園一卡通后臺(tái)程序代碼運(yùn)行在校內(nèi)虛擬服務(wù)器的Oracle數(shù)據(jù)庫(kù)上，每天產(chǎn)生的實(shí)時(shí)數(shù)據(jù)量達(dá)到十萬(wàn)以上。因此為了得到一個(gè)好的聚類結(jié)果，針對(duì)流水?dāng)?shù)據(jù)選擇能夠反映學(xué)生消費(fèi)行為特征的關(guān)鍵字段作為原始數(shù)據(jù)，同時(shí)可以設(shè)置數(shù)據(jù)的時(shí)間等約束條件。

（二）新算法應(yīng)用到高校學(xué)生消費(fèi)數(shù)據(jù)中的結(jié)果對(duì)比與分析

本實(shí)驗(yàn)采用的軟件環(huán)境：開發(fā)平臺(tái)使用Matlab7.9，在Windows8操作系統(tǒng)下完成。硬件環(huán)境：CPU Inter(R)Core(TM)i5-4570，4GB內(nèi)存。

本論文的實(shí)驗(yàn)數(shù)據(jù)集來源于無錫商業(yè)職業(yè)技術(shù)學(xué)院一卡通數(shù)據(jù)平臺(tái)，其中學(xué)生三餐消費(fèi)數(shù)據(jù)以數(shù)字媒體學(xué)院14級(jí)學(xué)生的3月份早、中、晚餐消費(fèi)情況為研究樣本，校內(nèi)商鋪營(yíng)業(yè)數(shù)據(jù)以全校師生的3月、11月、12月的消費(fèi)情況為研究樣本。具體實(shí)驗(yàn)參數(shù)設(shè)置如表1所示。

仿真實(shí)驗(yàn)一，用學(xué)生三餐消費(fèi)數(shù)據(jù)集比較兩種算法（K-均值算法、改進(jìn)的K-均值算法）在聚類上的性能，其中目標(biāo)函數(shù)分別選用公式（1）和（3），各運(yùn)行100次，實(shí)驗(yàn)結(jié)果取目標(biāo)函數(shù)、類內(nèi)距離及運(yùn)行時(shí)間三項(xiàng)指標(biāo)的平均值，所得的結(jié)果如表2所示。

從表2可以看出：數(shù)字媒體學(xué)院2014級(jí)學(xué)生三餐消費(fèi)數(shù)據(jù)使用新距離標(biāo)準(zhǔn)進(jìn)行聚類，相較于基本K-均值算法得出的目標(biāo)函數(shù)值小，且聚類之間差異性較大；兩種算法收斂速度都很快，能達(dá)到相同的量級(jí)。

表1 實(shí)驗(yàn)數(shù)據(jù)集簡(jiǎn)單描述及參數(shù)設(shè)置

表2 數(shù)字媒體學(xué)院2014級(jí)學(xué)生三餐消費(fèi)數(shù)據(jù)的聚類結(jié)果對(duì)比

圖1 校內(nèi)商鋪營(yíng)業(yè)數(shù)據(jù)聚類結(jié)果比較

圖2 校內(nèi)商鋪營(yíng)業(yè)數(shù)據(jù)改進(jìn)的聚類結(jié)果分析

改進(jìn)的K-均值算法把學(xué)生三餐消費(fèi)分成五類時(shí)，付出的時(shí)間代價(jià)不高，得到的聚類中心也最符合實(shí)際。將此聚類效果應(yīng)用于數(shù)字媒體學(xué)院2014級(jí)的貧困生評(píng)定工作，如果某學(xué)生的早、中、晚餐消費(fèi)均值金額分別為4.63元、6.88元、4.29元，與聚類中心最低類（3.5438，7.3606，4.9365）距離最近，那么該學(xué)生可評(píng)定為特困生。因此，聚類效果可以為相關(guān)部門學(xué)生資助工作提供決策依據(jù)，并實(shí)現(xiàn)有效監(jiān)管。

仿真實(shí)驗(yàn)二，兩種算法應(yīng)用于校內(nèi)商鋪營(yíng)業(yè)數(shù)據(jù)集，其聚類結(jié)果比較如圖1所示。

從圖1、圖2可以看出：各算法所得出的聚類中心點(diǎn)代表該類別商鋪營(yíng)業(yè)的均值水平，其中改進(jìn)的K-均值聚類中心較符合實(shí)際情況。如一餐廳三樓炒菜、砂鍋，二餐廳二樓麻辣燙三個(gè)窗口的消費(fèi)均值分別為9.29元、8.87元及9.21元，這三個(gè)窗口歸類于高消費(fèi)窗口較為合適。

四、結(jié)論

在基本K-均值算法中，新的度量標(biāo)準(zhǔn)取代歐幾里得標(biāo)準(zhǔn)，仿真實(shí)驗(yàn)證明新度量標(biāo)準(zhǔn)的健壯性。本文基于高校學(xué)生消費(fèi)數(shù)據(jù)，利用數(shù)據(jù)挖掘技術(shù)，對(duì)消費(fèi)群體進(jìn)行聚類分析，將結(jié)果應(yīng)用于校內(nèi)貧困生的評(píng)定工作，為相關(guān)部門提供學(xué)生資助的輔助管理決策依據(jù)，實(shí)現(xiàn)有效監(jiān)管。同時(shí)，依據(jù)各商鋪的營(yíng)業(yè)月均值數(shù)據(jù)，分析各商鋪窗口的營(yíng)業(yè)狀況，幫助商鋪合理定位，為提高服務(wù)質(zhì)量提供數(shù)據(jù)依據(jù)。

[1]劉志龍.校園一卡通數(shù)據(jù)分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].上海：華東師范大學(xué),2007.

[2]Jiawei Han,Micheline Kamber.Data Mining：Concepts and Techniques[M].Morgan Kaufmann Publishers,2007.

[3]梁循.數(shù)據(jù)挖掘算法與應(yīng)用[M].北京：北京大學(xué)出版社，2006.

[4]朱明.數(shù)據(jù)挖掘[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2008.

[5]Everitt B.,Landau S.,Leesse M.Cluster Analysis[M]. London,2001.

[6]Sulaiman,S.N Adaptive fuzzy-K-means clustering algorithmforimagesegemen-tation[C].IEEE Transactions on Consumer Elect-ronics,2010（4）：2661-2668.

[7]Wu Kuo-lung,YangMiinshen.Alternative c-means clustering algorithms[J].Pattern Recognition，2002（35）：2267-2278.

（編輯：林鋼）

Application of Campus card Consumption data based on Improved K-means Algorithm

MA Xing-feiLI Yin
（Educational Informatization Centre，Wuxi Institute of Commerce,Wuxi 214153，china）

As an important part of digital urban construction,campus card system is more and more to a wide range,through the effective integration of various resources.It has replaced the traditional consumption management pattern.The paper proposes a novel K-means clustering algorithm based on a new metric,which canθenhance the ability of dealing with the abnormal data.This algorithm has been adopted in analysis of students'consuming data and business data.It can provide scientific and effective data in proverty stricken students'assessment system and the product orientation process.

campus card system；Data mining;cluster analysis;a new metric；K-means clustering algorithm

G 647.4

A

1671-4806（2016）06-0082-04

2016-10-10

無錫商業(yè)職業(yè)技術(shù)學(xué)院教科研課題（SYKJ15B13）

馬幸飛（1982—），男，江蘇宜興人，助理實(shí)驗(yàn)師，研究方向計(jì)算機(jī)系統(tǒng)設(shè)計(jì)、信息化管理；李引（1987—），女，安徽碭山人，助理實(shí)驗(yàn)師，碩士，研究方向計(jì)算機(jī)系統(tǒng)設(shè)計(jì)、數(shù)據(jù)分析。