2025-11-24T15:01:18.137860

Kernel Representation and Similarity Measure for Incomplete Data

Cao, Yang, He et al.
Measuring similarity between incomplete data is a fundamental challenge in web mining, recommendation systems, and user behavior analysis. Traditional approaches either discard incomplete data or perform imputation as a preprocessing step, leading to information loss and biased similarity estimates. This paper presents the proximity kernel, a new similarity measure that directly computes similarity between incomplete data in kernel feature space without explicit imputation in the original space. The proposed method introduces data-dependent binning combined with proximity assignment to project data into a high-dimensional sparse representation that adapts to local density variations. For missing value handling, we propose a cascading fallback strategy to estimate missing feature distributions. We conduct clustering tasks on the proposed kernel representation across 12 real world incomplete datasets, demonstrating superior performance compared to existing methods while maintaining linear time complexity. All the code are available at https://anonymous.4open.science/r/proximity-kernel-2289.
academic

अधूरे डेटा के लिए कर्नल प्रतिनिधित्व और समानता माप

मूल जानकारी

  • पेपर ID: 2510.13352
  • शीर्षक: अधूरे डेटा के लिए कर्नल प्रतिनिधित्व और समानता माप
  • लेखक: Yang Cao, Sikun Yang, Kai He, Wenjun Ma, Ming Liu, Yujiu Yang, Jian Weng
  • वर्गीकरण: cs.LG (मशीन लर्निंग)
  • प्रकाशन समय: 15 अक्टूबर 2024 (arXiv प्रस्तुति)
  • पेपर लिंक: https://arxiv.org/abs/2510.13352v1

सारांश

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

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

मूल समस्या

अधूरे डेटा की समानता माप नेटवर्क खनन, अनुशंसा प्रणाली और उपयोगकर्ता व्यवहार विश्लेषण में एक मौलिक चुनौती है। वास्तविक दुनिया के डेटा उपयोगकर्ता गोपनीयता वरीयताओं, सर्वेक्षण गैर-प्रतिक्रिया, सूचना स्वैच्छिक गैर-प्रकटीकरण और अन्य कारकों के कारण अनिवार्य रूप से अधूरे होते हैं।

समस्या की महत्ता

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

मौजूदा विधियों की सीमाएं

  1. विलोपन विधि: लापता मानों को अनदेखा करता है या पूरी तरह से अधूरे नमूनों को हटाता है, जिससे गंभीर सूचना हानि और पूर्वाग्रह होता है
  2. प्रक्षेपण विधि: सांख्यिकीय मात्रा या जटिल तकनीकों का उपयोग करके लापता मानों को भरता है, अक्सर अंतर्निहित डेटा वितरण को पकड़ने में विफल रहता है, और वास्तविक समानता संरचना को प्रतिबिंबित न करने वाले कृत्रिम पैटर्न पेश कर सकता है
  3. गहन शिक्षण विधि: आशाजनक होने के बावजूद, आमतौर पर बड़े डेटासेट और महत्वपूर्ण कम्प्यूटेशनल संसाधनों की आवश्यकता होती है, सैद्धांतिक गारंटी की कमी होती है और हाइपरपैरामीटर के प्रति संवेदनशील होते हैं

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

मौजूदा विधियां "दो-चरणीय" रणनीति अपनाती हैं (पहले प्रक्षेपण फिर समानता गणना), यह पेपर कर्नल प्रतिनिधित्व स्थान में प्रक्षेपण और समानता माप को संयुक्त रूप से संभालने का एक नया दृष्टिकोण प्रस्तावित करता है।

मूल योगदान

  1. निकटता कर्नल विधि प्रस्तावित करना: समान-आवृत्ति बिनिंग और Voronoi-आधारित निकटता आवंटन के माध्यम से, डेटा को उच्च-आयामी विरल प्रतिनिधित्व में प्रक्षेपित करता है, स्पष्ट घनत्व अनुमान की आवश्यकता के बिना स्थानीय घनत्व के अनुकूल होता है
  2. कैस्केडिंग फॉलबैक रणनीति: लापता मान प्रबंधन के लिए, प्रतिच्छेदन से संघ तक फिर वैश्विक पूर्व तक क्रमिक बाधा छूट मिलान रणनीति प्रस्तावित करता है
  3. रैखिक समय जटिलता: रैखिक समय जटिलता को लागू करता है, जो विधि को बड़े पैमाने पर डेटासेट के लिए स्केलेबल बनाता है
  4. प्रायोगिक सत्यापन: 12 डेटासेट पर क्लस्टरिंग कार्य में मौजूदा विधियों से बेहतर प्रदर्शन प्रदर्शित करता है

विधि विवरण

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

n नमूनों वाले डेटासेट D = {x₁, x₂, ..., xₙ} दिया गया है, जहां प्रत्येक नमूना xᵢ ∈ ℝᵈ एक d-आयामी विशेषता वेक्टर है, जिसमें लापता मान (NaN के रूप में दर्शाए गए) हो सकते हैं। लक्ष्य समानता फ़ंक्शन s : D × D → 0,1 की गणना करना है, जो किसी भी दो नमूनों के बीच समानता को मापता है, जिसका उपयोग डाउनस्ट्रीम क्लस्टरिंग जैसे कार्यों के लिए किया जाता है।

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

1. डेटा-निर्भर बिनिंग और निकटता आवंटन

बिन केंद्र चयन: प्रत्येक विशेषता j के लिए, समान-आवृत्ति बिनिंग का उपयोग करके n_bins बिन केंद्र चुनें:

c_{j,k} = percentile(X_{obs,j}, (k-1)×100/(n_{bins}-1))

जहां k ∈ {1,2,...,n_bins}, X_obs,j विशेषता j के सभी प्रेक्षित मान हैं।

निकटता आवंटन तंत्र: परंपरागत अंतराल सदस्यता के बजाय निकटता आवंटन अपनाएं:

b_{i,j} = argmin_{k∈{1,...,n_{bins}}} |x_{i,j} - c_{j,k}|

यह विशेषता स्थान का Voronoi आरेख बनाता है, जहां प्रत्येक केंद्र c_j,k एक Voronoi कक्ष को परिभाषित करता है।

घनत्व-अनुकूल विशेषता:

  • घने क्षेत्र में: क्रमागत केंद्रों के बीच की दूरी छोटी होती है, छोटे Voronoi कक्ष बनाते हैं, समान दूरी के दो बिंदु अलग-अलग कक्षों में गिरने की अधिक संभावना रखते हैं
  • विरल क्षेत्र में: क्रमागत केंद्रों के बीच की दूरी बड़ी होती है, बड़े Voronoi कक्ष बनाते हैं, समान दूरी के दो बिंदु एक ही कक्ष में गिरने की अधिक संभावना रखते हैं

2. वन-हॉट एन्कोडिंग निर्माण

प्रत्येक विशेषता j और नमूना i के लिए, बाइनरी वेक्टर h_i,j ∈ {0,1}^{n_bins} बनाएं:

h_{i,j,k} = {1 if b_{i,j} = k; 0 otherwise}

संपूर्ण एन्कोडिंग सभी विशेषताओं का संयोजन है: z_i = h_i,1, h_i,2, ..., h_i,d

3. लापता मानों को संभालने के लिए कैस्केडिंग फॉलबैक रणनीति

स्तर 1 - प्रतिच्छेदन मिलान: सभी प्रेक्षित विशेषताओं पर मेल खाने वाले नमूने खोजें:

S₁(i) = ∩_{j∈O_i} C_{i,j}

जहां C_i,j = {m : m≠i, b_m,j = b_i,j}

स्तर 2 - संघ मिलान: यदि S₁(i) = ∅, किसी भी प्रेक्षित विशेषता मिलान तक छूट दें:

S₂(i) = ∪_{j∈O_i} C_{i,j}

स्तर 3 - वैश्विक पूर्व: यदि S₂(i) = ∅, वैश्विक वितरण का उपयोग करें:

p_{j,k} = count of samples in bin k for feature j / count of samples with observed feature j

प्रत्येक स्तर के लिए, लापता एन्कोडिंग का अनुमान लगाने के लिए कर्नल माध्य एम्बेडिंग (KME) का उपयोग करें:

h_{i,j,k} = 1/|S(i)| ∑_{m∈S(i)} h_{m,j,k}

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

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

निकटता कर्नल परिभाषा

K(x_m, x_n) = 1/d · z_m^T z_n = <z_m, z_n>

यह कर्नल Mercer शर्त को संतुष्ट करता है (सममितता और सकारात्मक अर्ध-निश्चितता), संभाव्य व्याख्या है: सभी विशेषताओं पर दोनों नमूनों के एक ही बिन में गिरने की अपेक्षित संभावना की गणना करता है।

प्रायोगिक सेटअप

डेटासेट

UCI से 12 वास्तविक डेटासेट का उपयोग करें, कई क्षेत्रों को कवर करते हुए:

  • चिकित्सा निदान: Kidney, Hepatitis, Heart, Tumor, Cancer
  • जैविक वर्गीकरण: Soybean, Mushroom
  • वित्तीय विश्लेषण: Credit
  • जनसंख्या पूर्वानुमान: Adult
  • राजनीतिक विश्लेषण: Voting
  • अन्य: Mammography, Horse

डेटासेट नमूना संख्या 155 से 48,842 तक, आयाम 5 से 35 तक, लापता दर 0.15% से 19.39% तक।

मूल्यांकन मेट्रिक्स

क्लस्टरिंग गुणवत्ता का मूल्यांकन करने के लिए सामान्यीकृत पारस्परिक सूचना (NMI) का उपयोग करें, K-means क्लस्टरिंग अपनाएं, क्लस्टर संख्या वास्तविक वर्ग संख्या पर सेट करें।

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

9 प्रतिनिधि विधियां:

  1. सरल प्रक्षेपण: माध्य प्रक्षेपण
  2. सांख्यिकीय विधि: MissForest, MICE, KNN, EM
  3. गहन शिक्षण: GAIN, MIRACLE, MIWAE
  4. कर्नल विधि: HI-PMK

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

  • प्रत्येक प्रयोग 10 बार दोहराएं और औसत लें
  • सभी आधारभूत विधियों के लिए हाइपरपैरामीटर ट्यूनिंग करें
  • निकटता कर्नल की बिन संख्या {2,3,4,6,8} में खोजें

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

मुख्य परिणाम

  1. समग्र प्रदर्शन: 12 डेटासेट में से 10 पर सर्वोत्तम या दूसरा सर्वोत्तम प्रदर्शन, औसत NMI सर्वोच्च (0.4245)
  2. सांख्यिकीय महत्व: Friedman-Nemenyi परीक्षण दिखाता है कि निकटता कर्नल HI-PMK को छोड़कर सभी अन्य विधियों से महत्वपूर्ण रूप से बेहतर है
  3. स्थिरता: बॉक्स प्लॉट दिखाता है कि निकटता कर्नल न केवल औसत प्रदर्शन में सर्वोत्तम है, बल्कि विभिन्न डेटासेट पर प्रदर्शन भी अधिक सुसंगत है

लापता दर मजबूती प्रयोग

3L और Messidor डेटासेट पर 10%-50% लापता दर का परीक्षण करें:

  • कम से मध्यम लापता दर (10%-40%) पर स्थिर श्रेष्ठ प्रदर्शन बनाए रखें
  • चरम लापता दर (50%) पर भी उचित प्रदर्शन बनाए रखें
  • इसके विपरीत, KNN और MissForest 30% लापता दर पर प्रदर्शन लगभग शून्य तक गिर जाता है

स्केलेबिलिटी विश्लेषण

  • समय जटिलता: O(nd + d·n log n), निश्चित आयाम के लिए नमूना संख्या के अनुसार रैखिक
  • स्थान जटिलता: O(nd), नमूना संख्या और विशेषता संख्या के अनुसार रैखिक
  • वास्तविक चलने का समय: HI-PMK और MIWAE से महत्वपूर्ण रूप से तेज़

संवेदनशीलता विश्लेषण

बिन संख्या 2 से 10 तक भिन्न होने पर, तीन डेटासेट पर NMI परिवर्तन बहुत कम होता है (जैसे Mammo डेटासेट 0.30-0.33 के बीच उतार-चढ़ाव करता है), विधि की हाइपरपैरामीटर के प्रति असंवेदनशीलता दिखाता है।

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

परंपरागत प्रक्षेपण विधियां

  • सरल प्रक्षेपण: माध्य/बहुलक प्रक्षेपण, कम्प्यूटेशनल रूप से कुशल लेकिन डेटा की प्राकृतिक परिवर्तनशीलता को संरक्षित नहीं कर सकता
  • KNN प्रक्षेपण: k सबसे समान नमूनों पर आधारित, लेकिन उच्च-आयामी विरल डेटा पर खराब प्रदर्शन
  • EM एल्गोरिथ्म: अधिकतम संभावना घनत्व अनुमान पर आधारित, मजबूत वितरण धारणा की आवश्यकता
  • MICE: कई प्रक्षेपण डेटासेट बनाता है, कम्प्यूटेशनल रूप से महंगा और सावधानीपूर्वक मॉडल निर्दिष्टीकरण की आवश्यकता
  • MissForest: यादृच्छिक वन का उपयोग करके पुनरावृत्त प्रक्षेपण, संभावित ओवरफिटिंग और अभिसरण गारंटी की कमी

गहन शिक्षण विधियां

  • GAIN: लापता डेटा वितरण सीखने के लिए जनरेटिव विरोधी नेटवर्क का उपयोग
  • MIWAE: प्रेक्षित डेटा संभावना के निचले बाउंड को अधिकतम करने के लिए गहन अव्यक्त चर मॉडल का उपयोग
  • MIRACLE: कारणात्मक अनुमान और गहन शिक्षण को जोड़कर प्रक्षेपण गुणवत्ता में सुधार

कर्नल विधियां

  • परंपरागत दूरी: यूक्लिडियन दूरी अधूरे डेटा पर सीधे लागू नहीं होती
  • HI-PMK: डेटा-निर्भर कर्नल विधि, लेकिन उच्च कम्प्यूटेशनल जटिलता, हाइपरपैरामीटर संवेदनशील

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

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

  1. निकटता कर्नल कर्नल विशेषता स्थान में अधूरे डेटा के बीच समानता की गणना को सफलतापूर्वक लागू करता है, मूल स्थान में स्पष्ट प्रक्षेपण से बचता है
  2. डेटा-निर्भर बिनिंग को निकटता आवंटन के साथ जोड़कर स्थानीय घनत्व के अनुकूल प्रतिनिधित्व बनाता है, स्पष्ट घनत्व अनुमान की आवश्यकता के बिना
  3. कैस्केडिंग फॉलबैक रणनीति उपलब्ध सूचना को प्रभावी रूप से उपयोग करती है, कठोर मिलान से क्रमिक रूप से वैश्विक पूर्व तक
  4. विधि रैखिक समय जटिलता बनाए रखते हुए श्रेष्ठ प्रदर्शन प्राप्त करती है

सीमाएं

  1. लापता तंत्र धारणा: वर्तमान मूल्यांकन मुख्य रूप से MCAR (पूरी तरह से यादृच्छिक लापता) तंत्र पर आधारित है, वास्तविक डेटा अक्सर अधिक जटिल MAR और MNAR पैटर्न प्रदर्शित करते हैं
  2. बिनिंग रणनीति: समान-आवृत्ति बिनिंग सभी डेटा वितरण के लिए इष्टतम नहीं हो सकती
  3. सैद्धांतिक गारंटी: कैस्केडिंग फॉलबैक तंत्र के सैद्धांतिक अभिसरण गारंटी की कमी

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

  1. MAR और MNAR लापता तंत्र के तहत विधि व्यवहार का अनुसंधान करें
  2. अनुकूली बिनिंग चयन रणनीति का अन्वेषण करें
  3. कैस्केडिंग फॉलबैक तंत्र के सैद्धांतिक अभिसरण गारंटी स्थापित करें
  4. अधिक जटिल डेटा प्रकार और संरचनाओं तक विस्तार करें

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

शक्तियां

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

कमियां

  1. लापता तंत्र सीमा: मुख्य रूप से MCAR धारणा के तहत मूल्यांकन, अधिक जटिल लापता पैटर्न के अनुकूलन की पर्याप्त पुष्टि नहीं
  2. घनत्व अनुमान: हालांकि स्पष्ट घनत्व अनुमान की आवश्यकता नहीं होने का दावा करता है, समान-आवृत्ति बिनिंग अनिवार्य रूप से एक निहित घनत्व अनुमान है
  3. विशेषता स्वतंत्रता: कैस्केडिंग रणनीति में विशेषताओं के बीच निर्भरता संबंध का मॉडलिंग पर्याप्त नहीं हो सकता है
  4. तुलना निष्पक्षता: गहन शिक्षण विधियों के साथ तुलना में, कम्प्यूटेशनल संसाधन और ट्यूनिंग डिग्री में अंतर हो सकता है

प्रभाव

  1. शैक्षणिक योगदान: अधूरे डेटा समानता माप के लिए नया सैद्धांतिक ढांचा प्रदान करता है
  2. व्यावहारिक मूल्य: अनुशंसा प्रणाली, नेटवर्क खनन आदि अनुप्रयोगों में प्रत्यक्ष मूल्य है
  3. पुनरुत्पादनशीलता: कोड लिंक प्रदान करता है, विधि सत्यापन और प्रचार में सहायता करता है

लागू परिदृश्य

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

संदर्भ

पेपर 21 संबंधित संदर्भों का हवाला देता है, जो लापता डेटा प्रबंधन, कर्नल विधि, गहन शिक्षण और अन्य कई क्षेत्रों के महत्वपूर्ण कार्यों को कवर करते हैं, यह अनुसंधान के लिए एक मजबूत सैद्धांतिक आधार और तुलनात्मक बेंचमार्क प्रदान करता है।

सारांश: इस पेपर द्वारा प्रस्तावित निकटता कर्नल विधि अधूरे डेटा समानता माप क्षेत्र में महत्वपूर्ण योगदान देती है, कर्नल प्रतिनिधित्व डिजाइन और कैस्केडिंग फॉलबैक रणनीति के माध्यम से, प्रदर्शन और दक्षता का अच्छा संतुलन प्राप्त करता है। कुछ सीमाओं के बावजूद, इसकी नवाचार और व्यावहारिकता संबंधित अनुप्रयोग क्षेत्रों में महत्वपूर्ण मूल्य रखती है।