Publication View

Beyond Market Baskets: Generalizing Association Rules to Dependence Rules (1997)

Abstract

One of the more well-studied problems in data mining is the search for association rules in market basket data. Association rules are intended to identify patterns of the type: "A customer purchasing item A often also purchases item B." Motivated partly by the goal of generalizing beyond market basket data and partly by the goal of ironing out some problems in the definition of association rules, we develop the notion of dependence rules that identify statistical dependence in both the presence and absence of items in itemsets. We propose measuring significance of dependence via the chi-squared test for independence from classical statistics. This leads to a measure that is upward-closed in the itemset lattice, enabling us to reduce the mining problem to the search for a border between dependent and independent itemsets in the lattice. We develop pruning strategies based on the closure property and thereby devise an efficient algorithm for discovering dependence rules. We demonstrat...

Publication details

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.8964
Source	http://www-cs-students.stanford.edu/~csilvers/papers/chi2-dmkd.ps
Contributors	CiteSeerX
Repository	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Keywords	data mining, market basket, association rules, dependence rules, closure properties, text mining
Type	text
Language	English
Relation	10.1.1.40.6984, 10.1.1.12.6495, 10.1.1.103.5437, 10.1.1.41.6931, 10.1.1.42.342, 10.1.1.40.2201, 10.1.1.76.7322, 10.1.1.40.7203, 10.1.1.12.8836, 10.1.1.34.5131, 10.1.1.107.847, 10.1.1.42.3240, 10.1.1.38.5305, 10.1.1.13.1494, 10.1.1.21.9653, 10.1.1.43.7539, 10.1.1.23.2928, 10.1.1.32.7084, 10.1.1.33.574, 10.1.1.13.1236, 10.1.1.102.3937, 10.1.1.15.9737, 10.1.1.31.9403, 10.1.1.14.8740, 10.1.1.107.5027, 10.1.1.27.491, 10.1.1.23.6873, 10.1.1.44.5662, 10.1.1.45.9005, 10.1.1.47.863, 10.1.1.24.714, 10.1.1.90.9635, 10.1.1.23.5522, 10.1.1.37.5880, 10.1.1.103.8744, 10.1.1.24.8606, 10.1.1.30.2724, 10.1.1.121.6624, 10.1.1.14.5094, 10.1.1.58.6828, 10.1.1.6.1447, 10.1.1.135.1248, 10.1.1.13.4637, 10.1.1.43.6901, 10.1.1.1.9750, 10.1.1.42.5517, 10.1.1.45.9337, 10.1.1.34.3050, 10.1.1.13.7335, 10.1.1.35.2061, 10.1.1.100.8543, 10.1.1.103.1683, 10.1.1.27.6418, 10.1.1.12.3630, 10.1.1.42.3941, 10.1.1.111.7831, 10.1.1.57.6480, 10.1.1.117.106, 10.1.1.19.5364, 10.1.1.8.6436, 10.1.1.36.9179, 10.1.1.22.9235, 10.1.1.21.9550, 10.1.1.41.7924, 10.1.1.102.1174, 10.1.1.18.3738, 10.1.1.3.2277, 10.1.1.70.4856, 10.1.1.10.7105, 10.1.1.16.3876, 10.1.1.22.7050, 10.1.1.16.270, 10.1.1.16.5909, 10.1.1.11.9661, 10.1.1.34.1639, 10.1.1.34.8737, 10.1.1.16.7243, 10.1.1.21.9600, 10.1.1.23.5416, 10.1.1.56.6663, 10.1.1.5.2470, 10.1.1.48.306, 10.1.1.64.1749, 10.1.1.110.7816, 10.1.1.136.9956, 10.1.1.28.5466, 10.1.1.100.8030, 10.1.1.13.8744, 10.1.1.21.2630, 10.1.1.41.5002, 10.1.1.70.9971, 10.1.1.76.3286, 10.1.1.77.2923, 10.1.1.130.861, 10.1.1.13.5470, 10.1.1.14.8042, 10.1.1.17.2964, 10.1.1.25.3360, 10.1.1.8.4754, 10.1.1.83.1901, 10.1.1.88.471, 10.1.1.9.9457, 10.1.1.134.9476, 10.1.1.51.7763, 10.1.1.13.9889, 10.1.1.108.864, 10.1.1.14.1411, 10.1.1.53.8267, 10.1.1.93.4039, 10.1.1.128.6362, 10.1.1.103.3812, 10.1.1.19.1855, 10.1.1.21.741, 10.1.1.17.5385, 10.1.1.56.8391, 10.1.1.130.1682, 10.1.1.98.7123, 10.1.1.112.8568, 10.1.1.136.210, 10.1.1.32.5492, 10.1.1.3.6989, 10.1.1.1.3221, 10.1.1.59.1494, 10.1.1.1.9593, 10.1.1.104.3119, 10.1.1.104.41, 10.1.1.14.7933, 10.1.1.15.7665, 10.1.1.36.4236, 10.1.1.59.7311, 10.1.1.69.3886, 10.1.1.7.1373, 10.1.1.71.1085, 10.1.1.72.4661, 10.1.1.84.7169, 10.1.1.86.3463, 10.1.1.87.8841, 10.1.1.9.4594, 10.1.1.91.5814, 10.1.1.92.3606, 10.1.1.92.6216, 10.1.1.94.4740, 10.1.1.113.4283, 10.1.1.123.9738, 10.1.1.43.8106, 10.1.1.46.2045, 10.1.1.23.9740, 10.1.1.19.1974, 10.1.1.14.528, 10.1.1.1.8168, 10.1.1.60.4609, 10.1.1.60.9453, 10.1.1.1.1711, 10.1.1.100.27, 10.1.1.100.6274, 10.1.1.100.8163, 10.1.1.102.5340, 10.1.1.103.6295, 10.1.1.103.8670, 10.1.1.104.1273, 10.1.1.104.3272, 10.1.1.104.5180, 10.1.1.104.6034, 10.1.1.105.2925, 10.1.1.105.4071, 10.1.1.105.8353, 10.1.1.106.2451, 10.1.1.106.9938, 10.1.1.107.7701, 10.1.1.107.8049, 10.1.1.107.8509, 10.1.1.108.123, 10.1.1.108.2188, 10.1.1.108.3657, 10.1.1.108.3896, 10.1.1.108.5439, 10.1.1.108.9587, 10.1.1.109.2858, 10.1.1.109.720, 10.1.1.11.3706, 10.1.1.12.9374, 10.1.1.13.4563, 10.1.1.24.530, 10.1.1.24.9692, 10.1.1.3.1385, 10.1.1.33.1465, 10.1.1.40.4188, 10.1.1.50.619, 10.1.1.58.382, 10.1.1.58.8780, 10.1.1.6.7061, 10.1.1.64.3313, 10.1.1.64.353, 10.1.1.101.8919, 10.1.1.66.1721, 10.1.1.66.6955, 10.1.1.66.8131, 10.1.1.68.3713, 10.1.1.68.577, 10.1.1.69.3494, 10.1.1.69.6767, 10.1.1.69.8529, 10.1.1.70.2994, 10.1.1.70.4214, 10.1.1.71.3937, 10.1.1.71.5577, 10.1.1.71.5737, 10.1.1.71.6261, 10.1.1.71.8184, 10.1.1.73.1725, 10.1.1.122.5837, 10.1.1.75.4950, 10.1.1.75.5628, 10.1.1.76.4177, 10.1.1.77.2718, 10.1.1.77.3272, 10.1.1.78.3978, 10.1.1.78.432, 10.1.1.78.6610, 10.1.1.79.6397, 10.1.1.80.1412, 10.1.1.80.268, 10.1.1.81.3185, 10.1.1.81.4523, 10.1.1.81.573, 10.1.1.81.8707, 10.1.1.83.2539, 10.1.1.83.8083, 10.1.1.83.8383, 10.1.1.83.8463, 10.1.1.83.9732, 10.1.1.84.2725, 10.1.1.84.520, 10.1.1.85.5527, 10.1.1.85.8471, 10.1.1.85.9868, 10.1.1.86.6823, 10.1.1.86.7018, 10.1.1.87.7548, 10.1.1.87.7693, 10.1.1.88.5031, 10.1.1.89.6566, 10.1.1.89.8770, 10.1.1.90.1852, 10.1.1.91.1602, 10.1.1.115.6607, 10.1.1.91.2633, 10.1.1.92.4129, 10.1.1.132.2570, 10.1.1.92.5913, 10.1.1.93.5671, 10.1.1.108.3995, 10.1.1.94.6032, 10.1.1.96.242, 10.1.1.96.8068, 10.1.1.96.8249, 10.1.1.97.4212, 10.1.1.97.4529, 10.1.1.97.5116, 10.1.1.98.7918, 10.1.1.98.900, 10.1.1.99.7822, 10.1.1.110.1651, 10.1.1.110.9540, 10.1.1.113.6205, 10.1.1.113.6735, 10.1.1.116.1949, 10.1.1.116.3404, 10.1.1.116.5865, 10.1.1.116.8937, 10.1.1.117.327, 10.1.1.117.8532, 10.1.1.119.2767, 10.1.1.120.3007, 10.1.1.121.277, 10.1.1.121.5489, 10.1.1.122.6122, 10.1.1.123.1690, 10.1.1.123.8259, 10.1.1.129.455, 10.1.1.129.5982, 10.1.1.129.9420, 10.1.1.130.1845, 10.1.1.131.1327, 10.1.1.131.1330, 10.1.1.131.2323, 10.1.1.132.4676, 10.1.1.133.3335, 10.1.1.134.2223, 10.1.1.16.7635, 10.1.1.113.5568, 10.1.1.135.279, 10.1.1.135.7710, 10.1.1.135.9187, 10.1.1.136.3445, 10.1.1.136.5476, 10.1.1.137.151, 10.1.1.137.7987, 10.1.1.137.9769, 10.1.1.51.9643, 10.1.1.34.184, 10.1.1.42.1268, 10.1.1.34.4777, 10.1.1.35.5599, 10.1.1.35.7159, 10.1.1.36.9791, 10.1.1.32.8693, 10.1.1.21.2453, 10.1.1.21.5955, 10.1.1.23.3990, 10.1.1.14.1998, 10.1.1.24.6002, 10.1.1.17.6594, 10.1.1.17.7979, 10.1.1.19.1555, 10.1.1.11.4000, 10.1.1.13.9005, 10.1.1.14.7064, 10.1.1.15.2509, 10.1.1.6.8763, 10.1.1.7.1211, 10.1.1.8.3586, 10.1.1.9.3046, 10.1.1.9.4851, 10.1.1.10.2733, 10.1.1.10.8766, 10.1.1.11.2695, 10.1.1.2.9468, 10.1.1.3.2424, 10.1.1.3.6651, 10.1.1.4.3837, 10.1.1.5.7468, 10.1.1.6.1720, 10.1.1.2.4218, 10.1.1.59.8644, 10.1.1.61.363, 10.1.1.61.764, 10.1.1.61.8760, 10.1.1.62.484, 10.1.1.62.516