CWYAlpha

Just another WordPress.com site

Archive for 八月 2012

Thought this was cool: 为神马android NFC不能模拟RFID Tag

leave a comment »

今天研究了一下这个玩意。

  1. Galaxy Nexus的2.3 ROM可以用com.pocketluxus.nfclassic 这个 nfca.apk模拟。有人成功过
  2. Nexus S可以用一个定制过的firmware来打开驱动的卡模拟模式,模拟任意RFID Tag。步骤非常麻烦。需要编译android源码(我日)

至于什么普通手机可以读取RFID Tag,而不能模拟呢?

国内的一些说法是,rfid卡加密了,没法模拟。其实这是错误的。

我在XDA翻了下一些理论,大概是这样的:

RFID/ID卡分两种,一种是只读的,一种是可写的。

比如门禁卡,就是只读的,然后门禁系统有个白名单,列表允许的uid就可以开门。只读的信息不可能变的。所以加密了也能模拟。

比如公交卡,是可写的,余额信息是写入ID卡内的。有的数据有加密,有的没有。

(第一种情况其实可以用xda大神写的ReTag来把数据强行写入)

那为什么手机有NFC芯片却不能任意模拟门禁卡RFID tag呢?

RFID都有一个唯一uid,门禁卡的这个uid是静态的。关键是NFC芯片厂商为了安全,每次NFC芯片刷卡,都会动态随机生成一个新的uid。要强制把这个uid改成静态,就需要修改驱动和firmware了。

目前三桑的S Beam和GoogleWallet都是动态uid的。并不能直接支持自定义静态uid。

所以,等待大神的hack吧。xda上已经有人研究出来了,但是app只是小范围分享。

如果这玩意公开了估计很多学校、写字楼、酒店、公共交通刷卡设备报要报废。

from est's blog: http://blog.est.im/post/30566340794

Advertisements

Written by cwyalpha

八月 31, 2012 at 4:08 上午

发表在 Uncategorized

Thought this was cool: 为什么处理排序的数组要比非排序的快?

leave a comment »

参考Why is processing a sorted array faster than an unsorted array?

问题

看以下代码:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;


    // !!! with this, the next loop runs faster
    std::sort(data, data + arraySize);


    // test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

问题就在于,去掉std::sort那一行,以上代码将运行更长的时间。在我的机器上未去掉std::sort耗时8.99s,去掉后耗时24.78s。编译器使用的是gcc4.4.3。事实上,以上代码跟编译器没有关系,甚至跟语言没有关系。那这是为什么呢?

这跟处理这个数组的逻辑有非常大的关系。如以上代码所示,这个循环里有个条件判断。条件判断被编译成二进制代码后,就是一个跳转指令,类似:

具体为什么会不同,这涉及到计算机CPU执行指令时的行为。

CPU的流水线指令执行

想象现在有一堆指令等待CPU去执行,那么CPU是如何执行的呢?具体的细节可以找一本计算机组成原理的书来看。CPU执行一堆指令时,并不是单纯地一条一条取出来执行,而是按照一种流水线的方式,在CPU真正执行一条指令前,这条指令就像工厂里流水线生产的产品一样,已经被经过一些处理。简单来说,一条指令可能经过这些过程:取指(Fetch)、解码(Decode)、执行(Execute)、放回(Write-back)。

假设现在有指令序列ABCDEFG。当CPU正在执行(execute)指令A时,CPU的其他处理单元(CPU是由若干部件构成的)其实已经预先处理到了指令A后面的指令,例如B可能已经被解码,C已经被取指。这就是流水线执行,这可以保证CPU高效地执行指令。

Branch Prediction

如上所说,CPU在执行一堆顺序执行的指令时,因为对于执行指令的部件来说,其基本不需要等待,因为诸如取指、解码这些过程早就被做了。但是,当CPU面临非顺序执行的指令序列时,例如之前提到的跳转指令,情况会怎样呢?

取指、解码这些CPU单元并不知道程序流程会跳转,只有当CPU执行到跳转指令本身时,才知道该不该跳转。所以,取指解码这些单元就会继续取跳转指令之后的指令。当CPU执行到跳转指令时,如果真的发生了跳转,那么之前的预处理(取指、解码)就白做了。这个时候,CPU得从跳转目标处临时取指、解码,然后才开始执行,这意味着:CPU停了若干个时钟周期!

这其实是个问题,如果CPU的设计放任这个问题,那么其速度就很难提升起来。为此,人们发明了一种技术,称为branch prediction,也就是分支预测。分支预测的作用,就是预测某个跳转指令是否会跳转。而CPU就根据自己的预测到目标地址取指令。这样,即可从一定程度提高运行速度。当然,分支预测在实现上有很多方法。

简单的预测可以直接使用之前的实际执行结果。例如某个跳转指令某一次产生了跳转,那么下一次执行该指令时,CPU就直接从跳转目标地址处取指,而不是该跳转指令的下一条指令。

答案

了解了以上信息后,文章开头提出的问题就可以解释了。这个代码中有一个循环,这个循环里有一个条件判断。每一次CPU执行这个条件判断时,CPU都可能跳转到循环开始处的指令,即不执行if后的指令。使用分支预测技术,当处理已经排序的数组时,在若干次data[c]>=128都不成立时(或第一次不成立时,取决于分支预测的实现),CPU预测这个分支是始终会跳转到循环开始的指令时,这个时候CPU将保持有效的执行,不需要重新等待到新的地址取指;同样,当data[c]>=128条件成立若干次后,CPU也可以预测这个分支是不必跳转的,那么这个时候CPU也可以保持高效执行。

相反,如果是无序的数组,CPU的分支预测在很大程度上都无法预测成功,基本就是50%的预测成功概率,这将消耗大量的时间,因为CPU很多时间都会等待取指单元重新取指。

本文完。最后感叹下stackoverflow上这个帖子里那个老外回答问题的专业性,我要是楼主早就感动得涕泪横飞了。感谢每一个传播知识的人。

参考资料

  1. http://blog.sina.com.cn/s/blog_6c673e570100zfmo.html
  2. http://www.cnblogs.com/dongliqian/archive/2012/04/05/2433847.html
  3. http://en.wikipedia.org/wiki/Branch_predictor

原文地址:http://codemacro.com/2012/08/29/branch-predictor/

written byKevin Lynx posted athttp://codemacro.com


0

   

0

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 0
|
10000+ 本编程/Linux PDF/CHM 电子书下载

from IT牛人博客聚合网站: http://www.udpwork.com/item/8032.html

Written by cwyalpha

八月 30, 2012 at 11:00 上午

发表在 Uncategorized

Thought this was cool: EM算法的R实现和高斯混合模型

leave a comment »

EM(Expectatioin-Maximalization)算法即期望最大算法,被誉为是数据挖掘的十大算法之一。它是在概率模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测到的隐变量。最大期望算法经过两个步骤交替进行计算,第一步是计算期望(E),也就是将隐藏变量象能够观测到的一样包含在内,从而计算最大似然的期望值;另外一步是最大化(M),也就是最大化在 E 步上找到的最大似然的期望值从而计算参数的最大似然估计。M 步上找到的参数然后用于另外一个 E 步计算,这个过程不断交替进行。对于信息缺失的数据来说,EM算法是一种极有效的工具,我们先用一个简单例子来理解EM算法,并将其应用到GMM(高斯混合模型)中去。

幼儿园里老师给a,b,c,d四个小朋友发糖吃,但老师有点偏心,不同小朋友得到糖的概率不同,p(a)=0.5, p(b)=miu, p(c)=2*miu, p(d)=0.5-3*miu 如果确定了参数miu,概率分布就知道了。我们可以通过观察样本数据来推测参数。设四人实际得到糖果数目为(a,b,c,d),可以用ML(极大似然),估计出miu=(b+c)/6*(b+c+d),假如某一天四个小朋友分别得到了(40,18,0,23)个糖。根据公式可求出miu为0.1。在信息完整条件下,ML方法是很容易估计参数的。

假设情况再复杂一点:知道c和d二人得到的糖果数,也知道a与b二人的糖果数之和为h,如何来估计出参数miu呢?前面我们知道了,如果观察到a,b,c,d就可以用ML估计出miu。反之,如果miu已知,根据概率期望 a/b=0.5/miu,又有a+b=h。由两个式子可得到 a=0.5*h/(0.5+miu)和b=miu*h/(0.5+miu)。此时我们面临一个两难的境地,a,b需要miu才能求出来,miu需要a,b才能求出来。有点类似岸上的八戒和河里的沙僧的对话:你先上来,你先下来,你先上来……

那么一种思路就是一方先让一步,暂且先抛出一个随机的初值,然后用对方算出的数值反复迭代计算。直到计算结果收敛为止。这就是EM算法的思路,我们来看看用R来实现这种思路:

# 已知条件

h = 20
c = 10
d = 10
 
# 随机初始两个未知量
miu = runif(1,0,1/6)
b = round(runif(1,1,20))
 
iter = 1
nonstop=TRUE
while (nonstop) {
# E步骤,根据假设的miu来算b
b = c(b,miu[iter]*h/(0.5+miu[iter]))
# M步骤,根据上面算出的b再来计算miu
miu = c(miu,(b[iter+1] + c)/(6*(b[iter+1]+c+d)))
# 记录循环次数
iter = iter + 1
# 如果前后两次的计算结果差距很小则退出
nonstop = (miu[iter]-miu[iter-1]>10^(-4))
}
print(cbind(miu,b))
当循环到第四次时结果已经收敛,miu为0.094,b为3.18

EM算法在高斯混合模型GMM(Gaussian Mixture Model )中有很重要的用途。简单来讲GMM就是一些高斯分布的组合。如果我们已知观测到的数据的类别,则可以根据ML来估计出GMM的参数。反之,对于没有类别信息一堆数据,如果我们已知GMM的参数,可以很容易用贝叶斯公式将它们归入不同的类中;但尴尬的问题是我们即不知道GMM参数,也不知道观测数据的类别。以下面生成的一维数据为例,我们希望找到这两个高斯分布的参数,同时为这些数据分类。
# 设置模拟参数
miu1 <- 3
miu2 <- -2
sigma1 <- 1
sigma2 <- 2
alpha1 <- 0.4
alpha2 <- 0.6
# 生成两种高斯分布的样本
n <- 5000
x <- rep(0,n)
n1 <- floor(n*alpha1)
n2 <- n - n1
x[1:n1] <- rnorm(n1)*sigma1 + miu1
x[(n1+1):n] <- rnorm(n2)*sigma2 + miu2
hist(x,freq=F)
lines(density(x),col='red')
下面用EM算法来估计GMM的参数。

# 设置初始值
m <- 2
miu <- runif(m)
sigma <- runif(m)
alpha <- c(0.2,0.8)
prob <- matrix(rep(0,n*m),ncol=m)
 
for (step in 1:100){
# E步骤
for (j in 1:m){
prob[,j]<- sapply(x,dnorm,miu[j],sigma[j])
}
sumprob <- rowSums(prob)
prob<- prob/sumprob
 
oldmiu <- miu
oldsigma <- sigma
oldalpha <- alpha
 
# M步骤
for (j in 1:m){
p1 <- sum(prob[ ,j])
p2 <- sum(prob[ ,j]*x)
miu[j] <- p2/p1
alpha[j] <- p1/n
p3 <- sum(prob[ ,j]*(x-miu[j])^2)
sigma[j] <- sqrt(p3/p1)
}
 
# 变化
epsilo <- 1e-4
if (sum(abs(miu-oldmiu))<epsilo &
sum(abs(sigma-oldsigma))<epsilo &
sum(abs(alpha-oldalpha))<epsilo) break
cat('step',step,'miu',miu,'sigma',sigma,'alpha',alpha,'\n')
}
在33次循环之后运算结果趋于稳定,估计的miu为(-2.2,2.8),sigma为(1.82,1.14)

GMM 模型常用于基于模型的聚类分析,GMM中的每一个高斯分布都可以代表数据的一类,整个数据就是多个高斯分布的混合。在R中的mclust包中的Mclust函数可以用来进行基于GMM的聚类分析。下面即是以最常用的iris数据集为例,聚类结果生成的图形就是文章的第一幅图:
library(mclust)
mc <- Mclust(iris[,1:4], 3)
plot(mc, data=iris[,1:4], what="classification",dimens=c(3,4))
table(iris$Species, mc$classification)

参考资料:
http://architects.dzone.com/articles/machine-learning-algorithms
http://www.autonlab.org/tutorials/gmm14.pdf
http://www.cs.ubbcluj.ro/~csatol/gep_tan/Bishop-CUED-2006.pdf
http://blog.sciencenet.cn/blog-637323-572768.html
http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/mixture.html
http://wenku.baidu.com/view/f780fb0590c69ec3d5bb7538.html
http://www.matrixq.net/2011/09/10218.html

from 数据科学与R语言: http://xccds1977.blogspot.com/2012/08/emr.html

Written by cwyalpha

八月 30, 2012 at 9:27 上午

发表在 Uncategorized

Thought this was cool: 聚类结果除了目测,如何度量靠谱?

leave a comment »

有人问我关于聚类结果度量的问题,我经验也不足,大体想了下:

1、最靠谱的目测?

2、运气好如果样本有标记,那么用分类的一些度量方法就好;

3、簇内距离的均值、方差;簇间距离的均值、方差;

4、熵?

===

网上一篇小文章,介绍了一下:Liupq的博客

数据聚类的目标是用某种相似性度量的方法将数据组织成有意义的和有用的各组数据.

由于基因表达谱数据的特殊性,要求新的方法除了具有能够发现数据间的真正关系,分类精度高,方法简单,速度快,鲁棒性强(在分类算法受到随机干扰及其它不确定因素影响时能够保持较高的分类精度) 这些特点外,还要求分析结果可视化程度好,可解释性强,具有很好的统计学和生物学意义.

几点疑问:(1)鲁棒性具体是如何衡量的?(2)什么叫可解释性好.

A算法聚出了五个类,B算法聚出了四个类,哪一个算法好呢?有一个一致的标准吗?还是依赖于生物学家的经验?聚类算法中一般都有有些输入参数,如在Figueroa的方法中有一个EPSILON,Xiaowen Liu的”Computing the maximum similarity bi-cluster of gene expression data”中有alpha,gamma等,输入某个大小参数的依据是什么?如果参数不同的话,结果是不同的.

看了Xiaowen Liu的文章后初步感觉,算法并不是多么的高深,更多的工作量是在对程序的测试与其它方法结果的比较上.一个是速度的,一个聚类结果上的(什么样的结果算是准确的呢,标准是什么?).

下文中提到了为什么聚类分析不能被人接受和利用,有三点:

[A03] Gelbard R, Goldman O, Spiegler I. Investigating diversity of lustering methods: An empirical comparison. Data & Knowledge Engineering, 2007,63(1):155-166.

(1) Firstly, there is a standardization problem. Different clustering algorithms produce different clusters and there is no clear-cut and standard method to compare them.
(2) Secondly, the interpretation for the various clusters formed, and their implementation in the original environment is not defined. Managers and business users hardly know the value of what they can attain by performing clustering using whatever technique. Indeed, the clustering process is unpredictable and sometimes even inconsistent.  Different programs generally divide the same dataset differently. This diversity makes the clustering process difficult.
(3) Furthermore, there is no clear way to measure and evaluate the quality of a clustering algorithm.

聚类结果相似性的度量

文[A01]中讲到了类相似性度量的方法,分两类来讲的,一是分类已知的前提下的度量(测试前我们知道,但是测试程序是不知道的,主要是用来作测试的程序吧,如对模拟数据的测试就是这样。),二是分类未知的前提下的相似性度量。

在分类已知前提下,假定TC分别是已知聚类矩阵和求解出的聚类矩阵,其结构是每个元素为0或是1,若Cij=1,则i,j在聚中属于同一个类,否则不属于一个类.相似性可以Minkowski measure进行度量:

image

这里,nk,l对(i,j)的数量,且Tij=k, Cij=l.公式的值越小,聚类结果越好.还可以用如下Jaccard系数进行度量,系数越大聚类结果越好.

image

当分类结果未知时.以对聚类结果的相以性度量分为同质性(homogeneity),分离性(separation).最后得到的有实际意义的分类具有这样两个特点,一是组内的样本具有内聚的结构;二是组与组之间被很好的分开.对于指纹数据(fingerprin date),同质性是通过同类中一个无素的指纹与类中其余元素之间的平均相似度来评价(evalued)的(原文:For fingerprint data, homogeneity is evalued by the average similarity of an element and that of its cluster).确切的讲,如时cl(u)是u所在的类,F(X),F(U)分别是类X和无素u的指纹.那么:

image

分离性是通过聚类指纹间的权重平均相似度来评价的(Separation is evalued by the weighted average similarity between cluster fingerprints).如果聚类结果是X1,X2… …Xt,

则:image

image

您可能也喜欢:


Spectral Clustering[谱聚类]


A Tutorial on Clustering Algorithms-朴素聚类小知识


k-means聚类算法[C语言]


Bag-Of-Words中K-Means聚类的效率优化


Mallet:自然语言处理工具包

无觅

相关文章

from 丕子: http://www.zhizhihu.com/html/y2012/3900.html

Written by cwyalpha

八月 30, 2012 at 1:22 上午

发表在 Uncategorized

Thought this was cool: 使用Weka进行数据挖掘

leave a comment »

1.简介

数据挖掘、机器学习这些字眼,在一些人看来,是门槛很高的东西。诚然,如果做算法实现甚至算法优化,确实需要很多背景知识。但事实是,绝大多数数据挖掘工程师,不需要去做算法层面的东西。他们的精力,集中在特征提取,算法选择和参数调优上。那么,一个可以方便地提供这些功能的工具,便是十分必要的了。而weka,便是数据挖掘工具中的佼佼者。

Weka的全名是怀卡托智能分析环境(Waikato Environment for Knowledge
Analysis),是一款免费的,非商业化的,基于JAVA环境下开源的机器学习以及数据挖掘软件。它和它的源代码可在其官方网站下载。有趣的是,该软件的缩写WEKA也是New
Zealand独有的一种鸟名,而Weka的主要开发者同时恰好来自新西兰的the University of
Waikato。(本段摘自百度百科)。

Weka提供的功能有数据处理,特征选择、分类、回归、聚类、关联规则、可视化等。本文将对Weka的使用做一个简单的介绍,并通过简单的示例,使大家了解使用weka的流程。本文将仅对图形界面的操作做介绍,不涉及命令行和代码层面的东西。

2.安装

Weka的官方地址是http://www.cs.waikato.ac.nz/ml/weka/。点开左侧download栏,可以进入下载页面,里面有windows,mac
os,linux等平台下的版本,我们以windows系统作为示例。目前稳定的版本是3.6。

如果本机没有安装java,可以选择带有jre的版本。下载后是一个exe的可执行文件,双击进行安装即可。

安装完毕,打开启动weka的快捷方式,如果可以看到下面的界面,那么恭喜,安装成功了。

image图2.1 weka启动界面

窗口右侧共有4个应用,分别是

1)Explorer

用来进行数据实验、挖掘的环境,它提供了分类,聚类,关联规则,特征选择,数据可视化的功能。(An environment for
exploring data with WEKA)

2)Experimentor

用来进行实验,对不同学习方案进行数据测试的环境。(An environment for performing
experiments and conducting statistical tests between learning
schemes.)

3)KnowledgeFlow

功能和Explorer差不多,不过提供的接口不同,用户可以使用拖拽的方式去建立实验方案。另外,它支持增量学习。(This
environment supports essentially the same functions as the Explorer
but with a drag-and-drop interface. One advantage is that it
supports incremental learning.)

4)SimpleCLI

简单的命令行界面。(Provides a simple command-line interface that allows
direct execution of WEKA commands for operating systems that do not
provide their own command line interface.)

3.数据格式

Weka支持很多种文件格式,包括arff、xrff、csv,甚至有libsvm的格式。其中,arff是最常用的格式,我们在这里仅介绍这一种。

Arff全称是Attribute-Relation File Format,以下是一个arff格式的文件的例子。

%

%  Arff file example

%

@relation ‘labor-neg-data’

@attribute ‘duration’ real

@attribute ‘wage-increase-first-year’ real

@attribute ‘wage-increase-second-year’ real

@attribute ‘wage-increase-third-year’ real

@attribute ‘cost-of-living-adjustment’ {‘none’,’tcf’,’tc’}

@attribute ‘working-hours’ real

@attribute ‘pension’ {‘none’,’ret_allw’,’empl_contr’}

@attribute ’standby-pay’ real

@attribute ’shift-differential’ real

@attribute ‘education-allowance’ {‘yes’,’no’}

@attribute ’statutory-holidays’ real

@attribute ‘vacation’ {‘below_average’,’average’,’generous’}

@attribute ‘longterm-disability-assistance’ {‘yes’,’no’}

@attribute ‘contribution-to-dental-plan’
{‘none’,’half’,’full’}

@attribute ‘bereavement-assistance’ {‘yes’,’no’}

@attribute ‘contribution-to-health-plan’
{‘none’,’half’,’full’}

@attribute ‘class’ {‘bad’,’good’}

@data

1,5,?,?,?,40,?,?,2,?,11,’average’,?,?,’yes’,?,’good’

2,4.5,5.8,?,?,35,’ret_allw’,?,?,’yes’,11,’below_average’,?,’full’,?,’full’,’good’

?,?,?,?,?,38,’empl_contr’,?,5,?,11,’generous’,’yes’,’half’,’yes’,’half’,’good’

3,3.7,4,5,’tc’,?,?,?,?,’yes’,?,?,?,?,’yes’,?,’good’

3,4.5,4.5,5,?,40,?,?,?,?,12,’average’,?,’half’,’yes’,’half’,’good’

2,2,2.5,?,?,35,?,?,6,’yes’,12,’average’,?,?,?,?,’good’

3,4,5,5,’tc’,?,’empl_contr’,?,?,?,12,’generous’,’yes’,’none’,’yes’,’half’,’good’

3,6.9,4.8,2.3,?,40,?,?,3,?,12,’below_average’,?,?,?,?,’good’

2,3,7,?,?,38,?,12,25,’yes’,11,’below_average’,’yes’,’half’,’yes’,?,’good’

1,5.7,?,?,’none’,40,’empl_contr’,?,4,?,11,’generous’,’yes’,’full’,?,?,’good’

3,3.5,4,4.6,’none’,36,?,?,3,?,13,’generous’,?,?,’yes’,’full’,’good’

2,6.4,6.4,?,?,38,?,?,4,?,15,?,?,’full’,?,?,’good’

2,3.5,4,?,’none’,40,?,?,2,’no’,10,’below_average’,’no’,’half’,?,’half’,’bad’

这个例子来自于weka安装目录data文件下的labor.arff文件,来源于加拿大劳资谈判的案例,它根据工人的个人信息,来预测劳资谈判的最终结果。

文件中,“%”开头的是注释。剩余的可以分为两大部分,头信息(header information)和数据信息(data
information)。

头信息中,“@relation”开头的行代表关系名称,在整个文件的第一行(除去注释)。格式是

@relation <relation-name>

“@attribute”开头的代表特征,格式是

@attribute <attribute-name>
<datatype>

attribute-name是特征的名称,后面是数据类型,常用数据类型有以下几种

1)numeric,数字类型,包括integer(整数)和real(实数)

2)nominal,可以认为是枚举类型,即特征值是有限的集合,可以是字符串或数字。

3)string,字符串类型,值可以是任意的字符串。

从“@data”开始,是实际的数据部分。每一行代表一个实例,可以认为是一个特征向量。各个特征的顺序与头信息中的attribute逐个对应,特征值之间用逗号分割。在有监督分类中,最后一列是标注的结果。

某些特征的数值如果是缺失的,可以用“?”代替。

数据挖掘流程

使用weka进行数据挖掘的流程如下图


image
图4.1 数据挖掘流程图

其中,在weka内进行的是数据预处理,训练,验证这三个步骤。

1)数据预处理

数据预处理包括特征选择,特征值处理(比如归一化),样本选择等操作。

2)训练

训练包括算法选择,参数调整,模型训练。

3)验证

对模型结果进行验证。

本文剩余部分将以这个流程为主线,以分类为示例,介绍使用weka进行数据挖掘的步骤。

5. 数据预处理

打开Explorer界面,点“open
file”,在weka安装目录下,选择data目录里的“labor.arff”文件,将会看到如下界面。我们将整个区域分为7部分,下面将分别介绍每部分的功能。


image
图5.1 Explorer界面

1)区域1共6个选项卡,用来选择不同的数据挖掘功能面板,从左到右依次是Preprocess(预处理)、Classify(分类)、
Cluster(聚类)、Associate(关联规则)、Select
attribute(特征选择)和Visualize(可视化)。

2)区域2提供了打开、保存,编辑文件的功能。打开文件不仅仅可以直接从本地选择,还可以使用url和db来做数据源。Generate按钮提供了数据生成的功能,weka提供了几种生成数据的方法。点开Edit,将看到如下界面


image
图5.2 arff viewer

在这个界面,可以看到各行各列对应的值,右键每一列的名字,可以看到一些编辑数据的功能,这些功能还是比较实用的。

3)区域3名为Filter,有些人可能会联想到特征选择里面的Filter方法,事实上,Filter针对特征(attribute)和样本(instance)提供了大量的操作方法,功能十分强大。

4)在区域4,可以看到当前的特征、样本信息,并提供了特征选择和删除的功能。

5)在区域4用鼠标选择单个特征后,区域5将显示该特征的信息。包括最小值、最大值、期望和标准差。

6)区域6提供了可视化功能,选择特征后,该区域将显示特征值在各个区间的分布情况,不同的类别标签以不同的颜色显示。

7)区域7是状态栏,没有任务时,小鸟是坐着的,任务运行时,小鸟会站起来左右摇摆。如果小鸟站着但不转动,表示任务出了问题。

下面将通过实例介绍Filters的各项功能。

点开Filter下面的choose按钮,可以看到如下界面


image
图5.3 filter方法选择界面

Filters可分为两大类,supervised和unsupervised。supervised下的方法需要类别标签,而unsupervised则不需要。attribute类别表示对特征做筛选,instance表示对样本做选择。

1)case 1:特征值归一化

该项功能与类别无关,且是针对attribute的,我们选择unsupervised ->
attribute下面的Normalize。点开Normalize所在的区域,将看到如下界面。左边的窗口,有几个参数可以选择。点击more,将出现右边的窗口,该窗口详细介绍了此功能。


image
图5.4 归一化参数设置界面

使用默认参数,点击ok,回到主窗口。在区域4选好将要归一化的特征,可以是一个或多个,然后点击apply。在可视化区域中,我们可以看到特征值从1到3被归一到了0到1之间。


image
2)case 2:
分类器特征筛选

该功能与类别相关,选择supervised ->
attribute下面的AttributeSelection。该界面有两个选项,evaluator是评价特征集合有效性的方法,search是特征集合搜索的方法。在这里,我们使用InformationGainAttributeEval作为evaluator,使用Ranker作为
search,表示我们将根据特征的信息增益值对特征做排序。Ranker中可以设置阈值,低于这个阈值的特征将被扔掉。


image
图5.7 特征选择参数

点击apply,可以看到在区域4里特征被重新排序,低于阈值的已被删掉。


image
3)case
3:选择分类器错分的样本

选择unsupervised ->
instance下面的RemoveMisclassified,可以看到6个参数,classIndex用来设置类别标签,classifier用来选择分类器,这里我们选择J48决策树,invert我们选择true,这样保留的是错分样本,numFolds用来设置交叉验证的参数。设置好参数之后,点击apply,可以看到样本的数量从57减少到了7。


image
图5.10 参数设置

6. 分类

在Explorer中,打开classifer选项卡,整个界面被分成几个区域。分别是

1)Classifier

点击choose按钮,可以选择weka提供的分类器。常用的分类器有

a)bayes下的Naïve Bayes(朴素贝叶斯)和BayesNet(贝叶斯信念网络)。

b)functions下的LibLinear、LibSVM(这两个需要安装扩展包)、Logistic
Regression、Linear Regression。

c)lazy下的IB1(1-NN)和IBK(KNN)。

d)meta下的很多boosting和bagging分类器,比如AdaBoostM1。

e)trees下的J48(weka版的C4.5)、RandomForest。

2)Test options

评价模型效果的方法,有四个选项。

a)Use training set:使用训练集,即训练集和测试集使用同一份数据,一般不使用这种方法。

b)Supplied test set:设置测试集,可以使用本地文件或者url,测试文件的格式需要跟训练文件格式一致。

c)Cross-validation:交叉验证,很常见的验证方法。N-folds
cross-validation是指,将训练集分为N份,使用N-1份做训练,使用1份做测试,如此循环N次,最后整体计算结果。

d)Percentage split:按照一定比例,将训练集分为两份,一份做训练,一份做测试。

在这些验证方法的下面,有一个More options选项,可以设置一些模型输出,模型验证的参数。

3)Result list

这个区域保存分类实验的历史,右键点击记录,可以看到很多选项。常用的有保存或加载模型以及可视化的一些选项。

4)Classifier output

分类器的输出结果,默认的输出选项有Run
information,该项给出了特征、样本及模型验证的一些概要信息;Classifier
model,给出的是模型的一些参数,不同的分类器给出的信息不同。最下面是模型验证的结果,给出了  
一些常用的一些验证标准的结果,比如准确率(Precision),召回率(Recall),真阳性率(True positive
rate),假阳性率(False positive rate),F值(F-Measure),Roc面积(Roc
Area)等。Confusion
Matrix给出了测试样本的分类情况,通过它,可以很方便地看出正确分类或错误分类的某一类样本的数量。

Case 1:使用J48对labor文件做分类

1)打开labor.arff文件,切换到classify面板。

2)选择trees->J48分类器,使用默认参数。

3)Test options选择默认的十折交叉验证,点开More options,勾选Output
predictions。

4)点击start按钮,启动实验。

5)在右侧的Classifier output里面,我们看到了实验的结果。


image
图6.1 Run information

上图给出了实验用的分类器以及具体参数,实验名称,样本数量,特征数量以及所用特征,测试模式。


image
图6.2 模型信息

上图给出了生成的决策树,以及叶子节点数、树的节点数、模型训练时间。如果觉得这样不直观,可以在Result
list里面右键点击刚刚进行的实验,点击Visualize Tree,可以看到图形界面的决策树,十分直观。


image
图6.3 决策树

再往下是预测结果,可以看到每个样本的实际分类,预测分类,是否错分,预测概率这些信息。


image
图6.4 预测结果

最下面是验证结果,整体的accuracy是73.68%,bad类准确率是60.9%,召回率70.0%,good类准确率是82.4%,召回率75.7%。


image
图6.5 模型效果评估结果

7. 可视化

打开Explorer的Visualize面板,可以看到最上面是一个二维的图形矩阵,该矩阵的行和列均为所有的特征(包括类别标签),第i行第j列表示特征i和特征j在二维平面上的分布情况。图形上的每个点表示一个样本,不同的类别使用不同的颜色标识。

下面有几个选项,PlotSize可以调整图形的大小,PointSize可以调整样本点的大小,Jitter可以调整点之间的距离,有些时候点过于集中,可以通过调整Jitter将它们分散开。


image
图7.1 plot matrix二维图

上图是duration和class两个特征的图形,可以看出,duration并不是一个好特征,在各个特征值区间,good和bad的分布差不多。

单击某个区域的图形,会弹出另外一个窗口,这个窗口给出的也是某两个特征之间分布的图形,不同的是,在这里,通过点击样本点,可以弹出样本的详细信息。

可视化还可以用来查看误分的样本,这是非常实用的一个功能。分类结束后,在Result
list里右键点击分类的记录,选择Visualize classify errors,会弹出如下窗口。


image
图7.2 误分样本可视化

这个窗口里面,十字表示分类正确的样本,方块表示分类错误的样本,X轴为实际类别,Y轴为预测类别,蓝色为实际的bad,红色为实际的good。这样,蓝色方块就表示实际为bad,但为误分为good的样本,红色方块表示实际为good,被误分为bad的样本。单击这些点,便可以看到该样本的各个特征值,分析为什么这个样本被误分了。

再介绍一个比较实用的功能,右键点击Result list里的记录,选择Visualize threshold
curve,然后选好类别,可以看到如下图形


image
图7.3 阈值曲线

该图给出的是分类置信度在不同阈值下,分类效果评价标准的对比情况。上图给出的是假阳性比率和真阳性比率在不同阈值下的对比,其实给出的就是ROC
曲线。我们可以通过选择颜色,方便地观察不同评价标准的分布情况。如果X轴和Y轴选择的是准确率和召回率,那我们可以通过这个图,在这两个值之间做
trade-off,选择一个合适的阈值。

其它的一些可视化功能,不再一一介绍。

8. 小结

本文仅仅针对weka的Explorer界面的某些功能做了介绍,Explorer其它的功能,比如聚类、关联规则、特征选择,以及Experimentor和KnowledgeFlow界面使用,可以参考weka的官方文档。

另外,weka支持扩展包,可以很方便地把liblinear、libsvm这样的开源工具放进来。

在Linux下面,可以使用weka的命令行进行实验,具体的使用方法,也请参考weka官方文档。

有这样一款开源、免费、强大的数据挖掘工具,你还在等什么呢?没有用过weka的数据挖掘工程师们,赶紧行动吧。

 

本文转载自:http://stblog.baidu-tech.com/?p=1918

 青春就应该这样绽放  游戏测试:三国时期谁是你最好的兄弟!!  你不得不信的星座秘密
from 互联网旁观者: http://blog.sina.com.cn/s/blog_72995dcc01016mxn.html

Written by cwyalpha

八月 30, 2012 at 1:22 上午

发表在 Uncategorized

Thought this was cool: python判断unicode是否是汉字,数字,英文,或者其他字符

leave a comment »

ps:中文处理经验不足,学习了。
下面这个小工具包含了 判断unicode是否是汉字,数字,英文,或者其他字符。 全角符号转半角符号。 unicode字符串归一化等工作。 还有一个能处理多音字的汉字转拼音的程序,还在整理中。
转自:
http://hi.baidu.com/fenghua1893/item/d1a71d5ac47ffdcfd3e10cd1

#!/usr/bin/env python
#
 -*- coding:GBK -*- 
 
“””汉字处理的工具:
判断unicode是否是汉字,数字,英文,或者其他字符。
全角符号转半角符号。
“””
 
def is_chinese(uchar):
        “””判断一个unicode是否是汉字“””
        if uchar >= u\u4e00 and uchar<=u\u9fa5:
                return True
        else:
                return False
 
def is_number(uchar):
        “””判断一个unicode是否是数字“””
        if uchar >= u\u0030 and uchar<=u\u0039:
                return True
        else:
                return False
 
def is_alphabet(uchar):
        “””判断一个unicode是否是英文字母“””
        if (uchar >= u\u0041 and uchar<=u\u005aor (uchar >= u\u0061 and uchar<=u\u007a):
                return True
        else:
                return False
 
def is_other(uchar):
        “””判断是否非汉字,数字和英文字符“””
        if not (is_chinese(uchar) or is_number(uchar) or is_alphabet(uchar)):
                return True
        else:
                return False
 
def B2Q(uchar):
        “””半角转全角“””
        inside_code=ord(uchar)
        if inside_code<0x0020 or inside_code>0x7e:      #不是半角字符就返回原来的字符
                return uchar
        if inside_code==0x0020: #除了空格其他的全角半角的公式为:半角=全角-0xfee0
                inside_code=0x3000
        else:
                inside_code+=0xfee0
        return unichr(inside_code)
 
def Q2B(uchar):
        “””全角转半角“””
        inside_code=ord(uchar)
        if inside_code==0x3000:
                inside_code=0x0020
        else:
                inside_code-=0xfee0
        if inside_code<0x0020 or inside_code>0x7e:      #转完之后不是半角字符返回原来的字符
                return uchar
        return unichr(inside_code)

 
def stringQ2B(ustring):
        “””把字符串全角转半角“””
        return “”.join([Q2B(uchar) for uchar in ustring])
 
def uniform(ustring):
        “””格式化字符串,完成全角转半角,大写转小写的工作“””
        return stringQ2B(ustring).lower()
 
def string2List(ustring):
        “””将ustring按照中文,字母,数字分开“””
        retList=[]
        utmp=[]
        for uchar in ustring:
                if is_other(uchar):
                        if len(utmp)==0:
                                continue
                        else:
                                retList.append(“”.join(utmp))
                                utmp=[]
                else:
                        utmp.append(uchar)
        if len(utmp)!=0:
                retList.append(“”.join(utmp))
        return retList
 
if __name__==__main__:
        #test Q2B and B2Q
        for i in range(0x0020,0x007F):
                print Q2B(B2Q(unichr(i))),B2Q(unichr(i))
 
        #test uniform
        ustring=u中国 人名a高频A
        ustring=uniform(ustring)
        ret=string2List(ustring)

        print ret

SunRise_at 2012-08-29 17:47 发表评论


from C++博客-首页原创精华区: http://www.cppblog.com/sunrise/archive/2012/08/29/188654.html

Written by cwyalpha

八月 29, 2012 at 1:07 下午

发表在 Uncategorized

Thought this was cool: PythonBooks – Learn Python the easy way !

leave a comment »

Comments: “PythonBooks – Learn Python the easy way !”

URL: http://pythonbooks.revolunet.com

The easiest and cheapest way to learn Python !

Python is a powerful programming language that lets you code efficiently and integrate various systems more effectively. Find here the best free publications to learn Python and muscle your brain !

Fork it on GitHub and add you issue !

PythonBooks will be updated with fresh and updated content out there. Drop your mail below to be notified on each update :


from Hacker News 200: http://pythonbooks.revolunet.com?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+hacker-news-feed-200+%28Hacker+News+200%29

Written by cwyalpha

八月 28, 2012 at 6:23 上午

发表在 Uncategorized