Evolving Classifiers - Evolutionary Algorithms in Data Mining

Data mining means to summarize information from large amounts of raw data. It is one of the key technologies in many areas of economy, science, administration and the internet. In this report we introduce an approach for utilizing evolutionary algorithms to breed fuzzy classifier systems. This approach was exercised as part of a structured procedure by the students Achler, Göb and Voigtmann as contribution to the 2006 Data-Mining-Cup contest, yielding encouragingly positive results.

Fast computation of concept lattices using data mining techniques

We present a new algorithm called TITANIC for computing concept lattices. It is based on data mining techniques for computing frequent itemsets. The algorithm is experimentally evaluated and compared with B. Ganter's Next-Closure algorithm.

Mining minimal non-redundant association rules using frequent closed itemsets

The problem of the relevance and the usefulness of extracted association rules is of primary importance because, in the majority of cases, real-life databases lead to several thousands association rules with high confidence and among which are many redundancies. Using the closure of the Galois connection, we define two new bases for association rules which union is a generating set for all valid association rules with support and confidence. These bases are characterized using frequent closed itemsets and their generators; they consist of the non-redundant exact and approximate association rules having minimal antecedents and maximal consequences, i.e. the most relevant association rules. Algorithms for extracting these bases are presented and results of experiments carried out on real-life databases show that the proposed bases are useful, and that their generation is not time consuming.

Towards semantic web mining

Semantic Web Mining aims at combining the two fast-developing research areas Semantic Web and Web Mining. The idea is to improve, on the one hand, the results of Web Mining by exploiting the new semantic structures in the Web; and to make use of Web Mining, on overview of where the two areas meet today, and sketches ways of how a closer integration could be profitable.

Efficient data mining based on formal concept analysis

Formal Concept Analysis is an unsupervised learning technique for conceptual clustering. We introduce the notion of iceberg concept lattices and show their use in Knowledge Discovery in Databases (KDD). Iceberg lattices are designed for analyzing very large databases. In particular they serve as a condensed representation of frequent patterns as known from association rule mining. In order to show the interplay between Formal Concept Analysis and association rule mining, we discuss the algorithm TITANIC. We show that iceberg concept lattices are a starting point for computing condensed sets of association rules without loss of information, and are a visualization method for the resulting rules.

Semantic web mining and the representation, analysis, and evolution of web space

Semantic Web Mining aims at combining the two fast-developing research areas Semantic Web and Web Mining. This survey analyzes the convergence of trends from both areas: Growing numbers of researchers work on improving the results of Web Mining by exploiting semantic structures in the Web, and they use Web Mining techniques for building the Semantic Web. Last but not least, these techniques can be used for mining the Semantic Web itself. The second aim of this paper is to use these concepts to circumscribe what Web space is, what it represents and how it can be represented and analyzed. This is used to sketch the role that Semantic Web Mining and the software agents and human agents involved in it can play in the evolution of Web space.

Mining association rules in folksonomies

Social bookmark tools are rapidly emerging on the Web. In such systems users are setting up lightweight conceptual structures called folksonomies. These systems provide currently relatively few structure. We discuss in this paper, how association rule mining can be adopted to analyze and structure folksonomies, and how the results can be used for ontology learning and supporting emergent semantics. We demonstrate our approach on a large scale dataset stemming from an online system.

Semantic web mining

Semantic Web Mining aims at combining the two fast-developing research areas Semantic Web and Web Mining. This survey analyzes the convergence of trends from both areas: an increasing number of researchers is working on improving the results of Web Mining by exploiting semantic structures in the Web, and they make use of Web Mining techniques for building the Semantic Web. Last but not least, these techniques can be used for mining the Semantic Web itself. The Semantic Web is the second-generation WWW, enriched by machine-processable information which supports the user in his tasks. Given the enormous size even of today’s Web, it is impossible to manually enrich all of these resources. Therefore, automated schemes for learning the relevant information are increasingly being used. Web Mining aims at discovering insights about the meaning of Web resources and their usage. Given the primarily syntactical nature of the data being mined, the discovery of meaning is impossible based on these data only. Therefore, formalizations of the semantics of Web sites and navigation behavior are becoming more and more common. Furthermore, mining the Semantic Web itself is another upcoming application. We argue that the two areas Web Mining and Semantic Web need each other to fulfill their goals, but that the full potential of this convergence is not yet realized. This paper gives an overview of where the two areas meet today, and sketches ways of how a closer integration could be profitable.

Efficient mining of association rules based on formal concept analysis

Association rules are a popular knowledge discovery technique for warehouse basket analysis. They indicate which items of the warehouse are frequently bought together. The problem of association rule mining has first been stated in 1993. Five years later, several research groups discovered that this problem has a strong connection to Formal Concept Analysis (FCA). In this survey, we will first introduce some basic ideas of this connection along a specific algorithm, TITANIC, and show how FCA helps in reducing the number of resulting rules without loss of information, before giving a general overview over the history and state of the art of applying FCA for association rule mining.

Adaptive Real-time Anomaly-based Intrusion Detection using Data Mining and Machine Learning Techniques

Die zunehmende Vernetzung der Informations- und Kommunikationssysteme führt zu einer weiteren Erhöhung der Komplexität und damit auch zu einer weiteren Zunahme von Sicherheitslücken. Klassische Schutzmechanismen wie Firewall-Systeme und Anti-Malware-Lösungen bieten schon lange keinen Schutz mehr vor Eindringversuchen in IT-Infrastrukturen. Als ein sehr wirkungsvolles Instrument zum Schutz gegenüber Cyber-Attacken haben sich hierbei die Intrusion Detection Systeme (IDS) etabliert. Solche Systeme sammeln und analysieren Informationen von Netzwerkkomponenten und Rechnern, um ungewöhnliches Verhalten und Sicherheitsverletzungen automatisiert festzustellen. Während signatur-basierte Ansätze nur bereits bekannte Angriffsmuster detektieren können, sind anomalie-basierte IDS auch in der Lage, neue bisher unbekannte Angriffe (Zero-Day-Attacks) frühzeitig zu erkennen. Das Kernproblem von Intrusion Detection Systeme besteht jedoch in der optimalen Verarbeitung der gewaltigen Netzdaten und der Entwicklung eines in Echtzeit arbeitenden adaptiven Erkennungsmodells. Um diese Herausforderungen lösen zu können, stellt diese Dissertation ein Framework bereit, das aus zwei Hauptteilen besteht. Der erste Teil, OptiFilter genannt, verwendet ein dynamisches "Queuing Concept", um die zahlreich anfallenden Netzdaten weiter zu verarbeiten, baut fortlaufend Netzverbindungen auf, und exportiert strukturierte Input-Daten für das IDS. Den zweiten Teil stellt ein adaptiver Klassifikator dar, der ein Klassifikator-Modell basierend auf "Enhanced Growing Hierarchical Self Organizing Map" (EGHSOM), ein Modell für Netzwerk Normalzustand (NNB) und ein "Update Model" umfasst. In dem OptiFilter werden Tcpdump und SNMP traps benutzt, um die Netzwerkpakete und Hostereignisse fortlaufend zu aggregieren. Diese aggregierten Netzwerkpackete und Hostereignisse werden weiter analysiert und in Verbindungsvektoren umgewandelt. Zur Verbesserung der Erkennungsrate des adaptiven Klassifikators wird das künstliche neuronale Netz GHSOM intensiv untersucht und wesentlich weiterentwickelt. In dieser Dissertation werden unterschiedliche Ansätze vorgeschlagen und diskutiert. So wird eine classification-confidence margin threshold definiert, um die unbekannten bösartigen Verbindungen aufzudecken, die Stabilität der Wachstumstopologie durch neuartige Ansätze für die Initialisierung der Gewichtvektoren und durch die Stärkung der Winner Neuronen erhöht, und ein selbst-adaptives Verfahren eingeführt, um das Modell ständig aktualisieren zu können. Darüber hinaus besteht die Hauptaufgabe des NNB-Modells in der weiteren Untersuchung der erkannten unbekannten Verbindungen von der EGHSOM und der Überprüfung, ob sie normal sind. Jedoch, ändern sich die Netzverkehrsdaten wegen des Concept drif Phänomens ständig, was in Echtzeit zur Erzeugung nicht stationärer Netzdaten führt. Dieses Phänomen wird von dem Update-Modell besser kontrolliert. Das EGHSOM-Modell kann die neuen Anomalien effektiv erkennen und das NNB-Model passt die Änderungen in Netzdaten optimal an. Bei den experimentellen Untersuchungen hat das Framework erfolgversprechende Ergebnisse gezeigt. Im ersten Experiment wurde das Framework in Offline-Betriebsmodus evaluiert. Der OptiFilter wurde mit offline-, synthetischen- und realistischen Daten ausgewertet. Der adaptive Klassifikator wurde mit dem 10-Fold Cross Validation Verfahren evaluiert, um dessen Genauigkeit abzuschätzen. Im zweiten Experiment wurde das Framework auf einer 1 bis 10 GB Netzwerkstrecke installiert und im Online-Betriebsmodus in Echtzeit ausgewertet. Der OptiFilter hat erfolgreich die gewaltige Menge von Netzdaten in die strukturierten Verbindungsvektoren umgewandelt und der adaptive Klassifikator hat sie präzise klassifiziert. Die Vergleichsstudie zwischen dem entwickelten Framework und anderen bekannten IDS-Ansätzen zeigt, dass der vorgeschlagene IDSFramework alle anderen Ansätze übertrifft. Dies lässt sich auf folgende Kernpunkte zurückführen: Bearbeitung der gesammelten Netzdaten, Erreichung der besten Performanz (wie die Gesamtgenauigkeit), Detektieren unbekannter Verbindungen und Entwicklung des in Echtzeit arbeitenden Erkennungsmodells von Eindringversuchen.

Microbial response to restoration of tantalite mine soils in western Rwanda

Artisanal columbite-tantalite (coltan) mining has had negative effects on the rural economy in the great Lakes region of Africa through labor deficits, degradation and loss of farmland, food insecurity, high cost of living, and reduced traditional export crop production alongside secondary impacts that remotely affect the quality of air, water, soil, plants, animals, and human wellbeing. The situation is multifaceted and calls for a holistic approach for short and long-term mitigation of such negative effects. This study focuses on the effects of mine land restoration on soil microbiological quality in the Gatumba Mining District of western Rwanda. Some coltan mine wastelands were afforested with pine and eucalyptus trees while farmers directly cultivated others due to land scarcity. Farmyard manure (FYM) is the sole fertilizer applied on the wastelands although it is insufficient to achieve the desired crop yields. Despite this, several multi-purpose plants such as Tithonia diversifolia, Markhamia lutea, and Canavalia brasiliensis thrive in the area and could supplement FYM. The potential for these “new” amendments to improve soil microbial properties, particularly in the tantalite mine soils was investigated. The specific objectives of the study were to: (a) evaluate the effects of land use on soil microbial indices of the tantalite mine soils; (b) investigate the restorative effects of organic amendments on a Technosol; and (c) estimate the short-term N and P supply potential of the soil amendments in the soils. Fresh soils (0-20 cm) from an unmined native forest, two mine sites afforested with pine and eucalyptus forests (pine and eucalyptus Technosols), an arable land, and two cultivated Technosols (Kavumu and Kirengo Technosols) were analyzed for the physicochemical properties. Afterwards, a 28-day incubation (22oC) experiment was conducted followed by measurements of mineral N, soil microbial biomass C, N, P, and fungal ergosterol contents using standard methods. This was followed by a 12-week incubation study of the arable soil and the Kavumu Technosol amended with FYM, Canavalia and Tithonia biomass, and Markhamia leaf litter after which soil microbial properties were measured at 2, 8, and 12 weeks of incubation. Finally, two 4-week incubation experiments each were conducted in soils of the six sites to estimate (i) potential mineralizable N using a soil-sand mixture (1:1) amended with Canavalia and goat manure and (ii) P mineralization mixtures (1:1) of soil and anion exchange resins in bicarbonate form amended with Tithonia biomass and goat manure. In study one, afforestation increased soil organic carbon and total N contents in the pine and eucalyptus Technosols by 34-40% and 28-30%, respectively of that in the native forest soil. Consequently, the microbial biomass and activity followed a similar trend where the cultivated Technosols were inferior to the afforested ones. The microbial indices of the mine soils were constrained by soil acidity, dithionite-extractable Al, and low P availability. In study two, the amendments substantially increased C and N mineralization, microbial properties compared with non-amended soils. Canavalia biomass increased CO2 efflux by 340%, net N mineralization by 30-140%, and microbial biomass C and N by 240-600% and 240-380% (P < 0.01), respectively after four weeks of incubation compared with the non-amended soils. Tithonia biomass increased ergosterol content by roughly 240%. The Kavumu Technosol showed a high potential for quick restoration of its soil quality due to its major responses to the measured biological parameters. In study three, Canavalia biomass gave the highest mineralizable N (130 µg g-1 soil, P < 0.01) in the Kavumu Technosol and the lowest in the native forest soil (-20 µg g-1 soil). Conversely, the mineralizable N of goat manure was negative in all soils ranging from -2.5 µg N g-1 to -7.7 µg N g-1 soil except the native forest soil. However, the immobilization of goat manure N in the “cultivated soils” was 30-70% lower than in the “forest soils” signifying an imminent recovery of the amended soils from N immobilization. The mineralization of goat manure P was three-fold that of Tithonia, constituting 61-71% of total P applied. Phosphorus mineralization slightly decreased after four weeks of incubation due to sulfate competition as reflected in a negative correlation, which was steeper in the Tithonia treatment. In conclusion, each amendment used in this research played a unique role in C, N, and P mineralization and contributed substantially to microbial properties in the tantalite mine soils. Interestingly, the “N immobilizers” exhibited potentials for P release and soil organic carbon storage. Consequently, the combined use of the amendments in specific ratios, or co-composting prior to application is recommended to optimize nutrient release, microbial biomass dynamics and soil organic matter accrual. Transport of organic inputs seems more feasible for smallholder farmers who typically manage small field sizes. To reduce acidity in the soils, liming with wood ash was recommended to also improve P availability and enhance soil biological quality, even if it may only be possible on small areas. Further, afforestation with mixed-species of fast-growing eucalyptus and legume or indigenous tree species are suggested to restore tantalite mine wastelands. It is emphasized most of this research was conducted under controlled laboratory conditions, which exclude interaction with environmental variables. Also fine fractions of the amendments were used compared with the usual practice of applying a mixture of predominantly coarser fractions. Therefore, the biological dynamics reported in the studies here may not entirely reflect those of farmers’ field conditions.