[發明專利]一種新的數據空間離散化算法

在審

• 申請號: 202110176659.2
• 申請日: 2021-02-07
• 公開（公告）號: CN113190794A
• 公開（公告）日: 2021-07-30
• 發明（設計）人: 趙銀軍;李家旭;丁愛中;鄧齊玉;童凱;莫莉萍
• 申請（專利權）人: 廣西中青態環境科技有限公司;南寧師范大學
• 主分類號: G06F17/18
• 分類號: G06F17/18;G06Q10/06
• 代理公司: 重慶為信知識產權代理事務所(普通合伙) 50216
• 代理人: 李曉賢

1.一種新的數據空間離散化算法，其特征在于，包括以下步驟：

(Ⅰ)初始化候選斷點：輸入已經處理好的空間數據，指定需要離散化的連續屬性，對連續屬性的所有取值進行數據預處理，得到候選斷點集合；

(Ⅱ)確定最優候選斷點集：包括候選區間分割和搜索莫蘭指數最優斷點兩個步驟，根據疊置斷點法，用候選斷點將連續屬性取值集合分割為左右兩個區間，分別計算分割后左右兩個區間的平均值，再用左右區間各自的平均值代替各自區間的所有屬性的取值，則空間數據的連續屬性取值集合只包含左右區間的兩個平均值，然后計算集合的全局莫蘭指數，取莫蘭指數最大值對應的分割點作為最優離散化斷點，再將分割后的左右區間重復上述過程直至滿足疊置斷點法的終止條件，最后收集所有最優候選斷點，得到最優候選斷點集合，具體步驟如下：

(1)如果CdCuts中的候選斷點個數i大于1則開始遍歷CdCuts，取出候選斷點p_i，判斷DivTree中根節點值ROOT是否為空，如果為空，則需要分割的區間inval＝[L,R]，如果不為空，則根據公式1.1確定inval的端點，

(2)計算空間數據圖層S中的地理要素屬性X和Y，其中X左側區間inval_L的莫蘭指數為Glmi(inval_L,X)，Y左側區間inval_L的莫蘭指數為Glmi(inval_L,Y)，根據公式1.2計算左側區間inval_L的地理要素屬性X與Y的差分值dfMi_L，同理，X右側區間inval_R的莫蘭指數為Glmi(inval_R,X)，Y右側區間inval_R的莫蘭指數為Glmi(inval_R,Y)，根據公式1.3計算右側區間inval_R的地理要素屬性X與Y的差分值dfMi_R，

dfMi_L＝Glmi(inval_L,X)-Glmi(inval_L,Y) (1.2)，

dfMi_R＝Glmi(inval_R,X)-Glmi(inval_R,Y) (1.3)；

(3)根據公式1.4計算inval_L和inval_R之間的最小差分值mdfMi，對于從CdCuts中遍歷出的任意p_i點都對應一個最小差分值mdfMi，

mdfMi＝min(dfMi_L,dfMi_R) (1.4)；

(4)創建一個數組plist，遍歷數組CdCuts的過程中，取出第一個點p₁對應的mdfMi作為最小的mdfMi_min，將點p₁存入數組plist，記點p₁分割的區間長度為l'，后面遍歷出的p_i點對應的mdfMi如果小于mdfMi_min，則令mdfMi_min＝mdfMi，將p_i點存入數組plist，數組plist中的最后一個元素為最優分割點O_i，第一個至倒數第二個元素均為次最優分割點O_i'；

(5)如果DivTree的ROOT為空，則直接創建CurrNode得到O_i和對應的l'，然后寫入CurrNode并壓入DivTree中，此時DivTree的CurrNode根節點值ROOT＝O_i，如果DivTree的ROOT不為空，則先檢索以下兩個條件：第一、DivTree中是否已經存在O_i，第二、O_i是否為CdCuts中的最后一個候選斷點，如果兩個條件同時不成立則創建CurrNode，將得到的O_i和對應的l'寫入CurrNode中，根據O_i數值與DivTree中已有結點的root的大小進行比較，然后在相應的位置插入CurrNode，令邊界點B＝O_i，如果兩個判斷條件只成立其中一個，則表示當前O_i點不符合要求，需要查找次最優分割點O'_i，具體過程為：在數組plist中刪除掉最后一個元素plist[-1]，原來的倒數第二個元素plist[-2]則為當前的次最優分割點O'_i，然后再創建CurrNode，并將得到O'_i和對應的l'寫入CurrNode并壓入DivTree中，一直到能夠壓入DivTree為止，則表示找到了符合條件的O'_i，此時令邊界點B＝O'_i，如果O'_i仍然無法壓入DivTree中，則返回重新查找次最優分割點O'_i，如果一直執行到數組plist中的元素為空，仍然沒有找到符合條件的O'_i，則說明當前的區間inval沒有最優分割點，即區間inval無法再繼續分割，此時將表示區間inval無法繼續分割的標志NondivFlag賦值為True；

(6)對于區間inval，首先判斷該區間是否同時滿足可分割的三個條件：第一個條件Glmi(inval,X)小于t、第二個條件NondivFlag＝False、第三個條件區間inval內的地理要素大于30個，如果不滿足則執行步驟(7)，如果同時滿足上述三個條件則繼續對區間inval進行劃分，通過公式1.5計算CdCuts_L，令CdCuts＝CdCuts_L，再進入區間inval的一次遞歸過程，一次遞歸的層數lev初始值為0，遞歸開始：執行步驟(1)-步驟(6)，一次遞歸完成后繼續判斷區間inval是否同時滿足上述可分割的三個條件，如果不滿足則執行步驟(7)，如果同時滿足則lev＝lev+1進入二次遞歸，遞歸開始：執行步驟(1)-步驟(6)，二次遞歸結束后，確定最優候選斷點集的步驟已全部完成；

待步驟(7)執行完成后通過公式1.1確定區間inval，通過公式1.6計算CdCuts_R，令CdCuts＝CdCuts_R，進入區間inval的遞歸過程，當前遞歸的層數為lev，遞歸開始：執行步驟(1)-步驟(6)，遞歸完成后繼續判斷區間inval是否同時滿足上述可分割的三個條件，如果同時滿足則lev＝lev+1，進入區間inval的遞歸過程，遞歸開始：執行步驟(1)-步驟(6)，遞歸結束后確定最優候選斷點集的步驟已全部完成；

如果區間inval不滿足上述可分割的三個條件，則第lev層inval的遞歸到達出口，然后執行步驟(8)，待步驟(8)完成后如果此時lev＝0則確定最優候選斷點集的步驟已全部完成，否則lev＝lev-1，當前的遞歸層數又回到lev，然后根據公式1.1確定區間inval，如果CdCuts＝CdCuts_L則執行步驟(9)，待步驟(9)完成后進入區間inval的遞歸過程，遞歸開始：執行步驟(1)-步驟(6)，遞歸結束后，確定最優候選斷點集的步驟已全部完成；

如果CdCuts＝CdCuts_R則執行步驟(10)，待步驟(10)完成后當前的遞歸層數還是回到lev，則lev＝lev-1，直到區間inval的遞歸過程回到lev＝0，確定最優候選斷點集的步驟已全部完成，

(7)對于inval，如果CurrNode的root等于max(CdCuts_L)并且CurrNode的parentNode不為空，則令L等于CurrNode的root，令CurrNode指向CurrNode的parentNode，再令B等于CurrNode的root，如果CurrNode的root等于max(CdCuts_R)并且CurrNode的parentNode不為空，令L等于CurrNode的root，令CurrNode指向CurrNode的parentNode，再令B等于CurrNode的root，如果CurrNode的parentNode為空，則說明只產生了一個O_i并且inval的Glmi(inval,X)大于t，inval無法進行繼續分割；

(8)對于inval，如果CurrNode的root等于max(CdCuts_L)并且CurrNode的parentNode不為空，令CurrNode指向CurrNode的parentNode，令L等于CurrNode的root，再令B等于CurrNode的parentNode包含的root，如果CurrNode的root等于max(CdCuts_R)并且CurrNode的parentNode不為空，令L等于CurrNode的root，令CurrNode指向CurrNode的parentNode，再令B等于CurrNode的root，如果CurrNode的parentNode為空，則說明只產生了一個O_i并且inval的Glmi(inval,X)大于t，區間inval無法再繼續分割；

(9)對于inval，同時滿足以下兩個條件NondivFlag＝True和CurrNode的root＝max(CdCuts_L)，令L等于CurrNode的root，如果CurrNode的parentNode不為空，則令CurrNode指向CurrNode的parentNode，再令B等于CurrNode的root，NondivFlag＝False，如果CurrNode的parentNode為空，令B等于CurrNode的root，NondivFlag＝False，如果NondivFlag＝False并且CurrNode的parentNode為空，則令L和B都等于CurrNode的root，如果NondivFlag＝False并且CurrNode的parentNode不為空，判斷inval_L是否可分，如果可分，令L等于CurrNode的root，CurrNode指向CurrNode的parentNode，再令B等于CurrNode的root，如果不可分，CurrNode指向CurrNode的parentNode，L等于CurrNode的root，B等于CurrNode的parentNode包含的root；

(10)對于inval，如果滿足NondivFlag＝True、CurrNode的parentNode不為空、CurrNode的root＝max(CdCuts_L)這三個條件，則令CurrNode指向CurrNode的parentNode，L等于CurrNode的root，再令B等于CurrNode的parentNode包含的root＝False和NondivFlag＝False，如果CurrNode的parentNode為空，則令NondivFlag＝False；

(Ⅲ)確定最優區間數：對于最優候選斷點集合，經增量組合最優斷點、區間數PD值序列匹配、滑動計算區間比值后可確定最優區間數，即根據每個斷點分割的區間長度進行降序排序，將集合中的第一個點作為起點，每次從起點開始增量截取斷點，直到從起點截取至最后一個斷點，得到與最優斷點集合的長度相同的斷點組合的集合，計算集合中每個斷點組合的因子探測值，按照斷點組合長度的降序順序構造與其對應的因子探測值的序列，計算因子探測值與區間長度的比值，由前向后查找，如果遇到后面比值小于前面比值的，則前面位置對應的組合長度值加一為最優區間數，對應的斷點組合為最優斷點集合；

(Ⅳ)連續屬性離散化：對于步驟(Ⅲ)得到的最優斷點集合，將指定的連續屬性按照斷點進行劃分并檢查區間是否正常，進而得到帶有離散屬性的空間數據。