基于分治策略歸并算法的考研擇校指南平臺研究

李博涵 王紅蕾 青島黃海學(xué)院

據(jù)最新統(tǒng)計(jì)，2019年研究生招生考試考生已達(dá)285萬人，比去年增加47萬人。但是，考研時(shí)對報(bào)考學(xué)校的選擇成為很多應(yīng)屆生面臨的首要問題。有些同學(xué)因?yàn)椴涣私鈭?bào)考的相關(guān)知識而達(dá)不到預(yù)期的報(bào)考效果，甚至有些同學(xué)因此錯過了深造的機(jī)會。

1 歸并算法與分治策略

對于此類問題我們首先考慮的是歸并算法，于是我們在已有的歸并算法基礎(chǔ)上做出了改進(jìn)。首先我們先向內(nèi)存申請空間，該空間存儲排序序列之和。然后設(shè)置狀態(tài)指針，賦予指針初始值進(jìn)行合并空間操作，這一步的目的是進(jìn)行目標(biāo)院校的聚類操作，設(shè)置目標(biāo)狀態(tài)量作為指針改進(jìn)原有的歸并算法，將目標(biāo)院校，目標(biāo)專業(yè)，師資力量，科研狀況，生活環(huán)境，學(xué)習(xí)氛圍以及綜合排名等作為序列。同時(shí)設(shè)置新的目標(biāo)狀態(tài)量作為新的指針，用來合并分?jǐn)?shù)、興趣、排名等序列與前序列進(jìn)行擬合，執(zhí)行歸并操作。

本文在數(shù)據(jù)結(jié)構(gòu)上基于歸并技術(shù)，但在歸并技術(shù)上，我們改進(jìn)的算法復(fù)雜度低，結(jié)構(gòu)相對簡單，實(shí)現(xiàn)相對容易，更實(shí)用，更適合數(shù)據(jù)聚類分析。擇校系統(tǒng)有大量的數(shù)據(jù)，它可以被視為采樣點(diǎn)，每個采樣點(diǎn)都有不同的屬性，輸出的結(jié)果是根據(jù)候選人的需要。根據(jù)不同屬性進(jìn)行數(shù)據(jù)分類，從而找到最合適的學(xué)校類型信息。

2 改進(jìn)的人工魚群算法

面對龐大的數(shù)據(jù)量與篩選數(shù)值，歸并算法執(zhí)行起來顯然力不從心，所以我們想到使用仿真技術(shù)的加持進(jìn)行分治，兩者配合使用有效的縮短了查詢所用時(shí)間亦提高效率。

首先，輸入算法的初始值，包括人工魚的范圍、位置坐標(biāo)、魚群的擁擠因子等等。將初始迭代次數(shù)設(shè)為0，然后在范圍內(nèi)生成n個隨機(jī)人工魚個體并計(jì)算隨機(jī)初始魚群中個體的食物濃度，并在公告欄中篩選出最大值。人工魚群個體通過模擬魚群的聚集和覓食行為，不斷地改變其狀態(tài)，經(jīng)過一定時(shí)間后產(chǎn)生新的魚群。每只人工魚移動一次后，它會檢查自己的狀態(tài)，并將其與公告板上的狀態(tài)進(jìn)行比較。如果它比公告板更好，它會將其當(dāng)前狀態(tài)更新到公告板。最后確定迭代次數(shù)是否達(dá)到最大值，如果達(dá)到最大值，則將結(jié)果輸出到公告板上，否則，將從改變狀態(tài)產(chǎn)生新的魚群開始繼續(xù)執(zhí)行。

根據(jù)人工魚群的行為描述可以得到每條人工魚個體都是依據(jù)其視線范圍搜尋其目前所處的境以及伙伴的狀況，由此達(dá)到幾個局部極值附近聚集人工魚的效果。通過這個方法我們不難發(fā)現(xiàn)目標(biāo)函數(shù)值較大的人工魚聚集在較大的值域附近，從而得到全局極值域。

本文將人工魚群算法運(yùn)用到擇校最優(yōu)解中，首先選取目標(biāo)函數(shù)為考生的擇校信息與某學(xué)校的相似度最高，數(shù)學(xué)模型如下：

由以上步驟可知，人工魚算法可以在較短時(shí)間內(nèi)將某個數(shù)據(jù)最近距離的極值點(diǎn)匯聚在一起，但是考慮到考生在檢索過程中可能不會將所有元素都輸入或者一些用戶的檢索歷史比較少或者比較多，都會造成一定的誤差，因此本文又采用了稀疏矩陣的方法將該系統(tǒng)進(jìn)行進(jìn)一步完善。

3 稀疏矩陣

因?yàn)榭忌鷮W(xué)校的要求比較繁多，本文將這些檢索的信息進(jìn)行融合，形成一種屬性，根據(jù)屬性相似來為數(shù)據(jù)稀疏的同學(xué)推薦一些學(xué)校。

通過計(jì)算考生檢索的相似度較高的信息，將它們列成一個集合{Uk}，記錄為稀疏矩陣，通過定義函數(shù)f(x，y，z)表示考生x與考生y關(guān)于某個要求的相似度。假設(shè)考生x與考生y都喜歡學(xué)術(shù)類比賽較多的學(xué)校，則 f(x，y，z)=1，否則 f(x，y，z)=0?？梢酝ㄟ^以下算法進(jìn)行描述：用 表示對學(xué)術(shù)類比賽的要求所占的比重，

之后設(shè)置一個閾值w，如果考生所輸入的對學(xué)術(shù)類比賽的數(shù)據(jù)量低于w，則引入考生的屬性，融合考生屬性后，預(yù)測評分計(jì)算公式為：

其中N(x)表示所有與用戶屬性x相似的用戶集合，rxi表示用戶x對科技類比賽興趣i預(yù)測值。

通過以上三種方法的結(jié)合，既可以將系統(tǒng)內(nèi)所含院校進(jìn)行一個高效的分類，又可以更智能的為用戶匹配出適合自己的學(xué)校。

4 結(jié)語

本文采用計(jì)算機(jī)算法并進(jìn)行初步模擬，驗(yàn)證了算法的可行性，但是只有算法是遠(yuǎn)遠(yuǎn)不夠，我們還需要大量的數(shù)據(jù)來進(jìn)行模擬，以此達(dá)到最優(yōu)的效果。從國內(nèi)研究現(xiàn)狀來看，大多數(shù)學(xué)者只分析了考研擇校的現(xiàn)狀及影響因素，并沒有建立考研擇校指南平臺，沒有真正為考研學(xué)生提供便利。本項(xiàng)目結(jié)合軟件建模和計(jì)算機(jī)算法，創(chuàng)建指南系統(tǒng)，為考研學(xué)生提供真正的便利。