基于馬爾科夫模型的就餐人數(shù)預測①

徐彭娜, 林志興, 林 劼, 江育娥(福建師范大學 軟件學院, 福州 35008)(福建三明學院 現(xiàn)代教育技術(shù)中心, 三明 365004)

基于馬爾科夫模型的就餐人數(shù)預測①

徐彭娜1, 林志興2, 林 劼1, 江育娥11(福建師范大學 軟件學院, 福州 350108)2(福建三明學院 現(xiàn)代教育技術(shù)中心, 三明 365004)

準確預測就餐人數(shù)能夠降低學校食堂的運行成本, 提高學生對食堂的滿意度. 根據(jù)校園一卡通的消費情況, 提出一種基于馬爾科夫模型的就餐人數(shù)預測研究方法. 首先, 通過計算早餐就餐行為得到初始概率; 其次,分別通過計算早、午餐和午、晚餐就餐行為得到早餐午餐概率轉(zhuǎn)移矩陣和午餐晚餐概率轉(zhuǎn)移矩陣; 最后, 根據(jù)初始概率和概率轉(zhuǎn)移矩陣構(gòu)建的模型預測三餐的就餐人數(shù). 該方法的就餐人數(shù)預測的平均預測誤差率為1.31%, 具有良好的預測效果. 實驗結(jié)果表明, 該方法能夠反映學生的就餐行為, 從而可以為學校后勤部門提供一些參考意見, 有助于學校的建設和管理也有助于滿足學生的需要.

數(shù)據(jù)挖掘; 馬爾科夫模型; 就餐人數(shù); 預測; 概率轉(zhuǎn)移矩陣

數(shù)字化校園發(fā)展迅速, 其中校園一卡通系統(tǒng)是其重要的組成部分[1]. 校園一卡通憑借一卡多用、圈存消費、實時管理、數(shù)據(jù)共享等特征, 已成為學生、老師不可或缺的使用工具, 成為學校不可或缺的管理工具.大量用戶使用一卡通就餐、洗浴、出勤、借書等, 每天都將產(chǎn)生大量流水數(shù)據(jù). 其中就餐數(shù)據(jù)是最易獲取且最具有代表性的數(shù)據(jù). 校園一卡通還與校園的相關(guān)系統(tǒng)相結(jié)合[2], 如校園網(wǎng)的繳費、消費等. 所以, 如何從海量就餐數(shù)據(jù)中挖掘出能給予學校、老師、后勤部門有用的信息具有實際意義.

目前一卡通數(shù)據(jù)多采用聚類[3]、關(guān)聯(lián)規(guī)則、決策樹、數(shù)據(jù)倉庫等方法, 對數(shù)據(jù)進行統(tǒng)計分析處理. 但是一卡通數(shù)據(jù)在預測方面多數(shù)處于理論層面的描述, 實際的具體實現(xiàn)比較少. 本文通過對傳統(tǒng)一卡通數(shù)據(jù)進行數(shù)據(jù)統(tǒng)計分析, 在挖掘過程中采用基于馬爾科夫模型(Markov Model)對就餐人數(shù)進行預測研究. 即通過計算早餐的初始概率、早餐午餐概率轉(zhuǎn)移矩陣和午餐晚餐概率轉(zhuǎn)移矩陣, 在已有數(shù)據(jù)的基礎(chǔ)上預測校園內(nèi)早、中、晚餐的就餐總?cè)藬?shù). 馬爾科夫模型能較好的預測就餐人數(shù), 為學校后勤提供決策支持, 有效的防止供餐不足或過多剩余的現(xiàn)象; 對早、中、晚的人數(shù)預測, 能夠結(jié)合用戶或?qū)W校的其他數(shù)據(jù), 為之后更具體的學生行為分析提供借鑒和實驗基礎(chǔ).

本文總共分為四個部分. 第一部分介紹了校園一卡通的相關(guān)工作和近年來的成果; 第二部分詳細介紹了馬爾科夫的概念和用于就餐預測研究的馬爾科夫模型; 第三部分介紹了使用某高校的校園一卡通就餐流水數(shù)據(jù)的預測實驗和實驗結(jié)果; 第四部分是對本文的總結(jié).

1 相關(guān)研究

數(shù)據(jù)挖掘在校園一卡通數(shù)據(jù)上的理論分析和技術(shù)研究日益成熟. 研究的相關(guān)問題有: 消費行為如食堂就餐、熱水使用情況、水電費管理等; 教學輔助如貧困生補助、勵志獎學金評比、出勤率等; 行為特征分析如根據(jù)消費情況分析學生行為.

在消費行為方面, 王德才[4]使用支持向量機分類器將消費者分成三類, 在分類基礎(chǔ)上使用關(guān)聯(lián)規(guī)則分析消費行為, 了解學生的消費模式和消費類別, 對貧困生管理提供決策支持, 但是算法的效率不高,尚待優(yōu)化. 張碩[5]利用WEKA數(shù)據(jù)挖掘平臺, 使用K-Means算法和J48決策樹算法對在校就餐流水數(shù)據(jù)分析就餐周期性情況、就餐高峰、學生消費水平等情況, 有助于學校對學生的了解, 在勵志獎學金評比中做出相應的決策, 但是使用的數(shù)據(jù)較單一, 只針對消費數(shù)據(jù)進行分析. 羅華群[6]對校園一卡通的消費數(shù)據(jù)在消費時間和消費金額上的差異進行統(tǒng)計、分析, 對學校后勤部門提供決策支持, 但是在數(shù)據(jù)預處理階段沒有對異常情況進行預先處理, 這對統(tǒng)計結(jié)果產(chǎn)生一定的影響.

在教學影響方面, 歐陽圣[7]基于數(shù)據(jù)挖掘構(gòu)建一個校園行為分析系統(tǒng), 結(jié)合聚類方法對學生行為統(tǒng)計分析, 將理論應用于實踐, 并反作用于理論, 但是分析結(jié)果的準確性不夠理想. 陳建兵[8]使用關(guān)聯(lián)規(guī)則的方法對數(shù)據(jù)進行分析貧困學生的消費情況、參與勤工助學活動、學習成績之間的關(guān)系, 給學校和學生部門提供了決策支持, 但是在分析過程中只使用少量數(shù)據(jù),有一定的局限性. 李齊光[9]發(fā)明了一種基于一卡通消費行為分析識別經(jīng)濟困難生的方法和裝置, 通過數(shù)據(jù)統(tǒng)計等技術(shù)手段識別經(jīng)濟困難生, 以便于為經(jīng)濟困難生提供生活幫助,提高經(jīng)濟困難生判斷的客觀性, 減少人為主觀判斷, 并減少復雜的申請程序, 真正把幫助落實到經(jīng)濟有困難的學生上.

在行為分析方面, Fan[10]根據(jù)所收集的信息數(shù)字化校園卡, 提出一個基于網(wǎng)絡探索學生成就和其研究伙伴關(guān)系的方法, 結(jié)果表明, 優(yōu)秀學生的學習有更多樣化的成果, 更擅長與同學們合作學習, 通過優(yōu)秀學生的行為給學校的教學決策提供支持. 徐劍[11]對大學生的消費習慣進行聚類,將消費水平分為三類, 從早餐就餐情況判定學生的消費習慣是否具有不規(guī)律性, 將學生的成績, 消費習慣和學生的消費水平進行關(guān)聯(lián)性分析, 結(jié)論表明學生成績與消費習慣有一定關(guān)系, 為教學老師提供決策支持, 但由于學生的行為多樣化, 僅僅分為三類不能夠充分體現(xiàn)學生行為的特征.

綜上所述, 在校園一卡通數(shù)據(jù)的統(tǒng)計分析以及系統(tǒng)的理論和實現(xiàn)上都頗有成果, 但是在數(shù)據(jù)預測方面的研究還是比較少的. 本文提出基于馬爾科夫模型,預測高校就餐人數(shù), 給學校相關(guān)部門提供決策支持.

2 基于馬爾科夫模型的就餐預測研究

2.1 馬爾科夫模型

給定離散時間ti+1∈T, {0＜=t1＜t2＜...＜tn∈T} 和離散狀態(tài)空間Ii+1, {I0, I1, …, It+1∈I}, 設有隨機過程Xt+1, {Xt, t∈T}, 其Xt+1時刻的條件概率如公式(1)所示:

符合公式(1)的隨機過程被稱為馬爾科夫鏈. 馬爾科夫鏈主要用于離散變量的隨機模擬, 在實際中有著廣泛的應用[12].

公式(2)表示了馬爾科夫鏈{Xt, t∈T}在時刻t向時刻t+1變化的一階轉(zhuǎn)移概率.

其中, i, j∈I, 條件概率P{Xt+1=j|Xt=i}表示在時刻t發(fā)生i事件的條件下(當前狀態(tài)), t+1時刻發(fā)生j事件的概率(將來狀態(tài)), 這里假設t+1時刻事件j發(fā)生概率只與t時刻事件i發(fā)生概率有關(guān), 與已過去的其他時刻的事件無關(guān). 假設已知t時刻過程概率為Si(t), 那么第t+1時刻發(fā)生j事件的概率為Sj(t+1), 公式如下所示:

公式(3)中, k表示集合I的事件個數(shù). 對于t時刻的事件集合I的過程概率向量S(t)=(S1(t), S2(t),…, Sk(t)),有S(t+1)=S(t)P, 其中P為一階概率轉(zhuǎn)移矩陣[13].

使用馬爾科夫模型的前提條件是, 在任何期間或任何狀態(tài)下, 變量的下一個期間或下一個狀態(tài)的轉(zhuǎn)移概率是符合某一概率分布的隨機值, 下一個狀態(tài)僅僅依賴于最近期間的狀態(tài), 而不依賴于在此之前的狀態(tài). 2.2 馬爾科夫模型就餐預測研究

馬爾科夫模型體現(xiàn)馬爾科夫性質(zhì), 滿足t+1時刻系統(tǒng)狀態(tài)的概率分布只與t時刻的狀態(tài)有關(guān), 與t時刻以前的狀態(tài)無關(guān). 文獻[14]證實了午餐消費和晚餐消費具有較強的正相關(guān)性, 即午餐是否就餐的行為只與早餐有關(guān), 晚餐是否就餐的行為只與午餐的行為有關(guān).就餐類型分為三類: 早餐、午餐、晚餐, 用A、B、C依次表示早、午、晚有就餐行為, a、b、c依次表示早、午、晚的無就餐行為. 馬爾科夫過程中, 某過程的狀態(tài)根據(jù)一定的概率分布在各個狀態(tài)間轉(zhuǎn)換, 未來時間的狀態(tài)是不確定的, 一卡通用戶就餐行為可以認為在特定餐(如早中晚餐)的就餐狀態(tài)(用餐/不用餐)與下一餐的就餐狀態(tài)之間的轉(zhuǎn)移, 這樣的狀態(tài)轉(zhuǎn)移是完全隨機的, 因此應用馬爾科夫模型可以較好地表示一卡通用戶的就餐行為.

公式(5)和公式(6)是一階概率轉(zhuǎn)移矩陣. 其中公式(5)中表示訓練集中每個用戶星期i的早餐午餐概率轉(zhuǎn)移矩陣, 公式(6)中表示訓練集中每個用戶星期i的午餐晚餐概率轉(zhuǎn)移矩陣.

以上介紹的條件概率和概率轉(zhuǎn)移矩陣是預測模型的基礎(chǔ). 選取模擬隨機值r, 應用r對是否就餐進行模擬預測.

模擬方法如下:

(1) 在直線上將[0,1]區(qū)間劃分成兩個子區(qū)間, 其分點記為p, p為就餐概率. 如下所示.

(2) 在計算機上取隨機模擬值r.

(3) 判定r在x軸上所落的位置, 若r∈[0,p],則可以認為有就餐行為.

午餐預測方法: 根據(jù)預測的早餐就餐行為和隨機模擬值r2來預測午餐的就餐行為, 若早餐的就餐類型為A, 此時p=（AB）, 當r2＜p時預測午餐有就餐行為,反之則無, 若早餐的就餐類型為a, 此時p=(aB), 當r2＜p時預測午餐有就餐行為, 反之則無.

晚餐預測方法: 根據(jù)預測的午餐就餐行為和隨機模擬值r3來預測晚餐的就餐行為, 若午餐的就餐類型為B, 此時p=（BC）, 當r3＜p時預測晚餐有就餐行為,反之則無, 若午餐的就餐類型為b, 此時p=(bC), 當r3＜p時預測晚餐有就餐行為, 反之則無.

統(tǒng)計真實值與預測集的早、午、晚就餐人數(shù)數(shù)量,計算就餐總?cè)藬?shù)誤差率.

3 實驗與結(jié)果分析

3.1 數(shù)據(jù)來源

本實驗采用的數(shù)據(jù)是某高校2015年12月的食堂就餐流水數(shù)據(jù)共76萬條. 經(jīng)過數(shù)據(jù)預處理, 把每個用戶的系列就餐行為提取為一個時間序列. 這些時間序列數(shù)據(jù)總條數(shù)為12442. 也即, 總?cè)藬?shù)為12442人, 其中性別為男的人數(shù)為5651, 性別為女的人數(shù)為6791.教職工人數(shù)為753, 學生11689.

3.2 數(shù)據(jù)預處理

在實驗開始之前, 需將獲取到的76萬條就餐流水數(shù)據(jù)使用數(shù)據(jù)庫和R工具對數(shù)據(jù)進行預處理. 預處理步驟如下:

① 清洗數(shù)據(jù): 將學號缺失、就餐時間不在食堂營業(yè)時間的錯誤數(shù)據(jù)剔除.

② 為早午晚三餐分段: 將6:00:00-10:00:00置為早餐時間, 如有刷卡記錄則將就餐行為置為A, 將10:00:01-15:00:00置為午餐時間, 如有刷卡記錄則將就餐類型置為B, 將15:00:01-20:00:00置為晚餐時間,如有刷卡記錄則將就餐類型置為C.

③ 記錄合并: 將同一個學號的日期相同且就餐類型也相同的記錄合并, 記作一次就餐行為(如同一天的多次早餐刷卡行為合并為一次早餐刷卡行為).

④ 形成時間序列: 將每個用戶u的無就餐行為用小寫字母(a, b, c)補全后按照時間排序形成就餐類型序列Yu, Yu={yu,1, yu,2,…,yu,t,…,yu,m}. 其中m表示用戶u共有m次就餐行為, yu,t表示用戶u的第t次就餐行為.

預處理結(jié)果為n個用戶的就餐信息MESS={mess1, mess2,…messu,…,messn}, 其中n為用戶數(shù)量, messu表示用戶u的就餐信息. messu=(stdu, Yu), 其中stdu表示用戶u的學號, Yu表示用戶u的就餐行為序列.

3.3 預測模型和預測方法

本實驗使用軟件R對數(shù)據(jù)建模進行預測. 本實驗使用一卡通的就餐流水數(shù)據(jù), 基于馬爾科夫模型對每個用戶u在星期i對就餐人數(shù)進行預測研究. 將數(shù)據(jù)的前三周的數(shù)據(jù)作為訓練集, 第四周的數(shù)據(jù)作為測試集.

使用訓練集建立模型, 具體過程如下:

① 對每一個用戶u在星期i(1≤i≤7)的基礎(chǔ)上建立7天的訓練模型;

② 從就餐行為序列Yu中提取用戶u前三周的星期i的總就餐行為構(gòu)成的時間序列集合, 作為用戶u的訓練集trainui={yu,1, yu,2,…,yu,z}, yu,z表示前三周中星期i的第z次就餐行為;

③ 根據(jù)公式(4)計算用戶u在訓練集中的初始概率;

④ 根據(jù)公式(5)、公式(6)計算概率轉(zhuǎn)移矩陣, 建立訓練模型.

具體流程如圖1所示.

圖1 基于馬爾科夫模型預測流程圖

在已有的馬爾科夫模型上, 對用戶的早餐、午餐、晚餐進行預測, 具體過程如下:

① 早餐預測: 選取一個0-1之間的隨機模擬值r1,若r1＜Pi(A), 則早餐有就餐行為, 反之則無就餐行為;

u

② 午餐預測: 選取一個0-1之間的隨機模擬值r2,根據(jù)早餐的就餐行為結(jié)果和r2來預測午餐的就餐行為,若早餐的就餐類型為A且r2＜（AB）, 則預測午餐有就餐行為, 反之則無, 若早餐的就餐類型為a且r2＜(aB), 則預測午餐有就餐行為, 反之則無;

③ 晚餐預測: 選取一個0-1之間的隨機模擬值r3,根據(jù)午餐的就餐行為結(jié)果和r3來預測晚餐的就餐行為,若午餐的就餐類型為B且r3＜(bC), 則預測晚餐有就餐行為, 反之則無, 若午餐的就餐類型為b且r3＜(bC), 則預測晚餐有就餐行為, 反之則無.

3.4 實驗結(jié)果

在實驗過程中使用隨機模擬值預測三餐就餐行為,進行 20 次實驗, 分別形成 20 組不同實驗結(jié)果, 最終的算法評價是基于這 20 組實驗結(jié)果的平均值.

本實驗采用就餐人數(shù)預測誤差率err作為預測評估指標:

其中, Pik表示預測值, TiA表示真實值, i表示星期中的某天(i=1,2,…,7), k表示就餐類型(k=A,B,C), N表示就餐總?cè)藬?shù). 平均誤差值表示真實值和預測值之間的誤差. 平均誤差率越小, 表示預測效果越準確. 就餐人數(shù)預測誤差率如表1所示.

表1 就餐人數(shù)預測誤差率表

真實值 1413 4607 5006周日預測值 1448 4371 46961.56誤差率(%)0.28 1.90 2.50平均值(%)1.04 1.33 1.57 1.31

表1描述了某高校2015年12月的星期i的三餐就餐人數(shù)的真實值和預測值, 并計算真實值和預測值之間的誤差率. 為了直觀描述在星期i的就餐人數(shù)的分布情況, 如圖2所示.

圖2 基于馬爾科夫模型預測人數(shù)對比圖

圖3 基于馬爾科夫模型預測誤差率

圖3 中橫坐標表示星期i, 縱坐標表示平均誤差率.由圖3可知, 星期一和星期三的預測誤差率偏大, 均大于2%. 經(jīng)調(diào)查表明, 星期一請假和曠課情況較多,周三下午沒有課程安排, 學生在此階段行為比較隨機,這說明周末和不排課的客觀情況會對學生就餐情況產(chǎn)

圖2中橫坐標表示星期一至星期日的真實值和預測值; 縱坐標表示就餐人數(shù). 從圖2中可以發(fā)現(xiàn)早餐的就餐人數(shù)普遍比午餐和晚餐的就餐人數(shù)低, 周末的三餐就餐人數(shù)均偏低; 預測人數(shù)與真實人數(shù)相近. 為了直觀描述預測誤差情況, 如圖3所示.生影響(也影響實驗結(jié)果).

實驗結(jié)果表明, 星期四的人數(shù)預測誤差率最小,為0.4%, 一周的平均人數(shù)預測誤差率為1.31%. 周末的就餐人數(shù)相對普遍較低, 尤其是早餐的就餐人數(shù)大大減少, 但人數(shù)穩(wěn)定, 早餐預測誤差率低, 說明周末早起人數(shù)少, 外出就餐人數(shù)多. 除去周末, 周三、周五晚餐的就餐人數(shù)相對較少, 調(diào)查表明周三下午沒有安排課程, 周五晚上課程安排的較少, 部分學生在周五晚上開啟“周末模式”, 即和周末行為相似.

本文對就餐人數(shù)的總體預測, 在用戶總數(shù)為12442人的情況下, 平均誤差總?cè)藬?shù)僅為160人左右,這可以為學校食堂的后勤提供很大的備貨依據(jù)和備餐依據(jù), 有效的防止供餐不足或過多剩余的現(xiàn)象; 對早、中、晚的人數(shù)預測, 能夠結(jié)合用戶的其他屬性, 為之后更具體的學生行為分析提供借鑒和實驗基礎(chǔ).

4 總結(jié)

本文對一卡通數(shù)據(jù)采用了基于馬爾科夫模型的就餐人數(shù)預測研究. 通過對用戶的前三周就餐數(shù)據(jù)計算概率建立訓練模型, 預測第四周的就餐行為, 預測就餐總?cè)藬?shù)和預測早、中、晚餐人數(shù). 實驗結(jié)果表明, 基于馬爾科夫模型的就餐數(shù)據(jù)預測模型平均誤差率為1.31%, 平均早餐預測誤差率為1.04%, 平均午餐預測誤差率為1.33%, 平均晚餐預測誤差率為1.57%, 預測結(jié)果較為準確. 準確的預測能更好地為學校食堂的后勤提供很大的備貨依據(jù)和備餐依據(jù), 有效的防止供餐不足或過多剩余的現(xiàn)象; 對早、中、晚的人數(shù)預測, 能夠結(jié)合用戶的其他屬性, 為之后更具體的學生行為分析提供借鑒和實驗基礎(chǔ). 但由于只有就餐數(shù)據(jù), 存在數(shù)據(jù)單一的缺點[15], 如何進行更全面的學生行為分析是下一步要做的工作.

1 Feng JW. Study on the campus smart card system based on SaaS. International Conference on Information Sciences. Machinery, Materials and Energy. 2015.

2 Shi Q, Qian Y, Gong Y, et al. The analysis and data mining of students’ oline data based on digital campus. Applied Mechanics & Materials, 2013, 397-400: 2326–2329.

3 Shi Q, Xu L, Shi Z, et al. Analysis and research of the campus network user’s behavior based on k-means clustering algorithm. International Conference on Digital Manufacturing & Automation. IEEE Computer Society. 2013. 196–201.

4 王德才.數(shù)據(jù)挖掘在校園卡消費行為分析中的研究與應用[學位論文].哈爾濱:哈爾濱工程大學,2010.

5 張碩.基于WEKA的校園一卡通數(shù)據(jù)挖掘與分析[學位論文].武漢:華中師范大學,2014.

6 羅華群.校園一卡通數(shù)據(jù)的挖掘與應用[學位論文].上海:華東師范大學, 2009.

7 歐陽圣.數(shù)據(jù)挖掘在消費行為分析中的應用[學位論文].長沙:湖南大學, 2011.

8 陳建兵.利用校園一卡通數(shù)據(jù)優(yōu)化高校貧困生認定系統(tǒng)[學位論文].成都:成都電子科技大學,2012.

9 李齊光,張平,趙鑫.基于一卡通消費行為分析識別經(jīng)濟困難生的方法和裝置,2014.

10 Fan S, Li P, Liu T, et al. Population behavior analysis of Chinese university students via digital campus cards. IEEE International Conference on Data Mining Workshop. IEEE. 2015. 72–77.

11 徐劍.基于一卡通數(shù)據(jù)的消費行為與成績的關(guān)聯(lián)性研究分析[碩士學位論文].南昌:南昌大學,2011.

12 Ching WK, Ng MK. Markov Chains: Models, Algorithms and Applications. Springer Berlin, 2012, 83(483): xiv.

13 韓忠明,張晨,李斌.基于Markov模型的異常用戶檢測.計算機仿真,2014,31(6):316–320.

14 馬千.基于校園卡消費流水數(shù)據(jù)的大學生就餐行為分析[碩士學位論文].長春:東北師范大學,2015.

15 金培莉,王曉震.校園一卡通系統(tǒng)決策支持實例分析.華東師范大學學報(自然科學版),2015(S1):525–529.

Repast Number Prediction Based on Markov Model

XU Peng-Na1, LIN Zhi-Xing2, LIN Jie1, JIANG Yu-E11(Faculty of Software, Fujian Normal University, Fuzhou 350108, China)2(Center of Modern Education Technology, Sanming University, Sanming 365004, China)

To predict the repast number accurately can reduce the cost of school canteen and improve students’satisfaction. A novel method based on Markov model to predict repast number is proposed according to the consumption situation of campus card system. Firstly, an initial probability is obtained by calculating the eating behavior of breakfast. Secondly, two transfer probability matrices are computed, one is the transfer probability between the behaviors of students having breakfast and having lunch; the other is the transfer probability between the behaviors of students having lunch and having supper. Finally, a Markov model is constructed according to the initial probability and the two probability transfer matrices to forecast the number of diners. The average prediction error of the proposed method is 1.31%, which has a good prediction performance. The experimental results show that the proposed Markov method can capture the students’ dining behavior accurately. It may provide valuable information for the school logistics department, contribute to the construction and management of school and meet the needs of students better.

data mining; Markov models; repast number; prediction; transfer probability matrix

福建省自然科學基金(2014J01220);三明學院科研基金(B201201/G);福建省教育廳科技基金(JB13187)

2016-08-01;收到修改稿時間:2016-08-29

10.15888/j.cnki.csa.005685