dci 0.3.0

DCI-Closed, a frequent closed itemset mining algorithm, implemented in Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

use crate::{
	DataSet,
	ItemSet,
	Support,
	closed::{
		InitialSets,
		is_dup
	}
};


/// Sequential implementation of the DCI-Closed algorithm. This is a straightforward
/// implementation of the original algorithm from the paper. It uses only one CPU core.
///
/// The returned collection will **always** have at least one element, with maximum support:
/// the set of all elements which occur in all transactions.
pub fn closed<D>(dataset: &D, min_sup: usize) -> Box<[(D::ItemSet, Support)]>
where
	D: DataSet,
	for<'b> &'b D::ItemSet: IntoIterator<Item = usize>
{
	let InitialSets { closed, pre, post } = InitialSets::new(dataset, min_sup);

	let closed_set = closed.clone();
	let transactions_count = dataset.transactions_count();

	let mut closed_itemsets = vec![(closed_set, transactions_count)];

	_closed(
		dataset,
		min_sup,
		&closed,
		pre,
		&post,
		&mut closed_itemsets
	);

	closed_itemsets.into_boxed_slice()
}


fn _closed<'a, D>(
	dataset: &'a D,
	min_sup: usize,
	closed_set: &D::ItemSet,
	mut pre_set: D::ItemSet,
	post_set: &D::ItemSet,
	out: &mut Vec<(D::ItemSet, Support)>,
)
where
	D: DataSet,
	for<'b> &'b D::ItemSet: IntoIterator<Item = usize>
{
	for i in post_set.into_iter() {
		let mut new_gen = closed_set.clone();
		new_gen.add(i);

		let new_gen_cover = dataset.cover(&new_gen);

		if dataset.support(&new_gen) >= min_sup {
			if !is_dup(dataset, &new_gen_cover, &pre_set) {
				let mut closed_set_new = new_gen.clone();
				let mut post_set_new = D::ItemSet::empty();

				for j in post_set.into_iter().skip_while(|&j| i >= j) {
					if dataset.supports(j, &new_gen_cover) {
						closed_set_new.add(j);
					}
					else {
						post_set_new.add(j)
					}
				}

				out.push(
					(
						closed_set_new.clone(),
						dataset.support(&closed_set_new)
					)
				);

				let pre_set_new = pre_set.clone();

				_closed(
					dataset,
					min_sup,
					&closed_set_new,
					pre_set_new,
					&post_set_new,
					out,
				);

				pre_set.add(i);
			}
		}
	}
}