Efektywna procedura uzupełnienia funkcji boolowskich i jej zastosowanie w eksploracji danych

• Autorzy: Borowik G. , Kowalski K.

Warianty tytułu

EN

Efficient procedure of Boolean function complementation and its application in data mining

• Języki publikacji: PL

Abstrakty

PL

Podsumowano badania nad algorytmem uzupełnienia funkcji boolowskich. Wskazano rozwiązania, zaproponowane w czasie badan, w tym analizę istniejącej implementacji algorytmu oraz wykorzystane i proponowane sposoby przyśpieszenia obliczeń. Badania zostały zakończone wydajną implementacją współbieżną algorytmu. Wykonano zestawienie czasów obliczeń istniejących systemów analizy i eksploracji danych z autorską implementacją. Wynikiem prac jest łatwo rozszerzalne eksperymentalne oprogramowanie - najszybsze z testowanych rozwiązań i systemów eksploracji danych.

EN

The paper provides three-year research summary related to the Boolean function complement algorithm. It contains computational issues of the algorithm, the analysis of existing implementations, and solutions that have been considered during the research including both proposed and implemented enhancements to reduce the calculation time. As a result of the research new algorithm has been developed that has finally been implemented as efficient concurrent procedure. At last, the computation time comparison of existing data mining systems to the authors' implementation has been shown. These studies have resulted in experimental software that is the most effective of the tested solutions and data mining systems.

Słowa kluczowe

PL

optymalizacja; eksploracja danych; ekstrakcja cech; indukcja reguł; dyskretyzacja; wnioskowanie boolowskie; synteza logiczna

EN

optimization; data mining; feature extraction; rule induction; discretization; Boolean reasoning; logic synthesis

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2015
• Tom: nr 2-3
• Strony: 55--63
• Opis fizyczny: Bibliogr. 23 poz., rys., tab.

Twórcy

autor

Borowik G.

• Instytut Telekomunikacji, Wydział Elektroniki i Technik Informacyjnych Politechniki Warszawskiej

autor

Kowalski K.

• Instytut Telekomunikacji, Wydział Elektroniki i Technik Informacyjnych Politechniki Warszawskiej

Bibliografia

• [1] Bache K., Lichman M. : UCI Machine Learning Repository [http://archrve.ics.uci.edu/ml], Irvine, CA: University of California School of Information and Computer Science, stan z listopada 2013
• [2] Błaszczyński J., Greco S., Matarazzo B., Słowiński R., Szeląg M. : jMAF- Dominance-Based Rough Set Data Analysis Framework, Rough Sets and Intelligent Systems - Professor Zdzisław Pawlak in Memoriam, ser. Intelligent Systems Reference Library, Springer. 2012
• [3] Borowik G. : Boolean Function Complementation Based Algorithm for Data Discretization. Computer Aided Systems Theory - EUROCAST 2013, Lecture Notes in Computer Science, Volume 8112, Springer Berlin Heidelberg 2013
• [4] Borowik G., Kraśniewski A., ŁubaT.: Rule induction based on logic synthesis methods. Progress in Systems Engineering, ser. Advances in Intelligent Systems and Computing, Springer. 2015, DOI: 10.1007/978-3-319-08422-0_118
• [5] Borowik G., Łuba T.: Fast Algorithm of Attribute Reduction Based on the Complementation of Boolean Function. Advanced Methods and Applications in Computational Intelligence, ser .Topics in Intelligent Engineering and Informatics, Springer International Publishing. 2013 DOI: 10.1007/978-3-319-014364 2
• [6] Brayton R.K., Hachtel G.D., McMullen C.T., Sangiovanni-Vincentelli A.: Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers (1984)
• [7] Brzozowski J.A., Łuba T.: Décomposition of boolean functions specified by cubes. Journal of Multi-Valued Logic & Soft Computing 9 (2003)
• [8] GeForce GTX TITAN Z, http://www.nvidia.plgtc-700-graphics-cards/gtx-titan-z/
• [9] Jankowski C., Borowik G., Kowalski K.: Dyskretyzacja danych numerycznych metodami przekształceń boolowskich Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 10, 2014
• [10] Jankowski C., Mańkowski M., Zbierzchowski B.: Zastosowanie eksploracji danych w telekomunikacji. Przegląd Telekomunikacyjny i WiadomościTelekomunikacyjne, nr 10. 2014
• [11] Korzeń M., Jaroszewicz S.: Finding Reducts Without Building the Discernibility Matrix, ISDA, IEEE Computer Society, 2005
• [12] Kornorowski J., Pawlak Z., Polkowski L., Skowron A. Rough sets: A tutorial (1999)
• [13] Liu H., Hussain F., Tan Ch. L. Dash M.: Discretization: An Enabling Technique, Data Mining and Knowledge Discovery, vol. 6, 2002
• [14] Liu H., Setiono R.: Feature selection via discretization, IEEE Transactions on Knowledge and Data Engineering, vol. 9, no. 4,1997
• [15] Łuba T., Borowik G., Kowalski K., Pecio P., Jankowski C., Mańkowski M.: Rola i znaczenie syntezy logiczne, w eksploracji danych dla potrzeb telekomunikacji i medycyny. Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne nr 5/2014
• [16] ŁubaT., Borowik G., KraśniewskiA., Rutkowski P., Ługowska I.: Application of logic synthesis algorithms for data mining in medical databases. Ninth International Seminar on Statistics and Clinical Practice, Warsaw Poland June 1-4,2014.
• [17] Mańkowski M., Łuba T., Borowik G., Jankowski C. : Indukcja reguł decyzyjnych z dwustopniowym procesem selekcji reguł. Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 7, 2014
• [18] Nguyen H.S.: Approximate Boolean Reasoning Foundations and Applications in Data Mining, Lecture Notes in Computer Science Volume 4100, 2006
• [19] Papadimitriou C.H. : Computational complexity Academic Internet Publ. (2007).
• [20] ROSE2 - Rough Sets Data Explorer, http://idss.cs-put.poznan.pl/site/rose.html
• [21] RSES 2.2 - Rough Set Exploration System 2.2, http://logic.mimuw.edu.pl/rses/
• [22] Steinbach B., Posthoff C.: Improvements of the Construction of Exact Minimal Covers of Boolean Functions, Computer Aided Systems Theory EURO-CAST 2011, Lecture Notes in Computer Science Volume 6928, 2012
• [23] Steinbach B., Posthoff C.: Fast Calculation of Exact Minimal Unate Coverings on Both the CPU and the GPU. Computer Aided Systems Theory – EURO-CAST 2013, Lecture Notes in Computer Science Volume 8112, Springer Berlin Heidelberg, 2013