教學評價數(shù)據(jù)的離群點檢測算法研究

李 慧，王國強，郭瑞強，高靜偉，暴延敏

?

教學評價數(shù)據(jù)的離群點檢測算法研究

李 慧1,2，王國強1，郭瑞強1,2，高靜偉1，暴延敏1,2

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

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

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

0 引言

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

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

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

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

1 相關(guān)工作

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

1.1 基于信息熵的離群點檢測算法

He提出了一個基于信息熵的離群點檢測算法——貪心算法（Greedy Algorithm）[11]。

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

1.2 基于頻率的離群點檢測算法

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

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

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

Tab.1 Sample Data

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

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

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

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

2 改進的基于頻率的離群點挖掘算法

2.1 算法的基本思路

針對上述基于頻率的離群點檢測算法的不足，提出一種改進的基于頻率的離群點挖掘算法，算法的主要思想是：

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

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

2.2 聚類算法的選擇

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

本文聚類實驗使用R學院L課程的教學評分數(shù)據(jù)，實驗中把評分數(shù)據(jù)（5優(yōu)秀、4良好、3中等、2及格和1不及格）簡化為（5,4,3,2,1）。如下面兩個表所示，表3為聚類結(jié)果中的第一類的九項評分數(shù)據(jù)，表4為聚類結(jié)果的第四類的九項評分的數(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ù)類別分配錯誤。

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

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

Tab.3 The first kind of clustering results

（2）

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

Tab.4 The fourth class clustering results

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

（4）

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

圖1 K-modes算法流程圖

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

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

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

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

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

表3中的各條評價數(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ù)，把這四條評教數(shù)據(jù)放入候選離群點。

2.4 算法的描述

改進的基于頻率的離群點檢測算法描述如下：

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

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

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

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

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

4：輸出n個離群點。

2.5 算法分析

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

3 實驗與分析

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

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

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

Tab.6 Raw data form

對數(shù)據(jù)進行轉(zhuǎn)化，將數(shù)據(jù)轉(zhuǎn)化為挖掘?qū)嶒炈璧脑u分數(shù)據(jù)矩陣的形式，如表7所示，每一行數(shù)據(jù)包含一個學生對教師T的9項評分，經(jīng)過預(yù)處理之后的數(shù)據(jù)更加規(guī)整，方便之后的數(shù)據(jù)挖掘工作。

3.2 實驗結(jié)果及對比

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

（1）算法的準確性

利用Echarts3.0插件對檢測結(jié)果進行平行坐標可視化進而驗證算法的準確性，利用貪婪算法進行離群點檢測結(jié)果如圖2，利用AVF算法進行離群點檢測結(jié)果如圖3，本文提出的算法的檢測結(jié)果如圖4。圖中的11個平行坐標軸，分別代表學生的ID號、九項評價指標和數(shù)據(jù)的檢測結(jié)果，圖中的細實線代表非離群數(shù)據(jù)，菱形線、粗實線和虛線三條線分別代表檢測到的三個離群點。

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

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

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

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

Tab.7 Experimental data required for the matrix form

圖2 貪婪算法的離群點檢測結(jié)果

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

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

（2）算法的效率

三種算法的運行時間對比如下：

從圖5中可以看出，三個算法中，執(zhí)行時間最短的是AVF算法，貪心算法的執(zhí)行時間最長，本文提出的算法的執(zhí)行時間在和貪心算法之間。主要是因為本文提出的算法經(jīng)過了聚類算法，導致執(zhí)行時間高于AVF算法。因此，我們可以看出本算法仍是一種比較高效的算法。

圖5 三個算法的運行時間對比圖

4 結(jié)束語

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

[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ù)挖掘在大學英語成績預(yù)測中的應(yīng)用研究[J]. 軟件, 2016, 37(3): 67-69.

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

[5] 周慶, 牟超, 楊丹. 教育數(shù)據(jù)挖掘研究進展綜述[J]. 軟件學報, 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] 薛安榮, 姚林. 離群點挖掘方法綜述[J]. 計算機科學, 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

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

李慧(1993-)，女，研究生，主要研究方向為數(shù)據(jù)挖掘；郭瑞強(1974-)，男，教授，主要研究方向為數(shù)據(jù)庫，數(shù)據(jù)倉庫，數(shù)據(jù)挖掘；高靜偉(1972-)，男，副教授，主要研究方向為計算機應(yīng)用；暴延敏(1992-)，女，研究生，主要研究方向為數(shù)據(jù)挖掘。

王國強，男，實驗師，主要研究方向為計算機應(yīng)用。

本文著錄格式：李慧，王國強，郭瑞強，等. 教學評價數(shù)據(jù)的離群點檢測算法研究[J]. 軟件，2017，38（4）：18-25