基于Web 电子商务平台的食用菌产品共词聚类算法*

纪 琳

（浙江经济职业技术学院商贸流通学院，浙江 杭州 310018）

食用菌产品电子商务网站一般都包含有大量的信息。用户在对食用菌产品进行购买销售时，信息以检索或提交的方式传递给Web 后台数据库[1]，数据库进行查询、插入等操作。除交易信息外，Web页面也包含有大量其它的信息，如用户的登录次数、搜索产品的名称、查询所用的关键词或主题。这些信息对电子平台来说，是十分重要的信息。从中可以发现一些高影响力和高频检索的主题，将其中有共同特征的主题词进行分组，从而形成一组较高相似度的主题，这一过程即是称为聚类，采用的算法即为聚类算法。

1 共词聚类算法基本概念

对于食用菌产品电子商务平台来说，电子商务平台的Html 语言都以标签的形式来定义标题、主体等文档信息[2]。每一个标签都有其属性，属性提供了有关Html 标签的更多的信息，其中大多数Html 标签共同使用的标准属性有Class、Id 和Style。Class用来对信息进行归类，代表具有共同性质的数据信息，在同一页面中同一类信息可以多次出现。

1.1 聚类算法

聚类算法主要应用在主题和关键词的搜索以及它们之间关系的分析上[3]。这一组主题的集合称为“簇”，簇的特点是内部的数据对象之间有较高的相似度，而与簇外的数据有较高的相异度。对象间的相异度一般采用两对象间的距离来度量，常用的距离函数有欧几里得距离、切比雪夫距离、曼哈顿距离、明可夫斯基距离等。

以明可夫斯基距离为例[4]，如式（1） 所示。

式中：n表示n维空间，k为任意常数，x和y为n维空间两点坐标。

可以看出，距离越近相似度越高。在聚类算法中，相似系数是与距离相反的一种度量方法，相似系数大，说明对象间的相似性高。常用的夹角余弦法、数量积法、指数相似法等表示相似系数。

以数量积法为例，当i=j时，相似系数Sij=1；当i≠j时，相似系数计算如式（2） 所示。

式中：M为正数，且

1.2 共词聚类算法

共词聚类也是一种聚类算法，是一种无中心的网状聚类，没有明确的中心主题特征，并不关心其它主题与中心主题间的距离。共词聚类研究的是主题之间的关系，即主题与主题之间的距离，将距离比较近的主题归为一类，形成一个相对独立的小类，在这一小类中各主题的相似度很高，但每个小类之间的相异度较高。也就是将一个大类分成各个相对独立、互不干扰的小类。共词聚类算法常用在对文档中高频主题词之间关联性的评价上，主题词关系越紧密，则聚类效果越好，比较符合文档关键词的分布形态研究[5]。由于共词聚类描述的是主题词或关键词之间关系的紧密程度，因此主题与主题间的相互依赖关系十分重要，一旦一个主题属性变化，就会传递到其它主题，从而引起连锁反应，使聚类方式发生变化，影响聚类结果，所以共词聚类是不稳定的网状聚类方式[6]。

2 食用菌电子商务平台的共词聚类算法设计

食用菌电子商务平台是一个以销售各类食用菌的电子交易平台，大量的信息在给用户带来便利的同时，也带来了信息爆炸和信息过载的问题，数据分析处理越来越难，面对信息时的选择无所适从。用户无法快速锁定想要购买的产品，商家无法针对性营销，结果就造成了用户体验变差，潜在用户流失。

因此，急需将大量食用菌电子商务平台的数据、信息进行挖掘，对用户进行画像、分类找到潜在消费群体、挖掘爆款食用菌产品，实施精准营销。就食用菌电子商务平台的数据挖掘来说，共词聚类算法是一个比较好的选择，可以用于对电子商务网站Web 页面的文档主题和关键词进行挖掘，从而找到潜在用户的分类。

2.1 基于密度的共词聚类算法原理

常用的聚类算法有对于发现任意形状的聚类存在困难。对于共词聚类来说，更适合用密度来描述聚类。该算法按照给定的阈值，与划定聚类区域内所有的点个数进行比较，如果大于阈值则将其归为一类，从而实现相近小类的聚类。该聚类区域中点的个数用密度来表示。常见的密度聚类算法有OPTICS、DBSCAN 算法等。DBSCAN 算法就是利用密度连通性实现聚类。其基本思想是对于类中的每个对象都必须是核心对象。但由于该算法和数据的输入顺序无关，因此数据处理量较大，易产生高维数据。因此又有了基于网格的算法，将空间数据离散化，形成一个网结构，从而解决高维数据的处理速度问题，如CLIQUE 算法、Wave Cluster 算法等。

2.2 共词聚类算的实现

共词聚类算法实现主要步骤如下。

第一，找出含有聚类的密集子空间。在算法的实现过程中，由于是由k 维的密集单元格集合Dk生成k+1 维的密集的候选单元格集合Ck+1，因此数据结构应设计成树形。

从时间复杂度可以看出，时间复杂度和密集单元格最高维子空间称指数关系，维数的增加将导致时间复杂度的快速增长；这种算法在处理高维数据时效率仍不高[7]。密集单元会随着子空间维数的增长快速增长，对于密集单元不一定都是我们想要的，因此在实现过程中可以采用MDL 的裁剪，剪去一些不合格的候选集，只保留我们感兴趣的密集单元，从而降低时间复杂度。MDL 中心思想就是为了使代码最短，按照一定的模式对输入的数据进行编码。假设存在一个子空间集合{D1,D2, …,Dn}，MDL 方法计算各个子空间含有的记录数公式为：

式中：couny（ui）是ui中含有的数据点的数目。

对子空间进行覆盖的降序排序，子空间被分成两个集合，一个是被选中集合R，一个是被裁剪掉的单元的集合P。分别计算这两个集合区域覆盖的平均值，以及该平均值和集合中每个子空间的差；然后把存储这些值需要的数位进行相加，得到的结果就是我们想要的目标编码函数：

找到一个能使目标函数TL（i） 的值最小的i值，这个i值也就是被选中区域和被裁减区域的分界点。由于使用了MDL 裁剪技术进行了裁剪，这样可以降低时间复杂度，但同时也会导致一些密集单元被漏掉，降低了聚类的效果。

第二，非密集单元的移动处理。针对MDL 裁剪技术有遗漏的问题，在处理非密集单元时不能简单裁剪，而应将其移动处理。即如果某个单元格的中心点与重心点不在同一位置，即重心点偏向于邻近的密集单元，以该单元的重心为中心，重新画一个单元，使该单元中的数据点尽可能分布均匀，也就是说使它的中心和重心重合。本质上来看，新的单元就是原来的单元向密集单元移动了。最重要达到的目标就是使包含属于同一个簇中的数据点的单元靠的紧密一些。

非密集单元的移动处理目标是对于给定的数据集合找出它的簇，找出每一个对象所属的cluster 并进行标识，算法主要通过数据空间的划分将密集单元找出，而对于非密集单元，将其向密集单元移动。从而聚类生成cluster，cluster 中的每一个数据点都被标记一个clusterID，即聚类编号。和Step 1 中的步骤一样，采用深度优先算法来找出密集的连通的子空间。通过FindCluster (u,clusterno) 函数来实现，clusterno 是密集单元的cluster 编号。FindCluster (u,clusterno) 函数的伪代码如下：

输入：经移动处理后的数据单元；

FindCluster (u,clusterno) {

Cellnumber=oldCellnumber+addCellnumber;

For (i=0;i

If ( ui 是密集单元&&ui 不属于任何一个聚类&&ui 和u 是连通的) {

输出：生成的聚类以及它们的编号clusterno。

第三，找出给定的子空间的聚类。在这一步中，需要输入的是一个处在同一个子空间中的密集单元格集合D，输出是{D1,D2, …Dn} 即D的一个划分。

第四，产生聚类的描述。即输入同一个子空间中的一个密集单元格集合，这个集合中的单元在k维空间中本应该是连接在一起的，操作把它们分开了，这些单元组成一个聚类P。找出构成聚类的所有单元，这些单元包含的连通单元的数目最少，这样做的目的就是使每个聚类的描述达到最小。

3 结论

将共词聚类应用在食用菌电子商务平台的数据挖掘上，也是一种新的尝试和探索。但在实际的电子商务数据分析中，如果得到的聚类用户难于理解，那么就难把它应用到实际的电子交易中。聚类结果必须易于理解、方便平台用户的使用，需要把聚类结果和特定的解释与电子商务的应用相联系。共词聚类算法，克服了原有密度聚类算法的精度受方格大小影响、以及由于裁剪造成的聚类结果精确度不高等缺点，在电子商务平台的应用上表示出了良好的性能。后续还需要通过仿真实验验证算法有效性，进一步改进算法提高聚类精度。