余奎鋒,段桂華,時翔
(中南大學計算機學院,湖南長沙,410083)
普通高校招生考試是與萬千學子前途密切相關的重要考試,它的重要性不言而喻。如何最大化利用自己的分數進入理想的學校,是每個高考學子迫切想要解決的問題。自高考管理信息化建設以來,各專業領域專家一直致力于探索高考志愿填報的有效方法[1]。涉及高考科目、志愿填報[2]、考試內容等方面的研究成果很多,主要包含我國高考志愿填報的改革[3]、影響因素[4]、機遇與挑戰、信息化應用[5-6]和算法應用[7]等。模糊聚類算法由于可以利用數學方法來量化樣本間的模糊關系,能提高樣本分布特征描述的準確性[8],因而應用于各個領域,其中,模糊C 均值聚類算法FCM (fuzzy C-means)自提出后迅速成為數據挖掘研究的熱點,并衍生出許多性能優異的改進算法[9-10]。FCM具有能自動對樣本數據進行分類、聚類速度快等優點,被廣泛運用于圖像處理[11]、數據分析[12]、模式識別等領域。在高考志愿推薦方面,嚴衛[13]利用模糊聚類的方法對高考志愿推薦進行研究,考慮了升學因素、就業因素、名校因素和成本因素等,個性化選擇它們的比例進行模糊聚類,得到高考志愿推薦結果。任建濤[14]提出利用模糊C-均值聚類的方法,再根據用戶自己選擇的推薦策略分配,給出最后的推薦結果。這些推薦算法考慮的因素比較片面,主要針對學校本身因素進行關聯,忽略了學校歷年投檔線對應省排名位次、社會影響力排名等對志愿填報的影響,因而不夠準確。目前,市面上的一些比較成熟的志愿填報輔助系統[15]主要根據分數和投檔線對應省排名位次進行推薦,推薦結果多而繁雜,最終還需要用戶自己篩選決定,缺乏智能化和個性化的特點。本文作者在模糊均值聚類算法基礎上,提出一種應用于高考志愿推薦的多特征權重模糊聚類算法MFW-FCM(FCM with multiple feature weights)。該算法引入帶權重的多重影響因素,通過建立基于院校所在地區、院校實力排名、院校影響力、院校投檔線對應省排名等可能影響高校錄取分數線的多參數模型,再根據用戶自身的需求進行聚類,給出推薦結果。此外,基于多特征權重模糊聚類算法(MFW-FCM)建立了1個高考志愿推薦原型系統,輔助考生進行志愿填報。為了提供更加準確、清晰的推薦結果,本系統根據報考策略的風險性程度,將推薦結果分為3 類即沖、穩、保,分別代表可能會被錄取、被錄取的概率很大和肯定能被錄取。考生可以根據自身情況,調整這3類推薦結果,選擇更加符合自身需求的高考志愿填報方案。
本文提出基于多特征權重模糊聚類算法(MFW-FCM)并結合位差法和模糊C均值聚類算法,引入院校歷史分數線和投檔線對應省排名、院校實力、院校社會影響力等對高校錄取投檔線有影響的參數,建立多參數函數。根據考生的高考分數或省排名,得到可能匹配學校的錄取概率。基于FCM 聚類算法,結合多參數函數、可能匹配學校的錄取概率和用戶的個性化選擇,給出最后的推薦結果。MFW-FCM算法結構如圖1所示,包括數據預處理、特征篩選和模糊聚類3步。
1)數據預處理,即對高考數據進行查漏補缺,將整理后的數據存入數據庫。
2)特征篩選和離散度劃分,即對篩選出來的結果進行評估分類。
3)確定每個特征的權重之后進行模糊聚類,然后將結果排序,最后產生推薦的結果集。
MFW-FCM 算法的數據來源于招生考試信息港、中國教育在線、新東方高考網、高考網、中國校友網等各大高考咨詢網站,利用爬蟲技術獲得。數據包括省文理科一批、二批、三批招生的錄取分數線、擬錄取人數、各科錄取分數線等基本錄取信息、檔分一分段統計表等。
首先對爬取的數據進行清洗和預處理,去掉冗余和填補缺失的數據。例如,有些院校存在部分年份錄取分數線缺失的情況,采用以往與其最接近的幾所高校在對應年份錄取分數線的平均分進行填充。另外,有些學校存在改名或者院校合并的情況,如“***學院”改成“***大學”,在查詢確認信息之后,將所有的記錄改成現有的學校名稱。根據中國大學本科畢業生就業質量排行榜[16]將高校的就業情況等級量化成評分,將校友會中國大學排名和評星[17]量化成院校綜合實力,將最終形成的數據存放到全國各高校綜合素質評分表中,如表1所示。
首先根據用戶的分科和省排名,搜索歷年數據中投檔線對應省排名至少有1年大于用戶省排名即目標排名的學校,選取排名前50 所高校進入之后的篩選流程。假設用戶查詢的條件為湖南省理科,高考省排名為5 000 名,分數為600 分,所得MFW-FCM算法得到的部分高校信息如表2所示。
針對每一所候選高校,基于學校的相關信息進行評分,評分指標包括該校近n年的投檔線對應省排名、錄取分數線離散化程度、歷年的高考人數與投檔線對應省排名的離散化程度、歷年的投檔線對應省排名與省控線分數省排名的離散化程度以及該校的社會影響力評分等。根據這些評分指標,獲得5個用于確定最終目標院校分類的高校評估指標,包括近n年內的投檔線對應省排名大于目標排名的年份數占比p、投檔線對應省排名與目標排名的距離離散度dt、投檔線對應省排名與省控線分數省排名的均方差dc、投檔線對應省排名與當年參加高考人數之間的均方差ds以及高校社會影響力評分df。

圖1 算法結構Fig.1 Algorithm structure

表1 全國各高校素質評分(部分)Table 1 Quality evaluation of colleges and universities in China(part)
1)高校近n年內的投檔線對應省排名大于目標排名的年份數占比p為

其中:y為大于目標分數的年份數量。例如,在湖南省2014—2018 年這5 年的投檔線對應省排名中,中南大學分別為4 215,4 512,4 728,5 050 和4 706,故中南大學5 a內大于目標排名的年份數占比p為20%;四川大學的投檔線對應省排名分別為5 952,5 446,6 089,6 093,5 235,故四川大學5 a內大于目標排名的年份數占比p為100%。
2)高校投檔線對應省排名與目標排名的距離離散度dt為
其中:ri為高校第i年的理科投檔線對應省排名;s為考生分數對應的省排名即目標排名。同樣以中南大學為例,目標排名是5 000,則可以計算中南大學投檔線對應省排名與目標排名之間的離散度dt為0.040 34。
3)高校投檔線對應省排名與省控線對應排名距離的均方差dc為

其中:ui為高校第i 年理科的投檔線對應省排名與該年省控線對應排名的差值;u 為n 年中所有投檔線對應省排名與省控線排名差值的平均值。根據表3可以計算得到中南大學的投檔線對應省排名與省控線排名距離的均方差dc為6 912.26。
4)高校投檔線對應省排名與當年參加高考人數距離的均方差ds為

其中:ci為高校第i 年的理科投檔線對應省排名在該年參加高考理科考生人數的占比;f 為近n 年內該校理科投檔線對應省排名在參加高考理科考生人數的占比的平均值;ds為得到的投檔線對應省排名與當年參加高考人數之間差值的均方差。湖南省2014—2018 年高考總人數如表3 所示,選取理科考生的人數進行計算,同樣以中南大學為例,經計算ds為0.026。

表3 湖南省理工類第一批省控線和人數分布Table 3 The first batch of the minimum admission control score lines and population distribution of science and engineering in Hunan Province
5)高校社會影響力排名因素df為

其中:ti為該校第i年的影響力得分;maxFi表示第i 年的所有院校影響力最高得分;minFi為第i 年的所有院校影響力最低得分;n 為記錄的年份數量;df為該校的社會影響力得分。以中南大學為例,中南大學2015—2016,2016—2017,2017—2018,2018—2019 年這4 個階段社會影響力得分分別為46.69[18],45.34[19],44.33[20]和46.19[21],可以算出中南大學的社會影響力得分df為0.471。
6)將這5個指標綜合進行評分,建立多元線性函數,用于評估目標分數被高校錄取的概率a。
為了方便進行對比,需要將之前得到的所有高校的4項指標dt,dc,ds和df進行歸一化處理。歸一化方式為

以各項因素的重要性為基礎,經過影響高校錄取投檔線的程度不同和多次實驗結果對比,最終線性函數包含p,各項系數設定為0.68,0.12,0.05,0.05 和0.10。因為離散度越高,錄取概率就越低,且院校影響力越大,錄取的難度也會增大,所以,a的設置如下:

根據該公式,可得到目標分數被中南大學錄取的概率a為0.336 5。
用同樣的方式對50 所候選高校進行計算,基于計算結果對高校進行分類:a<0.6 的高校分為一類,作為“沖”的策略推薦;0.6≤a<0.8 的高校分為一類,作為“穩”的策略推薦;a≥0.8 為一類,作為“保”的策略推薦。
1.3.1 特征選擇與權重的選擇
根據目標院校篩選與評估分類結果,在每一類中進行模糊聚類。在模糊聚類中,選取學校的綜合實力排名、學校就業率排名、學校所在地區排名、學校所擁有的國家資助排名等特征,由用戶根據自身情況,將特征的重要性從高到低排序,以此對應著不同的權重,這4項指標的權重從高到低依次選取為2.0,1.5,1.0 和0.5。通過將權重加入到各個分類的4項指標中,將對應的離散化程度增大,擴大學校之間的差異,提高C均值模糊聚類結果的準確性。
1.3.2 聚類數與模糊因子的確定
在FCM 算法中,需要確定聚類數c 和模糊因子m,其中,模糊因子m對于模糊C均值聚類的聚類結果影響很大[22]。聚類結果為各聚類中心、各點到聚類中心的距離矩陣以及隸屬度矩陣。為了得到最貼近用戶需求的聚類中心以及最佳隸屬度,進行對比實驗。由于在樣本量不大時過多的聚類會失去意義,并且得不到足夠多的聚類簇中樣本數,因此,實驗選取的聚類數c 分別為2,3 和4。文獻[23]提出m 的經驗取值范圍為1.1≤m≤5.0,按照聚類有效性問題研究的結果[24],m的取值范圍可限制為1.5≤m≤2.5,經綜合,在每種聚類數中選取m取值由1.1逐增至2.1,得到每次聚類結果的聚類中心以及隸屬度,如圖2~4所示。
從圖2~4可見:隨著m增大,隸屬度普遍呈減小趨勢,但是在c=3時,減小趨勢趨于緩和,并且這3種策略下的隸屬度較接近,經綜合,最終選取c=3,m=1.1,進行FCM模糊聚類。將2.2節中得到的“沖”“穩”“保”這3 類高校分別進行模糊聚類,每一類高校將得到的3個聚類中心和對應的隸屬度。在這3個聚類中心中,根據學校的綜合實力排名、學校就業率排名、學校所在地區排名、學校所擁有的國家資助排名這4項指標,選取與用戶需求最接近的1個。從圖3可以看出:各推薦策略下模糊聚類的隸屬度非常高,證明聚類簇中高校特性相似度高,能夠得到十分接近于用戶需求的結果。

圖2 c=2時隸屬度隨m的變化Fig.2 Change of memberships with m when c=2

圖3 c=3時隸屬度隨m的變化Fig.3 Change of memberships with m when c=3

圖4 c=4時隸屬度隨m的變化Fig.4 Change of memberships with m when c=4
1.3.3 聚類結果的輸出
最后將“沖”“穩”“保”3個篩選后的聚類結果輸出,然后在每個聚類結果之中,按照目標分數被高校錄取的概率由小到大進行排序,得到所有候選高校的基本信息,與每一類的分類和排序后的結果組合起來,根據用戶自己選擇的“沖”“穩”“保”3個分類的選項個數,給出相應學校推薦的個數。最后輸出學校的基本信息以及學校的推薦策略,方便用戶進行選擇。
基于提出的多特征權重模糊聚類算法(MFW),本文結合用戶需求,采用Django后端框架、Vue前端框架和MySQL 數據庫,構建1 個基于多特征權重模糊聚類的高考志愿推薦系統CEVRS(college entrance voluntary recommendation system)。
CEVRS 中設計了用戶信息表、用戶推薦表、省控線表、學校信息表、專業信息表、招生信息表、錄取信息表、城市排名表、資金排名表、學校就業率表等。錄取信息表中存放了從網絡上爬取到的2005—2018 年文理科各高校在各省的錄取分數線,再根據歷年的一分一檔表形成錄取名次信息存入數據庫中。
系統的主要功能包括高考相關信息的咨詢和高考志愿填報的推薦2個主體部分。
1)高考信息咨詢。高考信息咨詢功能提供包括院校信息、專業信息、高校歷年錄取分數線和錄取名次變化、高校各項排名等各項信息的查詢。
2)高考志愿填報。志愿推薦功能是系統最核心的功能,考生提供其高考分科以及高考排名和成績,并給出想要的“沖”“穩”“保”這3種推薦的個數,選擇地區、綜合實力、就業率、國家資金這4個屬性中重要性的先后順序,然后根據所給信息,在后臺經過搜索和計算,給出相應的3種推薦策略。
系統判斷用戶的登錄狀態,根據用戶注冊情況派發相應的模塊功能。非注冊用戶只能查看高校信息,注冊后會加入用戶信息表中,已注冊用戶可以使用系統完整的功能,包括查看專業信息、高考志愿推薦等。
用戶登錄后可以在系統中查詢高校信息、專業信息以及各省內高考信息。以湖南省為例,湖南省近年內省控線變化如圖5 所示。從圖5 可見:近年來各批次錄取分數線的變化較大,但批次之間的差距變化并不大。

圖5 湖南省本科一批二批省控線走勢Fig.5 Trend of the minimum admission control score line of the first batch and the second batch of undergraduate in Hunan Province
高考志愿推薦功能需要首先輸入用戶基本考試信息。假設湖南省某理科考生的高考成績對應省排名位次為5 000名,使用本系統時,考生選擇理科,再輸入高考省排名5 000 名,按照自身興趣,選擇報考學校的重要性排序為所在城市、綜合實力、就業率和國家資金,再選擇3種推薦策略各自的推薦個數分別為3,4和4,點擊查詢按鈕即可得到推薦結果,推薦結果如圖6所示,其中,圖6(a)所示為推薦的院校、錄取批次、填報策略以及推薦的程度,讓學生根據自己的情況再進一步進行個性化填報選擇。用戶點擊查看詳情能夠生成該校2014—2018 年的錄取排名走勢和2005—2018年的錄取分數線與對應批次省控線的對比走勢。例如用戶點擊查詢中南大學的詳情,查詢中南大學近年來錄取分數線對應省排名變化(圖6(b))以及錄取分數線和對應的湖南省理科一批省控線變化示意圖(圖6(c)),可以看到,中南大學2014—2018年的錄取投檔分數線對應省排名在4 200~5 000,在湘理科投檔線與理科一批錄取分數線的距離逐年增大。
本系統在2019 年高考結束后,共150 名19 屆高考考生試用了本系統,并隨機模擬了350名考生的高考分數,其中一本考生150 名,二本考生150名和三本考生200名,對這500名考生的數據進行測試,每名考生“沖”“穩”“保”策略的推薦個數為3,3和4,院校錄取分數小于考生分數則視為成功命中,推薦結果如表4所示。
從表4可見:推薦結果為“沖”“穩”“保”策略的準確率依次提升,且一本、二本、三本的相應準確率依次降低,這是因為三本的學校多,學校之間的差異性較小。在推薦結果中,“保”策略的推薦準確率可達100%,“沖”策略的推薦準確率最低為36.9%,最高為62.2%;“穩”策略的推薦準確率最低為66.2%,最高為89.3%。
為驗證推薦模型的實際效果,選取市面上已有的能夠提供不同風險推薦策略以及錄取概率評估的高考志愿推薦系統進行對比實驗,進行不同分數段的縱向對比測試和不同系統之間的橫向對比測試。經過分析,選擇完美志愿網[15]和優志愿[25]這2個擁有良好口碑和龐大用戶群體的高考志愿推薦系統進行對比測試。
3.3.1 測試實驗設計
1)實驗數據。實驗對象統一設定為2019 屆考生,所在省份為湖南省。實驗選取6 項分數區間:652 分以上;(600,652]分;(550,600]分;(500,550]分;(475,500]分和(450,475]分。在每項分數區間隨機選取文理科排名及對應分數各50 名輸入到3個系統中,共600條測試樣例,分別記錄每個系統中各個排名的推薦結果,共獲得推薦院校數量為49 143個。
2)測試結果評估標準設計。測試收集的數據統一采用2019 年各高校在湖南省的錄取情況進行驗證。3 個系統都能提供3 類報考風險下的志愿推薦,分別記錄每個分數的各個風險推薦院校。因為平行志愿的填報方式中,每名考生最多只能填報10 所高校,所以,當某項推薦分類下的推薦院校不足10 個時全部記錄,超過10 個時只記錄前10個。

圖6 推薦結果Fig.6 Recommended results

表4 推薦結果準確率Table 4 Accuracy of recommended results
實驗定義2個推薦結果評估指標如下。
1)某個分數段內各分類下推薦準確率為
其中:n為該分數段內測試排名個數;ei為第i個測試排名得到的該推薦分類下錄取投檔線排名大于目標分數對應排名的院校個數;qi為第i 個測試排名得到的該分類下的所有推薦院校個數;h為該分數段的此分類下的院校推薦準確率。該指標用于評價推薦志愿推薦的準確性,尤其是用來評價“穩”類型以及“保”類型下的推薦準確率。

2)某個分數段內“沖”類型院校推薦的分數最大化利用率。若推薦院校的實際錄取投檔線排名大于目標排名且誤差不超過10%,則可視作該推薦院校滿足分數最大化利用。其中:n為該分數段內測試排名的個數;?i為第i個測試排名下“沖”類型推薦院校中滿足院校實際錄取分數線對應省排名大于測試分數對應省排名且不超過10%的推薦院校個數;si為第i 個測試排名下的“沖”類型推薦院校個數;m為該分數段內“沖”類型推薦下的分數最大化利用率。本測試指標用以評估“沖”類型院校推薦結果中院校實際錄取分數線與目標分數的差距足夠小的院校比例。
3.3.2 測試結果分析
統計本文設計的CEVRS、完美志愿網和優志愿網6 個分數段下隨機抽取測試分數的推薦結果,對于每項測試分數,3個系統都能給出“沖”“穩”“保”這3項不同風險的報考推薦。使用2019年各高校在湖南省實際錄取投檔線以及對應的省排名進行對比驗證,統計各個分數段下,所有測試分數所對應的“沖”“穩”“保”這3類院校推薦中的推薦院校準確率及其平均值,結果如表5所示。表5 中,最后1 列為各個推薦系統中所有分數段中各項分類推薦的綜合推薦準確率。選取3個推薦系統在6 個分數段的推薦院校平均準確率繪制折線圖,如圖7所示。

表5 各系統錄取推薦準確率統計表Table 5 Accuracy statistics of admission recommendation by system

圖7 各系統平均準確率對比圖Fig.7 Comparison of each system average accuracy rate
對表5和圖7進行分析可以得到:
1)CEVRS 的“沖”類型推薦結果準確率隨著測試分數的降低而升高,“穩類型”推薦結果準確率隨著測試分數的降低而降低。但在6 個分數段中,推薦準確率基本超過其他2 個系統的準確率,綜合推薦準確率比其他2個系統的高。這是因為隨著考生分數降低,同樣的分數差距導致對應省排名的變化逐漸增大,并且考生能夠選擇的院校也變得越來越多,對應分數段院校的錄取排名變化幅度也會越來越大,所以,在進行抽選實驗時,就會導致“穩”類型推薦結果準確率下降。又因為考生分數越高,相應分數區間內的高校錄取排名變化幅度越小,使得“沖”類型預測推薦更加困難,所以,分數越高,“沖”類型推薦結果準確率越低。
2)完美志愿網在分數段652 分以上以及(600,652]分這2 個分數段中,“沖”類型推薦與“穩”類型推薦的推薦準確率較高,并且推薦分數最大化利用率同樣較高。但根據實際推薦統計,在652 分以上和(600,652]分這2 個分數段的推薦結果中,“沖”類型與“穩”類型下的推薦院校個數非常少,多數不超過2個,甚至出現“沖”類型與“穩”類型推薦院校個數為0的情況。錄取分數越高的學校,每年的錄取分數對應排名越穩定,因此,完美志愿網在這2 個高分段區間推薦效果較好。
優志愿網在652 以上、(600,652]分和(550,600]分這3 個分數段的預測推薦中,“沖”類型推薦結果與“穩”類型推薦結果準確率較低,尤其是“沖”類型的推薦結果準確率非常低。
CEVRS 在652 以上、(600,652]分和(550,600]分這3 個分數區間的預測結果中,“穩”類型的推薦結果準確率非常高,尤其是在652分以上和(600,652]分這2 個分數區間的“穩”類型推薦結果準確率能到達97.1%和90.9%。“沖”類型的推薦結果中準確率也能到達40%左右。
3)完美志愿網在(475,500]分和(450,475]分這2 個分數段中,“沖”類型推薦結果以及“穩”類型推薦結果準確率較低,尤其是“沖”類型準確率最低,只有40.8%。
優志愿網在(475,500]分和(450,475]分這2個分數段中,“沖”類型院校推薦與“穩”類型院校推薦準確率較高,但(450,475]分這個分數段中“保”類型推薦準確率只有67.8%。
CEVRS 在(475,500]分和(450,475]分這2 個分數區間中,“穩”類型志愿推薦結果中的準確率開始下降,總體穩定在60%左右。但“沖”類型志愿推薦結果的準確率較高,最高能夠達到66.8%。
在獲取推薦院校尤其是“沖”類型推薦院校時,考生們不僅關注推薦的準確率,而且更加關注分數的最大化利用率,因為考生們在“沖”的心理狀態下,更加希望自己能夠進入分數滿足情況下的最好高校,因此,還需要對3項推薦系統的各分數段下推薦結果的分數最大化利用率進行統計。根據設定的計算指標,統計3個系統各個分數段的“沖”類型分數最大化利用率和所有分數段的分數最大化利用率的平均值,作為綜合分數最大化利用率,統計結果如表6所示,根據統計結果繪制折線圖,如圖8所示。

表6 “沖”類型的分數最大化利用率統計Table 6 The maximization score utilization statistics of"risky"type%

圖8 各系統分數最大化利用率對比圖Fig.8 Comparison of the maximized utilization ratio of various systems
對“沖”類型下的分數最大化利用率的統計結果進行對比分析,可得出如下結論:
1)在3個推薦系統各個分數段下“沖”類型推薦結果中,分數最大化利用率隨著分數降低而增大。但本系統在600分以下的所有分數段中,“沖”類型志愿推薦結果最大化利用率均比其他2個系統的高,且本系統的平均分數最大化利用率比其他2個系統的高。
2)CEVRS 在(450,475]分的“沖”類型推薦院校中,“沖”類型志愿推薦結果的分數最大化利用率能到達60.1%,與“沖”類型推薦結果的準確率接近,也就是說,在該分數段內,“沖”志愿推薦結果中成功預測的院校基本能夠實現分數利用最大化。
3)優志愿網在652 分以上時,“沖”類型推薦的最大化利用率較高,這是因為兩者實際提供的“沖”類型院校推薦個數較少,且分數較穩定。本系統考慮了2014—2018 年的所有數據,近3 年高分段的院校位置趨于穩定,因此,導致高分段下“沖”類型推薦院校的分數最大化利用率降低。
因為存在時效性,本次測試只采用2019 年的高考數據進行試驗的對比驗證,難免會造成誤差,若后續能增加不同年份的預測對比,則將使預測結果更加準確。因為低分段中,1分之差會導致排名差距過大,難以確認每一個具體排名以及錄取情況,所以,統計低分段預測結果時可能存在誤差。
1)基于C均值模糊聚類(FCM),引入院校歷史分數線和投檔線省排名、院校實力、院校社會影響力等對高校錄取投檔線有影響的參數,提出了多特征權重模糊聚類算法(MFW-FCM)。根據用戶對填報院校的個性化需求,提供“沖”“穩”“保”3 種類型高考志愿推薦。
2)基于提出的MFW-FCM 算法,實現了高考志愿推薦原型系統。系統操作方便,實用性強,在2019年的考生中進行實際檢測,推薦準確率高,可幫助考生最大化利用自己的分數,獲得滿意的志愿填報結果。
3)系統推廣應用后,隨著用戶數增加,后續可以考慮加入反饋機制,自適應地對模型進行優化,使推薦的個性化需求更加準確。