基于LSA模型的改進(jìn)密度峰值算法的微學(xué)習(xí)單元文本聚類研究*

武國(guó)勝，張?jiān)虑?/p>

(太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院,山西 晉中 030600)

1 引言

信息化時(shí)代及快節(jié)奏生活讓社會(huì)進(jìn)入到信息碎片化、作息時(shí)間碎片化的時(shí)代。為適應(yīng)利用碎片化時(shí)間進(jìn)行學(xué)習(xí)的需求，2005年微學(xué)習(xí)[1]的概念應(yīng)運(yùn)而生。作為一種新的在線學(xué)習(xí)方式，微學(xué)習(xí)和其他學(xué)習(xí)方式最大的不同，在于微學(xué)習(xí)資源廣泛存在于網(wǎng)絡(luò)上，MOOC、SNS等平臺(tái)中的短文本、短視頻、圖片等都可以成為微學(xué)習(xí)資源，讓學(xué)習(xí)者可以在短時(shí)間內(nèi)進(jìn)行學(xué)習(xí)。隨著微學(xué)習(xí)這種新學(xué)習(xí)方式的出現(xiàn)，學(xué)習(xí)者不僅可以無(wú)處不在地學(xué)習(xí)，更可以利用碎片化時(shí)間進(jìn)行學(xué)習(xí)。近年來(lái)，微學(xué)習(xí)獲得了越來(lái)越多的學(xué)者的關(guān)注和研究，并取得了一定的研究成果[2]。但是，隨著學(xué)習(xí)資源的日益豐富，同一學(xué)習(xí)內(nèi)容的多源異構(gòu)形式也給學(xué)習(xí)者帶來(lái)了“學(xué)習(xí)迷航”和“信息過載”等問題，導(dǎo)致學(xué)習(xí)者很難在短時(shí)間里找到適合自己的學(xué)習(xí)資源。為此，實(shí)現(xiàn)對(duì)微學(xué)習(xí)資源的合理組織，對(duì)促進(jìn)學(xué)習(xí)者的個(gè)性化學(xué)習(xí)具有重要意義。

聚類技術(shù)通過無(wú)人監(jiān)督的方式廣泛應(yīng)用于發(fā)現(xiàn)信息間的隱藏關(guān)系。為了便于發(fā)現(xiàn)微學(xué)習(xí)資源間的隱藏關(guān)系，本文把微學(xué)習(xí)過程中最小的學(xué)習(xí)單元[3]——微學(xué)習(xí)單元作為研究對(duì)象。從微學(xué)習(xí)單元的構(gòu)成形式來(lái)看，文本是重要形式之一，所以本文將嘗試對(duì)文本形式的微學(xué)習(xí)單元進(jìn)行聚類，以方便學(xué)習(xí)者甄別適合自己的學(xué)習(xí)資源。

文本聚類是文本挖掘的研究方向之一，其研究成果被廣泛應(yīng)用于信息檢索。而語(yǔ)義分析處理等方面的研究成果也被用于改善文本聚類的效果。經(jīng)過多年的發(fā)展，文本聚類取得了大量成果，但是微學(xué)習(xí)單元的聚類準(zhǔn)確度還有進(jìn)一步改善的空間。首先，目前傳統(tǒng)的文本聚類方法使用向量空間模型VSM(Vector Space Model)[4]，采用特征詞及其權(quán)重構(gòu)成向量表示文本。由于微學(xué)習(xí)單元文本信息具有短小、精煉且數(shù)量巨大的特點(diǎn)，文本特征向量表現(xiàn)出高維稀疏性，使得模型在表征微學(xué)習(xí)單元文本主題時(shí)容易失焦。其次，雖然文本聚類算法數(shù)量眾多[5]，但在微學(xué)習(xí)單元文本聚類方面表現(xiàn)不佳。例如，K-means算法[6]需要事先指定類別數(shù)，迭代過程中容易陷入局部最優(yōu)；基于層次的算法[7，8]聚類過程中不可逆，合并終止條件對(duì)聚類結(jié)果影響較大。而基于密度的聚類算法[9,10]通過將關(guān)聯(lián)緊密的樣本劃為一類，來(lái)獲取不同聚類類別，可適用于凸樣本集和非凸樣本集，鑒于其適合的樣本集較為廣泛，故本文嘗試?yán)没诿芏鹊木垲愃惴▉?lái)實(shí)現(xiàn)對(duì)微學(xué)習(xí)單元文本的聚類處理。作為一種基于密度的經(jīng)典聚類算法DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[8],該算法具有不需預(yù)置聚類數(shù)量，能分辨噪聲，可找出任何形狀的聚類等優(yōu)點(diǎn)。但同時(shí)也存在調(diào)參過程復(fù)雜的問題，如果未能充分把握數(shù)據(jù)的密度比例，將很難選擇適合的參數(shù)。

2014年，Rodriguez等人[11]提出了密度峰值聚類CFSFDP(Clustering by Fast Search and Find of Density Peaks)算法。CFSFDP算法較DBSCAN算法擁有更多的優(yōu)點(diǎn)，但在處理存在高維稀疏問題的向量空間數(shù)據(jù)時(shí)，也存在計(jì)算局部密度時(shí)沒有統(tǒng)一的度量，選擇歐氏距離作為度量會(huì)導(dǎo)致所表示的微學(xué)習(xí)單元數(shù)據(jù)缺乏全局性的問題，且截?cái)嗑嚯x(Cutoff Distance)的選擇對(duì)聚類結(jié)果的影響較大。此外，密度中心的選擇依賴于人工監(jiān)督，在處理大規(guī)模數(shù)據(jù)時(shí)會(huì)影響算法效率和計(jì)算的準(zhǔn)確率。為解決原有文本聚類算法在微學(xué)習(xí)單元文本聚類方面存在的上述問題，本文采用潛在語(yǔ)義分析LSA(Latent Semantic Analysis)模型[12]對(duì)微學(xué)習(xí)單元建模，并利用奇異值分解SVD(Singular Value Decomposition)方法對(duì)高維稀疏特征向量進(jìn)行降維處理；然后通過密度敏感距離重定義密度計(jì)算方式，并改進(jìn)密度峰值中心獲取方法，使其更適用于微學(xué)習(xí)單元文本聚類。用人工和微學(xué)習(xí)真實(shí)數(shù)據(jù)集在Matlab中進(jìn)行仿真實(shí)驗(yàn)，通過和原算法以及一些經(jīng)典文本聚類算法進(jìn)行比較發(fā)現(xiàn)，本文提出的微學(xué)習(xí)單元聚類算法更適用于微學(xué)習(xí)單元文本聚類。

2 相關(guān)工作

本節(jié)首先介紹與文本聚類相關(guān)的向量空間模型，然后介紹密度峰值聚類算法，最后對(duì)與密度聚類算法密切相關(guān)的參數(shù)密度敏感距離進(jìn)行說(shuō)明。

2.1 向量空間模型(VSM模型)

向量空間模型VSM是由Salton等人[4]在1969年提出的。該模型將文本內(nèi)容轉(zhuǎn)換為特征詞及其權(quán)重構(gòu)成的向量，在多維空間表示為1個(gè)點(diǎn)，使文本處理問題復(fù)雜度大幅降低。VSM模型表示文本的流程包括分詞、停用詞處理、詞根處理以及權(quán)重計(jì)算等。模型中文本集D中存在M個(gè)特征詞、N個(gè)文本，任一文本dj都可以表示成dj={(t1j,ω1j),(t2j,ω2j),…,(tMj,ωMj)}的形式，其中tij(i=1,2,…,M;j=1,2,…,N)為特征詞，ωij(i=1,2,…,M;j=1,2,…,N)為特征詞對(duì)應(yīng)的權(quán)重。權(quán)重計(jì)算方法使用得較多的是由Salton等人[13]提出的詞頻及逆向文檔頻TF-IDF函數(shù)。

向量空間模型以其基于線性代數(shù)的簡(jiǎn)單模型，允許以文本間可能的相關(guān)性進(jìn)行排序，以及對(duì)相似度進(jìn)行連續(xù)取值，受到廣泛青睞。不過，由于向量空間模型假定文本在統(tǒng)計(jì)上是獨(dú)立的，即認(rèn)為詞與詞之間是相互獨(dú)立的，割裂了文本固有的語(yǔ)義關(guān)系，因此該模型處理微學(xué)習(xí)單元短文本時(shí)存在因特征不足而帶來(lái)的嚴(yán)重稀疏性問題。

2.2 密度峰值聚類算法(CFSFDP)

Rodriguez等人[11]提出的CFSFDP算法基于2個(gè)簡(jiǎn)單直觀的假設(shè)：(1)聚類中心的密度高于其鄰居點(diǎn)的密度；(2)聚類中心與具有較高局部密度的任何點(diǎn)的距離都相對(duì)較遠(yuǎn)。根據(jù)這2個(gè)假設(shè)，CFSFDP算法首先需要確定2個(gè)參數(shù)：(1)局部密度；(2)與高密度點(diǎn)間的截?cái)嗑嚯x。并以此為依據(jù)把其他點(diǎn)分配到以潛在的密度峰值點(diǎn)為中心的聚類里。其中，局部密度為與當(dāng)前數(shù)據(jù)點(diǎn)間的距離小于截?cái)嗑嚯x的數(shù)據(jù)點(diǎn)的個(gè)數(shù)。截?cái)嗑嚯x為聚類時(shí)的數(shù)據(jù)點(diǎn)到當(dāng)前數(shù)據(jù)點(diǎn)的最大距離。該算法在計(jì)算數(shù)據(jù)點(diǎn)間的距離時(shí)采用歐氏距離。

文獻(xiàn)[11]中使用大量實(shí)驗(yàn)證明了密度峰值算法對(duì)凸型和非凸型數(shù)據(jù)均具有良好的處理效果。但是，在針對(duì)微學(xué)習(xí)單元文本聚類的應(yīng)用中發(fā)現(xiàn)，CFSFDP算法中計(jì)算局部密度和選取密度峰值中心的方法未能適應(yīng)微學(xué)習(xí)數(shù)據(jù)的特點(diǎn)。

首先，CFSFDP算法使用的“截?cái)嗑嚯x”參數(shù)，采用取鄰近的平均數(shù)據(jù)點(diǎn)數(shù)是總數(shù)據(jù)點(diǎn)數(shù)的1%～2%作為截?cái)嗑嚯x，該選擇沒有明確的選擇依據(jù)。如圖1所示，在不同截?cái)嗑嚯x下，聚類準(zhǔn)確度和效果會(huì)出現(xiàn)差異。

圖1表示在pathbased2數(shù)據(jù)集上選取不同截?cái)嗑嚯x進(jìn)行實(shí)驗(yàn)的結(jié)果。圖1a表示在截?cái)嗑嚯x選取不合適時(shí)的聚類結(jié)果，其類簇?cái)?shù)變?yōu)?，出現(xiàn)錯(cuò)誤。圖1b表示選取截?cái)嗑嚯x合適的聚類結(jié)果，其正確的類簇?cái)?shù)為3。

近年來(lái)許多學(xué)者也注意到了該不足，如Mehmood 等人[14]提出了一種利用熱擴(kuò)散的方法和核密度來(lái)重新定義密度，此方法可以自適應(yīng)計(jì)算帶寬，以不依賴任何參數(shù)的方式解決階段距離敏感的問題。Xie等人[15]提出了一種使用模糊加權(quán)K-最近鄰的方式來(lái)定義點(diǎn)的局部密度并搜索和發(fā)現(xiàn)聚類中心，只需要1個(gè)參數(shù)來(lái)解決CFSFDP算法密度測(cè)量不均的問題。Liu等人[16]引入共享近鄰的概念重新設(shè)計(jì)了一種分配策略，可以快速搜索和找到密度峰值進(jìn)行聚類。

其次，CFSFDP算法在選取密度峰值點(diǎn)時(shí)，采用人工監(jiān)督的方式。在預(yù)先知道類簇?cái)?shù)目的前提下繪制密度-距離決策圖，并認(rèn)為密度峰值點(diǎn)是局部密度和與高密度點(diǎn)之間的距離均較大的點(diǎn)，這些點(diǎn)在決策圖中一般出現(xiàn)在所有數(shù)據(jù)點(diǎn)右上角的位置，且通過人為選出圖中表現(xiàn)“突出”的已知類簇?cái)?shù)目的數(shù)據(jù)點(diǎn)作為密度峰值點(diǎn)。這一選擇方法在面對(duì)大量數(shù)據(jù)處理時(shí)難度大，會(huì)影響算法的準(zhǔn)確度和執(zhí)行效率。許多學(xué)者針對(duì)此問題取得了一些研究進(jìn)展。Gao等人[17]設(shè)計(jì)了一種非視覺決策圖，采用基于降序碰撞選擇聚類中心的方法選取聚類中心。Liang 等人[18]利用DBSCAN框架中的分而治之和密度可達(dá)概念提出了自動(dòng)選擇聚類中心的策略，該策略可以以遞歸方式自動(dòng)查找正確數(shù)量的簇。

Figure 1 Influence of different cutoff distances on clustering results圖1 不同截?cái)嗑嚯x對(duì)聚類結(jié)果產(chǎn)生的影響

2.3 密度敏感距離

2007年，王玲等人[19]通過觀察樣本數(shù)據(jù)的空間分布情況，設(shè)計(jì)了一種簡(jiǎn)單有效的空間一致性距離測(cè)度：密度敏感距離。密度敏感距離測(cè)度可以度量沿著流形上的最短路徑，從而實(shí)現(xiàn)了放大位于不同高密度區(qū)域上數(shù)據(jù)點(diǎn)間的距離，而縮短位于同一高密度區(qū)域內(nèi)數(shù)據(jù)點(diǎn)間距離的目的。

密度敏感距離建立在密度可調(diào)節(jié)距離的基礎(chǔ)之上，其思路是引入伸縮因子，并把歐氏距離作為伸縮因子的冪因子；然后通過調(diào)節(jié)伸縮因子的大小來(lái)增大或縮小2個(gè)數(shù)據(jù)點(diǎn)間的距離。

密度敏感距離則用于發(fā)現(xiàn)不同流形數(shù)據(jù)點(diǎn)上的最短路徑，這使得位于同一高密度區(qū)域內(nèi)的2點(diǎn)可以用較短的邊相連接，而位于不同高密度區(qū)域內(nèi)的2點(diǎn)要用較長(zhǎng)的邊相連接，從而實(shí)現(xiàn)了放大位于不同高密度區(qū)域上數(shù)據(jù)點(diǎn)間的距離，縮短位于同一高密度區(qū)域內(nèi)數(shù)據(jù)點(diǎn)間距離的目的[20]。

2.4 潛在語(yǔ)意分析

潛在語(yǔ)義分析(LSA)模型最早由Deerwesster等人[12]提出，其原理為將高維向量空間通過奇異值分解SVD映射到低維的潛在語(yǔ)義空間，在擴(kuò)展語(yǔ)義信息的同時(shí)達(dá)到降維去噪的目的[21]。

相比于VSM模型的獨(dú)立性假設(shè)，LSA模型假設(shè)文本中詞語(yǔ)間存在緊密的聯(lián)系，構(gòu)造M×N維特征詞-文本矩陣來(lái)描述文本中詞項(xiàng)的共現(xiàn)性，其中M表示文本集特征詞個(gè)數(shù)，N表示文本集中文本個(gè)數(shù)。特征項(xiàng)A通常采用TF-IDF[12]向量計(jì)算權(quán)重。

對(duì)原始空間矩陣A做奇異值分解(SVD)，如式(1)所示：

(1)

其中，矩陣UM×M為M×M的左奇異向量矩陣，存儲(chǔ)了語(yǔ)義相關(guān)的詞向量。矩陣VN×N為N×N的右奇異矩陣，存儲(chǔ)了主題相關(guān)的文本向量。Σ=diag(σ1,σ2,…,σr)∈Rr×r是一個(gè)由A的特征值組成的r×r的對(duì)角陣，σ稱為奇異值。奇異值按降序排列且前k(k<

(2)

3 新的微學(xué)習(xí)單元文本聚類算法的研究

本文提出的微學(xué)習(xí)單元文本聚類算法由以下4部分組成：微學(xué)習(xí)單元分割和標(biāo)記、微學(xué)習(xí)單元文本數(shù)據(jù)預(yù)處理、微學(xué)習(xí)單元特征提取、微學(xué)習(xí)單元聚類。該聚類方法的流程圖如圖2所示。

Figure 2 Process of proposed algorithm applied to micro-learning unit text clustering圖2 本文算法應(yīng)用于微學(xué)習(xí)單元文本聚類流程

第1部分微學(xué)習(xí)單元分割和標(biāo)記是將獲取的微學(xué)習(xí)文本資源中標(biāo)題和描述作為數(shù)據(jù)處理對(duì)象，對(duì)其內(nèi)容類別進(jìn)行手工標(biāo)注和分割，從而獲取微學(xué)習(xí)單元。第2部分文本數(shù)據(jù)預(yù)處理階段將標(biāo)注的微學(xué)習(xí)單元文本數(shù)據(jù)進(jìn)行文本的分詞處理、停用詞處理、詞干提取。第3部分微學(xué)習(xí)單元特征提取對(duì)處理過的文本數(shù)據(jù)進(jìn)行建模和特征降維，得到合適的文本特征向量。第3和第4部分構(gòu)建模型及微學(xué)習(xí)單元聚類是本文研究的重點(diǎn)。

3.1 微學(xué)習(xí)單元模型構(gòu)建

微學(xué)習(xí)單元是微學(xué)習(xí)過程中最小的學(xué)習(xí)單位，每個(gè)課程C由一系列微學(xué)習(xí)單元構(gòu)成。假設(shè)微學(xué)習(xí)過程中存在n個(gè)課程，任意1個(gè)課程Ci(i=1,2,…,n)可以由m個(gè)微學(xué)習(xí)單元組成，即Ci={U1,U2,…,Um}。

在進(jìn)行模型構(gòu)建過程中，由于本文使用微學(xué)習(xí)單元的標(biāo)題、描述和文本內(nèi)容作為微學(xué)習(xí)單元的文本數(shù)據(jù)，故數(shù)據(jù)有著單一文本長(zhǎng)度較短、文本特征詞數(shù)據(jù)量少、文本數(shù)量較多的特點(diǎn)。若使用VSM模型(向量空間模型)建立微學(xué)習(xí)單元模型，會(huì)遇到微學(xué)習(xí)單元特征不足、特征詞向量高維稀疏等問題。故本文選擇采用潛在語(yǔ)義分析模型LSA進(jìn)行微學(xué)習(xí)單元建模及特征降維工作。

3.2 基于密度敏感距離的局部密度

在上述基礎(chǔ)之上，本文對(duì)密度峰值算法在微學(xué)習(xí)單元文本聚類中存在的問題，提出2點(diǎn)改進(jìn)。

首先，本文改進(jìn)了數(shù)據(jù)點(diǎn)間距離計(jì)算時(shí)的度量方法，提出了自然指數(shù)型距離度量方法，以解決文獻(xiàn)[19]中伸縮因子大于1時(shí)遇到的伸縮比例不易調(diào)整的問題。

定義1 基于密度峰值算法的自然指數(shù)型距離度量矩陣L如式(3)所示:

L(xi,xj)=eρ×dij-1

(3)

其中，dij表示數(shù)據(jù)xi與xj之間的歐氏距離，ρ表示伸縮因子(ρ>0)，ρ可用于調(diào)節(jié)數(shù)據(jù)點(diǎn)間的距離度量。使用指數(shù)型調(diào)節(jié)函數(shù)，并通過伸縮因子ρ在次冪上進(jìn)行調(diào)節(jié)，這樣可以使得調(diào)節(jié)的幅度得到合理的控制。

通過改進(jìn)距離度量方法來(lái)引入密度敏感距離，將密度敏感距離作為微學(xué)習(xí)單元文本聚類的相似性度量，以此來(lái)改進(jìn)CFSFDP算法對(duì)微學(xué)習(xí)單元文本聚類時(shí)遇到的全局一致性不足的缺陷，并通過該方法更好地尋找密度峰值中心。

定義2(數(shù)據(jù)點(diǎn)局部密度) 根據(jù)改進(jìn)的自然指數(shù)型距離度量計(jì)算方法，并將其引入密度敏感矩陣中，即得到任意2個(gè)數(shù)據(jù)點(diǎn)xi,xj密度敏感距離矩陣S。

(4)

其中，p∈Vl表示圖G中1個(gè)長(zhǎng)度為l=|p|-1的連接點(diǎn)p1和p|p|的路徑，且邊(pk,pk+1)∈E(1≤k≤|p|-1),Pij表示xi與xj之間所有路徑的集合，L(pk,pk+1)表示連接pk與pk+1之間基于密度峰值算法的自然指數(shù)型距離。采用Dijkstra[22]計(jì)算最短路徑長(zhǎng)度。

隨后，將密度敏感距離作為相似性度量，重新定義不依賴于截?cái)嗑嚯x的局部密度公式。已知空間X={x1,x2,…,xi,…,xn}中對(duì)象xi的密度記作density(xi)，如式(5)所示:

(5)

該局部密度定義可以描述為數(shù)據(jù)點(diǎn)xi與其相連接的所有數(shù)據(jù)點(diǎn)間距離的比值之和。這樣的密度定義方法降低了算法對(duì)截?cái)嗑嚯x取值的敏感性，并且可以反映數(shù)據(jù)的密度分布，和CFSFDP算法的密度計(jì)算方法相比，能更好地保持全局一致性，便于聚類分配時(shí)正確地分配微學(xué)習(xí)單元，提高文本聚類的效果。具體描述如算法1所示。

算法1 基于密度敏感距離重定義局部密度

輸入：微學(xué)習(xí)單元文本子空間X={x1,x2,…,xn}，伸縮因子ρ。

輸出：數(shù)據(jù)點(diǎn)局部密度density(xi)。

步驟1 計(jì)算文本子空間X中各數(shù)據(jù)點(diǎn)間的歐氏距離，得到歐氏距離的矩陣D:

D(xi,xj)=dij,1≤i≤n,1≤j≤n

步驟2 根據(jù)歐氏距離矩陣D用式(3)計(jì)算密度可調(diào)節(jié)線段長(zhǎng)度，在ρ∈(0,3)調(diào)整伸縮因子，得到自然指數(shù)型距離度量矩陣L;

步驟3 將自然指數(shù)型距離度量矩陣L代入式(4)，得到密度敏感距離矩陣S；

步驟4 將密度敏感距離矩陣代入式(5)，得到每個(gè)數(shù)據(jù)點(diǎn)的局部密度density(xi)

步驟5 算法結(jié)束。

3.3 自動(dòng)選取密度峰值中心

本文從CFSFDP算法選取密度峰值中心的原理出發(fā)，提出根據(jù)殘差分析異常點(diǎn)，進(jìn)而選取密度峰值的方法。如圖3a和圖3b所示，密度峰值點(diǎn)A、B、C與普通數(shù)據(jù)點(diǎn)距離較遠(yuǎn)，且處于右上方的位置(圖3b)。如果嘗試將ρ-δ組成的數(shù)據(jù)進(jìn)行線性擬合，可發(fā)現(xiàn)該數(shù)據(jù)集密度峰值中心就是經(jīng)過線性擬合后的那些最為偏離大部分?jǐn)?shù)據(jù)的異常點(diǎn)——野值點(diǎn)。

線性回歸是利用數(shù)理統(tǒng)計(jì)中的回歸分析，來(lái)確定2種或2種以上變量間相互依賴的定量關(guān)系的一種統(tǒng)計(jì)分析方法[23]。即對(duì)于n個(gè)數(shù)據(jù)的數(shù)據(jù)集，ρ和δ擬合時(shí)的線性關(guān)系為：δi=f(ρi)=a+bρi,i=1,2,…,n。所以，當(dāng)利用殘差分析的方法對(duì)ρ-δ線性擬合以找出線性擬合過程中的奇異點(diǎn)時(shí)，如圖4所示，其中，A1、B1、C1分別對(duì)應(yīng)圖3b中A、B、C3個(gè)密度峰值點(diǎn)的殘差，奇異點(diǎn)包括密度峰值點(diǎn)，但奇異點(diǎn)不都是密度峰值點(diǎn)，這是因?yàn)槊芏确逯抵行氖悄切│押挺木容^大的數(shù)據(jù)點(diǎn)，而有些數(shù)據(jù)點(diǎn)是ρ或δ其中1項(xiàng)較大，而另1項(xiàng)較小，這些點(diǎn)往往是遠(yuǎn)離類簇的點(diǎn)或類間點(diǎn)。本文算法的目標(biāo)是去除這些點(diǎn)，而保留最為偏離大部分?jǐn)?shù)據(jù)的點(diǎn)——野值點(diǎn)。所以，在進(jìn)行線性擬合時(shí)，并不能1次性地選擇出這些野值點(diǎn)作為正確的密度峰值中心。

Figure 3 Using density peak algorithm to find the peak center point law圖3 密度峰值算法尋找峰值中心點(diǎn)規(guī)律

Figure 4 Analysis of outliers by residuals in Matlab圖4 在Matlab中通過殘差分析異常點(diǎn)

為選擇出野值點(diǎn)，本文集中對(duì)使用殘差法進(jìn)行線性擬合時(shí)得到的參數(shù)進(jìn)行分析。本文觀察到野值點(diǎn)與其他奇異點(diǎn)在殘差上存在較大不同，為此本文對(duì)殘差分析后得到的殘差加以約束，使用這個(gè)約束條件將野值點(diǎn)和其他奇異點(diǎn)分離，保留野值點(diǎn)，剔除其他的奇異點(diǎn)。保留的野值點(diǎn)由于ρ和δ均較大，而導(dǎo)致其進(jìn)行線性擬合時(shí)成為奇異點(diǎn)，而密度峰值點(diǎn)是一些被低密度點(diǎn)包圍且到其他高密度點(diǎn)的距離較大的點(diǎn)，為此這些野值點(diǎn)能夠代表整個(gè)類作為類簇中心，即野值點(diǎn)就是密度峰值中心點(diǎn)。具體描述如下文所述：

假設(shè)密度峰值中心數(shù)據(jù)點(diǎn)下標(biāo)為DPCDP(Density Peak Center Data Point)，線性擬合過程中得到的數(shù)據(jù)點(diǎn)殘差為ri，殘差下限為rli，殘差平均值為ra，殘差的方差為rσ,則約束條件為：

DPCDP={i|rli>0&&(ri-ra)>3×rσ}

(6)

其中，

(7)

(8)

其中，約束條件中的數(shù)字3為實(shí)驗(yàn)得到的最佳約束參數(shù)。

使用這樣的約束條件后，其他奇異點(diǎn)被剔除，剩下的就是經(jīng)過線性擬合得到的野值點(diǎn)，而這些奇異點(diǎn)在數(shù)據(jù)集中表現(xiàn)為各類的密度峰值中心，下標(biāo)點(diǎn)的個(gè)數(shù)即為密度峰值算法需要聚類的類簇?cái)?shù)。如此，通過殘差分析和條件約束可以避免CFSFDP算法中人工選擇的不準(zhǔn)確以及不夠智能的缺陷，提高算法選擇密度峰值中心的準(zhǔn)確率以及算法運(yùn)行效率。通過Matlab仿真實(shí)現(xiàn)改進(jìn)的CFSFDP選取峰值中心的具體步驟如算法2所示。

算法2 自動(dòng)選取密度峰值中心

輸入：局部密度ρ，最近且密度比數(shù)據(jù)點(diǎn)大的點(diǎn)的距離δ。

輸出：密度峰值中心數(shù)據(jù)點(diǎn)下標(biāo)DPCDP。

步驟1 由局部密度ρ和距離δ繪制ρ-δ決策圖；

步驟2 根據(jù)以ρ為橫坐標(biāo)、δ為縱坐標(biāo)的數(shù)據(jù)點(diǎn)在Matlab上進(jìn)行線性擬合，由Matlab自帶的殘差分析工具得到殘差ri和殘差下界rli；

步驟3 根據(jù)式(7)和式(8)計(jì)算殘差平均值ra和殘差的方差rσ；

步驟4 根據(jù)式(6)計(jì)算密度峰值中心數(shù)據(jù)點(diǎn)的下標(biāo)，得到DPCDP；

步驟5 算法結(jié)束。

4 實(shí)驗(yàn)和結(jié)果

4.1 實(shí)驗(yàn)相關(guān)介紹

本次實(shí)驗(yàn)采用微學(xué)習(xí)單元的真實(shí)數(shù)據(jù)集，并和經(jīng)典文本聚類算法以及CFSFDP算法進(jìn)行對(duì)比實(shí)驗(yàn)，從而分析以得到最后的結(jié)論。對(duì)比的經(jīng)典文本聚類算法是K-means算法[6]、DBSCAN算法[9]和DPC-KNN算法[24]。K-means算法是由Matlab自帶的庫(kù)函數(shù)進(jìn)行測(cè)試工作的，DBSCAN算法是根據(jù)作者提供的源碼進(jìn)行測(cè)試和實(shí)驗(yàn)。DPC-KNN算法是一種采用K-最近鄰方式避免截?cái)嗑嚯x敏感的算法，由于其性能近年來(lái)得到了廣泛的關(guān)注，且該算法類簇分配策略與本文算法一致，便于進(jìn)行對(duì)比，所以本文選擇該算法進(jìn)行對(duì)比實(shí)驗(yàn)。DPC-KNN算法按照文獻(xiàn)[25]理論使用Matlab模擬。

本次實(shí)驗(yàn)使用的微學(xué)習(xí)真實(shí)數(shù)據(jù)集來(lái)自于網(wǎng)絡(luò)平臺(tái)。使用Python 2.7在Windows 10系統(tǒng)下，通過官方提供的Scrapy模塊進(jìn)行爬取。數(shù)據(jù)來(lái)源網(wǎng)站是 Coursera，Coursera是世界上三大MOOC平臺(tái)之一，由于其課程免費(fèi)，且課程數(shù)量較多，內(nèi)容較為豐富，便于系統(tǒng)收集學(xué)習(xí)課件，所以選擇該平臺(tái)作為數(shù)據(jù)來(lái)源。最后，實(shí)驗(yàn)?zāi)M使用的測(cè)試軟件為Matlab R2016a ，實(shí)驗(yàn)環(huán)境是Intel Core i5, 8 GB內(nèi)存,Windows 10操作系統(tǒng)。

在實(shí)驗(yàn)中采用聚類準(zhǔn)確率(ACC)、調(diào)整互信息指數(shù)(AMI)[26]和調(diào)整蘭德指數(shù)(ARI)[27]來(lái)評(píng)價(jià)聚類結(jié)果。

ACC指標(biāo)定義如下：

其中,n是數(shù)據(jù)點(diǎn)的數(shù)量，yi和ci是真實(shí)標(biāo)簽和數(shù)據(jù)點(diǎn)xi的預(yù)測(cè)標(biāo)簽。當(dāng)yi=ci時(shí)，δ(yi,ci)=1，否則為0。

ARI指標(biāo)定義如下：

AMI指標(biāo)定義如下：

其中，U表示實(shí)際類別集合，V表示真實(shí)聚類類別集合，p(u)和p(v)分別為u和v的邊緣概率密度函數(shù)，p(u,v)為聯(lián)合概率密度函數(shù)。H(U)和H(V)為U和V的信息熵。

這3種度量指標(biāo)取值上界均為1，值越接近1表示聚類結(jié)果越好。

4.2 實(shí)驗(yàn)實(shí)施

按照本文聚類算法的4個(gè)組成部分，本次實(shí)驗(yàn)的步驟如下所示：

(1)微學(xué)習(xí)單元分割和標(biāo)記。選擇課程平臺(tái)中每個(gè)課程的課程名稱及課程標(biāo)題作為主要文本內(nèi)容。課程提供平臺(tái)并沒有已存在的微學(xué)習(xí)單元，所以本文以周為分割周期將課程分割成微學(xué)習(xí)單元，每個(gè)課程由多個(gè)微學(xué)習(xí)單元組成，每個(gè)單元獨(dú)立存在。為微學(xué)習(xí)單元標(biāo)注4個(gè)屬性，分別為微學(xué)習(xí)單元編號(hào)、微學(xué)習(xí)單元類別、微學(xué)習(xí)單元標(biāo)題(Unit Title)和微學(xué)習(xí)單元描述(Unit Description)。部分微學(xué)習(xí)單元內(nèi)容如表1所示，手工標(biāo)注后的微學(xué)習(xí)單元所屬類別和編號(hào)如表2所示。

(2)微學(xué)習(xí)單元文本數(shù)據(jù)預(yù)處理。數(shù)據(jù)預(yù)處理的操作包括：文本的分詞處理、停用詞處理、詞干提取。本文使用Python NLTK[28]工具實(shí)現(xiàn)文本分詞工作，通過設(shè)置停用詞表的方式將停用詞進(jìn)行過濾處理，詞干提取方法采用波特詞干提取法[29]。

(3)微學(xué)習(xí)單元特征提取。經(jīng)過預(yù)處理后的微學(xué)習(xí)單元數(shù)據(jù)需要進(jìn)一步結(jié)構(gòu)化表示，這樣才能被計(jì)算機(jī)識(shí)別，從而通過計(jì)算機(jī)分析處理。這一過程的步驟包括：特征項(xiàng)的選擇，特征項(xiàng)權(quán)重計(jì)算，LSA模型[12]表示微學(xué)習(xí)單元，相似度計(jì)算。經(jīng)預(yù)處理得到特征維度為1 131維的稀疏特征詞空間，采用TF-IDF算法[13]分別計(jì)算微學(xué)習(xí)單元的標(biāo)題和單元內(nèi)容描述這2個(gè)字段的特征詞權(quán)重。最后通過LSA模型表示微學(xué)習(xí)單元數(shù)據(jù)，以便于計(jì)算機(jī)識(shí)別，本文k值選擇100，

Table 1 Partial micro-learning unit content表1 部分微學(xué)習(xí)單元內(nèi)容

Table 2 Category and content of the micro-learning unit after manual labeling表2 手工標(biāo)注微學(xué)習(xí)單元后的所屬類別和內(nèi)容

經(jīng)SVD分解降維后得到低維語(yǔ)義空間，最后使用歐氏距離[25]計(jì)算相似度。

(4)使用本文提出的改進(jìn)的密度峰值算法、K-means算法、DBSCAN算法和DPC-KNN算法在微學(xué)習(xí)單元真實(shí)數(shù)據(jù)集上進(jìn)行聚類。其中CFSFDP算法中需要考慮截?cái)嗑嚯x選取的問題，算法選擇鄰近的平均數(shù)據(jù)點(diǎn)數(shù)是總數(shù)據(jù)點(diǎn)數(shù)的1%～2%作為截?cái)嗑嚯x，本文選取1%～2%中結(jié)果最好的作為參數(shù)。DBSCAN算法選擇使得結(jié)果最佳的參數(shù)Eps和MinPts作為最終結(jié)果。K-means算法預(yù)設(shè)類別數(shù)5，運(yùn)行10次取平均值作為最終結(jié)果。DPC-KNN算法需要選取KNN的百分比參數(shù)，按照經(jīng)驗(yàn)本文選取百分比p為樣本數(shù)的0.1%，0.5%，1%中聚類效果最好的參數(shù)作為最終選擇。本文的改進(jìn)算法參數(shù)ρ取聚類結(jié)果最佳時(shí)的結(jié)果。聚類評(píng)價(jià)指標(biāo)使用準(zhǔn)確率ACC、調(diào)整互信息指數(shù)AMI以及調(diào)整蘭德指數(shù)ARI，每個(gè)指標(biāo)值在0～1，且值越大表明聚類效果越好。

4.3 分析真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

本文使用的微學(xué)習(xí)真實(shí)數(shù)據(jù)集經(jīng)過LSA模型的結(jié)構(gòu)化后，經(jīng)過SVD分解降維，從原先1 131維高維語(yǔ)義空間映射到k=100的低維語(yǔ)義空間，較好地避免了傳統(tǒng)使用VSM模型導(dǎo)致的特征空間高維稀疏性問題。微學(xué)習(xí)單元真實(shí)數(shù)據(jù)映射到二維空間的幾何形狀圖如圖5所示，本文提出的改進(jìn)的密度峰值算法及CFSFDP算法在微學(xué)習(xí)單元真實(shí)數(shù)據(jù)上運(yùn)行得到的幾何形狀圖如圖6所示。

從圖5中可以看出，微學(xué)習(xí)單元數(shù)據(jù)每個(gè)類別的全局一致性較強(qiáng)。在圖6b中原算法由于使用依賴于截?cái)嗑嚯x和人工監(jiān)督的方法，在微學(xué)習(xí)單元數(shù)據(jù)中盡管已知真實(shí)微學(xué)習(xí)單元數(shù)目，由于不同類微學(xué)習(xí)單元數(shù)據(jù)間距離較同一類微學(xué)習(xí)單元數(shù)據(jù)間距離更近，且歐氏距離度量使得數(shù)據(jù)點(diǎn)間全局一致性不足，使得在聚類分配階段出現(xiàn)誤分類，從而導(dǎo)致聚類效果不如用本文算法的。如圖6a所示，由于本文算法采用了更適用于微學(xué)習(xí)單元真實(shí)數(shù)據(jù)的新的密度定義方式，該方式中距離判據(jù)為密度敏感距離，使得真實(shí)數(shù)據(jù)集中數(shù)據(jù)點(diǎn)具有全局一致性，在聚類分配階段能獲得更好的聚類效果。除此之外，改進(jìn)算法采用了可以自動(dòng)確定微學(xué)習(xí)單元簇?cái)?shù)的方法，該方法采用殘差分析線性擬合決策圖中的2個(gè)字段找到所有奇異點(diǎn)，并通過約束條件將密度峰值中心選擇出來(lái)，所以該算法相比原算法擁有更優(yōu)的性能。

Figure 5 Geometry diagram of micro-learning unit real datasets圖5 微學(xué)習(xí)單元真實(shí)數(shù)據(jù)集幾何形狀圖

Figure 6 Running results of improved algorithm and original algorithm on real datasets圖6 改進(jìn)算法及原算法在真實(shí)數(shù)據(jù)集上的運(yùn)行結(jié)果

表3所示為對(duì)比實(shí)驗(yàn)的參數(shù)設(shè)置及各聚類性能指標(biāo)，其中，CI表示算法中實(shí)際的簇?cái)?shù)，Par代表每種算法的參數(shù)設(shè)置情況：改進(jìn)的密度峰值算法參數(shù)為伸縮因子ρ，CFSFDP算法參數(shù)為截?cái)嗑嚯x選取百分比，DBSCAN算法參數(shù)Eps和MinPts通過“/”分隔，分別表示鄰域距離和鄰域內(nèi)樣本數(shù)，K-means算法參數(shù)為真正的簇?cái)?shù)k。

如表3所示，與原算法CFSFDP相比，改進(jìn)算法可以準(zhǔn)確確定簇?cái)?shù)，而原算法由于真實(shí)數(shù)據(jù)集數(shù)據(jù)復(fù)雜度較高，在決策圖中很難得到正確的簇?cái)?shù)和簇中心，所以改進(jìn)算法在準(zhǔn)確率上比原算法高，并且在AMI和ARI上也體現(xiàn)出了改進(jìn)算法在微學(xué)習(xí)真實(shí)數(shù)據(jù)集上的優(yōu)越性，本文可以認(rèn)為改進(jìn)算法對(duì)于原算法而言有一定的提高。通過與DPC-KNN算法對(duì)比，發(fā)現(xiàn)使用KNN(K最近鄰)作為局部密度的定義方式的算法的準(zhǔn)確率、AMI、ARI低于使用密度敏感距離新定義的密度方式的算法的，由于DPC-KNN算法分配策略與本文提出的聚類算法的一致，但DPC-KNN算法選擇峰值中心不夠智能，為此本文認(rèn)為，改進(jìn)算法在微學(xué)習(xí)單元文本數(shù)據(jù)集上聚類效果更優(yōu)。通過與經(jīng)典的算法對(duì)比發(fā)現(xiàn)，K-means算法在指定類別數(shù)的前提下，其準(zhǔn)確率在4個(gè)算法中最低，說(shuō)明了該算法在此處真實(shí)數(shù)據(jù)集上表現(xiàn)較差。從DBSCAN算法通過調(diào)整2個(gè)參數(shù)得到的結(jié)果來(lái)看，其聚類準(zhǔn)確率僅次于改進(jìn)算法的，但是該算法調(diào)參過程復(fù)雜，AMI和ARI2項(xiàng)指標(biāo)均低于改進(jìn)算法的，可以看出改進(jìn)算法相比DBSCAN算法有著較大的優(yōu)勢(shì)。

如圖7折線圖所示，本文提出的改進(jìn)算法在不同的微學(xué)習(xí)單元類別中的準(zhǔn)確率均高于其他對(duì)比算法的，通過不同微學(xué)習(xí)單元準(zhǔn)確率的直觀表現(xiàn)可以得出這樣一個(gè)結(jié)論：本文提出的改進(jìn)密度峰值算法在微學(xué)習(xí)單元真實(shí)數(shù)據(jù)集上更加有效。

Figure 7 Accuracy comparison of different algorithms in each micro-learning unit class圖7 不同算法在每個(gè)微學(xué)習(xí)單元類別中的準(zhǔn)確率對(duì)比

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

本文提出一種基于LSA模型的改進(jìn)密度峰值微學(xué)習(xí)單元文本聚類算法，通過LSA模型和SVD奇異值分解方法緩解VSM模型存在的高維稀疏性，并在原密度峰值算法的基礎(chǔ)上引入密度敏感距離，并重新定義密度，避免了原算法類簇分配時(shí)的全局一致性不足及截?cái)嗑嚯x敏感的問題。同時(shí)，本文利用線性擬合殘差分析找到野值點(diǎn)的方法自動(dòng)選取密度峰值中心，消除了原CFSFDP算法中人工監(jiān)督的選取方式對(duì)準(zhǔn)確率和效率的不利影響。本文在真實(shí)的微學(xué)習(xí)單元數(shù)據(jù)集上和CFSFDP算法及其他經(jīng)典的算法進(jìn)行對(duì)比后發(fā)現(xiàn)，所提出的算法獲得了較好的聚類性能。使用本文算法可以組織微學(xué)習(xí)資源，從而幫助學(xué)習(xí)者進(jìn)行個(gè)性化學(xué)習(xí)。

但是，由于本文算法引入了密度敏感距離，增大了算法的時(shí)間復(fù)雜度，因此將在今后的工作中對(duì)此進(jìn)行改進(jìn)。