Математичне та програмне забезпечення виявлення кон’юнктивних асоціативних залежностей у великих масивах даних

Abstract

У дисертаційній роботі розв’язано актуальну науково-практичну задачу виявлення асоціативних залежностей у великих масивах даних з метою підвищення якості процесів підтримки прийняття рішень. Проаналізовано сучасні методи та засоби аналізу даних на предмет наявності кореляцій, асоціацій та іншого роду залежностей між атрибутами. Виявлено головні проблеми та обмеження існуючих методів. Здійснено формальну постановку задачі виявлення залежностей у даних. Розроблено метод пошуку асоціативних правил, у яких умовна та результуюча частини є предикатами в кон’юнктивній нормальній формі, у реляційних відношеннях. Для ефективної побудови агрегованих асоціативних правил введено набір операторів та визначено правила виведення залежностей. Проведено оцінку асимптотичної складності розробленого алгоритму по часу та по пам’яті. Проведено порівняння розробленого методу із відомими аналогами. Спроектовано систему аналізу даних, що реалізовує розроблений метод. Результати досліджень використано при проведенні аналізу даних різних предметних областей для українських та зарубіжних компаній. This thesis solves a major scientific problem of associative dependencies detection in large data volumes in order to increase the quality of decision making support processes. The first chapter describes modern methods of data dependency detection, their pros and cons, fields of application and restrictions. It analyzes possibilities of usage of each method for various data structures and volumes, finds out common problems and needs in the field of data dependency detection. General issues with methods, available nowadays are high computation complexity, narrow field of application, data errors handling and the need of intense human interaction with data analysis system. The second chapter introduces formal model of data dependency, provides data attributes classification and describes the theoretical basis for operating with special subtype of associative dependencies – conjunctive associative dependencies (CAD) – those ones which have conditional and result predicates represented in conjunctive normal form. Operation set on CAD is introduced in this chapter for expressing dependency aggregation rules set and proving its completeness. Based on it, a conjunctive associative data dependency detection method is described. Dependency aggregation rules provide the ability to reduce algorithm complexity owing to the ability to detect only elementary associative dependencies in the original data storage and then perform dependency aggregation, obtaining full set of CADs which meet the criteria, specified by user of data analysis system. The criteria may include any or all of the following characteristics: support level, confidence level, improvement level, full mutual information and any custom user-defined criteria based on previous ones. This gives great flexibility in specifying searched dependencies criteria. In the third chapter CAD detection algorithm is described. Algorithm has three stages: building data statistics tree, aggregation elementary dependencies, and building multi-attribute dependencies. Asymptotic complexity of algorithm is proven to be polynomial depending on the size of input dataset. It can scale linearly in case of selection constant support level criteria. Chapter also shows comparison of the developed method with few analogues by quality and quantitative characteristics. It indicates that the developed method is not dominated by any other data analysis methods and has high performance and low algorithm complexity. That allows using this method in a wide range of scientific branches which collects large data volumes. The fourth chapter describes the architecture of CAD detection system and scheme of its internal databases. It allows using the developed method with various structure data sources, distributed databases, enables administrator to control the analysis process. Architecture is durable and failure-resistant. It is also capable working with multiple clients and performing few data analysis tasks simultaneously. This chapter also lists results of the developed system application in a bunch of knowledge branches such as data analysis of pancreatitis disease statistics, driver license and vehicle audit, legal documentation accounting and portal of online football game and the achieved gains in those areas. В диссертационной работе решена актуальная научно-практическая задача выявления ассоциативных зависимостей в больших массивах данных с целью повышения качества процессов поддержки принятия решений. Проанализированы современные методы и средства анализа данных на предмет наличия корреляций, ассоциаций и другого рода зависимостей между атрибутами. Выявлены основные проблемы и ограничения существующих методов. Осуществлена формальная постановка задачи выявления зависимостей в данных. Разработан метод поиска ассоциативных правил, в которых условная и результирующая части являются предикатами в конъюнктивный нормальной форме. Для эффективного построения агрегированных ассоциативных правил введено набор операторов и определены правила вывода зависимостей. Проведена оценка асимптотической сложности разработанного алгоритма по времени и по памяти. Проведено сравнение разработанного метода с известными аналогами. Спроектирована система анализа данных, реализующая разработанный метод. Результаты исследований использованы при проведении анализа данных различных предметных областей для украинских и зарубежных компаний.