物联网水产品追踪算法研究

叶质刚

摘要：针对物联网在水产品的捕捞、生产、加工、销售过程中会产生大量数据，如何在大量的数据里面，进行水产品的快速追踪。分析了水产品的各个环节的关联，提出了改进CLARANS聚类追踪算法，来进行运算存储，从而达到快速追踪水产品的安全信息的目的。

关键词：物联网；水产品；改进CLARANS算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）16-0135-02

Abstract： For things in fish harvesting， production， processing and sales process will generate a lot of data， how large amounts of data inside， fast track of aquatic products. It analyzes the relationship between the various aspects of aquatic products， an improved tracking CLARANS clustering algorithm for computing storage， so as to achieve fast track aquatic safety information purposes.

Key words： the internet of things； aquatic； improved algorithm CLARANS

1 背景

主要以水产品在捕捞、生产、加工、销售全过程的物联网采集信息为基础，建立起有效的水产品追踪与溯源大数据，经过后台的云计算平台实现水产品的安全信息追踪，现在的追踪算法还比较慢，如何提高大数据的数据查询效率从而提高水产品的追踪效率成为现在食品安全追踪的一个瓶颈。

2 相关技术介绍

基于物联网的水产品安全信息追踪系统：捕捞管理子系统、生产管理子系统、大数据中心、监管子系统、水产品追踪服务子系统。

1）捕捞管理子系统：是水产品的前端环节，把外海捕捞的水产品通过RFID、全球定位系统、二维码扫描、摄像头等来认识和感知物体的信息，并将相关的物体信息传递保存到大数据中心。

2）生产管理子系统：感知层采集的水产养殖产品从育苗、喂养到收成实时数据通过传输层传送到大数据中心存储。

3）大数据中心：利用大数据和云存储的技术对传输过来的实时数据进行存储和处理，为决策提供依据，最终体现物联网的效率与优势。

4）监管子系统：对水产品的生产捕捞环境、病虫害防治用药及剂量、质量安全管理进行监控管理。

5）水产品跟踪定位子系统：对水产品的生命周期信息进行溯源跟踪定位，包含水产品的育苗到销售终端的全程跟进，增强消费者的满意度，细化政府的监管粒度，提高企业的产品质量标准。

3 CLARANS算法及起源

CLARANS算法是Clara算法的改进，它本身是一种分割聚类算法。首先来看一下CLARANS算法的逻辑。首先会在聚集里随机选一个点作为当前点，然后随机检查它周围不超过指定个数的一些邻节点，假如找到一个比它更好的邻节点，则把它移入该邻节点，否则把该点作为局部最小代价。然后再任意选一个节点来捕获另一个局部最小代价值，一直到所捕获的局部最小代价数目达到客户所要求的数目为止，才结束循环。此算法要求所有聚类的对象都必须事先调人内存空间，而且还要N次扫描数据集合，这对于大数据量来讲，无论是时间复杂性还是空间复杂性都相当的巨大，所以运行的效率是必须考虑的重要因素。CLARANS与Clara算法不同之处：Clara算法在找寻最佳的medoids进程中，所有的采样都是不变的。但CLARANS算法在每一次循环的进程中所采用的采样样本都是不相同的。而且与上面所讲的获得最佳medoids的过程不相同的地方，就是必须由人来限定循环的次数。

4 Clara算法

研究CLARANS算法就必须先了解Clara算法，在这里对Clara算法进行说明。Clara算法又是K-medoids算法的一种改进。主要由于K-medoids算法适合于小数据量的计算，所以提出了一种基于对大数据量进行采样的方法，这就是 Clara算法，进行了这样的改进，Clara算法就可以适合进行针对大数据量的运算。Clara算法的基本思路就是对那些具有大数据量的真实数据采用其中的抽样数据来代替整个大数据，进而再在这些抽样的小数据上利用K-medoids算法提取最佳的medoids。Clara算法从实际数据中会进行多个采样动作，在每个采样上进行K-medoids算法运算得到对应的（O1，O2?Oi?Ok），然后在这当中选取最小的一个代价E作为最终的结果。

5 K-MEDOIDS算法

K-medoids是对K-MEANS的一种改进，因为K-MEANS有其缺点：产生类的大小相差不会很大，对于脏数据很敏感。 改进的地方：会先选取一个对象叫做mediod来代替K-MEANS的中心的作用，这样的一个medoid就标识了这个聚类 。这样对于错误数据和异常数据就不会受大的波动，但运算工作量明显要比K均值方法要大，一般在小数据量的情况下采用。

CLARANS算法的改进

6 改进算法

研究了CLARANS算法，就是循环次数N的确定和抽样的方式最影响效率和准确性，在这提出一种改进方式，称之为CLARANS-CY，那就是抽样方式可以采用：

1）简单随机抽样法；2）分层随机抽样法；3）整群抽样法；4）预定随机法的方式进行循环，numlocal设定为4的倍数，maxneighbor的设置随着抽样方法来选定，当采用简单随机抽样法时值设得大一些，分层随机抽样法值设得小一些，整群抽样法值设得更小，预定随机法则值最小，以便适应水产品生命周期的数据实际情况。改进后的CLARANS步骤：

1）输入参数numlocal和maxneighbor. numlocal 表示抽样的次数，这里改进成为4的倍数， maxneighbor 用来表述一个节点可以与任意特别指定邻节点进行比较的数值，并且随着抽样方法的不同随时进行适当调整。

令：i=1，i用来表示已经选样的次数，minwortht为最小值，初始时设为大数。

2）设置当前节点current为抽样Kn中的任意一个节点。

3）令：j =1。（j在这里代表已经与current进行较验的邻接点的数目）。

4）考虑当前点的一个随机的节点P，并计算两个节点的值worth。

5）如果P的值较低，则current：=P，转到步骤3。

6）否则，令j=j+1。如果j<=maxneighbor，则转到步骤4。

7）否则，当j>maxneighbor，当前节点为本次选样最小值节点. 如果其值worth小于minworth，令minworth为当前节点的值，最佳节点为当前的节点。

8）令 i= i+1，如果i〉numlocal，输出最佳节点，运算中止.否则，转到步骤2。

7 实验测试

以5类水产品的育苗、销售、养殖、捕捞、批发、零售的数据作为测试数据来验证改进算法的追踪效率，进行了10次的追踪查询，其中有4次的CLARANS-CY算法与CLARANS算法相同，6次的CLARANS-CY算法比CLARANS算法的效率高。通过对比可知改进的CLARANS-CY算法在物联网水产品追踪过程中能够提高一定的查询定位效率。

8 结束语

虽然物联网在水产品安全追踪带来新的优势，但同时带来数据处理效率的问题。通过研究物联网水产品的追踪系统的结构原理，针对水产品的安全信息的特点，提出了改进的CLARANS-CY算法在水产品大数据分析存储和安全信息追踪中的想法。文章分为几部分，涉及物联网水产品的结构，常用的几种聚类算法；最后着重讨论了改进的CLARANS-CY算法并进行实验室的验证测试。

参考文献：

[1] 潘丽娜， 王治和， 党辉. 基于关联函数的数据流聚类算法[J]. 计算机应用， 2013， 33（1）： 202-206.

[2] 米红娟， 水静. 基于CLARANS 算法的孤立点挖掘[J]. 北京电子科技学院学报， 2007（12）： 80-83.

[3] 杨信廷， 孙传恒， 钱建平，等. 基于流程编码的水产养殖产品质量追溯系统的构建与实现[J]. 农业工程学报， 2008（2）： 159-163.

[4] 董微， 闻育. 基于数据关联性聚类的数据布局算法[J]. 计算机工程与应用， 2014， 50（3）： 117-120.

[5] 程文静， 姚立， 岳子琳，等. 基于物联网的MES产品追踪的研究[J]. 计算机与数字工程， 2013（2）： 330-332.