返回首頁

利用Flash實現MSApriori算法

時間:2012-05-07 21:33來源:知行網www.wtckvq.live 編輯:麥田守望者

傳統的Apriori算法對于不同項目之間出現頻率相關太大的數據,在挖掘時可能存在兩個問題:
1、如果將最小支持度設置太大,那顯然得不到含有出現頻率較低的項目(稀有項目)的關聯規則。
2、如果想要得到包含稀有的關聯規則,就不得不把最小支持度設置得很小。這會引發組合爆炸,符合要求的頻繁項目集和關聯規則的數目將以指數級的速度增長,會導致挖掘過程無法進行。
解決問題1的方法是讓用戶指定多個最小支持度閾值,為每個項目指定一個最小項目支持度MIS(Minimum Item Support)。解決問題2可將頻繁項目集中那些兩個或多個頻率相關太大的項目的候選集給過濾掉,即設置一個“約束條件”。
這個擴展模型即令MIS(i)表示第i個項目的MIS值。一條規則R的最小支持度為R中所有項目中最低的MIS值。如一條規則R:i1,i2,...,ik->ik+1,...,ir。滿足它的最小支持度,那數據集的真實支持度要大于或等于min(MIS(i1),MIS(i2),...,MIS(ir))。
算法如:(參考劉兵WEB數據挖掘)
 

利用Flash實現MSApriori算法 1
利用Flash實現MSApriori算法 2
利用Flash實現MSApriori算法 3
下面是使用Flash來實現的MS-Apriori:(這回用OOP方式來寫)
package
{
import flash.display.Sprite;
public class MSAprioriFla extends Sprite
{
public function MSAprioriFla()
{
//var T:String = "牛肉,雞肉,牛奶;牛肉,奶酪;奶酪,靴子;牛肉,雞肉,奶酪;牛肉,雞肉,衣服,奶酪,牛奶;雞肉,衣服,牛奶;雞肉,牛奶,衣服;牛奶,衣服;牛奶,衣服,雞肉";
//var T:String = "1,2;2,4;2,3;1,2,4;1,3;2,3;1,3;1,2,3;1,2,3";
//var T:String = "1,2,5;2,4;2,3;1,2,4;1,3;2,3;1,3;1,2,3,5;1,2,3";
//var T:String="牛肉,面包;面包,衣服;牛肉,面包,牛奶;奶酪,靴子;牛肉,面包,奶酪,鞋子;牛肉,面包,奶酪,牛奶;面包,牛奶,衣服";//cn example
var T:String="牛肉,面包;面包,衣服;面包,衣服,牛奶;奶酪,靴子;牛肉,面包,奶酪,鞋子;牛肉,面包,奶酪,牛奶;面包,牛奶,衣服";//en example
var arrT:Array = T.split(";");
var vT:Vector.<Vector.<String>>=new Vector.<Vector.<String>>();
var vs:Vector.<String>;
var arr:Array;
var i,j:int;
for(i=0;i<arrT.length;i++)
{
arr=arrT[i].split(",");
vs=new Vector.<String>();
for(j=0;j<arr.length;j++)
{
vs.push(arr[j]);
}
vT.push(vs);
}
//準備MIS
var vMIS:Vector.<ItemMIS>=new Vector.<ItemMIS>();
//vMIS.push( new ItemMIS("1",.1),
// new ItemMIS("2",.2),
// new ItemMIS("3",.05),
// new ItemMIS("4",.06))
vMIS.push(new ItemMIS("牛奶",.5),new ItemMIS("面包",.7),new ItemMIS("衣服",.25),
new ItemMIS("牛肉",.25),new ItemMIS("奶酪",.25),new ItemMIS("靴子",.25),new ItemMIS("鞋子",.25));
var msa:MSApriori=new MSApriori(vT,vMIS);
trace(msa.TToString());
msa.exec();

}
}
}
///////////////////////////////
package
{
public class MSApriori
{
private var T:Vector.<Vector.<String>>=new Vector.<Vector.<String>>();
private var Tn:int;
private var IMIS:Vector.<ItemMIS > ;
var oMIS:Object=new Object();
private var Phi:Number=.1;
public function MSApriori(_T:Vector.<Vector.<String>>,_imis:Vector.<ItemMIS>)
{
T = _T;
Tn = T.length;
IMIS = _imis;
}

public function exec():void
{
//從T中提取1-項目集
var vtC1:Vector.<ItemSet>=new Vector.<ItemSet>();
var oC1:Object=new Object();//當hash表用
var vtF1:Vector.<ItemSet>=new Vector.<ItemSet>();
var i,j:int;
var vt1,vt2:Vector.<String>;
var item:ItemSet;

//IMIS排序
IMIS.sort(function compare(x:ItemMIS, y:ItemMIS):Number {
if(x.MIS==y.MIS) return 0;
else if(x.MIS>y.MIS) return 1;
else return -1;
});//按數值排序
//將IMIS hash,方便檢索
for(i=0;i<IMIS.length;i++)
{
oMIS[IMIS[i].Item1k]=IMIS[i].MIS;
}


//1.候選1-項集
for (i=0; i<T.length; i++)
{
vt1 = T[i];
for (j=0; j<vt1.length; j++)
{
if (!Contain(vtC1,vt1[j]))
{
vt2=new Vector.<String>();
vt2.push(vt1[j].toString());
item=new ItemSet(vt2);
vtC1.push(item);
oC1[vt1[j].toString()]=item;
}
}
}
//排序
vtC1 = vtC1.sort(
function compare(x:ItemSet, y:ItemSet):Number {
if(x.Item[0]==y.Item[0]) return 0;
else if(x.Item[0]>y.Item[0]) return 1;
else return -1;
}
);

//計算各項集的count
var key:String;
for(i=0;i<T.length;i++)
{
for(j=0;j<T[i].length;j++)
{
key=T[i][j];
if(oC1[key]!=undefined) oC1[key].count++;
}
}
//計算每個項集的count/n
for(i=0;i<vtC1.length;i++)
{
vtC1[i].sup=vtC1[i].count/Tn;
}
//調試用

//將C1按MIS的值來升序排序
var vtC11:Vector.<ItemSet>=new Vector.<ItemSet>();
for(i=0;i<IMIS.length;i++)
{
vtC11.push(oC1[IMIS[i].Item1k]);
}
vtC1=vtC11;

//在MIS中找出第1個滿足i.count/n>=MIS(i)的位置
vtC11=new Vector.<ItemSet>();
for(i=0;i<IMIS.length;i++)
{
if(oC1[IMIS[i].Item1k].sup>=IMIS[i].MIS)
{
vtC11.push(oC1[IMIS[i].Item1k]);
break;
}
}
trace("i為"+i);
var iimis:Number=IMIS[i].MIS;

for(i++;i<IMIS.length;i++)
{
if(oC1[IMIS[i].Item1k].sup>=iimis)vtC11.push(oC1[IMIS[i].Item1k]);
}
vtC1=vtC11;
trace("1.候選1-項集:\n"+ISToString(vtC1));


//2.1-頻繁集
var mis:Number;
for(i=0;i<vtC1.length;i++)
{
mis=oMIS[vtC1[i].Item.toString()];
if(vtC1[i].sup>=mis){
vtF1.push(vtC1[i]);
}
}
trace("2.1-頻繁集為:\n"+ISToString(vtF1));

var k:int=2;
var vtFk:Vector.<ItemSet>;
var vtCk:Vector.<ItemSet>;



do
{
if(k==2)vtCk=level2_candidate_gen(vtC1,Phi);
else vtCk=MScandidate_gen(vtFk,Phi);
trace("3."+k+"-候選集為:"+ISToString(vtCk));
for(i=0;i<T.length;i++)
{
for(j=0;j<vtCk.length;j++)
{
if(Contain2(T[i],vtCk[j].Item))vtCk[j].count++;
}
}
vtFk=new Vector.<ItemSet>();

for(i=0;i<vtCk.length;i++)
{
vtCk[i].sup=vtCk[i].count/Tn;
if(vtCk[i].sup>=oMIS[vtCk[i].Item[0]]) vtFk.push(vtCk[i]);
}
trace("3."+k+"-頻繁集為:"+ISToString(vtFk));
k++

}while(vtFk.length>0);



}

private function MScandidate_gen(Fk:Vector.<ItemSet>,phi:Number):Vector.<ItemSet>
{
var rs:Vector.<ItemSet>=new Vector.<ItemSet>();
var i,j:int;
var k:int=Fk[0].Item.length+1;
var vt1,vt2:Vector.<String>;
var itemset:ItemSet;
//合并
for(i=0;i<Fk.length-1;i++)
{
for(j=i;j<Fk.length;j++)
{
vt1=Fk[i].Item.slice(0,Fk[i].Item.length);

------分隔線----------------------------
標簽(Tag):FLASH FLASH實例教程 flash技巧 flash源代碼 flash基礎教程
------分隔線----------------------------
推薦內容
猜你感興趣
深蓝海域APP