聚類是一種重要的數據挖掘技術。它可以根據相似性將對象劃分為不同的簇，每個簇對應一個特定的類別。聚類有廣泛的應用，如大氣預測、圖像處理和生物信息學[1]。最近的調查也強調了其在各個領域的持續相關性[2]，包括基于密度的方法的進步[3]和多視圖設置[4]。

隨著聚類技術的發展，人們越來越關注改進聚類算法以處理專門的數據集。例如，處理缺失值的聚類仍然是一個活躍的研究領域[5]，最近的研究探索了矩陣補全策略[6]，全面的綜述指出了存在的挑戰[7]。不完整的數據集（即包含缺失值的數據集）是一類專門的數據，其中一些對象在某些維度上包含缺失的條目。這類數據集在現實世界場景中非常普遍。目前，一種常見的策略是先對缺失值進行插補，然后再進行標準聚類[8]。其他方法包括直接從不完整數據中學習表示[9]或通過輔助約束來提高魯棒性[10]。然而，插補和聚類過程通常需要輸入參數，導致可調整的設置過多。過多的輸入參數不可避免地增加了獲得準確聚類結果的難度，這一點在關于參數敏感性和可重復性的研究中得到了強調[11]和[12]。圖1展示了在100組參數值下，兩種現有算法獲得高準確性和低準確性的概率，其中0.5被用作區分高準確性和低準確性的閾值。結果表明，這些算法只有很小的概率能夠獲得高準確性。換句話說，大多數參數配置都無法產生良好的性能。顯然，消除用于聚類不完整數據集的輸入參數是一個有意義的研究方向。

近年來，一些研究人員探索使用決策圖來替代輸入參數[15]。這個想法已經被擴展用于加速圖構建，同時保持可解釋性[16]。這些方法利用決策圖來可視化隱含的數據集結構，并幫助用戶獲得有效的結果——要么不需要參數（如DPC [15]），要么只需要很少的參數（如TGP [17]）。例如，DPC使用密度度量ρ和最小距離度量δ作為坐標來生成決策圖。從這個圖中，用戶可以識別出同時具有高ρ和δ的簇中心，從而避免了K-means [18]所需的預先定義簇數k的需求。然而，現有決策圖中的度量依賴于所有對象之間的等效維度，這使得它們不適合包含缺失值的數據集。例如，DPC需要計算對象之間的歐幾里得距離來確定δ。由于歐幾里得距離依賴于完整的坐標信息，當任何維度上的值缺失時，就無法可靠地計算。因此，將決策圖適應于包含缺失值的聚類任務仍然是一個重大挑戰。

在本文中，我們提出了一種名為SDC（單維聚類）的新聚類算法，用于將決策圖適應于不完整數據集的聚類，使用戶無需參數即可獲得有效的聚類結果。SDC的總體框架如圖2所示，它包括三個主要階段：（1）將原始數據集分割成單維非缺失子集，（2）通過基于密度的決策圖對每個子集進行無參數聚類，并通過受重力啟發的邊界收縮來增強簇結構，（3）使用分區交集融合部分聚類結果以生成最終聚類。

本工作的貢獻如下：

•

我們提出了第一個用于處理包含缺失值的聚類任務的無參數算法。（第3節）

•

我們為SDC設計了一種單維策略，以消除插補過程并使決策圖適應于包含缺失值的數據集。該策略涉及將不完整數據集分割成幾個“非缺失”的單維數據集，然后使用密度分布決策圖為每個“非缺失”的單維數據集獲得聚類結果。最后，我們使用提出的“分區交集”方法組合這些聚類結果以獲得最終結果。（第3.2節）

•

我們引入了“重力”來收縮簇的邊界，使單維數據集盡可能多地繼承原始數據集的信息，從而提高單維策略的有效性。（第3.3節）

•

我們設計了一種輕量級的批量密度計算方法來加速決策圖的生成和重力計算，顯著降低了SDC的時間復雜度。（第3.4節）

•

廣泛的實驗表明，在三個評估指標上，無參數的SDC的性能至少比具有多個參數的基線算法高出13.7%（NMI）、23.8%（ARI）和8.1%（純度）。此外，無論缺失數據率如何增加，SDC相對于基線算法的優勢都保持一致。（第4節）