2025-11-10T02:57:56.733881

Regularized Sparse Optimal Discriminant Clustering

Hiraishi, Tanioka, Yadohisa
We propose a new method based on sparse optimal discriminant clustering (SODC), incorporating a penalty term into the scoring matrix based on convex clustering. With the addition of this penalty term, it is expected to improve the accuracy of cluster identification by pulling points within the same cluster closer together and points from different clusters further apart. When the estimation results are visualized, the clustering structure can be depicted more clearly. Moreover, we develop a novel algorithm to derive the updated formula of this scoring matrix using a majorizing function. The scoring matrix is updated using the alternating direction method of multipliers (ADMM), which is often employed to calculate the parameters of the objective function in the convex clustering. In the proposed method, as in the conventional SODC, the scoring matrix is subject to an orthogonal constraint. Therefore, it is necessary to satisfy the orthogonal constraint on the scoring matrix while maintaining the clustering structure. Using a majorizing function, we adress the challenge of enforcing both orthogonal constraint and the clustering structure within the scoring matrix. We demonstrate numerical simulations and an application to real data to assess the performance of the proposed method.
academic

नियमितकृत विरल इष्टतम विभेदक क्लस्टरिंग

मूल जानकारी

  • पेपर ID: 2501.10147
  • शीर्षक: Regularized Sparse Optimal Discriminant Clustering
  • लेखक: Mayu Hiraishi, Kensuke Tanioka, Hiroshi Yadohisa (डोशिशा विश्वविद्यालय)
  • वर्गीकरण: stat.ME (सांख्यिकीय विधियाँ)
  • प्रकाशन तिथि: 15 अक्टूबर 2025
  • पेपर लिंक: https://arxiv.org/abs/2501.10147

सारांश

यह पेपर विरल इष्टतम विभेदक क्लस्टरिंग (SODC) पर आधारित एक नई विधि प्रस्तावित करता है, जिसमें उत्तल क्लस्टरिंग पर आधारित दंड पद को स्कोरिंग मैट्रिक्स में शामिल किया गया है। इस दंड पद को जोड़कर, समान क्लस्टर के भीतर बिंदुओं को करीब लाकर और विभिन्न क्लस्टरों के बीच बिंदुओं को दूर करके क्लस्टरिंग पहचान की सटीकता में सुधार की अपेक्षा की जाती है। जब अनुमान परिणामों को दृश्यमान किया जाता है, तो क्लस्टरिंग संरचना अधिक स्पष्ट रूप से चित्रित की जा सकती है। इसके अलावा, लेखकों ने एक नवीन एल्गोरिदम विकसित किया है जो प्रमुख कार्य का उपयोग करके स्कोरिंग मैट्रिक्स के अद्यतन सूत्र को प्राप्त करता है। स्कोरिंग मैट्रिक्स को वैकल्पिक दिशा गुणक विधि (ADMM) का उपयोग करके अद्यतन किया जाता है, जो सामान्यतः उत्तल क्लस्टरिंग उद्देश्य फलन के मापदंडों की गणना के लिए उपयोग की जाती है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

आयाम न्यूनीकरण क्लस्टरिंग बड़े जटिल डेटा की विशेषताओं की व्याख्या करने में व्यापक रूप से उपयोग की जाती है। यह एक निम्न-आयामी स्थान का अनुमान लगाता है ताकि क्लस्टरों की पहचान की जा सके, उच्च-आयामी डेटा की महत्वपूर्ण विशेषताओं को बनाए रखते हुए कुशल प्रसंस्करण प्राप्त किया जा सके। मौजूदा इष्टतम विभेदक क्लस्टरिंग (ODC) और विरल इष्टतम विभेदक क्लस्टरिंग (SODC) विधियाँ, हालांकि प्रमुख घटक विश्लेषण की तुलना में क्लस्टरिंग को अधिक स्पष्ट रूप से वर्णित करती हैं, निम्नलिखित समस्याओं का सामना करती हैं:

  1. स्कोरिंग मैट्रिक्स संरचना समस्या: SODC में स्कोरिंग मैट्रिक्स LDA में इष्टतम स्कोरिंग के समान क्लस्टरिंग पहचान संरचना को संरक्षित नहीं करता है
  2. स्वतंत्र क्लस्टरिंग सूचना मैट्रिक्स की कमी: ODC और SODC में क्लस्टरिंग सूचना युक्त स्वतंत्र मैट्रिक्स नहीं होता है, जो क्लस्टरिंग अनुमान की सटीकता को प्रभावित कर सकता है
  3. खराब दृश्यमान प्रभाव: SODC डेटा को निम्न-आयामी स्थान में कम करते समय और परिणामों को दृश्यमान करते समय अच्छी तरह से अलग किए गए क्लस्टरिंग संरचना का उत्पादन नहीं कर सकता है

अनुसंधान प्रेरणा

उपरोक्त समस्याओं को हल करने के लिए, लेखकों ने SODC में उत्तल क्लस्टरिंग पर आधारित दंड पद जोड़ने का प्रस्ताव दिया है, ताकि स्कोरिंग मैट्रिक्स पारंपरिक SODC की तुलना में अधिक स्पष्ट क्लस्टरिंग संरचना प्रदान करे, समान क्लस्टर से डेटा बिंदुओं को करीब लाकर और विभिन्न क्लस्टरों से डेटा बिंदुओं को अलग करके।

मुख्य योगदान

  1. RSODC विधि का प्रस्ताव: SODC के आधार पर उत्तल क्लस्टरिंग पर आधारित नियमितकरण पद जोड़कर क्लस्टरिंग पहचान सटीकता में सुधार
  2. नए एल्गोरिदम का विकास: प्रमुख कार्य का उपयोग करके स्कोरिंग मैट्रिक्स के अद्यतन सूत्र को प्राप्त करना, साथ ही ऑर्थोगोनल बाधाओं और क्लस्टरिंग संरचना आवश्यकताओं को पूरा करना
  3. ADMM अनुकूलन ढांचा: स्कोरिंग मैट्रिक्स को अद्यतन करने के लिए वैकल्पिक दिशा गुणक विधि का उपयोग, जटिल बाधा शर्तों को प्रभावी ढंग से संभालना
  4. सैद्धांतिक और अनुभवजन्य सत्यापन: संख्यात्मक सिमुलेशन और वास्तविक डेटा अनुप्रयोग के माध्यम से विधि की प्रभावशीलता को सत्यापित करना

विधि विवरण

कार्य परिभाषा

दिए गए डेटा मैट्रिक्स X∈Rn×pX \in \mathbb{R}^{n \times p} के लिए, लक्ष्य निम्न-आयामी स्थान में kk क्लस्टरों की पहचान करना है, साथ ही चर चयन और आयाम न्यूनीकरण भी करना है।

मॉडल आर्किटेक्चर

RSODC उद्देश्य फलन

RSODC की अनुकूलन समस्या को निम्नानुसार परिभाषित किया गया है:

min⁡B,Y†12∥Y†−HnXB∥F2+η2∥B∥F2+η1∑j=1p∥βj∥2+γ∑i<jαi,j∥yi†−yj†∥2\min_{B,Y^{\dagger}} \frac{1}{2}\|Y^{\dagger} - H_nXB\|_F^2 + \eta_2\|B\|_F^2 + \eta_1\sum_{j=1}^p\|\beta_j\|_2 + \gamma\sum_{i<j}\alpha_{i,j}\|y_i^{\dagger} - y_j^{\dagger}\|_2

बाधा शर्तें: Y†⊤Y†=Ik−1Y^{\dagger\top}Y^{\dagger} = I_{k-1} और Y†⊤1=0Y^{\dagger\top}1 = 0

जहाँ:

  • पहले तीन पद SODC के समान हैं
  • चौथा पद उत्तल क्लस्टरिंग पर आधारित दंड पद है, जो समान नमूनों को करीब लाने को प्रोत्साहित करता है
  • αi,j\alpha_{i,j} भार है, जिसकी गणना इस प्रकार की जाती है: αi,j=ιδi,jexp⁡(−τ∥xi−xj∥22)\alpha_{i,j} = \iota_{\delta_{i,j}}\exp(-\tau\|x_i - x_j\|_2^2)

ADMM विघटन

ADMM एल्गोरिदम लागू करने के लिए, समस्या को इस प्रकार पुनः लिखा जाता है:

min⁡B,Y,V,Λ12∥Y−HnXB∥F2+η2∥B∥F2+η1∑j=1p∥βj∥2+γ∑l∈εαl∥vl∥2\min_{B,Y,V,\Lambda} \frac{1}{2}\|Y - H_nXB\|_F^2 + \eta_2\|B\|_F^2 + \eta_1\sum_{j=1}^p\|\beta_j\|_2 + \gamma\sum_{l \in \varepsilon}\alpha_l\|v_l\|_2

बाधा शर्तें:

  • yi−yj=vly_i - y_j = v_l
  • Y⊤Y=Ik−1Y^{\top}Y = I_{k-1}
  • Y⊤1=0Y^{\top}1 = 0

तकनीकी नवाचार बिंदु

प्रमुख कार्य विधि

मुख्य नवाचार स्कोरिंग मैट्रिक्स अद्यतन में द्विघात पद को संभालने के लिए प्रमुख कार्य का उपयोग करना है। द्विघात रूप tr(Y⊤CY)\text{tr}(Y^{\top}CY) के लिए, प्रमुख कार्य का निर्माण करें:

tr(Y⊤CY)≤2ω−2tr(Y⊤(ωI−C)Q)−tr(Q⊤CQ)\text{tr}(Y^{\top}CY) \leq 2\omega - 2\text{tr}(Y^{\top}(\omega I - C)Q) - \text{tr}(Q^{\top}CQ)

जहाँ ω\omega C=ρ2∑l∈εglgl⊤C = \frac{\rho}{2}\sum_{l \in \varepsilon}g_lg_l^{\top} का सबसे बड़ा eigenvalue है।

ऑर्थोगोनल Procrustes विश्लेषण

प्रमुख कार्य के माध्यम से, Y के अद्यतन को ऑर्थोगोनल Procrustes समस्या में परिवर्तित करें:

min⁡Y∥Y−D∥F2,s.t. Y⊤Y=I\min_Y \|Y - D\|_F^2, \quad \text{s.t. } Y^{\top}Y = I

समाधान Y←LR⊤Y \leftarrow LR^{\top} है, जहाँ D=LΣR⊤D = L\Sigma R^{\top} विलक्षण मान विघटन है।

प्रयोग सेटअप

डेटासेट

  1. सिमुलेशन डेटा:
    • नमूना संख्या n=60,96,156n = 60, 96, 156
    • चर संख्या p=20,50,80,100p = 20, 50, 80, 100
    • क्लस्टर संख्या k=3,4k = 3, 4
    • सूचनात्मक चर संख्या q=2q = 2
  2. वास्तविक डेटा: स्तन कैंसर प्रोटिओमिक्स डेटा (breast TCGA)
    • 150 नमूने, 142 प्रोटीन
    • 3 कैंसर उप-प्रकार: Basal, Her2, LumA
    • 10 सूचनात्मक चर और 70 गैर-सूचनात्मक चर का चयन

मूल्यांकन संकेतक

  • समायोजित Rand सूचकांक (ARI): क्लस्टरिंग सटीकता का मूल्यांकन
  • विचरण अनुपात: क्लस्टर के भीतर विचरण और क्लस्टर के बीच विचरण का अनुपात
  • संवेदनशीलता और विशिष्टता: चर चयन प्रभाव का मूल्यांकन

तुलनात्मक विधियाँ

  • विरल इष्टतम विभेदक क्लस्टरिंग (SODC)
  • टेंडम क्लस्टरिंग (Tandem clustering)
  • न्यूनीकृत k-means (Reduced k-means)
  • कारक k-means (Factorial k-means)
  • t-SNE

कार्यान्वयन विवरण

  • पैरामीटर चयन: kappa गुणांक पर आधारित क्रॉस-सत्यापन
  • η2=0\eta_2 = 0, τ=0.1\tau = 0.1, δ=25\delta = 25
  • अभिसरण सीमा: ϵ>0\epsilon > 0

प्रयोग परिणाम

मुख्य परिणाम

सिमुलेशन प्रयोग

सभी सिमुलेशन सेटिंग्स में, RSODC ARI संकेतक पर तुलनात्मक विधियों से बेहतर प्रदर्शन करता है:

  • k=3 पर: RSODC लगभग सभी पैटर्न में सर्वश्रेष्ठ प्रदर्शन करता है
  • k=4 पर: RSODC सभी तुलनात्मक विधियों से बेहतर प्रदर्शन करता है
  • स्थिरता: pp बढ़ने के साथ, RSODC स्थिर रहता है, जबकि SODC अस्थिर हो जाता है
  • क्लस्टरिंग गुणवत्ता: क्लस्टर केंद्र दूरी ϑ\vartheta बढ़ने के साथ, RSODC का ARI मान अधिक स्पष्ट रूप से बढ़ता है

वास्तविक डेटा अनुप्रयोग

स्तन कैंसर डेटा पर परिणाम:

विधिARI(XB^X\hat{B})ARI(Y^\hat{Y})विचरण अनुपात (XB^X\hat{B})विचरण अनुपात (Y^\hat{Y})
RSODC0.4060.4413.0383.056
SODC0.4010.3632.9092.660

विलोपन प्रयोग

पैरामीटर संवेदनशीलता विश्लेषण

  • भार पैरामीटर: जब τ=0\tau = 0 और δ=0.01\delta = 0.01 हो तो ARI सर्वोच्च है
  • ट्यूनिंग पैरामीटर: η1,γ,ρ\eta_1, \gamma, \rho के विभिन्न संयोजनों का परिणामों पर कम प्रभाव पड़ता है
  • क्लस्टर संख्या चयन: gap सांख्यिकी का उपयोग करके वास्तविक क्लस्टर संख्या को प्रभावी ढंग से निर्धारित किया जा सकता है

कम्प्यूटेशनल जटिलता

RSODC की कम्प्यूटेशनल समय SODC की तुलना में अधिक है, विशेष रूप से जब nn बड़ा हो, लेकिन बेहतर क्लस्टरिंग गुणवत्ता प्रदान करता है।

केस विश्लेषण

दृश्यमान परिणाम दिखाते हैं कि RSODC निम्नलिखित कर सकता है:

  • समान क्लस्टर के भीतर बिंदुओं को अधिक कसकर एकत्रित करना
  • विभिन्न क्लस्टरों के बीच बिंदुओं को अधिक दूर अलग करना
  • अधिक स्पष्ट क्लस्टर सीमाएँ प्रदान करना

संबंधित कार्य

आयाम न्यूनीकरण क्लस्टरिंग विधियाँ

  • इष्टतम विभेदक क्लस्टरिंग (ODC): Zhang और Dai (2009) Fisher रैखिक विभेदक विश्लेषण पर आधारित इष्टतम स्कोरिंग
  • विरल ODC (SODC): Wang आदि (2016) ODC के आधार पर समूह लैसो दंड जोड़ते हैं
  • उत्तल क्लस्टरिंग: Pelckmans आदि (2005), Hocking आदि (2011) उत्तल अनुकूलन का उपयोग करके स्थिर क्लस्टरिंग

इस पेपर का नवाचार

मौजूदा विधियों की तुलना में, RSODC के मुख्य लाभ:

  1. मूल स्थान के बजाय न्यूनीकृत स्थान में मॉडल का अनुमान लगाना
  2. ऑर्थोगोनल बाधाओं और क्लस्टरिंग संरचना को एक साथ संभालने के लिए प्रमुख कार्य का उपयोग करना
  3. अधिक स्पष्ट क्लस्टरिंग दृश्यमान प्रभाव प्रदान करना

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. RSODC उत्तल क्लस्टरिंग दंड पद जोड़कर क्लस्टरिंग पहचान सटीकता में महत्वपूर्ण सुधार करता है
  2. प्रमुख कार्य विधि ऑर्थोगोनल बाधाओं और क्लस्टरिंग संरचना के एक साथ संतुष्ट होने की समस्या को प्रभावी ढंग से हल करती है
  3. प्रयोग सिमुलेशन और वास्तविक डेटा पर विधि की प्रभावशीलता को सत्यापित करते हैं

सीमाएँ

  1. कम्प्यूटेशनल जटिलता: SODC की तुलना में अधिक कम्प्यूटेशनल समय की आवश्यकता है
  2. पैरामीटर चयन: क्रॉस-सत्यापन की कम्प्यूटेशनल लागत अधिक है
  3. भार गणना: मूल स्थान में भार की गणना करना इष्टतम नहीं हो सकता है
  4. डेटा वितरण धारणा: निहित रूप से त्रुटि सामान्य वितरण का पालन करती है

भविष्य की दिशाएँ

  1. अधिक कुशल पैरामीटर चयन विधि विकसित करना
  2. निम्न-आयामी स्थान में भार की गणना करना
  3. क्रॉस-सत्यापन लागत को कम करने के लिए सूचना मानदंड प्राप्त करना
  4. गैर-सामान्य वितरण के विस्तार पर विचार करना

गहन मूल्यांकन

शक्तियाँ

  1. विधि नवाचार शक्तिशाली है: उत्तल क्लस्टरिंग और विरल विभेदक विश्लेषण को चतुराई से जोड़ता है
  2. सैद्धांतिक आधार मजबूत है: प्रमुख कार्य विधि सैद्धांतिक रूप से कठोर है
  3. प्रयोग व्यापक हैं: 5 सिमुलेशन प्रयोग और वास्तविक डेटा सत्यापन शामिल हैं
  4. एल्गोरिदम डिजाइन परिष्कृत है: ADMM ढांचा जटिल बाधा शर्तों को संभालता है

कमियाँ

  1. कम्प्यूटेशनल दक्षता: SODC की तुलना में कम्प्यूटेशनल लागत में महत्वपूर्ण वृद्धि
  2. पैरामीटर संवेदनशीलता: कई हाइपरपैरामीटर को ट्यून करने की आवश्यकता है
  3. प्रयोज्यता सीमा: मुख्य रूप से छोटे पैमाने की क्लस्टरिंग समस्याओं के लिए उपयुक्त है
  4. सैद्धांतिक विश्लेषण: अभिसरण और जटिलता का सैद्धांतिक विश्लेषण अनुपस्थित है

प्रभाव

  1. शैक्षणिक योगदान: आयाम न्यूनीकरण क्लस्टरिंग के लिए नई सोच प्रदान करता है
  2. व्यावहारिक मूल्य: स्पष्ट क्लस्टरिंग दृश्यमान प्रभाव की आवश्यकता वाले परिदृश्यों के लिए उपयुक्त है
  3. पुनरुत्पादनीयता: एल्गोरिदम विवरण विस्तृत है, कार्यान्वयन में आसान है

प्रयोज्य परिदृश्य

  • उच्च-आयामी डेटा का क्लस्टरिंग विश्लेषण
  • चर चयन की आवश्यकता वाले क्लस्टरिंग कार्य
  • स्पष्ट क्लस्टरिंग दृश्यमान प्रभाव की आवश्यकता वाली अन्वेषणात्मक डेटा विश्लेषण
  • जैव सूचना विज्ञान और जीनोमिक्स डेटा विश्लेषण

संदर्भ

मुख्य संदर्भ साहित्य में शामिल हैं:

  • Zhang & Dai (2009): इष्टतम विभेदक क्लस्टरिंग का मूल कार्य
  • Wang et al. (2016): विरल इष्टतम विभेदक क्लस्टरिंग
  • Chi & Lange (2015): उत्तल क्लस्टरिंग के लिए ADMM एल्गोरिदम
  • Hunter & Lange (2004): MM एल्गोरिदम और प्रमुख कार्य

समग्र मूल्यांकन: यह एक उच्च गुणवत्ता वाला सांख्यिकीय विधि पेपर है जो प्रस्तावित RSODC विधि में सैद्धांतिक नवाचार और व्यापक प्रयोगात्मक सत्यापन प्रदान करता है। हालांकि कम्प्यूटेशनल जटिलता अधिक है, लेकिन क्लस्टरिंग गुणवत्ता और दृश्यमान प्रभाव में महत्वपूर्ण सुधार प्रदान करता है, जो आयाम न्यूनीकरण क्लस्टरिंग क्षेत्र में महत्वपूर्ण योगदान देता है।