李 慧，王國(guó)強(qiáng)，郭瑞強(qiáng)，高靜偉，暴延敏

?

教學(xué)評(píng)價(jià)數(shù)據(jù)的離群點(diǎn)檢測(cè)算法研究

李 慧1,2，王國(guó)強(qiáng)1，郭瑞強(qiáng)1,2，高靜偉1，暴延敏1,2

(1. 河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，石家莊 050024； 2. 河北省計(jì)算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室(河北師范大學(xué))，石家莊 050024)

教學(xué)評(píng)價(jià)是大學(xué)教學(xué)活動(dòng)中不可缺少的環(huán)節(jié),可能出現(xiàn)故意抬高或壓低評(píng)分及虛假評(píng)分的現(xiàn)象，應(yīng)該找出這些離群數(shù)據(jù)并加以清除，以提高學(xué)生評(píng)教數(shù)據(jù)的正確性。離群點(diǎn)檢測(cè)問(wèn)題是數(shù)據(jù)挖掘技術(shù)的重要研究領(lǐng)域之一，本文實(shí)驗(yàn)所用教學(xué)評(píng)價(jià)數(shù)據(jù)屬于分類型數(shù)據(jù)，目前針對(duì)分類型數(shù)據(jù)的離群點(diǎn)檢測(cè)算法常用的有基于信息熵的貪婪算法和基于頻率的AVF算法。針對(duì)貪婪算法時(shí)間復(fù)雜度較高，AVF算法不夠準(zhǔn)確的問(wèn)題，本文提出一種改進(jìn)的基于頻率的離群點(diǎn)檢測(cè)算法。本文算法首先采用改進(jìn)的k-modes算法對(duì)教學(xué)評(píng)價(jià)數(shù)據(jù)進(jìn)行聚類，并提出應(yīng)用調(diào)整的余弦相似度公式作為相似性度量，篩選出遠(yuǎn)離簇中心的候選離群點(diǎn)，最后通過(guò)基于頻率的離群點(diǎn)檢測(cè)算法對(duì)候選集進(jìn)行檢測(cè)。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明算法在精確度和效率方面均具有優(yōu)勢(shì)。

離群點(diǎn)檢測(cè)；k-modes聚類；余弦相似度；分類型數(shù)據(jù)

0 引言

近年來(lái)，在教育信息化、遠(yuǎn)程教育和Web 2.0等應(yīng)用的帶動(dòng)下,教育數(shù)據(jù)挖掘（educational data mining，簡(jiǎn)稱 EDM）開(kāi)始受到越來(lái)越多的研究者的關(guān)注[1-4]。教育數(shù)據(jù)挖掘技術(shù)綜合應(yīng)用教育學(xué)、計(jì)算機(jī)科學(xué)、心理學(xué)和統(tǒng)計(jì)學(xué)等多個(gè)學(xué)科的理論和技術(shù)來(lái)解決教育研究與教學(xué)實(shí)踐中的問(wèn)題，通過(guò)分析和挖掘教育相關(guān)的數(shù)據(jù)，EDM技術(shù)可以發(fā)現(xiàn)和解決教育中的各類問(wèn)題，如輔助管理人員做出決策、幫助教師改進(jìn)課程以及提高學(xué)生的學(xué)習(xí)效率等[5]。比如Jingyi Luo，Shaymaa E.Sorour等人利用每節(jié)課下課時(shí)同學(xué)們寫(xiě)下的評(píng)論內(nèi)容，進(jìn)行學(xué)生最終成績(jī)的預(yù)測(cè)[6]；K. juszczyszyn和A. Prusiewicz Surjeet等人，利用學(xué)生選課數(shù)據(jù)，結(jié)合社會(huì)網(wǎng)絡(luò)構(gòu)造方法，構(gòu)造學(xué)生選課網(wǎng)絡(luò)，進(jìn)行學(xué)生選課的推薦[7]；Renza Campagni，Donatella Merlini等人利用聚類和序列模式挖掘方法研究由學(xué)生自己安排的課程考試順序?qū)ζ渥罱K畢業(yè)成果之間的影響，以給學(xué)生提供更好的學(xué)習(xí)策略，同時(shí)利用挖掘結(jié)果給提供更加合理的課程安排[8]。

教學(xué)評(píng)價(jià)是大學(xué)教學(xué)活動(dòng)中不可缺少的環(huán)節(jié)，學(xué)生的評(píng)教效果依賴于學(xué)生對(duì)評(píng)教的態(tài)度和學(xué)生對(duì)教師的態(tài)度，學(xué)生評(píng)教過(guò)程中，如果學(xué)生評(píng)教態(tài)度不認(rèn)真，或者學(xué)生存在偏見(jiàn)必然會(huì)扭曲評(píng)教結(jié)果，因而會(huì)出現(xiàn)故意抬高或壓低評(píng)分及虛假評(píng)分的現(xiàn)象，從而出現(xiàn)評(píng)教的離群數(shù)據(jù)，在學(xué)生評(píng)教過(guò)程中，應(yīng)該找出這些離群數(shù)據(jù)并加以清除，以提高學(xué)生評(píng)教數(shù)據(jù)的正確性。同時(shí)由于教學(xué)評(píng)價(jià)數(shù)據(jù)由學(xué)生主觀評(píng)價(jià)得到，所以可以利用教學(xué)評(píng)價(jià)數(shù)據(jù)進(jìn)行特殊學(xué)生的發(fā)現(xiàn)，進(jìn)一步研究特殊學(xué)生的特征與表現(xiàn)，因此，對(duì)于教學(xué)評(píng)價(jià)數(shù)據(jù)的離群點(diǎn)檢測(cè)方法的研究具有重要意義。

離群點(diǎn)挖掘可揭示稀有事件和現(xiàn)象、發(fā)現(xiàn)有趣的模式，有著廣闊的應(yīng)用前景，因此引起廣泛關(guān)注[9]。離群點(diǎn)檢測(cè)亦稱為離群點(diǎn)挖掘，是數(shù)據(jù)挖掘的主要任務(wù)之一，其目的是消除噪聲或發(fā)現(xiàn)潛在的、有意義的知識(shí)，廣泛運(yùn)用在網(wǎng)絡(luò)入侵檢測(cè)、欺詐檢測(cè)、醫(yī)療診斷等領(lǐng)域中[10]。本文研究分類型數(shù)據(jù)的離群點(diǎn)檢測(cè)算法及其在大學(xué)教學(xué)評(píng)價(jià)中的應(yīng)用。

針對(duì)常用的基于頻率的分類型數(shù)據(jù)離群點(diǎn)檢測(cè)算法精確度不夠高，基于信息熵的貪婪算法時(shí)間復(fù)雜度高的問(wèn)題，本文先用基于同現(xiàn)率的改進(jìn)的K-modes算法對(duì)數(shù)據(jù)進(jìn)行聚類，去除相似度較高數(shù)據(jù)，得到候選離群點(diǎn)集合，再通過(guò)基于頻率的離群點(diǎn)算法對(duì)候選離群點(diǎn)集合進(jìn)行離群點(diǎn)挖掘，從而解決了基于頻率算法精確度不夠高的問(wèn)題。經(jīng)在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明本算法的運(yùn)行效率與貪婪算法相比較高，并能有效檢測(cè)出教學(xué)評(píng)價(jià)數(shù)據(jù)中的離群點(diǎn)數(shù)據(jù)。

1 相關(guān)工作

本文針對(duì)教學(xué)評(píng)價(jià)數(shù)據(jù)進(jìn)行離群點(diǎn)檢測(cè)，教學(xué)評(píng)價(jià)共有九項(xiàng)評(píng)價(jià)指標(biāo)，每項(xiàng)評(píng)價(jià)指標(biāo)有五種評(píng)價(jià)等級(jí)，分別是5優(yōu)秀、4良好、3中等、2及格和1不及格，屬于序數(shù)型數(shù)據(jù)，序數(shù)型數(shù)據(jù)屬于分類型數(shù)據(jù)，本文針對(duì)分類型數(shù)據(jù)的離群點(diǎn)檢測(cè)算法進(jìn)行研究。目前，針對(duì)分類型的數(shù)據(jù)，經(jīng)典的離群點(diǎn)檢測(cè)算法有基于信息熵的離群點(diǎn)檢測(cè)算法、基于頻率的離群點(diǎn)檢測(cè)算法。

1.1 基于信息熵的離群點(diǎn)檢測(cè)算法

He提出了一個(gè)基于信息熵的離群點(diǎn)檢測(cè)算法——貪心算法（Greedy Algorithm）[11]。

信息熵可用于度量數(shù)據(jù)集的無(wú)序和雜亂程度。熵值越大，說(shuō)明數(shù)據(jù)集無(wú)序和雜亂程度越高；反之，說(shuō)明數(shù)據(jù)集越有序和越純凈，無(wú)序性越高[12]。這個(gè)算法認(rèn)為，對(duì)于數(shù)據(jù)集D，如果某個(gè)對(duì)象去掉后，整個(gè)數(shù)據(jù)集的熵值變小，那么這個(gè)點(diǎn)就極有可能是離群點(diǎn)。每次找出一個(gè)使得熵值變小幅度最大的點(diǎn)，然后從D中去除，再繼續(xù)查找下一個(gè)使得熵值變小幅度最大的點(diǎn)，直到找到需要的n個(gè)離群點(diǎn)?；谛畔㈧氐呢澬乃惴?，如果要求查找n個(gè)離群點(diǎn)，那么就需要掃描整個(gè)數(shù)據(jù)集n+l遍，第一遍統(tǒng)計(jì)每個(gè)屬性值的分布和值域，之后需要查找出n個(gè)離群點(diǎn)，因此，需要再掃描n遍，假設(shè)用N表示數(shù)據(jù)集中數(shù)據(jù)的個(gè)數(shù)，P表示數(shù)據(jù)的屬性特征的個(gè)數(shù)，時(shí)間復(fù)雜度為O（n*N*P）。在需要查找的離群點(diǎn)數(shù)目非常大時(shí)，貪心算法時(shí)間復(fù)雜度比較大。

1.2 基于頻率的離群點(diǎn)檢測(cè)算法

Koufakou提出了一個(gè)用屬性值的頻數(shù)直接計(jì)算離群因子的方法[13]。算法定義每個(gè)數(shù)據(jù)對(duì)象的離群因子用AVF（Attribute Value Frequency）表示，計(jì)算公式如公式（1）所示，該算法計(jì)算數(shù)據(jù)中每一個(gè)數(shù)據(jù)對(duì)象的AVF值，數(shù)據(jù)對(duì)象的AVF值越低，其為離群點(diǎn)的可能性越大。

基于頻率的離群點(diǎn)檢測(cè)算法假設(shè)所有屬性都是相互獨(dú)立的。對(duì)每個(gè)屬性分別進(jìn)行計(jì)算，并不考慮不同屬性相互之間的關(guān)系。如果是由幾個(gè)屬性值共同作用的離群點(diǎn)，那么基于頻率的離群點(diǎn)檢測(cè)方法就存在不足，如表1中的示例數(shù)據(jù)所示。

表1 示例數(shù)據(jù)

Tab.1 Sample Data

從表1中可以明顯看出，第5條記錄與其它記錄并不相同。但是如果用基于頻率的算法檢測(cè)，得到的結(jié)果如表2所示。

表2 頻率計(jì)算結(jié)果

Tab.2 Based on the frequency of the results of the algorithm

表2為根據(jù)表1中的數(shù)據(jù)計(jì)算出的頻率結(jié)果，可以看出第五條記錄的頻率值要高于另外四個(gè)記錄的頻率值，按照AVF算法的思想，第五條記錄無(wú)法被檢測(cè)出來(lái)。

2 改進(jìn)的基于頻率的離群點(diǎn)挖掘算法

2.1 算法的基本思路

針對(duì)上述基于頻率的離群點(diǎn)檢測(cè)算法的不足，提出一種改進(jìn)的基于頻率的離群點(diǎn)挖掘算法，算法的主要思想是：

第一階段基于聚類的離群點(diǎn)檢測(cè)。先用聚類方法對(duì)數(shù)據(jù)進(jìn)行聚類，去除比較相似的數(shù)據(jù)。通常含有數(shù)據(jù)較少的簇被視為離群簇，因此將含有數(shù)據(jù)較少的類別從類別集合中刪去，放入候選離群點(diǎn)集。另外，在基于聚類的離群點(diǎn)檢測(cè)方法中，可以用對(duì)象與它所屬類別的簇中心的相似度來(lái)度量對(duì)象屬于簇的程度，計(jì)算簇內(nèi)數(shù)據(jù)點(diǎn)與所在類別簇中心的相似度，并計(jì)算該類別的平均相似度，如果數(shù)據(jù)點(diǎn)與所在類別簇中心的相似度小于平均相似度，說(shuō)明該數(shù)據(jù)點(diǎn)相對(duì)來(lái)說(shuō)離群度更高，將這些數(shù)據(jù)點(diǎn)同樣放入候選離群點(diǎn)集中。

第二階段基于AVF的離群點(diǎn)檢測(cè)。依據(jù)AVF算法對(duì)候選離群點(diǎn)集中的數(shù)據(jù)計(jì)算每個(gè)數(shù)據(jù)的AVF值，取最小的n個(gè)點(diǎn)放入離群點(diǎn)集中。

2.2 聚類算法的選擇

對(duì)于分類型數(shù)據(jù)來(lái)說(shuō)，k-modes算法[14]是常采用的聚類算法。k-modes算法是對(duì)k-means算法的擴(kuò)展。k-modes算法采用相異度來(lái)表示k-means算法中的距離，k-modes算法中相異度越小，距離越小。在k-modes聚類算法中，相異度度量方法采用簡(jiǎn)單的0-1方法，即對(duì)象的某一屬性與另一對(duì)象同一屬性值相同，則相異度量值為0。相反，若對(duì)象的這一屬性與另一對(duì)象的同一屬性不同，則為1。本文通過(guò)聚類實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)這種簡(jiǎn)單的0、1匹配，用于教學(xué)評(píng)價(jià)數(shù)據(jù)中并不合理，可能造成聚類結(jié)果不正確的問(wèn)題。

本文聚類實(shí)驗(yàn)使用R學(xué)院L課程的教學(xué)評(píng)分?jǐn)?shù)據(jù)，實(shí)驗(yàn)中把評(píng)分?jǐn)?shù)據(jù)（5優(yōu)秀、4良好、3中等、2及格和1不及格）簡(jiǎn)化為（5,4,3,2,1）。如下面兩個(gè)表所示，表3為聚類結(jié)果中的第一類的九項(xiàng)評(píng)分?jǐn)?shù)據(jù)，表4為聚類結(jié)果的第四類的九項(xiàng)評(píng)分的數(shù)據(jù)。表3第12條數(shù)據(jù)與類內(nèi)其他數(shù)據(jù)差距較大，而與表4的數(shù)據(jù)更加相似。第一類的聚類中心為（4,4,3,4,4,4,4,3,4），第四類的聚類中心為（3,3,3,3,4,3,3,4,3），按照0–1匹配的相異度度量方法，數(shù)據(jù)（4,3,1,2,3,2,1,1,2）與第一類聚類中心的相異度為0+1+1+1+1+1+1+1+1=8，與第四類聚類中心的相異度為1+0+1+1+1+1+1+1+1=8，這種相異度度量方式忽略了同一屬性下，不同屬性值之間的差異，得到了相同的相異度值造成了數(shù)據(jù)類別分配錯(cuò)誤。

除了簡(jiǎn)單的0、1匹配，Ahmad等人將同一屬性下的不同的屬性值之間的相異度用它們的共現(xiàn)程度（co-occurence）來(lái)反映[15]。

表3 聚類結(jié)果第一類

Tab.3 The first kind of clustering results

（2）

表4 聚類結(jié)果第四類

Tab.4 The fourth class clustering results

假設(shè)數(shù)據(jù)集的屬性個(gè)數(shù)為m，對(duì)于數(shù)據(jù)集中任意屬性的兩個(gè)不同取值x和y之間的距離可以表示為：

（4）

改進(jìn)后的距離度量可以區(qū)別同一屬性下不同屬性的差異，上述碰到的數(shù)據(jù)類別分配錯(cuò)誤問(wèn)題，根據(jù)改進(jìn)的k-modes算法的相異度計(jì)算公式計(jì)算得數(shù)據(jù)（4,3,1,2,3,2,1,1,2）與第一類聚類中心的相異度為5.2203，與第四類聚類中心的相異度為4.8631，根據(jù)計(jì)算結(jié)果數(shù)據(jù)的類別歸為第四類。經(jīng)觀察實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，改進(jìn)的k-modes算法用于本文實(shí)驗(yàn)數(shù)據(jù)的整體聚類結(jié)果比傳統(tǒng)的k-modes算法聚類效果更好，本文采用這種改進(jìn)的k-modes算法進(jìn)行聚類，k-modes算法的流程圖如圖1。

圖1 K-modes算法流程圖

2.3 調(diào)整的余弦相似度度量

余弦相似度是最常見(jiàn)的分類型數(shù)據(jù)相似度度量方式。余弦相似度（Cosine Similarity）用向量空間中兩個(gè)向量夾角的余弦值衡量?jī)蓚€(gè)個(gè)體間差異的大小。公式如下：

余弦值越接近1，就表明夾角越接近0度，也就是兩個(gè)向量越相似，余弦值越接近–1，就表明夾角越接近180度，也就是兩個(gè)向量越不相似。

這種經(jīng)典的余弦相似度用在學(xué)生教學(xué)評(píng)價(jià)數(shù)據(jù)中存在問(wèn)題，如X和Y兩個(gè)學(xué)生對(duì)教師T的兩項(xiàng)評(píng)分分別為（1,2）和（4,5），使用余弦相似度得出的結(jié)果是0.98，兩者極為相似，但從評(píng)分上看X和Y對(duì)教師T的評(píng)價(jià)相差很大，需要修正這種不合理性，

調(diào)整的余弦相似度，將所有維度上的數(shù)值都減去一個(gè)均值，比如X和Y的評(píng)分均值都是3，那么調(diào)整后為（–2,–1）和（1,2），再用余弦相似度計(jì)算，得到–0.8，相似度為負(fù)值并且差異很大，顯然更加符合現(xiàn)實(shí)，所以本文在篩選候選離群點(diǎn)時(shí)采用調(diào)整的余弦相似度作為計(jì)算數(shù)據(jù)與所在類別簇中心之間的相似度的方式。例如表3中的評(píng)教數(shù)據(jù)，簇中心的值為（4,4,3,4,4,4,4,3,4）設(shè)簇中心為c，第一行評(píng)教數(shù)據(jù)設(shè)為d，那么第一項(xiàng)評(píng)教數(shù)據(jù)與簇中心的調(diào)整的余弦相似度計(jì)算為：

表3中的各條評(píng)價(jià)數(shù)據(jù)與簇中心的調(diào)整的余弦相似度如表5。

表5 聚類結(jié)果第一類各數(shù)據(jù)與簇中心的調(diào)整的余弦相似度

Tab.5 The clustering results of the first kind of various data and the cluster center adjusted cosine similarity

簇中數(shù)據(jù)與簇中心的平均相似度為0.6135，小于平均相似度的有第2、4、11、12這四條數(shù)據(jù)，把這四條評(píng)教數(shù)據(jù)放入候選離群點(diǎn)。

2.4 算法的描述

改進(jìn)的基于頻率的離群點(diǎn)檢測(cè)算法描述如下：

輸入：數(shù)據(jù)集D，聚類個(gè)數(shù)k，離群點(diǎn)個(gè)數(shù)n，簇的大小判別閾值t

輸出：離群點(diǎn)數(shù)據(jù)集

1：將數(shù)據(jù)集D和聚類個(gè)數(shù)k，作為參數(shù)，輸入改進(jìn)的k-modes算法，對(duì)數(shù)據(jù)集D進(jìn)行聚類。

2：將聚類結(jié)果簇中數(shù)據(jù)個(gè)數(shù)小于t的放入離群點(diǎn)候選項(xiàng)集，根據(jù)公式（5）計(jì)算剩余簇中各點(diǎn)到聚類中心的調(diào)整的余弦相似度，將余弦相似度小于簇內(nèi)平均余弦相似度的點(diǎn)放入離群點(diǎn)候選項(xiàng)集。

3：根據(jù)公式（1）計(jì)算離群點(diǎn)候選項(xiàng)集中每個(gè)點(diǎn)的AVF值，先將前n個(gè)點(diǎn)按從小到大排序再?gòu)牡趎+1個(gè)數(shù)據(jù)點(diǎn)開(kāi)始查找，如果與第n個(gè)點(diǎn)相比，AVF值更不滿足離群點(diǎn)定義，就可以不與其它點(diǎn)進(jìn)行比較，依次掃描整個(gè)數(shù)據(jù)集。

4：輸出n個(gè)離群點(diǎn)。

2.5 算法分析

算法共分三個(gè)階段，第一階段通過(guò)改進(jìn)的k-modes算法進(jìn)行聚類，第二階段計(jì)算數(shù)據(jù)與簇中心之間的余弦相似度篩選候選離群點(diǎn)，第三階段用AVF方法檢測(cè)離群點(diǎn)。用n表示數(shù)據(jù)集中數(shù)據(jù)的個(gè)數(shù)，m表示數(shù)據(jù)的屬性特征的個(gè)數(shù)。第一階段對(duì)數(shù)據(jù)集進(jìn)行聚類，改進(jìn)的k-modes算法，時(shí)間復(fù)雜度為O（n*m*k*t+m2n+m2s3），其中k為聚類個(gè)數(shù)，t為迭代次數(shù)，s為每個(gè)屬性下相異屬性值的數(shù)量的平均值。第二階段的時(shí)間復(fù)雜度為O（n）。第三階段的時(shí)間復(fù)雜度為O（n*m）。因此大致時(shí)間復(fù)雜度為O（n*m）。基于信息熵的貪婪算法如果需要查找N個(gè)離群點(diǎn)，那么就需要掃描整個(gè)數(shù)據(jù)庫(kù)N+1遍，時(shí)間復(fù)雜度為O（N*n*m）。在需要查找的離群點(diǎn)數(shù)目較大時(shí)，貪心算法時(shí)間復(fù)雜度比較大。

3 實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)預(yù)處理

本研究所用的數(shù)據(jù)存儲(chǔ)在Oracle數(shù)據(jù)庫(kù)中，所用的數(shù)據(jù)涉及的表有學(xué)生信息表、學(xué)生選課表、學(xué)生評(píng)教評(píng)分表、課程信息表、教學(xué)任務(wù)表、教師信息表。這些表中的數(shù)據(jù)獨(dú)立存在，我們需要將數(shù)據(jù)整理成數(shù)據(jù)挖掘工作需要的形式，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。數(shù)據(jù)預(yù)處理工作的主要任務(wù)是對(duì)數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗、集成、變換和規(guī)范化，將數(shù)據(jù)整理成需要的格式。首先在數(shù)據(jù)庫(kù)中創(chuàng)建匯總表視圖，先對(duì)學(xué)生信息表進(jìn)行清洗，刪掉沒(méi)有按時(shí)報(bào)到的學(xué)生數(shù)據(jù)，然后聯(lián)合查詢這六張表，得到包含學(xué)年、學(xué)期、學(xué)院、班級(jí)、選課課號(hào)、學(xué)號(hào)、課程代碼、課程性質(zhì)、課程歸屬、學(xué)分、教師工號(hào)、評(píng)教號(hào)、評(píng)分、評(píng)價(jià)等級(jí)等字段的學(xué)生評(píng)教綜合信息表。

表6 原始數(shù)據(jù)形式

Tab.6 Raw data form

對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)化，將數(shù)據(jù)轉(zhuǎn)化為挖掘?qū)嶒?yàn)所需的評(píng)分?jǐn)?shù)據(jù)矩陣的形式，如表7所示，每一行數(shù)據(jù)包含一個(gè)學(xué)生對(duì)教師T的9項(xiàng)評(píng)分，經(jīng)過(guò)預(yù)處理之后的數(shù)據(jù)更加規(guī)整，方便之后的數(shù)據(jù)挖掘工作。

3.2 實(shí)驗(yàn)結(jié)果及對(duì)比

為驗(yàn)證算法的有效性與效率，將通過(guò)實(shí)驗(yàn)來(lái)比較本文所提出的算法、與貪婪算法和基于頻率的離群點(diǎn)檢測(cè)算法各自的性能。實(shí)驗(yàn)的硬件環(huán)境是 CPU1.7GHz，主存4GB，軟件環(huán)境為 Matlab 2014、Sublime Text 3、Echarts3。實(shí)驗(yàn)所用的數(shù)據(jù)集是H高校的大學(xué)教學(xué)評(píng)價(jià)數(shù)據(jù)，由于原始數(shù)據(jù)集非常龐大，僅從經(jīng)過(guò)預(yù)處理后的評(píng)分矩陣數(shù)據(jù)集里篩選出R學(xué)院C班程序設(shè)計(jì)的評(píng)分矩陣作為實(shí)驗(yàn)數(shù)據(jù)。C班共50名學(xué)生，教學(xué)評(píng)價(jià)共有九項(xiàng)評(píng)價(jià)指標(biāo)，每項(xiàng)評(píng)價(jià)指標(biāo)有五種評(píng)價(jià)等級(jí)，分別是5優(yōu)秀、4良好、3中等、2及格和1不及格，實(shí)驗(yàn)中將評(píng)分等級(jí)數(shù)據(jù)簡(jiǎn)化為5、4、3、2、1。數(shù)據(jù)形式如表7所示。下面從準(zhǔn)確性和效率兩個(gè)方面，分析算法的性能。

（1）算法的準(zhǔn)確性

利用Echarts3.0插件對(duì)檢測(cè)結(jié)果進(jìn)行平行坐標(biāo)可視化進(jìn)而驗(yàn)證算法的準(zhǔn)確性，利用貪婪算法進(jìn)行離群點(diǎn)檢測(cè)結(jié)果如圖2，利用AVF算法進(jìn)行離群點(diǎn)檢測(cè)結(jié)果如圖3，本文提出的算法的檢測(cè)結(jié)果如圖4。圖中的11個(gè)平行坐標(biāo)軸，分別代表學(xué)生的ID號(hào)、九項(xiàng)評(píng)價(jià)指標(biāo)和數(shù)據(jù)的檢測(cè)結(jié)果，圖中的細(xì)實(shí)線代表非離群數(shù)據(jù)，菱形線、粗實(shí)線和虛線三條線分別代表檢測(cè)到的三個(gè)離群點(diǎn)。

圖2中菱形線為離群點(diǎn)1，粗實(shí)線為離群點(diǎn)2，虛線為離群點(diǎn)3。從圖中可以看出，三條離群數(shù)據(jù)線明顯偏離正常數(shù)據(jù)，貪婪算法檢測(cè)結(jié)果比較理想。

圖3中菱形線為離群點(diǎn)1，粗實(shí)線為離群點(diǎn)2，虛線為離群點(diǎn)3。從圖中可以看出離群點(diǎn)1的數(shù)據(jù)與正常數(shù)據(jù)無(wú)明顯的偏差，不應(yīng)判斷為離群數(shù)據(jù)，AVF算法的檢測(cè)結(jié)果不準(zhǔn)確。

圖4中菱形線為離群點(diǎn)1，粗實(shí)線為離群點(diǎn)2，虛線為離群點(diǎn)3。從圖中可以看出三條離群數(shù)據(jù)線明顯偏離正常數(shù)據(jù)，所以本文提出算法可以有效的檢測(cè)出離群點(diǎn)，且與AVF算法相比本文所提出的算法的檢測(cè)結(jié)果更加準(zhǔn)確，與貪婪算法的檢測(cè)結(jié)果相同。

表7 實(shí)驗(yàn)所需數(shù)據(jù)矩陣形式

Tab.7 Experimental data required for the matrix form

圖2 貪婪算法的離群點(diǎn)檢測(cè)結(jié)果

圖3 AVF算法離群點(diǎn)檢測(cè)結(jié)果的可視化

圖4 本文的離群點(diǎn)檢測(cè)算法檢測(cè)結(jié)果的可視化

（2）算法的效率

三種算法的運(yùn)行時(shí)間對(duì)比如下：

從圖5中可以看出，三個(gè)算法中，執(zhí)行時(shí)間最短的是AVF算法，貪心算法的執(zhí)行時(shí)間最長(zhǎng)，本文提出的算法的執(zhí)行時(shí)間在和貪心算法之間。主要是因?yàn)楸疚奶岢龅乃惴ń?jīng)過(guò)了聚類算法，導(dǎo)致執(zhí)行時(shí)間高于AVF算法。因此，我們可以看出本算法仍是一種比較高效的算法。

圖5 三個(gè)算法的運(yùn)行時(shí)間對(duì)比圖

4 結(jié)束語(yǔ)

本文算法先采用改進(jìn)的k-modes算法對(duì)教學(xué)評(píng)價(jià)數(shù)據(jù)進(jìn)行聚類，再根據(jù)簇內(nèi)數(shù)據(jù)與簇中心之間的調(diào)整的余弦相似度的值篩選出候選離群數(shù)據(jù)集，最后通過(guò)基于頻率的離群點(diǎn)檢測(cè)算法對(duì)候選離群項(xiàng)集進(jìn)行離群點(diǎn)的檢測(cè)，進(jìn)而得到最后的離群點(diǎn)，既改善了基于頻率的離群點(diǎn)檢測(cè)算法精度不夠高的問(wèn)題，又利用了基于頻率的離群點(diǎn)檢測(cè)算法的高效率的優(yōu)點(diǎn)，與基于信息熵的貪婪算法相比效率較高。算法可以有效的檢測(cè)出教學(xué)評(píng)價(jià)數(shù)據(jù)中的離群點(diǎn)，由于教學(xué)評(píng)價(jià)中的離群點(diǎn)檢測(cè)方法的研究還比較少，在下一步的工作中，筆者打算將本文提出的算法應(yīng)用與R學(xué)院的所有教學(xué)評(píng)價(jià)數(shù)據(jù)中，探索教學(xué)評(píng)價(jià)數(shù)據(jù)中的全局離群點(diǎn)，情景離群點(diǎn)和集體離群點(diǎn)的情況，并結(jié)合其它數(shù)據(jù)對(duì)離群點(diǎn)進(jìn)行解釋，以給學(xué)校的教學(xué)工作提供意見(jiàn)。

[1] Anjewierden A, Kolloffel B, Hulshof C.Towards educati-onal data mining: Using data mining methods for automat-ed chat analysis to understand and support inquiry learning processes. In: Proc. Of the Int’l Workshop on Applying Data Mining in e-Learning (ADML 2007), 2007.

[2] 黎未然. 數(shù)據(jù)挖掘技術(shù)在數(shù)字化校園建設(shè)中的應(yīng)用[J]. 軟件, 2012, 33(10): 61-63.

[3] 欒紅波, 文福安. 數(shù)據(jù)挖掘在大學(xué)英語(yǔ)成績(jī)預(yù)測(cè)中的應(yīng)用研究[J]. 軟件, 2016, 37(3): 67-69.

[4] 胡健, 王理江. 數(shù)據(jù)挖掘在選課推薦中的研究[J]. 軟件, 2016, 37(4): 119-121.

[5] 周慶, 牟超, 楊丹. 教育數(shù)據(jù)挖掘研究進(jìn)展綜述[J]. 軟件學(xué)報(bào), 2015, 26(11): 3026-3042.

[6] Jingyi Luo, Shaymaa E.Sorour, Kazumasa Goda, Tsunen-ori Mine. Predicting Student Grade based on Free-style Comments using Word2Vec and ANN by Considering Prediction Results Obtained in Consecutive Lessons. EDM 8th, Jun 26-29, 2015.

[7] Agnieszka Prusiewicz. Educational Services Recommen- dation Using Social Network Approach. Intelligent Infor- mation and Database Systems, 2011, 6591: 327-336

[8] Renza Campagni, Donatella Merlinii. Data mining models for student careers[J]. Expert Systems with Applications, 2015(13): 5508-5521.

[9] 薛安榮, 姚林. 離群點(diǎn)挖掘方法綜述[J]. 計(jì)算機(jī)科學(xué), 2008, 35(11): 13-18.

[10] CASSISI C, FERRO A, ROSALBA G. Enhancing density-based clustering: parameter reduction and outlier detection[J]. Information Systems, 2013, 38(3): 317-330.

[11] He Z, Deng S, Xu X. A fast greedy algorithm for outlier mining[C]. Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Ming, pages 567-576, Seoul-Korea, 2006.

[12] COVER T M, THOMAS J A. Elements of information theory[M]. 2nd ed. New Jersey: Wiley & Sons, 2006.

[13] Koufakou A, Ortiz E G, el al. A Scalable and Efficient Outlier Detection Strategy for Categorical Data[C]. Proc. Of the 19th IEEE International Conference on Tools with Artificial Intelligence, Washington DC, 2007, 210-217.

[14] Z. Huang. Extensions to the K-Modes algorithm for clustering large data sets with categorical values[J]. Data Min. Knowl. Disc. 2(3), 1998: 283-304.

[15] Amir Ahmad, Lipika Dey. A k-mean clustering algorithm for mixed numeric and categorical data[J]. Data & Knowledge Engineering, 2007, 503-527.

Research on Outlier Detection Algorithm Based on Teaching Evaluation Data

LI Hui1,2, WANG Guo-qiang1, GUO Rui-qiang1,2, GAO Jing-wei1, BAO Yan-min1,2

(1. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024; 2. Key Laboratory of Computational Mathematics and application Hebei Normal University, Hebei Province, Shijiazhuang 050024)

Teaching evaluation is an indispensable link in university teaching activities. In the process of teaching evaluation, some students may raise or reduce scores on purpose or do not take the evaluation seriously, in order to improve the correctness of the evaluation, we should detect and clear the outlier data. Outliers detection problem is one of the important research field of data mining technology. The experimental data of this paper is categorical data,currently outlier detection algorithm for categorical data commonly use greedy algorithm based on information entropy, and AVF algorithm based on frequency. In view of the greedy algorithm time complexity is high, and the AVF algorithm is not accurate enough, this paper proposes an improved outlier detection algorithm based on the frequency. The proposed algorithm first using the improved k-modes algorithm to cluster the teaching evaluation data, and put forward using the Adjusted cosine similarity formula as the similarity metric to screen out candidate outliers far from cluster center, finally detect the outlier from candidate selection by AVF algorithm. Experiments on real data sets show that the algorithm has advantages in terms of accuracy and efficiency.

Outlier detection; K-modes clustering; Cosine similarity;Categorical data

TP391

A

10.3969/j.issn.1003-6970.2017.04.004

河北師范大學(xué)教改課題資助(2015XJJG023)。

李慧(1993-)，女，研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘；郭瑞強(qiáng)(1974-)，男，教授，主要研究方向?yàn)閿?shù)據(jù)庫(kù)，數(shù)據(jù)倉(cāng)庫(kù)，數(shù)據(jù)挖掘；高靜偉(1972-)，男，副教授，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用；暴延敏(1992-)，女，研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘。

王國(guó)強(qiáng)，男，實(shí)驗(yàn)師，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用。

本文著錄格式：李慧，王國(guó)強(qiáng)，郭瑞強(qiáng)，等. 教學(xué)評(píng)價(jià)數(shù)據(jù)的離群點(diǎn)檢測(cè)算法研究[J]. 軟件，2017，38（4）：18-25