标签: approximation

我正在为数百万个50-1000维点设计一个凝聚的,自下而上的聚类算法.在我的算法的两个部分中,我需要比较两个点的集群并决定两个集群之间的分离.的精确距离是接管点P1-P2的所有对,其中P1是从集群C1取出并P2从集群C2拍摄的最小欧几里得距离.如果C1具有X点且C2具有Y点,则这需要X*Y距离测量.

我目前估计这个距离需要X + Y测量:

1. 找到簇C1的质心Ctr1.
2. 在群集C2中找到最接近Ctr1的点P2.(Y比较.)
3. 在C1中找到最接近P2的点P1.(X比较.)
4. 从P1到P2的距离是簇C1和C2之间距离的近似度量.它是真实价值的上限.

如果簇是大致球形的,这非常有效.我的测试数据由椭球高斯簇组成,因此效果很好.但是,如果簇具有奇怪的,折叠的,弯曲的形状,则可能产生差的结果.我的问题是:

是否存在使用甚至少于X + Y距离测量的算法,并且在一般情况下产生良好的精度？

要么

是否有一种算法(像我的一样)使用X + Y距离测量,但提供的精度比我的更高？

(我在C#中对此进行编程,但是伪代码或任何其他语言的算法描述都很好.请避免使用R或Matlab中的专用库函数.具有概率保证的算法,如"距离的95%几率"在最小值的5%范围内"是可以接受的."

注意:我刚刚发现了这个相关的问题,它讨论了类似的问题,但不一定是针对高维度的问题.给定两个(大)点集,我如何有效地找到彼此最近的对？

注意:我刚刚发现这被称为双色最近对问题.

对于上下文,以下是整体聚类算法的概述:

1. 第一次通过使用空间填充曲线(希尔伯特曲线)将最密集的区域合并成小的簇.它错过了异常值,并且经常无法合并彼此非常接近的相邻聚类.但是,它确实发现了一个特征性的最大连杆距离.所有以小于此特征距离分隔的点必须聚集在一起.此步骤没有预定义数量的集群作为其目标.

2. 如果它们的最小距离小于最大连杆距离,则第二次通过通过将簇组合在一起来执行单连杆聚集.这不是层次聚类; 它是基于分区的.将组合彼此的最小距离小于该最大连杆距离的所有簇.此步骤没有预定义数量的集群作为其目标.

3. 第三遍执行额外的单链接聚集,对所有簇间距离进行排序,并且仅组合簇,直到簇的数量等于预定义的目标簇数.它处理一些异常值,更喜欢只合并具有大簇的异常值.如果存在许多异常值(通常是异常值),则可能无法减少到目标的簇数.

4. 第四遍将所有剩余的异常值与最近的大型集群组合在一起,但不会导致大型集群与其他大型集群合并.(这可以防止两个相邻的簇意外地合并,因为它们的异常值在它们之间形成一条细链.)

是否有可能找到最接近混合整数问题的解决方案？例如,我想要下面的简化问题:

f = [1;1;1];
intcon = 1:3;

Aeq = [0.99,0.97,0.15];
beq = 0.16;
lb = zeros(3,1);
ub = [1;1;1]; 

x = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub)

返回,x=[0;0;1]因为这是目标值的最接近的整数解0.16.相反,它现在返回

Intlinprog因为没有任何一点满足约束而停止了.

不一定要跑intlinprog.beq例如,如果低,理想情况下也需要工作0.14.

我有一些麻烦解释清楚,但它很简单..

我在我的C++程序中有一个双重命名值,如果它是一个正值,我想要它,如果它是负值,我想要Ceil,精度由外部变量给出.

一个例子:

精度为1000的值为0.2659,因此近似值为0.265,
值为-0.2659,因此近似值为-0.265

我写了一个简单的代码,但我想知道是否有一个更简单或/和方式来做它.

到目前为止我所拥有的:

void NodeImpl::approximation(double& value, const double& precision)
{
    if (value > 0.0)
    {
        value = std::floor(value * precision);
    }
    else
    {
        value = std::ceil(value * precision);
    }
    value /= precision;
}

我写了一个简单的代码,但我想知道是否有一个更简单或/和方式来做它.

我有一个高频运行的控制回路,需要在每个周期计算一个平方根.典型的平方根函数工作正常但需要花费过多时间.由于我采用平方根的值在每个周期上没有太大变化,我想找到一个迭代的平方根,它将收敛然后跟踪正确的结果.这样我就可以在每个时间步进行一次迭代,而不是很多次迭代.

问题是,当输入发生变化时,我看到的所有迭代平方根方法都可能会失败.特别是当输入变为零然后再次增加时,看起来会出现问题 - 方法不喜欢从零开始猜测.

我的输入范围是0-4.5,我需要大约0.01精密所以用的0.01递增/递减可能需要的时间太长了 - 我想这主要是在10次以内收敛.

仅供参考我使用16/32bit定点输入为16bit q12.它在微控制器上,所以我对使用1K查找表不感兴趣.代码也是从simulink模型生成的,它们的表查找功能相当充满了开销.

有一个很好的解决方案吗？

鉴于在RGB中我们可以表示256 ^ 3种组合= 16,777,216种颜色,并且由于人眼只能区分大约10,000,000种,因此显然有6,777,216种RGB组合的过剩,其色彩与对应颜色无法区分.

压缩算法在此基础上工作,当我相信帧中颜色范围的空间差异近似时.考虑到这一点,如何可靠地计算给定颜色是否在与另一个颜色"相似"的范围内？

当然,"相似性"将是某种可以调整的任意/可调参数,但无论如何这都是近似值.那么任何指针,伪代码,直观的代码示例,资源都有帮助我建模这样的功能吗？

非常感谢您的帮助

我正在尝试做一些我认为非常简单的事情：用三次贝塞尔曲线替换 SVG 路径中的所有弧。

这个：http : //www.w3.org/TR/SVG11/implnote.html#ArcImplementationNotes并没有真正帮助我，因为它并没有真正说明转换。

我知道如何制作简单的弧，但 SVG 弧确实有很多参数。

所以我需要的基本上只是一个算法，它需要：

rx ry x-axis-rotation large-arc-flag sweep-flag x y

（也是圆弧的起点）

并计算：

x1 y1 x2 y2 x y

（当然，起点，x 和 y 保持相同的值...）

有人知道这样的事情吗？

提前致谢！:-)

[序幕]

这个Q&A旨在更清楚地解释我在这里首次发表的近似搜索类的内部工作

• 提高超越方程解的精度

我已经被要求提供关于这几次的更多详细信息(由于各种原因)所以我决定写关于这个的Q&A风格主题,我将来可以很容易地参考这个主题并且不需要一遍又一遍地解释它.

[题]

如何逼近Real域(double)中的值/参数以实现多项式,参数函数或求解(困难)方程(如超越)的拟合？

限制

• 真实域名(double精确)
• C++语言
• 可配置的近似精度
• 已知的搜索间隔
• 拟合值/参数不是严格单调的或根本不起作用

我正在使用软件渲染器开发游戏,以获得最准确的PS1外观.当我正在研究PS1图形/渲染系统如何工作,摇摆顶点等的原因时,我偶然发现了一些关于它们划分方式的文档.以下是它的链接:http://problemkaputt.de/psx-spx.htm#gteoverview(参见"GTE Division Inaccuracy"部分)

相关代码:

  if (H < SZ3*2) then                            ;check if overflow
    z = count_leading_zeroes(SZ3)                ;z=0..0Fh (for 16bit SZ3)
    n = (H SHL z)                                ;n=0..7FFF8000h
    d = (SZ3 SHL z)                              ;d=8000h..FFFFh
    u = unr_table[(d-7FC0h) SHR 7] + 101h        ;u=200h..101h
    d = ((2000080h - (d * u)) SHR 8)             ;d=10000h..0FF01h
    d = ((0000080h + (d * u)) SHR 8)             ;d=20000h..10000h
    n = min(1FFFFh, (((n*d) + 8000h) SHR 16))    ;n=0..1FFFFh
  else n = 1FFFFh, FLAG.Bit17=1, FLAG.Bit31=1    ;n=1FFFFh plus …

嗨,我有一个多边形问题.我不知道该找什么,所以我决定在这里问一下.下图显示了一个简单的形状.使用OpenCV的findContours()检测轮廓,并通过CV_CHAIN_APPROX_TC89_KCOS(对于那些想知道如何完成此操作的算法)算法进行近似,以便将一行中的所有点汇总为一行.所以无论如何,一些轮廓包含某种形状,我称之为噪音.下图显示了噪音的含义.红线是轮廓.(抱歉没有油漆技巧)

我的目标是重新定义形状以接近形状,但忽略这种"噪音".所以轮廓应该是这样的.蓝线显示校正的轮廓.

我有一个特定的运动学作为一个更复杂的机器的一部分,需要计算一些非常困难(更不可能)的物理参数,用我可以使用的仪器以适当的精度进行测量

[运动学]

首先看它是一个简单1的自由度臂(黑色),它可以围绕x轴旋转.它有一个重量,迫使它一直向上,直到它达到机械终点(角度a0)或一些半径的管(蓝色)r0.手臂旋转中心位于y0.管可以移动到任何y(t)高度.

[用法]

这用于测量管的半径以进行进一步处理.可以计算半径(通过基本测角仪),这导致图像底部的方程.常数a0,y0,z0非常难以测量(它在复杂的机械内部),因此距离的测量精度是最小值0.1 mm和角度0.1 deg,甚至是有问题的.

[校准]

所以我决定尝试从机器本身完成的一组测量中计算这些参数(自动校准).所以我有已知半径的校准管r0.所有绿色参数都可以作为常量处理.现在我沿着y轴定位管子以尽可能多地覆盖手臂的角度.遗憾的是,该范围仅为20 degrees(对于当前的机器设置)记住测量a(t)的预设y(t)...作为n点数据集.这给了我n超越方程组.从此我尝试/猜测a0,y0,z0记住最佳解决方案的"所有"可能性(最接近r0)

[近似a0,y0,z0]

近似是基于这类矿井:

//---------------------------------------------------------------------------
class approx
    {
public:
    double a,aa,a0,a1,da,*e,e0;
    int i,n;
    bool done,stop;

    approx()            { a=0.0; aa=0.0; a0=0.0; a1=1.0; da=0.1; e=NULL; e0=NULL; i=0; n=5; done=true; }
    approx(approx& a)   { *this=a; …