载入中。。。 'S bLog
 
载入中。。。
 
载入中。。。
载入中。。。
载入中。。。
载入中。。。
载入中。。。
 
填写您的邮件地址,订阅我们的精彩内容:


 
一些数据挖掘题与做的答案.
[ 2012/8/28 22:25:00 | By: 梦翔儿 ]
 

梦翔儿学数据挖掘课时,做的一些题与答案,参考数目是韩家玮的数据挖掘教材.

1. 说明:为什么要进行数据预处理?数据预处理包括那些内容?

答:现实世界的数据库极易受噪声、丢失数据和不一致数据的侵扰,数据库往往是内容庞大,原始数据往往是不完整的,仅包含聚集数据,含躁声的,不一致的,来自异构数据源、低质量的。针对这样的数据进行处理,这也会导致低质量的挖掘结果。

数据预处理包括:数据清理、数据集成和数据变换、数据归约(泛化、离散化、概念分层处理等)

2. 请简要说明维归约的几种常用方法。

答:维度归约使用数据编码或变换,以便得到原数据的归约或“压缩”表示。如果原数据可以由压缩数据重新构造而不丢失任何信息,则该数据归约是无损的,如果我们只能构造原数据的看近似表示,则该数据归约是有损的。流行的有效的有损的维归约方法有小波变换和主成分分析。

1)小波变换 离散小波变换(DWT),是一种线性信号处理技术,当用于数据向量X时,将它变换成的数值上不同的小波系数向量X’。两个向量具有相同的长度,当这种技术用于数据归约时,每个元组看作是一个n维数据向量,描述n个数据库属性在元组上的n个测量值。小波变换可以用于多维数据。详见书P49-50页。

2)主要成分分析(PCA):搜索K个最能代表数据的n维正交向量,其中K<<n。这样,原来的数据投影到一个小得多的空间,导致维度归约。其特点是计算开销低,可用于有序和无序的属性,并可以处理稀疏和倾斜数据。详见书:P51

 

 

3. Apriori算法,找出数据库D中最小支持数为23-频繁项目集。

 

数据库D

事务号

事务中的项目

001

A, B, E

002

B, D

003

B, C

004

A, B, D

005

A, C

006

B, C

007

A, C

008

A, B, C, E

009

A, B, C

 

解:Apriori计算过程如下:

1)扫描D,对每个侯选计数,C1

 项集

支持度计数

A

6

B

7

C

6

D

2

E

2

(2) 比较侯选支持度计数与最小支持度计数,因为支持度都大于2,所以得到,L1

项集

支持度计数

A

6

B

7

C

6

D

2

E

2

(3) L1产生侯选C2,并对每个侯选计数,得到:

项集

支持度计数

A,B

4

A,C

4

A,D

1

B,C

4

B,D

2

{B,E}

2

{C,D}

0

{C,E}

1

(4) 比较侯选支持计数与最小支持度计数得到L2

项集

支持度计数

A,B

4

A,C

4

B,C

4

B,D

2

{B,E}

2

(5) L2产生侯选C3

项集

支持度计数

A,B,C

2

A,B,D

1

A,B,E

2

(6) 比较侯选支持度计数与最小支持度计数得,3频繁项集结果:

项集

支持度计数

A,B,C

2

A,B,E

2

 

4. 给出数据库DFP-树的构造过程,最小支持数为3

 

数据库D

TID

D中的项目

T100

{f, a, c, d, g, i, m, p}

T200

{a, b, c, f, l, m, o}

T300

{b, f, h, j, o, w}

T400

{b, c, k, s, p}

T500

{a, f, c, e, l, p, m, n}

解:书P157

(1)先计算频繁项集:

项集

支持度计数

a

3

b

3

c

4

d

1

e

1

{f}

4

{g}

1

{h}

1

{i}

1

{j}

1

{k}

1

{l}

2

{m}

3

{n}

1

{o}

2

{p}

3

(2) 比较侯选支持度计数与最小支持度计数,大于3的得到,L1

项集

支持度计数

a

3

b

3

c

4

{f}

4

{m}

3

{p}

3

3)按递减支持度排序,得到L序列:

项集

支持度计数

c

4

{f}

4

a

3

b

3

{m}

3

{p}

3

(4)扫描D来建树:

T100L中次序处理得到:T100:c, f, a, m,p

T200L中次序处理得到:T200:c, f, a,b, m

T300L中次序处理得到:T300: f, b

T400L中次序处理得到:T400:c,b,p

T500L中次序处理得到:T500:c, f, a, m,p

也就是最后得到的结果是:

5. 根据Y样本集合,利用朴素贝叶斯分类方法,确定测试样本X={A1=1, A2=2, A3=2}

Y样本集合为:

样本

A1

A2

A3

C

1

1

2

1

1

2

0

0

1

1

3

2

1

2

2

4

1

2

1

2

5

0

1

2

1

6

2

2

2

2

7

1

0

3

1

 

(1) 在类标号属性C具有两个不同值,即{1,2}

C1对就于类1C2对就于类2

希望分类的元组X=A1=1A2=2A3=2}。

(2) 需要最大化P(X|Ci)i=12。每个类的先验概率P(Ci)可以根据训练元组计算:

P(C=1)=4/7=0.571

P(C=2)=3/7=0.429

(3) 为了计算P(X|Ci)i=12,计算下面的条件概率

   PA1=1|C=1=2/4=0.5

   PA1=1|C=2=1/3=0.333

   PA2=2|C=1=1/4=0.25

   PA2=2|C=2=2/3=0.667

   PA3=2|C=1=1/4=0.25

   PA3=2|C=2=2/3=0.667

(4) 使用上面的概率得到:

   PX|C=1= PA1=1|C=1* PA2=2|C=1* PA3=2|C=1=0.5*0.25*0.25=0.03125

   PX|C=2= PA1=1|C=2* PA2=2|C=2* PA3=2|C=2=0.333*0.667*0.667=0.1481

(5) 为了发现最大化P(X|Ci)P(Ci)的类,计算

   PX|C=1PC=1=0.3125*0.571=0.0178

   PX|C=2PC=2=0.1481*0.429=0.0635

(6) 结论:对于元组X,朴素贝叶斯分类器预测元组X的类为C=2

6. K-均值方法将下面数据集(用8(xy)表示空间点)聚类为3个簇。

A1(2, 10), A2(2, 5), A3(8, 4), B1(5, 8), B2(7, 5), B3(6, 4), C1(1, 2), C2(4, 9)

注释:各点的距离函数可用欧几里德距离或曼哈坦距离。

用欧几里德距离求得:

******************************************************

A1C2B1为一组,其中心值为(3.7,9)

1个分组内容为:

2,10

5,8

4,9

A2,C1为一组,其中心值为(717

2个分组内容为:

2,5

1,2

B2A3B3为一组,其中心值为(11.7,15.7

3个分组内容为:

8,4

7,5

6,4

******************************************************

使用Java完成的算法

KAverage.java

======

import java.io.BufferedReader;   
import java.io.FileNotFoundException;   
import java.io.FileReader;   
import java.io.IOException;   
  
public class KAverage {   
    private int sampleCount = 0;   
    private int dimensionCount = 0;   
    private int centerCount = 0;   
    private double[][] sampleValues;   
    private double[][] centers;   
    private double[][] tmpCenters;   
    private String dataFile = "";   
  
    /**  
     * 通过构造器传人数据文件  
     */  
    public KAverage(String dataFile) throws NumberInvalieException {   
        this.dataFile = dataFile;   
    }   
  
    /**  
     * 第一行为s;d;c含义分别为样例的数目,每个样例特征的维数,聚类中心个数 文件格式为d[,d]...;d[,d]... 如:1,2;2,3;1,5  
     * 每一维之间用,隔开,每个样例间用;隔开。结尾没有';' 可以有多行  
     */  
  
    private int initData(String fileName) {   
        String line;   
        String samplesValue[];   
        String dimensionsValue[] = new String[dimensionCount];   
        BufferedReader in;   
        try {   
            in = new BufferedReader(new FileReader(fileName));   
        } catch (FileNotFoundException e) {   
            e.printStackTrace();   
            return -1;   
        }   
        /*  
         * 预处理样本,允许后面几维为0时,不写入文件  
         */  
        for (int i = 0; i < sampleCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                sampleValues[i][j] = 0;   
            }   
        }   
  
        int i = 0;   
        double tmpValue = 0.0;   
        try {   
            line = in.readLine();   
            String params[] = line.split(";");   
            if (params.length != 3) {// 必须为3个参数,否则错误   
                return -1;   
            }   
            /**  
             * 获取参数  
             */  
            this.sampleCount = Integer.parseInt(params[0]);   
            this.dimensionCount = Integer.parseInt(params[1]);   
            this.centerCount = Integer.parseInt(params[2]);   
            if (sampleCount <= 0 || dimensionCount <= 0 || centerCount <= 0) {   
                throw new NumberInvalieException(line);   
            }   
            if (sampleCount < centerCount) {   
                throw new NumberInvalieException(line);   
            }   
  
            sampleValues = new double[sampleCount][dimensionCount + 1];   
            centers = new double[centerCount][dimensionCount];   
            tmpCenters = new double[centerCount][dimensionCount];   
  
            while ((line = in.readLine()) != null) {   
                samplesValue = line.split(";");   
                for (int j = 0; j < samplesValue.length; j++) {   
                    dimensionsValue = samplesValue[j].split(",");   
                    for (int k = 0; k < dimensionsValue.length; k++) {   
                        tmpValue = Double.parseDouble(dimensionsValue[k]);   
                        sampleValues[i][k] = tmpValue;   
                    }   
                    i++;   
                }   
            }   
  
        } catch (IOException e) {   
            e.printStackTrace();   
            return -2;   
        } catch (Exception e) {   
            e.printStackTrace();   
            return -3;   
        }   
        return 1;   
    }   
  
    /**  
     * 返回样本中第s1个和第s2个间的欧式距离  
     */  
    @SuppressWarnings("unused")
 private double getDistance(final int s1, final int s2) throws NumberInvalieException {   
        double distance = 0.0;   
        if (s1 < 0 || s1 >= sampleCount || s2 < 0 || s2 >= sampleCount) {   
            throw new NumberInvalieException(dataFile);   
        }   
        for (int i = 0; i < dimensionCount; i++) {   
            distance += (sampleValues[s1][i] - sampleValues[s2][i])   
                    * (sampleValues[s1][i] - sampleValues[s2][i]);   
        }   
        return distance;   
    }   
  
    /**  
     * 返回给定两个向量间的欧式距离  
     */  
    private double getDistance(double s1[], double s2[]) {   
        double distance = 0.0;   
        for (int i = 0; i < dimensionCount; i++) {   
            distance += (s1[i] - s2[i]) * (s1[i] - s2[i]); 
            //System.out.println(distance);
        }  

        return distance;   
    }   
  
    /**  
     * 更新样本中第s个样本的最近中心  
     */  
    private int getNearestCenter(int s) {   
        int center = 0;   
        double minDistance = Double.MAX_VALUE;   
        double distance = 0.0;   
        for (int i = 0; i < centerCount; i++) {   
            distance = getDistance(sampleValues[s], centers[i]);   
            if (distance < minDistance) {   
                minDistance = distance;   
                center = i;   
            }   
        }   
        sampleValues[s][dimensionCount] = center;
       //System.out.println(center);
        return center;   
    }   
  
    /**  
     * 更新所有中心  
     */  
    private void updateCenters() {   
        double center[] = new double[dimensionCount];   
        for (int i = 0; i < dimensionCount; i++) {   
            center[i] = 0;   
        }   
        int count = 0;   
        for (int i = 0; i < centerCount; i++) {   
            count = 0;   
            for (int j = 0; j < sampleCount; j++) {   
                if (sampleValues[j][dimensionCount] == i) {   
                    count++;   
                    for (int k = 0; k < dimensionCount; k++) {   
                        center[k] += sampleValues[j][k]; 
                    }   
                }   
            }   
            for (int j = 0; j < dimensionCount; j++) {   
                centers[i][j] = center[j] / count;
                System.out.println("i="+(i+1)+"centers="+centers[i][j]);
            }
        }   
    }   
  
    /**  
     * 判断算法是否终止  
     */  
    private boolean toBeContinued() {   
        for (int i = 0; i < centerCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                if (tmpCenters[i][j] != centers[i][j]) {   
                    return true;   
                }   
            }   
        }   
        return false;   
    }   
  
    /**  
     * 关键方法,调用其他方法,处理数据  
     */  
    public void doCaculate() {   
        initData(dataFile);   
  
        for (int i = 0; i < centerCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                centers[i][j] = sampleValues[i][j];   
            }   
        }   
        for (int i = 0; i < centerCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                tmpCenters[i][j] = 0;   
            }   
        }   
  
        while (toBeContinued()) {   
            for (int i = 0; i < sampleCount; i++) {   
                getNearestCenter(i);   
            }   
            for (int i = 0; i < centerCount; i++) {   
                for (int j = 0; j < dimensionCount; j++) {   
                    tmpCenters[i][j] = centers[i][j];   
                }   
            }   
            updateCenters();   
            System.out   
                    .println("******************************************************");   
            showResultData();   
        }   
    }   
  
    /*  
     * 显示数据  
     */  
    private void showSampleData() {   
        for (int i = 0; i < sampleCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                if (j == 0) {   
                    System.out.print(sampleValues[i][j]);   
                } else {   
                    System.out.print("," + sampleValues[i][j]);   
                }   
            }   
            System.out.println();   
        }   
    }   
  
    /*  
     * 分组显示结果  
     */  
    private void showResultData() {   
        for (int i = 0; i < centerCount; i++) {   
            System.out.println("第" + (i + 1) + "个分组内容为:");   
            for (int j = 0; j < sampleCount; j++) {   
                if (sampleValues[j][dimensionCount] == i) {   
                    for (int k = 0; k <= dimensionCount; k++) {   
                        if (k == 0) {   
                            System.out.print(sampleValues[j][k]);   
                        } else {   
                            System.out.print("," + sampleValues[j][k]);   
                        }   
                    }   
                    System.out.println();   
                }   
            }   
        }   
    }   
  
    public static void main(String[] args) {   
        /*  
         *也可以通过命令行得到参数  
         */  
        String fileName = "D:\\sample.txt";   
        if(args.length > 0){   
            fileName = args[0];   
        }   
           
        try {   
            KAverage ka = new KAverage(fileName);   
            ka.doCaculate();   
            System.out   
                    .println("***************************<<result>>**************************");   
            ka.showResultData();   
        } catch (Exception e) {   
            e.printStackTrace();   
        }   
    }   
}

=======

NumberInvalieException.java

=======

/*  
 * 根据自己的需要定义一些异常,使得系统性更强  
 */  
public class NumberInvalieException extends Exception {   
    private String cause;   
       
    public NumberInvalieException(String cause){   
        if(cause == null || "".equals(cause)){   
            this.cause = "unknow";   
        }else{   
            this.cause = cause;   
        }   
    }   
    @Override  
    public String toString() {   
        return "Number Invalie!Cause by " + cause;   
    }   
}  

=========

数据集sample.txt

------
8;2;3
2,10;2,5;8,4;5,8;7,5;6,4;1,2;4,9;

==========

部分内容参考自教材与网络.

 
 
  • 标签:数据挖掘 
  • 发表评论:
    载入中。。。

     
     
     

    梦翔儿网站 梦飞翔的地方 http://www.dreamflier.net
    中华人民共和国信息产业部TCP/IP系统 备案序号:辽ICP备09000550号

    Powered by Oblog.