Apriori algorithm Anti-monotonic vs monotonic

Question

According to Wikipedia, a monotonic function is a function that is either increasing or decreasing. If a function is increasing and decreasing then it's not a monotonic function or it's an anti-monotonic function.

But the data mining book, "Data Mining: Concepts and Techniques," describes anti-monotonic property as: If a set is infrequent then all of its supersets are also infrequent.

Doesn't this property look the same as monotonic according to Wikipedia? What is the difference between the two?

Solution 1

To begin with a quote:

Mathematics is the art of giving the same name to different things.

Ferdinand Verhulst

Indeed, according to Wikipedia's page on Monotonic functions, the use of "anti" (before "monotone" or "monotonic") for a function in the realm of order theory is different than its use in calculus and analysis. In order theory, "a monotone function is also called isotone, or order-preserving. The dual notion is often called antitone, anti-monotone, or order-reversing". It only means that the order of the images of the function is inverted.

But generally speaking, we deal with calculus. There, your first definition is the right one : a function "is called monotonic if and only if it is either entirely non-increasing, or entirely non-decreasing."And if a function increases and decreases, it would be simply called non-monotonic.

In data mining, what would be a monotonic function would be the support function of an itemset (its frequency in the transaction database). But when "frequent" (i.e sup(X) > supmin) is our criteria : "if a set is frequent, then all of its subset are frequent too", and also "if a set is infrequent then all of its superset are also infrequent." The combination of both means the anti-monotonicity in this context.

Solution 2

Different people use different definitions.

For real valued functions and sets, even the same author might be using different definitions.

Solution 3

When stating that Apriori is antimonotonic one is referring to the definition of antimonocity where "a constraint c is anti-monotone if an itemset S violates constraint c, so does any of its supersets". Apriori pruning is pruning with a anti-monotonic constraint.

Another way of looking at it would be that whenever an anti-monotonic constraint is met, we do not need to mine any further. Indeed, this is what Apriori pruning does.

Comments

[Mohamed Horani]

Thanks for Clarification :)