Секвенцијална анализа података

Секвенцијално претраживање је тема анализе података усмерена ка проналажењу статистички релевантних образаца између примера података где су подаци достављени у секвенци.^[1] Обично се претпоставља да су вредности дискретне, тако да анализа временских серија (енгл. time series) тесно повезана, али обично сматрана за другчију активност. Секвенцијално претраживање је специјалан вид структурне анализе података. Постоје неколико кључних традиционалних рачунарских проблема везана за ово поље. Она укључују израду ефикасних база података и индекса за секвенце информација, издвајање образаца који се често извршавају, поређење сличности секвенци, и повратити недостајале чланове секвенци. Генерално, проблеми секвенцијалне анализе се могу сврстати као анализирање ниски које је обично засновано на алгоритмима за обраду ниски и анализу колекције ставки која је обично заснована на асоцијативном учењу по правилима.

Анализа ниски

Анализа ниски се обично бави ограниченим алфабетом за објекте који се појављују у низу, али сам низ обично може бити веома дугачак. Примери алфабета могу бити у ASCII сету знакова који се користе у природним језичким текстовима, нуклеотида базе „А“,“Г“, „Ц“ и „Т“ ДНК низу или амино-киселине у протеинским низовима. У биологији апликационе анализе распореда алфабета у нискама могу се користити да испитају генетске и протеинске низове како би им се одредиле особине. Познавање низа слова ДНК протеина није коначан циљ сам по себи. Уместо тога, главни задатак је разумети низ, у смислу структуре и биолошке функције. Ово се обично постиже најпре идентификацијом појединачне регионе или структурне јединице сваког низа и затим додељивањем функције свакој структурној јединици. У многим случајевима ово захтева упоређивање датог низа са претходно проучаваним низовима. Упоређивање ниски постаје компликованије када се убацивање, брисање и мутација појаве у ниски.

Истраживање и класификација кључних алгоритама за поређење низова за биоинформатику је представљено од стране Абуелхода и Ганема(2010), које укључује:^[2]

Проблем понављања: који се бави операцијама на једном низу и може бити заснован на методама за тачно подударање ниски или за приближно подударање ниски за проналажење дисперзионе фиксне дужине и максималне дужине понављања, проналажење тандем понављања и проналажење јединственог подниза и (ненаписаних) низова који недостају.
Проблем поравнања: који се бави упоређивањем ниски, тиме што се прво поравају једна или више низова; примери популарних метода укључују BLAST за упоређивање појединачног низа са више низова у бази података, и ClustalW за вишеструка поравнања. Алгоритми понављања могу бити засновани на било методама тачног или приближног поравнања, и могу такође бити класификоване као глобална поравнања, полу-глобална и локална поравнања. Види поравнање низова.

Анализа колекције ставки

Неке проблеме у секвенцијалној анализи откривају честе колекције стваки и ред у коме се јављају, на пример, неко тражи правила форме "ако {муштерија купу кола}, он или она ће вероватно {купити осигурање} у року од недељу дана", или у контексту цена берзе, " Ако це {Нокија и Ериксон унапреде}, веома је вероватно да ће се {Моторола и Самсунг унапредити} у року од 2 дана“. Традиционално, анализа колекције ставки се користи у трговинским апликацијама за откривање правилности између учесталих истовремених изврашавања ставки у великим трансакцијама. На пример, анализирањем трансакција или муштеријине корпе за куповину у продавници, може се извести правило које каже "ако муштерија купи црни лук и кромпир заједно, он или она ће вероватно купити месо за пљескавице у истој куповини.

Истраживање кључних алгоритама за колекције ставки је представљено од стране "Han et al." (2007).^[3]

Две честе технике које се примењују секвенцама база података за учесталу анализу колекција ставки су утицајни "априори" алгоритми и скорија {јез-енг|FP-Growth}} техника.

Варијанте

Традиционална секвенцијална анализа образаца је уређена укључујући и нека ограничења и неко понашање. Џорџ и Бину (2012) су интегрисали три значајна маркетиншка сценарија за анализу промотивно-оријентисаних секвенцијалних образаца.^[4] Промотивно засновани тржишни сценарији у свом истраживању узимају у обзир 1) Пад производа, 2) Ревизију производа и 3) Пуштање у промет производа енгл. DRL(Downturn-Revision-Launch). Разматрањем овога, они су развили енгл. DRL-Prefix Span алгоритам (израђен од Prefix Span) за анализирање DRL образаца свих дужина.

Апликакације

Са великим варијацијама производа и одлика купаца, полица на којој је производ постављен је једна од најважнијих ствари у трговинском окружењу. Трговци не само да могу да повећају сопствен добит него, такође могу да снизе цену се правилним управљањем обезбеђеног простора на полицама и излагањем производа. Да би решио овај проблем, Џорџ и Бину (2013) су предложили приступ да анализирају корисничке обрасце куповине користећи енгл. PrefixSpan алгоритме и смештају производе на полице у односу на анализу образаца куповине.^[5]

Алгоритми

Commonly used algorithms include:

Погледајте

Association rule learning
Анализа података
Process mining
Секвенцијална анализа ДНК (Биоинформатика)
Sequence clustering
Sequence labeling
ниска (рачунарство и информатика)
Sequence alignment
Time series

Референце

^ Mabroukeh, Nizar R.; Ezeife, C. I. (2010). „A taxonomy of sequential pattern mining algorithms”. ACM Computing Surveys. 43: 1—41. S2CID 207180619. doi:10.1145/1824795.1824798.
^ Abouelhoda, M.; Ghanem, M. (2010). „String Mining in Bioinformatics”. Ур.: Gaber, M. M. Scientific Data Mining and Knowledge Discovery. Springer. ISBN 978-3-642-02787-1. doi:10.1007/978-3-642-02788-8_9.
^ Han, J.; Cheng, H.; Xin, D.; Yan, X. (2007). „Frequent pattern mining: current status and future directions”. Data Mining and Knowledge Discovery. 15 (1): 55—86. S2CID 8085527. doi:10.1007/s10618-006-0059-1.
^ George, Aloysius; Binu, D. (2012). „DRL-PREFIXSPAN A Novel Pattern Growth Algorithm for Discovering Downturn, Revision and Launch (DRL) Sequential Patterns”. Central European Journal of Computer Science. 2 (4): 426—439. S2CID 6351139. doi:10.2478/s13537-012-0030-8.
^ George, A.; Binu, D. (2013). „An Approach to Products Placement in Supermarkets Using PrefixSpan Algorithm”. Journal of King Saud University-Computer and Information Sciences. 25 (1): 77—87. doi:10.1016/j.jksuci.2012.07.001.
^ Ahmad, Ishtiaq; Qazi, Wajahat M.; Khurshid, Ahmed; Ahmad, Munir; Hoessli, Daniel C.; Khawaja, Iffat; Choudhary, M. Iqbal; Shakoori, Abdul R.; Nasir-ud-Din (1. 5. 2008). „MAPRes: Mining association patterns among preferred amino acid residues in the vicinity of amino acids targeted for post-translational modifications”. Proteomics. 8 (10): 1954—1958. PMID 18491291. S2CID 22362167. doi:10.1002/pmic.200700657.

Литература

Abouelhoda, M.; Ghanem, M. (2010). „String Mining in Bioinformatics”. Ур.: Gaber, M. M. Scientific Data Mining and Knowledge Discovery. Springer. ISBN 978-3-642-02787-1. doi:10.1007/978-3-642-02788-8_9.

Спољашње везе

Имплементација

SPMF, бесплатна платформа отвореног кода за анализирање података, написана у Јави, пружа више од 45 алгоритама за секвенцијално анализирање образаца, секвенцијално анализирање по правилима, анализирање колекција ставки и асоцијативно анализирање по правилима.

[1] Mabroukeh, Nizar R.; Ezeife, C. I. (2010). „A taxonomy of sequential pattern mining algorithms”. ACM Computing Surveys. 43: 1—41. S2CID 207180619. doi:10.1145/1824795.1824798.

[2] Abouelhoda, M.; Ghanem, M. (2010). „String Mining in Bioinformatics”. Ур.: Gaber, M. M. Scientific Data Mining and Knowledge Discovery. Springer. ISBN 978-3-642-02787-1. doi:10.1007/978-3-642-02788-8_9.

[3] Han, J.; Cheng, H.; Xin, D.; Yan, X. (2007). „Frequent pattern mining: current status and future directions”. Data Mining and Knowledge Discovery. 15 (1): 55—86. S2CID 8085527. doi:10.1007/s10618-006-0059-1.

[4] George, Aloysius; Binu, D. (2012). „DRL-PREFIXSPAN A Novel Pattern Growth Algorithm for Discovering Downturn, Revision and Launch (DRL) Sequential Patterns”. Central European Journal of Computer Science. 2 (4): 426—439. S2CID 6351139. doi:10.2478/s13537-012-0030-8.

[5] George, A.; Binu, D. (2013). „An Approach to Products Placement in Supermarkets Using PrefixSpan Algorithm”. Journal of King Saud University-Computer and Information Sciences. 25 (1): 77—87. doi:10.1016/j.jksuci.2012.07.001.

[6] Ahmad, Ishtiaq; Qazi, Wajahat M.; Khurshid, Ahmed; Ahmad, Munir; Hoessli, Daniel C.; Khawaja, Iffat; Choudhary, M. Iqbal; Shakoori, Abdul R.; Nasir-ud-Din (1. 5. 2008). „MAPRes: Mining association patterns among preferred amino acid residues in the vicinity of amino acids targeted for post-translational modifications”. Proteomics. 8 (10): 1954—1958. PMID 18491291. S2CID 22362167. doi:10.1002/pmic.200700657.

[1]

[2]

[3]

[4]

[5]

[6]