<input id="0qass"><u id="0qass"></u></input>
  • <input id="0qass"><u id="0qass"></u></input>
  • <menu id="0qass"><u id="0qass"></u></menu>

    2021 年 五一數學建模比賽 B 題(第四問至第六問)



    本人專挑數據挖掘、機器學習和 NLP 類型的題目做,有興趣也可以逛逛我的 數據挖掘競賽專欄。

    如果本篇博文對您有所幫助,請不要吝嗇您的點贊 😊

    賽題官網:http://51mcm.cumt.edu.cn/


    返回目錄

    第一題到第三題鏈接

    第四問

    題目是找出不同區域,相關性最高的事件。我們首先整理出事件類型-事件發生密度表格,如下所示:
    在這里插入圖片描述

    什么是相關性,我覺得有兩個理解:

    1. 相關性是否指:事件對區域而言呢?也就是找出,該區域某事件發生的密度,在其他區域時,發生密度相差很大的事件,可否如此理解?
    2. 相關性是否指:事件-事件呢?也就是,不同區域,事件 A 和事件 B 的相關性最大,找出 A 和 B 呢?

    第一理解

    對于第一個理解,可以沿著上表的行,求出事件的方差,方差最大的那個,就是啦。求出方差如下:
    在這里插入圖片描述

    于是,事件 7 是不同區域相關性最大的。

    第二理解

    第二個理解,沿著行,求出數據的相關性矩陣,找出最大的那個相關性,對應的兩個事件,就是啦。

    計算偏相關矩陣(使用Pearson相關系數),偏相關系數可以刪除其他因素的影響,所以使用偏相關系數:
    在這里插入圖片描述

    從上圖可以找出,事件 3 和 事件 7 在不同區域的相關性最高。

    第五問

    找出人口密度和事件密度的關系,首先就得統計出數據咯:
    在這里插入圖片描述
    其中事件密度是根據 16-20 年的總數據算出來的。

    如何找出關系呢?還記得問題二的方法嗎?

    我們首先畫出數據:
    在這里插入圖片描述

    大致可以猜測出,人口密度越大,事件密度(16-20年)越大。

    采用第二問的一元回歸方法,用線性函數去擬合數據,可得:

    在這里插入圖片描述

    我們可以用 R 方來評價模型的效果,計算出模型的 R 方為:0.9996,可見模型的效果很好。

    于是,人口密度和事件密度(16-20): y = 0.4116 x ? 0.02374 y=0.4116 x - 0.02374 y=0.4116x?0.02374

    第六問

    第六問是:

    目前該地有兩個消防站,分別位于區域J和區域N,請依據附件1和附件2,綜合考慮各種因素,建立數學模型,確定如果新建1個消防站,應該建在哪個區域?如果在2021-2029年每隔3年新建1個消防站,則應依次建在哪些區域?

    從第四問可知,由于人口密度和事件密度呈現線性關系,且是正相關,所以我們只需要考慮人口密度即可。

    先看第一問:該地已經有兩個消防站,另一個消防站該建在哪里?

    我們不妨先考慮簡單的:如果沒有消防站,那么消防站應該建在哪里?

    若沒有消防站,那么,我們可以用谷歌的網頁排行算法來解決這個問題。具體是:

    1. 把每一個節點看成網頁
    2. 把邊看成是網頁到網頁的鏈接,邊的權重視為鏈接的權重
    3. 把人口密度視為網頁的權重

    于是:就可以搜索出最重要的網頁,也就是,最重要的節點!

    那么,邊的權重,以及網頁的權重,該如何設置呢?

    首先得來看看 PageRank 算法的原理:
    在這里插入圖片描述

    PageRank 算法

    PageRank 算法要求每一個節點的權重之和是 1,權重是為了模擬每個網頁被點擊的概率(所有網頁被點擊的概率當然是 1)

    PageRank 算法要求每一個節點,散發出的所有邊,的權重之和,為 1。

    然后,PageRank 的算法如下(篇幅原因,就用專業的語言描述吧):

    設每一個節點的權重為 N i N_i Ni? i i i 是節點編號,為了方便,就即為 { 1 , 2 , ? ? , n } \{1,2,\cdots,n\} {1,2,?,n} n n n 為節點的數量;若 i i i, j j j 存在邊,記邊的權重為 w i j w_{ij} wij?。設收斂標準為:tol,最大迭代步長為:T,當前步長為:t,設權重傳遞時的損失參數為 α \alpha α算法如下:


    i n i t i a l N i ( 0 ) t = 0 for???i???in??? n : ????????for???j???in??? w i : ???????????????????? N j ( t + 1 ) + = α ? N i ( t ) ? w i j i f ???? t ≤ T : ???????? b r e a k w h i l e ∑ ∣ N i ( t ? 1 ) ? N i ( t ) ∣ ≤ t o l \begin{aligned} &initial N_i(0) \\ &t=0 \\ &\text{for ~ }\text{i ~ in ~ }n: \\ &\text{~~~~~~~~for ~ }\text{j ~ in ~ } w_i: \\ &\text{ ~~~~~~~~~~~~~ ~~~~ } N_j(t+1) += \alpha \cdot N_i(t) \cdot w_{ij}\\ &if \text{~~~~}t \leq T:\\ &\text{~~~~~~~~}break\\ &while \sum|{N_i(t-1)-N_i(t)}|\leq tol \end{aligned} ?initialNi?(0)t=0for???i???in???n:????????for???j???in???wi?:????????????????????Nj?(t+1)+=α?Ni?(t)?wij?if????tT:????????breakwhileNi?(t?1)?Ni?(t)tol?

    應用 PageRank

    如何應用呢?

    首先如何將節點設置為總和為 1?我認為直接將人口密度進行標準化即可。

    如何將某節點的邊,設置為總和為 1?

    當兩個點的距離越大時,應該賦予一個較大的權重。因為距離越遠,意味著越需要消防站。因此,如某點到 1,2, 3 的距離為 40,50,10,則權重分別為 0.4, 0.5, 0.1;

    帶入 PageRank 算法,可得結果如下:
    在這里插入圖片描述

    因此,當沒有消防站時,最重要的節點是 D。此時應該在 D 中設置消防站。從這個結果來看,還算是比較合理,畢竟 D 節點鏈接的邊最多,而且人口密度也比較多:
    在這里插入圖片描述

    J 和 N 設置消防站后

    沒有設置消防站是,我們用人口密度的標準化,作為節點的權重。

    在 J 和 N 設置消防站后,只需要將 J 和 N 的權重設置為 0 即可(或負數,意味著其鏈接的點的權重也會在迭代過程中下降),這里設置為負數也即,標準化后,J 和 N 的權重為 $ n(w)/15$。其中 n ( w ) n(w) n(w) 為該節點的邊數。

    之所以設置為 ? 2 / 15 -2/15 ?2/15,是因為圖的節點總數為 15 個,而我們認為一個消防站所起到的撲滅功能,頂的上平均意義上的 n ( w ) n(w) n(w) 個節點權重。當然,這個數值的設置有主觀性,it depends。

    此時依舊使用 PageRank 算法,可得:
    在這里插入圖片描述

    逐年建立消防站(失敗的嘗試)

    因為不知道人口密度的變化,所以按照我們的理論,這是一個靜態模型。2021 到 2029 一共 9 年,三年一次,迭代三次。按照上述算法,迭代三次即可:
    在這里插入圖片描述
    在運行代碼時,我們發現連續三次都需要在 I 中設置消防站,這明顯是不合理的。究其原因,就是因為負數在迭代過程中,對周圍的線條的影響,超出了我們主觀上的預估。

    但筆者在將有消防站的節點的權重,設置為 0 時,則出現下面的情況:
    在這里插入圖片描述

    改進方案

    本文所講解的 PageRank 是最簡單形式。實際上還有許多復雜的算法。對于設置了消防站的節點,我們可以將其視為懸浮節點,也即對所有節點都看成有鏈接,且鏈接是單向的,并根據距離,設置單獨地權重。

    至于如何實現,就要看大家啦!

    代碼與提問

    若需要代碼,請點贊,關注、私信、說明題目和年份

    如果有其他問題,請到評論區留言,私信提問,概不回答。也在此鼓勵大家獨立思考。

    本人不會回訪,不互關,不互吹,以及謝絕諸如此類事

    相關推薦
    ??2020 CSDN 皮膚主題: 技術黑板 設計師:CSDN官方博客 返回首頁
    多乐彩