A cikin wannan labarin za mu yi magana game da dogara da aiki a cikin bayanan bayanai - menene su, inda ake amfani da su da abin da algorithms ke wanzu don nemo su.
Za mu yi la'akari da dogaron aiki a cikin mahallin bayanan bayanai masu alaƙa. Don sanya shi sosai, a cikin irin waɗannan bayanan bayanai ana adana bayanai a cikin nau'ikan tebur. Na gaba, muna amfani da madaidaitan ra'ayoyi waɗanda ba za su iya musanya ba cikin ƙayyadaddun ka'idar alaƙa: za mu kira teburin da kansa dangantaka, ginshiƙai - halayen (saitin su - tsarin dangantakar), da saitin ƙimar jere akan wani yanki na halaye. - tuple.
Misali, a cikin teburin da ke sama, (Benson, M, M tsarin) shi ne tuple na sifofi (Patient, Paul, Doctor).
A bisa ƙa'ida, an rubuta wannan kamar haka: [Mara lafiya, Jinsi, Doctor] = (Benson, M, M organ).
Yanzu zamu iya gabatar da manufar dogaro da aiki (FD):
Ma'anar 1. Dangantakar R ta gamsar da dokar tarayya X → Y (inda X, Y ⊆ R) idan kuma idan ga kowane tuples , ∈ R yana riƙe: idan [X] = [X], sannan [Y] = [Y]. A wannan yanayin, mun ce X (mai tantancewa, ko ma'anar saitin halayen) yana ƙayyade Y (saitin dogara).
A wasu kalmomi, kasancewar dokar tarayya X → Y yana nufin idan muna da tuple biyu a ciki R kuma sun daidaita a cikin halaye X, sa'an nan za su zo daidai a cikin halaye Y.
Kuma yanzu, a cikin tsari. Bari mu dubi halayen Mai haƙuri и Jima'i wanda muke son sanin ko akwai dogaro a tsakaninsu ko babu. Don irin wannan saitin halayen, abubuwan dogaro masu zuwa na iya kasancewa:
- Mara lafiya → Jinsi
- Jinsi → Mara lafiya
Kamar yadda aka bayyana a sama, domin dogaro na farko ya riƙe, kowace ƙima ta musamman Mai haƙuri Dole ne ƙimar shafi ɗaya ta dace Jima'i. Kuma ga tebur misali wannan hakika lamarin yake. Duk da haka, wannan ba ya aiki a cikin kishiyar shugabanci, wato, dogara na biyu bai gamsu ba, da sifa Jima'i ba mai kayyadewa ba ne Mai haƙuri. Hakazalika, idan muka ɗauki dogaro Likita → Mara lafiya, za ku iya ganin an keta shi, tun da darajar Robin wannan sifa yana da ma'anoni daban-daban - Ellis da Graham.
Don haka, dogaro na aiki yana ba da damar tantance alaƙar da ke akwai tsakanin saitin halayen tebur. Daga nan gaba za mu yi la'akari da alaƙa mafi ban sha'awa, ko kuma irin wannan X → Ymenene su:
- ba maras muhimmanci ba, wato bangaren dama na dogaro ba bangaren hagu ba ne (Y ̸⊆ X);
- kadan, wato babu irin wannan dogaro Z → Y, cewa Z ⊂ X.
Abubuwan dogaro da aka yi la’akari da su har zuwa wannan lokacin sun kasance masu tsauri, wato, ba su samar da duk wani cin zarafi akan teburin ba, amma ban da su, akwai kuma waɗanda ke ba da damar rashin daidaituwa tsakanin ƙimar tuples. Ana sanya irin waɗannan abubuwan dogara a cikin wani aji daban, wanda ake kira kimanin, kuma ana ba da izinin keta su don wasu adadin tuples. Ana daidaita wannan adadin ta matsakaicin madaidaicin kuskuren max. Misali, adadin kuskure = 0.01 na iya nufin cewa za a iya keta dogaro da kashi 1% na tuples ɗin da aka samu akan sifofin da aka yi la'akari. Wato, don rikodin 1000, matsakaicin tuples 10 na iya keta Dokar Tarayya. Za mu yi la'akari da dan kadan daban-daban awo, dangane da nau'i-nau'i daban-daban dabi'u na tuples ana kwatanta. Don jaraba X → Y kan hali r ana la'akari da shi kamar haka:
Bari mu lissafta kuskuren don Likita → Mara lafiya daga misalin da ke sama. Muna da tuples guda biyu waɗanda ƙimarsu ta bambanta akan sifa Mai haƙuri, amma ya zo daidai Likita: [Likita, mai haƙuri] = (Robin, Ellis) da kuma [Likita, mai haƙuri] = (Robin, Graham). Bayan ma'anar kuskure, dole ne mu yi la'akari da dukkan nau'i-nau'i masu cin karo da juna, wanda ke nufin za a kasance biyu daga cikinsu: ((, ) da sabaninsa (, ). Bari mu musanya shi cikin dabara kuma mu sami:
Yanzu bari mu yi kokarin amsa wannan tambaya: "Me ya sa shi duka?" A gaskiya, dokokin tarayya sun bambanta. Nau'in farko shine waɗannan abubuwan dogaro waɗanda mai gudanarwa ya ƙaddara a matakin ƙirar bayanai. Yawancin su ba su da yawa, masu tsauri, kuma babban aikace-aikacen shine daidaita bayanai da ƙira na alaƙa.
Nau'i na biyu shine dogara, wanda ke wakiltar bayanan "boye" da alakar da ba a san su ba tsakanin halaye. Wato, ba a yi la'akari da irin waɗannan abubuwan dogara ba a lokacin ƙira kuma ana samun su don saitin bayanan da ake da su, don haka daga baya, bisa ga yawancin dokokin tarayya da aka gano, za a iya yanke shawara game da bayanan da aka adana. Daidai waɗannan dogara ne muke aiki da su. Ana magance su gabaɗayan fannin hakar bayanai tare da dabaru daban-daban na bincike da algorithms waɗanda aka gina bisa tushensu. Bari mu gano yadda abubuwan dogaro na aiki da aka samu (daidai ko kusan) a cikin kowace bayanai na iya zama da amfani.
A yau, ɗaya daga cikin manyan aikace-aikacen dogara shine tsaftace bayanai. Ya ƙunshi haɓaka matakai don gano "bayanan datti" sannan kuma gyara shi. Shahararrun misalan “dattin datti” sune kwafi, kurakuran bayanai ko buga rubutu, ɓataccen ƙimar ƙima, bayanan da suka shuɗe, ƙarin sarari, da makamantansu.
Misalin kuskuren bayanai:
Misalin kwafi a cikin bayanai:
Misali, muna da teburi da jerin dokokin tarayya waɗanda dole ne a aiwatar da su. Tsabtace bayanai a cikin wannan yanayin ya haɗa da canza bayanan don Dokokin Tarayya su zama daidai. A wannan yanayin, adadin gyare-gyare ya kamata ya zama kadan (wannan hanya yana da nasa algorithms, wanda ba za mu mayar da hankali a kan wannan labarin ba). A ƙasa akwai misalin irin wannan canjin bayanai. A gefen hagu shine dangantaka ta asali, wanda, a fili, FLs masu mahimmanci ba su hadu ba (misali na cin zarafi na ɗaya daga cikin FLs yana nunawa a ja). A hannun dama shine dangantakar da aka sabunta, tare da sel kore suna nuna ƙimar da aka canza. Bayan wannan hanya, an fara kiyaye abubuwan da suka dace.
Wani mashahurin aikace-aikacen shine ƙirar bayanai. A nan yana da daraja tunawa da siffofin al'ada da al'ada. Daidaitawa shine tsari na kawo alaƙa cikin daidaituwa tare da wasu buƙatu, kowannensu an bayyana shi ta hanyar al'ada ta hanyarsa. Ba za mu bayyana buƙatun nau'ikan nau'ikan al'ada daban-daban (ana yin wannan a cikin kowane littafi akan kwas ɗin bayanai don farawa), amma za mu lura kawai cewa kowannensu yana amfani da manufar dogaro da aiki ta hanyar kansa. Bayan haka, FLs sune ƙayyadaddun amincin gaskiya waɗanda ake la'akari da su yayin zayyana bayanan bayanai (a cikin mahallin wannan aikin, FLs wani lokaci ana kiran su superkeys).
Bari mu yi la'akari da aikace-aikacen su don siffofin al'ada guda huɗu a cikin hoton da ke ƙasa. Ka tuna cewa tsarin al'ada na Boyce-Codd ya fi tsauri fiye da nau'i na uku, amma ƙasa da ƙarfi fiye da na huɗu. Ba mu yin la'akari da na ƙarshe a yanzu, tun da tsarinsa yana buƙatar fahimtar abubuwan dogara masu yawa, waɗanda ba su da sha'awar mu a cikin wannan labarin.
Wani yanki da abin dogaro ya sami aikace-aikacen su shine rage girman yanayin sararin samaniya a cikin ayyuka kamar gina ƙirar Bayes mai butulci, gano mahimman fasali, da sake fasalin ƙirar koma baya. A cikin labaran asali, ana kiran wannan ɗawainiyar ƙayyadaddun abubuwan da suka dace da sake fasalin [5, 6], kuma an warware shi tare da yin amfani da mahimman bayanai. Tare da zuwan irin waɗannan ayyuka, zamu iya cewa a yau akwai buƙatar mafita wanda zai ba mu damar haɗa bayanan bayanai, nazari da aiwatar da matsalolin ingantawa na sama zuwa kayan aiki guda ɗaya [7, 8, 9].
Akwai algorithms da yawa (na zamani da na zamani) don neman dokokin tarayya a cikin tsarin bayanai, ana iya raba irin waɗannan algorithms zuwa rukuni uku:
- Algorithms ta amfani da traversal of algebraic lattices (Lattice traversal algorithms)
- Algorithms dangane da neman ƙimar da aka yarda da su (Bambanci- da daidaita-daidaita algorithms)
- Algorithms bisa kwatance biyu (Algorithms shigar da Dogaro)
An gabatar da taƙaitaccen bayanin kowane nau'in algorithm a cikin tebur da ke ƙasa:
Kuna iya karanta ƙarin game da wannan rarrabuwa [4]. A ƙasa akwai misalan algorithms ga kowane nau'in:
A halin yanzu, sabbin algorithms suna bayyana waɗanda ke haɗa hanyoyi da yawa don gano abubuwan dogaro da aiki. Misalan irin waɗannan algorithms sune Pyro [2] da HyFD [3]. Ana sa ran yin nazarin ayyukansu a talifofi na gaba na wannan jerin. A cikin wannan labarin za mu bincika kawai mahimman ra'ayoyi da lemma waɗanda ke da mahimmanci don fahimtar dabarun gano dogaro.
Bari mu fara da mai sauƙi - bambanci- da kuma yarda-saitin, ana amfani da su a cikin nau'in algorithms na biyu. Saitin Bambanci shine saitin tuples waɗanda ba su da ƙima iri ɗaya, yayin da aka yarda-saitin, akasin haka, tuple ne waɗanda suke da ƙima iri ɗaya. Ya kamata a lura cewa a cikin wannan yanayin muna la'akari kawai gefen hagu na dogara.
Wani muhimmin ra'ayi da aka ci karo da shi a sama shine algebraic lattice. Tun da yawancin algorithms na zamani suna aiki akan wannan ra'ayi, muna buƙatar samun ra'ayin abin da yake.
Domin gabatar da ra'ayi na lattice, ya zama dole a ayyana wani sashe da aka ba da oda (ko saitin da aka ba da umarni, taƙaice a matsayin poset).
Ma'anar 2. An ce saitin S za a yi odar shi ta hanyar alaƙar binary ⩽ idan ga duka a, b, c ∈ S waɗannan kaddarorin sun gamsu:
- Reflexivity, wato, a ⩽ a
- Antisymmetry, wato, idan a ⩽ b da b ⩽ a, to a = b
- Transitivity, wato, ga a ⩽ b da b ⩽ c ya bi cewa a ⩽ c
Ana kiran irin wannan alaƙar alaƙar oda (sako da baya), kuma saitin kanta ana kiran sa wani ɓangaren tsari. Bayanin hukuma: ⟨S, ⩽⟩.
A matsayin mafi sauƙi misali na saitin da aka ba da oda, za mu iya ɗaukar saitin duk lambobi na halitta N tare da tsarin tsari na yau da kullun ⩽. Yana da sauƙi don tabbatar da cewa duk abubuwan da ake bukata sun gamsu.
Misali mafi ma'ana. Yi la'akari da saitin duk rukunin rukunin {1, 2, 3}, wanda alaƙar haɗawa ta yi oda ⊆. Lallai, wannan alaƙar tana gamsar da duk wani sharuɗɗan oda, don haka ⟨P ({1, 2, 3}), ⊆⟩ sashe ne da aka yi oda. Hoton da ke ƙasa yana nuna tsarin wannan saitin: idan ana iya samun kashi ɗaya ta kibiyoyi zuwa wani ɓangaren, to suna cikin tsari.
Za mu buƙaci ƙarin ma'anoni guda biyu masu sauƙi daga fagen ilimin lissafi - supremum da rashin ƙarfi.
Ma'anar 3. Bari ⟨S, ⩽⟩ zama saitin da aka yi oda, A ⊆ S. Iyakar sama ta A shine element u ∈ S kamar haka∀x ∈ S: x ⩽ u. Bari U zama saitin duk manyan iyakokin S. Idan akwai ƙarami a cikin U, to ana kiransa supremum kuma ana nuna shi sup A.
An gabatar da manufar ainihin ƙananan iyaka kamar haka.
Ma'anar 4. Bari ⟨S, ⩽⟩ zama saitin da aka yi oda, A ⊆ S. Marasa lafiya na A shine element l ∈ S kamar haka∀x ∈ S: l ⩽ x. Bari L ya zama saitin duk ƙananan iyakokin S. Idan akwai mafi girma kashi a cikin L, to ana kiran shi rashin ƙarfi kuma ana nuna shi azaman inf A.
Yi la'akari a matsayin misali sashe na sama da aka yi odar sa ⟨P ({1, 2, 3}), ⊆⟩ kuma sami mafi girma da rashin ƙarfi a ciki:
Yanzu za mu iya tsara ma'anar algebraic lattice.
Ma'anar 5. Bari ⟨P,⩽⟩ ya zama saiti na wani yanki da aka yi oda kamar yadda kowane rukunin abubuwa biyu yana da iyaka na sama da ƙasa. Sannan P ana kiransa lattice algebraic. A wannan yanayin, ana rubuta sup{x, y} a matsayin x y, kuma inf {x, y} a matsayin x ∧ y.
Bari mu duba cewa misalin aikin mu ⟨P ({1, 2, 3}), ⊆⟩ lattice ne. Lallai, ga kowane a, b ∈ P ({1, 2, 3}), a∨b = a∪b, da a∧b = a∩b. Misali, la'akari da saitin {1, 2} da {1, 3} kuma ku nemo mafi ƙarancinsu da mafi girman su. Idan muka haɗu da su, za mu sami saitin {1}, wanda zai zama marasa lafiya. Muna samun mafi girma ta hanyar haɗa su - {1, 2, 3}.
A cikin algorithms don gano matsalolin jiki, ana wakilta sararin binciken sau da yawa a cikin nau'i na lattice, inda saiti na kashi ɗaya (karanta matakin farko na lattice na bincike, inda gefen hagu na masu dogara ya ƙunshi sifa ɗaya) yana wakiltar kowane sifa. na asali dangantakar.
Na farko, mun yi la'akari da abubuwan dogaro da nau'in ∅ → Sifa guda ɗaya. Wannan mataki yana ba ku damar sanin waɗanne halaye ne maɓallai na farko (don irin waɗannan halayen ba su da ƙima, sabili da haka gefen hagu ba komai). Bugu da ari, irin waɗannan algorithms suna motsawa zuwa sama tare da lattice. Yana da kyau a lura cewa ba za a iya ƙetare dukkanin lattice ba, wato, idan girman girman da ake so na gefen hagu ya wuce zuwa shigarwar, to algorithm ba zai wuce matakin da girman wannan girman ba.
Hoton da ke ƙasa yana nuna yadda za a iya amfani da lattice na algebra a cikin matsalar neman FZ. Anan kowane gefe (X, XY) yana wakiltar dogaro X → Y. Misali, mun wuce matakin farko kuma mun san cewa ana kiyaye jaraba A → B (za mu nuna wannan a matsayin haɗin gwiwa mai kore tsakanin madaidaitan A и B). Wannan yana nufin cewa kara, lokacin da muka matsa sama da lattice, ba za mu iya duba dogara A, C → B, domin ba zai ƙara zama kaɗan ba. Hakazalika, ba za mu bincika ba idan an riƙe abin dogaro C → B.
Bugu da ƙari, a matsayin mai mulkin, duk algorithms na zamani don neman dokokin tarayya suna amfani da tsarin bayanai kamar bangare (a cikin asali na asali - ɓangaren cirewa [1]). Ma'anar ma'anar bangare ita ce kamar haka:
Ma'anar 6. Bari X ⊆ R ya zama saitin halaye don alaƙar r. Tari shine saitin indices na tuples a cikin r waɗanda suke da ƙima ɗaya ga X, wato, c(t) = {i|ti[X] = t[X]}. Bangare saitin gungu ne, ban da gungu na tsawon raka'a:
A cikin kalmomi masu sauƙi, bangare don sifa X jerin jeri ne, inda kowane jeri ya ƙunshi lambobin layi tare da ƙima iri ɗaya don X. A cikin wallafe-wallafen zamani, ana kiran tsarin da ke wakiltar ɓangarori (PLI). An keɓe gungu masu tsayin raka'a don dalilai na matsi na PLI saboda gungu ne waɗanda ke ƙunshe da lambar rikodin kawai tare da ƙima na musamman wanda koyaushe zai kasance mai sauƙin ganewa.
Bari mu kalli misali. Bari mu koma teburin guda tare da marasa lafiya kuma mu gina ɓangarori don ginshiƙan Mai haƙuri и Jima'i (sabon ginshiƙi ya bayyana a hagu, wanda a cikinsa ake yiwa lambobin layin tebur alama):
Bugu da ƙari, bisa ga ma'anar, ɓangaren don shafi Mai haƙuri za a zahiri zama fanko, tun da guda gungu an cire daga partition.
Ana iya samun ɓangarori ta halaye da yawa. Kuma akwai hanyoyi guda biyu don yin haka: ta hanyar shiga cikin tebur, gina partition ta amfani da duk halayen da ake bukata a lokaci guda, ko gina shi ta hanyar yin amfani da aikin tsaka-tsakin bangare ta hanyar amfani da sifofi. Algorithms na binciken dokokin tarayya suna amfani da zaɓi na biyu.
A cikin kalmomi masu sauƙi, don, alal misali, sami bangare ta ginshiƙai ABC, za ku iya ɗaukar partitions don AC и B (ko wani sashe na ɓangarorin ɓangarorin da ba a haɗa su ba) kuma ku haɗa su da juna. Aiki na tsaka-tsaki na sassan biyu yana zaɓar gungu na mafi girman tsayi waɗanda ke gama gari ga sassan biyu.
Bari mu kalli misali:
A cikin akwati na farko, mun sami bangare mara komai. Idan ka dubi teburin da kyau, to, lalle ne, babu daidaitattun dabi'u na halayen biyu. Idan muka ɗan gyara tebur (harka a hannun dama), za mu riga mun sami tsaka-tsaki mara komai. Haka kuma, layukan 1 da 2 a zahiri sun ƙunshi ƙima iri ɗaya don halayen Jima'i и Likita.
Na gaba, za mu buƙaci irin wannan ra'ayi kamar girman bangare. A bisa ka'ida:
A taƙaice, girman ɓangaren shine adadin gungu da aka haɗa a cikin ɓangaren (tuna cewa ba a haɗa gungu guda ɗaya a cikin ɓangaren ba!):
Yanzu za mu iya ayyana ɗaya daga cikin mahimman lemmas, wanda ga ɓangarorin da aka ba mu damar tantance ko ana gudanar da dogaro ko a'a:
Lemma 1. Dogaro A, B → C yana riƙe idan kuma kawai idan
Dangane da lemma, don tantance ko abin dogaro ya riƙe, dole ne a yi matakai huɗu:
- Yi lissafin ɓangaren don gefen hagu na abin dogaro
- Yi lissafin ɓangaren don gefen dama na abin dogaro
- Yi lissafin samfurin mataki na farko da na biyu
- Kwatanta girman ɓangarorin da aka samu a matakai na farko da na uku
A ƙasa akwai misali na bincika ko dogaro yana riƙe bisa ga wannan lemma:
A cikin wannan labarin, mun bincika ra'ayoyi irin su dogara na aiki, kusantar aikin aiki, duba inda ake amfani da su, da kuma menene algorithms don neman ayyukan jiki. Mun kuma bincika daki-daki na asali amma mahimman ra'ayoyi waɗanda ake amfani da su sosai a cikin algorithms na zamani don neman dokokin tarayya.
Magana:
- Huhtala Y. et al. TANE: ingantaccen algorithm don gano abubuwan dogaro da aiki da ƙima // Mujallar kwamfuta. - 1999. - T. 42. - Babu. 2. - shafi na 100-111.
- Kruse S., Naumann F. Ingantacciyar gano madaidaitan abubuwan dogaro // Taimakon Kyautar VLDB. - 2018. - T. 11. - Babu. 7. - shafi na 759-772.
- Papenbrock T., Naumann F. Haɗin kai don gano dogaro da aiki // Abubuwan da aka gabatar na taron kasa da kasa na 2016 akan Gudanar da Bayanai. - ACM, 2016. - shafi 821-833.
- Papenbrock T. et al. Gano dogaro na aiki: Ƙimar gwaji na algorithms bakwai // Ci gaba na Kyautar VLDB. - 2015. - T. 8. - Babu. 10. - shafi 1082-1093.
- Kumar A. Don shiga ko a'a shiga?: Tunani sau biyu game da shiga kafin zaɓin fasalin // Ci gaba na Babban Taron Duniya na 2016 akan Gudanar da Bayanai. - ACM, 2016. - shafi 19-34.
- Abo Khamis M. et al. Koyo a cikin bayanan bayanai tare da ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ma'aikata ta 37th ACM SIGMOD-SIGACT-SIGAI Taro na 2018 akan Ka'idodin Tsarin Bayanai. - ACM, 325. - shafi 340-XNUMX.
- Hellerstein JM et al. Laburaren nazarin MADlib: ko ƙwarewar MAD, SQL // Ci gaba na Kyautar VLDB. – 2012. – T. 5. – Babu. 12. - shafi 1700-1711.
- Qin C., Rusu F. Ƙididdiga masu ƙima don haɓaka haɓakar zuriya na terascale // Gabatarwa na Taron Bita na Hudu akan ƙididdigar bayanai a cikin gajimare. - ACM, 2015. - P. 1.
- Meng X. et al. Mllib: Koyon inji a cikin apache spark //The Journal of Machine Learning Research. - 2016. - T. 17. - Babu. 1. - shafi 1235-1241.
Marubutan labarin: , mai bincike a , и , mai bincike a
source: www.habr.com