Java implementation of the paper "Finding Highly Correlated Pairs with Powerful Pruning" by Zhang, J., & Feigenbaum, J. (2006, November). In Proceedings of the 15th ACM international conference on Information and knowledge management (pp. 152-161). ACM. pdf
The only dependency is Guava.
Licensed under the Apache 2.0 License.
The input are many transactions (aka baskets), each of which is a set of items. This algorithm will efficiently find items that tend to occur together in the same transactions. Technically, this is finding all pairs of items whose phi coefficient is above a specified threshold. This correlation is measured on the sets of transactions the two items occur in. These transactions can be any sets, such as baskets of products a user purchased or words in documents. This project provides sets of ingredients used by recipes, extracted from the Kaggle What's Cooking dataset in the file kaggle_whats_cookin.txt. That data has one listing of ingredient per line and looks like this:
plain_flour ground_pepper salt tomatoes ground_black_pepper thyme eggs green_tomatoes yellow_corn_meal milk vegetable_oil
eggs pepper salt mayonaise cooking_oil green_chilies grilled_chicken_breasts garlic_powder yellow_onion soy_sauce butter chicken_livers
...
Here are pairs of ingredients sorted only by the number of recipes they occur in together.
ingredient1 ingredient2 freq
==============================================
salt onions 4392
salt olive_oil 4180
salt water 3960
pepper salt 3844
garlic salt 3749
salt all-purpose_flour 3079
salt sugar 3061
salt garlic_cloves 2998
salt butter 2777
salt ground_black_pepper 2737
garlic onions 2659
onions olive_oil 2207
olive_oil garlic_cloves 2103
salt vegetable_oil 2101
garlic olive_oil 2080
water onions 1974
salt eggs 1919
salt black_pepper 1792
salt large_eggs 1700
salt tomatoes 1682
onions garlic_cloves 1643
garlic water 1605
water sugar 1576
salt ground_cumin 1533
ground_black_pepper olive_oil 1520
While this listing is useful, it does not account for the fact that certain ingredients are more common than others and will therefore occur with many other ingredients purely because they are both frequent. That's why "salt" shows up so often. Let's use the FHCP algorithm to find only pairs of ingredients that occur together at least ten times, and whose phi coefficient is at least 0.3:
ingredient1 ingredient2 Phi
==============================================
green_cardamom brown_cardamom : 0.460
warm_water active_dry_yeast : 0.453
pastry single_crust_pie : 0.450
garlic_powder onion_powder : 0.436
soy_sauce sesame_oil : 0.431
mirin sake : 0.409
buttermilk baking_soda : 0.408
wasabi nori_sheets : 0.405
kaffir_lime_leaves galangal : 0.393
green_cardamom shahi_jeera : 0.385
garlic_paste ginger_paste : 0.379
baking_powder baking_soda : 0.368
lemongrass galangal : 0.367
baking_powder all-purpose_flour : 0.364
cinnamon_sticks clove : 0.348
dried_bonito_flakes konbu : 0.341
warm_water dry_yeast : 0.337
ground_cumin ground_coriander : 0.336
cumin_seed coriander_seeds : 0.329
garam_masala coriander_powder : 0.328
mascarpone ladyfingers : 0.321
konbu bonito_flakes : 0.319
garlic_paste coriander_powder : 0.307
cumin_seed ground_turmeric : 0.306
garam_masala ground_turmeric : 0.305
rice_noodles beansprouts : 0.304
light_soy_sauce dark_soy_sauce : 0.301
lemongrass kaffir_lime_leaves : 0.301
ground_turmeric coriander_powder : 0.301
Much more interesting. The pairs make sense, yeast needs warm water to be activated, and many of the pairs reflect common regional pairings.
While the phi coefficient is a good measure of associativity, and it is equal to Pearson correlation for binary data, is proportional to the Chi square test, and relates to Jaccard similarity, it isn't the only one. There are other measures of associativity on 2x2 contingency tables, such as Fisher's eact test and the g-score. The algorithm implemented here uses Minhashes to find items whose transaction sets have high Jaccard similarity in a first pass. Then the phi coefficient is calculated in a second pass. This second pass could easily be replaced by one that caclulated an alternative associativity measure.
The algorithm has four parameters:
- theta
- The minimum Phi correlation that two items should have between their transaction sets. (e.g., 0.3)
- tau
- False negative tolerance. Allow no more than this fraction of false negatives. (e.g., 0.05 means 5%)
- minsup
- The minimum number of transactions two items must occur in together to be considered correlated. (e.g., 10)
- k
- Number simultaneous minhashes needed to match. For large numbers of unique items such as in the recipe dataset, k=1 is okay. For many transactions and small number of unique item types, large k values may be reasonable.
Everything is implemented in FHCP.java, which has a main() method that takes in the data file name:
java -classpath . FHCP kaggle_whats_cookin.txt
A related concept is frequent itemset mining, for which there is a great Java library called SPMF.