在给定班次列表的情况下创建计划的摘要描述

Question

假设我有一个事件的班次列表(格式为开始日期/时间,结束日期/时间) - 我是否可以使用某种算法来创建日程安排的概括？大多数轮班经常会出现某种常见的复发模式(即周一从上午9:00到下午1:00,周二从上午10:00到下午3:00等).但是,这条规则可以(并且将会是)例外(例如,其中一个班次在假期降低,并在第二天重新安排).将我的"摘要"中的内容排除在外是可以的,因为我希望提供一个更一般的答案,说明此事件通常何时发生.

我想我正在寻找某种统计方法来确定日期和时间,并根据列表中发现的最常见事件创建描述.对于像这样的东西,有某种通用算法吗？有没有人创造类似的东西？

理想情况下,我正在寻找C#或VB.NET的解决方案,但不介意从任何其他语言移植.

提前致谢!

Answer 1

您可以使用Cluster Analysis.

聚类是一种将一组数据分离为类似组件(子集)的方法."相似性"概念涉及点之间"距离"的某种定义.存在许多通常的距离公式,其中包括通常的欧几里德距离.

实际案例

在向您指出交易的怪癖之前,让我们为您的问题展示一个实际案例,这样您就可以参与算法和包,或者提前丢弃它们.

为了方便起见,我在Mathematica中对问题进行了建模,因为Cluster Analysis包含在软件中并且设置起来非常简单.

首先,生成数据.格式为{DAY,START TIME,END TIME}.
开始和结束时间添加了一个随机变量(+半小时,零,半小时),以显示算法处理"噪音"的能力.

有三天,每天三班,一个额外(最后一个)"异常"班次,从上午7点开始,到上午9点结束(可怜的家伙!).

每个"正常"班次中有150个事件,而在特殊班次中只有两个事件.

正如你所看到的,一些变化并不是很远.

我将代码包含在Mathematica中,以防您有权访问该软件.我试图避免使用函数语法,使代码更容易阅读"外国人".

这是数据生成代码:

Rn[] := 0.5 * RandomInteger[{-1, 1}];

monshft1 = Table[{ 1 , 10 + Rn[] , 15 + Rn[] }, {150}];  // 1
monshft2 = Table[{ 1 , 12 + Rn[] , 17 + Rn[] }, {150}];  // 2
wedshft1 = Table[{ 3 , 10 + Rn[] , 15 + Rn[] }, {150}];  // 3
wedshft2 = Table[{ 3 , 14 + Rn[] , 17 + Rn[] }, {150}];  // 4
frishft1 = Table[{ 5 , 10 + Rn[] , 15 + Rn[] }, {150}];  // 5
frishft2 = Table[{ 5 , 11 + Rn[] , 15 + Rn[] }, {150}];  // 6
monexcp  = Table[{ 1 , 7  + Rn[] , 9  + Rn[] }, {2}];    // 7

现在我们加入数据,获得一个大数据集:

data = Join[monshft1, monshft2, wedshft1, wedshft2, frishft1, frishft2, monexcp];

让我们对数据进行聚类分析:

clusters = FindClusters[data, 7, Method->{"Agglomerate","Linkage"->"Complete"}]

"Agglomerate"和"Linkage" - >"Complete"是Mathematica中实现的聚类方法的两个微调选项.他们只是指出我们正在努力寻找非常紧凑的集群.

我指定尝试检测7个集群.如果正确的移位数未知,您可以尝试几个合理的值并查看结果,或让算法选择更合适的值.

我们可以得到一个包含结果的图表,每个集群都有不同的颜色(不介意代码)

ListPointPlot3D[ clusters, 
           PlotStyle->{{PointSize[Large], Pink},    {PointSize[Large], Green},   
                       {PointSize[Large], Yellow},  {PointSize[Large], Red},  
                       {PointSize[Large], Black},   {PointSize[Large], Blue},   
                       {PointSize[Large], Purple},  {PointSize[Large], Brown}},  
                       AxesLabel -> {"DAY", "START TIME", "END TIME"}]  

结果是:

alt text http://i28.tinypic.com/2hmdlab.png

在那里你可以清楚地看到我们的七个星团.

这解决了部分问题:识别数据.现在你也希望能够标记它.

所以,我们将获得每个集群并采取手段(四舍五入):

Table[Round[Mean[clusters[[i]]]], {i, 7}]  

结果是:

Day   Start  End
{"1", "10", "15"},
{"1", "12", "17"},
{"3", "10", "15"},
{"3", "14", "17"},
{"5", "10", "15"},
{"5", "11", "15"},
{"1",  "7",  "9"}

随之而来的是你的七个班级.

现在,也许你想要对这些变化进行分类,无论白天.如果同一个人每天在同一时间完成相同的任务,那么将它称为"星期一从10变为15"是没有用的,因为它也发生在Weds和Fridays(如我们的例子中).

让我们分析一下无视第一列的数据:

clusters=
 FindClusters[Take[data, All, -2],Method->{"Agglomerate","Linkage"->"Complete"}];

在这种情况下,我们不会选择要检索的群集数量,而是将决策留给包裹.

结果是

图片http://i27.tinypic.com/mise9.png

您可以看到已识别出五个群集.

让我们像以前一样"标记"它们:

Grid[Table[Round[Mean[clusters[[i]]]], {i, 5}]]

结果是:

 START  END
{"10", "15"},
{"12", "17"},
{"14", "17"},
{"11", "15"},
{ "7",  "9"}

这正是我们"怀疑"的原因:每天都有重复的事件可以同时组合在一起.

编辑:隔夜转移和标准化

如果你有(或计划有)从一天开始并在下面结束的轮班,那么建模更好

{Start-Day Start-Hour Length}  // Correct!

比

{Start-Day Start-Hour End-Day End-Hour}  // Incorrect!  

这是因为与任何统计方法一样,变量之间的相关性必须明确,否则方法会失败.原则可能会像"保持候选人数据规范化"之类的.这两个概念几乎相同(属性应该是独立的).

---编辑结束---

到目前为止,我猜你很清楚,如果分析你可以用这种方法做什么.

一些参考

1. 当然,维基百科,其"参考"和"进一步阅读"都是很好的指南.
2. 这里有一个很好的视频,展示了Statsoft的功能,但是你可以通过算法了解其他许多想法.
3. 以下是所涉算法的基本解释
4. 在这里你可以找到R for Cluster Analysis 的令人印象深刻的功能(R是一个非常好的选择)
5. 最后,在这里您可以找到一长串用于统计的免费和商业软件,包括群集.

HTH!