用于周期现象的聚类技术

摘要

一种数据处理系统处理集体描述在一个物理过程中的几个实体中的至少一个变量的周期行为的数据组。每个周期包括几个时隙。输入例程(2－4)接收多个数据组，每个数据组包含多个数据项，每个数据项描述在一个时隙中的实体的变量。幅度确定例程(2－6)为几个实体的每一个确定诸如平均值、量值或峰值这样的具体幅度参数。定标例程(2－8)定标实体间的数据组，使具体幅度参数受到抑制并只保持其形状。训练例程(2－10)用第一多个定标的数据组训练聚类系统，以确定一组聚类中心。训练后，聚类例程(2－12)将第二多个定标的数据组施加到受训练的聚类系统。

说明书

技术领域

本发明涉及一种用于周期现象的聚类技术。例如，本发明可用于处理集体描述在一个物理过程中的几个实体的一个或多个变量的周期行为的数据组。

背景技术

聚类技术，诸如K-均值算法、分层聚类技术、自组织映射等，已广泛用于分析物理过程的变量行为。为了提供一个具体的但非限制性的示例，该物理过程可以是一个蜂窝电信网络的运作过程，其中几个实体中的每一个可以是该网络的小区或一些其它资源，而一个或多个的变量可以是性能指示符，例如业务量、资源使用，丢失的连接数目(或百分数)等。

现有的聚类技术存在着忽略了大量有用信息的缺点。

发明内容

本发明的目的是为了提供一种方法和实施该方法的装置，用以克服上述缺点。本发明的目的是通过具有独立权利要求中描述的技术特征的方法和设备来实现的。本发明的优选实施例公开在从属权利要求中。

本发明是基于这样一个发现：现有聚类技术将变量视为绝对量。在电信网络的环境下，这是可理解的，因为例如网络是受诸如业务信道数目这样的物理资源制约的，不能超过该数目。于是自然要考虑物理资源是否被超过的反常的情况。但正是这种将变量视作绝对值的观测使得大量有用的信息被浪费掉了。因此，本发明部分地基于如下的构思：小实体的周期行为可以类似于如果绝对值受抑制的大实体的周期行为。上述构思可以由用于处理集体描述在一个物理过程中的几个实体中的至少一个变量的周期行为的数据组的方法来实现。该方法包括下列步骤：

1.确定在周期行为中的第一周期，并将该第一周期分成多个时隙；

2.确定多个数据组，每个数据组包含多个数据项，使得每个数据项描述在一个时隙中的实体的变量；

3.为几个实体的每一个实体确定具体幅度参数；

4.定标实体间的数据组，使得具体幅度参数得以抑制；

5.用第一多个所定标的数据组训练聚类系统以确定一组聚类中心；以及

6.使用该受训练的聚类系统来聚类第二多个所定标的数据组。

为了更好地理解上述步骤，我们仍将以蜂窝电信网络为例进行说明。但读者要记住，这只是非限制性的示例和只用以阐明本发明的各要素之间的关系。

在步骤1中，如果物理过程是一个电信网络，则第一周期通常是24小时时段以及时隙通常为小时。24小时时段是由网络用户的生活节奏确定的，但1小时的时隙只是方便的选择而已，因为人类习惯于用小时计时。但就计算机而言，任何大小的时隙都是可行的，而且时隙也并非要求长度相等。例如，在平静时段期间(通常是夜晚)时隙可以比高活动时段期间较长。术语“第一周期”意味着：可以有进一步的周期，诸如具有一天一个的七个时隙的一周的周期。

术语“周期”应该以如通常在统计上的实际世界现象的环境下那样宽的意义上去理解。性能指示符是周期性的事实并不意味着在任何两个周期之间性能一样。该性能指示符总体上表明有一个周期地重复的模式：给定多个周期的每个周期的任何两个大取样时段，在这些时段上的性能趋于相似。然而，会出现差别，以及许多聚类系统的目的是确定是否这些差别代表了系统故障、欺诈的用户行为或其它异常。

在步骤2中，每个数据项描述在一个时隙中的实体的变量。例如，每个数据项可以描述具体时隙期间在蜂窝电信网络中的小区的性能指示符。通常，性能指示符在该时隙上被求和或被平均。数据组是在该周期上的数据项的集合。例如，如果时隙为一小时时段，则数据组可以是集体覆盖24小时时段的一组(例如一个阵列)24个取样值。如果将数据组想象为一条曲线，则它有确定形状和幅度(大小)。

在步骤3中，为每个实体确定具体幅度参数。在步骤4中，在实体间定标数据组，使得具体幅度参数受到抑制。幅度参数是可用来抑制绝对量而使之只保持形式的任何数学量。定标操作使大的和小的实体彼此相互兼容。换句话说，由聚类来自实体的数据所获得的信息可用于聚类来自另一个实体的数据，而不管实体的大小如何。(在这种情况下，“大小”是指诸如业务量这样的其性能指示符的幅度，而不是其地理尺度)

在步骤5中，用第一多个定标的数据组训练聚类系统以确定一组聚类中心。除了数据组的定标是如关于步骤3和4中所描述的那样以外，训练步骤可以完全是常规的。虽然下面要描述一些优选的聚类技术，但为常规的聚类系统意味着本发明并不需要任何具体的聚类系统或不依赖于任何具体的系统。

在步骤6中，在步骤5中受训练的聚类系统用于聚类第二多个定标的数据组。再一次，从纯粹数学的观点看，使用受训练的聚类系统的步骤完全可以是常规的，但正如下面要描述的，本发明的用定标的数据组抑制实体间的幅度的构思打开了通向新颖应用之路。

本发明的优点是：因为诸如性能指示符这样的变量不受限于给定大小的实体，所以可从物理过程获得更多有用的信息。通过在聚类前执行定标操作，使本发明的技术与常规的聚类技术相兼容。

本发明可用于几种应用。例如，利用本发明的方法所聚类的和所定标的数据组可用于检测反常情况。在另一个应用中，定标的数据组用于确定定价策略。在再一个应用中，定标的数据组被用于确定网络资源的最佳运行参数，该参数然后被复制到另一个网络资源。另外，本发明的技术可用于检测其特征数据(profile)紧密匹配于某些样板客户但其业务的使用不同于该样板客户的订户。该信息可用于将该所检测客户作为业务广告的目标。

根据本发明的优选实施例，对使用第一周期所聚类的数据组通过使用第二周期进行再聚类，该第二周期为多个第一周期。例如，具有第一周期的数据组可以代表网元或网络资源的日常行为，而用第二周期再聚类的数据组代表在几年内的日常行为的进展。

根据本发明的另一个优选实施例，该聚类系统是无监的聚类系统。使用无监聚类系统的好处是无需聚类中心的先验知识便可发现聚类中心。然而，如果有关于聚类中心的先验的信息，通常称之为“种子值”，则用该种子值初始化该无监聚类系统是有益的。

可以以新颖的方式使用通过本发明的处理获得的信息。在详细描述这些应用领域以前，让我们引入一些有助于使下面的描述更为精炼的术语。聚类系统将处理数据组并产生一组聚类中心。可以方便地将术语“原型”用于描述聚类中心的数据组。一个具有其各自指示符的原型的集合称为码本。使用码本带来若干好处。例如，我们可从码本选择最佳匹配的原型并只存储该最佳匹配的原型的指示符，而用不着归档某个时隙期间实体的行为，作为完整的数据片段(例如每天24个独立样本)，这样显然节省了大量的存储空间。因此，本发明在归档数据方面是有用的。

一个数据组与码本中的原型精确相同的情况即使发生也是罕见的。这就是为何定义置信区间使得可以检测从最佳匹配原型的大偏差是有益的原因。在一个数据组偏离最佳匹配原型大到越出置信区间的情况下，则归档整个数据组而不仅仅归档原型指示符是有益的。一个更好的选择是归档最佳匹配原型指示符和性能指示符超出置信区间的时隙以及归档在这些时隙中的实际(或定标的)数据值。下面要讨论用于确定置信区间的优选技术。

除了在数据归档中提供优越性以外，码本概念对数据分析也是有用的。例如，确定是否两个实体行为为相似或几乎相似的方式远非易事，特别是如果两个实体间的性能指示符的幅度不同时。如果相似性的检测是基于码本的原型指示符的分析，则检测实体间的相似行为是相对便捷的任务。

在某些实施例中，本发明可用于从可观测的变量的历史来恢复丢失的值，诸如在网络资源中的数量。如果我们只知道过去的该变量的日、周或月平均值，则可以通过外插当前的小时行为来得到该变量的每小时行为的合理估计。当前的每小时的行为可以从同一实体或其紧密匹配原型确定。

在聚类系统的环境中众所周知，本发明可以实施为编程的数据处理系统。可以由计算例程实现与现有技术的主要不同之处，即实现对观测的实体或变量的具体幅度参数的抑制。类似地，可以由计算例程确定在某些实施例中使用的置信区间。可以作为适当配置的数据库系统来实施这样一个实施例，使其在满足置信区间准则时，只归档最佳匹配原型指示符而将全部数据丢弃或移至第二存储器。

附图说明

下面将参照附图利用优选实施例更详细地描述本发明，其中：

图1是一个说明用于异常检测的聚类系统的方框图；

图2一个说明本发明的原理的流程图；

图3示出了被定标用以抑制不同大小的实体的幅度参数的四个聚类中心；

图4A和图4B示出了两个示例性的特征数据描述符；

图5示出了一个用于四个不同的每周聚类的概率分布；

图6说明存储观测结果的优选技术；

图7示出了一种异常情况；

31图8说明的用于归档数据的数据结构，其中容许有异常情况；和

32图9说明用于确定置信区间的优选技术。

具体实施方式

本发明可以用于若干应用。一个示例性的示例是处理异常情况。图1是一个说明用将诸如神经网络的聚类系统用于异常检测的方框图。参考数字102表示一个诸如电信网络(有别于一个神经网络)的物理系统的单元。物理单元可包括几个可观测的变量。例如，如果物理系统单元102是一个电信交换机，则其可观测的变量可包括吞吐量，等待时间，失败呼叫数(或百分数)等。指示符收集器106为每个时间单位收集指示符元组104。将该元组存储在指示符数据库110中。参考数字112表示用于训练神经网络114(或另一个学习机制)的数据组。该数据组112应该指示物理单元102的正常行为。存储器118包含受训神经网络。当物理单元102被观测时，从存储器118检索出相应的受训神经网络120并将其作为一个输入施加到异常检测机制122。异常检测机制的其它输入是用于测试异常行为的指示符组124。如果异常检测机制122判断到由指示符组124描述的行为是异常的，则异常P值和最偏离的指示符126被存储在异常历史数据库128中。同时，向诸如计算机屏幕这样的监视设备132给出一个告警130。

图2是一个说明本发明原理的流程图。步骤2-2是准备步骤，用来确定周期(或多嵌套周期)、时隙(诸如小时、天、周……)、实体(诸如物理网络资源)和待观测的变量(诸如吞吐量、丢弃呼叫数、切换数、短消息数等)。步骤2-4是另一个准备步骤，用来为可观测的变量确定数据组。例如，假设可观测变量之一为在小区中的切换数并且假设每个时隙为一小时而周期为24小时时段，则方便地将每个数据组描述为24个数据项(数)的矢量，而各个数据项描述在相应小时期间的切换数。

步骤2-6包括为每个实体确定具体幅度参数。一个具体幅度参数的优选类型是在一个周期上的和(积分)或平均值。假设将平均值用作为具体幅度参数，则每个实体的数据组(矢量)将被该实体的平均值相除，使得在该周期上，描述每个实体的数据项的平均值是相等的。换句话说，实体的具体幅度参数将受到抑制。这发生在步骤2-8中。接着，在步骤2-10中，利用定标的数据组的第一组(训练的一组)训练一个聚类系统。本步骤完成了聚类系统的准备和训练阶段。聚类系统的实际使用发生在步骤2-12中，除了通过抑制实体的具体幅度参数来定标数据组这点以外，本步骤可以是常规的。

使用平均值作为具体幅度参数的示例性好处在于：图1中所示出的并经来自任意实体的观测数据训练的异常检测系统，可用来检测在其它的具有相当大或相当小的容量的实体中的异常。

图3示出了4个聚类中心31-34，这些聚类中心被定标以抑制不同大小的实体的幅度参数。在该示例中，聚类中心是24单元矢量的图形表示，其中每个矢量代表了诸如网络小区内的业务量这样的物理资源的日常行为。由图3显而易见，本发明从实体的幅度提取了其行为的形状。每个矢量的平均值是一样的。这也意味着，由矢量的图形表示所覆盖的区域是相等的。换句话说，因为每个矢量的周期长度是相同的，所以用矢量的面积或积分作为幅度参数与用其平均值在数学上是等同的。

图4A示出了诸如物理资源这样的实体的示例性的特征数据40。再假设，物理资源是网络的小区以及可观测变量是业务量。最左一列表示周中的天，这样星期一是“1”，星期日是“7”。聚类数1到4是指图3中所示的4个聚类中心。在该示例中，特征数据40表明，就所讨论的小区而论，聚类4对星期一至星期四和星期日是最佳行为指示符。其它聚类成为最佳行为指示符的概率是可忽略的，这意味着，概率可能不正好为零，但实用上可以被忽略。同样，如特征数据40的最后一行所示，聚类3最好地表示了所有的星期六。然而，对所有的星期五则不同，聚类1最好地表示了它们的83％，而聚类4最好地表示了它们的余下的17％。

图4B示出了一个更为详细的每周特征数据45。概率列内的短线表示了小到可以忽略的值。该示例说明，聚类4在实际意义上最好地代表了所有的星期一(天数为1)，而聚类4只有30％的概率成为星期五的最佳描述符，聚类1则有70％的概率，等等。

图5示出了4个已知的每周聚类的概率分布50。在该示例中，我们有4个可选择的周特征数据和4个聚类中心(诸如其图形表示如图3所示的那些聚类中心)。为保持概率分布表50紧凑，该表各以百分之十的单位表示概率。例如，为4的条目表示40％。该概率分布50表明：在周特征数据1中，聚类1和2分别有20％或80％的概率成为星期一的最佳表示。在该特征数据中，剩下的聚类3和4的概率是可以忽略的。在周特征数据2中，聚类1和4分别有70或30的概率成为星期一的最佳表示，而剩下的聚类2和3的概率则可忽略，等等。

利用概率分布50，通过将一个周期上的平均变量值与该变量的估计的特征数据形状相乘，可以计算出每小时估计。

周特征数据40，45和/概率分布50可有若干应用。例如，可以用来在归档观测数据时减少存储器消耗。取代为每个24小时周期归档作为24个绝对值的观测数据，我们可以用该小区和周期的具体幅度参数(诸如平均值)来定标(除以)该绝对值并在定标后检查是否该实体的行为对应于预定的特征数据之一。如果对应于预定的一个特征数据，则归档那个24小时时段的具体幅度和特征数据数就足以了，这本身就大大减少了存储器消耗。

周特征数据40，45和/或概率分布50的另一个应用是改进了预测。通过抑制实体间幅度差别并将注意力集中在特征数据形状上，则有可能使用从任意幅度的实体获得的信息，假设实体具有相似的特征数据形状。

另一个应用是“预测过去”。这意味着，例如，我们可能只知道过去某个时刻的变量的平均值。利用知道其当前的特征数据形状，就有可能估计作为时间函数的该变量的过去的行为。

图6和图7说明一种归档观测结果的优选技术。如在此所用那样，“归档”意味着这样一种技术：将某些相关的数据存储一段时间(通常数年)，而丢弃不相关的数据或将其移存到便宜的、通常是脱机的存储器中。换句话说，归档包括判断存储什么、丢弃什么，以便减少存储器消耗。

图6是一个归档方法的流程图。步骤6-2是准备步骤，确定并存储用于所观测实体的具体幅度参数。该步骤类似于图2中的步骤2-6。步骤6-4包含获取所观测的变量的数据组，诸如每24小时的业务量矢量。在步骤6-6中，利用用于所观测实体的具体幅度参数来定标数据组。在步骤6-8中，用训练过的聚类系统处理所定标的数据组，以找到其最佳匹配聚类中心。在步骤6-10中，确定所定标的数据组偏离最佳匹配聚类中心是否在一个预定置信区间内。如果是，则执行步骤6-12，在该步骤中只存储(归档)最佳匹配聚类中心的指示符，而将实际的数据组丢弃或存储到第二存储器。另一方面，如果所定标的数据组与最佳匹配中心的偏离不在预定的置信区间内，则执行步骤6-14，在该步骤中以定标的或未定标的形式存储(归档)完整的数据组。通过归档最佳匹配聚类中心的指示符、样本偏离最佳匹配聚类中心而落在预定置信区间之外的时隙以及在这些时隙内的实际样本值，可以更有效的使用归档存储器。

图7示出了一种异常情况。曲线71示出了例如网络资源的物理实体的实际定标的观测结果。曲线72示出了最佳匹配原型(聚类中心)。除了在15:00，16:00和17:00的3个观测结果之外，该实际观测结果71在24小时周期的大部分时间是在预定置信区间73内的。

图8示出了用于存储观测结果的优选的数据结构80。该数据结构80包含对一个实体和一个变量的观测结果的历史。列81是周期的运行数，诸如24小时时段。包括了实际观测结果的数据组通过除以具体幅度参数82被定标。然后，用受训后的聚类系统聚类所定标的数据组。观测结果历史80示出了连续11天的条目。一天(或任何其它采用的周期)的条目包括最佳匹配聚类中心83以及指示所定标的数据组是否在预定置信区间内，即是否与最佳匹配聚类中心偏离小于某个置信量的标志84。

对大多数的天而言，聚类中心2是最紧密的匹配。对第7和8天，聚类中心3和1分别是最佳的匹配。然而，对第10天，我们假设实际的观测结果是遵循图7的曲线81。换句话说，除了从15:00点开始的三个连续的观测结果外，实际的观测结果是在最佳匹配原型(聚类中心)数2(如曲线82所示)的置信区间83之内的。于是，83列和第10天的条目表明聚类中心2是最佳匹配，但在84列的标志示出了所定标的观测结果在整个周期内是不在置信区间内。有一个实际的第10天观测结果记录85。实际的观测结果记录85表明：在第10天，从15:00点开始，对3个连续小时的观测结果是123，15和192。

如果诸如24小时时段这样的周期的所有的所定标的观测结果是在置信区间内，则只有3个描述符，即幅度(浮点数)、最佳匹配聚类中心(整数)和标志84必须要归档。

其它应用

本发明的应用并不限于处理异常情况。在本发明一个优选实施例中，创建了一个用于客户和由客户使用的服务的数据结构。该想法是要将客户具有几乎类似的服务分布的客户聚类在一起。该实施例采用了码本概念。由任何给定客户使用的服务组构成了一个数据组(矢量)。该数据组然后被聚类以找出聚类中心，在此情况下，聚类中心是其服务组合很流行的原型客户。任何给定的客户从最紧密匹配的原型客户的偏离代表了由这些客户使用的服务组中的差别。该信息可用于向还没有使用这种服务的客户提供服务。在电信网中，可以通过网络本身提供这种服务。

提供服务的基于聚类技术比起蛮力技术节省了诸如网络资源这样的资源，蛮力技术涉及对尚未使用某些服务的客户进行简单的数据库扫描。聚类技术节约资源的方面是源于：如果原型客户使用流行的服务组合A、B、C和D，而另一个客户使用服务A、B和C，则该客户比使用服务A、X、和Y的客户将更是服务D的可能的潜在目标。另一方面，蛮力技术因“盲目地”提供服务而浪费了网络和其它资源。也就是说，这种技术并没有考虑客户是否接近于但非等同地匹配于原型客户。

在本发明另一个实施例中，创建了用于客户及其小时服务使用特征数据的数据结构。该实施例可用于在当收费改变时优化时间。因为本发明使来自不同大小的实体的信息等同，所以这样的收费改变的优化可利用来自任何大小的实体的信息。

取代在当收费改变时使用本发明来优化时间，或在此之外，本发明可用于优化所观测实体的其它操作参数。例如，网络运营商可以从一个优化的实体将一组参数复制到一个未优化的实体，而不管该实体的大小如何。本实施例涉及创建活动形态码本(activity shapecodebook)和聚类实体的日常行为。例如，在一个蜂窝网络中，要优化的参数可以包括频率复用模式、服务间的带宽分配等等。

本发明的另一个实施例包括数据结构，用于为异步服务优化传输时间。可以期望蜂窝网将会越来越多地用于以多媒体文件的形式传递“信息”。网络运营商可以使用本发明来优化用于传输的传输时间。该网络可通过将文件传递安排到具有低预期负荷的未来时隙来实施负荷平衡。利用估计的负荷特征数据来识别最佳时隙。利用聚类的客户分类可影响选择，使得某些客户愿意承受较长时间的延迟。该网络应当能向该客户指明延迟时间的估计。

本发明也用于优化服务的时序安排。因为在抑制具体幅度后，来自小的或大的实体的信息是很大程度等同的，所以网络或服务运营商可得到的信息量要比未经具体幅度抑制可能得到的信息量更大。运营商可以用这一信息最佳地安排服务运行。例如，网络维护系统可从网元接收检索数据记录的请求。该系统可以检查估计的业务量特征数据形状并在业务量峰值之外安排请求的记录检索(或其他维护操作)。

置信区间

下面讨论用于确定置信区间或置信界限的优选技术。例如，一个与其最紧密匹配原型(聚类中心)偏离超过预定置信界限的变量值可被称为异常或意外。

置信界限通常计算为K·σ，其中σ是变量的标准偏差，K是表示要求的置信水平的覆盖系数。对于正常地分布的数据，K＝1.96意味着一个95％的置信水平。覆盖系数2和3是常常使用的而与基础分布无关。

根据本发明的一个优选实施例，对每个聚类和时隙独立计算标准偏差σ。以在08:00的聚类数1为例。将属于聚类1的日特征数据集合在一起。然后，从这些特征数据计算出08:00时的标准偏差值。

现在的构思是要定标置信界限，以便对源自具有较高平均变量值的实体的特征数据获得一个较为严格的置信界限。这可以由下式来完成：

         k_var＝k·f(mean(var))               (1)

在等式1中f是一个递减函数(单调或阶跃函数)，而mean(var)是周期上的变量平均值，例如，24小时周期内的小区的业务量的平均值。单调递减函数的优选版本是如下所示的每个周期(例如一天)的平均值的平方根倒数：

$$ >{}_{}$$

由此获得每个周期的不同变量相关覆盖系数。于是，可将置信界限表示如下：

        conf_level＝μ±k_var·σ                    (3)

这里，μ是具体时隙中聚类的平均值，其中聚类也是由K-均值聚类给定的聚类中心，而σ是如上所述的在聚类内数据的标准偏差。

图9示出了由等式2确定的置信界限的应用。Y轴代表变量(性能指示符)的定标值，X轴代表0-4的定标上的日平均值，在此例中该平均值是2。黑圈91代表观测结果。水平线92描述固定的置信界限，例如正/负两倍该标准偏差。

曲线93示意性地(但非精确地)说明了由等式2确定的置信界限，其中由置信界限定义的置信区间随着幅度参数的增加而逐渐(本例为渐近地)变窄。例如，观测结果94是在渐减的置信区间93内，但不在固定的置信区间92内。另一方面，观测结果95是在渐减的置信区间93之外，但在固定的置信区间92内。假设该变量描述小区内的业务量，则渐减置信区间93意味着当业务平静时可比较为活动的小区容许有较大的成比例的偏差。例如，在农村的平静的小区，通常每小时，譬如说只有10次呼叫。如果有人与故障的移动电话进行了三次失败的呼叫尝试，这不一定是异常，而100个电话中30个失败的呼叫尝试，则是十分严重的异常。

本领域的技术人员显然清楚，随着技术的进步，本发明的构思可以用各种方式实施。本发明及其实施例并不局限于上述示例，而是可以在权利要求书的范围内变化。