?
Turning Krimp into a Triclustering Technique on Sets of Attribute-Condition Pairs that Compress
P. 558–569.
Ignatov D. I., Yurov M.
Mining ternary relations or triadic Boolean tensors is one of the recent trends in knowledge discovery that allows one to take into account various modalities of input object-attribute data. For example, in movie databases like IMBD, an analyst may find not only movies grouped by specific genres but see their common keywords. In the so-called folksonomies, users can be grouped according to their shared resources and used tags. In gene expression analysis, genes can be grouped along with samples of tissues and time intervals providing comprehensible patterns. However, pattern explosion effects even with one more dimension are seriously aggravated. In this paper, we continue our previous study on searching for a smaller collection of “optimal” patterns in triadic data with respect to a set of quality criteria such as patterns’ cardinality, density, diversity, coverage, etc. We show how a simple data preprocessing has enabled us to use the frequent itemset mining algorithm Krimp based on MDL-principle for triclustering purposes.
Keywords: трикластеризацияItemsets that compressпринцип наименьшей длины описаниячастые закономерности Triclustering MDL principle Frequent patternsсжимающие множества признаков
Publication based on the results of:
In book
Vol. 10314. , Springer, 2017.
Ignatov D. I., Иванова П., Замалетдинова А., , in: Network Algorithms, Data Mining, and Applications. Springer Proceedings in Mathematics & StatisticsVol. 315.: Springer, 2020. Ch. 2 P. 19–35.
This paper is related to the problem of finding the maximal quasi-bicliques in a bipartite graph (bigraph). A quasi-biclique in the bigraph is its “almost” complete subgraph. The relaxation of completeness can be understood variously; here, we assume that the subgraph is a \(\gamma \)-quasi-biclique if it lacks a certain number of edges to form ...
Added: February 22, 2020
Ignatov D. I., Ivanova P., Zamaletdinova A. et al., , in: Supplementary Proceedings ICFCA 2019 Conference and WorkshopsVol. 2378.: CEUR Workshop Proceedings, 2019. P. 28–32.
This short paper is related to the problem of finding maximum quasi-bicliques in a bipartite graph (bigraph). A quasi-biclique in a bigraph is its “almost” complete subgraph; here, we assume that the subgraph is a quasi-biclique if it lacks γ · 100% of the edges to become a biclique. The problem of finding the maximal ...
Added: October 31, 2019
Ignatov D. I., Semenov A., Комиссарова Д. В. et al., , in: Formal Concept Analysis of Social Networks.: Springer, 2017. Ch. 4 P. 59–96.
Multimodal clustering is an unsupervised technique for mining interesting patterns in n-ary relations or n-mode networks. Among different types of such generalised patterns one can find biclusters and formal concepts (maximal bicliques) for two-mode case, triclusters and triconcepts for three-mode case, closed n-sets for n-mode case, etc. Object-attribute biclustering (OA-biclustering) for mining large binary datatables (formal contexts or two-mode ...
Added: December 17, 2017
Зудин С., Gnatyshak D. V., Ignatov D. I., , in: Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications Clermont-Ferrand, France, October 13-16, 2015Vol. 1466.: Clermont-Ferrand: CEUR Workshop Proceedings, 2015. P. 47–58.
In our previous work an efficient one-pass online algorithm
for triclustering of binary data (triadic formal contexts) was proposed.
This algorithm is a modified version of the basic algorithm for OAC-triclustering
approach; it has linear time and memory complexities. In
this paper we parallelise it via map-reduce framework in order to make
it suitable for big datasets. The results of ...
Added: October 23, 2015
Ignatov D. I., Gnatyshak D. V., Sergei O. Kuznetsov et al., Machine Learning 2015 Vol. 101 No. 1 P. 271–302
This paper presents several definitions of “optimal patterns” in triadic data and results of experimental comparison of five triclustering algorithms on real-world and synthetic datasets. The evaluation is carried over such criteria as resource efficiency, noise tolerance and quality scores involving cardinality, density, coverage, and diversity of the patterns. An ideal triadic pattern is a totally dense ...
Added: April 15, 2015
Гнатышак Д. В., Научно-техническая информация. Серия 2: Информационные процессы и системы 2015 № 2 С. 16–30
В связи с продолжающимся ростом популярности области больших данных все более активно ставится вопрос о создании эффективных алгоритмов с низкой временной сложностью и возможностью параллелизации. Целью данной работы было создание эффективного однопроходного алгоритма трикластеризации бинарных данных, пригодного для использования в области больших данных. В результате был получен однопроходный линейный онлайн-алгоритм OAC-трикластеризации (трикластеризации объект-признак-условие). Помимо того, ...
Added: April 15, 2015
Kashnitsky Y., В кн.: Труды Международной конференции по физико-технической информатике CPT-2013, 12-19 мая 2013 г., Ларнака, Республика Кипр.: М., Протвино: Изд-во ИФТИ, 2013. С. 251–258.
Triclustering is an outgrowth of Formal Concept Analysis intented to detect groups of objects with similar properties (clusters) in a context of three sets of entities. In case of social network analysis,
for instance, these sets might be users, their interests and events they take part in. Triclustering here can help to detect users with similar ...
Added: January 27, 2014
Kashnitsky Y., Труды Московского физико-технического института 2014 Т. 6 № 3 С. 43–56
Triclustering is an outgrowth of Formal Concept Analysis intented to detect groups of objects with similar properties (clusters) in a context of three sets of entities. In case of social network analysis, for instance, these sets might be users, their interests and events they take part in. Triclustering here can help to detect users with ...
Added: November 8, 2013
Ignatov D. I., Kuznetsov S., Zhukov L. E. et al., International Journal of General Systems 2013 Vol. 42 No. 6 P. 572–593
formal concept analysis,
data mining,
triclustering,
three-way data,
folksonomy,
spectral triclustering ...
Added: October 16, 2013
Ignatov D. I., Magizov R. A., В кн.: Социологические методы в современной исследовательской практике: Сборник статей, посвященный памяти первого декана факультета социологии НИУ ВШЭ А.О. Крыштановского [Электронный ресурс].: М.: Издательский дом НИУ ВШЭ, 2011. С. 315–322.
В работе представлен оригинальный метод трикластеризации, который использовался для поиска «плотных» троек вида (посетители, тэги, ресурсы) при анализе данных сервиса социальных закладок Bibsonomy. Предложенный метод является универсальным для анализа любых тримодальных данных, описываемых тернарными отношениями, и служит вычислительно эффективной альтернативой поиску трипонятий (в смысле анализа формальных понятий) и построению айсбергов трирешёток. ...
Added: August 30, 2013
Секинаева З. Р., Ignatov D. I., В кн.: Анализ изображений, сетей и текстов. Доклады всероссийской научной конференции АИСТ'12. Модели, алгоритмы и инструменты анализа данных; результаты и возможности для анализа изображений, сетей и текстов. Екатеринбург, 16 – 18 марта 2012 годаВып. 1.: М.: Национальный открытый университет «ИНТУИТ», 2012. С. 246–254.
Статья посвящена разработке метода трикластеризации на основе графовой спектральной кластеризации. В серии экспериментов на реальных данных исследована эффективность и пригодность метода к анализу данных систем совместного пользования ресурсами, т.н. фолксономий ...
Added: January 30, 2013
Ignatov D. I., Kuznetsov S., Poelmans J., В кн.: Математические методы распознавания образов: 15-я Всероссийская конференция, г.Петрозаводск, 11–17 сентября 2011 г.: Сборник докладов.: М.: МАКС Пресс, 2012. С. 258–261.
В работе предложен новый подход к трикластеризации трехмерных бинарных данных. Трикластер определен в терминах триадического анализа формальных понятий (Triadic Formal Concept Analysis) как плотное тримножество тернарного отношения Y между объектами, признаками и условиями. Такое определение является ослаблением определения трипонятия и дает возможность найти все трикластеры и трипонятия, содержащиеся в трикластерах больших наборов данных. Данный подход ...
Added: December 4, 2012
Ignatov D. I., Kuznetsov S., Zhukov L. E., , in: Rough Sets, Fuzzy Sets, Data Mining and Granular Computing: 13th International Conference, RSFDGrC 2011, Moscow, Russia, June 25-27, 2011. ProceedingsVol. 6743.: Berlin, Heidelberg: Springer, 2011. P. 257–264.
A novel approach to triclustering of a three-way binary data is proposed. Tricluster is defined in terms of Triadic Formal Concept Analysis as a dense triset of a binary relation Y , describing relationship between objects, attributes and conditions. This definition is a relaxation of a triconcept notion and makes it possible to find all ...
Added: December 3, 2012
Gnatyshak D. V., Ignatov D. I., Semenov A. et al., , in: Perspectives in Business Informatics Research. 11th International Conference, BIR 2012, Nizhny Novgorod, Russia, September 2012 ProceedingsIssue 128.: Berlin, Heidelberg: Springer, 2012. P. 162–171.
We combine bi- and triclustering to analyse data collected from the Russian online social network Vkontakte. Using biclustering we extract groups of users with similar interests and find communities of users which belong to similar groups. With triclustering we reveal users' interests as tags and use them to describe Vkontakte groups. After this social tagging ...
Added: December 3, 2012
Gnatyshak D. V., Ignatov D. I., Semenov A. et al., , in: Concept Discovery in Unstructured Data. 2nd International Workshop, CDUD 2012, Leuven, Belgium, May 2012, ProceedingsIssue 871.: Leuven: Katholieke Universiteit Leuven, 2012. P. 30–39.
In this paper we propose two novel methods for analyzing data collected from online social networks. In particular we will do analyses on Vkontake data (Russian online social network). Using biclustering we extract groups of users with similar interests and find communities of users which belong to similar groups. With triclustering we reveal users’ interests ...
Added: November 20, 2012
Gnatyshak D. V., Ignatov D. I., Kuznetsov S. et al., В кн.: Тринадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2012 (16-20 октября 2012 г., г. Белгород, Россия). Том 2Т. 2.: Белгород: Белгородский государственный технологический университет им. В.Г. Шухова, 2012. С. 66–73.
В этой работе предлагается новый метод для анализа данных онлайновых социальных сетей. В частности, проанализированы данные сайта Вконтакте. Используя бикластеризацию выявлены группы пользователей со схожими интересами и сообщества пользователей принадлежащих сходным группам. Предпринята попытка использовать интересы пользователей как теги, для того чтобы описывать группы сети Вконтакте. ...
Added: November 20, 2012