[發(fā)明專利]大型系統(tǒng)進(jìn)化樹的加速方法及裝置

在審

• 申請?zhí)枺?/td>: 202211241923.7
• 申請日: 2022-10-11
• 公開（公告）號: CN115691656A
• 公開（公告）日: 2023-02-03
• 發(fā)明（設(shè)計）人: 孟珍;張波;鄭玲璐;陳艷;胡智龍;汪嘉葭
• 申請（專利權(quán)）人: 中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心
• 主分類號: G16B10/00
• 分類號: G16B10/00;G16B40/30
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理有限公司 11200
• 代理人: 陳艷

1.一種大型系統(tǒng)進(jìn)化樹的加速方法，其特征在于，所述方法包括：

獲取系統(tǒng)進(jìn)化樹中所有節(jié)點的屬性；其中，所述屬性包括：橫向坐標(biāo)、縱向坐標(biāo)、父節(jié)點、子節(jié)點、可見狀態(tài)和半徑，所述可見狀態(tài)的初始值為當(dāng)前節(jié)點可見；

基于所述橫向坐標(biāo)和所述縱向坐標(biāo)，對所述系統(tǒng)進(jìn)化樹的葉子節(jié)點進(jìn)行聚類，以獲取離群點和節(jié)點簇；

在一個節(jié)點的子孫葉節(jié)點全部屬于一個所述節(jié)點簇，且所述子孫葉節(jié)點的數(shù)量不小于一數(shù)量閾值的情況下，將該節(jié)點作為一新的葉節(jié)點，且將所述子孫葉節(jié)點的所述可見狀態(tài)設(shè)置為當(dāng)前節(jié)點不可見，以得到新的系統(tǒng)進(jìn)化樹；其中，所述新的葉節(jié)點的半徑基于所述子孫葉節(jié)點的數(shù)量得到；

針對所述新的系統(tǒng)進(jìn)化樹，通過判斷每一葉子分支是否因被其它節(jié)點覆蓋而導(dǎo)致不可見，獲取該葉子分支中各節(jié)點的可見狀態(tài)；

基于每一葉子分支中各節(jié)點的可見狀態(tài)，生成所述系統(tǒng)進(jìn)化樹的加速結(jié)果。

2.如權(quán)利要求1所述的方法，其特征在于，所述獲取系統(tǒng)進(jìn)化樹中所有節(jié)點的屬性，包括：

讀取系統(tǒng)進(jìn)化樹的Newick格式文件，并轉(zhuǎn)換為JSON結(jié)構(gòu)；

基于所述JSON結(jié)構(gòu)初始化系統(tǒng)進(jìn)化樹，并從所述系統(tǒng)進(jìn)化樹的根節(jié)點開始，遍歷所有節(jié)點，記錄每個節(jié)點對應(yīng)的父節(jié)點；

設(shè)定橫向縮放倍率SCALE_X、縱向縮放倍率SCALE_Y；

設(shè)置葉節(jié)點位置為(X，Y)＝(TOTAL_DISTANCE*SCALE_X，COUNT*SCALE_Y-BIAS_Y)；其中，TOTAL_DISTANCE表示當(dāng)前節(jié)點到根節(jié)點之間所有路徑的路徑長度之和，COUNT為當(dāng)前遍歷的葉節(jié)點的數(shù)量，BIAS_Y為Y軸方向上的偏移；

從葉節(jié)點回溯遍歷父節(jié)點直到根節(jié)點，并且當(dāng)前遍歷的節(jié)點的位置為(X，Y)＝(TOTAL_DISTANCE*SCALE_X，(MIN_SON_Y+MAX_SON_Y)/2)；其中，MIN_SON_Y和MAX_SON_Y分別為子節(jié)點在Y方向的最小坐標(biāo)值和最大坐標(biāo)值；

層次遍歷所有節(jié)點和分支，設(shè)置所有節(jié)點為可見狀態(tài)。

3.如權(quán)利要求1所述的方法，其特征在于，所述基于所述橫向坐標(biāo)和所述縱向坐標(biāo)，對所述系統(tǒng)進(jìn)化樹的葉子節(jié)點進(jìn)行聚類，以獲取離群點和節(jié)點簇，包括：

設(shè)置第一超參數(shù)MIN_SAMPLES、第二超參數(shù)EPS，并設(shè)置輸入為所述系統(tǒng)進(jìn)化樹中所有的葉節(jié)點；其中，所述第一超參數(shù)MIN_SAMPLES為一個簇中最少的樣本數(shù)量，所述第二超參數(shù)EPS為掃描半徑；

利用所述第一超參數(shù)MIN_SAMPLES和第二超參數(shù)EPS，對所有的葉節(jié)點執(zhí)行DBSCAN算法，得到若干節(jié)點簇和離群點；其中每一節(jié)點簇中包含若干個葉節(jié)點。

4.如權(quán)利要求1所述的方法，其特征在于，所述在一個節(jié)點的子孫葉節(jié)點全部屬于一個所述節(jié)點簇，且所述子孫葉節(jié)點的數(shù)量不小于一數(shù)量閾值的情況下，將該節(jié)點作為一新的葉節(jié)點，且將所述子孫葉節(jié)點的所述可見狀態(tài)設(shè)置為當(dāng)前節(jié)點不可見，以得到新的系統(tǒng)進(jìn)化樹，包括：

設(shè)定數(shù)量閾值MIN_NODES，初始化列表TEMP_LIST為空；

對于每個類中的節(jié)點，從根節(jié)點開始層次遍歷，如果一個分支的子孫葉節(jié)點全部屬于一個節(jié)點簇，且這些子孫葉節(jié)點的數(shù)量大于或等于MIN_NODES個點，則設(shè)置該節(jié)點為的可見狀態(tài)修改為臨時狀態(tài)

對于每個節(jié)點簇中的節(jié)點，從根節(jié)點開始層次遍歷；

如果一個節(jié)點的子孫葉節(jié)點全部屬于一個所述節(jié)點簇，且所述子孫葉節(jié)點的數(shù)量大于或等于所述數(shù)量閾值MIN_NODES，則將所述節(jié)點的可見狀態(tài)修改為臨時狀態(tài)之后，加入到所述列表TEMP_LIST；

遍歷所述列表TEMP_LIST，將節(jié)點的可見狀態(tài)修改為當(dāng)前節(jié)點可見，且基于節(jié)點的子孫葉節(jié)點的數(shù)量設(shè)置節(jié)點的半徑之后，將該節(jié)點作為新的葉節(jié)點，以得到新的系統(tǒng)進(jìn)化樹。