首页 / 算法 / 数据挖掘经典算法——先验算法
数据挖掘经典算法——先验算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据挖掘经典算法——先验算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7333字，纯文字阅读大概需要11分钟。
内容图文
算法描述
先验算法是实现频繁项挖掘的一种经典算法，利用关联式规则不断扩展频繁项子集以获得全部的频繁项集合。解释一下关联式规则，所谓关联式是指在大量的数据中找出的项与项之间的关系。例如消费者购买了产品A，一般都会购买产品B，这就是一条关联式。
先验算法被设计用来处理包含事务的数据库，这里的每一个事务都被当成是一组项集，给定一个阈值C，我们需要找出至少出现C次的事务子集（即子项）。这边这个C值就是最小支持度，规定了一个项集出现多少次才能被认为是一个频繁项。
先验算法的核心思想基于以下一个事实：一个项集是频繁项集，其所有子集一定是频繁项集；一个项集不是频繁项，其超集一定不是频繁项集。那么我们在寻找事务中的最大频繁项的过程中，只需要扩展是频繁项的子集，这就大大地缩减了搜索空间。下面是该算法的伪代码实现：
其中T代表的是事务集合，
算法的优缺点
优点：
- 算法简单，易于理解，对数据的要求度低；
缺点：
- 在选取较小的支持度选取时，可能带来较多的候选集，大量的集合操作会导致算法效率低下；
- 每一次迭代都需要重新扫描数据库，I/O开销比较大；
Apriori算法的Java实现
1
import
java.util.ArrayList;
2
import
java.util.HashMap;
3
import
java.util.HashSet;
4
import
java.util.Iterator;
5
import
java.util.List;
6
import
java.util.Map;
7
import
java.util.Set;
8
9
/**
10
* 这是一个简单的先验算法的实现，包含了如下假设：
11
* 1.事务对应一个TID和一个项集合，每个项对应一个int类型的数值,保证同一个事务内部的项唯一
12
* 2.算法在实现方式上还存在很多可以优化剪枝的部分，这里省略了优化，是结构更加清晰
13
* 3.这只是一个样例程序
14
*
@author
LuZhou
15
* @email 448287076@qq.com
16
*/
17
public
class
Aprior {
18
19
20
public
static
class
TransactionItem {
21
22
private
Integer itemValue;
23
24
public TransactionItem( int i ){
25 itemValue = i;
26 }
27 28 @Override
29publicboolean equals(Object obj) {
30 TransactionItem it = (TransactionItem) obj;
31returnthis.itemValue == it.itemValue;
32 }
33 34 35 @Override
36public String toString() {
37return itemValue.toString();
38 }
39 40 @Override
41publicint hashCode() {
42return itemValue % 31;
43 }
44 }
45 46 47publicstaticclass ItemCollection{
48private Set<TransactionItem> items = new HashSet<Aprior.TransactionItem>();
49 50public ItemCollection(){
51 }
52 53public ItemCollection(int[] items){
54for (int i = 0; i < items.length; i++) {
55this.add(new TransactionItem(items[i]));
56 }
57 }
58 59publicboolean itemContains(Set<TransactionItem> sub){
60return items.containsAll(sub);
61 }
62 63 @Override
64publicboolean equals(Object obj) {
65 ItemCollection ic = (ItemCollection) obj;
66return ic.items.containsAll(items) &&
67 items.containsAll(ic.items);
68 }
69 70 @Override
71publicint hashCode() {
72int v = 0;
73for (TransactionItem ts : items) {
74 v = ( v + ts.hashCode() ) % 31;
75 }
76return v;
77 }
78 79publicboolean contains(ItemCollection sub){
80return items.containsAll(sub.items);
81 }
82 83publicboolean containItem(TransactionItem item){
84return items.contains(item);
85 }
86 87public Set<TransactionItem> getItems(){
88return items;
89 }
90 91publicvoid add(TransactionItem item){
92 items.add(item);
93 }
94 95 @Override
96public String toString() {
97 StringBuilder sb = new StringBuilder();
98 sb.append("{");
99for (TransactionItem item : getItems()) {
100 sb.append( item.toString() );
101 sb.append(",");
102 }
103 sb.append("}");
104return sb.toString();
105 }
106107 }
108109publicstaticclass Transaction{
110privateint id;
111private ItemCollection ic;
112113public Transaction(int id , ItemCollection itemCollection){
114this.id = id;
115this.ic = itemCollection;
116 }
117118publicboolean itemContains(ItemCollection sub){
119return ic.contains(sub);
120 }
121122public Set<TransactionItem> getItems(){
123return ic.getItems();
124 }
125126 }
127128private Set<TransactionItem> restItems = new HashSet<Aprior.TransactionItem>();
129private List<Transaction> transactions = new ArrayList<Aprior.Transaction>();
130131//统计一项的出现次数132privateint itemsFrequency( ItemCollection sub ){
133int frequency = 0 ;
134135for (Transaction t : transactions) {
136if(t.itemContains(sub)){
137 frequency ++;
138 }
139 }
140141return frequency;
142 }
143144//确定扩展项是否为频繁项145private Set< ItemCollection > filterWithThreadshold(
146 Set< ItemCollection > items, int threadshold ){
147148 Set< ItemCollection > result = new HashSet<ItemCollection>();
149for (ItemCollection subItems : items) {
150if( threadshold <= itemsFrequency(subItems))
151 result.add(subItems);
152 }
153154return result;
155 }
156157//根据现有的子项集获取所有的可能扩展158private Set< ItemCollection > extendItems( Set< ItemCollection > current){
159 Set< ItemCollection > extend = new HashSet<Aprior.ItemCollection>();
160161//找出剩余的项集162 restItems.clear();
163for (ItemCollection ic : current) {
164for (TransactionItem item : ic.getItems()) {
165 restItems.add(item);
166 }
167 }
168169//需要找到当前频繁项子集170for (ItemCollection itemCollection : current) {
171for (TransactionItem rest : restItems) {
172if( ! itemCollection.containItem(rest) ){
173//找到一个b 不属于 频繁项集 A 但是存在于剩余项中 用其构造其余的子项174 extend.add( buildCollection( itemCollection, rest ));
175 }
176 }
177178 }
179180return extend;
181 }
182183//result = ic.items & item184private ItemCollection buildCollection(ItemCollection ic,TransactionItem item){
185 ItemCollection ex = new ItemCollection();
186187 Iterator<TransactionItem> it = ic.getItems().iterator();
188while(it.hasNext()){
189 ex.add( it.next() );
190 }
191192 ex.add(item);
193194return ex;
195 }
196197198//初始化剩余项199private Set<ItemCollection> initCollection( int threadshold ){
200201 Map<TransactionItem , Integer> tc = new HashMap<Aprior.TransactionItem, Integer>();
202203for ( Transaction t : transactions ) {
204205for ( TransactionItem item : t.getItems() ) {
206207if( !restItems.contains(item) ){
208 restItems.add(item);
209 tc.put(item, 1);
210 }else211 tc.put( item, 1 + tc.get(item) );
212213 }
214 }
215216217 Set<ItemCollection> collection = new HashSet<Aprior.ItemCollection>();
218219 Iterator< TransactionItem > it = tc.keySet().iterator();
220while( it.hasNext() ){
221 TransactionItem item = it.next();
222if( threadshold <= tc.get( item ) ){
223 ItemCollection ic = new ItemCollection();
224 ic.add( item );
225 collection.add( ic );
226 }
227 }
228229return collection;
230 }
231232233/**234 * 找出频繁项
235 * @param threadshold 最小支持度
236 * @return237*/238public Set< ItemCollection > frequentItem( int threadshold ){
239240 Set< ItemCollection > current = initCollection( threadshold );
241 Set< ItemCollection > result = new HashSet<Aprior.ItemCollection>();
242243while( current.size() > 0 ){
244245 result.addAll( current );
246247 Set<ItemCollection> extendList = extendItems( current );
248249 current = filterWithThreadshold( extendList, threadshold );
250251 }
252253254return result;
255 }
256257publicvoid addTransaction(Transaction ts){
258 transactions.add(ts);
259 }
260261262publicstaticvoid main(String args[]){
263264finalint MINSUPPROT = 2;
265 Aprior aprior = new Aprior();
266/**267 * 数据集包括
268 * T1 {1,3,4}
269 * T2 {2,3,5}
270 * T3 {1,2,3,5}
271 * T4 {2,5}
272 * 最小支持度为2，请最大频繁项
273*/274 aprior.addTransaction(new Transaction(1, new ItemCollection(newint[]{1,3,4})));
275 aprior.addTransaction(new Transaction(2, new ItemCollection(newint[]{2,3,5})));
276 aprior.addTransaction(new Transaction(3, new ItemCollection(newint[]{1,2,3,5})));
277 aprior.addTransaction(new Transaction(4, new ItemCollection(newint[]{2,5})));
278279 System.out.println(aprior.frequentItem( MINSUPPROT ));
280281 }
282283284 }
参考资料
http://en.wikipedia.org/wiki/Apriori_algorithm
http://rakesh.agrawal-family.com/papers/vldb94apriori.pdf
http://www.cnblogs.com/gaizai/archive/2010/03/31/1701573.html
原文：http://www.cnblogs.com/yahokuma/p/3769969.html
内容总结
以上是互联网集市为您收集整理的数据挖掘经典算法——先验算法全部内容，希望文章能够帮你解决数据挖掘经典算法——先验算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】