singlepass聚类算法

A. 数码印花singlepass和onepass的区别

其实有三个翻译类似但概念完全不同的名称：Single pass、onepass与 1 pass，从打印方式简单讲：
single pass：专用于数码印花行业，一般4组喷头分离并排为4列，每组多个喷头串联在一起出一个单色，4组组合分别出C、M、Y、K，打印时喷头位置不变，送布平台不断送布；
onepass：用于UV打标签较多，多组工业喷头串排组合为一列，打印时喷头不动，送纸器移动
1 pass：任何喷头任何种类机型都可达要求，只需精度设置为最低精度即可。

B. 怎么解决使用NTSYS做聚类图出现时会出现too many(26) multifurcations in a single pass的问题

应该是你格式的问题，我做的时候也遇到了，后来就可以了。你弄个联系方式给我，我给你个格式。

C. single-pass算法的有哪些不足之处

对称加密算法是应用较早的加密算法，技术成熟。在对称加密算法中，数据发信方将明文（原始数据）和加密密钥一起经过特殊加密算法处理后，使其变成复杂的加密密文发送出去。收信方收到密文后，若想解读原文，则需要使用加密用过的密钥及相同算法

D. kmeans算法用python怎么实现

1、从Kmeans说起

Kmeans是一个非常基础的聚类算法，使用了迭代的思想，关于其原理这里不说了。下面说一下如何在matlab中使用kmeans算法。

创建7个二维的数据点：

复制代码 代码如下:
x=[randn(3,2)*.4;randn(4,2)*.5+ones(4,1)*[4 4]];

使用kmeans函数：

复制代码 代码如下:
class = kmeans(x, 2);

x是数据点，x的每一行代表一个数据；2指定要有2个中心点，也就是聚类结果要有2个簇。 class将是一个具有70个元素的列向量，这些元素依次对应70个数据点，元素值代表着其对应的数据点所处的分类号。某次运行后，class的值是：

复制代码 代码如下:

2
2
2
1
1
1
1

这说明x的前三个数据点属于簇2，而后四个数据点属于簇1。 kmeans函数也可以像下面这样使用：

复制代码 代码如下:

>> [class, C, sumd, D] = kmeans(x, 2)
class =
2
2
2
1
1
1
1

C =
4.0629 4.0845
-0.1341 0.1201

sumd =
1.2017
0.2939

D =
34.3727 0.0184
29.5644 0.1858
36.3511 0.0898
0.1247 37.4801
0.7537 24.0659
0.1979 36.7666
0.1256 36.2149

class依旧代表着每个数据点的分类;C包含最终的中心点，一行代表一个中心点；sumd代表着每个中心点与所属簇内各个数据点的距离之和；D的
每一行也对应一个数据点，行中的数值依次是该数据点与各个中心点之间的距离，Kmeans默认使用的距离是欧几里得距离（参考资料[3]）的平方值。
kmeans函数使用的距离，也可以是曼哈顿距离（L1-距离），以及其他类型的距离，可以通过添加参数指定。

kmeans有几个缺点（这在很多资料上都有说明）：

1、最终簇的类别数目（即中心点或者说种子点的数目）k并不一定能事先知道，所以如何选一个合适的k的值是一个问题。
2、最开始的种子点的选择的好坏会影响到聚类结果。
3、对噪声和离群点敏感。
4、等等。

2、kmeans++算法的基本思路

kmeans++算法的主要工作体现在种子点的选择上，基本原则是使得各个种子点之间的距离尽可能的大，但是又得排除噪声的影响。 以下为基本思路：

1、从输入的数据点集合（要求有k个聚类）中随机选择一个点作为第一个聚类中心
2、对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
3、选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
4、重复2和3直到k个聚类中心被选出来
5、利用这k个初始的聚类中心来运行标准的k-means算法

假定数据点集合X有n个数据点，依次用X(1)、X(2)、……、X(n)表示，那么，在第2步中依次计算每个数据点与最近的种子点（聚类中心）的
距离，依次得到D(1)、D(2)、……、D(n)构成的集合D。在D中，为了避免噪声，不能直接选取值最大的元素，应该选择值较大的元素，然后将其对应
的数据点作为种子点。

如何选择值较大的元素呢，下面是一种思路（暂未找到最初的来源，在资料[2]等地方均有提及，笔者换了一种让自己更好理解的说法）：
把集合D中的每个元素D(x)想象为一根线L(x)，线的长度就是元素的值。将这些线依次按照L(1)、L(2)、……、L(n)的顺序连接起来，组成长
线L。L(1)、L(2)、……、L(n)称为L的子线。根据概率的相关知识，如果我们在L上随机选择一个点，那么这个点所在的子线很有可能是比较长的子
线，而这个子线对应的数据点就可以作为种子点。下文中kmeans++的两种实现均是这个原理。

3、python版本的kmeans++

在http://rosettacode.org/wiki/K-means%2B%2B_clustering 中能找到多种编程语言版本的Kmeans++实现。下面的内容是基于python的实现（中文注释是笔者添加的）：

复制代码 代码如下:

from math import pi, sin, cos
from collections import namedtuple
from random import random, choice
from import
try:
import psyco
psyco.full()
except ImportError:
pass

FLOAT_MAX = 1e100

class Point:
__slots__ = ["x", "y", "group"]
def __init__(self, x=0.0, y=0.0, group=0):
self.x, self.y, self.group = x, y, group

def generate_points(npoints, radius):
points = [Point() for _ in xrange(npoints)]

# note: this is not a uniform 2-d distribution
for p in points:
r = random() * radius
ang = random() * 2 * pi
p.x = r * cos(ang)
p.y = r * sin(ang)

return points

def nearest_cluster_center(point, cluster_centers):
"""Distance and index of the closest cluster center"""
def sqr_distance_2D(a, b):
return (a.x - b.x) ** 2 + (a.y - b.y) ** 2

min_index = point.group
min_dist = FLOAT_MAX

for i, cc in enumerate(cluster_centers):
d = sqr_distance_2D(cc, point)
if min_dist > d:
min_dist = d
min_index = i

return (min_index, min_dist)

'''
points是数据点，nclusters是给定的簇类数目
cluster_centers包含初始化的nclusters个中心点，开始都是对象->(0,0,0)
'''

def kpp(points, cluster_centers):
cluster_centers[0] = (choice(points)) #随机选取第一个中心点
d = [0.0 for _ in xrange(len(points))] #列表，长度为len(points)，保存每个点离最近的中心点的距离

for i in xrange(1, len(cluster_centers)): # i=1...len(c_c)-1
sum = 0
for j, p in enumerate(points):
d[j] = nearest_cluster_center(p, cluster_centers[:i])[1] #第j个数据点p与各个中心点距离的最小值
sum += d[j]

sum *= random()

for j, di in enumerate(d):
sum -= di
if sum > 0:
continue
cluster_centers[i] = (points[j])
break

for p in points:
p.group = nearest_cluster_center(p, cluster_centers)[0]

'''
points是数据点，nclusters是给定的簇类数目
'''
def lloyd(points, nclusters):
cluster_centers = [Point() for _ in xrange(nclusters)] #根据指定的中心点个数，初始化中心点，均为(0,0,0)

# call k++ init
kpp(points, cluster_centers) #选择初始种子点

# 下面是kmeans
lenpts10 = len(points) >> 10

changed = 0
while True:
# group element for centroids are used as counters
for cc in cluster_centers:
cc.x = 0
cc.y = 0
cc.group = 0

for p in points:
cluster_centers[p.group].group += 1 #与该种子点在同一簇的数据点的个数
cluster_centers[p.group].x += p.x
cluster_centers[p.group].y += p.y

for cc in cluster_centers: #生成新的中心点
cc.x /= cc.group
cc.y /= cc.group

# find closest centroid of each PointPtr
changed = 0 #记录所属簇发生变化的数据点的个数
for p in points:
min_i = nearest_cluster_center(p, cluster_centers)[0]
if min_i != p.group:
changed += 1
p.group = min_i

# stop when 99.9% of points are good
if changed <= lenpts10:
break

for i, cc in enumerate(cluster_centers):
cc.group = i

return cluster_centers

def print_eps(points, cluster_centers, W=400, H=400):
Color = namedtuple("Color", "r g b");

colors = []
for i in xrange(len(cluster_centers)):
colors.append(Color((3 * (i + 1) % 11) / 11.0,
(7 * i % 11) / 11.0,
(9 * i % 11) / 11.0))

max_x = max_y = -FLOAT_MAX
min_x = min_y = FLOAT_MAX

for p in points:
if max_x < p.x: max_x = p.x
if min_x > p.x: min_x = p.x
if max_y < p.y: max_y = p.y
if min_y > p.y: min_y = p.y

scale = min(W / (max_x - min_x),
H / (max_y - min_y))
cx = (max_x + min_x) / 2
cy = (max_y + min_y) / 2

print "%%!PS-Adobe-3.0\n%%%%BoundingBox: -5 -5 %d %d" % (W + 10, H + 10)

print ("/l {rlineto} def /m {rmoveto} def\n" +
"/c { .25 sub exch .25 sub exch .5 0 360 arc fill } def\n" +
"/s { moveto -2 0 m 2 2 l 2 -2 l -2 -2 l closepath " +
" gsave 1 setgray fill grestore gsave 3 setlinewidth" +
" 1 setgray stroke grestore 0 setgray stroke }def")

for i, cc in enumerate(cluster_centers):
print ("%g %g %g setrgbcolor" %
(colors[i].r, colors[i].g, colors[i].b))

for p in points:
if p.group != i:
continue
print ("%.3f %.3f c" % ((p.x - cx) * scale + W / 2,
(p.y - cy) * scale + H / 2))

print ("\n0 setgray %g %g s" % ((cc.x - cx) * scale + W / 2,
(cc.y - cy) * scale + H / 2))

print "\n%%%%EOF"

def main():
npoints = 30000
k = 7 # # clusters

points = generate_points(npoints, 10)
cluster_centers = lloyd(points, k)
print_eps(points, cluster_centers)

main()

上述代码实现的算法是针对二维数据的，所以Point对象有三个属性，分别是在x轴上的值、在y轴上的值、以及所属的簇的标识。函数lloyd是
kmeans++算法的整体实现，其先是通过kpp函数选取合适的种子点，然后对数据集实行kmeans算法进行聚类。kpp函数的实现完全符合上述
kmeans++的基本思路的2、3、4步。

E. KMEANS算法。哪位高手指点一下啊。知道kmeans算法但看不懂下面代码。请尽量多注释一下啊。谢谢啦！在线等

程序需要一个数据文件
格式如下：
5 2 3
2 3 4 5 10 12 5 1 12 10
其中，5表示数据的数量，2表示数据的维度，3表示聚类的数量。
后面每两个实数对应一个数据点。
不过这个程序始数据维数固定为2，后来想改成4以下的任意维度，但没有改完，所以其实只能为2维。
我已经对程序做了注释。

#include < stdio.h>
#include < stdlib.h>
#include < string.h>
#include < conio.h>
#include < math.h>

#define SUCCESS 1
#define FAILURE 0
#define TRUE 1
#define FALSE 0
#define MAXVECTDIM 4 // 数据最大维数 (看来这个程序写了一半，维数实际上只能为2)
#define MAXPATTERN 1588 // 数据数量最大值
#define MAXCLUSTER 10 // 聚类最大值

// 聚类结构
struct aCluster {
double Center[MAXVECTDIM]; // 中心/引力数据对象
int Member[MAXPATTERN]; // 该聚类中数据在Pattern中的索引
int NumMembers; // 数据的数量
};

struct aVector {
double Center[MAXVECTDIM];
int Size;
};

static double Pattern[MAXPATTERN][MAXVECTDIM + 1]; // 所有数据存放在这个数组中

// 所以的东西都搁System类里面了
class System {
private :
aCluster Cluster[MAXCLUSTER]; // 聚类数组
int NumPatterns; // 输入数据的数量
int SizeVector; // 数据的维数
int NumClusters; // 数据的聚类数
void DistributeSamples(); // 根据中心聚类，重新分配数据到不同的聚类
int CalcNewClustCenters(); // 重新计算新的聚类中心
double EucNorm(int, int); // 误差准则
int FindClosestCluster(int); // 查找最接近的聚类
public :
System() {};
int LoadPatterns(char * fname); // 从文件中读取数据
void InitClusters(); // 初始化聚类
void RunKMeans(); // 执行K-Means算法
void ShowClusters(); // 显示聚类
void SaveClusters(char * fname); // 保存聚类到文件中
void ShowCenters(); // 显示聚类中心数据
};

void System::ShowCenters() {
int i;
printf("Cluster centers:\n");
for (i = 0; i < NumClusters; i++) {
Cluster[i].Member[0] = i;
printf("ClusterCenter[%d]=(%f,%f)\n", i, Cluster[i].Center[0],Cluster[i].Center[1]);
int b=0;
}
printf("\n");
}
int System::LoadPatterns(char * fname) {
FILE * InFilePtr;
int i, j;
double x;
if ( (InFilePtr = fopen(fname, "r")) == NULL)
return FAILURE;
// 读入数据的数量，维度和聚类数的数量
fscanf(InFilePtr, "%d", & NumPatterns);
fscanf(InFilePtr, "%d", & SizeVector);
fscanf(InFilePtr, "%d", & NumClusters);
// 读入数据
for (i = 0; i < NumPatterns; i++) {
for (j = 0; j < SizeVector; j++) {
fscanf(InFilePtr, "%lg", & x);
Pattern[i][j] = x;
}
}
// 打印读入的数据
printf("Input patterns:\n");
for (i = 0; i < NumPatterns; i++) {
printf("Pattern[%d]=(%2.3f,%2.3f,%d,%d)\n", i, Pattern[i][0], Pattern[i][1],Pattern[i][2], Pattern[i][3]);
}
printf("\n--------------------\n");
return SUCCESS;
}
void System::InitClusters() {
int i, j;
SizeVector=2; // 看来开始数据维数固定为2，后来想改成4以下的任意维度，但没有改完
printf("Initial cluster centers:\n");
// 把前NumClusters个数据作为NumClusters个聚类的数据中心
for (i = 0; i < NumClusters; i++) {
Cluster[i].Member[0] = i; // 记录这个数据的索引到第i个聚类中
for (j = 0; j < SizeVector; j++) {
Cluster[i].Center[j] = Pattern[i][j]; // 把这个数据作为数据中心
}
}
// 打印聚类的数据中心
for (i = 0; i < NumClusters; i++) {
printf("ClusterCenter[%d]=(%f,%f)\n", i, Cluster[i].Center[0], Cluster[i].Center[1]);
}
printf("\n");
}
void System::RunKMeans() {
int converged; // 是否收敛
int pass; // 计算的趟数
pass = 1; // 第一趟
converged = FALSE; // 没有收敛
while (converged == FALSE) { // 没有收敛的情况下反复跑
printf("PASS=%d\n", pass++); // 打印趟数
DistributeSamples(); // 重新分配数据
converged = CalcNewClustCenters(); // 计算新的聚类中心，如果计算结果和上次相同，认为已经收敛
ShowCenters(); // 显示聚类中心
}
}
// 第p个数据到第c个聚类中心的误差准则(距离的平方)
double System::EucNorm(int p, int c) {
double dist, x; // x可能是调试用，没有实际作用
int i;
dist = 0;
// 将每个维度的差的平方相加，得到距离的平方
for (i = 0; i < SizeVector; i++) {
x = (Cluster[c].Center[i] - Pattern[p][i]) *
(Cluster[c].Center[i] - Pattern[p][i]);
dist += (Cluster[c].Center[i] - Pattern[p][i]) *
(Cluster[c].Center[i] - Pattern[p][i]);
}
return dist;
}
// 查找第pat个数据的最近聚类
int System ::FindClosestCluster(int pat) {
int i, ClustID/*最近聚类的ID*/;
double MinDist/*最小误差*/, d;
MinDist = 9.9e+99; // 初始为一个极大的值
ClustID = -1;
// 依次计算3个聚类到第pat个数据的误差，找出最小值
for (i = 0; i < NumClusters; i++) {
d = EucNorm(pat, i);
printf("Distance from pattern %d to cluster %d is %f\n", pat, i, sqrt(d));
if (d < MinDist) { // 如果小于前最小值，将改值作为当前最小值
MinDist = d;
ClustID = i;
}
}
if (ClustID < 0) { // 没有找到？？！ —— 这个应该不可能发生，如果出现表示出现了不可思议的错误
printf("Aaargh");
exit(0);
}
return ClustID;
}

void System ::DistributeSamples() {
int i, pat, Clustid, MemberIndex;
// 将上次的记录的该聚类中的数据数量清0，重新开始分配数据
for (i = 0; i < NumClusters; i++) {
Cluster[i].NumMembers = 0;
}
// 找出每个数据的最近聚类数据中心，并将该数据分配到该聚类
for (pat = 0; pat < NumPatterns; pat++) {
Clustid = FindClosestCluster(pat);
printf("patern %d assigned to cluster %d\n\n", pat, Clustid);
MemberIndex = Cluster[Clustid].NumMembers; // MemberIndex是当前记录的数据数量，也是新加入数据在数组中的位置
Cluster[Clustid].Member[MemberIndex] = pat; // 将数据索引加入Member数组
Cluster[Clustid].NumMembers++; // 聚类中的数据数量加1
}
}

int System::CalcNewClustCenters() {
int ConvFlag, VectID, i, j, k;
double tmp[MAXVECTDIM]; // 临时记录新的聚类中心，因为需要比较，不能直接记录
char xs[255];
char szBuf[255];
ConvFlag = TRUE;
printf("The new cluster centers are now calculated as:\n");
// 逐个计算NumClusters个聚类
for (i = 0; i < NumClusters; i++) {
strcpy(xs,"");
printf("Cluster Center %d (1/%d):\n",i,Cluster[i].NumMembers);
// tmp所有维度数值清0
for (j = 0; j < SizeVector; j++) {
tmp[j] = 0.0;
}
// 计算聚类中所有数据的所有维度数值的和，为下一步计算均值做准备
for (j = 0; j < Cluster[i].NumMembers; j++) {
VectID = Cluster[i].Member[j];
for (k = 0; k < SizeVector; k++) {
tmp[k] += Pattern[VectID][k];
sprintf(szBuf,"%d ",Pattern[VectID][k]);
strcat(xs,szBuf);
}
printf("%s\n",xs); // 输出刚才计算的数据
strcpy(xs,"");
}
// 求出均值，并判断是否和上次相同
for (k = 0; k < SizeVector; k++) {
if(Cluster[i].NumMembers!=0)
tmp[k] = tmp[k] / Cluster[i].NumMembers;
if (tmp[k] != Cluster[i].Center[k]) // 如果不同，则认为没有收敛
ConvFlag = FALSE;
Cluster[i].Center[k] = tmp[k]; // 用新值代替旧值
}
printf("%s,\n", xs);
}
return ConvFlag; // 返回收敛情况
}
// 显示聚类中心数据
void System::ShowClusters() {
int cl;
for (cl = 0; cl < NumClusters; cl++) {
printf("\nCLUSTER %d ==>[%f,%f]\n", cl, Cluster[cl].Center[0],
Cluster[cl].Center[1]);
}
}
// 没有实现的函数
void System::SaveClusters(char * fname) {
}
#include <windows.h>
void main(int argc, char * argv[]) {
System kmeans;
// 如果没有提供参数，显示用法
if (argc < 2) {
printf("USAGE: KMEANS PATTERN_FILE\n");
exit(0);
}
// 参数1 为数据文件名，从中读入数据
if (kmeans.LoadPatterns(argv[1]) == FAILURE) {
printf("UNABLE TO READ PATTERN_FILE:%s\n", argv[1]);
exit(0);
}
kmeans.InitClusters();
kmeans.RunKMeans();
kmeans.ShowClusters();
kmeans.ShowCenters();
return ;
}

F. 数据流的模型描述

我们试图从数据集合、数据属性和计算类型三个不同方面对数据流的模型进行归纳和描述。实际上，很多文章提出了各种各样的数据流模型，我们并没有包括所有这些模型，只是将其中比较重要的和常见的进行了归纳和分类。 以下是对数据流的一个形式化描述。
考虑向量α，其属性的域为[1..n](秩为n)，而且向量α在时间t的状态
α(t)=<α1(t), ...αi(t), ...αn(t) >
在时刻s，α是0向量，即对于所有i，αi(s)=0。对向量的各个分量的更新是以二元组流的形式出现的。即，第t个更新为(i, ct)，意味着αi(t)= αi(t . 1) + ct，且对于i. =.i，αi. (t)= αi. (t . 1)。在时刻t发生的查询是针对α(t)的。 我们首先考虑在进行数据流计算时，有哪些数据被包含在计算范围之内。关于这个问题，主要有三种不同的模型：分别是数据流模型（data stream model）、滑动窗口模型（sliding window model）和n-of-N模型。
数据流模型（data stream model）在数据流模型中，从某个特定时间开始至今的所有数据都要被纳入计算范围。此时，s=0，即在时刻0，α是0向量。即这是数据流最初和最普遍的模型。
滑动窗口模型（sliding window model ，计算最近的N个数据）滑动窗口模型是指，从计算时算起，向前追溯的N个数据要被纳入计算范围。此时，s = t . N，即在时刻t . N，α是0向量。换句话说，要计算最近的N个数据。由于数据流的数据是不断涌现的，所以直观的看，这种模式就像用一个不变的窗口，数据随时间的推移经过窗口，出现在窗口内的数据就是被计算的数据集合。M. Datar等[91]首先提出这一模式，随后得到了广泛响应[92]。
n-of-N模型(计算最近的n个数据，其中0 <n ≤ N) 文献[93] 提出的这种模型建立在滑动窗口模型的基础之上，比滑动窗口模型更为灵活：被纳入计算范围的是从计算时算起，向前追溯的n个数据。此时，s = t . n，即在时刻t . n，α是0向量。注意，其中n ≤ N，而且是可以随查询要求变化的。而在滑动窗口模型中，n = N而且是固定不变的。对于数据流处理系统来说，要能够回答所有长度小于等于N的滑动窗口问题。 我们在来看一下数据本身的特征。
时间序列（time series model） 数据按照其属性(实际上就是时间)的顺序前来。在这种情况下，i = t，即一个t时刻的更新为(t, ct)。此时对α的更新操作为αt(t)= ct， 且对于i. =.t，αi. (t)= αi. (t . 1)。这种模型适用于时序数据，如某特定IP的传出的数据，或股票的定期更新数据等。
收款机模型（cash register model） 同一属性的数据相加，数据为正。在这种模型中，ct >=0。这意味着对于所有的i和t来说，αi(t)总是不小于零，而且是递增的。实际上，这种模型被认为是最常用的，例如可以用于对收款机（收款机模型由此得名），各个IP的网络传输量，手机用户的通话时长的监控等等。
十字转门模型（turnstile model） 同一属性的数据相加，数据为正或负。在这种模型中，ct可以大于0也可以小于0。这是最通用的模型。S. Muthukrishnan[89]称其为十字转门模型起因于这种模型的功能就象地铁站的十字转门，可以用来计算有多少人到达和离开，从而得出地铁中的人数。 对数据流数据的计算可以分为两类：基本计算和复杂计算。基本计算主要包括对点查询、范围查询和内积查询这三种查询的计算。复杂计算包括对分位数的计算、频繁项的计算以及数据挖掘等。
点查询（Point query） 返回αi(t)的值。
范围查询（Range query） 对于范围查询Q(f, t)，返回
t
. αi(t)
i=f
内积（Inner proct） 对于向量β，α与β的内积
α . β =Σni=1αi(t)βi
分位数（Quantile） 给定一个序号r，返回值v，并确保v在α中的真实排序r.符合以下要求：
r . εN ≤ r. ≤ r + εN
其中，ε是精度，N =Σni=1αi(t)。
G. S. Manku等[94]提供了对分位数进行一遍扫描进行近似估计的框架结构，将数据集合看成树的节点，这些节点拥有不同的权重（如节点中包含的数据个数）。认为所有的分位数的估计算法都可以被认为由三个对节点的操作组成产生新节点（NEW） 、合并（COLLAPSE）和输出（OUTPUT）。不同的策略构成了不同类型的树。这个框架结构成为后来很多分位数估计算法的基础。
频繁项（Frequent items）有时也称Heavy hitters，即找出在数据流中频繁出现的项。在这种计算中，实际上令ct =1。这样，αi(t)中保存了截至t时刻，维值等于i的数据到达的频率。对这些数据的查询又可分为两种：
找出头k个最频繁出现的项
找出所有出现频率大于1/k的项
对频率项的研究主要集中在后一种计算[95]。
挖掘对数据流数据进行挖掘涉及更复杂的计算。对这方面的研究包括：多维分析[96]，分类分析[97, 98]，聚类分析[99–102]，以及其他one-pass算法[103]。

G. 请教下 用理光GEN5的喷头，single pass 模式，600*300dpi ，线速度可以到多少

用理光GEN5的喷头，single pass 模式，600*300dpi ，线速度可以到12-14㎡/h。
相比较精工gs1024喷头，18-22㎡/h，慢了很多。

H. 云计算的海量数据挖掘工作是怎样实现的

云计算属于新兴技术领域，群英云计算转一篇关于问题的学术报告吧。对您应该有所帮助。

1引言

目前，人们正处于一个“无处不网、无时不网，人人上网、时时在线”的时代，图灵奖获得者吉姆·格雷（Jim Gray）认为，网络环境下每18个月产生的数据量等于过去几千年的数据量之和。目前互联网的数据具有海量增长、用户广泛、动态变化等特征。2010年，QQ同时在线的用户超过1亿人，淘宝一年交易次数比上年增长150%，视频服务Animoto在3天内通过Amazon将其服务能力迅速扩展至75万用户。

数据挖掘能够发现隐含在大规模数据中的知识，提高信息服务的质量。如伊朗事件中twitter快速传播假消息的识别、Amazon和淘宝网中商品关联关系分析，以及优酷网中视频个性化推荐等。海量数据挖掘在国家安全、国民经济和现代服务业中具有广泛应用，有助于提升网络环境下信息服务的质量，实现以人为本的信息服务。

从数据挖掘技术的发展历史看，随着互联网的蓬勃发展，数据的规模越来越大，从KB级发展到TB甚至PB级海量数据；数据挖掘的对象也变得越来越复杂，从数据库、到多媒体数据和复杂社会网络；数据挖掘的需求也从分类、聚类和关联到复杂的演化和预测分析；挖掘过程中的交互方式从单机的人机交互发展到现在社会网络群体的交互。这种发展给数据挖掘带来了巨大的挑战：对于网络环境下产生的TB级和PB级的复杂数据，需要有高效的海量数据挖掘算法；网络环境下大众的广泛参与，需要在数据挖掘算法中能够融入群体智慧；同时社会网络的迅速发展使得信息服务的个性化成为必然，要求能够满足即时组合的个性化挖掘服务。

云计算是一种基于互联网的、大众参与的计算模式，其计算资源（包括计算能力、存储能力、交互能力等）是动态、可伸缩、被虚拟化的，并以服务的方式提供 [1] 。具体表现在：云计算的动态和可伸缩的计算能力为高效海量数据挖掘带来可能性；云计算环境下大众参与的群体智能为研究集群体智慧的新的数据挖掘方法研究提供了环境；云计算的服务化特征使面向大众的数据挖掘成为可能。同时，云计算发展也离不开数据挖掘的支持，以搜索为例，基于云计算的搜索包括网页存储、搜索处理和前端交互三大部分。数据挖掘在这几部分中都有广泛应用，例如网页存储中网页去重、搜索处理中网页排序和前端交互中的查询建议，其中每部分都需要数据挖掘技术的支持。

因此，云计算为海量和复杂数据对象的数据挖掘提供了基础设施，为网络环境下面向大众的数据挖掘服务带来了机遇，同时也为数据挖掘研究提出了新的挑战性课题。

下面将对并行编程模型、基于并行编程模型高效海量数据挖掘算法，以及基于云计算的海量数据挖掘服务相关研究进行综述。

2并行编程模型相关方法

为了使用户能够通过简单的开发来方便地达到并行计算的效果，研究人员提出了一系列的并行计算模型。并行计算模型在用户需求和底层的硬件系统之间搭建桥梁使得并行算法的表示变得更加直观，对大规模数据的处理更加便捷。根据用户使用硬件环境的不同，并行编程模型又可以分为在多核机器、GPU计算、大型计算机以及计算机集群上的多种类型。目前比较常用的并行编程接口和模型包括：

pThread接口[2]。pThread是在类Unix系统上进行多线程编程的通用API，为用户提供了一系列对线程进行创建、管理和各类操作的函数，使用户能够方便地编写多线程程序。

MPI模型[3]。MPI的全称为消息传递接口（Message Passing Interface），它为用户提供了一系列的接口，使用户利用消息传递的方式来建立进程间的通信机制，从而方便地对各种算法进行并行实现。

MapRece模型[4]。MapRece模型是由谷歌公司提出的并行编程框架，它首先为用户提供分布式的文件系统，使用户能方便地处理大规模数据；然后将所有的程序运算抽象为Map和Rece两个基本操作，在Map阶段模型将问题分解为更小规模的问题，并在集群的不同节点上执行，在Rece阶段将结果归并汇总。MapRece是一个简单，但是非常有效的并行编程模型。

Pregel模型[5]。Pregel同样是由谷歌公司提出的专门针对图算法的编程模型，能够为大规模数据的图算法提供并行支持。一个典型的Pregel计算过程将在图上进行一系列的超级步骤（SuperSteps），在每个超级步骤中，所有顶点的计算都并行地执行用户定义的同一个函数，并通过一个“投票”机制来决定程序是否停止。

CUDA模型①。CUDA是由NVIDIA公司提出的一个基于GPU的并行计算模型。由于GPU在设计需求上与普通CPU不同，GPU通常被设计为能较慢地执行许多并发的线程，而不是较快的连续执行多个线程，这使得GPU在并行计算上有先天的优势。CUDA为用户提供了利用GPU计算的各种接口，使程序员能够像在普通电脑上进行CPU编程那样进行GPU程序的编写。

此外还有OpenMP、PVM、OpenCL等各种并行编程模型和方法。这些并行编程和方法一般都提供了主流编程语言的实现，从而使得用户能根据自身编程习惯来选用。

另一方面，随着云计算的不断推广，还出现了各种商用的并行计算/云计算平台，为用户提供并行计算服务。这其中比较着名的包括微软的Azure平台、Amazon公司的EC2平台、IBM公司的蓝云平台、谷歌公司的Google App Engine等。各大IT公司也纷纷开发自己的并行计算模型/框架作为自身技术服务的基本平台，这使得并行计算技术得到了更加快速的发展。

3基于并行编程模型高效海量数据挖掘算法研究

为了实现海量数据上的数据挖掘，大量分布式并行数据挖掘算法被提出。Bhari et al[6]整理了一个十分详尽的并行数据挖掘算法文献目录，包含了关联规则学习、分类、聚类、流数据挖掘四大类分布式数据挖掘算法，同时还包括分布式系统、隐私保护等相关的研究工作。

MapRece并行编程模型具有强大的处理大规模数据的能力，因而是海量数据挖掘的理想编程平台。数据挖掘算法通常需要遍历训练数据获得相关的统计信息，用于求解或优化模型参数。在大规模数据上进行频繁的数据访问需要耗费大量运算时间。为了提高算法效率，斯坦福大学Chu et al[7]提出了一种适用于大量机器学习算法的通用并行编程方法。通过对经典的机器学习算法进行分析可以发现，算法学习过程中的运算都能转化为若干在训练数据集上的求和操作；求和操作可以独立地在不同数据子集上进行，因此很容易在MapRece编程平台上实现并行化执行。将大规模的数据集分割为若干子集分配给多个Mapper节点，在Mapper节点上分别执行各种求和操作得到中间结果，最后通过Rece节点将求和结果合并，实现学习算法的并行执行。在该框架下，Chu et al实现了十种经典的数据挖掘算法，包括线性回归、朴素贝叶斯、神经网络、主成分分析和支持向量机等，相关成果在NIPS 2006会议上发表。

Ranger et al[8]提出了一个基于MapRece的应用程序编程接口Phoenix，支持多核和多处理器系统环境下的并行程序设计。Phoenix能够进行缓存管理、错误恢复和并发管理。他们使用Phoenix实现了K-Means、主成分分析和线性回归三种数据挖掘算法。

Gillick et al[9]对单程学习（Single-pass）、迭代学习（Iterative Learning）和基于查询的学习（Query-based Learning）三类机器学习算法在MapRece框架下的性能分别做了评测。他们对并行学习算法涉及到的如何在计算节点之间的共享数据、如何处理分布式存储数据等问题进行了研究。

Mahout①是APS（Apache Software Foundation）旗下的一个开源数据挖掘项目，通过使用Apache Hadoop库，可以实现大规模数据上的并行数据挖掘，包括分类、聚类、频繁模式挖掘、回归、降维等算法，目前已经发布了四个版本。

4基于云计算的海量数据挖掘服务研究

云计算除了给用户提供通用的并行编程模型和大规模数据处理能力之外，另一个重要的特点是为用户提供开放的计算服务平台。在数据挖掘方向，现在也有一系列的系统被开发出来，面向公众提供数据挖掘服务云计算平台。

Talia et al[10]提出可以从四个层次提供云计算数据挖掘服务：底层为组成数据挖掘算法的基本步骤；第二层为单独的数据挖掘服务，例如分类、聚类等；第三层为分布式的数据挖掘模式，例如并行分类、聚合式机器学习等；第四层为之前三层元素构成的完整的数据挖掘应用。在此设计基础上，他们设计了基于云计算的数据挖掘开放服务框架，并开发了一系列的数据挖掘服务系统，例如Weka4WS、Knowledge Grid、Mobile Data Mining Services、Mining@home等，用户可以利用图形界面定义自己的数据挖掘工作流，然后在平台上执行。

PDMiner[11]是由中国科学院计算技术研究所开发的基于Hadoop的并行分布式数据挖掘平台，该系统现在已经用于中国移动通信企业TB级实际数据的挖掘。PDMiner提供了一系列并行挖掘算法和ETL操作组件，开发的ETL算法绝大多数达到了线性加速比，同时具有很好的容错性。PDMiner的开放式架构可以使用户将算法组件经过简单配置方便地封装加载到系统中。

此外，商业智能领域的各大公司也提供面向企业的大规模数据挖掘服务，例如微策略、IBM、Oracle等公司都拥有自己的基于云计算的数据挖掘服务平台。

5总结和展望

通过云计算的海量数据存储和分布计算，为云计算环境下的海量数据挖掘提供了新方法和手段，有效解决了海量数据挖掘的分布存储和高效计算问题。开展基于云计算特点的数据挖掘方法的研究，可以为更多、更复杂的海量数据挖掘问题提供新的理论与支撑工具。而作为传统数据挖掘向云计算的延伸和丰富，基于云计算的海量数据挖掘将推动互联网先进技术成果服务于大众，是促进信息资源的深度分享和可持续利用的新方法、新途径。

I. 帮忙翻译一下这段英文，重谢，好的再补谢，有点急

4. Conclusion and Future Work
总结与未来的工作

In this paper, we propose a novel approach that appends clustering information by adding a relevant feature to the training set so as to improve the predictive power of basic classifiers against imbalanced data sets.
在这篇文章里，我们提出了一个崭新的方法，在添附的集群信息上把一个相关特性加进训练集合里，使之加强其对不平衡数据组基本分类法的推断能力。

In our approach, difficult examples from both the majority and minority classes are identified
ring execution of the single-pass clustering algorithm; thus both easy examples and difficult
examples will be labeled distinctly from the new extra feature.
我们我方法里，一次过的集群运算法的执行过程中，确定了从多数和少数两类得出的困虽例子。所以容易的例子和困难的例子将从新的额外特性里得以明显地标记。

Therefore, the original data distribution doesn’t change and the skewness of features biased towards the majority class has been alleviated.
于是，原来的数据分配不会影响和偏态特性的偏向于多数类亦被缓解了。

The comparison between the experimental results on data sets from UCI Machine Learning Repository and the basic classifiers shows that the cluster based extra-feature-adding approach achieved promising performance.
从UCI机器学习的存储库数据集上的实验结果和基本分类法之间的比较显示，基于集群的额外特性添加方法实现了很有前途的绩效。

In the further research, which kind of classifier is more appropriate to corporate our approach to solve the imbalance classification problem will be our concern.
在进一步的研究里，那一种分类方法会更适合企业解决不平衡分类问题将是我们关注。
Acknowledgments
This work is supported by the National Natural Science Foundation of China (No. 61070061),
Guangzhou Science and Technology Plan Projects (No.2011J5100004). The authors thank
ZhaoQing Xie and Bang Miao for helping do some data tests of the paper.
鸣谢
这项工作得到中国国家自然科学基金（编号：61070061）和广州省科技计划项目（no.2011j5100004）的支持。作者特此感谢肇庆和邦苗(翻音或会有偏差)的帮助，给我这篇文章做了一些数据测试。

已替你精心精工翻译好了，希望会对你有帮助，并望满意采纳，谢谢。