一種新的基于特殊離群樣本優化的三維點云特征選擇算法

黃 祥，王紅星，顧 徐，孟 悅，王浩羽

一種新的基于特殊離群樣本優化的三維點云特征選擇算法

黃 祥，王紅星，顧 徐，孟 悅，王浩羽

(江蘇方天電力技術有限公司，江蘇 南京 211102)

隨著元宇宙、數字孿生、虛擬現實與增強現實等前沿技術的快速發展，三維點云在電力、建筑、先進制造等行業中得到廣泛應用，隨之而來的，如何降低三維點云數據冗余度、有效進行點云特征選擇，已在充分利用海量點云數據中扮演著關鍵角色。考慮到現有大多數三維點云特征選擇算法忽略了特定樣本在特征評估中的表現，提出一種新的有監督特征選擇算法，即基于特殊離群樣本優化的特征選擇算法(FSSO)。具體地，為獲得精準的特殊離群樣本(SOs)，FSSO優化均值中心并動態地界定類簇主體；計算SOs的類內相對偏離程度，通過減小類內相對偏離對特征進行打分，實現特征選擇過程。在3個公共的三維點云模型分類數據集上(ModelNet40，IntrA，ShapeNetCore)的實驗，以及4個高維人工特征數據集的驗證實驗結果表明，相較于其他特征選擇算法，FSSO可選擇出具有更強分類能力的特征子集，并提升分類準確率。

三維點云數據；有監督特征選擇；特殊離群樣本；類內相對偏離程度；分類

三維點云數據分析旨在從無序、非結構化的三維數據中解構出有用信息，是機器學習和計算機視覺領域中的熱點問題[1-2]。在諸如元宇宙、數字孿生、數字城市、虛擬現實等現實應用中，不同技術手段獲取的三維點云數據往往含有大量冗余特征，增加了點云數據分析和解讀的難度。特征選擇是從原始特征集中選出有識別力的特征子集，不僅可以有效地降低數據維度，還能提升對樣本的表征能力，是點云數據分析的有效手段。

根據是否依賴樣本的類別標簽，特征選擇算法可以分為：有監督、無監督和半監督特征選擇[3]。有監督特征選擇方法又可以進一步劃分成過濾式、包裹式和嵌入式。其中，過濾式模型不依賴任何分類器的表現，通過衡量訓練樣本的本質屬性對各特征進行評分，因此計算效率很高。包裹式模式基于隨機搜索序列，需要依據分類結果選擇得分最高的特征子集，故計算量較大。嵌入式模型將特征選擇問題與分類問題結合成單一目標規劃問題，雖然相較于包裹式模型，其計算成本大大降低，但仍不及過濾式模型。考慮到三維點云數據含有豐富的內在屬性，且數據規模較大，因此本文設計采用過濾式模型的特征選擇算法。

此外，大多數特征選擇算法將數據庫中的每個樣本均視為同等重要。但在實際應用中，某些特定樣本如離群(outliers)，往往隱含更有價值的信息待挖掘。如圖1所示，類別“aneurysm”(記為類別1)中有一些樣本，如1(k1)，表現為遠離所屬類內大多數樣本，卻進入到了類別“blood vessel”(記為類別2)中。顯而易見，從信息論的角度而言，相較于普通樣本2(k1)，形如1(k1)這類特殊離群樣本信息熵大，含有更多有價值的信息，理應在特征選擇過程中獲得更多關注。

通過上述分析可以發現，為實現基于特殊離群優化的特征選擇算法，需解決如何準確地獲取特殊離群樣本(specific outliers，SOs)和基于SOs的特性進行特征選擇2個問題。本文基于SOs表現，提出了一種有監督、濾波式的，基于特殊離群樣本優化的特征選擇(feature selection based on specific outliers，FSSO)算法。首先，相較于常見的類均值中心，FSSO采用去除部分離群樣本后，計算剩余樣本的均值作為優化的類中心；然后，利用該優化的均值中心，計算各類中的SOs；最后，計算SOs的類內相對偏離程度，并引進具有統計意義的樣本正態分布3原則作為可調節閾值，將超過閾值的大片特征視為冗余特征，從候選特征集中篩除。基于3個不同類型的大規模點云模型數據集(ModelNet40，IntrA，ShapeNetCore)，以及4個高維人工特征數據集的對比實驗發現，本文提出的FSSO算法相比其他特征選擇算法，能夠選出有較強識別力的特征子集、并提高了分類準確率。

圖1 三維點云分類數據集IntrA中的特殊離群樣本x1(k1)

1 相關工作

1.1 三維點云數據處理

隨著深度學習的發展，出現了許多使用深度神經網絡進行點云分類的工作。CHARLES等[4]提出的PointNet是將多層感知機用于點云分析，但其無法獲取完整局部特征信息及學習鄰接點間關系。QI等[5]隨后提出的PointNet++則解決了提取點云局部特征的問題。后續研究者繼續提出了更多的基于PointNet++框架的點云分類網絡，其中代表的工作有PointWeb[6]，So-Net[7]和Grid-GCN[8]等。

本文的工作是基于三維點云特征選擇，因此實驗時只使用點云分類網絡中的特征提取層的輸出作為后續特征選擇算法的輸入。點云特征提取有CurveNet[9]網絡，其連接點(曲線)序列首先通過點云進行引導式步行分組，然后再重新聚合以增強其逐點的特征。3DMedPT[10]是專門針對醫療點云的基于注意力的深度網絡模型，在查詢中增加上下文信息和總結本地響應，并在注意力模塊中捕獲本地上下文和全局內容特征交互。DGCNN[11]中的EdgeConv可以在保持點云排列不變性的情況下，提取點云局部形狀的特征。

然而，通過深度神經網絡從三維點云數據中提取的高維特征不可避免包含冗余特征，會直接影響分類的準確率。因此，對三維點云特征進行特征選擇以提升后續分類器的準確率是有實際價值的。

1.2 特征選擇算法

根據是否使用樣本的標簽信息，特征選擇算法可分為無監督、半監督、有監督3類。由于無標簽信息，即無監督方法通常使用數據的相似度、數據重建誤差等準則來評估特征的重要程度[12]。半監督方法的動機是使用少量的有標簽數據作為無監督方法的補充信息來提升方法的性能，其適用于小樣本問題。Fisher算法[13]是一種常見的特征選擇算法，可計算全體樣本的類內方差和類間偏離程度，將兩者的比值作為特征的得分。ReliefF[14]算法根據樣本以及鄰近樣本的相關性來評價特征。量化MI[15]算法利用量化的離散變量計算信息熵，是十分適用于大規模超高維的數據集。ILFS[16]是全部可能的特征子集的得分。TRC[17]優化了特征子集的得分準則。在半監督和無監督方法范疇下，RLSR[18]利用重新調節的回歸系數來對特征進行評估；Inf-FS[19]將特征視為全連接圖上的節點；LRLMR[20]將潛在的代表行學習嵌入進無監督特征選擇；DGUFS[21]基于L2,0范數設計了無映射特征選擇模型。然而，上述方法對特征的評估準則均基于數據庫中全部樣本的表現，而忽略了一些特殊樣本對特征評分的影響。為公平起見，本文重點關注有監督特征選擇算法。但為了更加全面地驗證本文提出的FSSO方法，半監督和無監督特征選擇算法也參與了實驗比較。

2 本文方法

圖2為FSSO算法的總體框架。

圖2 FSSO算法的總體框架

2.1 相關符號和定義

2.2 三維點云優化的類均值中心計算方法

一般特征選擇方法基于全部樣本計算類均值中心，由于特殊離群樣本不能準確地反映類簇的主要特性，使用其得到的均值中心往往會偏向于離群樣本聚集的區域，從而影響特征評分(圖3)。

圖3 常見的均值中心和優化的均值中心比較

本文三維點云類中心計算方法的關鍵步驟為：

(2) 基于剩余樣本計算各類均值中心。根據上述公式和定義，三維點云優化的類中心計算算法為：

算法1.三維點云的類中心計算算法。

輸入：各類樣本集(k),= 1, 2,···,；各類的樣本總數n；參數。

輸出：優化的類均值中心(k),=1, 2,···,。

for=1, 2,···,do

顯然，由于在計算三維點云類中心時排除了離群者，此優化類均值中心能更加準確地代表類別的特性，且不受離群樣本影響。

2.3 三維點云的離群樣本和冗余特征

2.4 基于特殊離群樣本優化的三維點云特征選擇

本文受文獻[22]采用方向性離群樣本的特征選擇算法的啟發，提出了基于上述特殊離群樣本優化的特征選擇算法，并將直接篩除冗余特征的優化操作用于計算各個特征的得分，從而更加精準地實現對特征的選擇。即將={1,2,···,}記為初始特征集合。

基于上述公式和分析，三維點云特征選擇算法為：

算法2:基于SOs的特征選擇算法。

輸入：參數；選擇的特征數。

輸出：經選擇的特征集合。

初始化={1,2,···,};

do

6. 最終選擇得分最高的個特征。

3 實 驗

本文實驗選擇在3個開源的大規模三維點云分類數據集(ModelNet40，IntrA，ShapeNetCore)上進行實驗，分別與5種方法進行了比較，并使用評價指標——分類準確率進行評估對比。此外，為論證FSSO的適用性，還在4個高維人工特征數據集(USPS，TOX_171，lymphoma，CLL_SUB_111)上進行了驗證。

3.1 數據集

ModelNet40[23]是人造物體點云數據集，包含12 311個物體，涵蓋40個類別。遵循官方提供的實驗設置，其中9 843個物體用于訓練，剩余的2 468個物體用于測試。對該數據集使用CurveNet[9]進行特征提取，取網絡分類層的輸入作為提取的樣本特征，維數為2 048。

IntrA[24]是一個二分類的顱內動脈瘤的3D數據集，包含正常的血管片段和動脈瘤片段共2 025個樣本。實驗設置遵循五折交叉驗證方式。采用3DMedPT[10]對IntrA數據集進行特征提取，取網絡分類層的輸入作為提取的樣本特征，相應特征維數為512。

ShapeNetCore[25]數據集包含51 300個三維模型，覆蓋55個類別。依據官方提供的實驗設置，該數據集的訓練集、驗證集和測試集分別含35 708，5 158和10 261個樣本，其中驗證集僅在訓練深度模型時用到，保存驗證集上表現最好的模型參數。使用DGCNN[11]對ShapeNetCore數據集進行特征提取，取網絡分類層的輸入作為提取到的樣本特征，相應的維數為512。

這里CurveNet，3DMedPT和DGCNN均作為三維點云樣本的特征提取器，提取到的特征直接作為特征選擇算法的輸入。

此外，為充分地驗證FSSO的有效性，還在4個高維/較大規模手工特征數據集上進行了實驗：USPS，是手寫體數據集，含9 298個樣本，涵蓋0～9是個類別，特征維數是256；TOX_171，是生物數據集，涵蓋4個的共171個樣本，特征維數是5 748；lymphoma，是生物基因數據集，有來自 9個類別的96個樣本，維數是4 026；CLL_SUB_111是基因數據集，共111個樣本，來自3個類別，特征維數是11 340。

3.2 對比方法和實驗設置

表1展示了9種對比方法和基準方法(Baseline)的相關信息，其中基準方法指所有原始特征均被選擇。，，，分別代表樣本數、特征維數、類別數和算法的迭代次數。

表1 本文實驗涉及到的對比方法的基本信息

表1還給出各算法的時間復雜度，其數據均來自其參考文獻，若未提及，則用符號“-”替代。本文FSSO的時間復雜度包含2個部分，一是優化的類均值中心算法的時間復雜度，需要()的時間；二是基于類內相對偏離的特征選擇算法的時間復雜度。該特征選擇算法基于特殊離群樣本的類內相對偏離，考慮到一個數據庫中的離群樣本數遠小于樣本總數，因此特征選擇算法需要的時間小于()，那么FSSO的時間復雜度則最多為(+)。對于大多數的三維點云數據集，FSSO方法的時間損耗是可接受的。

本文實驗采用2種常見的分類器驗證分類效果，即：線性支持向量機(support vector machine，SVM)和K-近鄰分類器(K-nearest neighbor algorithm，KNN)。其中，設置KNN分類器的參數為=2,3,···,10，并選取最高分類準確率作為最終的結果。

遵循文獻[22,26]的工作，本文對所有方法采用網格搜索法，選擇不同百分比下的特征數并計算相應的分類準確率，將其中的全局最優的結果作為實驗結果展示。

3.3 實驗結果與分析

表2為不同對比方法、不同分類器在三維點云數據集ModelNet40，IntrA和ShapeNetCore上的全局最優分類結果。值得注意的是，由于TRC，DGUFS和LRMLR涉及計算求逆矩陣或成對樣本之間的距離，計算成本十分巨大，故不使用LRMLR對樣本數超過50 000的大規模數據集ShanpeNetCore進行實驗。圖4為在ModelNet40，IntrA和ShapeNetCore上，當選擇不同百分比特征數時得到的分類準確率，5種進行比較的方法為：ReliefF，MI，ILFS，RLSR和Inf-FS。注意到，由于二分類數據集IntrA的2個類別下的樣本數差別巨大，因此，基于SOs篩選特征的FSSO算法會在類內偏離不再減小時自動停止特征選擇，故在圖4(c)和(d)中，分別選擇前65%，70%，···，95%特征數進行比較。顯然對于3種數據集，本文的FSSO算法位于其他對比方法的上方，說明FSSO選擇出的特征子集表現更好，能獲得更高的分類準確率。此外，還可以得到如下結論：

(1) 表2展示的在全部數據集上、無論何種分類器，FSSO算法得到的分類準確率穩定地優于Baseline，這不僅說明對三維點云數據進行特征選擇是十分有必要的，并且表明了FSSO算法能有效地選出有識別力的特征子集。反觀一些對比方法，如Inf-FS，DGUFS和LRMLR等，其分類表現普遍劣于Baseline；

(2) 相較于其他對比方法，FSSO選出的特征子集表現的更加出色，如，在ModelNet40上，FSSO+SVM (93.03%)比次佳的ReliefF+SVM (92.95%)多正確分類了3個樣本；在IntrA上，FSSO+KNN (96.99%)比次佳的ReliefF+KNN (96.94%)多正確分類了1個樣本。值得注意的是，對于像IntrA這樣的醫學影像數據集，正確分類樣本數的提高是具有實際應用價值的；

(3) 結合圖4可以發現，選擇50%～90%特征數時，FSSO比其他對比方法有更加顯著地分類優越性。這說明FSSO能夠優先篩除冗余特征、更多地保留特征原始信息。

表2中有多個方法在ModelNet40和IntrA上取到了相同的全局最優分類準確率，因此在表3中列出了取得該準確率時對應的特征數。結合表3可以看到，在大多數情況下FSSO在選擇較少特征時已可以取得其全局最優結果，這是因為在FSSO特征選擇過程中，最冗余的特征總是被最先找到并被賦予較小的得分，這種方式得到的特征評分相較于其他對比方法更加準確。

表2 各方法在ModelNet40，IntrA，ShapeNetCore上的全局最優分類準確率(%)

注：加粗數據為最優值

圖4 5種對比方法(ReliefF，MI，ILFS，RLSR和Inf-FS)與FSSO在不同特征數百分比下的分類準確率比較

表3 各方法在取得最優分類準確率時的特征維數百分比(%)

3.4 FSSO在高維手工特征/較大規模數據集上的補充驗證

表4給出了本文方法在4個高維/較大規模手工特征數據集上的結果。可見，本文方法比其他特征選擇算法的分類準確率更高，說明本文方法在高維和較大規模的手工特征數據集上仍然表現出較好的性能。

表4 在高維/大規模手工特征數據集上的全局最優分類準確率，采用SVM分類器(%)

注：加粗數據為最優值

3.5 參數分析

使用SVM作為分類器對FSSO中的參數和進行分析。由圖5可見，FSSO在5個數據集上的準確率均較穩定，而出現下降的情況集中在圖的四周，即當或過大或過小時，準確率略有下降。圖5結果表明，FSSO對參數不敏感，當參數在一個較大的范圍內變化時，FSSO的分類準確率仍能保持穩定。因此，ModelNet40上建議參數區間為?[0.7,0.9]，?[3.8,4.2]；IntrA建議為?[0.7,0.9]，?[2,2.4]；ShapeNetCore建議為?[0.7,0.9]，?[8.2,8.6]；TOX_171建議為?[0.5,0.7]，?[2,2.2]；CLL_SUB_111建議為?[0.9,1]，?[1.6,1.8]。

圖5 不同參數組合下FSSO的比較結果(SVM分類器)

4 總結與展望

針對三維點云特征中包含大量冗余成分的問題，本文提出了一種新的特征選擇方法——基于特殊離群樣本優化的特征選擇算法(FSSO)。首先計算優化的均值中心，接著通過計算特殊離群樣本的類內相對偏離程度給特征賦值并進行篩選。與其他特征選擇算法相比，本文方法有2個顯著優勢：①在3個廣泛使用的點云分類數據集和4個高維/大規模手工特征數據集上取得了最優或接近最優的準確率，表明了本文方法有效地去除了冗余特征；②在一定范圍內調節2個參數，算法仍保持較高的準確率，表明算法對參數不敏感。實驗結果表明FSSO選擇出的特征能夠獲得更好地分類效果，且計算效率更高。后續工作將聚焦于設計出更加合理的類中心算法、設計更準確的特殊離群樣本捕捉算法，以提升特征選擇算法的性能。

[1] 王文曦, 李樂林. 深度學習在點云分類中的研究綜述[J]. 計算機工程與應用, 2022, 58(1): 26-40.

WANG W X, LI L L. Review of deep learning in point cloud classification[J]. Computer Engineering and Applications, 2022, 58(1): 26-40 (in Chinese).

[2] DENG S, FENG Y D, WEI M Q, et al. Direction-aware feature-level frequency decomposition for single image deraining[C]//The 13th International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2021: 650-656.

[3] 劉藝, 曹建軍, 刁興春, 等. 特征選擇穩定性研究綜述[J]. 軟件學報, 2018, 29(9): 2559-2579.

LIU Y, CAO J J, DIAO X C, et al. Survey on stability of feature selection[J]. Journal of Software, 2018, 29(9): 2559-2579 (in Chinese).

[4] CHARLES R Q, HAO S, MO K C, et al. PointNet: deep learning on point sets for 3D classification and segmentation[C]//2017 IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2017: 77-85.

[5] QI C R, YI L, SU H, et al. PointNet++: deep hierarchical feature learning on point sets in a metric space[C]//The 31st International Conference on Neural Information Processing Systems. New York: ACM Press, 2017: 5105-5114.

[6] ZHAO H, JIANG L, FU C, et al. Pointweb: Enhancing local neighborhood features for point cloud processing[C]//IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2019: 5565–5573.

[7] LI J, CHEN B, LEE G. So-net: self-organizing network for point cloud analysis[C]//IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2018: 9397-9406.

[8] XU Q, SUN X, WU C, et al. Grid-gcn for fast and scalable point cloud learning[C]//IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2020: 5661-5670.

[9] XIANG T G, ZHANG C Y, SONG Y, et al. Walk in the cloud: learning curves for point clouds shape analysis[C]//2021 IEEE/CVF International Conference on Computer Vision. New York: IEEE Press, 2021: 895-904.

[10] YU J, ZHANG C, WANG H, et al. 3D medical point transformer: introducing convolution to attention networks for medical point cloud analysis[EB/OL]. [2022-01-04]. https://arxiv.org/abs/2112.04863.

[11] WANG Y, SUN Y, LIU Z, et al. Dynamic graph CNN for learning on point clouds[J]. Acm Transactions on Graphics, 2019, 38(5): 1-12.

[12] LI J D, TANG J L, LIU H. Reconstruction-based unsupervised feature selection: an embedded approach[C]//The 26th International Joint Conference on Artificial Intelligence. New York: ACM Press, 2017: 2159-2165.

[13] DUDA R O, HART P E, STORK D G. Pattern classification[M]. 2nd Edition. Boston: McGraw-Hill, 2001: 177-179.

[14] KONONENKO I. Estimating attributes: analysis and extensions of RELIEF[J]. European Conference on Machine Learning, 1994, 784: 171-182.

[15] ZHANG Y, WU J, CAI J. Compact representation of high-dimensional feature vectors for large-scale image recognition and retrieval[J]. IEEE Transactions on Image Processing, 2016, 25(5): 2407-2419.

[16] ROFFO G, MELZI S, CASTELLANI U, et al. Infinite latent feature selection: a probabilistic latent graph-based ranking approach[C]//2017 IEEE International Conference on Computer Vision. New York: IEEE Press, 2017: 1407-1415.

[17] NIE F, XIANG S, JIA Y, et al. Trace ratio criterion for feature selection[C]//The 23th AAAI. Palo Alto: AAAI, 2008: 671-676.

[18] CHEN X J, NIE F P, YUAN G W, et al. Semi-supervised feature selection via rescaled linear regression[C]//The 26th International Joint Conference on Artificial Intelligence. New York: ACM Press, 2017: 1525-1531.

[19] ROFFO G, MELZI S, CRISTANI M. Infinite feature selection[C]//2015 IEEE International Conference on Computer Vision. New York: IEEE Press, 2015: 4202-4210.

[20] TANG C, BIAN M, LIU X, et al. Unsupervised feature selection via latent representation learning and manifold regularization[J]. Neural Netw, 2019, 117: 163-178.

[21] GUO J, ZHU W W. Dependence guided unsupervised feature selection[EB/OL]. [2021-12-13]. https://zhuanlan.zhihu.com/p/ 37216951.

[22] YUAN L, YANG G, XU Q, et al. Discriminative feature selection with directional outliers correcting for data classification[J]. Pattern Recognition, 2022, 126: 108541.

[23] WU Z R, SONG S R, KHOSLA A, et al. 3D ShapeNets: a deep representation for volumetric shapes[C]//2015 IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2015: 1912-1920.

[24] YANG X, XIA D, KIN T, et al. Intra: 3d intracranial aneurysm dataset for deep learning[C]//IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2020: 2656-2666.

[25] CHANG A, FUNKHOUSER T, GUIBAS L. Shapenet: an information-rich 3D model repository[EB/OL]. [2022-01-06]. https://arxiv.org/pdf/1512.03012.pdf.

[26] NIE F P, YANG S, ZHANG R, et al. A general framework for auto-weighted feature selection via global redundancy minimization[J]. IEEE Transactions on Image Processing, 2019, 28(5): 2428-2438.

A new 3D point clouds feature selection method using specific outliers optimization

HUANG Xiang, WANG Hong-xing, GU Xu, MENG Yue, WANG Hao-yu

(Jiangsu Frontier Electric Power Technology Co., Ltd., Nanjing Jiangsu 211102, China)

With the rapid development of technologies in metaverse, digital twins, virtual and augmented reality, three-dimensional (3D) point clouds have been widely applied to electric power, construction, advanced manufacturing, and other industries. As a result, how to reduce the redundancies of 3D point clouds data and how to effectively select useful point cloud features have played a critical role in the full use of massive point clouds data. Considering that most of the current feature selection methods pay little attention to specific instances, in this paper, we proposed a novel supervised feature selection method, named feature selection based on specific outliers optimization (FSSO). Specifically, in order to obtain accurate specific outliers (SOs), we first optimized the traditional mean center of class, and automatically defined the class majority. Then, we proposed the feature selection algorithm that could compute the intra-class relative deviation of SOs, and score features based on the deviations. Extensive experiments on 3D data clouds classification datasets (ModelNet40, IntrA, and ShapeNetCore), and on four high-dimensional handcrafted datasets show that the proposed FSSO can select discriminative features, and improve the classification accuracy.

three-dimensional point clouds; supervised feature selection; specific outliers; intra-class relative deviation degree; classification

TP 391

10.11996/JG.j.2095-302X.2022050884

A

2095-302X(2022)05-0884-08

2022-04-02；

2022-06-22

2 April，2022；

22 June，2022

黃 祥(1990-)，男，工程師，本科。主要研究方向為高壓電氣試驗、無人機電力巡檢作業及電力巡檢圖像識別等。E-mail：huangxiang1124@sohu.com

HUANG Xiang (1990-), engineer, bachelor. His main research interests cover include high-voltage electrical test, UAV power patrol operation and power patrol image recognition. E-mail：huangxiang1124@sohu.com