Call for chapters: High Utility Pattern Mining, the book

CALL FOR CHAPTERS

High-Utility Pattern Mining: Theory, Algorithms and Applications

Editors: Philippe Fournier-Viger, Chun-Wei Lin, Roger Nkambou, Bay Vo

An edited book to be published by Springer in 2018

Introduction

This book will provide an introduction to the high utility mining, reviews state-of-the-art techniques, and discusses recent advances.  The book will contains several chapters, contributed by authors.

Book aims

  • Presents an overview of the theory and core methods used in utility mining
  • Covers recent advances on high utility mining
  • Covers stream, incremental, sequence and the big data paradigm.
  • Discusses important applications and open-source software.

Important dates

If you wish to write a chapter, please submit a chapter proposal by according to the following deadlines:

Chapter proposal deadline: 1st October 2017
Proposal acceptance date: 10th October 2017
Full chapter submission deadline: 15th January 2018
Planned publication date: 1st July 2018

Topics of interest (not limited to):

  • high-utility itemset mining
  • high-utility sequential patterns and rules
  • incremental high-utility itemset mining
  • utility mining in streams
  • utility mining in uncertain databases
  • utility mining in big data
  • concise representations of utility patterns
  • periodic, recent, high utility patterns
  • visualization techniques.
  • privacy preserving utility mining
  • open-source software
  • application

A chapter can be either a survey of a topic of interest or be a research paper.

Submission

Interested researchers are invited to submit a chapter proposal clearly stating your focused problems and contributions related to one of the above topics due on the 1st October 2017. This must include a proposed titleabstractauthor list with names/affiliations/e-mails, and a brief description of the organization of your chapter in terms of sections and content. Authors of accepted chapters will be notified by the 10th October 2017. Full chapters are due by the 15th January 2018. The Springer LaTeX template for multi-author books must be used for chapters..

Enquiries and submissions can be sent to Philippe Fournier-Viger
(philfv8@yahoo.com)

Further information are on the website of the book

Related posts:

Posted in Big data, Data Mining, Data science, Research, Utility Mining | Tagged , , , , | Leave a comment

Introduction to the Apriori algorithm (with Java code)

This blog post provides an introduction to the Apriori algorithm, a classic data mining algorithm for the problem of frequent itemset mining. Although Apriori was introduced in 1993, more than 20 years ago, Apriori remains one of the most important data mining algorithms, not because it is the fastest, but because it has influenced the development of many other algorithms.

apriori algorithm

The problem of frequent itemset mining

The Apriori algorithm is designed to solve the problem of frequent itemset mining. I will first explain  this problem with an example. Consider a retail store selling some products. To keep the example simple, we will consider that the retail store is only selling five types of products: I= {pasta, lemon, bread, orange, cake}.   We will call these products “items”.

Now, assume that the retail store has a database of customer transactions:

Apriori transaction database

This database  contains four transactions. Each transaction is a set of items purchased by a customer (an itemset).  For example, the first transaction contains the items pasta, lemon, bread and orange, while the second transaction contains the items pasta and lemon. Moreover, note that each transaction has a name called its transaction identifier. For example, the transaction identifiers of the four transactions depicted above are T1, T2, T3 and T4, respectively.

The problem of frequent itemset mining is defined as follows. To discover frequent itemsets, the user must provide a transaction database (as in this example) and must set a parameter called the minimum support threshold (abbreviated as minsup).  This parameter represents the number of transactions that an itemset should at least appear in to be considered a frequent itemset and be shown to the user. I will explain this with a simple example.

Let’s say  that the user sets the minsup parameter to two transactions (minsup = 2 ). This means that the user wants to find all sets of items that are purchased together in at least two transactions. Those sets of items are called frequent itemsets. Thus, for the above transaction database,  the answer to this problem is the following set of frequent itemsets:

{lemon}, {pasta}, {orange}, {cake}, {lemon, pasta}, {lemon, orange}, {pasta, orange}, {pasta, cake}, {orange, cake}, {lemon, pasta, orange}

All these itemsets are considered to be frequent itemsets because they appear in at least two transactions from the transaction database.

Now let’s be a little bit more formal. How many times an itemset is bought is called the support of the itemset. For example, the support of {pasta, lemon} is said to be 3 since it is appears in three transactions. Note that the support can also be expressed as a percentage. For example, the support of {pasta, lemon} could be said to be 75% since pasta and lemon appear together in 3 out of 4 transactions (75 % percent of the transactions in the database).

Formally, when the support is expressed as a percentage, it is called a relative support, and when it is expressed as a number of transactions, it is called an absolute support.

Thus, the goal of frequent itemset mining is to find the sets of items that are frequently purchased in a customer transaction  database (the frequent itemsets).

Applications of frequent itemset mining

Frequent itemset mining is an interesting problem because it has applications in many domains. Although, the example of a retail store is used in this blog post, itemset mining is not restricted to analyzing customer transaction databases. It can be applied to all kind of data from biological data to text data. The concept of transactions is quite general and can be viewed simply as a set of symbols. For example, if we want to apply frequent itemset mining to text documents, we could consider each word as an item, and each sentence as a transaction. A transaction database would then be a set of sentences from a text, and a frequent itemset would be a set of words appearing in many sentences.

The problem of frequent itemset mining is difficult

Another reason why the problem of frequent itemset mining is interesting is that it is a difficult problem. The naive approach to solve the problem of itemset mining is to count the support of all possible itemsets and then output those that are frequent. This can be done easily for a small database as in the above example.  In the above example, we only consider five items  (pasta, lemon, bread, orange, cake). For five items, there are 32 possible itemsets. I will show this with a picture:

In the above picture, you can see all the sets of items that can be formed by using the five items from the example. These itemsets are represented as a Hasse diagram.  Among all these itemsets, the following itemsets highlighted in yellow are the frequent itemsets:

frequent itemsets

Now, a good question is: how can we write a computer program to quickly find the frequent itemsets in a database? In the example, there are only 32 possible itemsets. Thus, a simple approach is to write a program that calculate the support of each itemset by scanning the database. Then, the program would output the itemsets having a support no less than the minsup threshold to the user as the frequent itemsets.  This would work but it would be highly inefficient for large databases. The reason is the following.

In general, if a transaction database has items, there will be  2^x possible itemsets (2 to the power of x).  For example, in our case, if we have 5 items, there are 2^5 = 32 possible itemsets. This is not a lot because the database is small. But consider a retail store having 1,000 items. Then the number of possible itemsets would be:  2^1000 = 1.26 E30, which is huge, and it would simply not be possible to use a naive approach to find the frequent itemsets.

Thus, the search space for the problem of frequent itemset mining is very large, especially if there are many itemsets and many transactions. If we want to find the frequent itemsets in a real-life database, we thus need to design some fast algorithm that will not have to test all the possible itemsets.  The Apriori alorithm was designed to solve this problem.

The Apriori algorithm

The Apriori algorithm is the first algorithm for frequent itemset mining. Currently, there exists many algorithms that are more efficient than Apriori. However, Apriori remains an important algorithm as it has introduced several key ideas used in many other pattern mining algorithms thereafter. Moreover, Apriori has been extended in many different ways and used for many applications.

Before explaining the Apriori algorithm, I will introduce two important properties.

Two important properties

The Apriori algorithms is based on two important properties for reducing the search space. The first one is called the Apriori property (also called anti-monotonicity property). The idea is the following. Let there be two itemsets X and Y such that X is a subset of Y.  The support of X must be less than or equal to the support of Y.  In other words, if we have two sets of items  X and Y such that X is included in Y,  the number of transactions containing Y must be the same or less than the number of transactions containing X.  Let me show you this with an example:Apriori property

As you can see above, the itemset {pasta} is a subset of the itemset {pasta, lemon}. Thus, by the Apriori property the support of {pasta,lemon} cannot be less than the support of {pasta}. It must be equal or less than he support of {pasta}.

This property is very useful for reducing the search space, that is to avoid considering all possible itemsets when searching for the frequent itemsets. Let me show you this with some illustration.  First, look at the following illustration of the search space:Apriori search space

In the above picture, we can see that we can draw a line between the frequent itemsets (in yellow) and the infrequent itemsets (in white). This line is drawn based on the fact that all the supersets of an infrequent itemset must also be infrequent due to the Apriori property.  Let me illustrate this more clearly. Consider the itemset {bread} which is infrequent in our example because its support is lower than the minsup threshold. That itemset is shown in red color below.

Apriori search space bread

Then, based on the Apriori property, because bread is infrequent, all its supersets must be infrequent. Thus we know that any itemset containing bread cannot be a frequent itemset. Below, I have colored all these itemsets in red to make this more clear.

Apriori search space bread 2

Thus, the Apriori property is very powerful.  When an algorithm explores the search space, if it finds that some itemset (e.g. bread) is infrequent, we can avoid considering all itemsets that are supersets of that itemset (e.g. all itemsets containing bread).

A second important property used in the Apriori algorithm is the following.  If an itemset contain a subset that is infrequent, it cannot be a frequent itemset. Let me show an example:

Apriori subset property

The property say that if we have an itemset such as {bread, lemon} that contain a subset that is infrequent such as {bread}, then the itemset cannot be frequent. In our example, since {bread} is infrequent, it means that {bread, lemon} is also infrequent.  You may think that this property is very similar to the first property!  Actually, this is true. It is just a different way of writing the same property. But it will be useful for explaining how the Apriori algorithm works.

The Apriori algorithm

I will now explain how the Apriori algorithm works with an example, as I want to explain it in an intuitive way.  But first, let’s remember what is the input and output of the Apriori algorithm. The input is (1) a transaction database and (2) a minsup threshold set by the user.  The output is the set of frequent itemsets.  For our example, we will consider that minsup = 2 transactions.

The Apriori algorithm is applied as follows. The first step is to scan the database to calculate the support of all items (itemsets containing a single items). The results is shown belowapriori_step1

After obtaining the support of single items, the second step is to eliminate the infrequent itemsets.  Recall that the minsup parameter is set to 2 in this example. Thus we should eliminate all itemsets having a support that is less than 2. This is illustrated below:

apriori_step2

We thus now have four itemsets left, which are frequent itemsets. These itemsets are thus output to the user. All these itemsets each contain a single item.

Next the Apriori algorithm will find the frequent itemsets containing 2 items. To do that, the Apriori algorithm combines each frequent itemsets of size 1 (each single item) to obtain a set of candidate itemsets of size 2 (containing 2 items). This is illustrated below:

apriori step 3

Thereafter, Apriori will determine if these candidates are frequent itemsets. This is done by first checking the second property, which says that the subsets of a frequent itemset must also be frequent. For the candidates of size 2, this would be done by checking if the subsets containing 1 items are also frequent. For the candidate itemsets of size 2, it is always true, so the Apriori algorithm does nothing.

apriori step 4

Then, the next step is to scan the database to calculate the exact support of the candidate itemsets of size 2, to check if they are reallyfrequent. The result is as follows.

apriori step 5

Based on these support values,  the Apriori algorithm next eliminates the infrequent candidate itemsets of size 2. The result is shown below:

apriori 6As a result, there are only five frequent itemsets left.  The Apriori algorithm will output these itemsets to the user.

Next, the Apriori algorithm will try to generate candidate itemsets of size 3. This is done by combining pairs of frequent itemsets of size 2.  This is done as follows:

apriori step 7

Thereafter, Apriori will determine if these candidates are frequent itemsets. This is done by first checking the second property, which says that the subsets of a frequent itemset must also be frequent.  Based on this property, we can eliminate some candidates. The Apriori algorithm checks if there exists a subset of size 2 that is not frequent for each candidate itemset. Two candidates are eliminated as shown below.

apriori 8

For example, in the above illustration, the itemset {lemon, orange, cake} has been eliminated because one of its subset of size 2 is infrequent (the itemset {lemon cake}).  Thus, after performing this step, only two candidate itemsets of size 3 are left.

Then, the next step is to scan the database to calculate the exact support of the candidate itemsets of size 3, to check if they are really frequent. The result is as follows.

apriori step 9

Based on these support values,  the Apriori algorithm next eliminates the infrequent candidate itemsets of size 3 o obtain the frequent itemset of size 3. The result is shown below:

step 10 apriori

There was no infrequent itemsets among the candidate itemsets of size 3, so no itemset was eliminated.  The two candidate itemsets of size 3 are thus frequent and are output to the user.

Next, the Apriori algorithm will try to generate candidate itemsets of size 4. This is done by combining pairs of frequent itemsets of size 3.  This is done as follows:

apriori step 11

Only one candidate itemset was generated. hereafter, Apriori will determine if this candidate is frequent. This is done by first checking the second property, which says that the subsets of a frequent itemset must also be frequent.  The Apriori algorithm checks if there exist a subset of size 3 that is not frequent for the candidate itemset.

apriori 12

During the above step,  the candidate itemset {pasta, lemon, orange, cake} is eliminated because it contains at least one subset of size 3 that is infrequent. For example, {pasta, lemon cake} is infrequent.

Now, since there is no more candidate left. The Apriori algorithm has to stop and do not need to consider larger itemsets (for example, itemsets containing five items).

The final result found by the algorithm is this set of frequent itemsets.

frequent itemsets found

Thus, the Apriori algorithm has found 11 frequent itemsets. The Apriori algorithm is said to be a recursive algorithm as it recursively explores larger itemsets starting from itemsets of size 1.

Now let’s analyze the performance of the Apriori algorithm for the above example. By using the two pruning properties of the Apriori algorithm, only 18 candidate itemsets have been generated. However, there was 31 posible itemsets that could be formed with the five items of this example (by excluding the empty set). Thus, thanks to its pruning properties the Apriori algorithm avoided considering 13 infrequent itemsets. This may not seems a lot, but for real databases, these pruning properties can make Apriori quite efficient.

It can be proven that the Apriori algorithm is complete (that it will find all frequent itemsets in a given database) and that it is correct (that it will not find any infrequent itemsets). However, I will not show the proof here, as I want to keep this blog post simple.

Technical details

Now, a good question is how to implement the Apriori algorithm. If you want to implement the Apriori algorithm, there are more details that need to be considered.  The most important one is how to combine itemsets of a given size k to generate candidate of a size k+1.

Consider an example.  Let’s say that we combine frequent itemsets containing 2 items to generate candidate itemsets containing 3 items. Consider that we have three itemsets of size 2 : {A,B}, {A,E} and {B,E}.

A problem is that if we combine  {A,B} with {A,E}, we obtain {A,B,E}.  But if we combine {A,E} with {B,E}, we also obtain {A,B,E}. Thus, as shown in this example, if we combine all itemsets of size 2 with all other itemsets of size 2, we may generate the same itemset several times and this will be very inefficient.

There is a simple trick to avoid this problem. It is to sort the items in each itemset according to some order such as the alphabetical order. Then, two itemsets should only be combined if they have all the same items except the last one.

Thus, {A,B} and {A,E}  can be combined since only the last item is different.  But  {B,E} and {A,E} cannot be combined since some items are different that are not the last item of these itemsets. By doing this simple strategy, we can ensure that Apriori will never generate the same itemset more than once.

I will not show the proof to keep this blog post simple. But it is very important to use this strategy when implementing the Apriori algorithm.

How is the performance of the Apriori algorithm?

In general the Apriori algorithm is much faster than a naive approach where we would count the support of all possible itemsets, as Apriori will avoid considering many infrequent itemsets.

The performance of Apriori can be evaluated in real-life in terms of various criteria such as the execution time, the memory consumption, and also its scalability (how the execution time and memory usage vary when increasing the amount of data). Typically, researchers in the field of data mining will perform numerous experiments to evaluate the performance of an algorithm in comparison to other algorithms.  For example, here is a simple experiment that I have done to compare the performance of Apriori with other frequent itemset mining algorithms on a dataset called “Chess“.chess dataset

In that experiment, I have varied the minimum support threshold to see the influence on the execution time of the algorithms. As the threshold is set lower, more patterns need to be considered and the algorithms become slower. It can be seen that Apriori performs quite well but is still much slower than other algorithms such as Eclat and FPGrowth.  This is normal since the Apriori algorithm actually has some limitations that have been addressed in newer algorithms. For example, Apriori is an algorithm that can generate candidate itemsets that do not exist in the database (have a support of 0). More recent algorithms such as FPGrowth are designed to avoid this problem. Besides, note that here, I just show results on a single dataset. To perform a complete performance comparison, we should consider more than a single dataset. But I just show this as an example in this blog post. The experiment shown here was run with the SPMF data mining software which offers open-source implementations of Apriori and many other pattern mining algorithms in Java.

Source code and more information about Apriori

In this blog post, I have aimed at giving a brief introduction to the Apriori algorithm. I did not discuss optimizations, but there are many optimizations that have been proposed to efficiently implement the Apriori algorithm.

If you want to know more about Apriori, you could read the original paper by Agrawal published in 1993:

Rakesh Agrawal and Ramakrishnan Srikant Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.

To try Apriori, you can obtain a fast  implementation of Apriori as part of the SPMF data mining software, which is implemented in Java under the GPL3 open-source license.  The source code of Apriori in SPMF is easy to understand, fast, and lightweight (no dependencies to other libraries).

On the website of SPMF, examples and datasets are provided for running the Apriori algorithm, as well as more than 100 other algorithms for pattern mining. The source code of algorithms in SPMF has no dependencies to other libraries and can be easily integrated in other software. The SPMF software also provides a simple user-interface for running algorithms:apriori algorithm spmf

Besides, if you want to know more about frequent itemset mining, I recommend to read my recent survey paper about itemset mining . It is easy to read and goes beyond what I have discussed in this blog post. The survey paper is more formal, gives pseudocode of Apriori and other algorithms,  and also discusses extensions of the problem of frequent itemset mining and research opportunities.

Hope you have enjoyed this blog post! 😉

Philippe Fournier-Viger is a professor of computer science and founder of the SPMF data mining library.

Related posts:

Posted in Big data, Data Mining, Data science, Open-source | Tagged , , , , , | Leave a comment

Do not link to impact factors, they will censor you!

On July 20 2017, I received an e-mail from a company called Clarivate Analytics Trademark Enforcement ( legal@ip-clarivateanalytics.com ) about copyright infringement for the Journal Citation Reports, a product by Thomson Reuters.

They contact with me because a few years ago I have created a webpage that provides a list of useful links for researchers such as how to check if a journal is indexed by SCI, SCIE, IS, etc.  It is a very simple webpage that do not host any copyright data, and is very useful for researchers. You can see a screenshot below:

A webpage with links

Copryight claim

So what is the problem with this webpage? Well, the company did not like that I linked to two websites called SCIJ***nal.org  and bioxb…com  that provide the impact factors of journals, which is a very useful information for researchers.  They asked me to remove these two links as these websites apparently contain copyrighted data (the impact factors).

It should be clear that I do not host this data on my website, and I do not own these two websites either. Thus I am not responsible for their content. However, I have still decided to censor the links as you can see above, although I probably do not have to since linking to a website is generally not considered copyright infridgment.

A problem for academia

So what does this tells us about Thomson Reuters? I think that they would expect every researcher to pay to access the impact factors. But not all universities have the funding to pay to access this data, which is very inconvenient for young researchers or people working in small universities or less developed countries. To avoid such problems, I think that as researchers, we should try to move away from impact factors provided by a company.  An impact factor is basically just calculated using some simple math formula using data provided by journals. There should be a way to have alternatives to these impact factors that are not calculated or owned by a company.  

The Streisand effect

Besides, can they really expect to censor links to these two websites all over the Internet? In the past, many people have failed to do this, and this has backfired. For example, there is the well known Streisand effect where the fact of trying to hide something makes it even more popular.

This is all I wanted to write for today. Just wanted to share this story.

By the way, all the names mentioned in this blog posts belong to the respective companies.

Related posts:

Posted in Academia, General | Tagged , , , | Leave a comment

How to publish in top conferences/journals? (Part 2) – The opportunity cost of research

Many researchers wish to produce high quality papers and have a great research impact. But how? In a previous blog post, I have discussed how the “blue ocean strategy” can be applied to publish in top conference/journal. In this blog post, I will discuss another important concept for producing high impact research, which is to consider the opportunity cost of research.

Opportunity cost in research

Opportunity cost

The concept of opportunity cost is widely used in the field of economy. I will explain this concept and then explain how it can be applied to research. Consider a situation where you must choose between several mutually exclusive choices C1, C2, … Cn.  If you choose a choice Cx, then you cannot choose the other choices because they are mutually exclusive with Cx.  Thus, by making a choice Cx, you may be getting some benefits, but you may miss other benefits that could be obtained when making other choices. In other words, when we make a choice in a given situation, we not only get the rewards or benefits that goes with that choice but we also lose other benefits that we could have obtained if we had made other choices.  The opportunity cost for making a choice Cx is thus the lost of benefits caused by not making other alternative choices.

Applying the concept of opportunity cost in research

The concept of opportunity cost is simple but very useful in many domains, and considering it allows to take better decisions. When making a choice between multiple alternatives, we should not only think about the direct benefits of that choice but also at the missed opportunities from other alternative choices (the opportunity cost).

How does that applies to research?  Well, in research, a researcher has multiple resources (times, money, students). In terms of time, when a researcher decides to spend time on a given project, he may as a result not have time to work on alternative research projects. Thus, given the limited amount of time that a researcher has, he must carefully choose between multiple research opportunities to maximize his benefits.

For example, it is tempting for several young researchers to write several papers with simple an unoriginal ideas, just to publish papers as quickly as possible. This may seems like a good idea in the short term. However,  the hidden opportunity cost of doing so is that the time spent on writing these simple papers cannot be spent to work on better research ideas that take more time to develop but may result in a higher impact on the long term.

Thus, from the perspective of opportunity cost, a researcher should try to choose carefully the research projects that are promising and spend more time to develop these projects and make good papers out of it, rather than to try to write as many papers as possible.

From my experience, even the most simple conference papers requires at least 1 or 2 weeks of work that could be spend on better research projects. The fastest paper that I have written for a conference was done in about 1 week, several years ago. But still,  even if it only takes a week, one should not forget that additional time needs to be spent to travel, prepare a PowerPoint, and present the paper at a conference. Thus, totally, the cost in terms of time for a quick conference paper may still add up to two weeks or more. And then, as explained, the opportunity cost of writing a simple paper is that one may not have enough time to work on better or more promising research ideas.  Thus, in recent years, I have shifted my focus to target better conferences and journals and focus less on smaller conferences.  I write less papers but these papers are of higher quality and can have a greater impact.

Of course, many other factors must be considered to publish high quality papers such as the choice of a good research topic. But in this blog post, I wanted to highlight the concept of opportunity cost.

Conclusion

In this blog post, I have highlighted how opportunity cost is applicable to research in academia. I personally think that it is an important concept, as many researchers are tempted to publish as many papers as possible without focusing much on quality, and often without realizing that that time could be spent on better research ideas. But producing high impact research requires to spend a considerable amount of time. Thus, one should carefully chose to spend more time on promising projects, rather than focusing too much on quantity. Besides time, the concept of opportunity cost is also applicable to other kinds of resources such as funding and students.

If you like this blog, you can subscribe to the RSS Feed or my Twitter account (https://twitter.com/philfv) to get notified about future blog posts

Related posts:

Posted in Academia, Data Mining, Research | Tagged , | 1 Comment

Plagiarism by K. Raghu Naga Dhareswararao, T. Kishore

After the recent case of plagiarism at the  Ilahia college of engineering that I have reported recently, where no actions was taken at all to punish the professors who have plagiarized my paper, I have found today that another of my papers has been plagiarized by some Indian researchers.

I will write a short blog post about this topic because I am a little bit tired of writing about people from India who are plagiarizing my papers, as it happens several times every year. There are some excellent researchers in India. In my opinion, the problem of plagiarism is mostly in smaller colleges.

The plagiarized paper is published in an unknown journal named IJSEAT (International Journal of Science Engineering and Advance Technology). The title of this journal is very broad covering all fields of science and technology. Usually, this kind of journal is set up just for money by choosing a title as general as possible to collect more papers.

The paper is named  “AN SUITABLE MINIMUM UTILITY THRESHOLD BY TRIAL AND ERROR IS A TEDIOUS PROCESS FOR USERS” and is written by K. Raghu Naga Dhareswararao, T. Kishore ( http://ijseat.com/index.php/ijseat/article/view/852 )

Kishore_Kakinada_institute_of_engineering

The title of the paper already shows that the authors are not good at English writing.  It should be  “A suitable” rather than “An suitable”.

Then, there is the abstract:

We address the above issues by proposing another system for top-k high utility itemset mining, where k is the coveted number of HUIs to be mined. Two sorts of effective calculations named TKU (mining Top-K Utility item sets) and TKO (mining Top-K utility item sets in One stage) are proposed for mining such item sets without the need to set min util. We give a basic correlation of the two calculations with exchanges on their preferences and constraints. Exact assessments on both genuine and engineered datasets demonstrate that the execution of the proposed calculations is near that of the ideal instance of cutting edge utility mining algorithms.

In this abstract, the authors basically claim that the have proposed the TKU and TKO algorithms presented in a TKDE paper that I have co-authored.  That paper is not cited. Thus it is a clear case of plagiarism, which is unacceptable.

What will happen?

As I usually do, I will first send an e-mail to the editors of that journal to ensure that it will be retracted. Then I will send an e-mail to the department of their university so that punishment might be given to these authors.  In the past, this has generally worked. All the journals that I have contacted have retracted the plagiarized papers. However, some colleges like the Ilahia college of engineering and Galgotias college have simply ignored the cases of plagiarism that have happened in their colleges, by taking no actions at all. For example, I have contacted the head of department and principal of the Ilahia college of engineering  multiple times over several months before receiving an answer, and still no punishment was given.  Thus, in these colleges, the professors who committed plagiarism are still working as if nothing happened, which is a shame. In any western country, a professor committing plagiarism would likely be fired.

Anyway, I just write this blog post so that people know about these cases of plagiarism.

Related posts:

Posted in Academia, Plagiarism, Research | Tagged , , | Leave a comment

The PAKDD 2017 conference (a brief report)

This week, I have attended the PAKDD 2017 conference in Jeju Island, South Korea, this week, from the 23 to 26th May.  PAKDD is the top data mining conference for the asia-pacific region. It is held every year in a different pacific-asian country. In this blog post, I will write a brief report about the conference.

PAKDD 2017 LOGO

Conference location

The conference was held in the city of Seogwipo on Jeju island, a beautiful island in South Korea, which is famous for tourism, especially in Asia. Here is a map of the location.

PAKDD 2017 location

In particular, the conference was held at the Seogwipo KAL hotel.

PAKDD 2017 hotel korea

The hotel was well-chosen. It is about 1 km from the city, beside the sea.

Conference proceedings

The proceedings of the PAKDD conference are published by Springer in the Lecture Notes in Artificial Intelligence series. This ensures a good visibility to the papers published in the proceedings, which are indexed in the main computer science indexes such as DBLP.

The proceedings were given on a USB drive (4 Gb) rather than as a book, as many other conferences have been doing in recent years. Personally, I like to have proceedings as books, but USB drives are probably more friendly for the environment.

PAKDD 2017 proceedings

In general the quality of the papers at PAKDD conferences is good. This year,  458 papers were submitted. Among those, 45 papers were accepted as long papers and 84 as short papers. Thus, the global acceptance rate was about 28%.

Below, I present various slides from the opening ceremony presentation, which provides information about the PAKDD conference this year.

  1. The number of papers per category (submitted / accepted) is shown below. It is interesting to see that a large amount of applications and social network papers have been rejected. And for the topic of sequential data,  only 1 paper out of 10 was accepted.

PAKDD papers per category

2) The number of accepted long and short papers at PAKDD forthe last six years is presented below.PAKDD accepted papers

3) The decision criteria for accepting a paper at PAKDD are shown below.PAKDD decision criteria

4) There was 283 persons who have registered for PAKDD this year.PAKDD registration

5) The acceptance rate of long and short papers at PAKDD during the last six years PAKDD acceptance rate

6) The number of submitted vs accepted papers by country this year.  We can observe that China has the largest number of papers accepted and submitted.

PAKDD per country

 

Day 1 – workshops and tutorials, reception

On the first day, the registration started at 8:00 AM.

PAKDD 2017 registration

It was then followed by various workshops and tutorials. I have attended a workshop about Biologically Inspired Data Mining, a popular topic, which covers the applications of algorithms such as neural networks, bee swarm optimization, genetic algorithms, and ant colony optimization, to solve data mining problems. Evolutionary algorithms are quite interesting as they can  find approximate solutions to data mining problems that are quite good solutions, while running much faster than traditional algorithms that  find an optimal solution.  There was also some tutorials that I did not attend on information retrieval, recommender systems and tensor analysis. Besides, there was workshops on security, business process management, and sensor data analytics.

In the evening, there was a reception, which was a good opportunity for discussing with other researchers.

Day 2 – main conference, opening ceremony

There was an opening ceremony, followed by a keynote by Sang Kyun Cha from the Seoul National University of Korea. The keynote was about a potential fourth industrial revolution that would occurs due to the growth of AI-based services and big data technologies. This would lead to a need for more skilled workers such as engineers or “data scientists”. The talk was interesting but personally I prefer talks that are a little bit more technical. After that, there was multiple sessions of paper presentations.

Besides technical sessions, I also discussed with some representatives from Nvidia who were promoting a new supercomputer specially designed for training deep learning neural networks. It is called NVIDIA DGX-1 and costs around 200,000 $ USD. According to the promotional material, this computer has a eight Tesla P100 GPUs, each with 16 GB of memory, a total of 28672 NVIDIAN CUDA cores, and two dual 20-core Intel Xeon E5-2698 v4 2.2 Ghz processors. But what is the most interesting is that this GPU based system is claimed to be 250 times faster than a conventional CPU-only server for deep learning. I saw that there is also a similar product by IBM called the IBM Minsky, also equipped with NVidia GPUs.  This is especially interesting for those working on deep learning related topics.

NVidia DGX1

NVidia DGX1

Day 3 – main conference, excursion, banquet

On the third day of the conference, there was a keynote speech by Rakesh Agrawal, a senior researcher, who is one of the founder of data mining.  The talk was about the usage of social data.. The main question addressed in this talk was whether social data from websites such as Twitter is garbage or it can be useful for businesses.  R. Agrawal presented a project that he carried a few years ago at Microsoft where he analyzed Twitter data to study the opinion of people about Microsoft products. He also described a work where he compared the results of the Bing and Google search engines, and the result obtained when searching using social data rather than traditional search engines. The conclusion was that social data is certainly useful. R. Agrawal also gave some advices that young researchers should try to choose good research topics that are useful and can have an impact rather than just focusing on publishing a paper as quickly as possible.

Rakesh Agrawal PAKDD

On the afternoon, there was an excursion to Seopjikoji beach,  Seongsan Sunrise Peak and Seongeup Folk Village.

PAKDD excursion PAKDD excursion 2

In the evening, there was a banquet at the Seogwipo KAL hotel, with a musical performance.

Day 4 – main conference, closing ceremony

On the fourth day, there was a keynote by Dacheng Tao, from the University of Sydney Australia about current challenges in artificial intelligence. It was followed by several technical sessions, a lunch and a closing ceremony.

Conclusion

The conference was quite interesting. I had the occasion to meet many interesting people from academia and also from industry (e.g. Microsoft, Yahoo, Adobe, Nvidia). PAKDD is not the largest conference in data mining but it is a quite good conference, especially for the asia-pacific region, and the quality of the papers is quite high.  It was announced that next year, the PAKDD 2018 conference will be held in Melbourne, Australia. I will certainly try to attend it.

By the way, I had previously written a report about the PAKDD 2014 conference in Taiwan. You may have a look also at that report if you are interested by PAKDD.

Hope you have enjoyed this post!


Philippe Fournier-Viger is a professor of Computer Science and also the founder of the open-source data mining software SPMF, offering more than 120 data mining algorithms.

Related posts:

Posted in Academia, Big data, Conference, Data Mining, Data science | Tagged , , , | 2 Comments

Plagiarism by Bhawna Mallick and Kriti Raj at Galgotias College of Engineering & Technology

Today, I found that a paper written by Bhawna Mallick Kriti Raj and Himani from India is plagiarizing my papers. Those persons are affiliated to the  Galgotias College of Engg & Tech., India formerly known as Uttar Pradesh  Technical University.

The paper is called “Weather prediction using CPT+ algorithm” and was published in the International Journal Of Engineering And Computer Science ISSN: 2319-7242 Volume 5 Issue 5 May 2016, Page No. 16467-16470. (https://www.ijecs.in/issue/v5-i5/23%20ijecs.pdf ).

Bhawna Mallick Galgotias College of Engineering & Technology

Plagiarism by Bhawna Mallick Uttar at Galgotias College of Engineering & Technology

The paper is an obvious case of plagiarism as it copies several pages of my PAKDD 2015 paper about the CPT+ algorithm, published a year before ( http://www.philippe-fournier-viger.com/spmf/PAKDD2015_Compact_Prediction_tree+.pdf ).

The authors of the plagiarized paper,  Bhawna Mallick et al., claims to propose the CPT+ algorithm in their paper, and infringes our copyright by copying several pages of the paper, with figures and text, which is unacceptable.

Who is Bhawna Mallick, Kriti Raj  et al.?

I have done a little search to find who these persons are. According to the paper, their e-mails addresses are:

  • Bhawna Mallick. Galgotias College of Engg & Technology, Greater Noida, UP, India bhawna.mallick@galgotiacollege.edu
  • Kriti Raj. Galgotias College of Engg & Technology, Greater Noida, UP, India kritiraj31may@gmail.com
  • Himani.  Galgotias College of Engg & Technology, Greater Noida, UP, India himanichaprana@gmail.com

The website of the Galgotias College of Engineering & Technologycan be found here: http://www.galgotiacollege.edu/gcet.asp

Galgotias college plagiarism

Galgotias college plagiarism

And it can be found that Bhawna Mallick et al are affiliated to the Department of Computer Science and Engineering.  In particular,  it is possible to find the following information about Bhawna Mallick the first author of the plagiarized paper:

Prof. (Dr.) Bhawna Mallick Professor & HOD Data Mining and Fuzzy Logic

Apparently, Bhawna Mallick is professor and head of the department.  Here is a screenshot of her webpage:

http://www.galgotiacollege.edu/gei-courses/docse-faculty-bhawna-mallick.asp

Bhawna Mallick Uttar Pradesh Plagiarism

Bhawna Mallick (Galgotias College of Engg & Technology) homepage

The fact that this person is head of that department and put her name as first author on a plagiarized paper raises serious questions about the quality of that college.

Also it raises questions about the quality of that journal.

And who is Kriti Raj?

According to this LinkedIn page, he is a student at the Galgotias College:
https://www.linkedin.com/in/kriti-raj-06ab2574/

Kriti Raj Galgotia College Plagiarism

Kriti Raj Galgotia College Plagiarism

 

What will happen?

Well, this is not the first time that someone plagiarizes my papers. I stopped counting a while ago. I think that it has happened more than 10 times already in the last 7 years. So what I will do? I will send an e-mail to the Galgotias College of Engg & Technology to let them know about the situation, and I will ask them to take appropriate action. Moreover, I will ask that the journal paper be retracted  by contacting the journal editor.

Hopefully, the Galgotias College of Engg & Technology will take this problem of plagiarism seriously and take appropriate action to punish those responsible.  In India, this is not always the case. In another case of plagiarism that I had reported just a few months ago at the Ilahia College of Engineering and Technology, they have decided to simply ignore the e-mails and take no actions, which is very bad from an academic perspective.

Related posts:

Posted in Plagiarism | Tagged | 3 Comments

How to publish in top conferences/journals? (Part 1) – The Blue Ocean Strategy

A question that many young researchers ask is how to get your papers published in top conferences and journal.  There are many answers to this question. In this blog post, I will discuss a strategy for carrying research called the “Blue Ocean Strategy”.  This strategy was initially proposed in the field of marketing. But in this blog post, I will explain how it is also highly relevant in Academia.

The Blue Ocean Strategy was proposed in a 2007 book by Kim, C. W. and Mauborgne, R. The idea is quite simple. Let’s say that you want to start a new business and get rich. To start your business, you need to choose a market where your business will operate. Let’s say that you decide to start selling pens.  However, there are already a lot of pen manufacturers that are well-established and thus this market is extremely competitive and profit margins are very low. Thus, it might be very difficult to become successful in this market if you just try to produce pens like every other manufacturers. It is like jumping in a shark tank!

The Blue Ocean Strategy indicates that rather than fighting for some existing market, it is better to create some new markets (what is called a “blue ocean“). By creating a new market, the competition becomes irrelevant and you may easily get many new customers rather than fighting for a small part of an existing market. Thus, instead of trying to compete with some very well established manufacturer in a very competitive market (a “red ocean“), it is more worthy to start a new market (a “blue ocean”). This could be for example, a new type of pens that has some additional features.

Now let me explain how this strategy is relevant for academia.

In general,  there are two main types of research projects:

  • a researcher try to provide a solution to an existing research problem,
  • the researcher works on a new research problem.

The first case can be seen as a red ocean, since many researchers may be already working on that existing problem and it may be hard to publish something better. The second case is a blue ocean, since the researcher is the first one to work on a new topic. In that case, it can be easy to publish something since you do not need to do something better than other people, since you are the first one on that topic.

For example, I work in the field of data mining. In this field, many researchers work on publishing faster or more memory efficient algorithms for existing data mining problems. Although this research is needed, it can be viewed in some cases as lacking originality, and it can be very competitive to publish a faster algorithm.  On the other hand, if researchers instead work on proposing some new problems, then the research appears more original, and it becomes much more easy to publish an algorithm as it does not need to be more efficient than some previous algorithms.  Besides, from my observation, top conferences/journal often prefer papers on new problems to incremental work on existing problems.

Thus, it is not only easier to provide a solution to new research problem, but top conferences in some fields at least put a lot of value on papers that address new research problems. Thus, why fighting to be the best on an existing research problem?

Of course, there are some exceptions to this idea. If a researcher succeeds to publish some exceptional paper in a red ocean (on an existing research problem), his impact may actually be greater. This is especially if the research problem is very popular. But the point is that publishing in a red ocean may be harder than in a blue ocean.  And of course, not all blue oceans are equal. It is thus also important to find some good idea for new research topics (good blue oceans).

Personally, for these reasons, I generally try to work on “blue ocean” research projects.

Conclusion

In this blog post, I have discussed how the “Blue Ocean Strategy” and how it can be applied in academia to help in publishing in top conferences/journals. Of course, there are also a lot of other things to consider to write a good paper. You can read the follow up blog post on this topic here, where the opportunity cost of research is discussed.

If you like this blog and want to support it, please share it on social networks (Twitter, LinkedIn, etc.), write some comments, and continue reading other articles on this blog. 🙂

Related posts:

Posted in Academia, General, Research | Tagged , , , | 1 Comment

This is why you should visualize your data!

In the data science and data mining communities, several practitioners are applying various algorithms on data, without attempting to visualize the data.  This is a big mistake because sometimes, visualizing the data greatly helps to understand the data. Some phenomena are obvious when visualizing the data. In this blog post, I will give a few examples to convince you that visualization can greatly help to understand data.

An example of why using statistical measures may not be enough

The first example that I will give is a the Francis Anscombe Quartet.  It is a set of four datasets consisting of X, Y points. These four datasets are defined as follows:

Dataset I

Dataset II

Datset III

Dataset IV

x

y

x

y

x

y

x

y

10.0

8.04

10.0

9.14

10.0

7.46

8.0

6.58

8.0

6.95

8.0

8.14

8.0

6.77

8.0

5.76

13.0

7.58

13.0

8.74

13.0

12.74

8.0

7.71

9.0

8.81

9.0

8.77

9.0

7.11

8.0

8.84

11.0

8.33

11.0

9.26

11.0

7.81

8.0

8.47

14.0

9.96

14.0

8.10

14.0

8.84

8.0

7.04

6.0

7.24

6.0

6.13

6.0

6.08

8.0

5.25

4.0

4.26

4.0

3.10

4.0

5.39

19.0

12.50

12.0

10.84

12.0

9.13

12.0

8.15

8.0

5.56

7.0

4.82

7.0

7.26

7.0

6.42

8.0

7.91

5.0

5.68

5.0

4.74

5.0

5.73

8.0

6.89

To get a feel of the data, the first thing that many  would do is to calculate some statistical measures such as the mean, average, variance, and standard deviation.  This allows to measure the central tendency of data and its dispersion. If we do this for the four above datasets, we obtain:

Dataset 1:   mean of X = 9, variance of X= 11, mean of Y = 7.5, variance of Y = 4.125
Dataset 2:   mean of X = 9, variance of X= 11, mean of Y = 7.5, variance of Y = 4.125
Dataset 3:   mean of X = 9, variance of X= 11, mean of Y = 7.5, variance of Y = 4.125
Dataset 4:   mean of X = 9, variance of X= 11, mean of Y = 7.5, variance of Y = 4.125

So these datasets appears quite similar. They have exactly the same values for all the above statistical measures.  How about calculating the correlation between X and Y for each dataset to see how the points are correlated?

Dataset 1:   correlation 0.816
Dataset 2:  correlation 0.816
Dataset 3:  correlation 0.816
Dataset 4:  correlation 0.816

Ok, so these datasets are very similar, isn’t it?  Let’s try something else. Let’s calculate the regression line of each dataset (this means to calculate the linear equation that would best fit the data points).

Dataset 1:  y = 3.00 + 0.500x
Dataset 2:  y = 3.00 + 0.500x
Dataset 3:  y = 3.00 + 0.500x
Dataset 4:  y = 3.00 + 0.500x

Again the same!  Should we stop here and conclude that these datasets are the same?

This would be a big mistake because actually, these four datasets are quite different! If we visualize these four datasets with a scatter plot, we obtain the following:

Francis Anscombe Quartet

Visualization of the four datasets (credit: Wikipedia CC BY-SA 3.0)

This shows that these datasets are actually quite different. The lesson from this example is that by visualizing the data, difference sometimes becomes quite obvious.

Visualizing the relationship between two attributes

Simple visualizations techniques like scatter plots are also very useful for quickly analyzing the relationship between pairs of attributes in a dataset. For example, by looking at the two following scatter plots, we can quickly see that the first one show a positive correlation between the X and Y axis (when values on the X axis are greater, values on the Y axis are generally also greater), while the second one shows a negative correlation (when values on the X axis are greater, values on the Y axis are generally also smaller).

(a) positive correlation  (b) negative correlation (Credit: Data Mining Concepts and Techniques, Han & Kamber)

If we plot two attributes on the X and Y axis of a scatter plot and there is not correlation between the attributes, it may result in something similar to the following figures:

No correlation between the X and Y axis (Credit: Data Mining Concepts and Techniques, Han & Kamber)

These examples again show that visualizing data can help to quickly understand the data.

Visualizing outliers 

Visualization techniques can also be used to quickly identify outliers in the data. For example in the following chart, the data point on top can be quickly identified as an outlier (an abnormal value).

outlier scatter plot

Identifying outliers using a scatter plot

Visualizing clusters

In data mining, several clustering algorithms have been proposed to identify clusters of similar values in the data. These clusters can also often be discovered visually for low-dimensional data. For example, in the following data, it is quite apparent that there are two main clusters (groups of similar values), without applying any algorithms.

Two clusters

Data containing two obvious clusters

Conclusion

In this blog post, I have shown a few simple examples of how visualization can help to quickly see patterns in the data without actually applying any fancy models or performing calculations. I have also shown that statistical measures can actually be quite misleading if no visualization is done, with the classic example of the Francis Anscombe Quartet.

In this blog post, the examples are mostly done using scatter plots with 2 attributes at a time, to keep things simple. But there exists many other types of visualizations.


Philippe Fournier-Viger is a professor of Computer Science and also the founder of the open-source data mining software SPMF, offering more than 120 data mining algorithms.

Related posts:

Posted in Big data, Data Mining, Data science | Tagged , , , , | 3 Comments

An Introduction to Sequential Pattern Mining

In this blog post, I will give an introduction to sequential pattern mining, an important data mining task with a wide range of applications from text analysis to market basket analysis.  This blog post is aimed to be a short introductino. If you want to read a more detailed introduction to sequential pattern mining, you can read a survey paper  that I recently wrote on this topic.

What is sequential pattern mining?

Data mining consists of extracting information from data stored in databases to understand the data and/or take decisions. Some of the most fundamental data mining tasks are clustering, classification, outlier analysis, and pattern mining. Pattern mining consists of discovering interesting, useful, and unexpected patterns in databases  Various types of patterns can be discovered in databases such as frequent itemsets, associations, subgraphs, sequential rules, and periodic patterns.

The task of sequential pattern mining is a data mining task specialized for analyzing sequential data, to discover sequential patterns. More precisely, it consists of discovering interesting subsequences in a set of sequences, where the interestingness of a subsequence can be measured in terms of various criteria such as its occurrence frequency, length, and profit. Sequential pattern mining has numerous real-life applications due to the fact that data is naturally encoded as sequences of symbols in many fields such as bioinformatics, e-learning, market basket analysis, texts, and  webpage click-stream analysis.

I will now explain the task of sequential pattern mining with an example. Consider the following sequence database, representing the purchases made by customers in a retail store.

sequence database

This database contains four sequences.  Each sequence represents the items purchased by a customer at different times. A sequence is an ordered list of itemsets (sets of items bought together). For example, in this database, the first sequence (SID 1) indicates that a customer bought some items a and b together, then purchased an item c, then purchased items f and g together, then purchased an item g, and then finally purchased an item e.  

Traditionally, sequential pattern mining is being used to find subsequences that appear often in a sequence database, i.e. that are common to several sequences. Those subsequences are called the frequent sequential patterns. For example, in the context of our example, sequential pattern mining can be used to find the sequences of items frequently bought by customers. This can be useful to understand the behavior of customers to take marketing decisions.

To do sequential pattern mining, a user must provide a sequence database and specify a parameter called the minimum support threshold. This parameter indicates a minimum number of sequences in which a pattern must appear to be considered frequent, and be shown to the user. For example, if a user sets the minimum support threshold to 2 sequences, the task of sequential pattern mining consists of finding all subsequences appearing in at least 2 sequences of the input database.  In the example database, 29  subsequences met this requirement. These sequential patterns are shown in the table below, where the number of sequences containing each pattern (called the support) is indicated in the right column of the table.sequential patterns

For example, the patterns <{a}> and <{a}, {g}> are frequent and have a support of 3 and 2 sequences, respectively. In other words, these patterns appears in 3 and 2 sequences of the input database, respectively.  The pattern <{a}> appears in the sequences 1, 2 and 3, while the pattern <{a}, {g}> appears in sequences 1 and 3.   These patterns are interesting as they represent some behavior common to several customers. Of course, this is a toy example. Sequential pattern mining can actually be applied on database containing hundreds of thousands of sequences.

Another example of application of sequential pattern mining is text analysis. In this context, a set of sentences from a text can be viewed as sequence database, and the goal of sequential pattern mining is then to find subsequences of words frequently used in the text. If such sequences are contiguous, they are called “ngrams” in this context. If you want to know more about this application, you can read this blog post, where sequential patterns are discovered in a Sherlock Holmes novel.

Can sequential pattern mining be applied to time series?

Besides sequences, sequential pattern mining can also be applied to time series (e.g. stock data), when discretization is performed as a pre-processing step.  For example, the figure below shows a time series  (an ordered list of numbers) on the left. On the right, a sequence (a sequence of symbols) is shown representing the same data, after applying a transformation.   Various transformations can be done to transform a time series to a sequence such as the popular SAX transformation. After performing the transformation, any sequential pattern mining algorithm can be applied.

sequences and time series

Where can I get Sequential pattern mining implementations?

To try sequential pattern mining with your datasets, you may try the open-source SPMF data mining software, which provides implementations of numerous sequential pattern mining algorithms: http://www.philippe-fournier-viger.com/spmf/

It provides implementations of several algorithms for sequential pattern mining, as well as several variations of the problem such as discovering maximal sequential patterns, closed sequential patterns and sequential rules. Sequential rules are especially useful for the purpose of performing predictions, as they also include the concept of confidence.

What are the current best algorithms for sequential pattern mining?

There exists several sequential pattern mining algorithms. Some of the classic algorithms for this problem are PrefixSpan, Spade, SPAM, and GSP. However, in the recent decade, several novel  and more efficient algorithms have been proposed such as CM-SPADE  and CM-SPAM (2014), FCloSM and FGenSM (2017), to name a few.  Besides, numerous algorithms have been proposed for extensions of the problem of sequential pattern mining such as finding the sequential patterns that generate the most profit (high utility sequential pattern mining).

Conclusion

In this blog post, I have given a brief overview of sequential pattern mining, a very useful set of techniques for analyzing sequential data.  If you want to know more about this topic, you may read the following recent survey paper that I wrote, which gives an easy-to-read overview of this topic, including the algorithms forf sequential pattern mining, extensions,  research challenges and opportunities.

Fournier-Viger, P., Lin, J. C.-W., Kiran, R. U., Koh, Y. S., Thomas, R. (2017). A Survey of Sequential Pattern Mining. Data Science and Pattern Recognition, vol. 1(1), pp. 54-77.


Philippe Fournier-Viger is a professor of Computer Science and also the founder of the open-source data mining software SPMF, offering more than 120 data mining algorithms.

Related posts:

Posted in Big data, Data Mining, Data science | Tagged , , , , , , , | 7 Comments