Hidden PL/SQL Gem in 10g: DBMS_FREQUENT_ITEMSET for PL/SQL based Data Mining

7

Data Mining in PL/SQL applications – Supplied Package DBMS_FREQUENT_ITEMSET (new in 10gR1)

Resource: Oracle 10g Supplied Packages – dbms_frequent_itemset.
This package exposes some part of the Data Mining capability of the Oracle 10g Server through PL/SQL and indirectly SQL. It allows us to quickly scan sets of data to find out if certain items frequently appear in combination. “frequent itemsets provides an efficient mechanism for counting how often multiple events occur together”. The example often used for this is the (super)market basket; upon investigation you will probably find out that pizza and parmezan cheese are often bought together, as are steak, sausages, spareribs, charcoal and barbecue-sauce. The fun of data mining is of course that a) you may find things you did not expect and b) you can apply this technique to many other aspects of life as well.

For example:

  • the occurrence of a certain disease in combination with behavioral or diet-related characteristics,
  • the preference for a certain type of car in combination with properties such as income, profession, preferred make of father/neighbour/friend, age
  • the preference for a political candidate or party; you can think of some of the associated properties…(religion, income, skincolor, corporate associations etc.)
  • the occurrence of a software bug given some of the characteristics of the application, the organization, the technology and the programmer

Of course when you find out that there is a strong likelyhood of certain combinations, the next step is predicting the occurrence of one item as a function of the others.

The resource referred to gives a good code example of applying this package dbms_frequent_itemset to a very simple basket-analysis.

Other resources:
Computing Frequent Itemsets inside Oracle 10G – white paper – (“somewhat scientific, interesting as background but not your best introduction”)
Frequent Itemsets in Oracle10g An Oracle White Paper (August 2003) (“very good overview of what it is and does, how it fits in with Data Mining, and where Data Mining can take you a step further”).

Using Frequent Itemset to spot patterns in Movie Preferences or: How to please a 5-year old?

In this example, I will apply PL/SQL based Data Mining exposed through dbms_frequent_itemset to a collection of movie-preference data. The following very simple data model shows three tables that hold respectively data on AGE_CATEGORIES, MOVIES and the Movie Top 3 selections made by a bunch of fictive people.

I have collected 27 statements from people of both genders in five different age categories, each picking their favorite three movies from a list with 10 fairly recent movies. From this rather small data-set for performing data-mining, I will nevertheless demonstrate the use and power of Frequent Itemset.

Note: you can download the following files to install the sample-tables and demo-data: MovieTables and MovieData.txt

A brief look into each table:

AGE_CATEGORIES:

 ID DESCRIPTION
--- ----------------
  1 2-6 years
  2 7-12 years
  3 12-15 years
  4 16-21 years
  5 21+ years

MOVIES:

 ID TITLE
--- ------------------------------------------
  1 Shrek 2
  2 Monster Inc
  3 Sharktale
  4 Bridget Jones - On the edge of reason
  5 Love Actually
  6 Dodgeball
  7 The Matrix Reloaded
  8 K3 en het betoverde medaillon
  9 Lord of The Rings
 10 Finding Nemo

MOVIE_PREFERENCES:

   ID AGE_CATEGORY G   MVE_ID_1   MVE_ID_2   MVE_ID_3
----- ------------ - ---------- ---------- ----------
    1            5 M          9          7          5
    2            5 M          9         10          2
    3            5 M         10          7          9
    4            4 M          6          7          9
    5            4 M          6          7          9
    6            4 F          4          7          9
    7            4 F          4          3          9
    8            4 F          4          5          6
    9            5 F          4          5          3
   10            5 F          4          5          3
   ..... 26 records

It is important to realize exactly what we see in the MOVIE_PREFERENCES table: 26 people, categorized by age and gender, pick their three favorite movies out of 10. For example, record with id=3: A Male person, highest age category and fan of Finding Nemo, The Matrix Reloaded and Lord of the Rings. We will investigate whether certain movies often occur together in the personal top three AND we will see whether certain movies frequently pair up with specific gender or age categories.

The most basic of analysis is made with a query such as this one. It first requires the creating of a Nested Table type in the database:

CREATE TYPE fi_number_nt AS TABLE OF NUMBER;

Then we ask dbms_frequent_itemset for a first rough analysis:

SELECT CAST (itemset as FI_number_NT) itemset
,      support
,      length
,      total_tranx
FROM   table( DBMS_FREQUENT_ITEMSET.FI_TRANSACTIONAL
              (  cursor
                 ( SELECT id, mve_id_1 FROM movie_preferences mpe
                   union
                   SELECT id, mve_id_2 FROM movie_preferences mpe
                   union
                   SELECT id, mve_id_3 FROM movie_preferences mpe
                   union
                   SELECT id, 1000* age_category FROM movie_preferences mpe
                   union
                   SELECT id, case mpe.gender when 'M' then -1 else -2 end FROM movie_preferences mpe
                 )
              , 0.05
              , 4
              , 6
              , NULL
              , NULL
              )
            )
order
by     support desc
,      length  desc

I have requested a list of all frequently occurring combinations where frequently is defined as 5% or more of the cases (support_threshold = 0.05). The combinations I am interested in should contain at least 4 and no more than 6 items. (itemset_length_min = 4 and itemset_length_max = 6). I have not excluded items from the analysis (excluding_items = null), nor have I listed any items as required in sets that are to be considered (including_items = null).

Note that I had to use the CASE..WHEN construction to turn Gender (values M or F ) into a numeric value: all values in the transaction have to be of the same type – either VARCHAR2 or NUMBER. Furthermore, since all values are considered equal and position in a transaction plays no part, I must ensure that the numeric values used for Gender and Age_Category do not overlap with the values used for MVE_ID. I multiply the age_category (acy_id) by 1000 to make sure those values are in an entirely different range from the mve_id values, and therefore easily recognizable. For the same reason I assign negative numbers for the Gender values.

We used the dbms_frequent_itemset.FI_TRANSACTIONAL procedure, which is defined as follows in the documentation:

DBMS_FREQUENT_ITEMSET.FI_TRANSACTIONAL (
   tranx_cursor         IN    SYSREFCURSOR, -- The cursor parameter that the user will supply when calling the function. It should return two columns in its returning row, the first column being the transaction id, the second column being the item id. The item id must be number or character type (for example, VARCHAR2(n)).
   support_threshold    IN    NUMBER, -- A fraction number of total transaction count. An itemset is termed "frequent" if [the number of transactions it occurs in]divided by [the total number of transactions]exceed the fraction. The parameter must be a NUMBER.
   itemset_length_min   IN    NUMBER, -- The minimum length for interested frequent itemset. The parameter must be a NUMBER between 1 and 20, inclusive
   itemset_length_max   IN    NUMBER, -- The maximum length for interested frequent itemset. This parameter must be a NUMBER between 1 and 20, inclusive, and must not be less than itemset_length_min.
   including_items      IN    SYS_REFCURSOR DEFAULT NULL, -- A cursor from which a list of items can be fetched. At least one item from the list must appear in frequent itemsets that will be returned. The default is NULL.
   excluding_items      IN    SYS_REFCURSOR DEFAULT NULL) -- A cursor from which a list of items can be fetched. No item from the list can appear in frequent itemsets that will returned. The default is NULL.
  RETURN TABLE OF ROW (
     itemset [Nested Table of Item Type DERIVED FROM tranx_cursor], -- A collection of items which is computed as frequent itemset. This will be returned as a nested table of item type which is the item column type of the input cursor.
     support        NUMBER, -- The number of transactions in which a frequent itemset occurs. This will be returned as a NUMBER.
     length         NUMBER, -- Number of items in a frequent itemset. This will be returned as a NUMBER
     total_tranx    NUMBER);-- The total transaction count. This will be returned as a NUMBER, and will be the same for all returned rows, similar to a reporting aggregate.
Usage Notes

The results:

ITEMSET                                     SUPPORT   LENGTH      TOTAL_TRANX
----------------------------------------   ---------- ---------- -----------
FI_NUMBER_NT(-2, 3, 5, 5000)                 3          4          26
FI_NUMBER_NT(-2, 3, 10, 3000)                3          4          26
FI_NUMBER_NT(-2, 4, 5, 5000)                 3          4          26
FI_NUMBER_NT(1, 3, 10, 3000)                 3          4          26
FI_NUMBER_NT(-1, 2, 3, 1000)                 3          4          26
FI_NUMBER_NT(-2, 1, 3, 10, 3000)             2          5          26
... 38 records

This tells us for example that 3 out of 26 transactions contained a combination of: Female, 21+ years, Sharktale, Love Actually. We also found 3 transactions that supported the combination of Female, 12-16 years, Sharktale and Finding Nemo. There is one combination of five values that occurs more than once: Female, 12-16 years, Sharktale, Shrek 2 and Finding Nemo..

To present the data in better way, we have to rewrite the query somewhat:

SELECT present_items( CAST (itemset as FI_number_NT)) itemset
,      support
,      length
,      total_tranx
FROM   table( DBMS_FREQUENT_ITEMSET.FI_TRANSACTIONAL
              (  cursor
                 ( SELECT id, mve_id_1 FROM movie_preferences mpe
                   union
                   SELECT id, mve_id_2 FROM movie_preferences mpe
                   union
                   SELECT id, mve_id_3 FROM movie_preferences mpe
                   union
                   SELECT id, 1000* age_category FROM movie_preferences mpe
                   union
                   SELECT id, case mpe.gender when 'M' then -1 else -2 end FROM movie_preferences mpe
                 )
              , 0.05
              , 4
              , 6

              , NULL
              , NULL
              )
            )
order
by     support desc
,      length  desc

The results this time are more meaningful:

ITEMSET                                                                          SUPPORT     LENGTH TOTAL_TRANX
-------------------------------------------------------------------------------- ---------- ---------- -----------
Female, Sharktale, Love Actually, 21+ years                                        3          4          26
Female, Sharktale, Finding Nemo, 12-15 years                                       3          4          26
Female, Bridget Jones - On the edge of reason, Love Actually, 21+ years            3          4          26
Shrek 2, Sharktale, Finding Nemo, 12-15 years                                      3          4          26
Female, Shrek 2, Sharktale, Finding Nemo, 12-15 years                              2          5          26
Male, Dodgeball, The Matrix Reloaded, Lord of The Rings, 16-21 years               2          5          26
Female, Sharktale, Bridget Jones - On the edge of reason, Love Actually, 21+ years 2          5          26
...

The function present_items that I created to support this query is defined as follows:

create or replace
function present_items
( p_itemset in FI_NUMBER_NT
) return varchar2
is
  l_return_value varchar2(1000):='';
  l_help varchar2(100):='';

  procedure add(p_string in varchar2)
  is
  begin
    l_return_value:= l_return_value||p_string||', ';
  end add;

begin
  for i in 1..p_itemset.count loop
    if p_itemset(i) < 0
    then
      case p_itemset(i) when '-1' then add('Male'); else add('Female'); end case;
    elsif p_itemset(i) > 1000
    then
      select description
      into   l_help
      from   age_categories
      where  id = p_itemset(i)/1000
      ;
      add(l_help);
    else
      select title
      into   l_help
      from   movies
      where  id = p_itemset(i)
      ;
      add(l_help);
    end if;
  end loop;
  return substr(l_return_value, 1, length(l_return_value)-2);
end;

siness Problem – What movie to rent to entertain my nephew?

Now we can try to attack a more interesting business issue: Our nephew is visiting; he is 5 years old and he enjoyed Finding Nemo. What movie should we rent for him?

DBMS_FREQUENT_ITEMSET can find out for us which combinations of movie-preferences occur for Males in the youngest age-category that also include Finding Nemo:

select items.column_value "Recommended Movie"
from   ( SELECT CAST(itemset as FI_varchar_NT) itemset
         ,      support
         ,      length
         ,      total_tranx
         FROM   table ( DBMS_FREQUENT_ITEMSET.FI_TRANSACTIONAL
                        ( cursor
                          ( SELECT mpe.id, title FROM movie_preferences mpe, movies mve where mve.id = mpe.mve_id_1
                            union
                            SELECT mpe.id, title FROM movie_preferences mpe, movies mve where mve.id = mpe.mve_id_2
                            union
                            SELECT mpe.id, title FROM movie_preferences mpe, movies mve where mve.id = mpe.mve_id_3
                            union
                            SELECT mpe.id, acy.description FROM movie_preferences mpe, age_categories acy  where acy.id = mpe.age_category
                            union
                            SELECT mpe.id, mpe.gender FROM movie_preferences mpe
                          )
                        , 0.05
                        , 4
                        , 6
                        , CURSOR( SELECT * FROM table(FI_VARCHAR_NT('Finding Nemo')))
                        , NULL
                        )
                      )
        ) it
,       table(it.itemset) items
,       movies mve
where support &gt; 1
and   set_contains_item( itemset, '2-6 years' ) = 1
and   set_contains_item( itemset, 'M' ) = 1
and   mve.title = items.column_value
and   mve.title != 'Finding Nemo'

At the heart of this query, we ask for Frequent Itemsets that contain at least Finding Nemo, in total between 4 and 6 items and a support of at least 5% (meaning that at least 5% of the transactions contains the frequent combination -otherwise we do not want to consider it frequent). Furthermore – and somewhat superfluously – we only care for frequent itemsets supported by at least two (>1) transactions. Note that this time we choose to present all data as VARCHAR2 rather than NUMBER. In this query we make use of stored function set_contains_item that was defined as follows:

create or replace
function set_contains_item
( p_itemset in FI_varchar_NT
, p_value   in varchar2
) return number
is
begin
  for i in 1..p_itemset.count loop
    if p_itemset(i) = p_value
    then
      return 1;
    end if;
  end loop;
  return 0;
end;

The result of this query is quite clear:

Recommended Movie
------------------------------
Sharktale

So we will install His Nephewness in front of the TV set, watching Sharktale! Data Mining showed us the way.

Some similar investigations: Recommended Movie for a young adult male (16-21 years) who expressed some enjoyment over Dodgeball:

select items.column_value "Recommended Movie"
from   ( SELECT CAST(itemset as FI_varchar_NT) itemset
         ,      support
         ,      length
         ,      total_tranx
         FROM   table ( DBMS_FREQUENT_ITEMSET.FI_TRANSACTIONAL
                        ( cursor
                          ( SELECT mpe.id, title FROM movie_preferences mpe, movies mve where mve.id = mpe.mve_id_1
                            union
                            SELECT mpe.id, title FROM movie_preferences mpe, movies mve where mve.id = mpe.mve_id_2
                            union
                            SELECT mpe.id, title FROM movie_preferences mpe, movies mve where mve.id = mpe.mve_id_3
                            union
                            SELECT mpe.id, acy.description FROM movie_preferences mpe, age_categories acy  where acy.id = mpe.age_category
                            union
                            SELECT mpe.id, mpe.gender FROM movie_preferences mpe
                          )
                        , 0.05
                        , 4
                        , 6
                        , CURSOR( SELECT * FROM table(FI_VARCHAR_NT('Dodgeball')))
                        , NULL
                        )
                      )
        ) it
,       table(it.itemset) items
,       movies mve
where support &gt; 1
and   set_contains_item( itemset, '16-21 years' ) = 1
and   set_contains_item( itemset, 'M' ) = 1
and   mve.title = items.column_value
and   mve.title != 'Dodgeball'

As far as DBMS_FREQUENT_ITEMSET can tell based on a relatively small set of data, he might be interested in:

Recommended Movie
-------------------------
The Matrix Reloaded

Finally I try to find a movie that my girlfriend will enjoy – knowing that she liked “Love Actually”:

select items.column_value "Recommended Movie"
from   ( SELECT CAST(itemset as FI_varchar_NT) itemset
         ,      support
         ,      length
         ,      total_tranx
         FROM   table ( DBMS_FREQUENT_ITEMSET.FI_TRANSACTIONAL
                        ( cursor
                          ( SELECT mpe.id, title FROM movie_preferences mpe, movies mve where mve.id = mpe.mve_id_1
                            union
                            SELECT mpe.id, title FROM movie_preferences mpe, movies mve where mve.id = mpe.mve_id_2
                            union
                            SELECT mpe.id, title FROM movie_preferences mpe, movies mve where mve.id = mpe.mve_id_3
                            union
                            SELECT mpe.id, acy.description FROM movie_preferences mpe, age_categories acy  where acy.id = mpe.age_category
                            union
                            SELECT mpe.id, mpe.gender FROM movie_preferences mpe
                          )
                        , 0.05
                        , 4
                        , 6
                        , CURSOR( SELECT * FROM table(FI_VARCHAR_NT('Love Actually')))
                        , NULL
                        )
                      )
        ) it
,       table(it.itemset) items
,       movies mve
where support &gt; 1
and   set_contains_item( itemset, '21+ years' ) = 1
and   set_contains_item( itemset, 'F' ) = 1
and   mve.title = items.column_value
and   mve.title != 'Love Actually'
Recommended Movie
------------------------------------------------
Bridget Jones - On the edge of reason

Associations in a strange country

Another way to make use of the data we assembled and the functionality offered by DBMS_FREQUENT_ITEMSET could be this situation:

I arrive in a strange city in a foreign country. I walk around town and see billboard for a certain movie: “K3 en het betoverde medaillon”. I do not know the movie, and I am wondering whether I might like it. So now based on the movie-preference data gathered I would like to know:
– what age groups and genders are interested in this movie?
– what other movies can this movie be compared to – or at least, which movies are often liked by people who also like this movie?
– or, putting it altogether, which movies that I do know should be liked by someone with my age-category and my gender to have a good possibility to also like this movie? For example: if I see posters for Lord of the Rings part 3, chances are that in general people who liked part 2 also liked part 3.

Issue with Horizontal Data in DBMS_FREQUENT_ITEMSET

Note: dbms_frequent_itemset allows us to present data either transactionally (all data in records that consist of a transaction identifier and a single value, i.e. many records per transaction) or horizontally (one record per transaction that contains all values). Our data in MOVIE_PREFERENCES is already in horizontal format, so that is the obvious choice when using dbms_frequent_itemset. However, I ran into some problems – presumably bugs – with the horizontal data approach, so I switched to the transactional procedure in dbms_frequent_itemset.

The following query should have worked I believe:

SELECT CAST(itemset as FI_varchar_NT) itemset, support, length, total_tranx
FROM   table( DBMS_FREQUENT_ITEMSET.FI_HORIZONTAL
              ( CURSOR ( SELECT acy.description
                         ,      gender
                         ,      mve1.title
                         ,      mve2.title
                         ,      mve3.title
                         FROM   movie_preferences mpe
                         ,      movies  mve1
                         ,      movies  mve2
                         ,      movies  mve3
                         ,      age_categories acy
                         where  mpe.age_category = acy.id
                         and    mpe.mve_id_1 = mve1.id
                         and    mpe.mve_id_2 = mve2.id
                         and    mpe.mve_id_3 = mve3.id
                       )
               , 0.2
               , 3
               , 6
               , null
               , null
               )
              );

However, after some serious processor activity, it returns with:

SELECT CAST(itemset as FI_varchar_NT) itemset, support, length, total_tranx
*
ERROR at line 1:
ORA-00600: internal error code, arguments: [qqesfCBM_QBReadNext.1], [0], [],
[], [], [], [], []
Share.

About Author

Lucas Jellema, active in IT (and with Oracle) since 1994. Oracle ACE Director for Fusion Middleware. Consultant, trainer and instructor on diverse areas including Oracle Database (SQL & PLSQL), Service Oriented Architecture, BPM, ADF, Java in various shapes and forms and many other things. Author of the Oracle Press book: Oracle SOA Suite 11g Handbook. Frequent presenter on conferences such as JavaOne, Oracle OpenWorld, ODTUG Kaleidoscope, Devoxx and OBUG. Presenter for Oracle University Celebrity specials.

7 Comments

  1. Pingback: glamour-agency

  2. Nice article. A piece of information that might interest you is that the code wrapped by the DBMS_FREQUENT_ITEMSET feature is used in the Association algorithm in Oracle Data Mining.

  3. Mike Friedman on

    This is cool. Any feel for how fast it runs? For example, could it be deployed in a real time POS application?

  4. I am the author of the feature of frequent itemset counting. Your paper is the biggest reward I’ve got since working on the feature. Sadly, I have already left and can not make it further.

  5. Pingback: Hidden PL/SQL Gem in 10g: DBMS_FREQUENT_ITEMSET for PL/SQL based Data Mining

  6. Pingback: Hidden PL/SQL Gem in 10g: DBMS_FREQUENT_ITEMSET for PL/SQL based Data Mining