改進K-means算法在高校輿情中的應用

徐建國 韓琮師

摘 要：互聯網時代，網絡焦點話題討論對當代高校學生的思想有很大影響，因此對高校輿情進行監測具有十分重要的意義。通過改進的K-means算法對高校輿情進行聚類，獲取輿情熱點。通過聚類算法獲取熱點話題，進而對熱點輿情話題進行引導，對改進高校學生思想政治工作作用顯著。對改進算法進行實驗，結果表明該算法準確率達到75%，比傳統算法高出8%，改善了傳統算法的聚類效果。

關鍵詞：高校輿情;聚類;K-means算法

DOI：10. 11907/rjdk. 191734 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP319文獻標識碼：A 文章編號：1672-7800（2019）007-0142-03

Application of Improved K-means Algorithm in University Public Opinion

XU Jian-guo， HAN Cong-shi

（ College of Computer Science and Engineering，Shandong University of Science and Technology，Qingdao 266590，China）

Abstract： In the Internet age， the discussion of network focus topics has a great influence on the thinking of contemporary college students. Therefore， it is of great significance to monitor public opinion in colleges and universities. Through the improved K-means algorithm， the college public opinion clusters， the hotspots and the hot topics of the current colleges and universities are obtained through the clustering algorithm， which can guide the hot topic of the hot topics and play an important role in the development of college students' thoughts. Experiments on the improved algorithm show that the accuracy of the algorithm reaches 75%， which is 8% higher than the traditional algorithm， which improves the clustering effect of the traditional algorithm.

Key Words： university public opinion; clustering; K-means algorithm

基金項目：國家重點研發計劃項目（2017YFC0804406）

作者簡介：徐建國（1964-），男，山東科技大學計算機科學與工程學院副教授、碩士生導師，研究方向為智能信息處理、網絡輿情分析、商務智能;韓琮師（1993-），女，山東科技大學計算機科學與工程學院碩士研究生，研究方向為大數據分析、圖書情報與數字圖書館、智能信息處理。

0 引言

提高大學生思想水平，正確引導培養其價值觀，是我國教育界的重要任務。隨著科技進步，網絡成為信息傳播的主要渠道[1]。據統計，網絡傳播了90%以上的虛假詐騙信息、消極負面信息等，思想尚未完全成熟的高校學生極易受到網絡信息沖擊，從而產生消極思想，可能做出危害社會的行為。

K-means算法應用廣泛，文獻[2]提出將K-means算法用在網絡輿情分析中;文獻[3]將K-means算法應用在微博熱點話題分析中，對實時微博話題進行聚類分析;文獻[4]將K-means算法用于大學生消費水平統計，獲取大學生消費水平層次;文獻[5]通過K-means算法對航空旅客出行目的進行聚類分析，從而有效地推送產品。K-means算法的不足主要表現在選取聚類中心時決策的隨機性，這種隨機性使得聚類結果浮動性較大。此外在更新聚類中心時，通過樣本點的均值求取新的聚類中心容易受孤立點影響。本文借鑒此算法在其它領域的應用情況，提出改進算法并將其應用在高校輿情分析中。

1 改進算法

1.1 K-means聚類算法

K-means算法是基于劃分的聚類算法[6-9]，其基本思想是對給定的數據集隨機選取K個初始聚類中心，將其余數據進行相似性度量，將相似性度量大的數據樣本劃分到同一類中;然后在每個類中重新計算聚類中心，循環迭代，直到滿足終止條件。在K-means算法中，初始聚類中心的選擇直接影響聚類結果，而隨機選取初始聚類中心具有隨機性[10-13]，聚類效果差且很不穩定。因此，本文對聚類中心選擇進行改進。

對于一個給定的樣本集[D={Xi，Xi？Xn}]，將其劃分為K個簇[C={C1，C2？Ck}]，簇內的聚類中心點分別為[ci（i=1，2，？k）]，方式如下：

首先，通過式（1）計算樣本間的距離。

[dist（Xi，Xj）=（Xi-Xj）T（Xi-Xj）]? ? （1）

其中[Xi]為樣本點。

然后，隨機選取一個樣本點作為初始聚類中心[c1]。如果樣本點[Xi]滿足式（2），則將樣本點[Xi]作為初始聚類中心[c2]，如果樣本點[Xj≠ck（k=1，2，3？）]且和前面所選取的聚類中心點也滿足式（2），則將其作為下一個聚類中心。重復進行直到找到第k個聚類中心[ck]。

[θ=σni≠jndist（Xi，Xj）]? ? ? ?（2）

其中[σ]為調節聚類中心間距離參數。通過相似性原則將每個樣本點歸類，通過下式更新每一個類的聚類中心[ck]。

[c'k=1nkXi∈CkXi]? ? ? （3）

[ck={Xi|minXi∈Ckdist（Xi，c'k）}]? ? ?（4）

其中，[nk]為第K個聚類中心所包含的樣本個數，[ck]為第K個聚類中心。

通過對初始聚類中心調整，減小了隨機選取聚類中心的影響，增大了各類之間的距離，提高了聚類準確性;在更新聚類中心時，本文通過選取類中的樣本點作為新的聚類中心，降低了孤立點[14-18]帶來的影響。

1.2 改進算法流程

改進的算法流程如圖1所示。

圖1 算法流程

輸入：樣本集合[D={Xi，Xi...Xn}]，聚類數目K。

輸出：聚類后形成的簇[C={C1，C2…Ck}]。

算法流程如下：①輸入樣本集合D，聚類數目K;②選擇初始聚類中心c1，計算各樣本間的距離[dist（Xi，Xj）]，并根據公式（2）挑選出全部聚類中心;③根據公式（1）計算各樣本[Xi（i=1，2，？，N）]到各聚類中心[ck（k=1，2？k）]的相似性，并將樣本歸入K個類中;④根據公式（3）、公式（4）更新聚類中心。如果聚類中心不變，輸出聚類后的簇C，否則返回步驟③。

2 實驗與分析

2.1 數據處理與試驗指標

本文通過對比實驗驗證改進算法的有效性。在數據獲取上，首先構建一個抓取文本的API工具[19-21]，通過此工具對貼吧、微博和論壇等高校學生喜歡瀏覽并參與的網站進行數據抓取，并通過ICTCLAS分詞系統[22-23]對爬取到的數據進行過濾，得到最終所需數據集。

使用傳統TDT[24-26]評價標準作為實驗評價指標，評價指標分別為：準確率acr，指正確分類的樣本數量所占比重;召回率rec，指特定話題樣本集在所有相關信息中所占比重;漏報率mir，指未獲取的樣本集在所有相關樣本集中所占比重;誤報率fpr，指錯誤判斷的話題信息集在其應該存在的集合中所占比重。公式分別如下：

[acr=A/（A+B）]? ? ? ? ? （5）

[rec=A/（A+C）]? ? ?（6）

[mir=C/（A+C）]? ?（7）

[fpr=B/（B+D）]? ? ? ? ? （8）

其中，A為分類正確的樣本數目，B為錯誤歸類的樣本數目，C為未檢索到的樣本數量，D為不相關樣本數量。

2.2 實驗結果對比

對得到的數據集進行仿真實驗，將傳統K-means算法作為對比實驗，實驗結果如表1所示，算法平均指標如表2所示。

表1 實驗結果對比

從實驗結果可以看出，傳統的K-means算法平均準確率為0.671 375，通過改進算法進行聚類得到的準確率為0.750 25，提高了8%。在召回率rec上，本文提出的改進算法比傳統算法高出10%，體現了本文算法的聚類準確性。在漏報率mir及誤報率fpr上，本文算法均低于傳統的K-means聚類算法。

表2 實驗結果的平均指標值

通過進一步實驗分析，得出高校學生所關注的焦點主要集中在游戲、晨跑打卡、周邊游、掙錢、晚自習、曠課、網吧、美食、戀愛等項目中。除了對晚自習進行討論外，對學習關心很少，需要對學生的學習態度進行引導;此外在戀愛涉及的話題中，很多高校學生對戀愛不知所措，也需要對其進行積極引導。

在高校輿情處理中，本文所提算法提高了聚類準確性。通過改進算法對高校輿情進行分析，能更準確地獲取高校輿情熱點，進而對學生的思想態度進行引導。

3 結語

本文對傳統的K-means算法進行改進，通過閾值逐步選取初始聚類中心，避免了隨機挑選聚類中心帶來的弊端。在聚類中心更新上，通過樣本間距離指標選取樣本點作為新的聚類中心，有效降低了孤立點對樣本聚類的影響。實驗表明，改進算法在性能上得到提升，在很大程度上提高了聚類準確性。通過改進算法對高校輿情進行聚類分析，可有效獲取高校學生所關注的話題焦點，從而對其思想狀態進行積極引導。

參考文獻：

[1] 章永來，周耀鑒. 聚類算法綜述[J]. 計算機應用，2019（5）：1-14.

[2] 徐建國，韓青君，李青. K-means聚類算法及其在網絡輿情中的應用[J]. 軟件導刊，2018，17（11）：65-67.

[3] 劉榮凱，孫忠林. PCA-KDKM算法及其在微博輿情中的應用[J]. 山東科技大學學報：自然科學版，2018，37（6）：84-92.

[4] 馬幸飛，李引. 基于改進的K-means算法在高校學生消費數據中的應用[J]. 無錫商業職業技術學院學報，2016，16（6）：82-85.

[5] 龔婷，普慧潔，張嘉偉，等. 基于K-means的航空旅客聚類研究[J]. 價值工程，2018，37（35）：52-54.

[6] 東方.? 改進的聚類算法在電子商務中的應用[D]. 南昌：南昌大學，2019.

[7] 鄧林培. 經典聚類算法研究綜述[J]. 科技傳播，2019，11（5）：108-110.

[8] 李鵬浩，朱立敬，石秀君. 基于K-means算法微博熱點話題預測分析[J]. 數字通信世界，2019（3）：84-122.

[9] 馮彩英，劉玉. K-means初始聚類中心優化研究[J]. 計算機產品與流通，2019（2）：152-153.

[10] 徐建國，藺珍，張鵬，等. 網絡輿情熱點獲取與分析算法研究[J]. 軟件導刊，2019，18（1）：1-5.

[11] 馬廷博，劉太安，徐建國，等. 基于改進的K-means聚類算法的汽車市場競爭情報分析[J]. 山東科技大學學報：自然科學版，2019，38（1）：74-84.

[12] 劉葉，吳晟，周海河，等. 基于K-means聚類算法優化方法的研究[J]. 信息技術，2019，43（1）：66-70.

[13] 楊丹，朱世玲，卞正宇. 基于改進的K-means算法在文本挖掘中的應用[J]. 計算機技術與發展，2019，29（4）：68-71.

[14] 陳艷紅，向軍，劉嵩. 高校網絡輿情分析的K-means算法優化研究[J]. 湖北民族學院學報：自然科學版，2018，36（4）：442-447.

[15] 楊莉云，顏遠海. 基于孤立點自適應的K-means算法[J]. 河南科學，2019，37（4）：507-513.

[16] 賀艷芳，梁書田. 優化加權多視角K-means聚類算法[J]. 計算機技術與發展，2019，29（3）：81-84.

[17] 黃靈，王云鋒，陳光武. 基于密度標準差優化初始聚類中心的K-means改進算法[J]. 電腦知識與技術，2019，15（6）：147-151.

[18] 王輝，趙瑋，祁薇. 基于用戶特征的K-means聚類算法應用與改進研究[J]. 電腦知識與技術，2018，14（35）：17-19.

[19] 杜佳穎，段隆振，段文影，等. 基于Spark的改進K-means算法的并行實現[J]. 計算機應用研究：2018（7）：1-5.

[20] 徐思，孫仁誠. 結合聚類的半監督分類方法[J]. 青島大學學報：自然科學版，2018，31（4）：49-53.

[21] 楊濤. 中文信息處理中的自動分詞方法研究[J]. 現代交際，2019（7）：93-95.

[22] 劉燕. 基于抽樣和最大最小距離法的并行K-means聚類算法[J]. 智能計算機與應用，2018，8（6）：37-39，43.

[23] 唐海波，林煜明，李優. 一種基于K-Means的平衡約束聚類算法[J]. 華東師范大學學報：自然科學版，2018（5）：164-171.

[24] 劉榮凱，孫忠林. 針對K-means初始聚類中心優化的PCA-TDKM算法[J]. 軟件導刊，2018，17（9）：85-87，91.

[25] 許強. 基于Spark的話題檢測與跟蹤技術研究[D]. 成都：電子科技大學，2018.

[26] 張尚韜. 網絡輿情話題檢測技術研究[J]. 廣東石油化工學院學報，2017，27（3）：41-45.

（責任編輯：杜能鋼）