類不平衡問題的距離映射重疊復雜度度量
中文題目：類不平衡問題的距離映射重疊復雜度度量
論文題目：Distance Mapping Overlap Complexity Metric for Class-Imbalance Problems
錄用期刊/會議：【Applied Soft Computing】 (中科院大類1區，JCR Q1 Top)
原文DOI：https://doi.org/10.1016/j.asoc.2024.111904
原文鏈接：
https://www.sciencedirect.com/science/article/pii/S1568494624006781
錄用/見刊時間：2024.06.21
封面圖片：
作者列表：
1） 代琪 中國石油大學（北京）人工智能學院 控制科學與工程 博20
2） 劉建偉 中國石油大學（北京）人工智能學院 自動化系 教師
3） 施永輝 華北理工大學 理學院
摘要:
類不平衡問題的數據復雜度是數據挖掘領域的熱點。經典的數據復雜性度量方法使用kNN等技術，計算每個樣本的最近鄰。但是，基于kNN的方法獲取所有樣本的最近鄰是一個NP難問題，不利于大規模數據復雜度計算。為了解決這個問題，分別從全局和局部兩個角度提出四種距離映射復雜度度量方法，將這類復雜度稱為距離映射重疊指數(DMOI)。首先，使用馬氏距離或標準化歐氏距離計算樣本到數據集中心點的距離，并按照每個樣本的距離大小排序。然后，根據有序標簽向量，遍歷搜索每一類的映射割點數。最后，根據不同類的映射割點數，計算數據集的DMOI。在50個類不平衡數據集上的實驗表明，提出的方法優于最新的針對類不平衡問題的復雜度度量方法。雖然對于基于規則或樹的分類器，DMOI與ONB相比，仍然存在差距，但是，使用皮爾遜相關系數表明，DMOI能夠有效地近似ONB，且它們之間存在強正相關性。
背景與動機:
數據的復雜性度量方法致力于評估訓練數據集復雜程度。類重疊問題是影響分類器的重要數據問題之一。目前的研究表明，當數據集中類重疊和類不平衡問題同時存在時，分類器的性能將會受到嚴重的影響。對于數據集的重疊程度的度量方法并未形成統一的標準度量方法。
特征重疊度度量方法主要是衡量個體特征之間的重疊程度。在使用這類重疊度度量方法之前，我們默認特征之間是不存在相關性的。然而，這樣的情況在實際應用中并不多見。結構重疊度量方法主要是搜索數據集中的結構特征估計數據集的類重疊程度。然而，傳統的結構重疊度度量方法主要是通過暴力搜索的方式，遍歷整個數據集。當面臨大規模數據集時，暴力搜索并不可取。通常我們認為樣本之間的相似性或距離越小，則樣本之間越容易出現類重疊問題。
在重疊度度量方法中，通過使用距離函數映射的方式，搜索數據集中存在的重疊問題。在距離映射向量上，如果不同類的樣本交織在一起，則表明它們更有可能位于相同的區域中。因此，首次使用距離映射的方式，提出一種估計數據集的全局類重疊復雜度的方法。通過移除數據集的某一個特征，從理論上證明了數據集的特征子空間中，仍然存在潛在的重疊問題。為了避免忽略特征之間的相關性，我們進一步提出一種從局部特征子空間的角度估計數據集的類重疊程度的方法。
設計與實現:
提出的距離映射重疊復雜度度量（DMOI）的示意圖如下所示。
主要內容:
在提出的DMOI方法中，主要分為三個階段：距離映射與排序、映射割點數計算和重疊指數計算。注意，MDOI和SEDMOI兩種方法除了距離度量方法存在差異之外，其具有相同的計算過程。
在第一階段中，計算數據集中的所有樣本的距離值，并獲取整個數據集的有序距離向量。
第二階段，根據有序距離向量中樣本的原始索引值，記錄有序距離向量中樣本的標簽信息。根據標簽索引與有序距離向量對應，獲得樣本的有序標簽向量。然后，根據有序標簽向量計算數據集中每個類的樣本的映射割點數。
第三階段，分別提出全局距離映射重疊指數(DMOI-G)和局部距離映射重疊指數(DMOI-L)。
實驗結果及分析:
在50個不平衡數據集上進行對比實驗，并計算分類結果與復雜度度量方法之間的皮爾遜相關系數，實驗結果如下所示。
不同評估度量與復雜度度量方法之間的皮爾遜相關系數：
(a)G-mean (b)Kappa
(c)AUC (d)MCC
圖1 不同評估度量與復雜度度量之間的皮爾遜相關系數
復雜度之間的相關性如下所示：
表1 復雜度度量之間的相似性
結論:
DMOI是一種快速的數據重疊復雜度度量方法，在該方法中，根據不同的距離函數，提出兩種復雜度度量方法。為了考慮數據集中樣本間的相關性，使用局部多粒度子空間思想，從全局和局部兩個視角，全面評估數據集的復雜程度。實驗結果表明，DMOI計算獲得的數據重疊程度與非規則歸納分類器的性能呈現強負相關性，而對于規則歸納分類器而言，ONBavg的近似能力更好。此外，ONBavg的計算復雜度較高，不適合在大規模數據集上使用。實驗結果表明，DMOI系列的方法能夠有效地近似ONBavg的計算結果，并且呈現出明顯的正相關性。
作者簡介:
代琪 自動化系2020級博士研究生。
通訊作者簡介:
劉建偉，教師，學者。