Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
International Journal of Machine Learning and Cybernetics
Published in: International Journal of Machine Learning and Cybernetics 6/2014

01-12-2014 | Original Article

Conditions for coverings to induce matroids

Authors: Jingqian Wang, William Zhu, Fei-Yue Wang, Guilong Liu

Published in: International Journal of Machine Learning and Cybernetics | Issue 6/2014

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Coverings are a useful form of data structure, and covering-based rough sets provide an effective tool to cope with this type of data. However, many important problems such as covering reduction in covering-based rough sets are NP-hard, so that most algorithms to solve them are greedy ones. Matroids, as a generalization of the linear independence in vector spaces, provide well-established platforms for greedy algorithms. Therefore, it is necessary to integrate covering-based rough sets and matroids. In this paper, we present conditions for coverings to induce matroids. Firstly, some conditions under which the minimal set of a covering satisfies the circuit axiom of matroids are presented through three sides, which are coverings, matroids and neighborhoods, then a matroid is induced by the covering. Secondly, two conditions under which two different coverings can induce the same matroid are studied. Finally, two sufficient and necessary conditions for a neighborhood covering to induce an Eulerian matroid are investigated, where the neighborhood covering is a family of all neighborhoods. In a word, these results show an interesting view to investigate the combination between covering-based rough sets and matroids.
previous article Retina based biometric authentication using phase congruency
next article Secondary basis unique augmentation matroids and union minimal matroids

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Show more products
Literature
1.
2.
3.
Chen D, Wang C, Hu Q (2007) A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets. Inf Sci 177:3500–3518CrossRefMATH
4.
Chen Y, Miao D, Wang R, Wu K (2011) A rough set approach to feature selection based on power set tree. Knowl Based Syst 24:275–281CrossRef
5.
6.
Dai J, LI Y, Liu Q (2002) A hybrid genetical gorithm for reduct of attributes in decision system based on rough set theory. Wuhan Univ J Nat Sci 7:285–289CrossRef
7.
Dai J, Wang W, Tian H, Liu L (2013) Attribute selection based on a new conditional entropy for incomplete decision systems. Knowl Based Syst 39:207–213CrossRef
8.
9.
Du Y, Hu Q, Zhu P, Ma P (2011) Rule learning for classification based on neighborhood covering reduction. Inf Sci 181:5457–5467CrossRefMathSciNet
10.
Dougherty R, Freiling C, Zeger K (2007) Networks, matroids, and non-shannon information inequalities. IEEE Trans Inf Theory 53:1949–1969CrossRefMATHMathSciNet
11.
12.
Fan N, Hu G, Xiao X, Zhang W (2012) Study on conditions of neighborhoods forming a partition. In: International Conference on Fuzzy Systems and Knowledge Discovery, pp 256–259
13.
14.
Jia X, Liao W, Tang Z, Shang L (2013) Minimum cost attribute reduction in decision-theoretic rough set models. Inf Sci 219:151–167CrossRefMATHMathSciNet
15.
Johnson JA, Liu M, Chen H (2000) Unification of knowledge discovery and data mining using rough sets approach in a real-world application. In: Rough Sets and Current Trends in Computing. Volume 2005 of LNCS. pp 330–337
16.
Kondo M (2005) On the structure of generalized rough sets. Inf Sci 176:589–600CrossRef
17.
Lai H (2001) Matroid theory. Higher Education Press, Beijing
18.
Lawler E (2001) Combinatorial optimization: networks and matroids. Dover Publications, Mineola, NY
19.
Li J (2004) Topological methods on the theory of covering generalized rough sets. Pattern Recognit Artif Intell (in Chinese) 17:7–10
20.
Li F, Yin Y (2009) Approaches to knowledge reduction of covering decision systems based on information theory. Inf Sci 179:1694–1704CrossRefMATHMathSciNet
21.
Li Y (2007) Some researches on fuzzy matroids. PhD Thesis, Shaanxi Normal University
22.
23.
24.
Liu G (2013) The relationship among different covering approximations. Inf Sci 250:178–183CrossRef
25.
Liu Y, Zhu W (2012) Parametric matroid of rough set. arXiv:1209.4975 [cs.AI]
26.
Lin TY (2003) Granular computing: structures, representations, and applications. In: Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. Volume 2639 of LNAI, pp 16–24
27.
28.
29.
Pal S, Mitra S, Mitra P (2003) Rough-fuzzy mlp: modular evolution, rule generation, and evaluation. IEEE Trans Knowl Data Eng 15:15–24CrossRef
30.
Qian Y, Liang J, Pedrycz W, Dang C (2010) Positive approximation: an accelerator for attribute reduction in rough set theory. Artif Intell 174:597–618CrossRefMATHMathSciNet
31.
Rouayheb SYE, Sprintson A, Georghiades CN (2010) On the index coding problem and its relation to network coding and matroid theory. IEEE Trans Inf Theory 56:3187–3195CrossRef
32.
Skowron A, Stepaniuk J, Swiniarski R (2012) Modeling rough granular computing based on approximation spaces. Inf Sci 184:20–43CrossRef
33.
34.
Wang X, Tsang EC, Zhao S, Chen D, Yeung DS (2007) Learning fuzzy rules from fuzzy samples based on rough set technique. Inf Sci 177:4493–4514CrossRefMATHMathSciNet
35.
36.
Wu W (2008) Attribute reduction based on evidence theory in incomplete decision systems. Inf Sci 178:1355–1371CrossRefMATH
37.
Wang S, Zhu W (2011) Matroidal structure of covering-based rough sets through the upper approximation number. Int J Granul Comput Rough Sets Intell Syst 2:141–148CrossRef
38.
Wang S, Zhu W, Min F (2011) Transversal and function matroidal structures of covering-based rough sets. In: Rough Sets and Knowledge Technology. Volume 6954 of LNCS, pp 146–155
39.
Wang J, Zhu W (2013) Contraction to matroidal structure of rough sets. In: Rough Sets and Knowledge Technology. Volume 8171 of LNAI, pp 75–86
40.
Wang J, Zhu W (2013) Applications of matrices to a matroidal structure of rough sets. J Appl Math Article ID 493201
41.
42.
43.
Yun Z, Ge X, Bai X (2011) Axiomatization and conditions for neighborhoods in a covering to form a partition. Inf Sci 181:1735–1740CrossRefMATHMathSciNet
44.
Zhong N (2001) Rough sets in knowledge discovery and data mining. J Jpn Soc Fuzzy Theory Syst 13:581–591
45.
Zhu W, Wang F (2003) Reduction and axiomization of covering generalized rough sets. Inf Sci 152:217–230CrossRefMATH
46.
Zhu W, Wang F (2006) Relationships among three types of covering rough sets. In: Granular Computing,. pp 43–48
47.
48.
Zhu W (2009) Relationship among basic concepts in covering-based rough sets. Inf Sci 179:2478–2486CrossRefMATH
49.
Zhu W, Wang S (2011) Matroidal approaches to generalized rough sets based on relations. Int J Mach Learn Cybern 2:273–279CrossRef
Metadata
Title
Conditions for coverings to induce matroids
Authors
Jingqian Wang
William Zhu
Fei-Yue Wang
Guilong Liu
Publication date
01-12-2014
Publisher
Springer Berlin Heidelberg
Published in
International Journal of Machine Learning and Cybernetics / Issue 6/2014
Print ISSN: 1868-8071
Electronic ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-014-0236-2

Other articles of this Issue 6/2014

International Journal of Machine Learning and Cybernetics 6/2014 Go to the issue

Original Article

A fast template matching-based algorithm for railway bolts detection

Original Article

A comparison of ℓ1-regularizion, PCA, KPCA and ICA for dimensionality reduction in logistic regression

Original Article

Primitive attempt to turn images into percepts

Original Article

Secondary basis unique augmentation matroids and union minimal matroids

Original Article

A novel prior-based real-time click through rate prediction model

Original Article

Towards enriching the quality of k-nearest neighbor rule for document classification