目前互联网上产生了海量的数据, 而单机串行处理海量数据时存在瓶颈, 因此使用云计算、大数据对海量数据进行挖掘的技术不断涌现. 文本聚类可将相似的文本进行归类处理, 提取出文本中的关键信息, 该技术目前被广泛的应用在众多领域^[1,2]. 针对目前互联网上的海量数据, 采用Hadoop对海量数据并行化实现文本聚类可有效的解决单机处理数据效率低的缺点.

目前, 国内外的一些学者对文本聚类的算法进行了研究. 国内的贾瑞玉等^[3,4]基于MapReduce模型并行化实现了遗传K-means聚类算法; 赵卫中等^[5]通过对云计算平台Hadoop进行研究, 将K-means聚类算法与遗传算法相结合并基于Hadoop平台进行了并行实现; 而国外的Er和Erdoğan^[6]通过改进遗传算法中的染色体编码和适应度函数来选取聚类算法中的最优K值; 文献[7]中的Jiang为减少算法的计算量, 以遗传算法中染色体的基因编码值作为K-means聚类算法的簇中心.

本文针对K-means聚类算法存在易陷入局部最优解等缺点, 而遗传算法所具备的特点正好可解决其缺点, 由此提出并实现了一种基于Hadoop的改进型遗传聚类算法.

1 Hadoop平台及文本聚类 1.1 Hadoop平台

Hadoop平台是由Apache Software Foundation开发的开源项目^[8,9]. 该平台的核心组件是MapReduce和HDFS.

HDFS以分布式的形式将划分的数据块存储到多节点中. 其中名字节点的工作用于管理名字空间和处理有关客户端对数据的访问等操作; 数据节点的工作则用以完成所在节点的存储、根据名字节点的要求实现对数据块的创建和删除等操作^[10,11].

MapReduce的核心是map和reduce函数, 通过它们可实现对海量数据的并行化编程. MapReduce中用户输入的键值对在map的映射下会得到新的键值对作为中间输出结果, 而该中间结果经过reduce函数的规约处理后, 可得到最终结果^[12,13].

1.2 文本聚类

文本聚类是指将无序的对象作为输入, 使用相似性度量函数计算未知类别文本的相似性, 输出则为相似性文本组成的簇集. 其聚类过程采用数学形式表示为: 设文本数据集: D={d₁, d₂, …, d_i, …, d_n}, d_i为数据集中的文本, n为总文本数, 聚类之后得到的簇集为: E={e₁, e₂, …, e_j, …, e_k}, e_j为相似文本聚成的簇, k为聚类个数. 当满足条件 $\forall {d_i}({d_i} \in D),\exists {e_j}({e_j} \in E),{d_i} \in {e_j}$ , 将语料库D分为k个簇, 使其满足如下公式: $ \cup _{i = 1}^k{e_i} = D$ , 且 ${e_i} \cap {e_j} = \varphi $ .

2 基于Hadoop的改进型遗传聚类算法 2.1 遗传算法

遗传算法由学者Holland提出. 该算法包括5个不可缺少的成分: 种群规模、编码、种群初始化、适应度函数和遗传操作.

2.1.1 编码

常见的编码方法有二进制编码、浮点数编码和符号编码, 因二进制编码在编码和解码上操作简单, 易于实现, 故最为常用.

2.1.2 种群初始化

编码方式确定后, 可对种群进行初始化, 通常可采用两种方法, 一种是参数范围内通过重复随机选择个体的方式达到种群所需的规模; 另一种则在局部最优解区间内, 根据经验选出初始种群.

2.1.3 适应度函数

适应度函数的选择通常和目标函数相关. 当目标函数分别为求最小值和最大值问题时, 适应度函数分别如式(1)和式(2)所示.

$Fit(f(x)) = \left\{ \begin{split} & {F_{\max }} - f(x),\;\;f(x) < {F_{\max }} \\ & 0,\;\;f(x) \ge {F_{\max }} \\ \end{split} \right.\quad {\kern 1pt} $

(1)

$Fit(f(x)) = \left\{ \begin{split} & f(x) - {F_{\min }},\;\; f(x) > {F_{\min }} \\ & 0,\;\; f(x) \le {F_{\min }} \\ \end{split} \right.\quad $

(2)

式中, ${F_{\min }}$ 为最小值, ${F_{\max }}$ 为最大值, $f(x)$ 均为适应度值^[14].

2.1.4 遗传操作

选择算子通过选择策略将种群中适应度值较大的个体选择出来, 将较优的个体传给下一代.

交叉算子决定着遗传算法的全局寻优能力, 是算法的核心. 在进行交叉操作时可通过单点交叉、两点交叉和多点交叉等方式进行.

在种群规模较大时, 可通过变异操作提高遗传算法的局部搜索能力. 一般变异概率取值均小于0.1. 通常在二进制编码中, 变异操作就是互换0和1的操作.

2.2 改进型遗传算法

针对遗传算法存在的不足和增强遗传算法的全局搜索能力, 从而保证种群的多样性, 提出了一种新的改进型遗传算法(Improved Genetic Agrithom, IGA), 该算法分别在交叉算子、变异算子和自适应遗传算子上做了相应的改进.

2.2.1 交叉算子、变异算子和遗传算子的改进

遗传算法在执行时不仅要提高收敛速度, 也应在迭代过程中提高种群的多样性以增强其全局寻优能力, 因此本文对交叉算子进行了改进, 分别通过进行族内交叉和族间交叉来实现.

变异算子并没有直接选取所有变异后的个体, 而是通过比较变异前后的个体已防止优秀的个体被破坏.

为防止算法陷入局部最优, 本文采用的自适应算子如式(3)和式(4)所示.

${P_c} = \left\{ \begin{split} & \frac{{({p_{c\max }} - {p_{c\min }})}}{{1 + \exp \left( {A\left( {\dfrac{{2(f - {f'})}}{{{f_{\max }} - {f_{\rm avg}}}}} \right)} \right)}} + {p_{c\min }},\quad f \ge {f_{\rm avg}} \\ & {P_{c\max }},\quad f < {f_{\rm avg}}_{} \\ \end{split} \right.\quad $

(3)

${P_m} = \left\{ \begin{split} & \frac{{({p_{m\max }} - {p_{m\min }})}}{{1 + \exp \left( {A\left( {\dfrac{{2({f{''}} - {f'})}}{{{f_{\max }} - {f_{\rm avg}}}}} \right)} \right)}} + {p_{m\min }},\quad {f{''}} \ge {f_{\rm avg}} \\ & {P_{m\max }},\quad {f^{''}} < {f_{\rm avg}}_{} \\ \end{split} \right.$

(4)

式中, ${f'} = \dfrac{1}{2}({f_{\max }} + {f_{{\rm{avg}}}})$ ; ${f^{''}}_{}$ 为要变异个体的适应度值; ${p_{c\max }}$ , ${p_{c\min }}$ , ${p_{m\max }}$ , ${p_{m\min }}$ 均在(0,1)之间.

2.2.2 IGA算法实现的具体步骤

Step 1. 给出种群规模N, 交叉概率P_c, 变异概率P_m和最大迭代次数G_max;

Step 2. 生成初始种群, 对初始种群进行二进制编码;

Step 3. 采用最小生成树Prim算法对种群规模为N的种群进行分类, 得到的最小生成树的每个子连通图作为子类, 对子类编号得到C_i (i=1, 2, … , k);

Step 4. 对个体P_i (i=1, 2, …, N) 的选择采用轮盘赌选择法;

Step 5. 执行交叉操作, 对个体P_i (i=1, 2, … , N)的交叉过程为:

(1)在P_i所属的类C_ic(C_ic∈{C₁, C₂, …, C_k})中进行查找, 随机选择一个类C_ic1(C_ic1∈{C₁, C₂, …, C_k}且C_ic ≠C_ic1)并从中选择出适应度值最大对应的个体P_j, 对P_i和P_j进行单点交叉, 得出子个体表示为T₁和T₂;

(2)在P_i所属的类C_ic(C_ic∈{C₁, C₂, …, C_k})中寻找据C_ic最远的类C_ic2并随机获得一个最优的个体P_k, 对P_i和P_k进行单点交叉, 得出子个体表示为T₃和T₄;

(3)在P_i所属的类C_ic(C_ic∈{C₁, C₂, …, C_k})内选择最优个体P_n, 对P_i和P_n进行单点交叉, 得出子个体表示为T₅和T₆;

(4)对T_i, i ∈(1, 2, 3, 4, 5, 6)进行比较, 从中得到最优子个体T_i并将T_i赋值给P_i.

Step 6. 对P_i执行变异操作, 将得到的新个体P_j的适应度值与P_i的进行比较, 最优的赋值给P_i.

Step 7. 比较P_i的数目与种群规模, 如小于转到Step 4, 如相等则继续;

Step 8. 将迭代次数与设定的最大迭代次数G_max进行比较, 如相等, 算法结束, 否则转向Step 3.

2.3 改进型遗传聚类算法

将上述改进的遗传算法与K-means聚类算法相结合得到改进型的遗传聚类算法IGA-K, 在IGA-K算法中将K-means算法的聚类中心和聚类中心的个数分别作为遗传算法的染色体的基因和染色体的长度, 并对其适应度函数和编码方式进行了改进.

2.3.1 适应度函数的设置

为得到合适的分类结果, 将IGA-K算法的适应度函数设置为式(5)所示:

$f = \frac{{{D_{\min }}}}{{C(x)}} = \dfrac{{\mathop {\min }\limits_{i,j = 1}^k {{\left\| {{c_i} - {c_j}} \right\|}^2}}}{{\dfrac{1}{k}\left( {\displaystyle\sum\limits_{i = 1}^k {\left( {{{\displaystyle\sum\limits_{j = 1}^{{n_j}} {\left\| {{x_j} - {c_j}} \right\|} }^2}/{n_i}} \right)} } \right)}}$

(5)

为使类内更加紧凑, 式中 ${D_{\min }}$ 的值尽可能取大, 而 $C(x)$ 的值尽可能取小.

2.3.2 编码方式的选择

改进的遗传聚类算法中编码方式采用混合型编码, 具体为:

$chrom = \left\{ {\begin{array}{*{20}{l}} {binstr1}&{x1}&{{\mkern 1mu} k(x1)}&{f(x1)}\\ {binstr2}&{x2}&{{\mkern 1mu} k(x2)}&{f(x2)}\\ {\; \vdots }& \vdots &{{\mkern 1mu} \vdots }&{\; \vdots }\\ {binstrn}&{xn}&{{\mkern 1mu} k(xn)}&{{\mkern 1mu} f(xn)} \end{array}} \right. $

2.3.3 IGA-K算法的基本步骤

改进型遗传聚类算法(IGA-K)的具体实现过程如下:

Step 1. 给出遗传操作的基本参数;

Step 2. 对初始种群采用改进的编码形式实现编码;

Step 3. 采用K-means聚类算法的初始聚类中心作为种群中的每个个体并实现对样本的分类, 依据结果计算得到适应度值.

Step 4. 按照IGA算法进行个体的分类和执行相应的遗传操作;

Step 5. 算法如满足结束条件则结束, 否则转到Step 3接着执行.

2.4 基于Hadoop的改进型遗传聚类算法

由于K-means算法和遗传算法二者均具有并行性的特点, 由此本文将改进型的遗传聚类算法迁移到Hadoop平台上进行并行化的实现并将其命名为H-IGA-K算法. 为并行化实现该算法必须实现两个函数, 其中一个关键函数为遗传算法中用于求个体适应度的内部子函数(K-inner), 另一个函数则是H-IGA-K算法的主函数.

2.4.1 K-inner内部子函数的实现

K-inner中包含3个函数, 分别为Map、Combine和Reduce, 其中Map函数的功能为计算数据集中各个样本所属的类别, 输入输出均为键值对. Map的输入键值对中的key表示当前样本相对于数据文件起始点的偏移量; value则为样本属性值生成的字符串; 输出键值对中的key'表示所属类的序号, value'和value一样, 意义没发生变化.

Combine函数为计算本地节点中各类的样本数及其属性值组成的字符串. 该函数的输入键值对中的key表示样本所属类的序号, value为样本属性值生成的字符串; 输出键值对中的key'表示样本所属类的序号, value'则为样本总数和样本属性值组成的字符串.

在K-inner中, Reduce函数的功能尤为重要, 因此这里主要说明Reduce实现的伪代码.

Reduce(<key, value>,<key', value'>)

{ 　 Initialize an Array A; //初始化数组A

　　A.Length=Count of Class; //类的个数为数组长度

　　for i=0 to A.Length-1 //初始分量值为0

　　　A[i]=0; //A[i]为各个类内距离

　　While (value not null)

　　{ 分解得到each sample的各维坐标值;

　　　Get sample number; //得到样本个数

　　　Compute distance between each sample and the center of corresponding class;

　　　Add distance; //计算得到的距离值相加

　　　 value=value.next()

　　}

　　Compute minimum distance base center;

　　//计算最小类间距

　　Compute fitness of population individual;

　　//计算个体适应度的值

　　 key'=value of individual fitness

　　 value'=string of individual chromosome;

　　// value'的值为个体染色体字符串

　　output < key', value'>;

}

2.4.2 H-IGA-K算法主函数的实现

H-IGA-K算法主函数实现的过程中的关键点同样是Reduce函数, 下面是Reduce实现过程的伪代码.

Reduce(<key, value>,<key', value'>)

{

　for i=1 to n

　　{K-inner Function; }

　调用Prim算法对种群进行分类;

　if (满足问题最优解||达到最大遗传代数)

　　{ output(key, maxValue); }

　else

　　{ 按照改进交叉方法执行交叉操作,

　　优选得到下代个体;

　　按照改进变异方法执行变异操作,

　　得到新个体;

　　}

　output(key', value');

}

3 实验结果

本文对基于Hadoop的改进型遗传聚类算法进行了实验. 实验采用10台相同的计算机搭建了实验平台; 该平台使用的软件为Hadoop-2.9.1.tar.gz、CentOS-7-x86_64-NetInstall-1804.iso和jdk-8u181-linux-x6. 实验用数据集为从UCI数据库的Iris、Glass及Adult三个数据集中选择出的数据, 并经人工构造而得, 构造的3个数据集Dataset1、Dataset2和Dataset3的规模分别为100、1000和5000, 3个数据集对应的分类数分别为3、5和10. H-IGA-K算法参数分别为: G_max=300、P_c=0.92、P_m=0.02、自适应算子中的p_cmin、p_mmin、p_cmax和p_mmax的取值分别为0.1, 0.05, 0.9和0.1. 实验分别从聚类准确性和聚类效率两个方面进行了测试.

3.1 聚类准确性实验

为测试基于Hadoop改进型遗传聚类算法的聚类准确性, 本实验使用基于Hadoop的K-means算法和H-IGA-K算法对实验用数据集中的数据分别进行了处理, 表1给出了二者的聚类准确率情况.

由表1可见, 随着数据规模的增加, 两种算法的聚类准确率均在下降, 但下降的程度有所差距, 并且在任何一个数据集下H-IGA-K算法在聚类准确率上均比基于Hadoop的传统K-means聚类算法要高, 特别是Dataset3数据集, 由此说明基于Hadoop的改进型遗传聚类算法优于基于Hadoop的K-means聚类算法, 而且适用于处理大规模的数据集.

3.2 聚类效率实验

为了测试基于Hadoop改进型遗传聚类算法的聚类效率, 本实验通过对3个测试数据集Dataset1、Dataset2和Dataset3分别在1、5、10个节点构建的集群上进行了基于Hadoop的改进型遗传聚类算法的实验, 表2给出了数据集Dataset1、Dataset2和Dataset3在不同节点个数上进行文本聚类时运行所需的时间比较.

由表2可见, 对Dataset1、Dataset2和Dataset3进行操作时, Hadoop集群节点个数越多, 程序运行时所需的总时间均在减少, 节点个数增加越多, 程序运行所需时间越少, 并且随着数据集规模增加, 算法运行时消耗的时间减少的也越多, 由此表明基于Hadoop的多节点的集群更适合处理大数据集, 特别在节点个数达到10个时, 算法运行效率大大提高.

4 结论

本文提出了一种改进型的遗传聚类算法, 并针对单机串行对海量数据聚类效率低的问题, 将改进型的遗传聚类算法基于Hadoop平台进行了实现. 实验表明改进型的算法优于经典聚类算法, 在聚类准确性和聚类效率上均有较大的提高, 适用于处理大规模的数据集. 本文主要针对传统K-means存在易陷入局部最优解的缺点进行的研究, 而传统的K-means算法存在诸多不足, 因此在接下来的研究中, 还可尝试解决K-means算法的其他不足点.