检索结果-内蒙古大学图书馆

Revisiting data reduction for boolean matrix factorization algorithms based on formal concept analysis

INTERNATIONAL JOURNAL OF MACHINE LEARNING AND CYBERNETICS 2025年第1期16卷 419-447页

作者： Yang, Lanzhen Tsang, Eric C. C. Mao, Hua Zhang, Chengling Wu, Jiaming Macau Univ Sci & Technol Sch Comp Sci & Engn Taipa Macao Peoples R China Hebei Univ Coll Math & Informat Sci Baoding 071002 Peoples R China

boolean matrix factorization (BMF) helps unveil hidden patterns in boolean datasets and is a powerful tool in machine learning. However, when dealing with large datasets, reducing data size becomes crucial for BMF algorithms. In this paper, we revisit and propose novel data reduction approaches for BMF algorithms based on Formal Concept Analysis (FCA), aiming to minimize the impact of data reduction on factor quality. Specifically, we introduce the concept of intent vectors , and present incremental algorithms along with their associated theorems for capturing and quantifying these vectors, thereby facilitating a reduction in data size. More importantly, we propose two innovative approaches based on FCA principles that effectively identify and eliminate redundant rows in datasets through distinct deletion strategies. The first approach incrementally deletes rows while preserving the intent vectors of attribute concepts, thus maintaining the quality of factors. The second approach progressively removes rows from the reduced dataset by the first approach, by gradually adjusting the amount of concept loss to minimize any degradation in factor quality. Experiments demonstrate that our first reduction algorithm significantly decreases data size without degrading factor quality, consistently outperforming current leading algorithms with a 100%\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$100\%$$\end{document} success rate. Our second algorithm outperformed the existing algorithm in 72 out of 96 comparisons, greatly reducing data size with minimal loss in factor quality.

关键词： Formal concept boolean matrix factorization Intent vector Data reduction Factor

来源：评论

学校读者我要写书评

暂无评论

boolean matrix factorization based on collaborative neurodynamic optimization with Boltzmann machines

引用

NEURAL NETWORKS 2022年 153卷 142-151页

作者： Li, Xinqi Wang, Jun Kwong, Sam Univ Exeter Dept Comp Sci Exeter England City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China City Univ Hong Kong Sch Data Sci Kowloon Hong Kong Peoples R China

This paper presents a collaborative neurodynamic approach to boolean matrix factorization. Based on a binary optimization formulation to minimize the Hamming distance between a given data matrix and its low-rank reconstruction, the proposed approach employs a population of Boltzmann machines operating concurrently for scatter search of factorization solutions. In addition, a particle swarm optimization rule is used to re-initialize the neuronal states of Boltzmann machines upon their local convergence to escape from local minima toward global solutions. Experimental results demonstrate the superior convergence and performance of the proposed approach against six baseline methods on ten benchmark datasets. (c) 2022 Elsevier Ltd. All rights reserved.

关键词： boolean matrix factorization Collaborative neurodynamic optimization Boltzmann machines

来源：评论

学校读者我要写书评

暂无评论

boolean matrix factorization via Nonnegative Auxiliary Optimization

引用

IEEE ACCESS 2021年 9卷 117169-117177页

作者： Truong, Duc P. Skau, Erik Desantis, Derek Alexandrov, Boian Los Alamos Natl Lab Comp Computat & Stat Div Los Alamos NM 87545 USA Los Alamos Natl Lab Theoret Div Los Alamos NM 87545 USA Los Alamos Natl Lab Ctr Nonlinear Studies Los Alamos NM 87545 USA

A novel approach to boolean matrix factorization (BMF) is presented. Instead of solving the BMF problem directly, this approach solves a nonnegative optimization problem with an additional constraint over an auxiliary matrix whose boolean structure is identical to the initial boolean data. This additional auxiliary matrix constraint forces the support of the NMF solution to adhere to that of a BMF solution. The solution of the nonnegative auxiliary optimization problem is thresholded to provide a solution for the BMF problem. We provide the proofs for the equivalencies of the two solution spaces under the existence of an exact solution. Moreover, the nonincreasing property of the algorithm is also proven. Experiments on synthetic and real datasets are conducted to show the effectiveness and complexity of the algorithm compared to other current methods.

关键词： Optimization matrix decomposition Approximation algorithms Feature extraction Licenses Probabilistic logic Greedy algorithms boolean matrix factorization nonnegative matrix factorization

来源：评论

学校读者我要写书评

暂无评论

From-below boolean matrix factorization algorithm based on MDL

引用

ADVANCES IN DATA ANALYSIS AND CLASSIFICATION 2021年第1期15卷 37-56页

作者： Makhalova, Tatiana Trnecka, Martin Natl Res Univ Higher Sch Econ Moscow Russia Univ Lorraine INRIA CNRS LORIA Vanduoevre Les Nancy France Palacky Univ Olomouc Dept Comp Sci Olomouc Czech Republic

During the past few years boolean matrix factorization (BMF) has become an important direction in data analysis. The minimum description length principle (MDL) was successfully adapted in BMF for the model order selection. Nevertheless, a BMF algorithm performing good results w.r.t. standard measures in BMF is missing. In this paper, we propose a novel from-below boolean matrix factorization algorithm based on formal concept analysis. The algorithm utilizes the MDL principle as a criterion for the factor selection. On various experiments we show that the proposed algorithm outperforms-from different standpoints-existing state-of-the-art BMF algorithms.

关键词： boolean matrix factorization Minimum description length factorization quality Formal concept analysis

来源：评论

学校读者我要写书评

暂无评论

Handling noise in boolean matrix factorization

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2018年 96卷 78-94页

作者： Belohlavek, Radim Trnecka, Martin Palacky Univ Olomouc Dept Comp Sci Olomouc Czech Republic

One of the challenges presented by boolean matrix factorization consists in what became known as the ability to deal with noise in data. In this paper, we critically examine existing considerations regarding noise, reported results regarding various algorithms' ability to deal with noise, and approaches used to evaluate this ability. We argue that the current understanding is underdeveloped in several respects and, in particular, that the present way to assess the ability to handle noise in data is deficient. We provide a new, quantitative way to assess this ability. Our method is based on a common-sense definition of robustness requiring that the factorizations computed from data should not be affected much by varying the noise in the data. We present an experimental evaluation of several algorithms, and compare the results to the observations available in the literature. The experiments reveal important properties of these algorithms as regards handling noise. In addition to providing methodological justification of some properties claimed in the literature without proper justification, they reveal properties which were not reported as well as properties which counter certain claims made in the literature. Importantly, our approach reveals a line separating robust-to-noise from sensitive-to-noise algorithms, which has not been revealed by the previous approaches. We conclude by outlining open problems to which the present considerations and experiments lead. (C) 2018 Elsevier Inc. All rights reserved.

关键词： boolean matrix factorization Algorithms Noise in boolean data

来源：评论

学校读者我要写书评

暂无评论

MDL4BMF: Minimum Description Length for boolean matrix factorization

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2014年第4期8卷 1–31页

作者： Miettinen, Pauli Vreeken, Jilles Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Saarland D-66123 Saarbrucken Germany Univ Antwerp Dept Wiskunde & Informat B-2020 Antwerp Belgium

matrix factorizations-where a given data matrix is approximated by a product of two or more factor matrices-are powerful data mining tools. Among other tasks, matrix factorizations are often used to separate global structure from noise. This, however, requires solving the "model order selection problem" of determining the proper rank of the factorization, that is, to answer where fine-grained structure stops, and where noise starts. boolean matrix factorization (BMF)-where data, factors, and matrix product are boolean-has in recent years received increased attention from the data mining community. The technique has desirable properties, such as high interpretability and natural sparsity. Yet, so far no method for selecting the correct model order for BMF has been available. In this article, we propose the use of the Minimum Description Length (MDL) principle for this task. Besides solving the problem, this well-founded approach has numerous benefits;for example, it is automatic, does not require a likelihood function, is fast, and, as experiments show, is highly accurate. We formulate the description length function for BMF in general-making it applicable for any BMF algorithm. We discuss how to construct an appropriate encoding: starting from a simple and intuitive approach, we arrive at a highly efficient data-to-model-based encoding for BMF. We extend an existing algorithm for BMF to use MDL to identify the best boolean matrix factorization, analyze the complexity of the problem, and perform an extensive experimental evaluation to study its behavior.

关键词： boolean matrix factorization model order selection model selection boolean rank pattern sets summarization minimum description length principle MDL parameter free

来源：评论

学校读者我要写书评

暂无评论

Data Reduction for boolean matrix factorization Algorithms Based on Formal Concept Analysis

引用

KNOWLEDGE-BASED SYSTEMS 2018年 158卷 75-80页

作者： Trnecka, Martin Trneckova, Marketa Palacky Univ Dept Comp Sci Olomouc Czech Republic

Data size reduction is an important step in many data mining techniques. We present a novel approach based on formal concept analysis to data reduction tailored for boolean matrix factorization methods. A general aim of these methods is to find factors that exactly or approximately explain data. The presented approach is able to significantly reduce the size of data by choosing a representative set of rows, and preserve (with a little loss) factors behind the data, i.e. it only slightly affects a quality of the factors produced by boolean matrix factorization algorithms.

关键词： boolean matrix factorization Formal concept analysis Data reduction

来源：评论

学校读者我要写书评

暂无评论

A new algorithm for boolean matrix factorization which admits overcovering

引用

DISCRETE APPLIED MATHEMATICS 2018年 249卷 36-52页

作者： Belohlavek, Radim Trnecka, Martin Palacky Univ Dept Comp Sci Olomouc Czech Republic

We present a new algorithm for general boolean matrix factorization. The algorithm is based on two key ideas. First, it utilizes formal concepts of the factorized matrix as crucial components of constructed factors. Second, it performs steps back during the construction of factors to see if some of the already constructed factors may be improved or even eliminated in view of the subsequently added factors. The second idea is inspired by 8M-an old, previously incompletely described and virtually unknown factorization algorithm, which we analyze and describe in detail. We provide experimental evaluation of the new algorithm and compare it to 8M and two other well-known algorithms. The results demonstrate that our algorithm outperforms these algorithms in terms of quality of the decompositions as well in its robustness with respect to small changes in data. (C) 2018 Elsevier B.V. All rights reserved.

关键词： boolean matrix factorization Formal concept analysis Algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel exploration of partial solutions in boolean matrix factorization

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2019年 123卷 180-191页

作者： Outrata, Jan Trnecka, Martin Palacky Univ Olomouc Dept Comp Sci 17 Listopadu 12 CZ-77146 Olomouc Czech Republic

boolean matrix factorization (BMF) is a well established method for preprocessing and analysis of data. There is a number of algorithms for BMF, but none of them uses benefits of parallelization. This is mainly due to the fact that many of the algorithms utilize greedy heuristics that are inherently sequential. In this work, we propose a general parallelization scheme for BMF in which several locally optimal partial matrix decompositions are constructed simultaneously in parallel, instead of just one in a sequential algorithm. As a result of the computation, either the single best final decomposition or several top-k of them may be returned. The scheme can be applied to any sequential heuristic BMF algorithm and we show the application on two representative algorithms, namely GRECoND and Asso. Improvements in decompositions are presented via results from experiments with the new algorithms on synthetic and real datasets. (C) 2018 Elsevier Inc. All rights reserved. .

关键词： boolean matrix factorization Parallel algorithm Data preprocessing

来源：评论

学校读者我要写书评

暂无评论

Data-driven Q-matrix learning based on boolean matrix factorization in cognitive diagnostic assessment

引用

BRITISH JOURNAL OF MATHEMATICAL & STATISTICAL PSYCHOLOGY 2022年第3期75卷 638-667页

作者： Xiong, Jianhua Luo, Zhaosheng Luo, Guanzhong Yu, Xiaofeng Jiangxi Normal Univ Sch Psychol 99 Ziyang Ave Nanchang 330022 Jiangxi Peoples R China Jiangxi Normal Univ Sch Comp & Informat Engn Nanchang Jiangxi Peoples R China

Attributes and the Q-matrix are the central components for cognitive diagnostic assessment, and are usually defined by domain experts. However, it is challenging and time consuming for experts to specify the attributes and Q-matrix manually. Thus, there is an urgent need for an automatic and intelligent means to address this concern. This paper presents a new data-driven approach for learning the Q-matrix from response data. By constructing a statistical index and a heuristic algorithm based on boolean matrix factorization, the response matrix is decomposed into the boolean product of the Q-matrix and the attribute mastery patterns. The feasibility of the proposed approach is evaluated using simulated data generated under various conditions. A real data example is also presented to demonstrate the usefulness of the proposed approach.

关键词： attribute mastery pattern boolean matrix factorization cognitive diagnostic assessment DINA model Q-matrix

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：