Stream Learning with Enity-Centric Models and Active Feature Aquisition

Abstract

Data stream mining addresses environments where data arrives continuously, often at high volumes and velocities, and requires models that adapt incrementally to changes in the data. In many cases, data stream instances are linked to specific entities, such as product reviews (instances) being linked to a particular product (entity). However, current practices generally utilize a single model per stream, disregarding the relationship between entities and their instances. Another common assumption is that arriving instances are feature-complete or that missing features must be imputed due to their unavailability. This thesis is organized into two parts. The first part introduces the concept of entity-centric learning on data streams, where the relationship between entities and their instances is explicitly modeled in the stream’s data space. Entity-centric learning involves creating individual prediction models for each entity, allowing model learning and adaptation to account for each entity’s unique characteristics. This approach contrasts with traditional methods that apply a single model across the entire stream. The analysis demonstrates that entity-centric learning can improve prediction quality in data streams. Initial experiments focused on comparing an entity-ignorant (global) model, which accessed features but pooled data from all entities, with basic entity-centric models that relied solely on an entity’s labels, such as a moving average. Results highlighted that, for some entities, even a simple entity-centric model outperformed a more complex entity-ignorant one. However, entities with fewer instances showed better results with the entity-ignorant model. A hybrid ensemble approach combining entity-centric and entity-ignorant models was proposed to address this. This ensemble significantly improved prediction quality across most entities. However, maintaining separate models for each entity posed a challenge for memory management. To resolve this, a memory management system was introduced, differentiating between active and inactive entities. Models for active entities were kept in primary memory, while those for inactive entities were moved to secondary storage. This makes entity-centric learning feasible on data streams with a large number of entities. The second part of the thesis shifts focus from the data space to the feature space, tackling the problem of missing features. One of the first studies on active feature acquisition (AFA) for data streams is presented, exploring scenarios where missing features can be acquired at a cost under budget constraints. The initial approach assumed equal feature costs and allowed the acquisition of one missing feature per instance. Using a stream feature selection metric to assess feature importance, it was shown that acquiring the most valuable feature outperformed random acquisition, usually a competitive baseline in the field of active learning. Subsequent work extended this method to handle varying acquisition set sizes and differing feature costs. Experiments across multiple cost distributions and levels of missingness demonstrated that the proposed methods consistently outperformed a random baseline. The experiments also highlighted that a feature importance metric that considers each feature independently can lead to superfluous acquisitions in the case of feature correlations, which wastes the available budget. This was addressed in the final study, which introduces a two-stage decision process for budget optimization, where imputation is considered before feature acquisition. A specialized imputation method, the feature-pair-imputer, was developed to predict missing features based on available ones, tracking imputation performance. This approach allowed for informed decisions on whether to impute or acquire missing features, achieving budget savings without significantly compromising prediction accuracy compared to an AFA-only strategy. In conclusion, this thesis presents novel methods for both entity-centric learning on data streams and active feature acquisition. Various experimental frameworks were developed to support these investigations, including synthetic dataset gener ators for exploring aspects such as concept drift, complex label dependencies, and feature correlations. The results demonstrate that entity-centric models can enhance prediction quality with minimal computational cost, while active feature acquisition enables cost-effective handling of missing features in data streams.

Das Lernen auf Datenströmen befasst sich mit Umgebungen, in denen Daten kontinuierlich, oft in großen Mengen und mit hoher Geschwindigkeit eintreffen, und erfordert Modelle, die sich inkrementell an Veränderungen in den Daten anpassen. In vielen Fällen sind Datenstrominstanzen mit bestimmten Entitäten verknüpft, wie z.B. Produktbewertungen (Instanzen), die einem bestimmten Produkt (Entität) zugeordnet sind. Die derzeitigen Praktiken verwenden jedoch in der Regel ein einzelnes Modell pro Datenstrom und ignorieren dabei die Beziehung zwischen Entitäten und ihren Instanzen. Eine weitere häufige Annahme ist, dass die eintreffenden Instanzen keine fehlenden Attribute haben oder dass fehlende Attribute aufgrund ihrer Nichtverfügbarkeit imputiert werden müssen. Diese Dissertation ist in zwei Teile gegliedert. Der erste Teil führt das Konzept des entitätszentrierten Lernens auf Datenströmen ein, bei dem die Beziehung zwischen Entitäten und ihren Instanzen explizit im Datenraum des Stroms modelliert wird. Das entitätszentrierte Lernen umfasst die Erstellung individueller Vorhersagemodelle für jede Entität, was eine Anpassung und das Lernen der Modelle an die spezifischen Charakteristiken jeder Entität ermöglicht. Dieser Ansatz steht im Gegensatz zu traditionellen Methoden, die ein einziges Modell über den gesamten Strom anwenden. Die Analyse zeigt, dass entitätszentriertes Lernen die Vorhersagequalität in Datenströmen verbessern kann. Die ersten Experimente konzentrierten sich auf den Vergleich eines entitätsignoranten (globalen) Modells, das auf Attribute zugriff, aber die Daten aller Entitäten verarbeitete, mit naiven entitätszentrierten Modellen, die sich ausschließlich auf die Labels einer Entität stützten, wie z.B. einen gleitenden Durchschnitt. Die Ergebnisse zeigten, dass für einige Entitäten selbst ein einfaches entitätszentriertes Modell ein komplexeres entitätsignorantes Modell übertraf. Allerdings erzielten Entitäten mit weniger Instanzen bessere Ergebnisse mit dem entitätsignoranten Modell. Um dies zu lösen, wurde ein hybrider Ensemble-Ansatz vorgeschlagen, der entitätszentrierte und entitätsignorante Modelle kombiniert. Dieses Ensemble verbesserte die Vorhersagequalität für die meisten Entitäten signifikant. Die Aufrechterhaltung separater Modelle für jede Entität stellte jedoch eine Herausforderung für das Speichermanagement dar. Um diese Herausforderung zu adressieren, wurde ein Speichermanagementsystem eingeführt, das zwischen aktiven und inaktiven Entitäten unterscheidet. Modelle für aktive Entitäten wurden im Primärspeicher gehalten, während Modelle für inaktive Entitäten in den Sekundärspeicher verschoben wurden. Dies macht entitätszentriertes Lernen auf vielen Datenströmen praktikabel. Der zweite Teil der Dissertation verlagert den Fokus vom Datenraum auf den Attributsraum und befasst sich mit dem Problem fehlender Attribute. Es wird eine der ersten Studien zur aktiven Attributsakquisition für Datenströme vorgestellt, die Szenarien untersucht, in denen fehlende Attribute zu Kosten unter Budgetbeschränkungen erworben werden können. Der anfängliche Ansatz ging von gleichen Attributkosten aus und ermöglichte den Erwerb eines fehlenden Attributs pro Instanz. Mithilfe einer Metrik zur Attributauswahl im Datenstrom, die die Wichtigkeit der Attribute bewertete, wurde gezeigt, dass der Erwerb des wertvollsten Attributs eine zufällige Akquisition übertraf. Darauf aufbauend wurde diese Methode erweitert, um unterschiedliche Akquisitionsgrößen und variierende Attributkosten zu berücksichtigen. Experimente über verschiedene Kostenverteilungen und Ausmaße des Fehlens zeigten, dass die vorgeschlagenen Methoden eine zufällige Baseline konstant übertrafen. Die Experimente zeigten auch, dass eine Metrik zur Attributwichtigkeit, die jedes Attribut unabhängig betrachtet, zu überflüssigen Akquisitionen führen kann, wenn Attributkorrelationen vorliegen, was das verfügbare Budget verschwendet. Dies wurde in der letzten Untersuchung aufgegriffen, die einen zweistufigen Entscheidungsprozess zur Budgetoptimierung einführt, bei dem die Imputation vor der Attributakquisition in Betracht gezogen wird. Eine spezialisierte Imputationsmethode, der "Feature-Pair-Imputer", wurde entwickelt, um fehlende Attribute basierend auf verfügbaren vorherzusagen und die Imputationsleistung zu verfolgen. Dieser Ansatz ermöglichte fundierte Entscheidungen darüber, ob fehlende Attribute imputiert oder akquiriert werden sollten, wodurch Budgeteinsparungen erzielt wurden, ohne die Vorhersagegenauigkeit im Vergleich zu einer rein auf aktiver Attributsakquisition basierenden Strategie signifikant zu beeinträchtigen. Diese Dissertation präsentiert Methoden sowohl für das entitätszentrierte Lernen auf Datenströmen als auch für die aktive Attributsakquisition. Verschiedene Software wurden entwickelt, um diese Untersuchungen zu unterstützen, einschließlich synthetischer Datengeneratoren zur Erkundung von Aspekten wie Concept Drift, komplexen Label-Abhängigkeiten und Attributskorrelationen. Die Ergebnisse zeigen, dass entitätszentrierte Modelle die Vorhersagequalität bei minimalen Rechenkosten verbessern können, während die aktive Attributsakquisition eine kosteneffiziente Handhabung fehlender Attribute in Datenströmen ermöglicht.