[發明專利]決策樹的生成方法和裝置

有效

• 申請號: 201210095978.1
• 申請日: 2012-04-01
• 公開（公告）號: CN102664787A
• 公開（公告）日: 2012-09-12
• 發明（設計）人: 胡晶;龔鈞
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 劉芳

1.一種決策樹的生成方法，其特征在于，包括：

根據規則集合生成編碼規則集合；所述規則集合包含多個規則，每個規則為包含0、1或者通配符的字符串，所述多個規則中任意兩個規則互不相等；所述編碼規則集合包括多個編碼規則，所述多個編碼規則中任意兩個編碼規則互不相等；所述多個編碼規則中每個編碼規則對應所述多個規則中的至少一個，所述多個規則中每個規則對應所述多個編碼規則中的一個；第一規則對應的編碼規則是根據第一函數對所述第一規則進行編碼得到的，所述第一規則是所述多個規則中的任意一個，所述第一函數用于將所述第一規則中的多個片段替換為多個編碼片段，進而得到第一編碼規則；所述第一規則由所述多個片段組成，每個片段包含至少一個字符；所述第一編碼規則由所述多個編碼片段組成，每個編碼片段為一個比特，所述多個片段與所述多個編碼片段一一對應，第一片段在所述第一規則中的位置與第一編碼片段在所述第一編碼規則中的位置一致；所述第一片段為所述多個片段中的任意一個片段；所述第一編碼片段為所述多個編碼片段中與所述第一片段對應的一個編碼片段；所述第一規則為所述第一函數的變量；所述第一編碼規則為所述第一函數的值；所述第一函數還用于根據所述第一片段計算所述第一編碼片段；在所述第一片段包含至少兩個字符的場景下，如果所述第一片段中通配符的個數大于或者等于N，則所述第一編碼片段為1，如果所述第一片段中通配符的個數小于N，則所述第一編碼片段為0，N為大于或者等于1并且小于或者等于M的整數，M為所述第一片段中的符號的個數；

生成第一帶權無向圖；所述第一帶權無向圖包括多個頂點，所述多個頂點與所述多個編碼規則一一對應，所述多個頂點中每個頂點對應一個子規則集合；第一頂點對應的子規則集合包含所述多個規則中所有與第一編碼規則對應的規則；所述第一頂點為所述第一帶權無向圖中的任意一個頂點；所述第一編碼規則為所述多個編碼規則中與所述第一頂點對應的編碼規則；

計算所述第一帶權無向圖中每個邊的權值；連接所述第一帶權無向圖中任意兩個頂點的邊為所述第一帶權無向圖的邊；第一邊的權值為以第二編碼規則和第三編碼規則為變量得到的第二函數的值；所述第一邊的兩個頂點分別對應所述第二編碼規則和所述第三編碼規則；所述第一邊為所述第一帶權無向圖中任意一個邊；所述第二函數用于對所述第二編碼規則與所述第三編碼規則執行按比特操作，計算按比特操作的結果中1的個數，按比特操作的結果中1的個數為所述第二函數的值；

如果第一帶權無向圖中權值最大的邊的權值大于第一閾值，所述第一閾值為大于等于0并且小于等于X-1的整數，X為所述第一編碼規則中比特的個數，則循環執行下述操作，直到最新生成的帶權無向圖中權值最大的邊的權值小于或者等于所述第一閾值：

根據已經生成的帶權無向圖中最后生成的帶權無向圖中權值最大的邊生成新的頂點，并根據所述新的頂點生成新的帶權無向圖；所述新的帶權無向圖包括所述新的頂點以及所述已經生成的帶權無向圖中最后生成的帶權無向圖中權值最大的邊的兩個頂點之外的所有的頂點；所述新的頂點對應的編碼規則為以所述已經生成的帶權無向圖中最后生成的帶權無向圖中權值最大的邊的兩個頂點分別對應的第四編碼規則和第五編碼規則為變量得到的第三函數的值；所述第三函數用于對所述第四編碼規則與所述第五編碼規則執行按比特與操作，按比特與操作的結果為所述第三函數的值；所述新的頂點對應的子規則集合包括所述已經生成的帶權無向圖中最后生成的帶權無向圖中權值最大的邊的兩個頂點分別對應的子規則集合中的所有規則；所述新的帶權無向圖中第二邊的權值為以第六編碼規則和第七編碼規則為變量得到的第四函數的值；所述第二邊的兩個頂點分別對應所述第六編碼規則和所述第七編碼規則；所述第二邊為所述新的帶權無向圖中任意一個邊；所述第四函數用于對所述第六編碼規則與所述第七編碼規則執行按比特操作，計算按比特操作的結果中1的個數，按比特操作的結果中1的個數為所述第四函數的值；

為所述最新生成的帶權無向圖中的每個頂點對應的子規則集合分別生成決策樹。

2.根據權利要求1所述的方法，其特征在于，所述按比特操作為與操作、或操作或者異或操作。

3.根據權利要求1或2所述的方法，其特征在于，在所述第一片段包含一個字符的場景下：

如果所述第一片段中的字符為1，則所述第一編碼片段為1；如果所述第一片段中的字符為0，則所述第一編碼片段為1；如果所述第一片段中的字符為通配符，則所述第一編碼片段為0。