電子發(fā)燒友App
一、關(guān)聯(lián)算法簡(jiǎn)介
關(guān)聯(lián)規(guī)則的目的在于在一個(gè)數(shù)據(jù)集中找出項(xiàng)之間的關(guān)系，也稱(chēng)之為購(gòu)物藍(lán)分析 （market basketanalysis）。例如，購(gòu)買(mǎi)鞋的顧客，有10%的可能也會(huì)買(mǎi)襪子，60%的買(mǎi)面包的顧客，也會(huì)買(mǎi)牛奶。這其中最有名的例子就是“尿布和啤酒”的故事了。關(guān)聯(lián)規(guī)則的應(yīng)用場(chǎng)合。在商業(yè)銷(xiāo)售上，關(guān)聯(lián)規(guī)則可用于交叉銷(xiāo)售，以得到更大的收入；在保險(xiǎn)業(yè)務(wù)方面，如果出現(xiàn)了不常見(jiàn)的索賠要求組合，則可能為欺詐，需要作進(jìn)一步的調(diào)查。在醫(yī)療方面，可找出可能的治療組合；在銀行方面，對(duì)顧客進(jìn)行分析，可以推薦感興趣的服務(wù)等等。Apriori algorithm是關(guān)聯(lián)規(guī)則里一項(xiàng)基本算法。
二、關(guān)聯(lián)算法的基本原理
該算法的基本思想是：首先找出所有的頻集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿(mǎn)足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項(xiàng)的所有規(guī)則，其中每一條規(guī)則的右部只有一項(xiàng)，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶(hù)給定的最小可信度的規(guī)則才被留下來(lái)。為了生成所有頻集，使用了遞推的方法
?
三、關(guān)聯(lián)算法的C++簡(jiǎn)單實(shí)現(xiàn)
（1）算法數(shù)據(jù)：
對(duì)給定數(shù)據(jù)集用Apriori算法進(jìn)行挖掘，找出其中的頻繁集并生成關(guān)聯(lián)規(guī)則。對(duì)下面數(shù)據(jù)集進(jìn)行挖掘：
?
對(duì)于數(shù)據(jù)集，取最小支持度minsup=2，最小置信度minconf=0.8。
（2）算法步驟：
① 首先單趟掃描數(shù)據(jù)集，計(jì)算各個(gè)一項(xiàng)集的支持度，根據(jù)給定的最小支持度閔值，得到一項(xiàng)頻繁集L1。
② 然后通過(guò)連接運(yùn)算，得到二項(xiàng)候選集，對(duì)每個(gè)候選集再次掃描數(shù)據(jù)集，得出每個(gè)候選集的支持度，再與最小支持度比較。得到二項(xiàng)頻繁集L2。
③ 如此進(jìn)行下去，直到不能連接產(chǎn)生新的候選集為止。
④ 對(duì)于找到的所有頻繁集，用規(guī)則提取算法進(jìn)行關(guān)聯(lián)規(guī)則的提取。
（3）C++算法的簡(jiǎn)單實(shí)現(xiàn)
①首先要在工程名文件夾里自己定義date.txt文檔存放數(shù)據(jù)，然后在main函數(shù)中用FILE* fp=fopen（“date.txt”，“r”）;將數(shù)據(jù)導(dǎo)入算法。
②定義int countL1［10］;找到各一維頻繁子集出現(xiàn)的次數(shù)。
定義char curL1［20］［2］;實(shí)現(xiàn)出現(xiàn)的一維子集。
由于給出的數(shù)據(jù)最多有4個(gè)數(shù)，所以同樣的我們要定義到4維來(lái)放數(shù)據(jù)。
int countL2［10］; //各二維頻繁子集出現(xiàn)的次數(shù)
char curL2［20］［3］; //出現(xiàn)的二維子集
int countL3［10］; //各三維頻繁子集出現(xiàn)的次數(shù)
char curL3［20］［4］; //出現(xiàn)的三維子集
char cur［50］［4］;
③定義int SizeStr（char* m） 得到字符串的長(zhǎng)度。實(shí)現(xiàn)代碼如下：
int SizeStr（char* m）
{
int i=0;
while（*（m+i）！=0）
{
i++;
}
return i;
}
④比較兩個(gè)字符串，如果相等返回true，否則返回false
bool OpD（char* x，char* y）
{
int i=0;
if（SizeStr（x）==SizeStr（y））
{
while（*（x+i）==*（y+i））
{
i++;
if（*（x+i）==0 && *（y+i）==0）
return true;
}
}
return false;
}
⑤通過(guò)void LoadItemL1（char **p） 得到所有1元的字串和各自出現(xiàn)的次數(shù)
void LoadItemL1（char **p）
{
int i，j，n=0，k=0;
char ch;
char* s;
int f;
memset（cur，0，sizeof（cur））;
for（i=0;i《20;i++）
{
curL1［i］［0］=0;
curL1［i］［1］=0;
}
for（j=0;j《10;j++）
countL1［j］=0;
for（i=0;i《10;i++）
for（j=0;j《4;j++）
{
ch=*（*（p+i）+j）;
if（ch==0）
break;
cur［n］［0］=ch;
n++;
}
curL1［0］［0］=cur［0］［0］;
curL1［0］［1］=cur［0］［1］;
k=0;
for（i=0;i《50;i++）
{
if（cur［i］==0）
break;
s=cur［i］;
f=1;
for（j=0;j《=k;j++）
{
if（OpD（s，curL1［j］））
{
f=0;
break;
}
}
if（f==1）
{
++k;
curL1［k］［0］=cur［i］［0］;
curL1［k］［1］=cur［i］［1］;
}
}
for（i=0;i《20;i++）
for（j=0;j《50;j++）
{
char* m;
m=curL1［i］;
if（*m==0）
break;
if（OpD（m，cur［j］））
countL1［i］++;
}
printf（“L1： \n ”）;
printf（“項(xiàng)集 支持度計(jì)數(shù)\n”）;
for（i=0;i《10;i++）
{
if（curL1［i］==0）
break;
if（countL1［i］》=2）
printf（“{I%s}： %d\n”，curL1［i］，countL1［i］）;
}
}
⑥通過(guò)void SubItem2（char **p） 得到所有的2元子串
void SubItem2（char **p）
{
int i，j，k，n=0;
char* s;
memset（cur，0，sizeof（cur））;
for（i=0;i《20;i++）
{
curL2［i］［0］=0;
curL2［i］［1］=0;
curL2［i］［2］=0;
}
for（i=0;i《10;i++）
countL2［i］=0;
for（k=0;k《10;k++）
{
s=*（p+k）;
if（SizeStr（s）《2）
continue;
for（i=0;i《SizeStr（s）;i++）
for（j=i+1;j《SizeStr（s）;j++）
{
if（*（s+j）==0）
break;
*（cur［n］+0）=*（s+i）;
*（cur［n］+1）=*（s+j）;
*（cur［n］+2）=0;
*（cur［n］+3）=0;
n++;
}
}
}
⑦通過(guò)void LoadItemL2（char **p） 得到各個(gè)2元頻繁子串出現(xiàn)的次數(shù)
void LoadItemL2（char **p）
{
int k，i，j;
char* s;
int f;
SubItem2（p）;
curL2［0］［0］=cur［0］［0］;
curL2［0］［1］=cur［0］［1］;
curL2［0］［2］=cur［0］［2］;
k=0;
for（i=0;i《50;i++）
{
if（cur［i］==0）
break;
s=cur［i］;
f=1;
for（j=0;j《=k;j++）
{
if（OpD（s，curL2［j］））
{
f=0;
break;
}
}
if（f==1）
{
++k;
curL2［k］［0］=cur［i］［0］;
curL2［k］［1］=cur［i］［1］;
curL2［k］［2］=cur［i］［2］;
}
}
for（i=0;i《20;i++）
for（j=0;j《50;j++）
{
s=curL2［i］;
if（*s==0）
break;
if（OpD（s，cur［j］））
countL2［i］++;
}
printf（“L2： \n”）;
printf（“項(xiàng)集 支持度計(jì)數(shù)\n”）;
for（i=0;i《10;i++）
{
if（curL2［i］==0）
break;
if（countL2［i］》=2）
printf（“{I%c，I%c}： %d\n”，curL2［i］［0］，curL2［i］［1］，countL2［i］）;
}
}
⑧通過(guò)定義void SubItem3（char **p） 得到所有3元的子串
void SubItem3（char **p）
{
char *s;
int i，j，h，m;
int n=0;
memset（cur，0，sizeof（cur））;
for（j=0;j《20;j++）
{
curL3［j］［0］=0;
curL3［j］［1］=0;
curL3［j］［2］=0;
curL3［j］［3］=0;
}
for（i=0;i《10;i++）
countL3［i］=0;
for（m=0;m《10;m++）
{
s=*（p+m）;
if（SizeStr（s）《3）
continue;
for（i=0;i《SizeStr（s）;i++）
for（j=i+1;j《SizeStr（s）;j++）
{
for（h=j+1;h《SizeStr（s）;h++）
{
if（*（s+h）==0）
break;
*（cur［n］+0）=*（s+i）;
*（cur［n］+1）=*（s+j）;
*（cur［n］+2）=*（s+h）;
*（cur［n］+3）=0;
n++;
}
}
}
}
⑨同樣我們要得到得到各個(gè)3元頻繁子串出現(xiàn)的次數(shù)
void LoadItemL3（char** p）
{
int k，i，j;
char* s;
int f;
SubItem3（p）;
curL3［0］［0］=cur［0］［0］;
curL3［0］［1］=cur［0］［1］;
curL3［0］［2］=cur［0］［2］;
curL3［0］［3］=cur［0］［3］;
k=0;
for（i=0;i《50;i++）
{
if（cur［i］==0）
break;
s=cur［i］;
f=1;
for（j=0;j《=k;j++）
{
if（OpD（s，curL3［j］））
{
f=0;
break;
}
}
if（f==1）
{
++k;
curL3［k］［0］=cur［i］［0］;
curL3［k］［1］=cur［i］［1］;
curL3［k］［2］=cur［i］［2］;
curL3［k］［3］=cur［i］［3］;
}
}
for（i=0;i《20;i++）
for（j=0;j《50;j++）
{
s=curL3［i］;
if（*s==0）
break;
if（OpD（s，cur［j］））
countL3［i］++;
}
printf（“L3： \n”）;
printf（“項(xiàng)集 支持度計(jì)數(shù)\n”）;
for（i=0;i《10;i++）
{
if（curL3［i］==0）
break;
if（countL3［i］》=2）
printf（“{I%c，I%c，I%c}： %d\n”，curL3［i］［0］，curL3［i］［1］，curL3［i］［2］，countL3［i］）;
}
}
⑩定義void LoadItemL4（char** p） 得到各個(gè)3元子串出現(xiàn)的次數(shù)
void LoadItemL4（char** p）
{
int i;
char* s;
int j=0;
for（i=0;i《10;i++）
{
s=*（p+i）;
if（SizeStr（s）==4）
j++;
}
printf（“四維子集出現(xiàn)的次數(shù)： %d\n”，j）;
printf（“沒(méi)有四維的頻繁子集，算法結(jié)束！ \n”）;
}
11通過(guò)void Support（char* w，int g） 得到關(guān)聯(lián)規(guī)則，并輸出結(jié)果
void Support（char* w，int g）
{
int i，j，k，n=0;
char* s;
float c=0.8，d=0;
memset（cur，0，sizeof（cur））;
s=w;
for（i=0;i《SizeStr（s）;i++）
{
*（cur［n］+0）=*（s+i）;
*（cur［n］+1）=0;
*（cur［n］+2）=0;
*（cur［n］+3）=0;
n++;
}
for（i=0;i《SizeStr（s）;i++）
for（j=i+1;j《SizeStr（s）;j++）
{
if（*（s+j）==0）
break;
*（cur［n］+0）=*（s+i）;
*（cur［n］+1）=*（s+j）;
*（cur［n］+2）=0;
*（cur［n］+3）=0;
n++;
}
for（i=0;i《10;i++）
{
if（SizeStr（cur［i］）==1）
{
for（j=0;j《10;j++）
{
if（OpD（cur［i］，curL1［j］））
{
d=countL3［g］/（float）countL1［j］;
if（d》=c）
printf（“{I%s}： %f”，curL1［i］，d）;
break;
}
}
}
if（SizeStr（cur［i］）==2）
{
for（j=0;j《10;j++）
{
if（OpD（cur［i］，curL2［j］））
{
d=countL3［g］/（float）countL2［j］;
if（d》=c）
printf（“{I%c，I%c}： %f \n”，curL2［j］［0］，curL2［j］［1］，d）;
break;
}
}
}
}
}
12最后通過(guò)main函數(shù)完成整過(guò)程序
int main（int argc， char* argv［］）
{
int i=0，j=0，k;
char buf［10］［6］;
char* p［10］;
char ch;
memset（buf，0，sizeof（buf））;
FILE* fp=fopen（“date.txt”，“r”）;
if（fp==NULL）
return 0;
ch=fgetc（fp）;
while（ch！=EOF）
{
if（ch==0xa || ch==0xd）
{
i++;
ch=fgetc（fp）;
j=0;
continue;
}
buf［i］［j］=ch;
j++;
ch=fgetc（fp）;
}
for（k=0;k《10;k++）
{
*（p+k）=buf［k］;
}
LoadItemL1（p）;
LoadItemL2（p）;
LoadItemL3（p）;
LoadItemL4（p）;
printf（“產(chǎn)生關(guān)聯(lián)規(guī)則： \n”）;
printf（“非空子集： 置信度：\n”）;
for（i=0;i《10;i++）
{
if（curL3［i］！=0 && countL3［i］》=2）
Support（curL3［i］，i）;
}
return 0;
}
（4）程序輸出結(jié)果：
四、學(xué)習(xí)心得體會(huì)
關(guān)聯(lián)算法基本原理學(xué)習(xí)思路簡(jiǎn)單，只需一步一步找出頻集。再通過(guò)支持度算出可信度，如對(duì)于A(yíng)—》C，support=support（{A，C}），confidence= support（{A，C}）/support（{A}）。其中頻繁子集的任何子集一定是頻繁的，子集頻繁父親一定頻繁。相對(duì)較難的的部分在于C++代碼的實(shí)現(xiàn)部分依次實(shí)現(xiàn)各個(gè)頻繁子集，完成整個(gè)程序。這學(xué)期在商務(wù)智能課中學(xué)習(xí)了數(shù)據(jù)挖掘的10大算法，數(shù)據(jù)挖掘十分經(jīng)典，掌握好一個(gè)簡(jiǎn)單的算法要下很功夫，在今后的工作中一定可以用到，我很慶幸這學(xué)期能選到這個(gè)課，在這之前聽(tīng)說(shuō)過(guò)數(shù)據(jù)挖掘但一直沒(méi)有機(jī)會(huì)接觸，原理容易理解但沒(méi)接觸到以前就沒(méi)有想過(guò)這樣考慮問(wèn)題，學(xué)習(xí)這個(gè)課程以后無(wú)論是知識(shí)面，智力上都是一個(gè)跳躍。還有也提醒我要多復(fù)習(xí)C++問(wèn)題的思考，這學(xué)期一直忙于網(wǎng)頁(yè)編程，忘記了上學(xué)期說(shuō)要復(fù)習(xí)C++數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)。希望以后還有機(jī)會(huì)能選到老師的課。
工商網(wǎng)監(jiān)
評(píng)論