هل من الممكن القيام منحنى جبري يصلح مع مجرد تمريرة واحدة من بيانات العينة؟

Question

أود أن أفعل جبري منحنى تناسب نقاط البيانات ثنائية الأبعاد، ولكن لأسباب مختلفة - ليس من الممكن حقا الحصول على الكثير من البيانات العينة في الذاكرة في وقت واحد، والتكرار من خلال كل ذلك عملية باهظة الثمن.

(السبب في ذلك هو أنه في الواقع أحتاج إلى تناسب الآلاف من المنحنيات بناء على في وقت واحد على غيغابايت من البيانات التي أقرأ القرص، وبالتالي فإن sloooooow).

لاحظ أن عدد المعاملات المتعددية سيكون محدودا (ربما 5-10)، لذلك سيكون مناسبا بالضبط غير مرجح للغاية، ولكن هذا جيد لأن أحاول العثور على نمط أساسي في البيانات مع كثيرا ضجيج عشوائي. أفهم كيف يمكن للمرء استخدام خوارزمية وراثية لتناسب المنحنى إلى مجموعة بيانات، ولكن هذا يتطلب الكثير من البيانات عبر بيانات العينة، وبالتالي ليس عمليا للتطبيق الخاص بي.

هل هناك طريقة لتناسب منحنى مع مرور واحد من البيانات، حيث يجب أن تكون الحالة التي يجب الحفاظ عليها من عينة إلى عينة ضئيلة؟

يجب أن أضيف أن طبيعة البيانات هي أن النقاط قد تكمن في أي مكان على المحور X بين 0.0 و 1.0، لكن قيم y ستكون دائما إما 1.0 أو 0.0.

لذلك، في Java، أبحث عن فئة مع الواجهة التالية:

public interface CurveFit {
   public void addData(double x, double y);
   public List<Double> getBestFit(); // Returns the polynomial coefficients
}

يجب ألا يحتاج الفصل الذي ينفذ إلى أن يحتاج إلى الكثير من البيانات في حقول مثيلها، ولا يزيد عن كيلوبايت حتى ملايين نقاط البيانات. هذا يعني أنه لا يمكنك فقط تخزين البيانات كما تحصل عليه للقيام بتمرير متعددة من خلاله لاحقا.

تعديل: اقترح البعض أن العثور على منحنى مثالي في تمريرة واحدة قد يكون مستحيلا، ولكن مناسبا مثاليا غير مطلوب، تماما كما هو قريب حيث يمكننا الحصول عليه في تمريرة واحدة.

قد تكون العظام العارية للنهج إذا كان لدينا طريقة للبدء بمنحنى، ثم طريقة لتعديلها للحصول عليها أقرب إلى نقاط بيانات جديدة لأنها تأتي - بشكل فعال من شكل نزول التدرج. من المأمول أن تكون البيانات الكافية (والبيانات تكون وفيرة)، نحصل على منحنى جيد جدا. ربما هذا يلهم شخص ما إلى حل.

Answer 1

أعتقد أنني وجدت الإجابة على سؤالي الخاص بناء على نسخة معدلة من هذه الشفرة. المهتمين، رمز Java الخاص بي هو هنا.

Answer 2

نعم، إنه إسقاط. بالنسبة

y = X beta + error        

حيث تكون المصطلحات المخفية هي ناقلات، و X هي مصفوفة، لديك ناقلات الحل

\hat{beta} = inverse(X'X) X' y

وفقا ل OLS. صفحة. أنت على الاغلب لا نريد حساب هذا مباشرة ولكن استخدام التحلل LR أو QR أو SVD. المراجع وفيرة في أدب الإحصاءات.

إذا كانت مشكلتك تحتوي على معلمة واحدة فقط (و X، وبالتالي، فإن هذا متجه أيضا)، فهذا يقلل من مجرد ترجمة من المنتجات المتقاطعة بين y و x.

Answer 3

إذا كنت لا تمانع في الحصول على خط مستقيم "منحنى"، فأنت بحاجة فقط ستة متغيرات لأي كمية من البيانات. إليك التعليمات البرمجية المصدرية التي تدخل في كتابي القادم؛ أنا متأكد من أنه يمكنك معرفة كيفية عمل فئة Datapoint:

الاستيفاء

#ifndef __INTERPOLATION_H
#define __INTERPOLATION_H

#include "DataPoint.h"

class Interpolation
{
private:
  int m_count;
  double m_sumX;
  double m_sumXX;  /* sum of X*X */
  double m_sumXY;  /* sum of X*Y */
  double m_sumY;
  double m_sumYY;  /* sum of Y*Y */

public:
  Interpolation();

  void addData(const DataPoint& dp);

  double slope() const;
  double intercept() const;

  double interpolate(double x) const;
  double correlate() const;
};

#endif // __INTERPOLATION_H

interpolation.cpp:

#include <cmath>

#include "Interpolation.h"

Interpolation::Interpolation()
{
  m_count = 0;
  m_sumX = 0.0;
  m_sumXX = 0.0;
  m_sumXY = 0.0;
  m_sumY = 0.0;
  m_sumYY = 0.0;
}

void Interpolation::addData(const DataPoint& dp)
{
  m_count++;
  m_sumX += dp.getX();
  m_sumXX += dp.getX() * dp.getX();
  m_sumXY += dp.getX() * dp.getY();
  m_sumY += dp.getY();
  m_sumYY += dp.getY() * dp.getY();
}

double Interpolation::slope() const
{
  return (m_sumXY - (m_sumX * m_sumY / m_count)) /
    (m_sumXX - (m_sumX * m_sumX / m_count));
}

double Interpolation::intercept() const
{
  return (m_sumY / m_count) - slope() * (m_sumX / m_count);
}


double Interpolation::interpolate(double X) const
{
  return intercept() + slope() * X;
}


double Interpolation::correlate() const
{
  return m_sumXY / sqrt(m_sumXX * m_sumYY);
}

Answer 4

لماذا لا تستخدم مخزن مؤقت الدائري لبعض الحجم الثابت (قل، آخر 1000 نقطة) وقم بتحويل المربعات الصلب المعيارية القائمة على التحلل QR إلى البيانات المخزنة؟ بمجرد ملء المخزن المؤقت، في كل مرة تحصل فيها على نقطة جديدة تحل محل أقدم وإعادة تناسبها. بهذه الطريقة لديك مجموعة عمل محادلة لا تزال لديها بعض محلية البيانات، دون كل تحديات معالجة البث المباشر (بلايم).

Answer 5

هل تحد من عدد معاملات متعددة الحدود (أي تركيب قوة أقصى من X في كثير الحدود)؟

إذا لم يكن الأمر كذلك، فأنت لا تحتاج إلى خوارزمية "أفضل تناسب" - يمكنك دائما تناسب نقاط البيانات N تماما إلى متعدد الحدود من المعاملات N.

ما عليك سوى استخدام المصفوفات لحل المعادلات المتزورية لعدم n غير معروف (معاملات N في كثير الحدود).

إذا كنت تقيد لعدد أقصى من المعاملات، فما هو ماكس الخاص بك؟

بعد تعليقاتك وتحرير:

ما تريده هو مرشح تمرير منخفض لتصفية الضوضاء، ولا يصلح متعدد الحدود إلى الضوضاء.

Answer 6

بالنظر إلى طبيعة بياناتك:

قد تكمن النقاط في أي مكان على المحور X بين 0.0 و 1.0، لكن قيم Y ستكون دائما إما 1.0 أو 0.0.

فأنت لا تحتاج حتى تمريرة واحدة، لأن هذين الخطين سوف يمر بالضبط من خلال كل نقطة:

• X = [0.0 ... 1.0]، Y = 0.0
• x = [0.0 ... 1.0]، Y = 1.0

اثنين من قطاعات الخط القصير، طول الوحدة، و كل نقطة يسقط على سطر واحد أو الآخر.

من المسلم به، خوارزمية للعثور على منحنى جيد مناسبة للنقاط التعسفية في تمريرة واحدة مثيرة للاهتمام، ولكن (بناء على سؤالك)، هذا ليس ما تحتاجه.

Answer 7

على افتراض أنك لا تعرف أي نقطة يجب أن تنتمي إليها المنحنى، شيء مثل هوغ تحويل قد تقدم ما تحتاجه.

تحول Hough هو تقنية تتيح لك تحديد الهيكل داخل مجموعة البيانات. استخدام واحد هو رؤية الكمبيوتر، حيث يسمح بتحديد سهلة من الخطوط والحدود داخل مجال البصر.

مزايا لهذا الموقف:

• كل نقطة تحتاج إلى اعتبار مرة واحدة فقط
• لا تحتاج إلى الاحتفاظ بنية بيانات لكل خط مرشح، مجرد هيكل واحد (معقد، متعدد الأبعاد)
• تجهيز كل سطر بسيط
• يمكنك التوقف عند أي نقطة وإخراج مجموعة من المباريات الجيدة
• لا تجاهل أي بيانات، لذلك لا يعتمد على أي محلية عرضية للمراجع
• يمكنك المتداول بين الدقة ومتطلبات الذاكرة
• لا يقتصر على التطابقات الدقيقة، ولكن سوف يبرز مباريات جزئية أيضا.

نهج

للعثور على يناسب مكعب، كنت تقوم بإنشاء مساحة هجو ثلاثية الأبعاد، حيث كنت تعرض لكل من نقاط بياناتك. النقاط الساخنة داخل مساحة هاوغ ستمنحك المعلمات للمكعب من خلال تلك النقاط.

Answer 8

تحتاج إلى الحل لنظام خطي مفرط. الأساليب الشعبية هي المعادلات العادية (لا ينصح عادة)، وعامل QR، وتحلل القيمة المفرد (SVD). ويكيبيديا لديها تفسيرات لائقة، trefethen و bau. جيد جدا. خياراتك:

1. التنفيذ خارج النواة عبر المعادلات العادية. هذا يتطلب المنتج A'A أين A لديه العديد من الصفوف أكثر من الأعمدة (لذلك النتيجة صغيرة جدا). المصفوفة A يتم تعريفها بالكامل بواسطة مواقع العينة حتى لا تضطر إلى تخزينها، وبالتالي الحوسبة A'A رخيص بشكل معقول (رخيص جدا إذا كنت لا تحتاج إلى ضرب الذاكرة لمواقع العقدة). مرة واحدة A'A يتم حسابها، يمكنك الحصول على الحل في مرحلة واحدة من خلال بيانات الإدخال الخاصة بك، ولكن الطريقة يمكن أن تكون غير مستقرة.

2. تنفيذ عاملات QR خارج النواة. Gram-Schmidt الكلاسيكية ستكون أسرع، ولكن عليك أن تكون حريصا على الاستقرار.

3. قم بذلك داخل النواة مع الذاكرة الموزعة (إذا كان لديك الأجهزة المتاحة). يمكن أن تفعل المكتبات مثل Plapack و Scalapack هذا، يجب أن يكون الأداء أفضل بكثير من 1. قابلية التوسع الموازي ليست رائعة، ولكنها ستكون على ما يرام إذا كانت حجم مشكلة أنك ستفكر حتى في القيام في المسلسل.

4. استخدم الأساليب التكرارية لحساب SVD. اعتمادا على الخصائص الطيفية لنظامك (ربما بعد الشرط المسبق)، يمكن أن يتوقف هذا بسرعة كبيرة ولا يتطلب التخزين من أجل المصفوفة (والتي في حالتك 5-10 أعمدة لكل منها حجم بيانات الإدخال الخاصة بك. مكتبة جيدة لهذا هو slowpc., ، عليك فقط العثور على منتج مصفوفة Vandermonde مع ناقل (لذلك تحتاج فقط إلى تخزين مواقع العينة). هذا قابل للتطوير جدا بالتوازي.