数据挖掘BUC计算冰山立方体及Python实现

灰太狼 2022-05-26 10:00 126阅读 0赞

因课程实验所需，对BUC算法进行了Python实现，过程多有坎坷，在此一记，以助后人。

# 一、关于BUC及冰山立方体的介绍 #

可参照如下链接：

【数据挖掘概念与技术】学习笔记5-数据立方体技术 - CSDN博客  
[https://blog.csdn.net/mamianskyma/article/details/15494471][https_blog.csdn.net_mamianskyma_article_details_15494471]

感觉讲的还ok

# 二、BUC的python实现 #

先附上输入，输出与代码。

输入：test.csv

a1,b1,c1,d1
    a1,b1,c1,d2
    a1,b1,c2,d1
    a1,b1,c2,d2
    a2,b1,c1,d2
    a2,b2,c2,d2
    a3,b3,c1,d1
    a4,b4,c1,d2

输出：result.txt

格式为符合条件的取值与count的元组数目（设定阈值min\_sup为3）

a1	4
    a1,b1	4
    b1	5
    b1,c1	3
    b1,d2	3
    c1	5
    c1,d2	3
    c2	3
    d1	3
    d2	5

代码：

编写环境：PyCharm 2018.01      Python3.6

有些冗余，未进行后期修改

fr =open(r"test.csv",'r')
    ls =[]  #全部数据
    for line in fr:
        line =line.replace("\n","")
        ls.append(line.split(","))
    fr.close()
    #读入文件结束
    
    '''
    n是维度数目
    numOfAllN是所有维度的取值个数数组
    min_sup是阈值
    '''
    min_sup=3
    
    numOfAllN=[0]*len(ls[0]) #所有维度的取值个数数组
    valueOfAllN=[]   #所有维度的取值集合
    #计算每个维度的取值个数，存储在数组numOfN中。
    for j in range(len(numOfAllN)):
        valueOfSingleN = []  # 单个维度取值集合
        for i in range(len(ls)):
            if(ls[i][j] not in valueOfSingleN):
                valueOfSingleN.append(ls[i][j])
        valueOfAllN.append(valueOfSingleN)
        numOfAllN[j]=len(valueOfSingleN)
    
    # print (numOfAllN)  #[4, 4, 2, 2]
    # print (valueOfAllN)
    
    def count(list):
        sum = 0
        xx=ls
        for x in range(len(list)):
            temp1 = temp2 = temp3 = temp4 = []
            if ("a" in list[x]):
                for i in range(len(xx)):
                    if (xx[i][0] == list[x]):
                        temp1.append(xx[i])
            elif("b" in list[x]):
                temp1=xx
                for i in range(len(temp1)):
                    if (temp1[i][1] == list[x]):
                        temp2.append(temp1[i])
            elif ("c" in list[x]):
                temp2=xx
                for i in range(len(temp2)):
                    if (temp2[i][2] == list[x]):
                        temp3.append(temp2[i])
            elif ("d" in list[x]):
                temp3=xx
                for i in range(len(temp3)):
                    if (temp3[i][3] == list[x]):
                        temp4.append(temp3[i])
            xx=temp4
            # print (xx)
        sum=len(temp4)
        # print (temp4)
        return sum
    
    result=[]
    
    def BUC(list,n,startD):
        # print ("开始一次BUC")
        len_list=len(list)
        # for i in range(len_list,n): #i是第几维度
        for i in range(startD, n):  # i是第几维度
            for j in range(numOfAllN[i]): #j是第i维度的第j个取值
                # print (list)
                # print (valueOfAllN[i][j])
                list.append(valueOfAllN[i][j])
                # print ("list是"+str(list))
                # print (list)
                # print (i)
                count_list=count(list)
                if(count_list>=min_sup):
                    # print ("结果增加前是" + str(result))
                    result.append(list)
                    # print ("结果增加后是"+str(result))
                    result2=[]
                    #去重
                    for singleResult in result:
                        if(singleResult not in result2):
                            result2.append(singleResult)
                    result2=result2[0]
                    fw=open("result.txt","a")
                    for sss in range(len(result2)-1):
                        fw.write(str(result2[sss]) + ",")
                    fw.write(str(result2[-1]) +'\t'+str(count_list)+ "\n")
                    fw.close()
                    startD=startD+1
                    BUC(list,n,startD)
                else:
                    # print ("删除前的list"+str(list))
                    list.pop()
                    # print ("删除后的list" + str(list))
        # print ("完成一次BUC")
        if(len(list)>=1):
            list.pop()
    
    BUC([],4,0)
    
    fr = open(r"result.txt", 'r')
    data= []
    data = fr.readlines()
    fr.close()
    for i in range(len(data)):
        data[i]=data[i].replace("\n","")
    print (data)s

# 三、代码解释 #

**思路概述**：

本实验通过计算元组个数的方法对冰山立方体进行统计。实验难点主要在于count函数的编写以及BUC递归的传递参数及逻辑。

数据集为自己编写的数据，格式为4维数据（A、B、C、D），其中每维的取值分别为

A:a1、a2、a3、a4

B:b1、b2、b3、b4

C:c1、c2

D:d1、d2

这样总共可以产生至多64条非重复数据，我手动编写了8条来做输入数据。可见上图输入数据。

设定阈值min\_sup为3，编写运行代码进行递归运算，最终生成result.txt。

**难点解释：**

**1.count函数的编写**

因为读取的是csv文件，对pandas的应用并不熟练，故而采取手动编写count函数。开始错误的以为可以以list数组的格式来进行比对，只要前n个字符完全匹配然后就可以进行count操作。后来发现并不是这样，因为list并不一定是全连续的，比如对（a1，d2）进行count，则count函数就会失效。

反复思索后，我联想到excel软件的筛选操作，考虑其原理，我意识到需要对单个维度进行多次比对，最终综合筛选出的结果才是真正需要的。如（a1，d2），应该对A维筛选“a1”，在其结果中再筛选D维值为“d2”的，这样得到的元组数目才是正确的count。

但问题在于，真正实现的时候，作为桥梁的list并不能起到识别哪一维的作用，迫于无奈，最终只能以a，b，c，d作为识别判据。这导致程序具有了一定的局限性，输入数据只能为a，b，c，d开头。

**2.BUC递归的传递参数及逻辑**

课本上的伪代码参数过于繁杂，故而我再理解BUC的思想后并未参照课本的伪代码进行实现，这样导致最严重的问题就是递归传递参数的缺失。

开始我只为递归传入两个参数，即BUC(list,n),list为递归之前传入的先决条件，如当判断A=a1，count=4>3时，进行BUC递归，list就是\[‘a1’\]。n为维度总数，此实验就是ABCD四个维度，n=4。这是用于判断for循环结束的条件。

在此基础上我编写了许多代码，前前后后也出了不少错误，此处不详细说明。最麻烦的问题在于在递归的过程中，由于python赋值的引用问题，即copy与deepcopy的区别（此处可自行百度或参考下面的链接），导致不能在内存中一直存储最终的result数组，故而我采取略微极端的做法，生成一个符合条件的结果就写入文件result.txt，采取追加写的方式，最终也可以得到正确结果。

Python-copy()与deepcopy()区别 - CSDN博客

[https://blog.csdn.net/qq\_32907349/article/details/52190796][https_blog.csdn.net_qq_32907349_article_details_52190796]

回到BUC（）参数的问题，解决完上述问题后，得到的result结果依旧不对，经过观察发现，存在（b1，b1）这样的“符合条件”的数组。问题就定位到递归函数的for循环。

fori in range(len\_list,n):

我发现我是以len\_list作为for循环的开始，这样就导致当list为\[‘b1’\]时，i依旧从1（即第二维B）开始，故而产生了（b1，b1）的问题。

如何解决？经过思索我发现，每一次BUC递归都会向前推进一个维度，这才是维度改变的根本原因，而非是list的长度。因为list的长度大多数情况下会随着递归的推进而不断+1，但是回溯时如list=\[‘b1’\]时，list的长度就不会与递归保持一致了。

明白了这点，马上改写函数，将BUC传递参数由BUC(list,n)变为BUC(list,n,startD)，startD是开始的维度数，每次进入下一次递归前就+1，for i in range(len\_list,n)也变成for i in range(startD, n)，这样就解决了诸如（b1，b1）的问题。

至此，程序难点编写完成。

**程序局限：**

由于count函数的限制，只能接受数据集为a，b，c，d开头的输入数据。

[https_blog.csdn.net_mamianskyma_article_details_15494471]: https://blog.csdn.net/mamianskyma/article/details/15494471
[https_blog.csdn.net_qq_32907349_article_details_52190796]: https://blog.csdn.net/qq_32907349/article/details/52190796