基于改進自適應(yīng)DBSCAN的混合式MOOC視頻觀看模式挖掘

王若賓,耿芳東,張永梅,宋 威,王偉鋒,徐 琳

(1.北方工業(yè)大學(xué)信息學(xué)院,北京 100144;2.南澳大學(xué)STEM學(xué)院,澳大利亞 阿德萊德 5095)

1 引言

近年來,混合式MOOC教學(xué)快速發(fā)展,已經(jīng)進入越來越多的高校課堂。不同于傳統(tǒng)的課堂教學(xué),混合式MOOC可以記錄大部分學(xué)習(xí)行為,為精準分析提供了數(shù)據(jù)來源;也不同于純MOOC學(xué)習(xí),學(xué)習(xí)者異質(zhì)化程度高,導(dǎo)致行為模式差異明顯?；旌鲜組OOC學(xué)習(xí)行為模式的差異往往體現(xiàn)為較高同質(zhì)化程度下更為微妙的區(qū)別,而學(xué)習(xí)模式的精準分類對于進一步理解和把握翻轉(zhuǎn)課堂情境中基于教師指導(dǎo)的自我調(diào)節(jié)學(xué)習(xí)規(guī)律具有重要的啟迪作用。

在實際教學(xué)活動中,學(xué)生往往會因為不同的視頻觀看行為呈現(xiàn)不同的分布,在部分行為上學(xué)生分布趨于集中,而在另外一些行為上卻差異明顯,尤其是對于一些難度較高、操作性強以及必修課表以外的課程[1]。因此,混合式MOOC教學(xué)情境對學(xué)習(xí)行為模式挖掘提出了更高的要求。

聚類分析是數(shù)據(jù)挖掘中一種重要的技術(shù)方法,也是無監(jiān)督學(xué)習(xí)中一個重要的研究方向。它能夠把數(shù)據(jù)劃分為若干簇,同一簇間的數(shù)據(jù)具有較高的相似性,不同簇間具有較低相似性,可實現(xiàn)無監(jiān)督模式下的合理劃分,進而獲得分類后的數(shù)據(jù)聚合形態(tài)。因此,以聚類算法對混合式MOOC教學(xué)情境下的視頻觀看模式進行挖掘具有一定的適用性。其中基于密度的聚類算法因適應(yīng)性好而得到廣泛應(yīng)用,如DBSCAN(Density-Based Spatial Clustering Applications with Noise)[2],具有抗噪聲和可以處理復(fù)雜數(shù)據(jù)等優(yōu)點。然而DBSCAN也存在參數(shù)依賴以及人工參與度高的缺陷。

基于此,本文提出一種基于k-dist圖斜率的自適應(yīng)DBSCAN算法KSSA-DBSCAN(Self-Adaptive DBSCAN based on K-dist Slope),可以根據(jù)實際應(yīng)用場景和數(shù)據(jù)集本身的統(tǒng)計特征自動選擇合適的參數(shù)輸入,不僅實現(xiàn)了在未知聚類數(shù)情況下對任意形態(tài)的樣本聚類,而且克服了傳統(tǒng)DBSCAN難以確定參數(shù)以及人工參與度高的不足。本文將其應(yīng)用到混合式MOOC視頻觀看模式挖掘中,可以根據(jù)具體的學(xué)生行為和分布特征,自動選取合適的參數(shù)輸入,聚類出視頻觀看行為模式不同的學(xué)生,進而實現(xiàn)混合式MOOC教學(xué)情境下學(xué)生視頻觀看行為模式的自動挖掘。

2 相關(guān)工作

聚類分析算法一般情況下可分為基于劃分的算法(如K-means)、基于層次的算法(如CURE(Clustering Using REpresentative)、BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies))、基于密度的算法(如DBSCAN)、基于網(wǎng)格的算法(如STING(STatistical INformation Grid))以及基于模型的算法(如EM(Expectation Maximization Algorithm))等。其中基于密度的聚類實際上是找出數(shù)據(jù)集中不同密度區(qū)域的集合,集合中對象之間平均距離較小的區(qū)域即為高密度區(qū)域,平均距離較大的即為低密度區(qū)域。DBSCAN就是一種傳統(tǒng)的密度聚類算法,其復(fù)雜度低、抗噪性強,且不需要提前指定聚類個數(shù),能夠發(fā)現(xiàn)任意形態(tài)的高密度區(qū)域,但是其對于參數(shù)的選擇過于敏感,且需要人工的參與,這一缺陷限制了其在實際中的應(yīng)用。

在算法改進方面,近年來,陸續(xù)有學(xué)者提出新的改進算法。Rodriguez等[3]提出基于快速搜索和發(fā)現(xiàn)密度峰值的聚類算法,但是算法容噪性低并且需要人工參與。Chen等[4]基于新的局部鄰域搜索技術(shù)提出NQ-DBSCAN(Neighbor Query- DBSCAN)算法,減少了大量不必要的距離運算,但是未能解決參數(shù)依賴問題。Brown等[5]基于密度網(wǎng)格提出一種快速聚類算法,雖然縮短了運行時間,但是與DBSCAN相比在精度上未有提升。 Chen等[6]針對大規(guī)模數(shù)據(jù)提出BLOCK- DBSCAN,雖然優(yōu)化了時間復(fù)雜度,但是仍需要人工的參與。Ohadi等[7]提出基于網(wǎng)格和局部參數(shù)的SW-DBSCAN(Sliding Window DBSCAN)聚類算法,通過使用動態(tài)Eps和MinPts參數(shù)提升了算法性能,但仍需要人工確定初始參數(shù)。Gholizadeh等[8]基于K-means++提出K-DBSCAN算法,縮短了DBSCAN算法執(zhí)行時間,但忽視了噪聲的影響,并且沒有解決參數(shù)依賴的問題。周紅芳等[9]基于距離分布矩陣提出自適應(yīng)確定參數(shù)的方法,但是其擬合過程在理論上存在誤差。李文杰等[10]提出KANN-DBSCAN(K-Average Nearest Neighbor-DBSCAN)算法,利用數(shù)據(jù)集自身分布特性生成候選Eps和MinPts參數(shù),并引入Density概念能夠根據(jù)簇數(shù)變化實現(xiàn)自適應(yīng)確定最優(yōu)參數(shù),但是不適合處理較大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)。綜上所述,盡管有一系列針對DBSCAN的改進研究,但是難以確定參數(shù)以及人工參與度高的缺陷仍然沒有得到有效解決。

在實際應(yīng)用方面,丁兆穎等[11]將改進的DBSCAN應(yīng)用在碼頭挖掘場景中,利用改進的DBSCAN算法聚類出包含碼頭的停泊區(qū)域,并通過融合了岸基結(jié)構(gòu)物等的空間數(shù)據(jù)對臨時停泊區(qū)域進行排除,最終實現(xiàn)了較好的碼頭位置選擇。于彥偉等[12]基于Cell距離分析理論提出簡單高效的CDBSCAN(Cell-DBSCAN)算法,解決了面向位置大數(shù)據(jù)的聚類問題。李文昊等[13]通過DBSCAN算法產(chǎn)生的類來約束層次聚類的聚類空間,并將其應(yīng)用到了代碼包層次重構(gòu)的問題上,對軟件進行了合理劃分。但是,相比工程問題中的應(yīng)用,把DBSCAN算法用于學(xué)習(xí)行為挖掘的研究仍然比較少。

基于此,本文提出基于k-dist圖斜率的自適應(yīng)DBSCAN算法KSSA-DBSCAN,不僅實現(xiàn)了在未知聚類數(shù)情況下對任意形態(tài)的樣本聚類,而且克服了參數(shù)依賴的缺陷,提高了聚類的準確率,適用于MOOC視頻觀看行為模式的自動挖掘。

3 相關(guān)概念

3.1 DBSCAN

密度聚類算法DBSCAN能夠通過密度差異劃分出高密度區(qū)域,并能有效發(fā)現(xiàn)任意形狀的簇。該算法定義密度為數(shù)據(jù)集中以某給定對象為圓心、以給定Eps為半徑的空間區(qū)域內(nèi)的對象個數(shù)。下面給出DBSCAN算法中一些必要的定義:

定義1(鄰域Eps) 以給定某對象為圓心、以Eps為半徑所確定的區(qū)域。

定義2(密度閾值MinPts) 以給定的某對象為圓心、以Eps鄰域為半徑所確定的區(qū)域內(nèi)的對象數(shù)目。

定義3(核心點) 如果某一對象在Eps鄰域中至少包含了MinPts個對象,則該對象為核心點。

定義4(直接密度可達) 在給定對象集合里,如果對象p是一個核心點,q在p的Eps鄰域內(nèi),則稱p到q直接密度可達。

定義5(密度可達) 如果存在對象鏈P1,P2,P3,…,Pn,P1=p,Pn=q,如果滿足Pi+1是Pi關(guān)于Eps和MinPts直接密度可達,則稱p到q密度可達。

定義6(密度相連) 如果在同一對象集合里,p和q都是關(guān)于Eps和MinPts密度可達的,則對象p和對象q是密度相連的。

定義7(噪聲點) 對象p不屬于數(shù)據(jù)集里的任何一個簇,則p為噪聲點。

DBSCAN算法基本步驟:

(1)給定MinPts=4(針對二維數(shù)據(jù)),采用k-最近鄰算法kNN(k-Nearest Neighbor)生成候選Eps列表,令k=4,求出所有點的第k個鄰居距離集合distk作為Eps候選值,并進行降序排列,畫出此時的k-dist圖,通過人工確定k-dist圖的第1個“拐點”(Valley)確定Eps的值。

(2)從數(shù)據(jù)集中依次訪問沒有被標記為任意簇的核心點,再把該核心點與它密度相連的對象聚類為同一簇。

(3)重復(fù)步驟(2),直至所有對象都被訪問。

3.2 KSSA-DBSCAN基本思想

由于DBSCAN算法難以確定輸入?yún)?shù),且需要人工的參與,不僅耗費人力,而且在準確率上也難以保證。因此,本文基于k-dist圖斜率的思想提出了一種KSSA-DBSCAN算法,可以根據(jù)實際應(yīng)用場景和數(shù)據(jù)集本身的統(tǒng)計特征自動選擇合適的參數(shù)輸入。其基本思想如算法1所示,具體實現(xiàn)流程如圖 1所示。

算法1KSSA-DBSCAN算法

輸入：數(shù)據(jù)Data,數(shù)據(jù)大小N。

輸出：聚類結(jié)果。

步驟1計算k值,k=N/25。

步驟2遍歷數(shù)據(jù),利用kNN計算每個樣本點的第k個鄰居距離并降序排列,作為候選Eps參數(shù)表。

步驟3根據(jù)降序的候選Eps列表畫出k-dist圖。

步驟4確定Slope閾值,并根據(jù)Slope閾值確定k-dist圖的第1個拐點作為最佳Eps參數(shù)。

步驟5根據(jù)最佳Eps參數(shù)確定初始MinPts參數(shù),并執(zhí)行第1次聚類DBSCAN(Data,最佳Eps,初始MinPts),記錄聚類數(shù),遞減MinPts參數(shù)值分別與最佳Eps聚類迭代,選取聚類數(shù)目第1個突變點對應(yīng)的MinPts值為最佳MinPts參數(shù)。

步驟6DBSCAN(Data,最佳Eps,最佳MinPts)。

Figure 1 Flow chart of KSSA-DBSCAN

3.3 確定Eps參數(shù)

采用k-最近鄰算法kNN生成候選Eps列表,kNN算法的基本思想是使用輸入數(shù)據(jù)找到距離某數(shù)據(jù)點最近的第k個鄰居(k=1時,即為最近鄰距離)?？紤]k值選擇為所有對象數(shù)目的1/25(即k=N/25,N為對象總數(shù)量),求出所有點的第k個鄰居距離集合distk并進行降序排列,作為Eps候選值,畫出此時的k-dist圖,如圖 2所示。

Figure 2 k-dist graph

對于非平滑的曲線,傳統(tǒng)的數(shù)學(xué)方法難以實現(xiàn)拐點的選擇,然而經(jīng)過多次實驗驗證,可以認為連續(xù)多點的坡度小于某一閾值時,則第1個點可判定為拐點。對于該閾值的選擇,可以引入Slope參數(shù)概念,定義Slope為k-dist圖中所有相鄰數(shù)據(jù)點的正切值的均值,如式(1)所示:

(1)

(2)

其中,tanαi表示第i點與第i+1點的正切值,N表示數(shù)據(jù)集中對象總數(shù)。

由于式中|xi-xi+1|的值始終等于1,因此式(1)和式(2)可以簡化為:

(3)

tanαi=yi-yi+1

(4)

對于小規(guī)模數(shù)據(jù),可以認為如果連續(xù)2點的正切值(即tanαi和tanαi+1)均小于閾值Slope,則判定第i點為拐點,選取此點對應(yīng)的y軸Eps值作為最佳Eps參數(shù),如圖 3所示。但是,如果在確定該拐點之前出現(xiàn)了截斷點(即tanαi=0),則判定此時該i點對應(yīng)y值為最佳Eps參數(shù),如圖 4所示。

Figure 3 Valley Pi

Figure 4 Cut-off point Pi

3.4 確定MinPts參數(shù)

本文通過數(shù)學(xué)期望法確定初始MinPts參數(shù)。對于上述方法確定的最佳Eps參數(shù),計算每一個對象在該鄰域中的鄰域?qū)ο髷?shù)量,并計算其數(shù)學(xué)期望值作為初始參數(shù)MinPts0,如式(5)所示:

(5)

其中,N表示數(shù)據(jù)集中對象的總數(shù),Ti表示i點在鄰域Eps中的鄰域?qū)ο罂倲?shù)。

此時由于MinPts0為所有對象的鄰域內(nèi)對象數(shù)量的期望,其中包含了噪聲對象,因此該值對于簇內(nèi)對象來說是偏大的,應(yīng)適當(dāng)縮小該值以排除噪聲對簇內(nèi)對象的干擾并保持此時的聚類簇數(shù)穩(wěn)定,由此得到更加穩(wěn)定緊湊的聚類結(jié)果。首先選取最佳Eps參數(shù)和參數(shù)MinPts0進行第1次聚類,記錄此時的聚類簇數(shù)為ClusterNo_mark。遞減MinPts0值并分別與Eps進行聚類,生成ClusterNo列表,找出ClusterNo列表中最后一個等于ClusterNo_mark的數(shù)據(jù)點i(即第1個突變點),則選取該i點所對應(yīng)的MinPts列表值為最佳MinPts參數(shù),如圖 5所示,p點即為突變點。

Figure 5 Clustering number change diagram

Figure 6 Performance of two algorithms on three 2D data sets

3.5 性能對比

為測試KSSA-DBSCAN算法的性能,本節(jié)選取UCI(University of California Irvine Machine Learning Repository)的wine、seeds、iris標準數(shù)據(jù)集以及3個合成數(shù)據(jù)集DS1、DS2和DS3進行實驗分析,并與KANN-DBSCAN和DBSCAN算法進行了對比,測試數(shù)據(jù)集基本屬性如表 1所示。圖 6展示了KSSA-DBSCAN和DBSCAN在DS1、DS2和DS3這3個二維數(shù)據(jù)集上的聚類結(jié)果,可以看出DBSCAN算法在3個二維數(shù)據(jù)集上的劃分簇數(shù)分別為5,12和5,而本文提出的KSSA-DBSCAN算法的劃分結(jié)果為9,15和6,相比之下KSSA-DBSCAN能夠劃分出更多具有細微差異的不同簇。

Table 1 Basic information of test data sets

為更加客觀地對比KSSA-DBSCAN算法與其他聚類算法的性能差異,本文采用有監(jiān)督的F度量(Fmeasure)方法檢測準確率,3種算法在6個數(shù)據(jù)集上聚類的性能指標如表 2所示?？梢钥闯?本文所提出的KSSA-DBSCAN算法在wine、seeds、DS2、DS3數(shù)據(jù)集上的準確率都優(yōu)于其他算法,并且與DBSCAN相比準確率最大提高了25%。

4 混合式MOOC視頻觀看模式挖掘?qū)嶒?/h2>

4.1 實驗場景

用KSSA-DBSCAN算法對混合式MOOC視頻觀看行為模式進行數(shù)據(jù)挖掘?qū)嶒?實驗選用某大學(xué)《大學(xué)計算機》混合式MOOC視頻學(xué)習(xí)行為數(shù)據(jù)集作為研究對象。該數(shù)據(jù)集包含12個班級301名學(xué)生在該課程169個視頻上共計50 119條視頻觀看行為記錄。通過前期數(shù)據(jù)清洗及記錄合并,最終選定198名學(xué)生在8章共169個課程視頻上的行為數(shù)據(jù)。根據(jù)課程內(nèi)容性質(zhì)以及學(xué)習(xí)行為特征將聚類指標定為視頻觀視比(視頻觀看時長/視頻時長)、次均觀看時長(視頻觀看時長/觀看次數(shù))和移動觀看量(視頻觀看時長/視頻時長-PC端觀看量)3個視頻學(xué)習(xí)行為指標。具體實驗環(huán)境參數(shù)及數(shù)據(jù)如表 3和表 4所示。

Table 2 Comparison of accuracy of different clustering algorithms

Table 3 Experimental configuration

該課程的第1～第4及第8章為課程內(nèi)必修內(nèi)容,第5～第7章為課程外學(xué)習(xí)內(nèi)容,但是觀看視頻可以得到分數(shù),具體信息及特征如表 5所示。

Table 4 Basic properties of experimental data

Table 5 Basic characteristics of each chapter

4.2 實驗及結(jié)果分析

由于該數(shù)據(jù)集維度高達507,因此實驗前先用PCA(Principal Component Analysis)進行降維,再通過t-SNE(t-distributed Stochastic Neighbor Embedding)將數(shù)據(jù)降至二維,以便可視化呈現(xiàn),最終原始數(shù)據(jù)分布和聚類實驗結(jié)果如圖 7所示。從實驗結(jié)果可以看到,198個對象被清晰地劃分為了3個集群,并排除了噪聲的干擾,圖中圓圈表示噪聲。

Figure 7 Original data graph and clustering result graph

為驗證KSSA-DBSCAN算法實驗結(jié)果的合理性,本文將其與其他算法聚類結(jié)果進行了對比,并通過內(nèi)部評價指標DBI(Davies-Bouldin Index)進行評價。DBI計算如式(6)所示,可以看出DBI越低表示聚類結(jié)果越好。

(6)

對比結(jié)果如表 6所示。從表6中可以看出,DBSCAN未能成功聚類,因此DBI值顯示為NAN,而KANN-DBSCAN雖然能夠聚類,但是其DBI值高于KSSA-DBSCAN的。對KSSA-DBSCAN算法聚類的3個集群特征做進一步的分析,圖 8展示了3個集群在169個視頻3個維度上的均值,可以看出各個集群在3個維度上體現(xiàn)出視頻觀看行為模式的差異。

Table 6 Comparison of clustering results

進一步地,按照視頻所屬的章合并后取均值,這將進一步放大各章觀看行為模式的差異。圖 9展示了在每章的均值,可以看出3個集群在不同章3個維度上大多有較為明顯的差異。

根據(jù)聚類的結(jié)果對每個集群特征總結(jié)如下:

(1)集群1:此類學(xué)生能完成課程內(nèi)的觀看任務(wù),并在難度較大的內(nèi)容上存在反復(fù)觀看行為,且次均觀看時長在各章都較長?；就瓿烧n程外內(nèi)容的觀看,根據(jù)特征,被標記為“刻苦型”。

Figure 8 Performance of three clusters on different videos

(2)集群2:此類學(xué)生基本能完成課程內(nèi)的任務(wù),但重復(fù)觀看率不高,一定程度上體現(xiàn)為刷課行為,并且有部分課程任務(wù)未能完成,學(xué)習(xí)積極性不高,因此此類學(xué)生被標記為“懈怠型”。

(3)集群3:此類學(xué)生不僅能完成課程內(nèi)的觀看任務(wù),對難度較大和操作性強的內(nèi)容反復(fù)學(xué)習(xí),而他們的次均觀看時長往往更短,顯示出更好的自我調(diào)節(jié)學(xué)習(xí)行為。而且能積極主動學(xué)習(xí)課程外的內(nèi)容,學(xué)習(xí)策略較好,因此被標記為“策略型”。

對3類學(xué)生的平均成績進一步分析,發(fā)現(xiàn)“刻苦型”學(xué)生平均成績?yōu)?5.047 9,“懈怠型”學(xué)生平均成績?yōu)?0.041 5,“策略型”學(xué)生平均成績?yōu)?2.730 3,存在差異,說明學(xué)生的課程成績與學(xué)習(xí)投入存在正相關(guān)關(guān)系,越多的視頻觀看投入越有可能獲得較高的課程分數(shù)。由于本課程包含了課外觀看內(nèi)容,觀看課外視頻對課程成績有一定的影響,這可能是導(dǎo)致“刻苦型”學(xué)生成績均值比“策略型”學(xué)生成績均值更高的一個原因。但是,單純的視頻觀看時長并不能反映學(xué)習(xí)的真實效果,這一點從“策略型”學(xué)生的學(xué)習(xí)行為可以看出,根據(jù)圖9可知,在觀視比方面,“策略型”學(xué)生在難度較大的章,如第1章和第8章,觀視比高于其他類型學(xué)生的,而在次均觀看時長方面并不是最高的,顯示出得當(dāng)?shù)膶W(xué)習(xí)策略在獲得更好的學(xué)習(xí)效果方面具有優(yōu)勢。

Figure 9 Performance of three clusters on different chapters

5 結(jié)束語

本文提出了一種KSSA-DBSCAN算法,能夠依據(jù)k-dist圖斜率自動選擇合適的k-dist圖拐點作為最佳Eps參數(shù),并在聚類迭代過程中依據(jù)聚類數(shù)目的變化自動確定最佳MinPts參數(shù),克服了DBSCAN參數(shù)敏感以及需要人工參與的缺陷。通過與其他算法在6個測試數(shù)據(jù)集上的對比,驗證了該算法在準確率上的優(yōu)勢,并且通過對混合式MOOC視頻觀看模式的挖掘,進一步驗證了該算法在實際應(yīng)用中的有效性。為使該算法適用更多應(yīng)用場景,特別是大數(shù)據(jù)應(yīng)用場景,未來研究將在時間復(fù)雜度上進行優(yōu)化以適應(yīng)大規(guī)模數(shù)據(jù)處理情境。