我其实对这个主题考虑得比健康的多,所以我会在这里分享我的想法和发现。也许有人会遇到类似的问题,并从中受益。
我很多年没有使用C++了,所以如果我用C#编写所有代码,请原谅我。我相信流利的C++使用者可以很容易地将算法转换过来。
平均角度
首先,让我们定义
平均角度。它是通过将您的点转换为弧度计算得出的,其中您的周期(256、360或任何值 - 被解释为与零相同的值)被缩放为
2*pi
。然后,计算这些弧度值的正弦和余弦。这些是您在单位圆上的值的y和x坐标。然后您将所有的正弦和余弦相加,并计算atan2。这给出了平均角度,可以通过除以缩放因子轻松地转换回您的数据点。
var scalingFactor = 2 * Math.PI / period;
var sines = 0.0;
var cosines = 0.0;
foreach (var value in inputs)
{
var radians = value * scalingFactor;
sines += Math.Sin(radians);
cosines += Math.Cos(radians);
}
var circularMean = Math.Atan2(sines, cosines) / scalingFactor;
if (circularMean >= 0)
return circularMean;
else
return circularMean + period;
边缘圆中位数
计算圆中位数的最简单方法是修改计算圆平均值的方式。
可以通过寻找正弦和余弦的中位数而不是总和,然后计算其atan2来计算圆中位数。这样,您就可以找到圆点的边缘中位数并将其角度作为结果。
var scalingFactor = 2 * Math.PI / period;
var sines = new List<double>();
var cosines = new List<double>();
foreach (var value in inputs)
{
var radians = value * scalingFactor;
sines.Add(Math.Sin(radians));
cosines.Add(Math.Cos(radians));
}
var circularMedian = Math.Atan2(Median(sines), Median(cosines)) / scalingFactor;
if (circularMedian >= 0)
return circularMedian;
else
return circularMedian + period;
这种方法是O(n),鲁棒性强,实现非常简单。它可能足够适合您的目的,但它有一个问题:旋转输入点会给出不同的结果。根据您输入数据的分布,这可能是一个问题或不是一个问题。
圆弧中位数
为了理解这个其他方法,您需要停止以“这就是如何计算”为思考均值和中位数,而是从结果值实际代表的角度来思考。
对于非循环数据,通过将所有值相加并除以元素数量获得平均值。然而,这个数字所代表的是与数据元素的所有平方距离之和最小的值。(我听到统计学家称这个值为L2位置估计,但一个统计学家应该确认或否认这一点。)
同样地,对于中位数。通过找到在所有数据排序后处于中间位置的数据元素来获得它(理想情况下,使用O(n)的选择算法,如C++中的nth_element)。然而,这个数字是一个具有最小绝对距离和的值(非平方!)到数据元素。(据说,这个值被称为L1位置估计。)
对于循环数据进行排序无法帮助您找到中间位置,因此通常思考中位数的方法不起作用,但是您仍然可以找到最小化与所有数据点的绝对距离之和的点。以下是我想出的算法,假设输入数据已归一化为>= 0且<周期,然后排序,时间复杂度为O(n)。(如果您需要将此排序作为计算的一部分进行,则运行时间为O(n log n)。)
它通过遍历所有数据点并跟踪距离总和来工作。当你将右侧的数据点向右移动D距离时,所有左侧点到原点的距离总和增加了
D*LeftCount
,而所有右侧点到原点的距离总和减少了
D*RightCount
。然后,如果一些左侧点现在实际上是右侧点,因为它们的左侧距离大于
period/2
,则会减去它们的先前距离并添加新的正确距离。
为了将当前总和与最佳总和进行比较,我添加了一些容差以防止不精确的浮点运算。
可能存在多个或无限多个满足最小距离条件的点。对于具有偶数个值的非循环中位数,中位数可以是两个中心值之间的任何值。通常取这两个中心值的平均值,因此我采用了类似的方法来计算这个中位数算法。我找到所有最小化距离的数据点,然后只计算这些点的圆形平均值。
int i;
var candidate = list[0];
var distanceSum = 0.0;
for (i = 1; i < list.Count; ++i)
{
if (list[i] >= candidate + period / 2)
break;
distanceSum += list[i] - candidate;
}
var leftCount = list.Count - i;
var circleStart = i;
if (circleStart == list.Count)
circleStart = 0;
else
for (; i < list.Count; ++i)
distanceSum += candidate + period - list[i];
var previousCandidate = candidate;
var bestCandidates = new List<double> { candidate };
var bestDistanceSum = distanceSum;
var equalityTolerance = period * 1e-10;
for (i = 1; i < list.Count; ++i)
{
candidate = list[i];
++leftCount;
distanceSum += (2 * leftCount - list.Count) * (candidate - previousCandidate);
if (i <= circleStart)
while (list[circleStart] < candidate + period / 2)
{
--leftCount;
distanceSum += 2 * (list[circleStart] - candidate) - period;
++circleStart;
if (circleStart == list.Count)
{
circleStart = 0;
break;
}
}
if (i > circleStart)
while (list[circleStart] < candidate - period / 2)
{
--leftCount;
distanceSum += 2 * (list[circleStart] - candidate) + period;
++circleStart;
}
if (distanceSum <= bestDistanceSum + equalityTolerance)
{
if (distanceSum >= bestDistanceSum - equalityTolerance)
{
bestDistanceSum = (bestCandidates.Count * bestDistanceSum + distanceSum) / (bestCandidates.Count + 1);
}
else
{
bestDistanceSum = distanceSum;
bestCandidates.Clear();
}
bestCandidates.Add(candidate);
}
previousCandidate = candidate;
}
if (bestCandidates.Count == 1)
return bestCandidates[0];
else
return CircularMean(bestCandidates, period);
几何圆中位数
在先前的算法中存在一些不一致之处,即中位数与圆平均值之间的定义方式。圆平均值将欧几里德距离的平方和最小化,即它看着连接圆上点的直线,穿过圆。
如我上面所计算的弧中位数,它看着弧距离:通过在圆的周长上移动来确定点之间的距离,而不是通过它们之间的直线。
如果这个问题困扰你,我已经考虑了如何解决它,但我还没有进行任何实验,因此无法声称以下方法有效。简而言之,我相信您可以使用迭代重新加权最小二乘算法(IRLS)的修改版本,这通常用于计算几何中位数。
这个算法的思路是选择一个起始值(例如上面提到的圆形平均值或弧中位数),并计算到每个点的欧几里德距离:Di = sqrt(dxi^2 + dyi^2)。圆形平均值将最小化这些距离的平方,因此每个点的权重应该抵消平方并重置为只有D:Wi = Di / Di^2,即Wi = 1 / Di。
使用这些权重,计算加权圆形平均值(与圆形平均值相同,但在对它们求和之前将每个正弦和余弦乘以该点的权重)并重复此过程。重复直到足够多的迭代已经过去或者结果变化不大为止。
这个算法的问题是,如果当前解恰好落在数据点上,则会出现除以零的情况。即使距离不是完全为零,如果你靠近点,解也会停止移动,因为权重将与所有其他权重相比变得巨大。这可以通过在除以距离之前添加一个小的固定偏移量来修复。这将使解不是最优的,但至少它不会停在错误的点上。
“除非偏差相对较大,否则仍需要进行若干次迭代才能使其摆脱错误点,并且最终解决方案的偏差越大,结果就越糟糕。因此,最好的方法可能是从一个相当大的偏差开始,然后逐步减小每个下一次迭代的偏差。”
[0 180]
,其中90
和270
都同样适用... 或者对于[0 60 120 180 270]
,存在 5 种可能的解决方案,即使是“最小间隔”条件也无法帮助唯一选择其中一个。 - 463035818_is_not_a_number