PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 10

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Greedy Algorithm with Weights for Decision Tree Construction
Moshkov M.Ju.
Fundamenta Informaticae
|
2010
|
Vol. 104, nr 3
285-292
EN
An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.
2
Content available remote On Minimal Inhibitory Rules for Almost All k-Valued Information Systems
Moshkov M.Ju., Skowron A., Suraj Z.
Fundamenta Informaticae
|
2009
|
Vol. 93, nr 1-3
261-272
EN
The minimal inhibitory rules for information systems can be used for construction of classifiers. We show that almost all information systems from a certain large class of information systems have relatively short minimal inhibitory rules. However, the number of such rules is not polynomial in the number of attributes and the number of objects. This class consists of all k-valued information systems, k ≥ 2, with the number of objects polynomial in the number of attributes. Hence, for efficient construction of classifiers some filtration techniques in rule generation are necessary. Another way is to work with lazy classification algorithms based on inhibitory rules.
3
Content available remote Greedy Algorithms with Weights for Construction of Partial Association Rules
Moshkov M.Ju., Piliszczuk M., Zielosko B.
Fundamenta Informaticae
|
2009
|
Vol. 94, nr 1
101-120
EN
This paper is devoted to the study of approximate algorithms for minimization of the total weight of attributes occurring in partial association rules. We consider mainly greedy algorithms with weights for construction of rules. The paper contains bounds on precision of these algorithms and bounds on the minimal weight of partial association rules based on an information obtained during the greedy algorithm run.
4
Content available remote Greedy Algorithm for Construction of Partial Association Rules
Moshkov M.Ju., Piliszczuk M.
Fundamenta Informaticae
|
2009
|
Vol. 92, nr 3
259-277
EN
Partial association rules can be used for representation of knowledge, for inference in expert systems, for construction of classifiers, and for filling missing values of attributes. This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during the greedy algorithm work, and results of theoretical and experimental study of association rules for the most part of binary information systems.
5
Content available remote On Minimal Rule Sets for Almost All Binary Information Systems
Moshkov M.Ju., Skowron A., Suraj Z.
Fundamenta Informaticae
|
2007
|
Vol. 80, nr 1-3
247-258
EN
The minimal rules for information systems are often used for inducing data models by methods in which the optimization of models is based on the minimal length principle. We show that almost all information systems from a certain large class of information systems have relatively short minimal rules. However, the number of such rules is not polynomial in the number of attributes and the number of objects. This class consists of all binary information systems with the number of objects polynomial in the number of attributes. Hence, for efficient inducing data models some filtration techniques in rule generation are necessary. In our further study we would like to extend our results for arbitrary information systems.
6
Content available remote On Construction of Partial Reducts and Irreducible Partial Decision Rules
Moshkov M.Ju., Piliszczuk M., Zielosko B.
Fundamenta Informaticae
|
2007
|
Vol. 75, nr 1-4
357-374
EN
In the paper for the most part of binary decision tables upper and lower bounds on the cardinality of partial reducts and length of irreducible partial decision rules are obtained. The number of partial reducts and the number of irreducible partial decision rules are evaluated. Complexity of algorithms for construction of all partial reducts and all irreducible partial decision rules is studied on the basis of obtained bounds.
7
Content available remote Consecutive Optimization of Decision Trees Concerning Various Complexity Measures
Moshkov M.Ju., Chikalov I.V.
Fundamenta Informaticae
|
2004
|
Vol. 61, nr 2
87--96
EN
In the paper algorithms are considered which allow to optimize decision trees consecutively againsts relatively different criterions. For decision tables over an arbitrary infinite restricted information system [4], these algorithms have polynomial time complexity.
8
Content available remote Compressible Infinite Information Systems
Moshkov M.Ju.
Fundamenta Informaticae
|
2003
|
Vol. 55, nr 1
51-61
EN
We investigate infinite information systems. Such systems are widely used in pattern recognition, data mining, discrete optimization, computational geometry. An information system is called compressible relatively to a given weight function if for each problem over the information system with sufficiently large weight (i.e., total weight of attributes in the problem description) there exists a decision tree (i) solving this problem and (ii) having the weighted depth less than the problem weight. In the paper all pairs (information system, weight function) such that the information system is compressible relatively to the weight function are described. For each such pair the behavior of Shannon type function is investigated characterizing the growth in the worst case of the minimal weighted depth of decision trees with the growth of problem weight.
9
Content available remote Classification of Infinite Information Systems Depending on Complexity of Decision Trees and Decision Rule Systems
Moshkov M.Ju.
Fundamenta Informaticae
|
2003
|
Vol. 54, nr 4
345-368
EN
In this paper, infinite information systems used in pattern recognition, data mining, discrete optimization, and computational geometry are investigated. Time and space complexity of decision trees and complete decision rule systems are studied. A partition of the set of all infinite information systems into two classes is considered. Information systems from the first class are close to the best from the point of view of time and space complexity of decision trees and decision rule systems. Decision trees and decision rule systems for information systems from the second class have in the worst case large time or space complexity.
10
Content available remote On Decision Trees for (1,2)-Bayesian Networks
Moshkov M.Ju.
Fundamenta Informaticae
|
2002
|
Vol. 50, nr 1
57-76
EN
Bayesian Networks (BN) are convenient tool for representation of probability distribution of variables. We study time complexity of decision trees which compute values of all observable variables from BN. We consider (1,2)-BN in which each node has at most 1 entering edge, and each variable has at most 2 values. For an arbitrary (1,2)-BN we obtain lower and upper bounds on minimal depth of decision tree that differ not more than by a factor of 4, and can be computed by an algorithm which has polynomial time complexity. The number of nodes in considered decision trees can grow as exponential on number of observable variables in BN. We develop an polynomial algorithm for simulation of the work of decision trees which depth lies between the obtained bounds.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.