Wiwa awọn igbẹkẹle iṣẹ ṣiṣe ni data ni a lo ni ọpọlọpọ awọn agbegbe ti itupalẹ data: iṣakoso data, mimọ data, imọ-ẹrọ iyipada data ati iṣawari data. A ti ṣe atẹjade tẹlẹ nipa awọn igbẹkẹle funrararẹ Anastasia Birillo ati Nikita Bobrov. Ni akoko yii, Anastasia, ọmọ ile-iwe giga ti Ile-iṣẹ Imọ-ẹrọ Kọmputa ti ọdun yii, pin idagbasoke iṣẹ yii gẹgẹbi apakan ti iṣẹ iwadii ti o daabobo ni ile-iṣẹ naa.
Aṣayan iṣẹ-ṣiṣe
Lakoko ti o nkọ ni ile-iṣẹ CS, Mo bẹrẹ lati ṣe iwadi awọn data data ni ijinle, eyun, wiwa fun iṣẹ ṣiṣe ati awọn igbẹkẹle iyatọ. Koko-ọrọ yii ni ibatan si koko-ọrọ ti iṣẹ ikẹkọ mi ni ile-ẹkọ giga, nitorinaa lakoko ti n ṣiṣẹ lori iṣẹ ikẹkọ, Mo bẹrẹ kika awọn nkan nipa ọpọlọpọ awọn igbẹkẹle ninu awọn apoti isura data. Mo ti kowe kan awotẹlẹ ti yi agbegbe - ọkan ninu awọn mi akọkọ ni Gẹẹsi ati fi silẹ si apejọ SEIM-2017. Inu mi dun pupọ nigbati mo rii pe o gba lẹhin gbogbo rẹ, o pinnu lati jinle si koko-ọrọ naa. Erongba funrararẹ kii ṣe tuntun - o bẹrẹ lati lo pada ni awọn ọdun 90, ṣugbọn paapaa ni bayi o ti lo ni ọpọlọpọ awọn agbegbe.
Lakoko igba ikawe keji mi ni aarin, Mo bẹrẹ iṣẹ akanṣe iwadii kan lati mu ilọsiwaju algorithms fun wiwa awọn igbẹkẹle iṣẹ ṣiṣe. O ṣiṣẹ lori rẹ pẹlu St. Petersburg State University ọmọ ile-iwe giga Nikita Bobrov ni JetBrains Iwadi.
Iṣiro idiju ti wiwa fun awọn igbẹkẹle iṣẹ
Iṣoro akọkọ jẹ iṣiro iṣiro. Nọmba ti o ṣeeṣe iwonba ati ti kii-bintin gbára ti wa ni opin loke nipa iye 
nibo 
- nọmba ti tabili eroja. Akoko iṣẹ ti awọn algoridimu ko da lori nọmba awọn abuda nikan, ṣugbọn tun lori nọmba awọn ori ila. Ni awọn ọdun 90, awọn algoridimu wiwa ofin apapo lori PC tabili deede le ṣe ilana awọn eto data ti o ni awọn abuda 20 ati ẹgbẹẹgbẹrun awọn ori ila ni to awọn wakati pupọ. Awọn algoridimu ode oni ti n ṣiṣẹ lori awọn olutọsọna oni-pupọ ṣe awari awọn igbẹkẹle fun awọn eto data ti o ni awọn ọgọọgọrun awọn abuda (to 200) ati awọn ọgọọgọrun ẹgbẹẹgbẹrun awọn ori ila ni isunmọ akoko kanna. Sibẹsibẹ, eyi ko to: iru akoko bẹẹ jẹ itẹwẹgba fun ọpọlọpọ awọn ohun elo gidi-aye. Nitorinaa, a ṣe agbekalẹ awọn ọna lati mu iyara awọn algoridimu ti o wa tẹlẹ.
Awọn eto caching fun awọn ikorita ipin
Ni apakan akọkọ ti iṣẹ naa, a ṣe agbekalẹ awọn ero caching fun kilasi kan ti awọn algoridimu ti o lo ọna ikorita ipin. Ipin kan fun abuda kan jẹ akojọpọ awọn atokọ, nibiti atokọ kọọkan ni awọn nọmba laini pẹlu awọn iye kanna fun abuda ti a fun. Iru atokọ kọọkan ni a pe ni iṣupọ. Ọpọlọpọ awọn algoridimu ode oni lo awọn ipin lati pinnu boya igbẹkẹle kan waye tabi rara, eyun, wọn faramọ lemma: Igbẹkẹle 
waye ti o ba ti 
. Nibi 
ipin kan jẹ apẹrẹ ati imọran ti iwọn ipin ti a lo - nọmba awọn iṣupọ ninu rẹ. Awọn alugoridimu ti o lo awọn ipin, nigbati igbẹkẹle ba ṣẹ, ṣafikun awọn abuda afikun si apa osi ti igbẹkẹle, lẹhinna tun ṣe iṣiro rẹ, ṣiṣe iṣẹ ikorita ti awọn ipin. Isẹ yii ni a pe ni iyasọtọ ninu awọn nkan. Ṣugbọn a ṣe akiyesi pe awọn ipin fun awọn igbẹkẹle ti yoo ni idaduro nikan lẹhin awọn iyipo diẹ ti amọja ni a le tun lo ni itara, eyiti o le dinku akoko ṣiṣe ti awọn algoridimu ni pataki, nitori iṣẹ ikorita jẹ gbowolori.
Nitorinaa, a dabaa heuristic kan ti o da lori Shannon Entropy ati aidaniloju Ginny, bakanna bi metiriki wa, eyiti a pe ni Reverse Entropy. O jẹ iyipada diẹ ti Shannon Entropy ati pe o pọ si bi iyasọtọ ti ṣeto data n pọ si. Heuristic ti a dabaa jẹ bi atẹle:
o ti wa ni 
- ìyí ti uniqueness ti awọn laipe iṣiro ipin 
, ati 
jẹ agbedemeji awọn iwọn ti iyasọtọ fun awọn abuda kọọkan. Gbogbo awọn metiriki mẹta ti a ṣalaye loke ni idanwo bi metiriki alailẹgbẹ. O tun le ṣe akiyesi pe awọn iyipada meji wa ni heuristic. Ni akọkọ tọkasi bi ipin ti isiyi ṣe sunmọ bọtini akọkọ ati gba ọ laaye lati kaṣe si iye nla ti awọn ipin ti o jinna si bọtini agbara. Atunṣe keji n gba ọ laaye lati ṣe atẹle kaṣe ibugbe ati nitorinaa ṣe iwuri lati ṣafikun awọn ipin diẹ sii si kaṣe ti aaye ọfẹ ba wa. Ojutu aṣeyọri ti iṣoro yii gba wa laaye lati ṣe iyara algorithm PYRO nipasẹ 10-40%, da lori dataset. O tọ lati ṣe akiyesi pe algorithm PYRO jẹ aṣeyọri julọ ni agbegbe yii.
Ninu nọmba ti o wa ni isalẹ o le rii awọn abajade ti lilo heuristic ti a dabaa ni akawe si ọna fifipamọ owo-isipade ipilẹ kan. Iwọn X jẹ logarithmic.
Ọna miiran lati tọju awọn ipin
Lẹhinna a dabaa ọna yiyan lati tọju awọn ipin. Awọn ipin jẹ ṣeto ti awọn iṣupọ, ọkọọkan eyiti o tọju awọn nọmba ti tuples pẹlu awọn iye kanna fun awọn abuda kan. Awọn iṣupọ wọnyi le ni awọn ilana gigun ti awọn nọmba tuple, fun apẹẹrẹ ti data inu tabili ba ti paṣẹ. Nitorinaa, a dabaa ero funmorawon fun titoju awọn ipin, eyun ibi ipamọ aarin ti awọn iye ni awọn iṣupọ ti awọn ipin:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Aarin akoko}, underbrace{7, 8}_{Aarin Aarin Keji, 10}}\isalẹ{Compression} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$àfihàn$$
Ọna yii ni anfani lati dinku lilo iranti lakoko iṣẹ ti TANE algorithm lati 1 si 25%. Algoridimu TANE jẹ algorithm Ayebaye fun wiwa awọn ofin apapo; Gẹgẹbi apakan ti adaṣe, a yan algorithm TANE, nitori o rọrun pupọ lati ṣe ibi ipamọ aarin ninu rẹ ju, fun apẹẹrẹ, ni PYRO lati le ṣe iṣiro boya ọna ti a dabaa ṣiṣẹ. Awọn abajade ti o gba ni a gbekalẹ ni aworan ni isalẹ. Iwọn X jẹ logarithmic.
Apero ADBIS-2019
Da lori awọn abajade iwadii naa, ni Oṣu Kẹsan ọdun 2019 Mo ṣe atẹjade nkan kan ni Apejọ 23rd European lori Awọn ilọsiwaju ni Awọn aaye data ati Awọn eto Alaye (ADBIS-2019). Lakoko igbejade, iṣẹ naa ni a ṣe akiyesi nipasẹ Bernhard Thalheim, eniyan pataki kan ni aaye data data. Awọn abajade iwadi ti ṣe ipilẹ ti iwe afọwọkọ mi ni alefa titunto si ni mathimatiki ati awọn oye ni Ile-ẹkọ giga ti Ipinle St. Pẹlupẹlu, awọn abajade fihan pe awọn ọna ti a dabaa jẹ gbogbo agbaye, nitori lori awọn algorithm mejeeji, pẹlu awọn ọna mejeeji, idinku nla ninu lilo iranti ni a ṣe akiyesi, ati idinku nla ni akoko iṣẹ ti awọn algoridimu.
orisun: www.habr.com
