回傳目錄

思路

具體思路請見：https://blog.csdn.net/weixin_42141390/article/details/106069244

回傳目錄

第一問

資料預處理

首先打開附件 2：

然后以留言詳情為輸入資料，以一級標簽為輸出標簽，于是問題轉換為一個文本分類的問題，因此，我們需要將非結構型文本資料轉換為結構型文本資料（表格）；將文本標簽（一級標簽）轉換為自然數，以表示類別，如下所示：

回傳目錄

二元語法

對于輸入文本，首先用二元語法對文本進行拆分，如下所示：

回傳目錄

詞袋模型

進行二元語法拆分后，我們需要進行特征提取，將上述文本結構轉換為結構化資料，我們將上述所有的資料的取值作為表頭，每一條資料，在某一列的取值為，其對應的二元字符，出現的頻次，

如第 0 條資料，列 “3區” 的取值 1；列“尊敬” 的取值為 0，不過，在實際編程上，可定不能直接用一個表格表示，因為轉換后的資料必然是極其稀疏的稀疏表格，并且，直接用中文字符來作為列名，也十分浪費存盤空間，本人曾經試過，若轉換為稀疏表格，則將占用 40 GB… 而我的小電腦才 8 GB 記憶體呀…

于是這里用稀疏矩陣的方式來存盤，比如將第一行存盤為：

[(0, 1),
 (1, 1),
 (2, 1),
 (3, 1),
...
 (90, 1),
 (91, 1),
 (92, 1)]

第二行存盤為：

[(7, 1),
(26, 1),
(73, 1),
(77, 1),
(93, 1),
...
(163, 1),
(164, 1),
(165, 1)]

轉換為稀疏矩陣后，由于輸入特征的數量很多，容易造成維度災難，所以需要采用一些過濾方法，這里采用卡方檢測法：卡方檢測法用于檢測兩個分布是否獨立，我們可以遍歷每一個輸入特征，與標簽做卡方檢測，若證明獨立，則可以排除掉當前特征，

這里設定卡方檢測的顯著水平為 0.001，原假設為當前輸入特征與標簽是獨立的，可得，那些保留下來的特征共 30291 個，

最后的出來的資料集為，一個 9210X30291 的稀疏矩陣：

回傳目錄

分類模型

機器學習方法

根據“沒有免費午餐定律”，我們首先從如下模型中篩選最佳模型：

但在此之前，先結合交叉驗證，網格尋優尋找最合適引數，引數網格和篩選結果如下：（其中隨機森林的基函式為最大深度為 5 的決策樹； AdaBoost 的基模型為邏輯回歸模型）

然后，在根據 5 折交叉驗證，計算最合適引數下，各模型的 F1 如下：

從各模型的 F1 的均值可以剔除決策樹、隨機森林和 kNN，剩下的模型差別均不大，但是，人們不能貿然地認為這些模型在效果上是 等 價的，因此，為了判斷這些模型是否等價，還需要采用 T 檢驗的方法，我們對上述保留下來的模型進行兩兩 T 檢驗：（原假設為均值相等）

可見，這些模型都是等價的，但由于 AdaBoost 耗費資源最多，訓練時長過長，運行時間過長，不建議選用，

個人覺得，除了 AdaBoost 之外，其他模型的性能如下表：

* 越多越好

分別訓練三個模型，并將資料集按 7:3 拆分為訓練集、測驗集，測出模型在訓練集、測驗集中的 F1 值如下所示：

回傳目錄

多層感知器

模型

因為我們將分類標簽視為 0/1/2 等自然數，所以這里可將分類問題看成一個回歸問題，（這也是一種解題思路吧，其實就是本人太懶了…）

當然，如果你想要按分類問題來做，那么利用深度學習的方法的話，你就必須進行 one-hot 編碼了！

設定網路的拓撲結構如下：

訓練演算法為：Adam； 評價指標為：均方誤差（MSE）；損失函式也是均方誤差，同時，對每一層隱藏層加上一個 dropout 率為 0.1 的 Dropout 正則化，

回傳目錄

結果

第二問

資料預處理

要從每一個群眾的留言中，收集某一時間段內群眾集中反映的問題，顯然屬于一個文本聚類的問題，如果將群眾相似的留言聚成一簇，即可將簇視為某個集中問題，根據該簇包含的留言條數、支持和反對的總數，并考慮其熱度隨時間的衰減，即可估計該問題的熱度，

為了提取出聚類簇中留言的問題描述，以及地點和人群，這里考慮使用關鍵陳述句提取演算法，從而自動生成關鍵句，再從關鍵句中人工提取出地點和人群，籍此就可以降低直接從留言詳情中，人工提取問題概述的作業量，

回傳目錄

分詞

首先，我們用一個條件隨機場來分詞，當然，條件隨機場是一個序列標注模型，屬于機器學習的一部分，為了訓練一個條件隨機場的分詞模型，我們用了開源的分詞資料集 MSR，最后訓練出以條件隨機場分詞模型，

以附件 3 的第一條為例，用條件隨機場分詞結果如下：

[座落, 在, A市, A, 3區聯豐路米蘭春天G2棟320, ，, 一家, 名, 叫, 一米, 陽光, 婚紗, 藝術, 攝影, 的, 影樓, ，, 據說, 年單, 這, 一個, 作業, 室, 營業額, 就, 上百萬, ，, 因為, 地處, 居民, 樓, 內部, ，, 而且, 有, 蠻長, 的, 時間, 了, ，, 請, 稅務局, 和, 工商局, 查, 一下, ，, 看看, 這個, 一米, 陽光, 有沒有, 正常, 納稅, ！, 如果, 沒有, ，, 應該, 會, 怎么, 操作, ！]

回傳目錄

停用詞過濾

采用雙向匹配法，運用 hanlp 自帶的停用詞字典，過濾掉那些沒有意義的詞和符號：

['座落', 'A市', 'A', '3區聯豐路米蘭春天G2棟320', '一家', '一米', '陽光', '婚紗', '藝術', '攝影', '影樓', '據說', '年單', '作業', '室', '營業額', '上百萬', '地處', '居民', '樓', '內部', '蠻長', '時間', '請', '稅務局', '工商局', '查', '看看', '一米', '陽光', '有沒有', '正常', '納稅', '沒有', '應該', '會', '操作']

回傳目錄

詞袋模型

和第一問一樣，我們依舊是用詞的頻次作為每一個特征的取值，以第一條為例，其值為：

{0: 1,
 1: 1,
 2: 1,
...
 32: 1,
 33: 1,
 34: 2}

第二條其值為：

{1: 3,
 2: 1,
 6: 1,
 15: 1,
 26: 1,
...
 76: 1,
 77: 2,
 78: 2}

詞袋模型有很多，除了單純地使用頻次外，還有使用 TF-IDF 的，但是使用 TF-IDF，會破壞資料的稀疏性，從而導致無法處理，所以這里只能采用頻次，但沒關系，能夠用就可以，

回傳目錄

PCA 降維

資料的特征個數，經過分詞、停用詞過濾、詞袋模型之后，共有 42754 個，我們將其降低至 1000 個，同時計算其貢獻和累計貢獻，圖如下：

回傳目錄

熱度挖掘

本文定義：話題熱度 = 話題留言數 + 點贊數 - 0.5 反對數；且熱度隨著時間的延遲而呈現指數下降，

話題——聚類

什么是話題？每條留言的背后都是一個話題，于是，肯定有些留言的話題是相似的，相同的，為了找出話題，我們可以采用聚類的方法，

注意：聚類并不能找出語意的相似，而是找出“表面”的相似，比如：
我是慢熱的人 和 他是慢熱的人 可能屬于一類，但 我是慢熱的人 和 我是內向的人 卻不是同一類，即使后者語意更加相近，反應的更近似于同一個主題，
但是，為了讓大家學習，我們這里采用聚類，在第三問，還有求相似度的，到了那里，我們再用其他方法好不？
其實這里主要是為了讓大家學習啦，不然我第一問就用分詞的方法了，何必再重復呢？希望大家能學到更多的東西，如果覺得這篇文章對你們有所幫助，請點贊咯~

如何聚類呢？這里采用 DBSCAN，

聚類結果如下：

{-1: 3629, 0: 3, 1: 2, 2: 227, 3: 2, 4: 3, 5: 2, 6: 2, 7: 2, 8: 2, 9: 2, 10: 3, 11: 2, 12: 2, 13: 2, 14: 2, 15: 3, 16: 4, 17: 2, 18: 2, 19: 2, 20: 2, 21: 2, 22: 2, 23: 3, 24: 3, 25: 3, 26: 3, 27: 2, 28: 2, 29: 2, 30: 2, 31: 2, 32: 2, 33: 2, 34: 2, 35: 3, 36: 2, 37: 2, 38: 2, 39: 2, 40: 2, 41: 4, 42: 2, 43: 3, 44: 3, 45: 2, 46: 3, 47: 5, 48: 3, 49: 3, 50: 2, 51: 2, 52: 2, 53: 2, 54: 2, 55: 2, 56: 3, 57: 3, 58: 3, 59: 2, 60: 4, 61: 2, 62: 2, 63: 2, 64: 2, 65: 2, 66: 2, 67: 2, 68: 3, 69: 4, 70: 2, 71: 2, 72: 2, 73: 2, 74: 2, 75: 2, 76: 2, 77: 3, 78: 4, 79: 2, 80: 2, 81: 2, 82: 2, 83: 2, 84: 3, 85: 2, 86: 2, 87: 2, 88: 2, 89: 2, 90: 2, 91: 2, 92: 3, 93: 2, 94: 2, 95: 2, 96: 2, 97: 2, 98: 2, 99: 2, 100: 2, 101: 2, 102: 2, 103: 2, 104: 2, 105: 2, 106: 2, 107: 2, 108: 2, 109: 3, 110: 2, 111: 2, 112: 2, 113: 2, 114: 2, 115: 2, 116: 2, 117: 2, 118: 2, 119: 2, 120: 2, 121: 2, 122: 2, 123: 2, 124: 2, 125: 2, 126: 2, 127: 2, 128: 2, 129: 3, 130: 2, 131: 2, 132: 2, 133: 2, 134: 2, 135: 2, 136: 2, 137: 2, 138: 2, 139: 2, 140: 2, 141: 4, 142: 2, 143: 2, 144: 2, 145: 2, 146: 2, 147: 2, 148: 3, 149: 3, 150: 2, 151: 3, 152: 2, 153: 2, 154: 2, 155: 2, 156: 2, 157: 2, 158: 2, 159: 2, 160: 5, 161: 2, 162: 2, 163: 2, 164: 2, 165: 2, 166: 3, 167: 2, 168: 2, 169: 2, 170: 3, 171: 2, 172: 2, 173: 2, 174: 2, 175: 2, 176: 2, 177: 2, 178: 2, 179: 2, 180: 2, 181: 2, 182: 2, 183: 2, 184: 3, 185: 2, 186: 2, 187: 2, 188: 2, 189: 2, 190: 2, 191: 2, 192: 2, 193: 2, 194: 2, 195: 2, 196: 2, 197: 2, 198: 2, 199: 2, 200: 2, 201: 2, 202: 3, 203: 4, 204: 2, 205: 2, 206: 2, 207: 2, 208: 2, 209: 2, 210: 2}

其中 -1 為游離個體，

我們把一個簇叫做一個話題，我們得出每一個話題的熱點計算公式如下：

{ y i = 10 + Y ? 0.5 N + Δ y i y i > 0 0 y i ≤ 0 \left\{\begin{array}{ll} y_{i}=10+Y-0.5 N+\Delta y_{i} & y_{i}>0 \\ 0 & y_{i} \leq 0 \end{array}\right. {yi?=10+Y?0.5N+Δyi?0?yi?>0yi?≤0?
Δ y i \Delta y_i Δyi? 為時間衰退，按一般觀點，熱度的衰退應該是呈現指數型的，所以我們將 Δ y i \Delta y_i Δyi? 定義為如下格式：
? Δ y = a exp ? ( b Δ t ) ? c -\Delta y=a \exp (b \Delta t)-c ?Δy=aexp(bΔt)?c
那么定義上述的引數呢？觀察資料可以發現，最近的留言時間為 T=2020-1-26 19:47:11；最遠的留言時間為：2017-6-8 17:31:20，時間間隔為 962 天，

挖掘所有課題，發現 10 + Y ? 0.5 N 10 + Y - 0.5N 10+Y?0.5N 取值最大為 2107，因此，我們定義：經過 962 天后，熱度應下降 2107，經過 962 / 2 962/2 962/2 天后，關注度下降 2107 / 16 2107/16 2107/16，據此可列出方程為：
{ a exp ? ( 0 ) ? c = 0 a exp ? ( 962 2 b ) ? c = 2107 / 16 a exp ? ( 962 b ) ? c = 2107 \left\{\begin{array}{l} a \exp (0)-c=0 \\ a \exp \left(\frac{962}{2} b\right)-c=2107 / 16 \\ a \exp (962 b)-c=2107 \end{array}\right. ????aexp(0)?c=0aexp(2962?b)?c=2107/16aexp(962b)?c=2107?
于是熱度下降函式為：
? Δ y = 262.125 exp ? ( 0.0023 Δ t ) ? 262.125 -\Delta y=262.125 \exp (0.0023 \Delta t)-262.125 ?Δy=262.125exp(0.0023Δt)?262.125

可得熱度結果如下：

最后得出前 10 熱點問題的所有留言如下：

回傳目錄

熱點描述

這里模仿 google 的 pagerank 演算法提出一種 textrank 演算法（前人做的），對于 pagerank，我們將網頁視為節點，節點的分數決定了其熱度，設節點 V i V_i Vi? 的分數為 S ( V i ) S(V_i) S(Vi?)，設節點 V i , V j V_i,V_j Vi?,Vj? 存在有向邊，則：

S ( V i ) = ( 1 ? d ) + d × ∑ V j ∈ In ? ( V i ) 1 ∣ O u t ( V j ) ∣ S ( V j ) S\left(V_{i}\right)=(1-d)+d \times \sum_{V_{j} \in \operatorname{In}\left(\mathrm{V}_{\mathrm{i}}\right)} \frac{1}{\left|\mathrm{Out}\left(\mathrm{V}_{\mathrm{j}}\right)\right|} S\left(V_{j}\right) S(Vi?)=(1?d)+d×Vj?∈In(Vi?)∑?∣Out(Vj?)∣1?S(Vj?)
S ( V ) S(V) S(V)的初始化為 1，KaTeX parse error: Can't use function '\]' in math mode at position 9: d\in(0,1\?]? 是一個常數因子，模擬用戶點擊網頁 V i V_i Vi? 的概率， O u t ( V j ) Out(V_j) Out(Vj?) 表示從 V j V_j Vj?出發鏈接到的節點的所有節點，

將 pagerank 推廣到關鍵句識別中，以句子為節點，設每條句子兩兩都存在鏈接，并記 d d d 為當前句子和其他所有句子之間的平均“間隔”，即處于中心的句子， d d d 越大，

由于所有句子都存在鏈接，所以上述公式不能用了，

因此，這是因為 ∣ O u t ( V j ) ∣ |Out(V_j)| ∣Out(Vj?)∣ 都相同，因此這里定義兩條句子的相似度如下：
B M 25 ( V i , V j ) = ∑ k = 1 n I D F ( term k ) T F ( term ? k , V i ) ( α + 1 ) T F ( term ? k , V i ) + α ( 1 ? β + β ∣ V i ∣ D L ) \begin{array}{r} B M 25\left(V_{i}, V_{j}\right)=\sum_{k=1}^{n} I D F\left(\text { term }_{k}\right) \frac{T F\left(\operatorname{term}_{k}, V_{i}\right)(\alpha+1)}{T F\left(\operatorname{term}_{k}, V_{i}\right)+\alpha\left(1-\beta+\beta \frac{\left|V_{i}\right|}{D L}\right)} \end{array} BM25(Vi?,Vj?)=∑k=1n?IDF( term k?)TF(termk?,Vi?)+α(1?β+βDL∣Vi?∣?)TF(termk?,Vi?)(α+1)??

其中 α , β = 1 \alpha, \beta=1 α,β=1， ∣ V i ∣ |V_i| ∣Vi?∣ 為句子 V i V_i Vi? 的單詞量， T F ( t e r m k , V i ) TF(term_k, V_i) TF(termk?,Vi?) 為單詞 t e r m k term_k termk? 在句子 V i V_i Vi? 中的詞頻， D F DF DF 為所有句子構成的合成檔案中，每一條句子的平均詞量，IDF 為逆文本頻率，計算公式如下：
I D F ( term k ) = log ? ( S D F + 1 ) I D F\left(\text { term }_{k}\right)=\log \left(\frac{S}{D F+1}\right) IDF( term k?)=log(DF+1S?)
這里的 D F DF DF 為合成檔案中，包含單詞 t e r m k term_k termk? 的句子數， S S S為合成檔案中，句子的總數，于是，仿照 pagerank，可得句子的分數如下：

S ( V i ) = ( 1 ? d ) + d × ∑ V j ∈ In ? ( V i ) B M 25 ( V i , V j ) ∑ V k ∈ Out ? ( V j ) B M 25 ( V i , V k ) S ( V j ) \begin{array}{l} S\left(V_{i}\right)=(1-d)+ d \times \sum_{V_{j} \in \operatorname{In}\left(V_{\mathrm{i}}\right)} \frac{B M 25\left(V_{i}, V_{j}\right)}{\sum_{V_{k} \in \operatorname{Out}\left(\mathrm{V}_{\mathrm{j}}\right)} B M 25\left(V_{i}, V_{k}\right)} S\left(V_{j}\right) \end{array} S(Vi?)=(1?d)+d×∑Vj?∈In(Vi?)?∑Vk?∈Out(Vj?)?BM25(Vi?,Vk?)BM25(Vi?,Vj?)?S(Vj?)?

我們將屬于前 10 熱度的，同一個話題的所有問題的詳細描述，合成一個檔案，之后，計算每一條句子的得分，最終找出得分最多的前三條句子作為關鍵句，即可得出問題描述，

對于時間范圍，我們將同一話題的所有問題資料的時間，的最近、最遠時間構成時間范圍即可，

至于地點和人群…，自己找吧 😂

回傳目錄

第三問

答復相關性

詞向量

首先用關鍵句提取演算法，從留言和答復中提取出三條關鍵句，之后比較這三條關鍵句的相關性即可，至于如何比較相關性，我們采用詞向量的方法，

什么是詞向量呢？詞向量是一個單詞的背景關系，意義相似的詞語，其背景關系也是相似的，根據這一點，每個詞語都存在一
個背景關系詞向量與之對應，使得統計模型能夠根據該單詞的詞向量，預測到該單詞，

背景關系向量：

“第八屆 泰迪杯 建模 挑戰 賽” ， 則 單 詞 “建模”的 背景關系向量為[第八屆， 泰迪杯， 挑戰，賽]，當然，所謂背景關系向量也是有長度限制的，如果語料庫太長，很顯然將所有的單詞作為背景關系是不可行的，這是就需要定義一個視窗，使得以本單詞為中心的，左右有限寬度的單詞，才構成背景關系向量，

one-hot 編碼法：

使 用 one-hot 編 碼 法， 可 轉 換 為 x = [ [ 1 , 0 , 0 , 0 , 0 ] T , [ 0 , 1 , 0 , 0 , 0 ] T , [ 0 , 0 , 0 , 1 , 0 ] T , [ 0 , 0 , 0 , 0 , 1 ] T ] x =[[1, 0, 0, 0, 0]^T , [0, 1, 0, 0, 0]^T , [0, 0, 0, 1, 0]^T, [0, 0, 0, 0, 1]^T] x=[[1,0,0,0,0]T,[0,1,0,0,0]T,[0,0,0,1,0]T,[0,0,0,0,1]T]，并與單詞 “建模”的 one-hot 編碼 y = [ 0 , 0 , 1 , 0 , 0 ] T y = [0, 0, 1, 0, 0]^T y=[0,0,1,0,0]T對應，

CBOW 模型 ：

上一小節我們知道，語料庫每一個單詞的 onehot 向量 y i y_i yi?，都對應一個或多個背景關系向量 x i x_i xi?，因此，若以 x i x_i xi? 為輸入，以 y i y_i yi? 為輸出，就可以訓練一個深度學習模型了，其中比較著名的就有 CBOW 模型，CBOW 模型實際上是一個三層的神經網路模型：

其中 x i , i ∈ { 1 , 2 , ? ? ? , C } x_i, i\in\{1, 2, · · · , C\} xi?,i∈{1,2,???,C} 為單詞 one-hot 編碼后的列向量， C C C 取決于視窗的大小，設視窗大小為 m m m, 則 C = 2 m 2m 2m，矩陣 W ∈ R n × ∣ V ∣ W \in R^{n×|V }| W∈Rn×∣V∣ 為 CBOW 網路的輸入層到隱藏層的權重矩陣， W ′ ∈ R ∣ V ∣ × n W^\prime \in R^{|V |×n} W′∈R∣V∣×n 為隱藏層到輸出層的權重矩陣，其中 n n n 為隱藏層的節點數， ∣ V ∣ |V| ∣V∣ 為語料庫中單詞“種”數， W W W 的第 i i i 個列向量為語料庫中第 i i i 個單詞的輸入詞向量，記為 w i w_i wi?；類似地， W ′ W^\prime W′ 中第 j j j 個行向量為第 j j j 個單詞的輸出詞向量，記為 w j ′ w^\prime_j wj′?，由于輸入詞向量離輸入層近，所以在應用中，一般拋棄輸出詞向量，將 輸入詞向量作為單詞的詞向量模塊使用，

因此，要求出每一個單詞的詞向量，求出 CBOW 模型的引數是關鍵，本質上，CBOW 模型也是一個機器學習模型，設 COW 模型的預測為 y ^ \hat{y} y^?，定義損失函式如下：
H ( y ^ , y ) = ? ∑ j = 1 ∣ V ∣ y i log ? y ^ H(\hat{y},y)=-\sum_{j=1}^{|V|}y_i \log{\hat{y}} H(y^?,y)=?j=1∑∣V∣?yi?logy^?
這里，我們還是使用 SHANG05 的開源語料庫 MSR 作為訓練集，訓練出一個隱藏層節點為 100 的 CBOW 模型，從而得出每一個單詞的詞向量，

回傳目錄

相似度計算

首先對于留言和答復，分別提取出 5 條關鍵句，然后，計算這 5 vs 5 的兩兩句的最大相關性作為最終的相關性，

那么，如何計算兩句的相關性呢？首先對句中的每一個詞，他們的詞向量取平均，從而得到一個稠密向量 s i s_i si? ，對于另一句也一樣，得出 s j s_j sj?，然后計算兩個向量夾角的余弦值，作為兩句的相似度，如下所示：
cos ? θ = s i ? s j ∣ s i ∣ × ∣ s j ∣ \cos \theta=\frac{\boldsymbol{s}_{i} \cdot \boldsymbol{s}_{j}}{\left|\boldsymbol{s}_{i}\right| \times | \boldsymbol{s}_{j} \mid} cosθ=∣si?∣×∣sj?∣si??sj??

最后得出的結果如下：

回傳目錄

答復完整性（代碼沒有實作）

本人理解的答復完整性，指的是陳述句是否通順（可能有些歧義，因此本人就不實作了），但句子是否通順，似乎也帶有非常大的主觀性，因此，本人采用一種類似于區域完整性的方法去評價，句子的通順性，具體如下：

為了評價答復的完整性與可理解性，本文將以相鄰兩個漢字為單位，逐一掃描留言答復，并匹配當前掃面是否存在于二元語法字典¹中，從而判斷留言的區域完整性，和可理解性，計算公式如下：
C = 1 ? N n o / L C = 1-N_{no}/L C=1?Nno?/L
其中 N n o N_{no} Nno? 為無法匹配的，句子中的二元對， L L L 為句子中二元對的數量，

代碼和資料

（關注一下唄 😁）代碼和檔案：https://gitee.com/zhuowoodbird/teddy_cup_C_2020

什么大佬好話就別說了，記得一鍵三連就可以了，咱們別做伸手黨哈… 博主這廂有禮

很想寫 2021 的泰迪杯 C 題，但怕呀… 所以希望這篇文章的解題代碼和思路，能夠為大家有一些參考作用吧

若果大家覺得這篇文章對大家有幫助，請不要吝嗇您的點贊 😊