Speaker: Philippe Fournier-Viger
Speaker: Philippe Fournier-Viger
Title: Algorithms to Find Interesting and Interpretable High Utility Patterns in Symbolic Data
Discovering interesting and useful patterns in symbolic data has been the subject of numerous studies. It consists of extracting patterns from data that meet a set of requirements specified by a user. Although early research work in this domain have mainly focused on identifying frequent patterns (e.g. itemsets), nowadays many other types of interesting patterns have been pro-posed and more complex data types and pattern types are considered. Mining patterns has applications in many fields as they provide glass-box models that are generally easily interpretable by humans either to understand the data or support decision-making. This talk will first highlight limitations of early work on frequent pattern mining and provide an overview of state-of-the-art problems and techniques related to identifying interesting patterns in symbol-ic data. Topics that will be discussed include high utility patterns, locally in-teresting patterns, periodic patterns and statistically significant patterns. Last-ly, the SPMF open-source software will be mentioned and opportunities re-lated to the combination of pattern mining techniques with traditional artifi-cial intelligence techniques.
Philippe Fournier-Viger (Ph.D) is a Canadian researcher, full professor at the Harbin Institute of Technology (Shenzhen, China). Five years after completing his Ph.D., he came to China and became full professor at the Harbin Institute of Technology (Shenzhen), after obtaining a title of national talent from the Nation-al Science Foundation of China. He has published more than 200 research papers in refereed international conferences and journals, which have received more than 1000 citations in the last year. He is the founder of the popular SPMF open-source data mining library, which provides more than 150 algorithms for identi-fying various types of patterns in data. The SPMF software has been used in more than 630 papers since 2010 for many applications from chemistry, smartphone usage analysis restaurant recommendation to malware detection. He is editor of the book “High Utility Pattern Mining: Theory, Algorithms and Applications” published by Springer in 2019, and co-organizer of the Utility Driven Mining and Learning workshop at KDD 2018 and ICDM 2019. His research interests include data mining, frequent pattern mining, sequence analysis and prediction, big data, and applications. Website: http://www.philippe-fournier-viger.com.
Speaker: Laszlo T. Koczy
Speaker: Laszlo T. Koczy
Title: Optimal routing in logistics by Discrete Bacterial Memetic Algorithm
Logistics transport routing problems usually lead to NP-hard mathematical graph search problems – so, they are theoretically unsolvable („intractable”) for larger instances. Nevertheless, to find high quality solutions to these routing tasks is very important because of several aspects. First of all, logistics companies aim at minimal costs of transport, in order to have more profitable operation. At the same time, it should be mentioned that transportation causes 20 % of the air pollution int he world, so the environmental awareness is an especially important issue of the same problem. Finding high quality (fast and precise) optimal or near-optimal routes may reduce not only the transportation costs thereby increasing the cost effectiveness of the company, but also the environmental load by reducing the emissions of air pollutants and greenhouse gases, which are supposedly the main causes of the climate change. As mentioned, these optimisation problems usually lead to NP-hard problems, so, no exact polynomial algorithm for solving them exists. For such purposes, a large variety of metaheuristics have been developed and have been used to solve, as efficient ones as possible, so as they find optimal or at least near-optimal but satisfactorily good solutions within reasonable time, with reasonable resource consumption.
These routing tasks can always be lead back to various NP-hard abstract mathematical search or optimisation problems, and researchers have proposed a very large number and variety of tailor made meta-heuristics for the most frequent ones, which have often been developed in a way entirely focused on a particular type of task, and have been based on the deep analysis of the particular problem on hand, but there are more generally applicable evolutionary, memetic (combined evolutionary and classic), population based and other problem-specific solutions available, too. While these methods are tackling one particular abstract problem, it may be an important direction of research to develop some more generally, in a way „universally” applicable, method or methods, especially because those abstract problems are usually not exactly suitable to address the real life problems of logistics companies, which are much more complex, with non-deterministic and uncertain elements, time variance, and other similar complicating issues. Our team has developed a new metaheuristic algorithm, the Discrete Bacterial Memetic Evolutionary Algorithm (DBMEA), which combines a rather efficient evolutionary approch proposed some decades ago by Furuhashi and colleagues, adding local search techniques coming from traditional graph theory. In addition, intensive development work concerning the speed-up of the actual implementation added tremendously to the efficiency of the actual DBMEA program package.
Our new algorithm was tested on several types of related transportation optimisation problems subsequently:
- the Traveling Salesman Problem (TSP) itself, and its various extensions which can model the practical logistics problems better than the original TSP, such as
- the Traveling Salesman Problem with Time Windows where the nodes need to be visited within pre-specified time periods,
- the Traveling Repairman Problem which is a cumulative version of the TSP,
- the Time Dependent Traveling Salesman Problem where the costs between the nodes vary in time depending on geographical location and the period of time (wekkly and dayly variation) and
- the One-commodity Pickup-and-Delivery Traveling Salesman Problem (1-PDTSP). In the latter the customers are divided into two groups: the delivery (they supply a given amount of product) and pickup customers (they demand a given amount of product). The values of demanded or delivered amounts are assigned individually to each node. The products are transported with one vehicle which has a maximum capacity.
The experience with testing the new algorithm on benchmark data on this set of more and more real life level tasks was rather promising, as the quality of the approximation results has proved rather good, often delivering the exact optimum, but in every case at least a very good approximation of the optimum. The totally new feature is here, that the SAME algorithm performed very well for a variety of equally difficult (complex) logistics optimisation tasks. Encouraged by these results we started to work on more realistic (and more complex) issues, which model the actual problems emerging in company practice by introducing the uncertainty element into the optimisation problems. We have introduced two entirely new real life motivated approaches:
- the Triple Fuzzy Time Dependent (3F-TDTSP) Traveling Salesman Problem and
- the Intuitionistic Fuzzy Time Dependent Traveling Salesman Problem (IFTD TSP).
In the 3F-TDTSP the costs (times, route lengths) between the nodes, the regions affected by time variant traffic jams and the rush hour periods when these traffic jams occur, are described with help of traditional fuzzy sets, while in the IFTD TSP problem we use intuitionistic fuzzy sets covering double uncertainty (membership and non-membership functions) for the purpose of expressing uncertainty in both the actual phenomena and the perception of this issue by the model constructing experts.
The DBMEA was tested on a large number of bechmark problems, available in publicly accessibble data repositories. Unfortunately, the amount and scope of the benchmarks examined by other authors is far from being homogeneous, and comparisons could be only made with existing results of other authors. So, our simulation results in the case of the above mentioned routing tasks were compared with all the available state-of-the-art approaches for all the examined optimisation problems.
Summarising, the DBMEA found optimal or close-optimal solutions for all types of problems. For the Traveling Repairman Problem, the DBMEA outperformed even all the state-of-the-art methods. In some other case it may be best approach, buti t would need further details on other authors’ results to state that with certainty. An additional feature of our new approach is that the runtime is much more predictable in he case of the DBMEA than most other algorithms published. In one of the contributed lectures presented at this conference we overview the most recent results concerning the approximated uniform complexities of all the up-to-date results and those of the DBMEA for the same type of problem. The comparison is based on non-linear correlation and evaluation of the squared error. For more details, please read the referred paper.
At the end of the talk some simple real life applications will be mentioned where we have done actual project work in collaboration with companies.
Speaker: Chattrakul Sombattheera
Speaker: Chattrakul Sombattheera
Title: A Hands-on Introduction to OpenCV
INVITED TALKS AND TUTORIALS
Philippe Fournier-Viger, Ph.D
School of Natural Sciences and Humanities
Harbin Institute of Technology, Shenzhen, China
Department of Computer Sciences
University of Quebec in Montreal, QC, Canada
Title & Abstract [click here]
Laszlo T. Koczy, Ph.D
Szechenyi Istvan University and Budapest University of Technology and Economics, Hungary
Title, Abstract & Materials [click here]