[發(fā)明專利]一種采用C4.5決策樹算法的電纜路徑尋優(yōu)方法

有效

• 申請?zhí)枺?/td>: 202110389163.3
• 申請日: 2021-04-12
• 公開（公告）號: CN113268837B
• 公開（公告）日: 2022-06-14
• 發(fā)明（設(shè)計）人: 徐展鵬;王運罡;陳福新
• 申請（專利權(quán)）人: 中國電建集團(tuán)華東勘測設(shè)計研究院有限公司
• 主分類號: G06F30/18
• 分類號: G06F30/18;G06F30/27;G06K9/62;G06Q10/04;G06Q50/06;G06F113/04
• 代理公司: 浙江杭州金通專利事務(wù)所有限公司 33100
• 代理人: 劉曉春

1.一種采用C4.5決策樹算法的電纜路徑尋優(yōu)方法，其特征在于：包括以下步驟：

S1：將實際的橋架布置圖進(jìn)行有向網(wǎng)絡(luò)建模；

S2：采用最短路徑算法，對任意兩點間的最短路徑和最短路徑的長度進(jìn)行計算，路徑的表現(xiàn)形式為具有一個起點和一個終點，起點和終點之間具有多個頂點，根據(jù)這個路徑，起點到終點的邊的長度和最短，即電纜敷設(shè)的長度最短；

S3：利用決策樹理論，采用C4.5決策樹算法，對S2中得到的最短路徑，引入影響路徑選擇的多個因素，對最短路徑進(jìn)行進(jìn)一步處理，得到最優(yōu)路徑；

所述決策樹算法對最短路徑進(jìn)行進(jìn)一步處理的具體步驟如下：

S3-1：選擇決定電纜走向的多個因素，并將這些需要考慮的因素編號為因素A，因素B，因素C，因素D...，因素N；

S3-2：針對需考慮的n個因素的每種可能情況建立不同的樣本組合，樣本個數(shù)為X，并在建立的樣本組合下，對每一個當(dāng)前所在頂點，決定是否按步驟S2中確定的最短路徑作為接下來的電纜路徑，以符號M表示該選擇，作為目標(biāo)變量，其取值為“是”和“否”；

S3-3：在樣本組合中，設(shè)目標(biāo)變量M的結(jié)果，選“是”的有X₁組，選“否”的有X₂組，則樣本總數(shù)為X＝X₁+X₂組，則計算M的經(jīng)驗熵為：

H(M)＝-P₁*log(P₁)-P₂*log(P₂)

其中：P₁＝X₁/X，P2＝X₂/X

S3-4：在樣本組合中，設(shè)因素A有j種不同的具體情況，編號為A₁，A₂，A₃，...，A_j，各情況出現(xiàn)的個數(shù)為Y₁，Y₂，Y₃，...，Y_j，Y₁+Y₂+Y₃+...+Y_j＝X；假設(shè)在第j個情況中，步驟S3-2中的目標(biāo)變量M選“是”的為Y_j1組，選“否”的為Y_j2組，Y_j1+Y_j2＝Y(jié)_j，則計算M在因素A下的經(jīng)驗條件熵為：

H(M/A)＝Y(jié)₁/X*H(A₁)+Y₂/X*H(A₂)+Y₃/X*H(A₃)+....+Y_j/X*H(A_j)

上式中，第j個情況中H(A_j)計算如下：

H(A_j)＝-P_j1*log(P_j1)-P_j2*log(P_j2)

其中：P_j1＝Y(jié)_j1/Y_j，P_j2＝Y(jié)_j2/Y_j

S3-5：將步驟S3-3和S3-4中得到的H(M)和H(M/A)，計算因素A的信息增益g(M，A)：

g(M，A)＝H(M)-H(M/A)

利用步驟S3-3和S3-4中的參數(shù)：Y₁，Y₂，Y₃...Y_j可得因素A的經(jīng)驗熵為：

H(A)＝-Y₁/X*log(Y₁/X)-Y₂/X*log(Y₂/X)......-Y_j/X*log(Y_j/X)

S3-6：利用步驟S3-5中的結(jié)果，計算采用決策樹C4.5算法下的因素A的信息增益率為：

gr(M，因素A)＝g(M，A)/H(A)

同理，重復(fù)步驟S3-3至S3-6，可得gr(M，因素B)，gr(M，因素C)，gr(M，因素D)....gr(M，因素N)；

S3-7：比較gr(M，因素A)、gr(M，因素B)、gr(M，因素C)、gr(M，因素D)....gr(M，因素N)之間的大小，最大的因素作為決策樹根節(jié)點，次小的作為下一個分枝節(jié)點，依次排序，最小的作為最末的分枝節(jié)點。