Soo*_*Soo 7 c++ algorithm median
我想编写一个 C++ 函数来查找循环数据数组的中位数。例如，考虑指南针的读数，其中读数假定在 [0,360) 内。虽然 1 和 359 看起来很远，但由于读数的循环性质，它们非常接近。
求普通数据中 N 个元素的中位数如下。1. 对 N 个元素的数据进行排序（升序或降序） 2. 如果 N 为奇数，则中位数为排序数组中的第 (N+1)/2 个元素。3.如果N是偶数，中位数是排序数组中第N/2和第N/2+1个元素的平均值。
然而，循环数据中的环绕问题将问题带到了不同的维度，并且解决方案并不简单。
这里解释了从循环数据中查找平均值的类似问题如何计算一组循环数据的平均值？ 上面链接中的建议是找到每个角度对应的单位向量并求平均值。然而，中位数需要对数据进行排序，而向量排序在这种情况下没有任何意义。因此，我认为我们不能使用提议的方案来找到中位数！
事实上，我对这个话题的思考超出了健康的范围，所以我将在这里分享我的想法和发现。也许有人会遇到类似的问题并发现这很有用。
我已经很多年没有使用过 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，则减去它们之前的距离并添加新的正确距离。
为了将当前总和与最佳总和进行比较，我添加了一些容差以防止不精确的浮点运算。
可能存在多个或无限多个满足最小距离条件的点。对于具有偶数个值的非循环中位数，中位数可以是两个中心值之间的任何值。它通常被认为是这两个中心值的平均值，所以我对这个中值算法采取了类似的方法。我找到所有使距离最小化的数据点，然后计算这些点的圆形平均值。
// Requires a sorted list with values normalized to [0,period).
// Doing an initialization pass:
// * candidate is the lowest number
// * finding the index where the circle with this candidate starts
// * calculating the score for this candidate - the sum of absolute distances
// * counting the number of values to the left of the candidate
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];
// A formula for correcting the distance given the movement to the right.
// It doesn't take into account that some values may have wrapped to the other side of the circle.
++leftCount;
distanceSum += (2 * leftCount - list.Count) * (candidate - previousCandidate);
// Counting all the values that wrapped to the other side of the circle
// and correcting the sum of distances from the candidate.
if (i <= circleStart)
while (list[circleStart] < candidate + period / 2)
{
--leftCount;
distanceSum += 2 * (list[circleStart] - candidate) - period;
++circleStart;
if (circleStart == list.Count)
{
circleStart = 0;
break; // Letting the next loop continue.
}
}
if (i > circleStart)
while (list[circleStart] < candidate - period / 2)
{
--leftCount;
distanceSum += 2 * (list[circleStart] - candidate) + period;
++circleStart;
}
// Comparing current sum to the best one, using the given tolerance.
if (distanceSum <= bestDistanceSum + equalityTolerance)
{
if (distanceSum >= bestDistanceSum - equalityTolerance)
{
// The numbers are close, so using their average as the next best.
bestDistanceSum = (bestCandidates.Count * bestDistanceSum + distanceSum) / (bestCandidates.Count + 1);
}
else
{
// The new number is significantly better, clearing.
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 到 259 的数字向量），创建两个新向量，我将它们称为x和y。这两个新向量分别是角度数据点的正弦和余弦。
也就是说，x[n] = cos(data[n])你的角度数据向量在y[n] = sin(data[n])哪里，无论有多少个数据点。datan
接下来，将向量中的所有值相加以x获得单个值，称之为 saysum_x并将向量中的所有值相加以y获得另一个单个值，称之为sum_y。
现在您可以执行正切逆运算（例如atan(sum_y/sum_x)）来获得新值。而这个值是非常有意义的。该值基本上告诉您数据“指向”哪个方向，即大部分数据存在的位置。注意：除以 0（当sum_x=0 时）和出现不定形式（当同时sum_x=0 和sum_y=0 时）时，必须小心。不定形式只是意味着你的数据是均匀分布的，在这种情况下中位数没有意义，当sum_x=0 但sum_y!=0 时，它实际上是atan(inf)或atan(-inf)，两者都是已知的。
编辑：
在这一点之后，我之前的答案需要一些调整。
从这里开始，这很容易。取您在上一步 ( ) 中获得的值atan(sum_y/sum_x)，并将该值加上 180 度。这是数据开始和结束位置的参考点。从这里，您可以以此参考点作为起点和终点对角度数据进行排序，并找到该数据的中位数。