MinHash
કોમ્પ્યુટર સાયન્સ અને ડેટા માઇનિંગમાં, મિનહેશ (અથવા લઘુત્તમ સ્વતંત્ર ક્રમચયો સ્થાનિક સંવેદનશીલ હેશિંગ યોજના) એ બે સમૂહો કેટલા સમાન છે તેનો ઝડપથી અંદાજ કાઢવાની એક તકનીક છે. આ યોજનાની શોધ અલ્તાવિસ્ટા દ્વારા કરવામાં આવી હતી અને શરૂઆતમાં તેનો ઉપયોગ ડુપ્લિકેટ વેબ પૃષ્ઠોને શોધવા અને તેમને શોધ પરિણામોમાંથી દૂર કરવા માટે અલ્તાવિસ્ટા સર્ચ એન્જિનમાં કરવામાં આવ્યો હતો. તે મોટા પાયે ક્લસ્ટરિંગ સમસ્યાઓમાં પણ લાગુ કરવામાં આવ્યું છે, જેમ કે ક્લસ્ટરિંગ દસ્તાવેજો તેમના શબ્દોના સમૂહની સમાનતા દ્વારા. જેકાર્ડ સમાનતા અને લઘુતમ હેશ મૂલ્યો જેકાર્ડ સમાનતા ગુણાંક એ બે સમૂહો વચ્ચેની સમાનતાનું સામાન્ય રીતે વપરાતું સૂચક છે. ચાલો એક સમૂહ હોઈએ અને તેનો ઉપગણ હોઈએ, પછી જેકાર્ડ અનુક્રમણિકાને તેમના આંતરછેદના તત્વોની સંખ્યા અને તેમના જોડાણના તત્વોની સંખ્યાના ગુણોત્તર તરીકે વ્યાખ્યાયિત કરવામાં આવે છેઃ જ્યારે બે સમૂહો અલગ હોય ત્યારે આ મૂલ્ય 0 હોય છે, જ્યારે તેઓ સમાન હોય ત્યારે 1 હોય છે, અને અન્યથા 0 અને 1 ની વચ્ચે સખત રીતે હોય છે. બે સમૂહો વધુ સમાન છે (એટલે કે. જ્યારે તેમનો જેકાર્ડ સૂચકાંક 1 ની નજીક હોય ત્યારે) સામાન્ય રીતે વધુ સભ્યો હોય છે. મિનહૅશનો ધ્યેય આંતરછેદ અને જોડાણની સ્પષ્ટ રીતે ગણતરી કર્યા વિના ઝડપથી અંદાજ કાઢવાનો છે. ચાલો એક હેશ ફંક્શન હોઈએ જે સભ્યોને અલગ પૂર્ણાંકો સાથે મેપ કરે છે, ચાલો સમૂહના તત્વોનું રેન્ડમ ક્રમચય હોઈએ, અને વ્યાખ્યાના કોઈપણ સબસેટ માટે-એટલે કે, સભ્યના સંદર્ભમાં ન્યૂનતમ સભ્ય હોવું જોઈએ. (એવા કિસ્સાઓમાં કે જ્યાં ઉપયોગમાં લેવાતા હેશ ફંક્શનમાં સ્યુડો-રેન્ડમ ગુણધર્મો હોવાનું માનવામાં આવે છે, ત્યાં રેન્ડમ ક્રમચયનો ઉપયોગ કરવામાં આવશે નહીં.) હવે, અને બંનેને લાગુ કરીને, અને કોઈ હેશ અથડામણ ન હોવાનું ધારીને, આપણે જોઈએ છીએ કે મૂલ્યો સમાન છે () જો અને માત્ર ત્યારે જ જો તમામ ઘટકોમાં, લઘુત્તમ હેશ મૂલ્ય ધરાવતું તત્વ આંતરછેદમાં હોય. આ સાચું હોવાની સંભાવના બરાબર જેકાર્ડ અનુક્રમણિકા છે, તેથીઃ એટલે કે, જે સંભાવના સાચી છે તે સમાનતાની બરાબર છે, એમ ધારીને કે તે સમાન વિતરણમાંથી દોરવામાં આવ્યું છે. બીજા શબ્દોમાં કહીએ તો, જો રેન્ડમ વેરિયેબલ છે જે ક્યારે એક છે અને અન્યથા શૂન્ય છે, તો તે એક નિષ્પક્ષ અંદાજ છે. તેના પોતાના પર જેકાર્ડ સમાનતા માટે ઉપયોગી અંદાજકાર બનવા માટે ખૂબ ઊંચું તફાવત છે, કારણ કે તે હંમેશા શૂન્ય અથવા એક હોય છે. મિનહૅશ યોજનાનો વિચાર એ જ રીતે બાંધવામાં આવેલા ઘણા ચલોને એકસાથે સરેરાશ કરીને આ તફાવતને ઘટાડવાનો છે. મિન્હાશ યોજનાનું સૌથી સરળ સંસ્કરણ વિવિધ હેશ કાર્યોનો ઉપયોગ કરે છે, જ્યાં એક નિશ્ચિત પૂર્ણાંક પરિમાણ હોય છે, અને આ કાર્યોના મૂલ્યો દ્વારા દરેક સમૂહને રજૂ કરે છે. યોજનાના આ સંસ્કરણનો ઉપયોગ કરીને અંદાજ કાઢવા માટે, ચાલો હેશ કાર્યોની સંખ્યા કે જેના માટે, અને અંદાજ તરીકે ઉપયોગ કરીએ. આ અંદાજ વિવિધ 0-1 રેન્ડમ ચલની સરેરાશ છે, જેમાંથી દરેક ક્યારે એક અને અન્યથા શૂન્ય છે, અને જેમાંથી દરેકનો નિષ્પક્ષ અંદાજ છે. તેથી, તેમની સરેરાશ પણ એક નિષ્પક્ષ અંદાજકાર છે, અને 0-1 રેન્ડમ ચલોના સરવાળા માટે પ્રમાણભૂત વિચલન દ્વારા, તેની અપેક્ષિત ભૂલ છે. તેથી, કોઈપણ અચળાંક માટે એક અચળાંક એવો હોય છે કે અંદાજની અપેક્ષિત ભૂલ મહત્તમ હોય. ઉદાહરણ તરીકે,. 05 કરતા ઓછી અથવા તેની બરાબરની અપેક્ષિત ભૂલનો અંદાજ કાઢવા માટે 400 હેશની જરૂર પડશે. બહુવિધ હેશ વિધેયોની ગણતરી કરવી ગણતરીત્મક રીતે ખર્ચાળ હોઈ શકે છે, પરંતુ મિનહેશ યોજનાનું સંબંધિત સંસ્કરણ માત્ર એક જ હેશ વિધેયનો ઉપયોગ કરીને આ દંડને ટાળે છે અને તેનો ઉપયોગ હેશ વિધેય દીઠ માત્ર એક ન્યૂનતમ મૂલ્ય પસંદ કરવાને બદલે દરેક સમૂહમાંથી બહુવિધ મૂલ્યો પસંદ કરવા માટે કરે છે. ચાલો એક હેશ ફંક્શન હોઈએ, અને એક નિશ્ચિત પૂર્ણાંક હોઈએ. જો ડોમેનમાં કોઈપણ અથવા વધુ મૂલ્યોનો સમૂહ હોય, તો તે સભ્યોના સબસેટ તરીકે વ્યાખ્યાયિત કરો કે જે સૌથી નાના મૂલ્યો ધરાવે છે. આ ઉપગણ સમૂહ માટે સહી તરીકે વપરાય છે, અને કોઈપણ બે સમૂહની સમાનતાનો અંદાજ તેમની સહીઓની સરખામણી કરીને કરવામાં આવે છે. ખાસ કરીને, ધારો કે A અને B કોઈપણ બે સમૂહો છે. પછી k તત્વોનો સમૂહ છે, અને જો h એ રેન્ડમ ફંક્શન છે તો k તત્વોનો કોઈપણ સબસેટ પસંદ થવાની શક્યતા સમાન છે; એટલે કે, તેનો એક સરળ રેન્ડમ નમૂનો છે. સબસેટ એ એવા સભ્યોનો સમૂહ છે જે આંતરછેદના છે. તેથી, | |/એક નિષ્પક્ષ અંદાજકાર છે. આ અંદાજકાર અને બહુવિધ હેશ વિધેયો દ્વારા ઉત્પાદિત અંદાજકાર વચ્ચેનો તફાવત એ છે કે હંમેશા બરાબર સભ્યો હોય છે, જ્યારે બહુવિધ હેશ વિધેયો બે અલગ-અલગ હેશ વિધેયોમાં સમાન મિનિમા હોઈ શકે તેવી શક્યતાને કારણે નમૂના તત્વોની ઓછી સંખ્યા તરફ દોરી શકે છે. જો કે, જ્યારે સેટના કદની તુલનામાં નાનો હોય, ત્યારે આ તફાવત નજીવી હોય છે. રિપ્લેસમેન્ટ વિના નમૂના લેવા માટે પ્રમાણભૂત ચેર્નોફ બાઉન્ડ્સ દ્વારા, આ અંદાજકર્તાએ બહુવિધ-હેશ-ફંક્શન યોજનાની કામગીરી સાથે મેળ ખાતી ભૂલની અપેક્ષા રાખી છે. સમયનું વિશ્લેષણ અંદાજકર્તાની ગણતરી યોજનાના કોઈપણ પ્રકારમાં, આપેલ સમૂહોની બે સહીઓમાંથી સમયસર કરી શકાય છે. તેથી, જ્યારે અને અચળાંકો હોય, ત્યારે સહીઓમાંથી અંદાજિત સમાનતાની ગણતરી કરવાનો સમય પણ અચળ હોય છે. દરેક સમૂહની સહીની ગણતરી સમૂહના કદ પર રેખીય સમયમાં કરી શકાય છે, તેથી જ્યારે ઘણી જોડી મુજબની સમાનતાનો અંદાજ કાઢવાની જરૂર હોય ત્યારે આ પદ્ધતિ દરેક સમૂહના સભ્યોની સંપૂર્ણ સરખામણી કરવાની સરખામણીમાં ચાલતા સમયમાં નોંધપાત્ર બચત તરફ દોરી શકે છે. ખાસ કરીને, સેટ કદ માટે ઘણા હેશ પ્રકારો સમય લે છે. સિંગલ હેશ વેરિઅન્ટ સામાન્ય રીતે ઝડપી હોય છે, એમ ધારીને લઘુત્તમ હેશ મૂલ્યોની કતાર જાળવવા માટે સમયની જરૂર પડે છે. વજનનો સમાવેશ મિનહેશની ગણતરીમાં વજનનો સમાવેશ કરવા માટે વિવિધ તકનીકો વિકસાવવામાં આવી છે. સૌથી સરળ તેને પૂર્ણાંક વજન સુધી વિસ્તરે છે. સમૂહ સભ્ય અને પૂર્ણાંક બંનેને સ્વીકારવા માટે અમારા હેશ કાર્યને વિસ્તૃત કરો, પછી દરેક વસ્તુ માટે તેના વજન અનુસાર બહુવિધ હેશ જનરેટ કરો. જો વસ્તુ વખત સમયે આવે, તો હેશ બનાવો. હેશના આ વિસ્તૃત સમૂહ પર મૂળ અલ્ગોરિધમ ચલાવો. આમ કરવાથી અથડામણની સંભાવના તરીકે ભારિત જેકાર્ડ સૂચકાંક મળે છે. વધુ વિસ્તરણ કે જે વધુ સારા રનટાઇમ સાથે વાસ્તવિક વજન પર આ અથડામણની સંભાવનાને પ્રાપ્ત કરે છે તે વિકસાવવામાં આવ્યા છે, એક ગાઢ ડેટા માટે અને બીજું વિરલ ડેટા માટે. એક્સ્ટેન્શન્સનો બીજો પરિવાર ઝડપથી વિતરિત હેશનો ઉપયોગ કરે છે. 0 અને 1 વચ્ચે સમાન રીતે રેન્ડમ હેશને સી. ડી. એફ. વ્યુત્ક્રમ દ્વારા ઘાતાંકીય વિતરણને અનુસરવા માટે રૂપાંતરિત કરી શકાય છે. આ પદ્ધતિ ઘાતાંકીય ચલોના ઓછામાં ઓછા સમૂહના ઘણા સુંદર ગુણધર્મોનો ઉપયોગ કરે છે. આ તેની અથડામણની સંભાવના જેકાર્ડ અનુક્રમણિકા લઘુત્તમ મુજબ સ્વતંત્ર ક્રમચયો તરીકે ઉપજ આપે છે ઉપર વર્ણવ્યા મુજબ મિનહેશ યોજનાને અમલમાં મૂકવા માટે, તત્વો પર રેન્ડમ ક્રમચયોને વ્યાખ્યાયિત કરવા માટે હેશ ફંક્શનની જરૂર પડે છે, જ્યાં સરખામણી કરવા માટેના તમામ સમૂહોના જોડાણમાં અલગ-અલગ તત્વોની કુલ સંખ્યા છે. પરંતુ કારણ કે ત્યાં વિવિધ ક્રમચયો છે, તેને માત્ર સાચા અર્થમાં રેન્ડમ ક્રમચયોને સ્પષ્ટ કરવા માટે બિટ્સની જરૂર પડશે, જે મધ્યમ મૂલ્યો માટે પણ અશક્ય રીતે મોટી સંખ્યા છે. આ હકીકતને કારણે, સાર્વત્રિક હેશિંગના સિદ્ધાંતની સામ્યતા દ્વારા, ક્રમચયોના કુટુંબને શોધવા પર નોંધપાત્ર કામ કરવામાં આવ્યું છે જે "લઘુત્તમ મુજબ સ્વતંત્ર" છે, જેનો અર્થ છે કે ડોમેનના કોઈપણ સબસેટ માટે, કોઈપણ તત્વ ન્યૂનતમ હોવાની સમાન સંભાવના છે. એવું સ્થાપિત કરવામાં આવ્યું છે કે ક્રમચયોના લઘુત્તમ સ્વતંત્ર કુટુંબમાં ઓછામાં ઓછા વિવિધ ક્રમચયો હોવા જોઈએ, અને તેથી તેને એક જ ક્રમચયોને સ્પષ્ટ કરવા માટે બિટ્સની જરૂર છે, જે હજુ પણ અશક્ય રીતે મોટા છે. વ્યવહારુ લઘુત્તમ મુજબના સ્વતંત્ર હેશ કાર્યો ઉપરોક્ત અવ્યવહારુતાને કારણે, લઘુત્તમ મુજબની સ્વતંત્રતાની બે ભિન્ન ધારણાઓ રજૂ કરવામાં આવી છેઃ મર્યાદિત લઘુત્તમ મુજબના સ્વતંત્ર ક્રમચયો પરિવારો અને અંદાજિત લઘુત્તમ મુજબના સ્વતંત્ર પરિવારો. મર્યાદિત લઘુત્તમ-મુજબની સ્વતંત્રતા એ લઘુત્તમ-મુજબની સ્વતંત્રતાની મિલકત છે જે મહત્તમ કાર્ડિનાલિટીના ચોક્કસ સમૂહો સુધી મર્યાદિત છે. લઘુતમ મુજબની અંદાજિત સ્વતંત્રતામાં સંપૂર્ણ સ્વતંત્રતામાં ફેરફાર થવાની નિશ્ચિત સંભાવના છે. 1999માં પિયોટર ઇન્ડીકે સાબિત કર્યું કે હેશ વિધેયોના કોઈપણ કે-મુજબના સ્વતંત્ર પરિવાર પણ મોટા માટે લગભગ લઘુત્તમ મુજબ સ્વતંત્ર છે. ખાસ કરીને, એવા અચળાંકો છે કે જેમ કે, પછી બધા સમૂહો માટે અને. (નોંધ, અહીં એનો અર્થ એ છે કે સંભાવના સૌથી વધુ એક પરિબળ છે જે ખૂબ મોટું છે અને સૌથી ઓછું છે.) આ ગેરંટી, અન્ય વસ્તુઓની સાથે, મિનહેશ અલ્ગોરિધમ દ્વારા જરૂરી જેકાર્ડ બાઉન્ડ આપવા માટે પૂરતી છે. એટલે કે, જો અને તે સમૂહો છે, તો પછી k મુજબના સ્વતંત્ર હેશ વિધેયોને માત્ર બિટ્સનો ઉપયોગ કરીને સ્પષ્ટ કરી શકાય છે, આ અભિગમ સંપૂર્ણપણે લઘુત્તમ મુજબના સ્વતંત્ર ક્રમચયોના ઉપયોગ કરતાં વધુ વ્યવહારુ છે. હેશ કાર્યોનો અન્ય વ્યવહારુ પરિવાર જે લઘુત્તમ સ્વતંત્રતા આપે છે તે ટેબ્યુલેશન હેશિંગ છે. એપ્લિકેશન્સ મિનહૅશ માટેની મૂળ એપ્લિકેશન્સમાં વેબ દસ્તાવેજો વચ્ચે ક્લસ્ટરિંગ અને નજીકના ડુપ્લિકેટ્સને દૂર કરવાનો સમાવેશ થાય છે, જે તે દસ્તાવેજોમાં આવતા શબ્દોના સમૂહ તરીકે રજૂ થાય છે. સમાન તકનીકોનો ઉપયોગ અન્ય પ્રકારના ડેટા માટે ક્લસ્ટરિંગ અને લગભગ-ડુપ્લિકેટ નાબૂદી માટે પણ કરવામાં આવે છે, જેમ કે છબીઓઃ છબી ડેટાના કિસ્સામાં, છબીને તેમાંથી કાપવામાં આવેલી નાની ઉપ-છબીઓના સમૂહ તરીકે અથવા વધુ જટિલ છબી લક્ષણ વર્ણનના સમૂહ તરીકે રજૂ કરી શકાય છે. ડેટા માઇનિંગમાં, એસોસિએશન રૂલ લર્નિંગ માટે એક સાધન તરીકે મિનહેશનો ઉપયોગ કરો. એક ડેટાબેઝ આપવામાં આવે છે જેમાં દરેક એન્ટ્રીમાં બહુવિધ વિશેષતાઓ હોય છે (ડેટાબેઝ એન્ટ્રી દીઠ પંક્તિ અને વિશેષતા દીઠ કૉલમ સાથે 0-1 મેટ્રિક્સ તરીકે જોવામાં આવે છે) તેઓ જેકાર્ડ અનુક્રમણિકામાં મિનહેશ-આધારિત અંદાજોનો ઉપયોગ કરે છે જે વારંવાર સહ-બનતા લક્ષણોની ઉમેદવાર જોડીને ઓળખવા માટે કરે છે, અને પછી માત્ર તે જોડીઓ માટે અનુક્રમણિકાના ચોક્કસ મૂલ્યની ગણતરી કરે છે જે નક્કી કરે છે કે જેની સહ-ઘટનાની આવર્તન આપેલ કડક થ્રેશોલ્ડથી નીચે છે. મિનહેશ અલ્ગોરિધમને બાયોઇન્ફોર્મેટિક્સ માટે સ્વીકારવામાં આવ્યું છે, જ્યાં જીનોમ સિક્વન્સની સરખામણી કરવાની સમસ્યા વેબ પરના દસ્તાવેજોની સરખામણી કરવા જેવી જ સૈદ્ધાંતિક આધાર ધરાવે છે. મિનહેશ-આધારિત સાધનો સંદર્ભ જીનોમ સાથે સમગ્ર જીનોમ અનુક્રમણિકાના ડેટાની ઝડપી સરખામણીને મંજૂરી આપે છે (રેફસેકમાં 90000 સંદર્ભ જીનોમ સાથે એક જીનોમની તુલના કરવા માટે લગભગ 3 મિનિટ), અને વિશિષ્ટતા અને કદાચ મર્યાદિત માત્રામાં માઇક્રોબાયલ પેટા-પ્રકાર માટે યોગ્ય છે. મેટાજેનોમિક્સ અને જિનોમ સંરેખણ અને જિનોમ એસેમ્બલી માટે મિનહેશ વ્યુત્પન્ન અલ્ગોરિધમ્સના ઉપયોગ માટે પણ એપ્લિકેશનો છે. ચોક્કસ સરેરાશ ન્યુક્લિયોટાઇડ ઓળખ (એએનઆઈ) મૂલ્યો મિનહેશ-આધારિત અલ્ગોરિધમ્સ સાથે ખૂબ જ અસરકારક રીતે પેદા કરી શકાય છે. અન્ય ઉપયોગો મિનહેશ યોજનાને સ્થાન-સંવેદનશીલ હેશિંગના ઉદાહરણ તરીકે જોવામાં આવી શકે છે, જે વસ્તુઓના મોટા સમૂહને નાના હેશ મૂલ્યો સુધી એવી રીતે મેપ કરવા માટે હેશ કાર્યોનો ઉપયોગ કરવા માટેની તકનીકોનો સંગ્રહ છે કે, જ્યારે બે વસ્તુઓ એકબીજાથી નાનું અંતર ધરાવે છે, ત્યારે તેમના હેશ મૂલ્યો સમાન હોવાની શક્યતા છે. આ કિસ્સામાં, સમૂહની સહીને તેના હેશ મૂલ્ય તરીકે જોઈ શકાય છે. સમૂહ વચ્ચેના અંતર અને વેક્ટર વચ્ચેના કોસાઇન અંતર માટે અન્ય સ્થાનિક સંવેદનશીલ હેશિંગ તકનીકો અસ્તિત્વ ધરાવે છે; સ્થાનિક સંવેદનશીલ હેશિંગ નજીકના પડોશી શોધ અલ્ગોરિધમ્સમાં મહત્વપૂર્ણ ઉપયોગો ધરાવે છે. મોટી વિતરિત પ્રણાલીઓ માટે, અને ખાસ કરીને મેપરેડ્યુસ માટે, બિંદુ પરિમાણ પર કોઈ નિર્ભરતા વિના સમાનતાની ગણતરી કરવામાં મદદ કરવા માટે મિનહેશની સુધારેલી આવૃત્તિઓ અસ્તિત્વમાં છે. મૂલ્યાંકન અને બેન્ચમાર્ક મિન્હાશ અને સિમહેશ અલ્ગોરિધમ્સની કામગીરીની તુલના કરવા માટે 2006માં ગૂગલ દ્વારા મોટા પાયે મૂલ્યાંકન હાથ ધરવામાં આવ્યું હતું. 2007માં ગૂગલે વેબ ક્રોલિંગ માટે ડુપ્લિકેટ ડિટેક્શન માટે સિમ્હાશનો ઉપયોગ કરવાની અને ગૂગલ ન્યૂઝ પર્સનલાઈઝેશન માટે મિન્હાશ અને એલએસએચનો ઉપયોગ કરવાની જાણ કરી હતી. આ પણ જુઓ સંદર્ભો હેશ કાર્યો ક્લસ્ટરિંગ માપદંડ હેશિંગ સંભવિત ડેટા સ્ટ્રક્ચર્સ