Thoughts, stories and ideas.

移动对象轨迹是由大量的时空数据组成的一系列数据，具有实时性、海量性、不确定性等特点，如何通过对实时的时空轨迹数据进行分析进而挖掘出用户需要的轨迹行为模式是基于位置服务的一大研究热点。

数据挖掘（Data Mining）近来一直备受关注，相关研究也逐渐深入，加之技术日趋成熟，已逐渐转变成用户移动数据挖掘的一种重要工具。由时间序列引出的序列模式挖掘（Sequence Pattern Mining），作为数据挖掘的一个重要方法，吸引了很多研究者前来研究，一定程度上解决了如何通过用户的移动轨迹数据集挖掘出有效信息的困惑。面对时间和空间两个方面的移动轨迹信息，首先通过时间这一属性将轨迹数据转化为时间线上的序列模式（Sequence Pattern），再对每条的序列数据进行模式挖掘（Pattern Mining），去除噪音，挖掘出有效信息。序列模式挖掘已经成为将移动对象的大量轨迹数据转化为有用的信息资源的有效工具，进而可以进行高效的科学决策。

对于序列模式挖掘算法，国内外的一些研究均在Apriori的算法以及PrefixSpan算法这两大类的基础上进行的。Apriori算法是R.Agrawal和R.Srikant共同提出的规则挖掘频繁项集的算法，并且此算法衍生了很多其他的算法，例如：AprioriAll算法、GSP算法和SPADE算法等。而PrefixSpan算法则是由J.Han等人提出的基于数据库投影模式增长的算法，此算法也衍生出很多算法，例如：Freespan算法等。

序列模式挖掘（Sequence Pattern Mining）是指在时间序列数据中挖掘频繁出现的时间序列。序列模式挖掘在数据挖掘的研究中占着十分重要的位置。时间序列数据通过系统提取，能够让人们做出适当的调整或者及时发现变动，而且时间序列数据之间的规律通过序列模式挖掘之后则可以发现更多潜在的知识，甚至成为一个重要的理论热点或者发现更高的实用价值。

• AprioriAll算法属于Apriori类算法，其基本思想为首先遍历序列数据库生成候选序列并利用Apriori性质进行剪枝得到频繁序列。每次遍历都是通过连接上次得到的频繁序列生成新的长度加1的候选序列，然后扫描每个候选序列验证其是否为频繁序列。
• GSP（generalized sequential pattern）算法是AprioriAll算法的扩展算法，其算法的执行过程和AprioriAll类似，最大的不同在于GSP引入了时间约束、滑动时间窗和分类层次技术，增加了扫描的约束条件，有效地减少了需要扫描的候选序列的数量。此外GSP利用哈希树来存储候选序列，减少了需要扫描的序列数量。
• FreeSpan算法是基于模式投影的序列挖掘算法，其基本思想：利用当前挖掘的频繁序列集将序列数据库递归地投影到一组更小的投影数据库上，分别在每个投影数据库上增长子序列。这一过程对数据和待检验的频繁模式集都进行了分割，并且每一次检验限制在与其相符合的更小投影数据库中。
• PrefixSpan是FreeSpan的改进算法，即通过前缀投影挖掘序列模式。其基本思想：投影时不考虑所有可能出现的频繁子序列，只检查前缀序列，然后把相应的后缀投影成投影数据库。每个投影数据库中，只检查局部频繁模式，在整个过程中不需要生成候选序列。

AprioriAll GSP这两种算法都属于Apriori类算法，都要产生大量的候选序列，需要有足够的存贮空间。同时还需要反复扫描数据库，需要占用很多运行时间。该类算法的执行效率比较低，特别是在支持度比较低的情况下，其执行效率将会大大下降。和AprioriAll相比，GSP的执行效率比较高，总体来说要比AprioriAll高2~20倍。

FreeSpan PrefixSpan这两种算法都属于模式增长算法，它们的查找更加集中和有效。由于该类算法不生成大量的候选序列以及不需要反复扫描原数据库，和Apriori类算法相比该类算法要快且更有效，特别是在支持度比较低的情况下更明显。此外，在时空的执行效率上，PrefixSpan比FreeSpan更优。

K-means算法属于基于划分的聚类方法，是一种最简单的无监督学习算法，也是十大经典数据挖掘算法之一。
K-means算法通过迭代来实现，其基本思想为：每次确定K个中心点，将各节点归属到与之最近的中心点所代表的cluster，然后确定新的中心点，并继续聚类，直到聚类结果不再变化停止迭代。

K值的选取：
算法中K值需要事先给定，但这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是K-means算法的一个不足。

初始中心点的选取：
初始聚类中心点唯一地决定了聚类结果，因此其选择对聚类结果有很大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也是K-means算法的一个主要问题。

K-means算法并不能保证得到的解为全局最优解，通常得到的是一个局部最优解。

K-means算法确定的K个cluster达到平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果比较好。对于处理大数据集，这个算法时高效和可扩展的，时间复杂度可达到最优。

改进算法：

• K-means要手工输入类数目，对初始值的设置很敏感，所以有了K-means++、intelligent K-means、genetic K-means；
• K-means对噪声和离群值非常敏感，所以有了K-medoids和K-medians；
• K-means只用于numerical类型数据，不适用于categorical类型数据，所以K-modes；
• K-means不能解决非凸（non-convex）数据，所以有了kernel K-means。

聚类算法主要是用在聚类分析中的算法，而聚类分析（群集分析）是对于统计数据分析的一门技术把相似的对象通过静态分类的方法分成不同的组别或者更多的子集，这样让在同一个子集中的成员对象都有相似的一些属性，常见的包括在坐标系中更加短的空间距离等。

移动对象常访问位置点的挖掘（聚类算法）：

• 基于划分的算法的输入是包含n个对象的数据库和簇的数目k；输出是k个簇，使平方误差准则最小。优点：简单，易于理解和实现；时间复杂度低。缺点：K-means要手工输入类数目，对初始值的设置很敏感；对噪声和离群值非常敏感；只用于numerical类型数据，不适用于categorical类型数据；不能解决非凸（non-convex）数据；主要发现圆形或者球形簇，不能识别非球形的簇。
• 基于密度的算法的输入是包含n个对象的数据库，输出是多个簇。优点：与K-means方法相比，DBSCAN不需要事先知道要形成的簇类的数量；与K-means方法相比，DBSCAN可以发现任意形状的簇类；同时，DBSCAN能够识别出噪声点；DBSCAN对于数据库中样本的顺序不敏感。缺点：DBSCAN不能很好反映高尺寸数据；DBSCAN不能很好反映数据集变化的密度；对于高维数据，点之间极为稀疏，密度很难定义。
• 基于层次的算法的输入是包含n个对象的数据库，输出是一类簇。优点：距离和规则的相似度容易定义，限制少；不需要预先制定聚类数；可以发现类的层次关系；可以聚类成其它形状。缺点：计算复杂度太高；奇异值也能产生很大影响；算法很可能聚类成链状。
• 基于网络的算法的输入是高维的输入向量，输出是聚类网络。优点：可以实现从输入空间(n维)到输出平面(2维)的降维映射。缺点：时间复杂度高，处理时间较长。

K-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。
K-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。K-means算法的处理过程如下：首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。

The Configuration of Wireshark

Capture the interface “enp2s0” which is my Ethernet adapter.
The filter rule is “udp port 67” for capturing DHCP packets, “udp port 53” for capturing DNS packets.

DHCP Message Format

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     op (1)    |   htype (1)   |   hlen (1)    |   hops (1)    |
+---------------+---------------+---------------+---------------+
|                            xid (4)                            |
+-------------------------------+-------------------------------+
|           secs (2)            |           flags (2)           |
+-------------------------------+-------------------------------+
|                          ciaddr  (4)                          |
+---------------------------------------------------------------+
|                          yiaddr  (4)                          |
+---------------------------------------------------------------+
|                          siaddr  (4)                          |
+---------------------------------------------------------------+
|                          giaddr  (4)                          |
+---------------------------------------------------------------+
|                                                               |
|                          chaddr  (16)                         |
|                                                               |
|                                                               |
+---------------------------------------------------------------+
|                                                               |
|                          sname   (64)                         |
+---------------------------------------------------------------+
|                                                               |
|                          file    (128)                        |
+---------------------------------------------------------------+
|                                                               |
|                          options (variable)                   |
+---------------------------------------------------------------+