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）的支持。作者特此感謝肇慶和邦苗(翻音或會有偏差)的幫助，給我這篇文章做了一些數據測試。

已替你精心精工翻譯好了，希望會對你有幫助，並望滿意採納，謝謝。