馬幸飛，李引

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

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

馬幸飛，李引

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

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

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

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

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

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

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

二、聚類分析

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

（一）K-均值聚類算法

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

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

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

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

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

三、實驗與結(jié)論

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

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

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

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

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

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

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

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

表1 實驗數(shù)據(jù)集簡單描述及參數(shù)設(shè)置

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

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

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

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

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

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

四、結(jié)論

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

[1]劉志龍.校園一卡通數(shù)據(jù)分析系統(tǒng)的設(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].合肥：中國科學(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—），男，江蘇宜興人，助理實驗師，研究方向計算機系統(tǒng)設(shè)計、信息化管理；李引（1987—），女，安徽碭山人，助理實驗師，碩士，研究方向計算機系統(tǒng)設(shè)計、數(shù)據(jù)分析。