基于DBSCAN聚類改進隨機森林算法的專利價值評估方法

李 玉, 王 利, 周志平, 趙衛東

(同濟大學電子信息與工程學院，上海 200093)

隨著經濟全球化的發展，科技創新已成為各國提升綜合國力的重要支撐。專利文獻是作為技術信息的最有效的載體，是知識產權的核心。隨著越來越多的有價值的專利商業化，準確評估專利價值的需求也逐漸增大。一個普遍適用于目前各種領域不同專利的價值評估指標體系和有效的評估方法是專利價值評估工作的關鍵。

關于專利指標體系的設計，中外學者都進行了相關研究。Lanjouw等[1]從公司的角度提供了專利權的評價方法，并通過關于專利指標和價值的實證研究，分析了13個用于商業目的的指標變量，同時還研究發現用綜合指標可以消減20%～73%的專利質量誤差，更好地評價專利質量。黃慶等[2]、李振亞等[3]、李偉等[4]運用層次分析法確定各指標權重。

關于專利價值評估方法，早期主要借用了資產評估中的成本法、市場法和收益現值等傳統方法[5]。眾多學者認為傳統的專利價值評估方法都是以市場為基準的方法，雖然較充分地捕獲了市場信息，但是通常耗時費力，主觀性強，也沒有考慮到應用專利權進行生產的特點。之后又引入了企業競爭優勢方法、模糊綜合評價方法、實物期權方法和組合預測等方法。然而這些評估方法在實踐中仍不夠成熟，受到較多條件的限制。經過中外學者們的研究，又出現了一些改進的評估方法。萬小麗等[6]將定性分析和定量分析相結合，從理論層面嘗試用層次分析法和模糊綜合評價法評估專利價值。綜合考慮多種因素的影響。夏軼群等[7]建立了一個有可替代性的不確定條件技術專利價值實物期權評估模型。李振亞等[8]提出的專利價值評估方法以技術質量指標、目標市場價值為基礎，量化了競爭程度和法律保護強度，通過數學運算來評估專利的價值，克服了傳統評估方法缺乏客觀性的弊端。

隨著近年來機器學習以及大數據的發展，在專利技術價值評估的研究中，許多學者開始使用機器學習算法取代傳統方法。如楊美妮等[9]基于3種機器學習模型對專利質量進行評估；張文德等[10]基于蟻群算法計算企業專利價值度；趙蘊華等[11]分別使用決策樹、支持向量機和神經網絡3種模型預測專利價值度，預測結果在總體趨勢上與真實數據呈現出一致性。

從專利自身的價值出發，選取合適的評估指標作為評估模型的輸入，使用隨機森林模型對專利價值進行預測評估，同時研究基于DBSCAN(density-based spatial clustering of applications with noise)聚類對傳統隨機森林模型進行改進，使用改進前后的模型分別在專利數據集上進行實驗得到專利的價值度。

1 專利價值評估指標選擇

為了能夠更加全面地考慮專利價值影響,需要綜合定性和定量的數據分析建立評估指標體系。目前，中外學者對評估指標的相關研究已經取得了不少的成果，參考王靜等[12]的專利價值指標值的確定方法，以及邱一卉等[13]利用分類回歸算法對專利評估指標的屬性選擇方法，基于已公開的專利自身文本和其基本屬性，選擇了專利數據庫中的18個屬性。屬性的數據集如表1所示。

表1 屬性數據集Table 1 Attributedata set

使用隨機森林算法將這18個屬性按重要性進行排序，讓它們更準確地反映專利價值度以及更加適用于評估模型的訓練。使用隨機森林計算特征重要性并將其按重要性從高到低排序。隨機森林包含很多決策樹，決策樹中的每一個節點都是某一特征將數據集分成兩部分的條件。這里以Gini不純度為選擇依據。

設有K個類別，pk代表類別k的樣本權重，Gini指數的計算方法如下：

(1)

那么特征Xj在節點m上的重要性，即節點m分枝前后的Gini指數變化量為

(2)

式(2)中：GIl和GIr分別表示分枝后兩個新節點的Gini指數。

如果特征Xj在決策樹i中出現的節點在集合M中，那么Xj在第i棵樹的重要性為

(3)

假設隨機森林中共有n棵樹，那么

(4)

最后，做歸一化處理：

(5)

經過特征重要性排序后，由于特征的選擇不一定代表著性能的提升，因此需要通過交叉驗證的方法來評估重要性排序前K個特征組合輸入模型的性能，得到圖1所示的結果。

圖1 不同特征數量的模型性能Fig.1 Model performance with different number of features

通過圖1可以看出，分類準確率首先會隨著特征個數的增加而遞增，當特征個數K=8時分類準確率最高，當K>8時分類準確率又逐步遞減最后趨向平穩。這是由于樣本特征稀疏時未能準確地描述樣本的分類信息，而當特征空間維度過高時數據中的冗余信息會影響分類器的準確率。經過選擇后的最佳特征子集如表2所示。

表2 最佳特征子集Table 2 The best future subset

2 評估方法

一個好的評估方法是決定專利價值評估是否有效的關鍵，將專利的價值量化為價值強度等級從低到高劃分為1～10類的專利價值度指標。基于上述對專利價值評估指標的選擇，專利價值評估被轉化為一個多分類問題，價值度作為分類標簽。選擇隨機森林算法訓練分類模型，并對原始隨機森林模型進行基于DBSACN聚類約簡決策樹實現對專利價值度的評估，并與決策樹模型進行了結果比較。

2.1 決策樹算法原理

決策樹是一種樹形分類器，算法分為建樹和剪枝兩部分。在建樹過程中，首先在訓練數據集上通過選擇信息增益最大的屬性創建樹結點，再根據結點中屬性不斷建立分支，直到分支結點里的數據都是同一類標簽，則該分支結點為樹的葉節點。然后通過剪枝優化樹的分類性能，消除噪聲干擾，最后得到決策樹模型，從而對新的樣本進行分類[14]。

2.2 隨機森林算法原理

隨機森林算法是2001年由Breiman[15]提出的一種基于決策樹的集成方法。隨機森林算法利用Bootstrap方法從訓練數據集中有放回地隨機抽取n個樣本，并構建n個決策樹組成隨機森林模型，再按多棵樹分類器投票決定最終分類結果。

2.3 基于DBSCAN聚類[16]的改進隨機森林算法原理

由于隨機森林是由若干個決策樹分類器集成的分類算法，所以隨機森林的性能取決于構成隨機森林中的每個決策樹的分類準確性以及各決策樹之間的多樣性。通過參考文獻[17]和文獻[18]，本文中的改進隨機森林模型從隨機森林中的單個決策樹的分類精度和決策樹的多樣性角度出發。首先從訓練數據集D上經過Bootstrap采樣的n個訓練子集Di(1≤i≤n)，分別在每個Di上訓練得到決策樹Ti，構成原始隨機森林F,再從F中選擇m個在測試數據集T1上分類精度較高的決策樹構成高精度子森林subF1，使用DBSCAN聚類方法[16]將subF1中的決策樹分為Q個類簇，選擇每個類簇Qi中分類精度最高的決策樹組成改進的隨機子森林subF,最后由subF中各決策樹在測試數據集T2上得到的分類結果經過多數投票法決定T2中每個樣本的最優分類。改進的隨機森林算法原理如圖2所示。

2.3.1 高精度子森林subF1的選擇方法

使用AUC(area under curve)來衡量決策樹的分類精度，AUC為受試者工作特征(receiver operating characteristic，ROC)曲線下的面積。AUC越高，說明該決策樹分類效果越好。ROC曲線是表示假正率(false positive rate，FPR)和真正率(true positive rate，TPR)的變化關系圖。根據定義可知AUC是用作二元分類的性能評估指標，而本文中的專利價值評估是一個多分類問題。為了引入AUC度量，需要采用以下的方法計算平均AUC作為每個決策樹的AUC，即

(6)

式(6)中：G為分類類別數；Ci表示第i類；C′i表示除第i類外其余的類作為一個類。

通過上述公式計算出原始隨機森林F的每個決策樹Ti(1≤i≤n)在測試數據集上的AUCi，然后按AUC從高到低將決策樹Ti排序，并選擇前m個Ti，則得到由m個決策樹組成的高精度子森林subF1。m的值由以下的方法來確定：

圖2 改進的隨機森林算法原理Fig.2 Improved random forest algorithm principle

(7)

(8)

(9)

式中：A為所有決策樹AUC的均值；σ為其標準差。先選擇F中AUC不小于A的決策樹組成的子森林F′，若F′中決策樹個數超過總F的2/3時，則F′就是要選取的高精度子森林subF1。否則，為了避免選取的子森林規模太小而無法體現隨機森林的多樣性的優勢，應降低精度閾值，選擇AUC不小于(A-σ)的決策樹構成高精度子森林subF1。

3.3.2 DBSCAN聚類選擇多樣性子森林

上一階段得到的高精度子森林subF1篩除了分類效果較差的決策樹，本階段則是根據之前在測試數據集上的預測結果將subF1進行聚類，選取屬于各個不同類簇的決策樹，降低森林中樹與樹之間的一致性，使改進后的模型具備更好的泛化性能。

為了衡量決策樹的分類多樣性，使用統計學上常用的Kappa統計量。設有兩個分類器分別為t1、t2，則t1和t2對同一樣本的分類一致性用Kappa統計量表示為Kt1，t2，其計算方法為

(10)

根據Kappa統計量的定義，式(10)中：Pr(a)表示兩個分類器分類一致的樣本數占所有樣本總數的比例；Pr(e)表示兩個分類器在偶然條件下的一致性。

(11)

(12)

式中：G為分類類別數；Cij表示在分類器t1中被標記為第i類而在分類器t2中被標記為第j類的樣本個數。

Kappa值的范圍為?-1，1」，越接近1說明這兩個分類器的一致性越高，等于0則說明兩個分類器的分類結果相似性與隨機情況下相同，而Kappa值小于0即相似性比隨機情況下的還要低，一般情況下Kappa值不會小于0。為了將subF1中相似性高的決策樹聚集為一個類簇，可以將Kappa值通過下面公式轉化為聚類方法中的距離度量。

Ldistance=0.5×(1-K)

(13)

則距離度量Ldistance趨向于0時，兩個分類器的一致性越高。

對于聚類方法的選擇，文獻[17]中通過多次實驗確定最佳聚類個數Q，并使用了最大最小距離算法進行聚類。現采用DBSCAN算法。DBSCAN是一種廣泛應用的基于密度的空間聚類算法，它將具有足夠密度的區域劃分為簇，并在具有噪聲的空間數據庫中發現任意形狀的簇，簇定義為密度相連的點的最大集合。DBSCAN聚類算法原理如圖3所示，圖中紅色的點代表核心點，當落在以某一點為中心，半徑為Eps的鄰域范圍內的所有樣本點數量不少于密度閾值MinPts時，這個中心點稱為核心點，其鄰域內的點為邊界點。不在任何一個核心點的鄰域范圍內的點被視為噪聲。圖中用綠色箭頭連起來的核心點組成了密度可達的樣本序列，在這些核心點的鄰域內所有邊界點都是密度可達的。這些密度可達的點構成一個簇。圖4展示了參數分別設置為Eps=1、MinPts=4和Eps=0.8、MinPts=4的笑臉數據集的DBSCAN聚類過程。

圖3 DBSCAN算法原理Fig.3 DBSCAN algorithm principle

圖4 笑臉數據集DBSCAN聚類過程Fig.4 DBSCAN clustering procedure of smiley face dataset

該算法能自動確定聚類的個數Q,而不需要再經過多次實驗，并且還能在聚類的同時發現噪聲。待聚類的高精度子森林subF1中不屬于任何一個類簇的樹則被視為噪聲。對高精度子森林subF進行DBSCAN聚類的算法流程如下。

(1)檢測subF1中尚未檢測的決策樹ti, 若ti未被處理(歸入某個簇或歸為噪聲), 則檢查以ti為圓心，以Eps為半徑的圓區域，即ti的Eps鄰域。如果其中包含的其他決策樹的數量≥密度閾值MinPts, 則建立新的類簇Cj，將其Eps鄰域中所有其他決策樹加入Cj。

(2)檢查類簇Cj中所有還未被處理的決策樹的Eps鄰域, 若其中包含的決策樹的數量≥MinPts, 則將其鄰域中尚未歸入任何一個類簇的決策樹加入Cj。

(3)重復步驟(2)直到沒有新的決策樹加入Cj。

(4)重復步驟(1)、(2)、(3)，直到處理完subF1中所有的決策樹，得到被劃分為Q個類簇的子森林subF′1。

然后從subF′1中的每個類簇中選擇分類精度最高的決策樹構成最終的改進隨機森林模型subF，其包含Q個高精度決策樹并且樹與樹之間的相關性較低。

3 實驗及結果分析

實驗使用的數據來源于合享創新專業專利數據庫網站，基于第1節選擇的價值指標，在該網站下載了一批包含19個字段的專利數據集，其中18個價值評估指標作為特征，價值度作為分類標簽。該數據集是2015—2018年已公開的專利中隨機抽取的4 616條專利信息數據。在本數據集中價值度為1～10級，由于樣本的不均衡，所以實驗將第1～3級劃分為類別1，4～10級每一級對應一個類別，分別為類別2～8，因此一共有8個分類標簽。實驗平臺為macOS Mojave10.14.3，內存為8 GB，CPU為雙核2.3 GHz，軟件環境為Python3.6。

經過第1章的特征選擇得到最佳特征子集，用于實驗的數據集樣本包含8個特征和價值度分類標簽。本實驗將決策樹算法、隨機森林算法和改進的隨機森林算法3種方法分別在選取了最佳特征子集的數據集上進行訓練，并將3個訓練模型實驗的測試結果進行對比。隨機抽取總體數據樣本的80%作為訓練數據集D，20%作為測試數據集T。由于實驗是多分類實驗，使用測試集上所有分類結果的準確率作為該模型的評價依據。

實驗采用10折交叉驗證得到模型的準確率并將其取均值的方式獲取評估結果。將改進的隨機森林算法(RF_improved)與傳統隨機森林(RF)算法進行比較，首先使用傳統的隨機森林算法生成包含n_estimators個決策樹的RF模型，不斷調整n_estimators的取值生成其對應的RF模型，經過測試集T得到不同n_estimators的RF模型的準確率，然后將這些RF模型根據上述的改進算法選擇高精度多樣性子森林得到RF_improved模型，再通過測試集T計算RF_improved模型的分類精度。

將n_estimators分別取值為40、50、60、70、80、90、100、110、120進行實驗，并繪制兩個模型的分類精度曲線，如圖5所示。可以直觀地看出，改進后的隨機森林比傳統隨機森林分類效果更好，模型準確率的提升范圍在1.4%～2.2%。一開始隨著n_estimators的增大，兩個隨機森林模型的分類精度逐漸增高，體現了集成算法的優勢，在n_estimators=90時RF模型的分類精度最高，當n_estimators繼續增大時，RF模型的精度呈現下降的趨勢。這是因為傳統的隨機森林算法隨機化地生成大量決策樹勢必導致“良莠不齊”的情況出現，從而降低集成后的準確率。而此時改進的隨機森林算法發揮其刪減掉效果較差且不具備代表性的決策樹的優勢，所以RF_improved模型的分類精度有所升高，最后趨于穩定。

圖5 RF與RF_improved的分類準確率比較Fig.5 Comparison of classification accuracy between RF and RF_improved

當n_estimators分別取90和110時，改進前后的隨機森林模型得到最佳的分類效果，然后與決策樹模型在相同數據集下的分類準確率比較，如表3所示。

表3 3種模型的平均準確率比較Table 3 Comparison of the average accuracy of three models

實驗結果表明，隨機森林模型能有效地預測專利的價值度，并且表現出比決策樹模型更好的效果。同時，通過將改進的隨機森林模型與傳統的隨機森林模型的分類結果比較得到，本文所提出的改進方法得到了高精度且多樣性豐富的子森林，提高了隨機森林模型的平均準確率，但是總體上來說，準確率仍有待提升。在本實驗的價值評估指標的選擇中，可能存在評估指標不夠科學和全面的問題，導致無法真實地反映專利價值度的特征。

4 結論

機器學習和大數據技術當前發展日益成熟，被各研究領域廣泛應用。對于專利價值的評估問題，也逐漸從傳統的評估方法發展為基于機器學習等數據挖掘算法的專利價值評估。首先通過選擇能有效反映專利價值度的評估指標，使用隨機森林算法對選取的指標基于Gini指數進行特征選擇得到一個最佳特征子集，同時基于DBSCAN聚類選擇高精度且一致性低的決策樹子森林改進傳統隨機森林算法，然后使用改進前后的兩種隨機森林模型對專利數據樣本進行訓練和測試，證明了改進模型對精度的提高，并將這兩種隨機森林模型與決策樹模型進行比較。實驗結果表明，改進的隨機森林模型在專利價值評估中具有較好的作用，總體上比較有效地反映了專利的價值度。然而，對于專利價值的評估準確率仍有待提高，這是由于在選取評估指標過程中，還應結合各方面數據信息以及專家打分為專利價值評估提供更加全面準確的特征信息，希望未來能在評估指標挖掘方面進行深入探究。