Abstract Clustering algorithms are essential in data analysis, but evaluating their performance is challenging when the true labels are not available, especially for non-convex clusters. Traditional performance evaluation metrics struggle to identify clustering quality, often assigning higher scores for linearly separated clusters than the true clusters. We propose an original approach to distance computation that accounts for the data structure, thus improving the clustering quality evaluation for non-convex clusters without affecting other shapes of clusters. We also showcase the applicability of this method through a modified version of K-Means using the proposed method that is capable of correctly separating non-convex clusters. The validation included the analysis of performance and time complexity of 3 traditional clustering quality evaluation metrics and the K-Means clustering algorithm against their augmented versions with the proposed approach. This analysis conducted on 7 benchmark synthetic datasets and 6 real datasets with various numbers of examples and features of diverse characteristics and joint complexities: simple convex clusters, overlapped and imbalanced clusters, and non-convex clusters. Through these analyses, we show the ineffectiveness of traditional methods and that the proposed approach overcomes the weaknesses of traditional methods.

Malware signatures represent a powerful tool for malware detection and classification, widely used by security researchers and security solution providers. Yara rules describe malware based on string patterns that are evaluated on targeted files. Generally, the security provider sends signatures to the client endpoints and the rule evaluation is performed locally, such that the scanned files do not leave the client machines. However, if a zero-day vulnerability is discovered and the security provider exposes the corresponding signature, there is a considerable risk to also disclose the unpatched vulnerability. A solution is represented by homomorphic encrypted Yara rules, which can be evaluated on targeted files without being decrypted. In this article, we propose a homomorphic Yara rules evaluation method and do a comparative analysis with the HENFA method (Homomorphic Encryption for Finite Automata (Genise et al., 2019)). For our method, we propose a fully homomorphic exact string matching algorithm based on the TFHE scheme (Fully Homomorphic Encryption over the Torus (Chillotti et al., 2020)). In order to determine how suitable is the exact string matching approach in practice, we analyze a public Yara rules repository and generate various statistics about the patterns used in the Yara rules. For the two homomorphic Yara rules matching methods, both theoretical and experimental comparative evaluations are presented. Our proposed method implies ciphertexts with smaller sizes and has better efficiency in the average testing scenarios compared to the HENFA method.

Meaning Representation parsing aims to represent a sentence as a structured, Directed, Acyclic Graph (DAG), in an attempt to extract meaning from text. This paper extends an existing 2-stage pipeline AMR parser with state-of-the-art techniques in dependency parsing. First, Pointer-Generator Networks are used for out-of-vocabulary words in the concept identification stage, with an improved initialization via the use of word-and character-level embeddings. Second, the performance of the Relation Identification module is improved by jointly training the Heads Selection and the Arcs Labeling components. Last, we underline the difficulty of end-to-end training with recurrent modules in a static deep neural network construction approach and explore a dynamic construction implementation, which continuously adapts the computation graph, thus potentially enabling end-to-end training in the proposed pipeline solution.

Data collected by sensors has hidden value that can be used to infer valuable knowledge about the system, such as identifying faults in transmission or functioning faults in various system components. Solutions for exploring and exploiting data need to be developed to extract such knowledge. This paper shows how the identification of transmission regularities can be used to extract knowledge about the overall system state.The focus of this work is defining a methodology for detecting transmission periodicity. In our approach, we evaluated other strategies, addressed various limitations they have, and narrowed their utility on real-world data. We further expand the scope by defining strategies for the identification of transmission gaps and duplicates. Finally, we validate the algorithms on samples of real industrial data obtained from monitoring different parts of home appliances.

Enhancing traffic experience in congested urban areas is one of the main challenge of Intelligent Transportation Systems caused by road infrastructure, time and investment cost. Since road infrastructure have very small chances to be changed and the changes' cost are high it is worth to address research solutions that have low costs and uses Intelligent Transportation System infrastructure's properties. Following this vision, in this work we propose a realistic cost efficient urban traffic simulation methodology in order to accurately simulate vehicular traffic. Such synthetic traffic can be used by congestion avoidance solutions implementations and evaluation in the context of connected vehicles that shares information based on a centralized Vehicle to Cloud infrastructure. The proposed traffic simulation methodology was validated on a real urban area map by using the fundamental traffic flow diagram metrics. Our findings shown the realistic behaviour and valuable output of the proposed model that can be used as input in traffic congestion avoidance solutions.

Most of the existing navigation solutions compute individual routes based on map topology and traffic data but, without considering the route effect on the entire navigation ecosystem. Traffic data usage and sharing in the context of connected cars is a key element for route planning. Such solutions require efficient implementation and deployment in order to reduce any kind of risk. Following a smart driving methodology, we run different route search algorithms on connected cars traffic scenarios in order to avoid traffic congestion and minimize total driving time on the entire navigation ecosystem. The experiments in this work proved that connected cars data usage and sharing reduce the total driving time of the navigation ecosystem and also that specific routing algorithms are more suitable for specific connected cars scenarios in order to obtain relevant results.

Neural networks have gained a lot of attention recently and there have different techniques have been developed in order to evolve them. Neuroevolution is a flexible yet robust way of evolving such networks and it has been applied in a variety of fields from learning behaviour in games to solving classification problems. Neat is one of the most powerful approaches when it comes to neuroevolution. It can handle both behaviour learning as well as classification problems. The downside of neuroevolution is the time it takes to reach a solution as evolving both weights and structure comes at great costs. Meta-NEAT offers a way to optimize the convergence rate of NEAT through the use of an additional genetic algorithm built on top of NEAT. It adds an additional layer which learns optimal hyper-parameter configurations in order to boost the convergence rate of NEAT. The obtained configurations are thus useful as they both reveal the most important aspects of a network's evolution and greatly speed up the evolution process. The difficulties of crossing over in the context of neuroevolving topologies and a novel approach to it are also presented. The problems on which the approach was tested on range from behaviour learning problems to classification problems.

The large amount of unstructured medical documents written in natural language bears a massive quantity of knowledge, whose extraction becomes useful. An automatic relation identification strategy leads to the discovery of relations, (possible unknown) interactions, and associations between medical conditions, investigations and treatments. The current paper introduces a learning based approach for the automatic discovery of relations between medical concepts, entitled REMed. We propose an original list of features, grouped into four categories with the following distribution: lexical - 3, context - 6, grammatical -- 4 and syntactic - 4. We analyzed the influence of each category on the classification performance and determined that the performance of the REMed solution is comparable with similar solutions. We report the overall F-measure as 74.9% that outperforms the best solution reported in the similar systems with 1.2%. This performance was achieved mostly by the features from the lexical and context categories.

In this paper we address the problem of identifying contradictions by opinion mining across documents. Our approach involves opinion extraction and storage by processing natural language documents such as reviews, news etc. and aims the identification of contradictory opinions related to the same target expressed by the same holder or by different holders. By matching the structured representations of opinions we identify a potential inconsistency occurring in two documents that is signaled and further analysis is applied to confirm/infirm the contradiction. Moreover, communities are detected both on individual opinions and social data. Thus, the (in)consistency might be tracked for the holder as a member of a community, as well as for the holder as an individual. We addressed scalability by designing a cloud-based storage infrastructure and an efficient indexing system that allows for fast retrieval and matching of structured representations.

Imbalanced classification problems represent a current challenge in data mining research, due to the classifiers' inability to produce sufficiently good models in such situations. We have previously proposed a general methodology for improving the performance of classifiers under imbalance conditions: ECSB -- Evolutionary Cost-Sensitive Balancing. This paper provides an empirical analysis on a distributed approach for ECSB (dECSB). The influence of the number of splits on the quality of the output classification model is studied on several data sets and J4.8 as base classifier. The data sets have been partitioned according to the imbalance ratio and the instances per attributes ratio. We found that the appropriate number of splits is highly dependent on the problem at hand, however, an influence of the two imbalance-related factors is present. The effect of altering the genetic settings has also been investigated, in the attempt to identify several values which constantly yield good results. Again, we found the results to be highly dependent on the problem, with some data sets exhibiting low performance variations due to the genetic settings.

Current important challenges in data mining research are triggered by the need to address various particularities of real-world problems, such as imbalanced data and error cost distributions. This paper presents Distributed Evolutionary Cost-Sensitive Balancing, a distributed methodology for dealing with imbalanced data and -- if necessary -- cost distributions. The method employs a genetic algorithm to search for an optimal cost matrix and base classifier settings, which are then employed by a cost-sensitive classifier, wrapped around the base classifier. Individual fitness computation is the most intensive task in the algorithm, but it also presents a high parallelization potential. Two different parallelization alternatives have been explored: a computation-driven approach, and a data-driven approach. Both have been developed within the Apache Watchmaker framework and deployed on Hadoop-based infrastructures. Experimental evaluations performed up to this point have indicated that the computation-driven approach achieves a good classification performance, but does not reduce the running time significantly, the data-driven approach reduces the running time for slow algorithms, such as the kNN and the SVM, while still yielding important performance improvements.

This paper studies the viability of GPGPU, by analyzing the speedup of 9 algorithms frequently used in practice. The speedup we have obtained suggests the possibility of implementing fast versions of Levenshtein distance and Knuth-Morris-Pratt exact search, required by many bioinformatics applications.

Perhaps the most utilized and demanded task in data mining is classification. Most existing classification algorithms require all the data used for constructing the model for classification, or at least a good part of it, to be stored in the memory. This makes them limited by the availability of the memory. We present a parallel algorithm, based on the SPRINT decision tree, which eliminates the dependency on the memory available by storing the data to be processed in a database.

This paper focuses on solutions to two NP-Complete problems: k-SAT and the knapsack problem. We propose a new parallel genetic algorithm strategy on the CUDA architecture, and perform experiments to compare it with the sequential versions. We show how these problems can benefit from the GPU solutions, leading to significant improvements in speedup while keeping the quality of the solution. The best performance obtained in terms of speedup is 67 times. The solution presented in this paper suggests a general strategy for finding fast and robust solutions to complex problems.

In this paper we present a new method that uses data flow coherence criteria in definite logic program generation. We outline three main advantages of these criteria supported by our results: (i) drastically pruning the search space (around 90%), (ii) reducing the set of positive examples and reducing or even removing the need for the set of negative examples, and (iii) allowing the induction of predicates that are difficult or even impossible to generate by other methods. Besides these criteria, the approach takes into consideration the program termination condition for recursive predicates. The paper outlines some theoretical issues and implementation aspects of our system for automatic logic program induction.